/**
 * A set of static list sorting methods that use ListIterators
 * to accomplish manipultions within the list.
 *
 * void selectSort(KWLinkedList)  clones the list and rebuilds from that
 * void insertSort(KWLinkedList)  clones the list and rebuilds from that
 * void mergeSort (KWLinkedList)  recursive use of clone and rebuild
 *
 * @author Timothy Rolfe
 */
import java.util.ListIterator;         // Used in sorts.

public class ListSort
{
/**
 * Apply the selection sort algorithm to a linked list.  This
 * implementation destroys the old list and generates a new one
 * in the linked list passed as a parameter.
 *
 * In the (remaining) old list, repeatedly find the smallest value.
 * Insert that at the BACK of the new list.  When the old list is
 * down to just one item remaining, do the move directly.
 *
 * @param work  Linked list to be sorted
 */
   public static void selectSort ( KWLinkedList work )
   {  KWLinkedList oldList  = work.clone();
      ListIterator finder;
      Comparable   maxValue;

      if ( oldList.size() < 2 )      // Empty or single-element list
         return;

      work.clear();     // Empty out the list to receive the new contents

      // When only one item remains, it is the smallest and goes first
      while ( oldList.size () > 1 )
      {  int maxIndex = 0;

         finder = oldList.listIterator(0);
         maxValue = (Comparable) finder.next();
         while ( finder.hasNext() )
         {  Comparable testValue = (Comparable) finder.next();

            if ( maxValue.compareTo(testValue) < 0 )
            {  maxValue = testValue;
               // We've just stepped PAST the item, so correct for that
               maxIndex = finder.nextIndex() - 1;
            }
         }
         // Note:  this generates an extra traversal
         finder = oldList.listIterator(maxIndex);
         maxValue = (Comparable) finder.next();
         finder.remove();  // Eliminate the element returned by finder.next()
         work.addFirst(maxValue);    // Add to the FRONT of the new list.
      }
      // Move the last value --- the smallest item
      finder = oldList.listIterator(0);
      maxValue = (Comparable) finder.next();
      finder.remove();      // not really required, given garbage collection
      work.addFirst(maxValue);
   }

/**
 * Apply the insertion sort algorithm to a linked list.  This
 * implementation destroys the old list and generates a new one
 * in the linked list passed as a parameter.
 *
 * Immediately move the first value into the new list.  Then
 * repeatedly remove values from the old list, find their correct
 * position within the new list, and add them at that position.
 *
 * @param work  Linked list to be sorted
 */
   public static void insertSort ( KWLinkedList work )
   {
      KWLinkedList oldList = work.clone();
      ListIterator oldIter = oldList.listIterator();
      Comparable   hold;

      if ( ! oldIter.hasNext() )            // Empty list.  Return.
         return;

      hold = (Comparable) oldIter.next();   // Pull first item
      if ( ! oldIter.hasNext() )            // One-item list.  Return
         return;

      work.clear();     // Empty out the list to receive the new contents

      work.addFirst(hold);                  // First entry in the new list
      oldIter.remove();

      while ( oldIter.hasNext() )
      {
         ListIterator finder = work.listIterator(0);

         hold   = (Comparable) oldIter.next();
         oldIter.remove();         // Explicit REMOVE this from the list.
         while ( finder.hasNext() )
         {
            Comparable test = (Comparable) finder.next();

            if ( test.compareTo(hold) > 0 )
            {
               finder.previous();  // Move past the in-position item
               break;
            }
         }
         finder.add(hold);
      }
   }

/**
 * Apply recursive merge sort to this linked list.  If the list is
 * larger than 1 element, divide it (with remove() from this list)
 * into two smaller lists, then recursively sort them and re-merge
 * the resulting lists
 *
 * @param work  Linked list to be sorted
 */
   public static void mergeSort ( KWLinkedList working )
   {
      KWLinkedList    left, right;
      ListIterator    iter = working.listIterator(0),
                      leftIter, rightIter;
      int size     = working.size(),
          sizeLeft = size/2, index;
      Comparable   leftValue, rightValue;

      if ( size < 2 ) return;

/*************** Split the list into two smaller lists ***************/

      left  = new KWLinkedList();

      for ( index = 0; index < sizeLeft; index++ )
      {
         left.addLast((Comparable)iter.next());
         iter.remove();
      }

      right = working.clone();    // The rest constitute the right list

      working.clear();            // Empty out for rebuilding

/*************** Recursively sort the two smaller lists ***************/

      mergeSort(left);  mergeSort(right);

/*************** Merge the two smaller lists ***************/

      leftIter   = left.listIterator(0);
      leftValue  = (Comparable) leftIter.next();
      rightIter  = right.listIterator(0);
      rightValue = (Comparable) rightIter.next();

      // Main loop:  both lists are non-empty
      while (leftValue != null && rightValue != null)
      {
         if (rightValue.compareTo(leftValue) < 0)
         {
            working.addLast(rightValue);
            if ( rightIter.hasNext() )
               rightValue = (Comparable) rightIter.next();
            else
               rightValue = null;
         }
         else
         {
            working.addLast(leftValue);
            if ( leftIter.hasNext() )
               leftValue = (Comparable) leftIter.next();
            else
               leftValue = null;
         }
      }

      // Clean-up:  we know which list is empty
      if ( leftValue == null )    // Right list is not empty
      {
         working.addLast(rightValue);

         while ( rightIter.hasNext() )
            working.addLast((Comparable) rightIter.next());
      }
      else                        // Left list is not empty
      {
         working.addLast(leftValue);

         while ( leftIter.hasNext() )
            working.addLast((Comparable) leftIter.next());
      }
   }

   // Method mimicking Collections.sort( List )
   // As specified in the Java API documentation for Collections.sort
   //
   //    This implementation dumps the specified list into an array,
   //    sorts the array, and iterates over the list resetting each
   //    element from the corresponding position in the array.
   //
   public static void sort( KWLinkedList list )
   {
      Comparable[] array = new Comparable[list.size()];
      ListIterator listIter = list.listIterator();
      int          k = 0;

      array = list.toArray(array);

      java.util.Arrays.sort(array);

      while ( listIter.hasNext() )
      {
         listIter.next();
         listIter.set(array[k++]);
      }
   }
}