import java.util.*;

public class SortedLinkedList extends LinkedList {
	private Comparator theComparator;
	
	/**
	  * Default constructor with natural comparator
	  */
	public SortedLinkedList() {
		theComparator = null;
	}
	
	/**
	  * Default constructor with comparator parameter
	  */
	public SortedLinkedList(Comparator aComparator) {
		theComparator = aComparator;
	}

	/**
	  * Inserts the specified into this list in it's sorted position
	  * @param x is the element inserted
	  * @returns true
	  */
	public boolean add(Object x) {
		ListIterator itr = listIterator();
		boolean moreInList = true;
		while( (moreInList = itr.hasNext()) && compare(x,itr.next()) > 0 );
		// if at the end of the List insert the object
		if( !moreInList ) {
			itr.add(x);
			return true;
		} // end if
		itr.previous();
		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 comparator() {
		return theComparator;
	} // end comparator
	
	private int compare(Object A, Object B) {
		if( theComparator == null ) {
			return ((Comparable)A).compareTo(B);
		} else {
			return theComparator.compare(A,B);
		} // end if
	} // end compare
    
} // end SortedLinkedList