/* 
 *  File: sortRahmen.java
 */

/* 
 *  Beschreibt das Verhalten "vergleichbarer" Objekte
 */
abstract class comparable {
   public abstract boolean equal        (comparable o);
   public abstract boolean greater      (comparable o);
   public          boolean less         (comparable o){
      return o.greater(this);
   }
   public          boolean greaterEqual (comparable o){
      return !less(o);
   }
   public          boolean lessEqual    (comparable o){
      return this.less(o) || this.equal(o);
   }
   public abstract void    minKey       ();
}//abstract class comparable

/*
 *  Hilfs-Klasse array, dient zum Vertauschen 
 *  von zwei Eintraegen in beliebigem Array von Objekten
 */
class array {
   public static void swap (Object arr[], int i, int j){
      Object o = arr[i]; arr[i] = arr[j]; arr[j] = o;
   }
}


/*
 *  Ein Objekt mit einem int-Key, der die Grundlage 
 *  der Vergleiche darstellt
 *  Info-typ optional
 */  
class comparableInt extends comparable {
   protected int i ; // key
	             // hier koennte noch ein Info-typ kommen
   comparableInt (int i){ this.i = i; }   // Konstruktor
   /* Implementierung der abstact-en Vergleiche aus der Superklasse */
   public boolean equal (comparable o){
      return i == ((comparableInt)o).i;
   }
   public boolean greater (comparable o){
      return i >  ((comparableInt)o).i;
   }
   public void minKey (){
      this.i = Integer.MIN_VALUE;
   }
   int intValue() { return i; }           // Gibt Key zurueck
   /* statische Methode zur Erzeugung eines Arrays 
      "vergleichbarer" comparableInt-Objekte aus einem int-Array.
      Komponente 0 enthaelt Element mit key 0
   */
   static comparableInt [] array (int arr[]){
      comparableInt resultArr [] = new comparableInt [arr.length+1];
      resultArr [0] = new comparableInt (0);
      for (int i = 0; i < arr.length; i++){
	 resultArr [i+1] = new comparableInt (arr [i]);
      }
      return resultArr;
   }
   /* statische Methode zur Ausgabe eines Arrays 
      "vergleichbarer" comparableInt-Objekte
   */
   static void printArray (comparable arr[]){
      for (int i = 1 ; i < arr.length; i++){
	 System.out.print (((comparableInt)arr[i]).intValue()+" ");
      }
      System.out.println ();
   }
}//class comparableInt

/*
 *  Quicksort, der seinem Namen Ehre macht, nach C.A.R. Hoare 
 */
class quickSort {
   /* sortiert das ganze Array */
   static void sort (comparable arr[]){
      arr [0].minKey();     // Stopper bekommt kleinsten Schluessel
      sort (arr, 1, arr.length-1);
   }
   /* sortiert das Array zwischen den Grenzen l und r */
   static void sort (comparable arr[], int l, int r){
      if (r > l){
	 int i = l-1;                 // linker  Zeiger auf Array
	 int j = r;                   // rechter Zeiger auf Array
	 comparable p = arr [r];      // das Pivot-Element
	 while (true){                // "Endlos"-Schleife
	    do i++; while (arr[i].less(p));
	    do j--; while (arr[j].greater(p));
	    if (i >= j) break;        // Abbruch der Schleife 
	    array.swap (arr, i, j);
	 }
	 array.swap (arr, i, r);
	 sort (arr, l, i-1);
	 sort (arr, i+1, r);
      } // if (r > l)
   }
}

class insertionSort{
     static void sort (comparable arr[]) {
         for (int i = 2; i < arr.length; i++) {
            comparable temp = arr[i];
            int j = i - 1;
            while (j >= 1 && arr[j].greater(temp)) {
                arr[j+1] = arr[j];
                j--;
            }
          arr[j+1] = temp;
	 }
    }
} // class InsertionSort
  

/*
 *  Programm zum Testen von Sortieralgorithmen 
 */
public class sortRahmen {
   public static void main(String args[]){
      int vec[] = {15, 2, 43, 17, 4, 8, 47}; // "Standard"-Array 
      if (args.length != 0) {
	 vec = new int [args.length];
	 for (int j = 0 ; j < args.length ; j++){
	    vec [j] = Integer.valueOf(args[j]).intValue();
	 }
      }

      /* t[0].i = 0 wird als Stopper verwendet */
      comparableInt t[] = comparableInt.array (vec);

      comparableInt.printArray (t);

      insertionSort.sort(t);

      comparableInt.printArray (t);
   }
}