// OO-Loesung der Aufgabe: Mit Klasse ArrayHandler
// wird ein Abstrakter Datentyp eingeführt, der
// Arrays kapselt. Mit pushElement() wird ein Element 
// hinzugefügt.
// Mit sort() [enthält den Quicksort - Algorithmus aus
// der Vorlesung] wird der Array sortiert. Mit search
// kann gesucht werden.
//
// Die Klasse hat den Nachteil, dass die Anzahl der 
// Array-Elemente fix ist. Dies führt uns dann auf natürliche 
// Weise zu Listen in den nächsten Vorlesungen.
//
class ArrayHandler {


    // Attribut a (der Array auf dem operiert wird) wird
    // erst bei Instantiierung des Objektes angelegt.
    int a[];

    // Anzahl der Elemente, die bereits eingefügt wurden
    int numElems;

    // Merker, ob der Array schon/noch sortiert ist
    boolean isSorted;

    public ArrayHandler(int arraySize) {

	a = new int[arraySize];
        numElems = 0;
        isSorted = false;
        
    }

//---------------------------------------------------------------------------
// füge ein Element hinzu, solange noch Platz ist
//-------------------------------------------------------------------------
   
    public void pushElement(int value) {

	if ( numElems < a.length ) {
	    a[numElems] = value;
            numElems = numElems + 1;
            isSorted = false;
	}
	else {
	    System.out.println("Array enthält schon " + numElems + " Elemente");
	}

    }

//---------------------------------------------------------------------------
    // Binäre Suche - analog zu BinSearch2, aber jetzt 
    // als eine dem Objekt zugeordnete - private, NICHT statische Methode
//---------------------------------------------------------------------------
    int binsearch(int ug, int og, int value) {


/* 
   Hier steht Euer  Loesungsverfahren
*/
	
    }

//-----------------------------------------------------------------------
    // Implementierung des Quicksort Algorithmus
//----------------------------------------------------------------------
    
// suche einen Schluesselwert in range(a), der nicht das kleinste Element ist
    //PRE: ug, og IN { 0..a.length - 1 } 
    int findPivot(int ug, int og) {

	int firstKey = a[ug];

	for (int iCnt = ug+1; iCnt <= og; iCnt++) {

	    if ( firstKey < a[iCnt] ) 
                return iCnt;
	    else if ( a[iCnt] < firstKey ) 
		return ug;

	}

        // alle a[j] fuer j in {ug..og} sind identisch, d.h.
        // FORALL i IN {ug..og} . a[i] = a[ug]
        return -1;

    }
    //POST: (findPivot(ug,og) = -1 IMPLIES  
    //                    FORALL i IN {ug..og} . a[i] = a[ug])
    //      AND
    //      (findPivot(ug,og) >= 0 IMPLIES
    //                    (findPivot(ug,og) <= og AND 
    //                    EXISTS i IN {ug..og} . a[i] < a[findpivot(ug,og)]))  
    //      AND findPivot(ug,og) IN { -1, ug..og}



    // vertausche die Array-Elemente an den Indizes i,j
    //PRE: i,j IN { 0..a.length -1 } 
    void swap(int i, int j) {

	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;

    }
    //POST: a[i] = a[j]@PRE AND a[j] = a[i]@PRE


    // der Partitionierungsalgorithmus
    //PRE: ug,og IN { 0..a.length-1 }
    //     AND
    //     EXISTS i IN {ug..og}. a[i] = pivot
    //     AND
    //     EXISTS j IN {ug..og}. a[j] < pivot


    int partition(int ug, int og, int pivot) {

	int links = ug;
	int rechts = og;

	do {
            swap(links,rechts);
	    while ( a[links] < pivot ) links = links + 1;
            while ( a[rechts] >= pivot ) rechts = rechts - 1;
            

	} while ( links <= rechts );

	return links;

    }
 //POST: partition(ug,og,pivot) IN {ug..og}
 //      AND
 //      FORALL i IN {ug..partition(ug,og,pivot)- 1} . a[i] < pivot
 //      AND
 //      FORALL j in {partition(ug,og,pivot)..og} . a[j] >= pivot

 

    void quicksort(int ug, int og) {

	int pivot;
	int pivotindex;
	int k;

	pivotindex = findPivot(ug,og);

	if ( 0 <= pivotindex ) {

	    pivot = a[pivotindex];

	    k = partition(ug,og,pivot);

	    quicksort(ug,k-1);
	    quicksort(k,og);

	}

    }


//---------------------------------------------------------------------------

    // oeffentliches Interface, um das Sortieren anzustossen

//---------------------------------------------------------------------------

    public void sort() {

	quicksort(0,numElems - 1);

	isSorted = true;

    }

//---------------------------------------------------------------------------
     
     // hier das oeffentliche Interface, um die Such-Methode aufzurufen

//---------------------------------------------------------------------------

    public int search(int value) {

	if ( ! isSorted ) {
	    System.out.println("Array-Objekt ist noch nicht sortiert!");
            return -1;
	}
	return binsearch(0,numElems -1,value);

    }

//---------------------------------------------------------------------------

    // hier das oeffentliche Interface, um die print-Methode aufzurufen

//---------------------------------------------------------------------------

    public void print() {

	for (int iCnt = 0; iCnt < numElems; iCnt++ ) 
             System.out.println("a[" + iCnt + "] = " + a[iCnt]);

    }

}






class BinSearch3 {

    public static void main(String args[]) {

	int value = 779;
	ArrayHandler obj1 = new ArrayHandler(10);

	obj1.pushElement(666);
	obj1.pushElement(2);
	obj1.pushElement(33);
	obj1.pushElement(444);
	obj1.pushElement(777);
	obj1.pushElement(778);
	obj1.pushElement(779);
	obj1.pushElement(779);
	obj1.pushElement(780);
	obj1.pushElement(555);

	obj1.sort();

        obj1.print();

	System.out.println("Wert " 
			   + value 
			   + " findet sich in obj1, Index "
			   + obj1.search(value));


    }


}