import java.lang.Character;
/* 
 *  File: sortRadixRahmen.java
 */

/* 
 Beschreibt das Verhalten von Objekten, bei denen auf eine Ziffer
 zugegriffen werden kann 
*/
abstract class decomposable {
  /* Wertebereich fuer Indizes der Zeichen:  0 .. range - 1 */
  public abstract int range () ;
  
  /* Index eines Zeichens an Stelle i im Bereich 0 .. range - 1;
     -1, falls an Stelle i kein Zeichen ist */
  public abstract int zeichen (int i);
  
  /* Anzahl der Zeichen des Objektes */
  public abstract int laenge ();
  
}//abstract class decomposable




/*
 *  Ein Objekt mit einem string-Key, der die Grundlage 
 *  der zeichen-Operation darstellt
 *  Info-typ optional
 */  
class decomposableString extends decomposable {
  protected String s ; // key
	               // hier koennte noch ein Info-typ kommen

  decomposableString (String s){ this.s = s; }   // Konstruktor

  /* Wir betrachten Zeichenketten von Zeichen mit Unicode in [0 .. 127] */
  public int range () {
    return 128;
  }

  /*
     gib Zeichen i zurueck (nulltes Zeichen steht ganz links),
     falls vorhanden; ansonsten -1
  */
  public int zeichen (int stelle){
    if (stelle < s.length ()) {
      return new Character(s.charAt(stelle)).hashCode () % 128;
    }
    else { return -1; }
  }
  
  /* gibt die Laenge von s zurueck */
  public int laenge () {
    return s.length ();
  }


  String string () { return s; }           // Gibt Key zurueck

  
  /* statische Methode zur Erzeugung eines Arrays 
     von decomposableString-Objekten aus einem String-Array.
     Komponente 0 enthaelt Element mit key " "
  */ 
  static decomposableString [] array (String arr[]){
     decomposableString resultArr [] = new decomposableString [arr.length+1];
     resultArr [0] = new decomposableString (" ");
     for (int i = 0; i < arr.length; i++){
        resultArr [i+1] = new decomposableString (arr [i]);
     }
     return resultArr;
  }
  
  /* statische Methode zur Ausgabe eines Arrays 
     von decomposableString-Objekten
  */
  static void printArray (decomposableString arr[], int l, int r){
     for (int i = l ; i <= r; i++){
	 System.out.print (((decomposableString)arr[i]).string()+" ");
     }
     System.out.println ();
  }
}//class decomposableString


/*
   (Backward) Radix Sort 
 */
class radixSort {
   static void sort (decomposable A[]){
     int n = A.length-1;
     int m = A[0].range (); 
     list fach [] = new list [m+1];

     /* Initialisiere die Faecher */
     for (int i = 0; i <= m; i++) {
       fach[i] = new list ();
     }

     /* Berechne die maximale Laenge einer Zeichenkette */
     int max = 1;
     for (int i = 2; i <= n; i++) {
       if (A[i].laenge () > A[max].laenge ()) {max = i;}
     }

     /* Sortiere die Zeichenketten */
     for (int z = A[max].laenge () - 1; z >= 0; z--) {
       /*
	  Verteile A[1] .. A[n] nach Zeichen z auf fach[1] .. fach[m];
	  fach[0] enthaelt Zeichenketten, die kein z-tes Zeichen haben
       */
       for (int i = 1; i <= n; i++) {
	 fach [A[i].zeichen (z) + 1].append (A[i]);
       }
       
       /* Sammle die Zeichen wieder ein */
       int i = 0;
       for (int j = 0; j <= m; j++) {
	 while (! fach[j].isEmpty ()) {
	   A[++i] = (decomposable) fach[j].removeFirst ();
	 }
       }
     }
   }
} // class radixSort



/*
 *  Programm zum Testen von Sortieralgorithmen 
 */
public class sortRadixRahmen {
   public static void main(String args[]){
      String vec[] = {"15", "02", "43", "17", "04", "08", "47"};  
      if (args.length != 0) {
	 vec = new String [args.length];
	 for (int j = 0 ; j < args.length ; j++){
	    vec [j] = args [j];
	 }
      }

      decomposableString t[] = decomposableString.array (vec);

      decomposableString.printArray (t, 1, t.length-1);

      radixSort.sort(t);

      decomposableString.printArray (t, 1, t.length-1);
   }
}