public class TestList
{
   static final int nNodes = 15;

   static public void main ( String[] args )
   {
      List  check = new List();
      int   k;
      int[] val = new int[nNodes];

      for ( k = 0; k < nNodes; k++ )
      {
         val[k] = k+1;
         check.addFront(val[k]);
      }

      System.out.println("Using addFront");
      check.traverse();
      System.out.println();
      check.empty();

      for ( k = 0; k < nNodes; k++ )
         check.addBack(val[k]);

      System.out.println("Using addBack");
      check.traverse();
      System.out.println();
      check.empty();

      shuffle ( val, nNodes );
      for ( k = 0; k < nNodes; k++ )
         check.addFront(val[k]);

      System.out.println("Shuffled array");
      check.traverse();
      System.out.println();

      check.mergeRecur();
      System.out.println("After mergeRecur");
      check.traverse();
      System.out.println();
      check.empty();

      for ( k = 0; k < nNodes; k++ )
         check.addFront(val[k]);

      check.mergeIter();
      System.out.println("After mergeIter");
      check.traverse();
      System.out.println();
      check.empty();

      for ( k = 0; k < nNodes; k++ )
         check.addFront(val[k]);

      check.mergeNatural();
      System.out.println("After mergeNatural");
      check.traverse();
      System.out.println();
      check.empty();

      for ( k = 0; k < nNodes; k++ )
         check.addSorted(val[k]);

   // Force boundary cases for addSorted
      check.addSorted(0);
      check.addSorted(nNodes+1);
   // Confirm that head and tail references are still value
      check.addFront (-1);
      check.addBack  (nNodes+2);

      System.out.println("Testing boundary cases");
      check.traverse();
      System.out.println();
   }

   static void shuffle ( int[] x, int n )
   {
      int k, temp, j;

      while ( n > 1 )
      {
         k = (int) (Math.random() * n--);
      // Node post-decrement of n above.
         temp = x[n];
         x[n] = x[k];
         x[k] = temp;
      }
   }
}