// TestRadixSort.java ปรับปรุง : 2548-06-09 ()
// เคล็ด : จับหลักหน่วยลงถัง 10 ถัง แล้วนำหลักสิบลง 10 ถึงอีก ไปเรื่อย ๆ
// โปรแกรมสำหรับ จัดเรียงข้อมูล แบบ Radix
// แหล่งอ้างอิง
//   http://www.thaiall.com/class
//   http://ww3.algorithmdesign.net/handouts/RadixSort.pdf
//   http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html
//   http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/radixsort.html (มี Animation)
//   http://www.cs.dal.ca/~prof2110/Tutorials/Tutorial08/tutorial08.html (ละเอียดมาก)
//   http://www.java2s.com/ExampleCode/Collections-Data-Structure/Sort-Search.htm
//
import java.lang.*;
class TestRadixSort {
  //LinkedList to keep track of numbers
  //based on radix 0 - 9
  private LinkedList[] l = {
    new LinkedList(), new LinkedList(),
    new LinkedList(), new LinkedList(),
    new LinkedList(), new LinkedList(),
    new LinkedList(), new LinkedList(),
    new LinkedList(), new LinkedList()
  };
  private int count; //array counter
  private int[] arr; //array contains data
  //initialize data structures
  TestRadixSort(int size) {
    arr = new int[size];
    count = 0;
  }
  //add data into array
  public void add(int num) {
    arr[count++] = num;
  }
  //sort array using radix sort algrithm
  private void sort() {
    //find maximum number in array
    int max = 0;
    for(int i = 0; i < arr.length; i++) {
      max = Math.max(max, arr[i]);
    }
    //find number of digits in maximum number
    //this is a number of passes through digits
    int digits = (int)Math.round((Math.log((double)max)/Math.log((double)10)));
    int index;
    for(int i = 1; i <= digits; i++) {
      index = 0;
      //put data into LinkedList based on radix
      //starting from least significant digit first
      //then second, ...
      for(int j = 0; j < arr.length; j++) {
        l[getRadix(arr[j], i)].enqueue(arr[j]);
      }
      //transfer partially sorted data in LinkedList
      //back into array for next passes
      for(int j = 0; j < l.length; j++) {
        while(!l[j].isEmpty()) {
          arr[index] = l[j].dequeue();
          index++;
        }
      }
    }
  }
  //return radix of a numver e.g.
  //first radix of 3476 is 6, second is 7 etc.
  private int getRadix(int number, int radix) {
    return (int)(number / Math.pow(10, radix - 1)) % 10;
  }
  //display data
  public void show() {
    System.out.print("(" + arr[0]);
    for(int i = 1; i < arr.length; i++) {
      System.out.print(", " + arr[i]);
    }
    System.out.println(")");
  }
  //test module
  public static void main(String[] args) {
    TestRadixSort rads = new TestRadixSort(5);
    rads.add(51);
    rads.add(46);
    rads.add(14);
    rads.add(35);
    rads.add(22);
    rads.show(); 
    rads.sort(); 
    rads.show(); 
  }
}
class LinkedList extends Object {
  private intNode start;
  private intNode end;
  private int length;     
  //Constructor
  LinkedList() {
    start = null;
    end = null;
    length = 0;
  }
  //Add an item to the end of the queue
  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 temp = start.value;
    intNode tempNode;
    tempNode = start;
    start = start.next;     //let start point to the next node
    tempNode = null;        //clear the first object
    return temp;
  }
  //returns true if its empty
  public boolean isEmpty() {
    return (length == 0);
  }
}
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;
}