/*  Änderungen zu der Version von Thorsten Horstmeyer:
 *  Im wesentlichen habe ich die SortierAlgorithmen frei von Grafik-
 *  Ausgabe und Initialisierung gemacht, so daß man jederzeit aus einer
 *  Methode heraus ausgabe() aufrufen kann, und schon wird das ganze (!) Feld
 *  ausgegeben. Dadurch wird auch bei Divide&Conquer-Algorithmen das ganze Feld
 *  ausgegeben, und nicht wie in der Version von Herrm Horstmeyer jeweils 
 *  nur das abgetrennte Unterstück.
 *  Author: Ralf Butenuth <butenuth@mathematik.uni-marburg.de>
 *  Originalversion von Prof. Dr. Manfred Sommer
 */
 

import java.awt.*;
import java.awt.event.*;

class MySortAnim extends Frame {

	private static int wartezeit = 0; //Wartezeit wird in der Ausgaberoutine benutzt
	
	private static final int Anzahl = 1000; //Wie viele Peek's das Array haben soll
						//(== Fensterbreite)

	private static final int MaxPeek = 300; //Wie groß der höchste Peek sein soll 
						//Achtung: Wg. Achsensymetrie in der Animation:
						//Fensterhöhe = MaxPeek * 2 + 2 :-)
	private static final int LeistenBreite = 55; // Wie breit die Symbolleiste ist
						     // Achtung: Das scheint auf jedem System anders
						     // zu sein, muß man ausprobieren.

	private static int[] feld = new int[Anzahl]; // Born to be sort!
	
	// Das Bild wird von der ausgabe-Routine benutzt. Ich verwende globale Variablen,
	// weil das ausgabe-Bild immer gleich groß ist, und ich dann nicht in jedem Sortier-
	// Algorithmus nochmal extra eine Variable für die Ausgabe deklarieren brauch. Die 
	// Algorithmen sind dann frei von Ausgabe-Routinen und das Bild braucht man ja eh.
	private static Image bild;
	private static Graphics gbild;
	
	//Titel und Datum, Bitte nach belieben ändern.
	private static final String VersionsDatum = "10. Mai 2002";
	private static final String Titel = "SortierAnimation 2002";
	
	//Schriften
	private static final Font FontMono  = new Font("Monospaced", Font.PLAIN, 20);
	private static final Font FontSansSerif = new Font("SansSerif", Font.PLAIN, 15);
	private static final Font BigItalicSansSerif = new Font("SansSerif", Font.ITALIC, 20);

	
	//Menü-Einträge
	private static MenuBar MainMenuBar = new MenuBar(); 	

	private static Menu DateiMenu = new Menu("Datei");	
	private static MenuItem Beenden = new MenuItem("Beenden"); 
	
	private static Menu SortMenu = new Menu("Sortier-Algorithmus");
	private static MenuItem BubbleSortM = new MenuItem("BubbleSort");
	private static MenuItem SelectionSortM = new MenuItem("SelectionSort");
	private static MenuItem InsertionSortM = new MenuItem("InsertionSort");
	private static MenuItem ShellSortM = new MenuItem("ShellSort");
	private static MenuItem QuickSortM = new MenuItem("QuickSort");
	private static MenuItem HeapSortM = new MenuItem("HeapSort");
	private static MenuItem DistributionSortM = new MenuItem("DistributionSort");

	
	private static Menu WaitMenu = new Menu("Wartezeit");
	private static MenuItem m000 = new MenuItem("keine Wartezeit");
	private static MenuItem m050 = new MenuItem("50 ms Wartezeit");
	private static MenuItem m100 = new MenuItem("100 ms Wartezeit");
	private static MenuItem m250 = new MenuItem("250 ms Wartezeit");
	private static MenuItem m500 = new MenuItem("500 ms Wartezeit");
	
	private static Menu HelpMenu = new Menu("Hilfe");
	private static MenuItem hilfe = new MenuItem("There is no help for this world!");
	private static MenuItem about = new MenuItem("About");

	public MySortAnim() {
		super(Titel);
		
		//Dieses Bild benutzt die ausgabe-Routine, und da jeder SortierAlgorithmus immer das
		//gleiche Feld auszugeben hat, deklariere ich es global, und dann sind die 
		//SortierAlgorithmen frei von Grafik-Zeugs, was das übersichtlicher macht. 
		//bild = createImage(Anzahl, MaxPeek * 2 + 20);
		//gbild = bild.getGraphics();
		
		//Die Schrift für das Menü
		setFont(FontMono);
		DateiMenu.setFont(FontSansSerif);
		Beenden.setFont(FontSansSerif);
		SortMenu.setFont(FontSansSerif);
	        BubbleSortM.setFont(FontSansSerif);	
		SelectionSortM.setFont(FontSansSerif);
		InsertionSortM.setFont(FontSansSerif);
		ShellSortM.setFont(FontSansSerif);
		QuickSortM.setFont(FontSansSerif);
		HeapSortM.setFont(FontSansSerif);
		DistributionSortM.setFont(FontSansSerif);
		WaitMenu.setFont(FontSansSerif);
		m000.setFont(FontSansSerif);
		m050.setFont(FontSansSerif);
		m100.setFont(FontSansSerif);
		m250.setFont(FontSansSerif);
		m500.setFont(FontSansSerif);
		HelpMenu.setFont(FontSansSerif);
		hilfe.setFont(FontSansSerif);									
		about.setFont(FontSansSerif);															
		setLayout(new FlowLayout());
		addWindowListener(new MyWindowListener()); //Da steht dann noch der Beenden-Knopf drinne.
	
		// Das Menü wird gebastelt.
		setMenuBar(MainMenuBar);
		MainMenuBar.add(DateiMenu);
		DateiMenu.addSeparator();
		DateiMenu.add(Beenden);
		
		MainMenuBar.add(SortMenu);
		SortMenu.add(BubbleSortM);
		SortMenu.add(SelectionSortM);
                SortMenu.add(InsertionSortM);	
		SortMenu.add(ShellSortM);	
		SortMenu.add(QuickSortM);
		SortMenu.add(HeapSortM);
                SortMenu.add(DistributionSortM);

		MainMenuBar.add(WaitMenu);
		WaitMenu.add(m000);
		WaitMenu.add(m050);
		WaitMenu.add(m100);
		WaitMenu.add(m250);
		WaitMenu.add(m500);
		
		MainMenuBar.add(HelpMenu);
		HelpMenu.add(hilfe);
		HelpMenu.addSeparator();
		HelpMenu.add(about);
		
		
		// Die ActionListener für die einzelnen Menüeinträge
		BubbleSortM.addActionListener(new ActionListener() {
			public void actionPerformed(ActionEvent e) { doBubbleSort(); }
		} );
		
		SelectionSortM.addActionListener(new ActionListener() {
			public void actionPerformed(ActionEvent e) { doSelectionSort(); }
		} );
		
		InsertionSortM.addActionListener(new ActionListener() {
			public void actionPerformed(ActionEvent e) { doInsertionSort(); }
		} );
                
		ShellSortM.addActionListener(new ActionListener() {
			public void actionPerformed(ActionEvent e) { doShellSort(); }
		} );

		QuickSortM.addActionListener(new ActionListener() {
			public void actionPerformed(ActionEvent e) { doQuickSort(); }
		} );

		HeapSortM.addActionListener(new ActionListener() {
			public void actionPerformed(ActionEvent e) { doHeapSort(); }
		} );

		DistributionSortM.addActionListener(new ActionListener() {
			public void actionPerformed(ActionEvent e) { doDistributionSort(); }
		} );
		
		
		Beenden.addActionListener(new ActionListener() {
			public void actionPerformed(ActionEvent e) { doBeenden(); }
		} );
	       
		m000.addActionListener(new ActionListener(){
		        public void actionPerformed(ActionEvent e){ wartezeit = 0; }
		} );

	        m050.addActionListener(new ActionListener(){
			public void actionPerformed(ActionEvent e){ wartezeit = 50; }
		} );
		
                m100.addActionListener(new ActionListener(){
		        public void actionPerformed(ActionEvent e){ wartezeit = 100; } 
		} );
	      
	        m250.addActionListener(new ActionListener(){	
		        public void actionPerformed(ActionEvent e){ wartezeit = 250; }
		} );

	        m500.addActionListener(new ActionListener(){
		        public void actionPerformed(ActionEvent e){ wartezeit = 500; }
		} );
					       
		about.addActionListener(new ActionListener(){
			public void actionPerformed(ActionEvent e){ showAboutBox(); }
		} );
		
		setBackground(Color.white);
		setSize(Anzahl + 2 , 2 * MaxPeek + LeistenBreite + 2);  
		//Die benötigte Größe des Fensters ergibt sich aus den Konstanten (s.o.)
		setVisible(true);
		
		//Dann halt hier das Image-Zeugs, dann klappts auch unter Windows.
		bild = createImage(Anzahl, MaxPeek * 2 + LeistenBreite);
		Graphics g = getGraphics();
		g.drawImage(bild, 0, 0, null);
		gbild = bild.getGraphics();
	}


	private void doBeenden() {
		dispose();
		System.exit(0);
	}
	
	// Fuellt das feld-Array zufällig mit Werten zwischen 0 und MaxPeek. 
	private void fuellen() {
		java.util.Random r = new java.util.Random();
		for (int i = 0; i < feld.length; i++) feld[i] = Math.abs(r.nextInt() % MaxPeek);
	}
	
	// Vertauschen zweier Elemente. Wird von den Sortieralgorithmen benutzt
	private void Swap(int i, int j){
		int temp = feld[i];
		feld[i] = feld[j];
		feld[j] = temp;
	}
	
	//Die Position mit dem kleinsten Eintrag in einem Intervall. Wird von den Sortieralgorithmen benutzt.
	private int minPos(int i, int j){
		int erg = i;
		for (int k = i+1; k < j; k++)
			if (feld[k] < feld[erg]) erg = k;
		return erg;
	}
	
	//Ab hier kommen die Sortieralgorithmen
	
	private void doBubbleSort() {
		fuellen();
		ausgabe();

		for (int k = Anzahl - 1;  k > 0; k--){
			boolean test = true;
			for (int i = 0; i < k; i++)
				if ( feld[i] > feld[i+1]) { Swap(i, i+1); test = false;}
			ausgabe();
			if (test) break;
		}
	}
	

	private void doSelectionSort(){
		fuellen();
		ausgabe();
		int Hi = feld.length - 1;		
		for (int k = 0; k < Hi; k++){
			int Min = minPos(k, Hi);
			if ( Min != k) Swap (Min, k);
			ausgabe();
		}
								            
	}

    	private void doInsertionSort(){
	       fuellen();
	       ausgabe();
	       int Hi = feld.length-1;
	       for (int k = 1; k <= Hi; k++) {
			if (feld[k] < feld[k-1]){
				int x = feld[k];
				int i;
				for ( i = k; ( (i > 0) && (feld[i-1] > x) ) ;  i-- ) feld[i] = feld[i-1];
				feld[i] = x;
			}
 		        ausgabe();
	       }
	}
    
	private void doShellSort(){
		fuellen();
		ausgabe();
		int Hi = feld.length-1;
		int hmax, h ;
		for ( hmax = 1; hmax < Hi ; hmax = 3*hmax+1 );
			for ( h = hmax/3; h > 0; h /= 3)
				for (int k = h; k <= Hi; k++){
					if (feld[k] < feld[k-h]){
						int x = feld[k];
					        int i;
					        for ( i = k; ( (i > (h-1)) && (feld[i-h] > x) ) ;  i-=h ) feld[i] = feld[i-h];
						feld[i] = x;
						}
					ausgabe();
					}
	}
	
	private void doQuickSort(){
		fuellen();
		ausgabe();
		int Hi = feld.length -1 ;
		RekQuickSort(0, Hi);
	}

	private void RekQuickSort(int Lo, int Hi){
		int li = Lo;
		int re = Hi;
		int mid = (li + re) / 2;
		if (feld[li] > feld[mid]) Swap(li, mid);
		if (feld[mid] > feld[re]) Swap(mid, re);
		if (feld[li] > feld[mid]) Swap(li, mid);
		if (re - li > 2) {
			int w = feld[mid];
			do {
				while (feld[li] < w) li++;
				while (feld[re] > w) re--;
				if (li <= re)  { 
					Swap(li, re);
					li++;
					re--;
				}
			} while ( li <= re);
			if (Lo < re) {
				RekQuickSort(Lo, re);
				ausgabe();
			}
			if (li < Hi) {
				RekQuickSort(li, Hi);
				ausgabe();
			}
		}
	}

 	private void DownHeap(int i, int m){
		int sonny = 2*i + 1;
		while (sonny <= m){
			if ((sonny < m) && (feld[sonny] < feld[sonny+1])) sonny++; // Linker oder rechter Zweig
			if (feld[i] < feld[sonny]) { // tauschen ?
				Swap(i, sonny);
				i = sonny;
				sonny += sonny + 1;
				}
			else break;
		}
	}

        private void doHeapSort(){
	        fuellen();
		ausgabe();
		int Hi = feld.length - 1;
		for (int i = Hi/2; i >= 0; i--) {
			DownHeap(i, Hi);
			ausgabe();
		}
		for (int i = Hi; i > 0; i--) {
			Swap(i, 0);
			DownHeap(0, i-1);
			ausgabe();
		}
	}

	private void doDistributionSort(){
		fuellen();
		ausgabe();
		int Hi = feld.length - 1;
		int[] B = new int[Hi + 1];
		int[] Count = new int[256];

		//Byte eins:
		for (int i = 0; i <= Hi; i++) //Zaehlen
			Count[(feld[i] & 0xff)]++;
		for (int i = 1; i < 256; i++)
			Count[i] = Count[i] + Count[i-1]; //Aufsummieren
		for (int i = Hi; i >= 0; i--)
			B[--Count[(feld[i] & 0xff)]] = feld[i]; //Verteilen
		System.arraycopy(B, 0, feld, 0, Hi + 1);
		ausgabe();

		//Byte zwei:
                for (int i = 0; i < 256; i++) Count[i] = 0;
		for (int i = 0; i <= Hi; i++) //Zaehlen
			Count[((feld[i] >> 8) & 0xff)]++;
		for (int i = 1; i < 256; i++)
			Count[i] = Count[i] + Count[i-1]; //Aufsummieren
		for (int i = Hi; i >= 0; i--)
			B[--Count[(feld[i] >> 8) & 0xff]] = feld[i]; //Verteilen
		System.arraycopy(B, 0, feld, 0, Hi + 1);
		ausgabe();

		//Eigentlich hat ein Integer ja 4 Byte, aber da die Werte in feld[] hier nur zwischen 0 und 
		//MaxPeek liegen, reichen wohl zwei Schritte. Bildschirmauflösungen größer als 2^16 gibt es
		//nicht.
		
	}

  
	// Die Ausgabe-Routine. Im wesentlichen das von Thomas Horstmeyer, nur daß ich hier eine global 
	// deklarierte Image-Variable benutze, so daß die Sortier-Algorithmen ganz frei von Grafik-Zeugs 
	// sind. Da man eh immer das ganze Feld ausgeben will, braucht man auch keine Grenzen übergeben.
	// Dadurch wird die Ausgabe-Routine etwas kürzer und einfacher.
	private void ausgabe() {
		Graphics g = getGraphics();
		gbild.clearRect(0,0,Anzahl, 2 * MaxPeek + LeistenBreite);
		gbild.setColor(Color.black);

		for (int i = 0; i < feld.length; i++)
			gbild.drawLine(i, MaxPeek - feld[i] + LeistenBreite, i, MaxPeek + feld[i] + LeistenBreite);
		g.drawImage(bild, 0, 0, null);
		g.dispose();
		if (wartezeit > 0) {
			long t = System.currentTimeMillis() + wartezeit;
			while (System.currentTimeMillis() < t);
		}
	}

	// Die Credits.
	private void showAboutBox(){
		final Frame f = new Frame("About Box");		         
		final Button Ok = new Button("Ok");
		f.addWindowListener(new WindowAdapter() {
			public void windowClosing(WindowEvent e) { f.dispose(); }
	  	} );
		Ok.addActionListener(new ActionListener(){
			public void actionPerformed(ActionEvent e) { f.dispose(); }
	        } );
		f.setFont(BigItalicSansSerif);
		f.setLayout(new GridLayout(0, 1));
		f.add(new Label(" ", Label.CENTER));
		f.add(new Label("Universität Marburg - Fachbereich Mathematik und Informatik", Label.CENTER));
	        f.add(new Label("Praktische Informatik II Vorlesung Sommersemester 2002", Label.CENTER));
	        f.add(new Label("Teilprojekt: Sortier Animation", Label.CENTER));
	        f.add(new Label("Datum der letzten Änderung: " + VersionsDatum, Label.CENTER));
	        f.add(new Label("Autor: Prof. Dr. Manfred Sommer", Label.CENTER));
	        f.add(new Label("Grafikroutine überarbeitet von Thomas Horstmeyer", Label.CENTER));
	        //Da steht jetzt noch mein Name. (Der kann bei Bedarf natürlich gerne entfernt werden :-)
		f.add(new Label("Überarbeitet von Ralf Butenuth", Label.CENTER));
		f.add(new Label(" ", Label.CENTER));
		f.add(Ok);
		f.pack();
                f.setVisible(true);											
	 }
	 
}