Radix Sort - Java Solution
(see the C++ counterpart)
import java.io.*;
import java.util.*;
class BigNumber
{
int number;
public BigNumber (int x) { number = x; }
public int value() { return number; }
public void display() { System.out.print(number + " "); }
}
class Cell
{
Object item;
Cell next;
public Cell (Object itm, Cell nxt) { item = itm; next = nxt; }
public void setNext(Cell nxt) { next = nxt; }
public Cell getNext() { return next; }
public Object getItem() { return item; }
}
class Queue
{
Cell tail;
public Queue () { tail = null; }
public void enqueue(Object obj)
{
Cell h;
if (obj == null) return;
if (tail == null)
{
tail = new Cell(obj, null);
tail.setNext(tail);
}
else
{
tail.setNext(new Cell(obj, tail.getNext()));
tail = tail.getNext();
}
}
public Object dequeue()
{
Object t;
if (tail == null) return null;
Cell ptr = tail.getNext();
t = ptr.getItem();
if (ptr != tail)
tail.setNext(ptr.getNext());
else
tail = null;
return t;
}
public void append(Queue q)
{
Cell ptr;
if (tail == null) tail = q.trailer();
else
if (!q.empty())
{
ptr = q.trailer().getNext();
q.trailer().setNext(tail.getNext());
tail.setNext(ptr);
tail = q.trailer();
}
}
public Cell trailer() { return tail; }
public boolean empty() { return tail == null; }
public void display()
{
Cell t;
if (tail == null) { System.out.println("(empty)"); return; }
for (t = tail.getNext() ; t != tail ; t = t.getNext())
((BigNumber)t.getItem()).display();
((BigNumber)tail.getItem()).display();
System.out.println();
}
}
public class Radix
{
static int GetDigit(long number, long place)
{
for (long i=0 ; i < place ; i++) number /= 10;
return (int)(number % 10);
}
static int ReadData(Queue q, String filename)
{
BigNumber number;
int count=0;
try
{
DataInputStream is = new DataInputStream(new FileInputStream(filename));
while (true)
{
String s = is.readLine();
try
{
StringTokenizer t = new StringTokenizer(s," ");
q.enqueue(new BigNumber(Integer.parseInt(t.nextToken())));
count++;
}
catch (NullPointerException e){ break; }
}
}
catch (IOException e) {}
return count;
}
public static void main (String argv[])
{
Queue q = new Queue();
Queue p[] = new Queue[10];
BigNumber numb;
int count=0, i, j;
count = ReadData(q, argv[0]);
for (j=0 ; j < Integer.parseInt(argv[1]) ; j++)
{
for (i=0 ; i < 10 ; i++) p[i] = new Queue();
for (i=0 ; i < count ; i++)
{
numb = (BigNumber)q.dequeue();
p[GetDigit(numb.value(), j)].enqueue(numb);
}
for (i=0 ; i < 10 ; i++) q.append(p[i]);
}
q.display();
}
}