import java.util.LinkedList;
import java.util.Comparator;
import java.util.ListIterator;

public class SortedLinkedList<T extends Comparable<T>> extends LinkedList<T> {
    private Comparator<T> theComparator;
    
    /**
     * Default constructor with natural comparator
     */
    public SortedLinkedList() {
        theComparator = null;
    }
    
    /**
     * Default constructor with comparator parameter
     */
    public SortedLinkedList(Comparator<T> aComparator) {
        theComparator = aComparator;
    }
    
    /**
     * Inserts the specified into this list in it's sorted position
     * @param x is the element inserted
     * @returns true if the list changes
     */
    public boolean add(T x) {
        ListIterator<T> itr = listIterator();
        while( itr.hasNext() ) {
            T save = itr.next();
            // if equal do not add.
            if( compare(x,save) == 0 ) return false;
            // if found the spot back up, add and return
            if( compare(x, save) < 0 ) {
                itr.previous();
                itr.add(x);
                return true;
            } // end if
        } // end while
        // add at end
        itr.add(x);
        return true;
    } // end add
    
    /**
     * Inserts the specified into this list in it's sorted position
     * @param x is the element inserted
     * @returns true
     */
    
    // Another solution
/*	public boolean add(Object x) {
                ListIterator itr = listIterator();
                boolean moreInList = true;
                Object save = null;
                while( (moreInList = itr.hasNext()) && compare(x,itr.next()) > 0 );
                if( moreInList ) {
                        save = itr.previous();
                } // end if
                if( moreInList && compare(x,save) == 0 ) return false;
                itr.add(x);
                return true;
        } // end add
 */
    /**
     * Returns the comparator associated with this sorted list,
     * or null if it uses its elements' natural ordering.
     * @return the comparator associated with this sorted list,
     * or null if it uses its elements' natural ordering.
     */
    public Comparator<T> comparator() {
        return theComparator;
    } // end comparator
    
    private int compare(T left, T right) {
        if( theComparator == null ) {
            return left.compareTo(right);
        } else {
            return theComparator.compare(left,right);
        } // end if
    } // end compare
    
} // end SortedLinkedList