import java.util.List;
import java.util.LinkedList;
import java.util.Comparator;

/* An instance of this class represents an indexed list whose elements
** are in ascending order with respect to the ordering defined by the
** Comparator provided at time of construction, referred to as the
** "resident" Comparator.  By "indexed" is meant that the manner in which
** list elements are referred to is by their ordinal position, or index,
** within the list (e.g., 0th, 1st, 2nd, etc.)
**
** Authors: R. McCloskey and <STUDENTS' NAMES>
** Date: April 2026
*/
public class OrderedIndexedList<T> {

   // instance variables
   // ------------------

   protected List<T> list;        // the elements of this list
   protected Comparator<T> comp;  // the "resident" Comparator

   // Class invariant:
   //   The order in which elements occur in this list is ascending
   //   according to the ordering defined by the resident Comparator.

   // constructor
   // -----------

   /* Establishes this list to be empty and to have the given Comparator
   ** as its "resident" Comparator; which determines the order in which
   ** the 
   */
   public OrderedIndexedList(Comparator<T> c) {
      this.list = new LinkedList<T>();
      this.comp = c;
   }

   // observers
   // ---------

   /* Returns the # of elements in this list.
   */
   public int size() { return list.size(); }

   /* Returns the k-th element of this list.
   ** pre: 0 <= k < size()
   */
   public T get(int k) { return list.get(k); }


   @Override
   public String toString() { return list.toString(); }

   public void printList() {
      System.out.println("List has size " + size());
      for (int i = 0; i != size(); i++) {
         System.out.printf("At position %2d: %s\n", i, get(i));
      }
   }

   // mutator
   // -------

   /* Inserts the specified item into this list at a position such that the
   ** list's ascending-orderedness (according to the resident Comparator)
   ** is preserved.
   */
   public void insert(T item) {
      int k = find(item);
      list.add(k, item);
   }


   // utilities
   // -------

   /* Reports whether or not the first item (itemA) is less than 
   ** the second (itemB), according to the resident Comparator.
   */
   protected boolean isLessThan(T itemA, T itemB) {
      return comp.compare(itemA, itemB) < 0;
   }

   /* Returns k, where (according to the resident Comparator) 
   ** k is the minimum value such that either k == size() or
   ** !isLessThan(get(k), item).  In other words, k is the
   ** smallest index such that the element at position k of this
   ** list is not less than the given item (according to the
   ** resident Comparator).
   */
   protected int find(T item) {
      return -1;   // STUB
   }

}