/*  This class implements a specific case of a radix sort.  It
    does a base 10 radix sort on an array of 100 random integers in 
    the range [0..1000).

    It uses the Queue class to implement the sorting buckets.

    H. Conrad Cunningham, 30 October 1996 
*/

public class RadixSort
{
    public static final int BASE   = 10;
    public static final int DIGITS = 3;
    public static final int RANGE  = 1000; // 10^2
    public static final int N      = 100;

    public static void distribute (int base, int digit, 
				   Integer[] val, Queue[] q)
    /*  Pre:   0 < base:    the base for the radix sort of integers
               0 <= digit:  the digit, from the right, on which to distribute
               val:  the array of Integer objects to the distribute
               q:  the output array of queues to hold distribution
        Post:  The queues in q contain the values from 'val'.  A value is 
               distributed to a queue according to the value of the selected
               'digit'.  Objects having the same value for the selected digit 
               are kept in the same relative order. 
	Note:  This method should be generalized to handle objects other
	       than Integer elements of val.  Perhaps define a Java interface
	       with methods to extract the "digits".
    */
    {   if (base <= 0 || digit < 0)
        {   System.out.println
	        ("ERROR.  In distribute, base and digit arguments are "
		 + base + " and " + digit + ", repectively.");
	    return;
	}
        if (q.length != base)
        {   System.out.println
	        ("ERROR.  In distribute, the base (" + base +
		 ") and number of queues (" + q.length + ") are not equal.");
	    return;
	}

        for (int i = 0; i < val.length; i++)
        {   int v = val[i].intValue();     // isolate selected digit
	    for (int j = 0; j < digit; j++)
	        v = v / base;
	    v = v % base;
	    q[v].enqueue(val[i]);
	}
    }

    public static void collect(Object[] val, Queue[] q)
    /*  Pre:   val must be sufficiently large to hold all of the values
               in the queues in array q.
        Post:  val contains all the elements from the queues input in q, in 
               the same order as initially in q (that is, q[0] from front to 
               back, then q[1], etc.).  All the queues in the output q are
               empty.
    */
    {   int l = 0;                        // compute total number of objects
	for (int i = 0; i < q.length; i++)
	    l = l + q[i].length();

	if (l > val.length)
	{   System.out.println
	        ("ERROR.  In collect, the size of the value array (" +
		 val.length + ") is too small to hold the queued data items ("
                 + l + ").");
	    val = null;
	    return;
	}

	int j = 0;
	for (int i = 0; i < q.length; i++)
            for ( ; !q[i].empty(); q[i].dequeue())
	    {   val[j] = q[i].front();
		j++;
	    }
    }

    public static void main (String[] args)
    /*  Pre:   true
        Post:  Does a base BASE radix sort on an array of N random integers 
               in the range [0..RANGE) and prints the resulting array.
    */
    {   Integer[] val = new Integer[N];
        Queue[] q     = new Queue[BASE];

        for (int i = 0; i < N; i++)
	    val[i] = new Integer( (int)(Math.random() * RANGE) );

	System.out.println("-------------------");
	System.out.println("Values before sort.");
	for (int i = 0; i < val.length; i++)
            System.out.println(val[i].intValue());

	for (int i = 0; i < BASE; i++)
	    q[i] = new Queue(N);

	for (int i = 0; i < DIGITS; i++)
	{   distribute(BASE, i, val, q);
	    collect(val, q);
	}

	if ( val != null)
	{   System.out.println("-------------------");
	    System.out.println("Values after sort.");
	    for (int i = 0; i < val.length; i++)
                System.out.println(val[i].intValue());
        }
    }
}