package testate;

import java.applet.*;
import java.awt.*;
import java.awt.event.*;
import java.lang.Thread;

public class SortTestApp extends java.applet.Applet implements ActionListener, ItemListener, Runnable {
    
    int counter=0;
    int xOffset, yOffset;
    int[] array, backup;
    Graphics g;
    Thread t1;
    boolean change=false;
    boolean stopThread=false;
    // Animationsgeschwindigkeit:
    int delay=20; Choice speed;
    String[] animation={"1","5","10","20","50","100"};
    // Sortieralgorithmen:
    int sortCode=0; Choice sort;
    String[] sortAlg={"BubbleSort", "InsertionSort", "MergeSort", "QuickSort", "SelectionSort"};
    // Feldgroesse:
    int num=500; Choice feldSize;
    String[] feldGroesse={"50","100","200","300","400","500"};
    // Maximalwert des Feldes:
    int max=500; Choice feldMax; 
    String[] feldMaximum={"50","100","200","300","400","500"};
    // Eigenschaft des Feldes:
    int typ=0; Choice feldTyp;
    String[] feldSortierung={"unsortiert", "absteigend", "aufsteigend"};
    // Eigenschaft des Startknopfes:
    Button start;
    String[] startKnopf={"Start","Stop"};
    
    // Grafische Feldausgabe:
    
    public void drawArray(Graphics g) {
        drawArray(g, -1, -1, -1);
    }
    
    public void drawArray(Graphics g, int wert) {
        drawArray(g, wert, -1, -1);
    }
    
    public void drawArray(Graphics g, int wert1, int wert2) {
        drawArray(g, wert1, wert2, -1);
    }
    
    public void drawArray(Graphics g, int wert1, int wert2, int wert3) {
        for (int index=0; index<array.length; index++) {
            // loescht "veraltete" Darstellungspunkte:
            if (backup[index]!=array[index]) {
                g.setColor(Color.lightGray);
                g.fillOval(xOffset+backup[index], (yOffset+500-index), 3, 3);
            }
            // entsprechende Farbausgabe:
            if ((wert1>=0)&&(index==wert1)) {
                g.setColor(Color.red);
            }
            else if ((wert2>=0)&&(index==wert2)) {
                g.setColor(Color.blue);
            }
            else if ((wert3>=0)&&(index==wert3)) {
                g.setColor(Color.green);
            }
            else {
                g.setColor(Color.black);
            }
            g.fillOval(xOffset+array[index], (yOffset+500-index), 3, 3);
        }
        // Kopie für Kontrolle ob "veraltet":
        backup=copyArray(array);
        // Pause:
        try {
            Thread.sleep(delay);
        }
        catch (InterruptedException e) {
        }
        counter++;
    }
    
    // Ausgabefeld:
    
    public void paint(Graphics g) {
        // Statuszeile:
        getAppletContext().showStatus("Maximum: "+max+"     Anzahl: "+num+
            "     Feldtyp: "+feldSortierung[typ]+"     Geschwindigkeit: "+delay+
            "     Sortieralgorithmus: "+sortAlg[sortCode]);
        // Ausgabeposition bestimmen:
        getOffsets();
        // Ausgabefenster:
        g.drawRect(xOffset-4,yOffset-4,508,508);
        g.setColor(Color.lightGray);
        g.fillRect(xOffset-3,yOffset-3,507,507);
        drawArray(g);
    }
    
    // sorgt fuer die Zentrierung der Ausgabe:
    
    void getOffsets(){
        xOffset=(getSize().width - 508) / 2;
        yOffset=((getSize().height - 508) / 2) - 10;
    }
    
    // Appletinitialisierung:
    
    public void init() {
        // Größe des Bildschirmes bei Start des Programms:
        resize(600, 650);
        // vordefiniertes Layout:
        setLayout(new BorderLayout() );
        Panel p1=new Panel();
        p1.setBackground(Color.white);
        p1.setLayout(new FlowLayout(FlowLayout.CENTER));
        add("North", p1);
        // Maximum des zu sortierenden Feldes auswählen:
        feldMax=new Choice();
        for (int index=0; index<feldMaximum.length; index++) {
            feldMax.add(feldMaximum[index]);
        }
        feldMax.addItemListener(this);
        p1.add(feldMax);
        // Größe des zu sortierenden Feldes auswählen:
        feldSize=new Choice();
        for (int index=0; index<feldGroesse.length; index++) {
            feldSize.add(feldGroesse[index]);
        }
        feldSize.addItemListener(this);
        p1.add(feldSize);
        // Art des zu sortierenden Feldes:
        feldTyp=new Choice();
        for (int index=0; index<feldSortierung.length; index++) {
            feldTyp.add(feldSortierung[index]);
        }
        feldTyp.addItemListener(this);
        p1.add(feldTyp);
        // Sortieralgorithmus auswaehlen:
        sort=new Choice();
        for (int index=0; index<sortAlg.length; index++) {
            sort.add(sortAlg[index]);
        }
        sort.addItemListener(this);
        p1.add(sort);
        // Animationsgeschwindigkeit auswählen:
        speed=new Choice();
        for (int index=0; index<animation.length; index++) {
            speed.add(animation[index]);
        }
        speed.addItemListener(this);
        p1.add(speed);
        // Steuerknopf:
        start=new Button(startKnopf[0]);
        start.setBackground(Color.lightGray);
        start.addActionListener(this);
        p1.add(start);
        // mit diesen Zuweisungen startet das Programm:
        feldMax.select("500");
        feldSize.select("500");
        speed.select("20");
        array=initArray(num, max);
        backup=copyArray(array);
        this.setBackground(Color.white);
    }
    
    // Eigenschaft des Startknopfes:
    
    public void actionPerformed(ActionEvent event) {
        String cmd = event.getActionCommand();
        if (cmd.equals(startKnopf[0])) {
            //if (t1.isAlive()==false) t1.start();
            //else t.resume();                           //nicht mehr ab JDK1.2 :-(
            stopThread=false;
            start.setLabel(startKnopf[1]);
            counter=0; t1=new Thread(this);
            t1.start();
        }
        if (cmd.equals(startKnopf[1])) {
            //t.suspend();                               //nicht mehr ab JDK1.2 :-(
            stopThread=true;
            start.setLabel(startKnopf[0]);
        }
        repaint();
    }
    
    // Eigenschaften der Choice-Felder:
    
    public void itemStateChanged(ItemEvent e) {
        if (e.getSource()==feldMax) {                          //Maximalwert
            for (int index=0; index<feldMaximum.length; index++) {
                if (e.getItem().equals(feldMaximum[index])) {
                    max=Integer.parseInt(feldMaximum[index]);
                    break;
                }
            }
        }
        if (e.getSource()==speed) {                            //Animationsgeschwindigkeit
            for (int index=0; index<animation.length; index++) {
                if (e.getItem().equals(animation[index])) {
                    delay=Integer.parseInt(animation[index]);
                    break;
                }
            }
            change=true;
        }
        if (e.getSource()==feldSize) {                         //Feldgroesse
            for (int index=0; index<feldGroesse.length; index++) {
                if (e.getItem().equals(feldGroesse[index])) {
                    num=Integer.parseInt(feldGroesse[index]);
                    break;
                }
            }
        }
        if (e.getSource()==sort) {                             //Sortieralgorithmus
            for (int index=0; index<sortAlg.length; index++) {
                if (e.getItem().equals(sortAlg[index])) {
                    sortCode=index;
                    break;
                }
            }
            change=true;
        }
        if (e.getSource()==feldTyp) {                          //Feldtyp
            for (int index=0; index<=2; index++) {
                if (e.getItem().equals(feldSortierung[index])) {
                    typ=index;
                    break;
                }
            }
        }
        if (!change) {
            // setzt Feldeigenschaft:
            if (typ==0) array=initArray(num, max);
            else if (typ==1) array=upArray(num);
            else if (typ==2) array=downArray(num);
            backup=copyArray(array);
            // (de-)aktiviert die Maximumauswahl:
            if (typ!=0) feldMax.setEnabled(false);
            else feldMax.setEnabled(true);        }
        else change=false;
        repaint();
    }
    
    // De-/Aktiviert die Steuerelemente:
    
    public void OnOff() {
        speed.setEnabled(!speed.isEnabled());
        feldSize.setEnabled(!feldSize.isEnabled());
        if (typ==0) feldMax.setEnabled(!feldMax.isEnabled());
        sort.setEnabled(!sort.isEnabled());
        feldTyp.setEnabled(!feldTyp.isEnabled());
    }
    
    
    // Thread-Methoden:
    
    public void run() {
        OnOff();
        switch (sortCode) {
            case 0: {bubbleSort(array);      break;}
            case 1: {insertionSort(array);   break;}
            case 2: {mergeSort(array);       break;}
            case 3: {quickSort(array);       break;}
            case 4: {selectionSort(array);   break;}
        }
        stopThread=false;
        OnOff();
        start.setLabel(startKnopf[0]);
    }
    
    //Feldfunktionen:
    
    public static int[] initArray(int feldSize, int maximum) { //zufaellig
        int feldTyp[]= new int[feldSize];
        maximum=maximum+1;
        for (int index=0; index<feldSize; index++) {
            feldTyp[index]=(int)(maximum*Math.random());
        }
        return feldTyp;
    }
    
    public static int[] downArray(int feldSize) {              //absteigend
        int feldTyp[]= new int[feldSize];
        for (int index=0; index<feldSize; index++) {
            feldTyp[index]=index;
        }
        return feldTyp;
    }
    
    public static int[] upArray(int feldSize) {                //aufsteigend
        int feldTyp[]= new int[feldSize];
        feldSize=feldSize-1;
        for (int index=0; index<=feldSize; index++) {
            feldTyp[index]=feldSize-index;
        }
        return feldTyp;
    }
    
    public static int[] copyArray(int[] quelle) {              //kopieren
        int laenge=quelle.length;
        int ziel[]= new int[laenge];
        for (int index=0; index<laenge; index++) {
            ziel[index]=quelle[index];
        }
        return ziel;
    }
    
    //Sortieralgorithmen:
    
    public void insertionSort(int[] array) {                   //InsertionSort
        Graphics g = this.getGraphics();
        int laenge=array.length;
        int temp;
        for (int i=1; i<laenge; i++) {
            int marker=i;
            temp=array[i];
            while (marker>0 && (array[marker-1]>temp)) {
                array[marker]=array[marker-1];
                marker--;
                drawArray(g, marker);
                if (stopThread) break;
            }
            array[marker]=temp;
            drawArray(g);
            //Externer Abbruch
            if (stopThread) break;
        }
    }
    
    public void selectionSort(int[] array) {                   //SelectionSort
        Graphics g = this.getGraphics();
        int laenge=array.length;
        int temp;
        for (int index1=0; index1<laenge-1; index1++) {
            int min = index1;
            temp = array[index1];
            for (int index2=index1+1; index2<laenge; index2++) {
                if (array[index2]<temp) {
                    min = index2;
                    temp = array[index2];
                    drawArray(g, index1, min, laenge); 
                    //Externer Abbruch
                    if (stopThread) break;
                }
            }
            array[min]= array[index1];
            array[index1]= temp;
            drawArray(g, index1, min, laenge);
            //Externer Abbruch
            if (stopThread) break;
        }
    }
    
    public void bubbleSort(int[] array) {                      //BubbleSort
        Graphics g = this.getGraphics();
        int laenge=array.length;
        int temp; 
        boolean change=true;
        // solange eine Vetauschung stattfindet:
        while (change) {
            change=false;
            for (int index=0; index<laenge-1; index++) {
                // größere "Blase" steigt nach oben:
                if (array[index]>array[index+1]) {
                    temp=array[index+1];
                    array[index+1]=array[index];
                    array[index]=temp;
                    drawArray(g);
                    change=true;
                }
                //Externer Abbruch
                if (stopThread) {
                    change=false;
                    break;
                }
            }
        }
    }
    
    public void quickSort(int[] array) {                       //QuickSort
        quickSort2(array, 0, array.length-1);
    }
    
    public void quickSort2(int[] array, int links, int rechts) {
        Graphics g = this.getGraphics();
        int left=links, right=rechts;
        int pivot=array[(links+rechts)/2], temp;
        do {
            //Tauschpartner links suchen:
            while (array[left]<pivot) left++;
            //Tauschpartner rechts suchen:
            while (array[right]>pivot) right--;
            //Vertauschen:
            if (left<=right) {
                temp=array[left]; array[left]=array[right]; array[right]=temp;
                left++; right--;
                drawArray(g, (links+rechts)/2, links, rechts);
                //Externer Abbruch
                if (stopThread) {
                    left=links=rechts=right=0;
                    break;
                }
            }
        } while (!(left>right));
        if (links<right) quickSort2(array, links, right);
        if (left<rechts) quickSort2(array, left, rechts);
    }
    
    public void mergeSort(int[] array) {                       //MergeSort
        mergeSort2(array, 0, array.length-1);
    }
    
    public void mergeSort2(int[] array, int links, int rechts) {
        if (links<rechts&&!stopThread) {
            int mitte=(links+rechts)/2;
            mergeSort2(array, links, mitte);
            mergeSort2(array, mitte+1, rechts);
            merge(array, links, rechts);
        }
    }
    
    public void merge(int[] array1, int links, int rechts) {
        Graphics g = this.getGraphics();
        int laenge=rechts-links;
        int mitte=(links+rechts)/2;
        int index1=0; int index2, index3;
        //Hilfsarray:
        int[] array2=new int[laenge+1];
        //untere Hälfte in Hilfsarray kopieren:
        for (index2=links; index2<=mitte; index2++) {
            array2[index1++]=array1[index2];
        }
        //obere Hälfte in Hilfsarray kopieren (umgekehrte Reihenfolge!):
        for (index3=rechts; index3>mitte; index3--) {
            array2[index1++]=array1[index3];
        }
        index1=links; index2=0; index3=laenge;
        while (index2<=index3) {
            if (array2[index2]<=array2[index3])
                array1[index1++]=array2[index2++];
            else 
                array1[index1++]=array2[index3--];
            drawArray(g, links, rechts, mitte);
            //Externer Abbruch
            if (stopThread) break;
        }
    }
}