import javax.swing.*;
import javax.swing.event.ChangeEvent;
import javax.swing.event.ChangeListener;

import java.applet.Applet;
import java.awt.*;
import java.awt.event.*;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FilePermission;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.RandomAccessFile;
import java.net.URI;
import java.net.URL;
import java.security.AccessController;
import java.security.PrivilegedAction;
import java.security.acl.Permission;
import java.util.Vector;
import java.util.jar.JarFile;


public class sort extends JApplet implements ActionListener, Runnable, ChangeListener, ComponentListener, WindowListener{

    private static final long serialVersionUID = 1746069960702724755L;
    
    // Die Swing Komponenten
    
    JComboBox methoden, mischmethoden, anzahl, sprache;
    BalkenFrame balken;
    JSlider geschwindigkeit;
    JList code;
    DefaultListModel codelines;
    JButton mischen, sortieren, einzelschritt;
    JProgressBar status;

    // Variablen für die Animation
    
    Vector aktionen = new Vector(1); // Der Vektor in dem die Animationen zwischengespeicher werden
    int animationpos, animatetopos; // Aktuelle Position im Animationsvektor und Position bis zu der die Animation laufen soll
    int[] actioncodelines = new int[100]; // Zeilennummern der einzelnen Aktionen im Quellcode
    int[] actioncodelinessize = new int[100]; // Anzahl der Zeilen für die Aktionen
    Thread animationthread = new Thread(this); // Thread für die Animationen
    
    // Typ Action, der einen Animationsschritt beschreibt
    
    private class Action
    {
        int type;
        int dataa, datab;
        int zeile;
        
        public Action(int type, int dataa, int datab, int zeile)
        {
            this.type = type;
            this.dataa = dataa;
            this.datab = datab;
            this.zeile = zeile;
        }
    }
    
    public void init(){ // Konstruktor
        
        // Grösse und Titel des Fensters setzen
        
        setSize(800,600);
        setMinimumSize(new Dimension(800,600));
        //setTitle("AniSort");
        addComponentListener(this);
        //addWindowListener(this);

        // Swing Komponenten einfügen
        
        JTextArea text;
        setLayout(new GridBagLayout());
        GridBagConstraints gbc = new GridBagConstraints();
        gbc.fill = GridBagConstraints.BOTH;
        gbc.gridy = 1;
        gbc.gridwidth = 3;
        gbc.insets = new Insets(3,3,0,0);
        
        JPanel oben = new JPanel();
        oben.setLayout(new BorderLayout());
        JPanel obenrechts = new JPanel();
        JPanel obenlinks = new JPanel();
        
        methoden = new JComboBox();
        methoden.addItem("Bubblesort");
        methoden.addItem("Quicksort");
        methoden.addItem("Heapsort");
        methoden.addItem("Insertationsort");
        methoden.addItem("Mergesort");
        methoden.addItem("Selectionsort");
        methoden.addActionListener(this);
        text = new JTextArea("Sortierverfahren:");
        text.setBackground(methoden.getBackground());
        obenlinks.add(text);
        obenlinks.add(methoden);
    
        anzahl = new JComboBox();
        anzahl.addItem("5");
        anzahl.addItem("10");
        anzahl.addItem("20");
        anzahl.addItem("30");
        anzahl.addItem("40");
        anzahl.addItem("50");
        anzahl.addItem("75");
        anzahl.addItem("100");
        anzahl.addItem("150");
        anzahl.addItem("200");
        anzahl.setSelectedIndex(2);
        anzahl.addActionListener(this);
        text = new JTextArea("Elemente:");
        text.setBackground(methoden.getBackground());
        obenlinks.add(text);
        obenlinks.add(anzahl);
    
        geschwindigkeit = new JSlider(0,40,35);
        geschwindigkeit.addChangeListener(this);
        text = new JTextArea("Geschwindigkeit:");
        text.setBackground(methoden.getBackground());
        obenrechts.add(text);
        obenrechts.add(geschwindigkeit);
        
        oben.add(obenlinks,BorderLayout.WEST);
        oben.add(obenrechts,BorderLayout.EAST);
        getContentPane().add(oben,gbc);
        
        gbc.gridwidth = 1; gbc.gridheight = 2;
        gbc.gridy = 2;
        gbc.weightx = 100;
        gbc.weighty = 100;
        balken=new BalkenFrame(20);
        balken.setPreferredSize(new Dimension(this.getWidth()-200,400));
        getContentPane().add(balken,gbc);
        gbc.weightx = 1;
        gbc.weighty = 1;

        gbc.gridheight = 1;
        sprache = new JComboBox();
        sprache.addItem("Java");
        sprache.addItem("C++");
        sprache.addActionListener(this);
        text = new JTextArea("Programmiersprache:");
        text.setBackground(methoden.getBackground());
        getContentPane().add(text,gbc);
        getContentPane().add(sprache,gbc);

        gbc.gridy = 3;
        gbc.gridwidth = 2;
        gbc.weighty = 1000;
        codelines = new DefaultListModel();
        code = new JList(codelines);
        code.setBackground(methoden.getBackground());
        getContentPane().add(code,gbc);
        gbc.weighty = 1;
        
        
        gbc.gridwidth = 3;
        gbc.gridy = 4;

        JPanel unten = new JPanel();
        
        mischen = new JButton("Mischen");
        mischen.addActionListener(this);
        unten.add(mischen,gbc);

        mischmethoden = new JComboBox();
        mischmethoden.addActionListener(this);
        mischmethoden.addItem("Zufällig");
        mischmethoden.addItem("Sortiert");
        mischmethoden.addItem("Absteigend");
        unten.add(mischmethoden,gbc);
        
        sortieren = new JButton("Sortieren");
        sortieren.addActionListener(this);
        unten.add(sortieren,gbc);

        einzelschritt = new JButton("Einzelschritt");
        einzelschritt.addActionListener(this);
        unten.add(einzelschritt,gbc);
        
        status = new JProgressBar();
        unten.add(status,gbc);

        getContentPane().add(unten,gbc);

        setVisible(true); // Fenster anzeigen
        mische(); // Elemente erzeugen
        loadcode(); // Quellcode anzeigen
    }
    
    // Elemente neu mischen
    
    private void mische(){
        // Animationsthread stoppen, falls dieser läuft
        if (animationthread.isAlive()) animationthread.stop();
        // Zufällige Elemente erzeugen
        if (mischmethoden.getSelectedItem().toString() == "Zufällig") 
            for (int i = 0; i < balken.laengen.length; i++)
                balken.laengen[i] = (int)(Math.random()*100)+10;
        // Elemente sortiert erzeugen
        if (mischmethoden.getSelectedItem().toString() == "Sortiert") 
            for (int i = 0; i < balken.laengen.length; i++)
                balken.laengen[i] = i*10+10;
        // Elemente absteigend sortiert erzeugen
        if (mischmethoden.getSelectedItem().toString() == "Absteigend") 
            for (int i = 0; i < balken.laengen.length; i++)
                balken.laengen[i] = (balken.laengen.length-i)*10+10;
        calcanimation(); // Animationsschritte berechnen
        balken.max = -1; // Maximalwert für die Balken zurücksetzen
        balken.balkenberechnen(); // Groesse und Position der Balken berechnen
    }
    
    // Einsprungspunkt ins Programm
    
    public static void main(String[] args) {
        new sort(); // Neues Objekt vom Typ sort erzeugen
    }

    // Animationsschritte berechnen
    
    private void calcanimation(){
        // Animationsthread stoppen, falls dieser läuft
        if (animationthread.isAlive()) animationthread.stop();
        // Das balken.langen Array nach balken.sortiert kopieren
        for (int i = 0; i < balken.anzahlbalken; i++)
            balken.sortiert[i] = balken.laengen[i];

        for (int i=0; i < 10; i++)
            balken.marker[i] = -1; // Alle Marker zurücksetzen

        balken.grenze = -1; // Grenze zurücksetzen
        
        balken.setactive(0,balken.sortiert.length-1); // Aktiven Bereich zurücksetzen

        aktionen.clear(); // Aktionenarray leeren
        
        // Berechne Aktionen für Bubblesort
        if (methoden.getSelectedItem().toString() == "Bubblesort")
        {
            boolean sortiert;
            do {
              sortiert = true;
              for (int i = 1; i < balken.laengen.length; i++) {
                  aktionen.addElement(new Action(1,i-1,i,1));
                  if (balken.sortiert[i - 1] > balken.sortiert[i]) {
                      aktionen.addElement(new Action(2,i-1,i,2));
                      int tmp = balken.sortiert[i - 1];
                      balken.sortiert[i - 1] = balken.sortiert[i];
                      balken.sortiert[i] = tmp;
                      sortiert = false;
                }
              }
              aktionen.addElement(new Action(0,0,0,0));
            } while (!sortiert);
        }
        // Berechne Aktionen für Quicksort
        if (methoden.getSelectedItem().toString() == "Quicksort")
            quickSort(balken.sortiert,0,balken.sortiert.length-1);
        // Berechne Aktionen für Heapsort
        if (methoden.getSelectedItem().toString() == "Heapsort")
            heapSort(balken.sortiert,balken.sortiert.length);
        // Berechne Aktionen für Insertationsort
        if (methoden.getSelectedItem().toString() == "Insertationsort")
            insertionsort(balken.sortiert);
        // Berechne Aktionen für Mergesort
        if (methoden.getSelectedItem().toString() == "Mergesort")
            balken.sortiert = mergesort(balken.sortiert,0);
        // Berechne Aktionen für Selectionsort
        if (methoden.getSelectedItem().toString() == "Selectionsort")
            selectionsort(balken.sortiert);
        animationpos = 0; // Position im Animationsarray zurücksetzen
        animatetopos = 0;
        status.setValue(0); // Statusbalken setzen
        status.setMaximum(aktionen.size());
    }
    
    // Quicksort Algorithmus
    
    private void quickSort(int array[], int start, int end)
    {
            int i = start;
            aktionen.addElement(new Action(3,1,i,0));
            int k = end;
            aktionen.addElement(new Action(3,2,k,1));

            if (end - start >= 1)
            {
                    aktionen.addElement(new Action(0,0,0,2));
                    aktionen.addElement(new Action(8,array[start],0,2));
                    int pivot = array[start];

                    while (k > i)
                    {
                            aktionen.addElement(new Action(1,start,i,3));
                            while (array[i] <= pivot && i <= end && k > i)
                            {
                                i++;
                                aktionen.addElement(new Action(3,1,i,3));
                                aktionen.addElement(new Action(1,start,i,3));
                            }
                            aktionen.addElement(new Action(1,start,k,4));
                            while (array[k] > pivot && k >= start && k >= i)
                            {
                                k--;
                                aktionen.addElement(new Action(3,2,k,4));
                                aktionen.addElement(new Action(1,start,k,4));
                            }
                            aktionen.addElement(new Action(1,k,i,5));
                            if (k > i)
                            {
                                aktionen.addElement(new Action(2,k,i,9));
                                int tmp = array[i];
                                array[i] = array[k];
                                array[k] = tmp;
                            }
                    }
                    aktionen.addElement(new Action(2,start,k,6));
                    int tmp = array[start];
                    array[start] = array[k];
                    array[k] = tmp;
                    aktionen.addElement(new Action(4,start,k-1,7));
                    quickSort(array, start, k - 1);
                    aktionen.addElement(new Action(4,k+1,end,8));
                    quickSort(array, k + 1, end);
                    aktionen.addElement(new Action(8,-1,0,2));
            }
            else
            {
                aktionen.addElement(new Action(4,start,end,8));
                return;
            }
            aktionen.addElement(new Action(4,start,end,8));
    }
    
    // Hilfsfunktion fuer einige Sortieralgorithmen

    private static void vertausche(int[] a, int x, int y) {
          int z = a[x]; a[x] = a[y]; a[y] = z;
        }
    
    // Hilfsfunktion für Heapsort

    private void versickere(int[] a, int n, int i) {
        while (i <= n/2) {
            int k = 2*i; 
            if (k < n)
            {
                aktionen.addElement(new Action(1,k-1,k,2));
                if (a[k] > a[k-1])
                    k++;
            }
            aktionen.addElement(new Action(1,i-1,k-1,3));
            if (a[k-1] > a[i-1]) {
                aktionen.addElement(new Action(2,i-1,k-1,0));
                vertausche(a, i-1, k-1);
                i = k;
            }
            else
                i = n;
        }
    }
    
    // Hilfsfunktion fuer Heapsort

    private void überführeInHeap(int[] a, int n) {
          for (int i = n/2; i >= 1; i--) {
            versickere(a, n, i);
          }
        }
    
    // Heapsort Algorithmus

    private void heapSort(int[] a, int n) {
          überführeInHeap(a, n);
          for (int i = n; i >= 1; i--) {
              aktionen.addElement(new Action(2,0,i-1,1));
            vertausche(a, 0, i-1);
            versickere(a, i-1, 1);
          }
        }
    
    // Insertionsort Algorithmus

    private void insertionsort(int[] a) {
        int pos;
        for (int i = 1; i <= a.length - 1; i++) {
            pos = binsearch(a, 0, i - 1, a[i]);
              aktionen.addElement(new Action(5,i,pos,0));
            move(i, pos, a);
        }
    }
    
    // Hilfsfunktion fuer Insertionsort

    private void move(int i, int j, int[] a) {
        int tmp = a[i];
        for (int g = i; g > j; g--) {
            a[g] = a[g - 1];
        }
        a[j] = tmp;
    }

    // Hilfsfunktion fuer Insertionsort

    private int binsearch(int[] a, int low, int high, int x) {
        int mitte = 0;
        int tmp = high+1;
        while (low <= high) {
            mitte = (low + high) / 2;
            if (a[mitte] == x)
            {
                  aktionen.addElement(new Action(1,mitte,tmp,1));
                return mitte;
            }
            if (a[mitte] < x)
            {
                  aktionen.addElement(new Action(1,mitte,tmp,2));
                low = mitte + 1;
            }
            if (a[mitte] > x)
            {
                  aktionen.addElement(new Action(1,mitte,tmp,3));
                high = mitte - 1;
            }
        }
        return low;
    }
    
    // Mergesort Algorithmus

    private int[] mergesort(int array[],int pos)
    {
        if(array.length > 1)
        {
            int elementsInA1 = array.length/2;
            int elementsInA2 = elementsInA1;
            if((array.length % 2) == 1)
                elementsInA2 += 1;
            int arr1[] = new int[elementsInA1];
            int arr2[] = new int[elementsInA2];
            for(int i = 0; i < elementsInA1; i++)
                arr1[i] = array[i];
            for(int i = elementsInA1; i < elementsInA1 + elementsInA2; i++)
                arr2[i - elementsInA1] = array[i];
            aktionen.addElement(new Action(4,pos,pos+elementsInA1-1,0));
              aktionen.addElement(new Action(7,0,0,0));
            arr1 = mergesort(arr1,pos);
            aktionen.addElement(new Action(4,pos+elementsInA1,pos+elementsInA2,1));
              aktionen.addElement(new Action(7,0,0,1));
            arr2 = mergesort(arr2,pos+elementsInA1);
            aktionen.addElement(new Action(4,pos,pos+array.length-1,2));
              aktionen.addElement(new Action(7,0,0,2));
                    
            int i = 0, j = 0, k = 0;
            while(arr1.length != j && arr2.length != k)
            {
                if(arr1[j] < arr2[k])
                {
                      aktionen.addElement(new Action(6,i+pos,arr1[j],3));
                    array[i] = arr1[j];
                    i++;
                    j++;
                }
                else
                {
                      aktionen.addElement(new Action(6,i+pos,arr2[k],4));
                    array[i] = arr2[k];
                    i++;
                    k++;
                }
            }
            while(arr1.length != j)
            {
                  aktionen.addElement(new Action(6,i+pos,arr1[j],5));
                array[i] = arr1[j];
                i++;
                j++;
            }
            while(arr2.length != k)
            {
                  aktionen.addElement(new Action(6,i+pos,arr2[k],6));
                array[i] = arr2[k];
                i++;
                k++;
            }
        }
        return array;
    }
    
    // Hilfsfunktion für Selectionsort

    private int minimum(int[] array, int anfang, int ende){
        int minIdx = anfang;
        for (int index=anfang+1; index<=ende; index++){
              aktionen.addElement(new Action(1,index,minIdx,0));
            if (array[index] < array[minIdx]){
                minIdx = index;
            }
        }
        return minIdx;
    }

    // Selectionsort Algorithmus

    private void selectionsort(int[] array){
        for (int index=0; index<array.length-1; index++){
            int minIdx = minimum(array, index, array.length-1);
              aktionen.addElement(new Action(2,index,minIdx,1));
            vertausche(array,index,minIdx);
        }
    }
         
    // Einstiegsfunktion für den Animationsthread
    
    public void run() {
        // So lange die Position im Array kleiner als animatetopos
        while ( (animationpos < animatetopos) && (animationpos < aktionen.size()) )
        {
            Action a = (Action)aktionen.elementAt(animationpos); // Waehle den Animationsschritt
            switch (a.type){
                case 0: // markiere Codezeilen
                    code.setSelectionInterval(actioncodelines[a.zeile],actioncodelines[a.zeile]+actioncodelinessize[a.zeile]-1);
                break;
                case 1: // vergleiche zwei Balken
                    code.setSelectionInterval(actioncodelines[a.zeile],actioncodelines[a.zeile]+actioncodelinessize[a.zeile]-1);
                    balken.vergleichen(a.dataa,a.datab);
                break;
                case 2: // vertausche zwei Balken
                    code.setSelectionInterval(actioncodelines[a.zeile],actioncodelines[a.zeile]+actioncodelinessize[a.zeile]-1);
                    balken.tauschen(a.dataa,a.datab);
                break;
                case 3: // setze einen Marker
                    code.setSelectionInterval(actioncodelines[a.zeile],actioncodelines[a.zeile]+actioncodelinessize[a.zeile]-1);
                    balken.setmarker(a.dataa,a.datab,false);
                break;
                case 4: // setze den aktiven Bereich
                    code.setSelectionInterval(actioncodelines[a.zeile],actioncodelines[a.zeile]+actioncodelinessize[a.zeile]-1);
                    balken.setactive(a.dataa,a.datab);
                    for (int i = 0; i < 10; i++)
                        balken.setmarker(i,-1,false);
                break;
                case 5: // verschiebe einen Balken
                    code.setSelectionInterval(actioncodelines[a.zeile],actioncodelines[a.zeile]+actioncodelinessize[a.zeile]-1);
                    balken.verschieben(a.dataa,a.datab);
                break;
                case 6: // setze die Länge eines Balkens neu
                    code.setSelectionInterval(actioncodelines[a.zeile],actioncodelines[a.zeile]+actioncodelinessize[a.zeile]-1);
                    balken.laengen[a.dataa] = a.datab;
                    balken.balkenberechnen();
                    balken.repaint();
                    try {
                        Thread.sleep(balken.delay*100);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                break;
                case 7: // warte etwas
                    code.setSelectionInterval(actioncodelines[a.zeile],actioncodelines[a.zeile]+actioncodelinessize[a.zeile]-1);
                    try {
                        Thread.sleep(balken.delay*100);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                break;
                case 8: // setze die Grenze
                    code.setSelectionInterval(actioncodelines[a.zeile],actioncodelines[a.zeile]+actioncodelinessize[a.zeile]-1);
                    balken.grenze = a.dataa;
                break;
            }
            animationpos++; // gehe zur nächsten Animation
            status.setValue(animationpos); // erneuere den Statusbalken
        }
    }

    // Callbackfunktion fuer die Swingkomponenten
    
    public void actionPerformed(ActionEvent arg0) {
        // "Mischen" wurde gedrückt
        if (arg0.getSource() == mischen)
        {
            mische();
        }
        // "Sortieren" wurde gedrückt
        else if (arg0.getSource() == sortieren)
        {
            animatetopos = aktionen.size();
            if (!animationthread.isAlive()){
                animationthread = new Thread(this);
                animationthread.start();
            }
        }
        // "Einzelschritt" wurde gedrueckt
        else if (arg0.getSource() == einzelschritt)
        {
            animatetopos = animationpos + 1;
            if (!animationthread.isAlive()){
                animationthread = new Thread(this);
                animationthread.start();
            }
        }
        // Ein neues Sortierverfahren wurde gewaehlt
        else if (arg0.getSource() == methoden)
        {
            loadcode();
            calcanimation();
        }
        // Eine neue Programmiersprache wurde gewaehlt
        else if (arg0.getSource() == sprache)
        {
            loadcode();
        }
        // Eine neue Anzahl an Elementen wurde gewaehlt
        else if (arg0.getSource() == anzahl)
        {
            balken.setanzahl(Integer.parseInt(anzahl.getSelectedItem().toString()));    
            mische();
            calcanimation();
        }
    }
    
    // Laed den Quellcode des gewaehlten Verfahrens in der gewaehlten Sprache

    private void loadcode(){
        String filename = getParameter("codeurl");
        if (filename == null) return;
        if (methoden.getSelectedItem().toString() == "Bubblesort")
            filename += "bubblesort";
        if (methoden.getSelectedItem().toString() == "Quicksort")
            filename += "quicksort";
        if (methoden.getSelectedItem().toString() == "Heapsort")
            filename += "heapsort";
        if (methoden.getSelectedItem().toString() == "Insertationsort")
            filename += "insertationsort";
        if (methoden.getSelectedItem().toString() == "Mergesort")
            filename += "mergesort";
        if (methoden.getSelectedItem().toString() == "Selectionsort")
            filename += "selectionsort";
        if (sprache.getSelectedItem().toString() == "Java")
            filename += ".java";
        if (sprache.getSelectedItem().toString() == "C++")
            filename += ".cpp";
        codelines.clear();
        try {
            URL url = new URL( filename+".txt" );
            BufferedReader f = new BufferedReader(new InputStreamReader(url.openStream())); // lade den Quelltext
            for ( String line; (line=f.readLine()) != null; )
                codelines.addElement(line);
            f.close();
            url = new URL( filename+".lines" );
            f = new BufferedReader(new InputStreamReader(url.openStream())); // lade die Zeilenangaben
            int i = 0;
            for ( String line1, line2; ((line1=f.readLine()) != null) && ((line2=f.readLine()) != null); )
            {
                try {
                    actioncodelines[i] = Integer.parseInt(line1);
                    actioncodelinessize[i] = Integer.parseInt(line2);
                } catch (NumberFormatException e) {
                    actioncodelines[i] = 0;
                    actioncodelinessize[i] = 0;
                }
                i++;
            }
            f.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
            codelines.addElement("Datei konnte nicht geöffnet werden.");
            return;
        } catch (IOException e) {
            e.printStackTrace();
            return;
        }
        return;
    }

    // Callbackfunktion fuer den Geschwindigkeiteregler
    
    public void stateChanged(ChangeEvent arg0) {
        balken.delay = 41-geschwindigkeit.getValue();
    }

    // Callbackfunktion falls die Fenstergroesse veraendert wird
    
    public void componentResized(ComponentEvent arg0) {
        if ( (arg0.getComponent().getSize().width < 800) || (arg0.getComponent().getSize().width < 600) )
        {
            int width = arg0.getComponent().getSize().width;
            int height = arg0.getComponent().getSize().height;
            if (width < 800) width = 800;
            if (height < 600) height = 600;
            arg0.getComponent().setSize(width,height);
        }
        
    }

    // Callbackfunktion falls das Fenster geschlossen wird
    
    public void windowClosing(WindowEvent arg0) {
        System.exit(0); // beende das Programm
    }

    public void componentMoved(ComponentEvent arg0) {}

    public void componentShown(ComponentEvent arg0) {}

    public void componentHidden(ComponentEvent arg0) {}

    public void windowOpened(WindowEvent arg0) {}

    public void windowClosed(WindowEvent arg0) {}

    public void windowIconified(WindowEvent arg0) {}

    public void windowDeiconified(WindowEvent arg0) {}

    public void windowActivated(WindowEvent arg0) {}

    public void windowDeactivated(WindowEvent arg0) {}
}

// Anzeige und Animationsklasse der Balken

class BalkenFrame extends JPanel implements ComponentListener{
    private static final long serialVersionUID = 177521082539809532L;
    Rectangle[] balken; // Array mit den Balkengroessen und Positionen
    int[] laengen, sortiert; // aktuelle und sortierte Laengen der Balken
    int anzahlbalken, max; // Anzahl der Balken und max. Laenge
    int delay = 5; // Geschwindigkeit mit Defaultwert
    int[] marker = new int[10]; // Positionen der Marker
    int grenze = -1, grenzey; // Wert und Y-Position der Grenze
    boolean[] active; // Aktiver Berech
    
    // Konstruktor
    
    public BalkenFrame(int anzahlbalken){
        setanzahl(anzahlbalken);
        this.addComponentListener(this);
        this.setMinimumSize(new Dimension(100,100)); // Setzen der minimalen Groesse für den Animationsbereich
    }
    
    // Anzahl der Balken setzen
    
    public void setanzahl(int anzahlbalken)
    {
        this.anzahlbalken = anzahlbalken;
        // Arrays erstellen
        balken = new Rectangle[anzahlbalken];
        laengen = new int[anzahlbalken];
        sortiert = new int[anzahlbalken];
        active = new boolean[anzahlbalken];
        for (int i=0; i < anzahlbalken; i++)
            balken[i] = new Rectangle();
        for (int i=0; i < 10; i++)
            marker[i] = -1; // Marker zurücksetzen
        setactive(0,anzahlbalken-1); // Aktiven Bereich zurücksetzen
    }

    // Groessen und Positionen der Balken berechnen

    public void balkenberechnen(){
        if (max <= 0) for (int i=0; i < anzahlbalken; i++)
            if (laengen[i] > max) max = laengen[i];
        if (max == 0) max = -1;
        for (int i=0; i < anzahlbalken; i++){
            balken[i].width = (getWidth()-4)/anzahlbalken-1;
            balken[i].height = (getHeight()-40)*(laengen[i])/max;
            balken[i].x = 1+(getWidth()-2)*i/anzahlbalken;
            balken[i].y = getHeight()-balken[i].height-20;
        }
        grenzey = getHeight()-((getHeight()-40)*(grenze)/max)-20;
        repaint();
    }
    
    // Marker setzen (Animation)
    
    public void setmarker(int a, int b, boolean wait){
        try {
            marker[a] = b;
            repaint();
            if (wait) Thread.sleep(delay*100);
        } catch (InterruptedException e) {
        }
    }
    
    // aktivem Bereich setzen (Animation)

    public void setactive(int a, int b){
        for (int i=0; i < anzahlbalken; i++)
            active[i] = false;
        for (int i=a; i <= b; i++)
            active[i] = true;
    }

    // Zwei Balken vergleichen (Animation)
    
    public void vergleichen(int a, int b){
        balkenberechnen();
        try {
            int x1 = balken[a].x;
            int x2 = balken[b].x;
            int w1 = balken[a].width;
            int w2 = balken[b].width;
            for (int i=0; i<=3; i++)
            {
                Thread.sleep(delay*5);
                balken[a].x = x1+i;
                balken[a].width = w1-2*i;
                balken[b].x = x2+i;
                balken[b].width = w2-2*i;
                repaint();
            }
            for (int i=3; i>=0; i--)
            {
                Thread.sleep(delay*5);
                balken[a].x = x1+i;
                balken[a].width = w1-2*i;
                balken[b].x = x2+i;
                balken[b].width = w2-2*i;
                repaint();
            }
            balkenberechnen();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
    
    // Zwei Balken vertauschen (Animation)

    public void tauschen(int a, int b){
        balkenberechnen();
        try {
            int x1 = balken[a].x;
            int x2 = balken[b].x;
            int y1 = balken[a].y;
            int y2 = balken[b].y;
            for (int i=0; i<=10; i++)
            {
                Thread.sleep(delay*3);
                balken[a].y = y1-i;
                balken[b].y = y2-i;
                repaint();
            }
            if (a != b) for (int i=0; i<=40; i++)
            {
                Thread.sleep(delay);
                balken[a].x = x1+(x2-x1)*i/40;
                balken[b].x = x2+(x1-x2)*i/40;
                repaint();
            }
            for (int i=10; i>=0; i--)
            {
                Thread.sleep(delay*3);
                balken[a].y = y1-i;
                balken[b].y = y2-i;
                repaint();
            }
            int t = laengen[a];
            laengen[a] = laengen[b];
            laengen[b] = t;
            balkenberechnen();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
    
    // Balken verschieben (Animation)

    public void verschieben(int a, int b){
        balkenberechnen();
        try {
            int x1 = balken[a].x;
            int x2 = balken[b].x;
            int y1 = balken[a].y;
            for (int i=0; i<=10; i++)
            {
                Thread.sleep(delay*3);
                balken[a].y = y1-i;
                repaint();
            }
            if (a > b) for (int i=0; i<=getWidth()/anzahlbalken; i++)
            {
                Thread.sleep(delay*5);
                for (int g = b; g < a; g++)
                    balken[g].x++;
                balken[a].x = x1-(x1-x2)*i/(getWidth()/anzahlbalken);
                repaint();
            }
            for (int i=10; i>=0; i--)
            {
                Thread.sleep(delay*3);
                balken[a].y = y1-i;
                repaint();
            }
            int tmp = laengen[a];
            for (int g = a; g > b; g--)
                laengen[g] = laengen[g - 1];
            laengen[b] = tmp;
            balkenberechnen();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    // Animationsberech zeichnen

    public void paintComponent(Graphics g){
        paintComponents(g);
        g.setColor(getBackground());
        g.fillRect(0,0,getWidth(),getHeight()); // Hintergrundlöschen
        FontMetrics metrics = g.getFontMetrics(); // Groesse der Schriftart bestimmen
        
        g.setColor(Color.BLACK);
        for (int i=0; i < anzahlbalken; i++){
            if (active[i]) // Farben des aktiven Bereichs
                if (laengen[i] == sortiert[i])
                    g.setColor(new Color(0,240,0));
                else
                    g.setColor(new Color(240,0,0));
            else // Farben des inaktiven Bereichs
                if (laengen[i] == sortiert[i])
                    g.setColor(new Color(220,255,220));
                else
                    g.setColor(new Color(255,220,220));
            g.fillRoundRect(balken[i].x,balken[i].y,balken[i].width,balken[i].height,balken[i].width/2,balken[i].width/2); // Balken malen
            g.setColor(Color.BLACK);
            String m = "";
            if (marker[1] == i ) m += " i "; // Marker schreiben
            if (marker[2] == i ) m += " k ";
            if (marker[3] == i ) m += " p ";
            g.drawString(m,balken[i].x+balken[i].width/2-metrics.stringWidth(m)/2,balken[i].y+balken[i].height+metrics.getHeight());
        }
        if (grenze != -1)
            g.drawLine(0,grenzey,getWidth(),grenzey); // Grenze zeichnen
    }
    
    public void componentResized(ComponentEvent arg0) {balkenberechnen();repaint();}

    public void componentMoved(ComponentEvent arg0) {balkenberechnen();repaint();}

    public void componentShown(ComponentEvent arg0) {balkenberechnen();repaint();}

    public void componentHidden(ComponentEvent arg0) {}
}