/** RadixSort. <br />
 *  <br />
 *  By: Alvin Raj, 12 August 2002<br />
 *  <br />
 *  Modif. 15.11.2005, Albrecht Weinert (a-weinert.de) :<br />
 *  {@link SortApplet.SortAlgorithm} + Kleinigkeiten.<br />  
 *  <br />
 *  @author   Albrecht Weinert
 *  @version  V.161, 28.05.2011
 */
public final class RadixSortAlgorithm extends SortApplet.SortAlgorithm {

// for each of the 10 digits
   private LinkedQueue[] queues = {
       new LinkedQueue(),  //0
       new LinkedQueue(),  //1
       new LinkedQueue(),  //2
       new LinkedQueue(),  //3
       new LinkedQueue(),  //4
       new LinkedQueue(),  //5
       new LinkedQueue(),  //6
       new LinkedQueue(),  //7
       new LinkedQueue(),  //8
       new LinkedQueue() }; //9

   // Assumes all positive integers
   // numbDigits is the number of digits in the largest number
   void sort(int[] a, int numDigits) {
      int arrayPos;
      // i is the radix
      for (int i = 1; i <= numDigits; ++i) {
         if (stopRequested)  return; // Abbruch
         arrayPos = 0;
         // Put values into queues according to radix
         // least significant digit first, then second,...
         // first pass sorts on least significant digit
         for (int j = 0; j < a.length; j++) {
            queues[getRadix(a[j], i)].enqueue(a[j]);
            pause(-1, j); // JH
         }
         // Collect the queues and put them back into the array
         // queues contain partially sorted lists after first
         // pass -- moving to next significant digit will
         // maintain this ordering.
         for (int j = 0; j < queues.length; ++j) {
            while(!queues[j].isEmpty()) {
               a[arrayPos] = queues[j].dequeue();
               arrayPos++;
            }
            pause(-1, arrayPos);
         }
      }
   } // sort(int[], int)
   
   @Override void sort(int[] a) {
      // Find the largest entry in a[]
      int max = 0;
      int maxIndex = 0;  // JH
      for (int i = 0; i < a.length; ++i) {
         if (max < a[i]) {
            if (stopRequested)  return; // Abbruch
            max = a[i];
            maxIndex = i; // JH
            pause(maxIndex, i); // JH
         }
      }
      
      int numDigits = 1;
      int temp = 10;
      // compute the max number of digits
      // JH: this could be more easily be computed by using
      //     numDigits = (int) log(base10, max)
      while (true) {
         if (max >= temp) {
            numDigits++;
            temp *= 10;
         }
         else
            break;
      }
      
      //call the sort
      sort(a, numDigits);
   } // sort(int[])
   
   //returns the radix of the given number
   //EG:
   //2nd radix of 79981 is 8
   //1st radix of 79981 is 1
   public static int getRadix(int number, int radix) {
      return (int)(number / Math.pow(10, radix-1)) % 10;
   }
   
// =====================================================================
   
   public final static class LinkedQueue extends Object {
      private IntNode start;
      private IntNode end;
      private int length;  //number of elements
      
/** Add an item to the end of the queue. <br /> */
      public void enqueue(int num) {
         ++length;   //increment the number of objects
         
         //Create new node with given info
         IntNode temp = new IntNode(num);
         
         //If this is the first time, then do this
         if (start == null) {
            start = temp;  //make start = to this
            end = start;   //start and end point to the same node
         }  else {
            //make the new node's next pointer
            //point to the end
            end.next = temp;
            //make start point to the new object
            end = temp;
         }
         temp = null;
      }
      
      //Dequeue -- returns the integer in the intNode
      //From the front of the queue
      //Assumes that the queue is not empty
      public int dequeue() {
         --length;
         int ret = start.value;
         start = start.next;  //let start point to the next node
         return ret;
      }
      
      //returns true if its empty
      public boolean isEmpty() {
         return (length == 0);
      }
      
   } // LinkedQueue         =============================================
   
   public final static class IntNode extends Object {
      
      IntNode(int a) {
         value = a;
         next = null;
         prev = null;
      }
      
      IntNode() {
         next = null;
         prev = null;
         value = 0;     //sets value to zero if no value is explicitly given
      }
      
      public int value;
      
      public IntNode next;
      public IntNode prev;
      
   } // class IntNode   =================================================
   
} // class RadixSort