// This program tests a subroutine, orderedInsert, that inserts
// a new item into a sorted list, at its correct position in
// the sorted order.  In this program, the command line arguments
// are put into the list.  When the list is printed, the arguments
// are in lexicographic order.  For example, for the command line:
//
//   java ListInsert cat zebra dog elephant dog tiger tiger aardvark frog
//
// the output is
//
//   [aardvark, cat, dog, dog, elephant, frog, tiger, tiger, zebra]


import java.util.List;
import java.util.LinkedList;
import java.util.ListIterator;


public class ListInsert {

   public static void main(String[] args) {
      List list = new LinkedList();
      for (int i = 0; i < args.length; i++)
         orderedInsert(list,args[i]);
      System.out.println(list);
   }


   static void orderedInsert(List list, Comparable newItem) {

          // Precondition:  The items in list are sorted into ascending
          //                order, according to the compareTo method.
          //                newitem.compareTo(item) must be defined for
          //                each item in the list.
          //
          // Postcondition: newItem has been added to the list in its
          //                correct postion, so that the list is still
          //                sorted into ascending order.

      ListIterator iter = list.listIterator();

      // Move the iterator so that it points to the position where
      // newItem should be inserted into the list.  If newItem is
      // bigger than all the items in the list, then the while loop
      // will end when iter.hasNext() becomes false, that is, when
      // the iterator has reached the end of the list.

      while (iter.hasNext()) {
         Object item = iter.next();
         if (newItem.compareTo(item) <= 0) {
               // newItem should come BEFORE item in the list.
               // Move the iterator back one space so that
               // it points to the correct insertion point,
               // and end the loop.
            iter.previous();
            break;
         } 
      }

      iter.add(newItem);

   } // end orderedInsert()

} // end class ListInsert