/*
 * Optimizing the World's Worst Sorting Algorithm
 *
 * Branch-and-Bound to the rescue!
 *
 * World's worst sorting algorithm:  examine all possible permutations
 * of the array contents and select the one that has NO elements out
 * of order.  Note that this is an OPTIMAL method if the data are
 * already sorted:  n-1 comparisons to termination if the permutations
 * are examined as they are generated.
 *
 * Branch and bound:  as each permutation is being generated,
 * examine at position k whether each candidate contents introduces
 * an out-of-order situation.  If it does not, enter that state into
 * the work data structure to be permuted at position k+1.  By the time
 * the state pulled from the work data structure has k==size, the vector
 * associated with it must be sorted.
 *
 * Observed behavior:  if work is implemented as a stack, reversed data
 * are actually optimal, since that last state entered into the stack is
 * the one with the LAST entry moved into the k'th position.  On the
 * other hand, if the priority queue takes the longest vector first, and
 * enforces a queue discipline on equal priority one will approximate the
 * processing of the backtracking implementation and the sorted vector is
 * optimal.
 *
 * Author:  Timothy Rolfe
 */
import java.util.Queue;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.math.BigInteger;

public class BoundSort
{
   // Note that Vector makes available the add() method
   // --- Stack extends Vector
   private static class Stack<T> extends java.util.Stack<T>
   {  public T       poll()    { return pop();  }
      public boolean isEmpty() { return empty();  }
   }

   private static class State implements Comparable
   {  Comparable[] vect;
      int          posn,
                   serial;
      static int   lastNo = 0;
      static long  nObj = 0;

      private State (Comparable[] vect, int posn)
      {  this.posn = posn;
         this.vect = new Comparable[vect.length];
         System.arraycopy(vect, 0, this.vect, 0, vect.length);
         nObj++;
         serial = ++lastNo;
      }

      public int compareTo(Object o)
      {  State rt = (State)o;
         int   c1 = rt.posn - this.posn, // Reversed
               c2 = this.serial - rt.serial;

         return c1 == 0 ? c2 : c1;
      }
   }

   // Test whether x[posn] is correctly positioned w.r.t. x[posn-1]
   static boolean test ( Comparable[] x, int posn )
   {  if (posn == 0) return true;    // true if there IS no predecessor
      else           return x[posn-1].compareTo(x[posn]) <= 0;
   }

   static void swap ( Comparable[] x, int p, int q )
   {  Comparable tmp = x[p]; x[p] = x[q]; x[q] = tmp;  }

   // NEARLY the world's WORST sorting algorithm:
   //
   // Examine all permutations of elements, but trim the partial
   // states that cannot give a valid permutation
   static void boundSort ( Comparable[] x )
   {
      Stack<State> work = new Stack<State>();
//    Queue<State> work = new LinkedList<State>();
//    Queue<State> work = new PriorityQueue<State>();
      int size  = x.length;

      work.add ( new State(x, 0) );

      while ( !work.isEmpty() )
      {
         State test = work.poll();
         Comparable[] trial = test.vect;
         int          posn  = test.posn;

         if ( posn == size )
         {  System.arraycopy(trial, 0, x, 0, size);  return;  }

         for ( int k = posn; k < size; k++ )
         {//Swap next candidate into [posn]
            swap (trial, k, posn);
         // then test:  if success, enter this state into the work structure
            if ( test(trial, posn) )
               work.add( new State(trial, posn+1) );
         }
         // No need to undo the rotations
      }
      return;
   }

   // Completely randomize positions within x[] from [0] to [n-1]
   static void shuffle (Comparable[] x, int n)
   {  while ( n > 1 )
      {  int k = (int) (Math.random() * n--);

         swap (x, k, n);
      }
   }

   static public void main ( String[] args )
   {  Data    x[];      // Array to be sorted
      int     size,     // Requested size for x
              k;        // Loop variable
      BigInteger fact = BigInteger.ONE;
      long    nCmp;
      java.util.Scanner console = new java.util.Scanner(System.in);

      System.out.print ("Size:  ");
      if ( args.length == 0 )
         size = console.nextInt();
      else
      {  size = Integer.parseInt(args[0]);  System.out.println(size);  }

      x = new Data[size];
      for ( k = 0; k < size;  )
      {  x[k] = new Data(size - k);
         fact = fact.multiply(new BigInteger(Integer.toString(++k)));
      }

      System.out.println (size + " gives " + fact + " possible sequences.");

   // The Data objects are reversed by the for loop above
      nCmp = Data.nCompares();    // Zero out the counter
      boundSort(x);
      nCmp = Data.nCompares();    // Capture the comparison count
      System.out.println ("Reversed data.");
      for ( k = 0; k < size; k++ )
         System.out.print ("  " + x[k]);
      System.out.printf (" --- %d comparisons, %d objects\n", nCmp, State.nObj);

   // Completely randomize the data
      shuffle (x, size);
      nCmp = Data.nCompares();    // Zero out the counter
      boundSort(x);
      nCmp = Data.nCompares();    // Capture the comparison count
      System.out.println ("Random data.");
      for ( k = 0; k < size; k++ )
         System.out.print ("  " + x[k]);
      System.out.printf (" --- %d comparisons, %d objects\n", nCmp, State.nObj);

   // Data left sorted from previous run.
      nCmp = Data.nCompares();    // Zero out the counter
      boundSort(x);
      nCmp = Data.nCompares();    // Capture the comparison count
      System.out.println ("Sorted data.");
      for ( k = 0; k < size; k++ )
         System.out.print ("  " + x[k]);
      System.out.printf (" --- %d comparisons, %d objects\n", nCmp, State.nObj);
   }

   static class Data implements Comparable
   {  static private long nCompares = 0;
      private int value;
   
//    Default constructor
      Data ()
      {  value = 0;  }
   
//    Initializing constructor
      Data (int value)
      {  this.value = value;  }
   
//    Copy constructor
      Data (Data item)
      {  value = item.value;  }
   
      public void set(int value)
      {  this.value = value;  }
   
      public int  get()
      {  return value;  }
   
      public String toString()
      {  return Integer.toString(value);  }
   
      public int compareTo ( Object right )
      {  nCompares++;
         return this.value - ((Data)right).value;
      }
   
      static public long nCompares ()
      {  long temp = nCompares;
   
         nCompares = 0;
         return temp;
      }
   }
}
/* Specimen execution of the above code:

Size:  16
16 gives 20922789888000 possible sequences.
Reversed data.
  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16 --- 524272 comparisons.
Random data.
  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16 --- 357945 comparisons.
Sorted data.
  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16 --- 15 comparisons.
*/