//Änderungen zur Originalversion
//	- neu überladene Grafikroutine ShowArray, jetzt mit Image zum Buffern
//	- in jeder do...Sort Methode:
//		* Image bild initialisiert
//		* den Aufruf von ShowArray ersetzt
//	- void RekQuickSort(Graphics g, int[] A, int Lo, int Hi) 
//	  ersetzt durch
//	  void RekQuickSort(Graphics g, int[] A, int Lo, int Hi, Image bild)
//	- About-Dialog angepasst

import java.awt.*;
import java.io.*;
import java.util.*;
import java.awt.event.*;

class SortAnimation extends Frame{

    private static final String VersionsDatum ="17. April 2000";
    
    private static String Titel = "Sortier Animation";
    
    private static int WarteZeit = 0; // default
    
    private final static int Anzahl = 1000;
    private final static ArrayGen AG = new ArrayGen(Anzahl);   
    
    private static final Font FontMono  = new Font("Monospaced", Font.PLAIN, 20);
    private static final Font FontSansSerif = new Font("SansSerif", Font.PLAIN, 18);
    private static final Font BigItalicSansSerif = new Font("SansSerif", Font.ITALIC, 20);
       
    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("Sort");
    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 OptionenMenu = new Menu("Optionen");
    private static MenuItem Optio1 = new MenuItem("Ohne Verzögerung");
    private static MenuItem Optio2 = new MenuItem("Verzögerung 50 mS");
    private static MenuItem Optio3 = new MenuItem("Verzögerung 150 mS");
    private static MenuItem Optio4 = new MenuItem("Verzögerung 300 mS");
    
    private static Menu HilfeMenu = new Menu("Hilfe");
    private static MenuItem Hilfe = new MenuItem("Es gibt keine Hilfe...");
    private static MenuItem AboutBox = new MenuItem("About");
    
      
        
    //// Constructor.
     
    public SortAnimation () {
	super(Titel);
	
	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);
	
	OptionenMenu.setFont(FontSansSerif);
        Optio1.setFont(FontSansSerif);
        Optio2.setFont(FontSansSerif);    
        Optio3.setFont(FontSansSerif);    
        Optio4.setFont(FontSansSerif);   
	HilfeMenu.setFont(FontSansSerif);
	Hilfe.setFont(FontSansSerif);
	AboutBox.setFont(FontSansSerif);
	setLayout(null);

	
	//// Menüs
	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(OptionenMenu);
	OptionenMenu.add(Optio1);
	OptionenMenu.add(Optio2);
	OptionenMenu.add(Optio3);
	OptionenMenu.add(Optio4);
	
	MainMenuBar.add(HilfeMenu);
	HilfeMenu.add(Hilfe);
	HilfeMenu.addSeparator();
	HilfeMenu.add(AboutBox);
	
	//// Allgemeine Initialisierung
	
	//doDateiNeu();
	
	//// Menü Listener
	
	Beenden.addActionListener(new ActionListener(){
	    public void actionPerformed(ActionEvent e){ FensterBeenden(); }
	    });
	
	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(); }
	    });
	
	
	
	Optio1.addActionListener(new ActionListener(){
	    public void actionPerformed(ActionEvent e){ WarteZeit = 0; }
	    });

        Optio2.addActionListener(new ActionListener(){
	    public void actionPerformed(ActionEvent e){ WarteZeit = 50; }
	    });

        Optio3.addActionListener(new ActionListener(){
	    public void actionPerformed(ActionEvent e){ WarteZeit = 150; }
	    });

        Optio4.addActionListener(new ActionListener(){
	    public void actionPerformed(ActionEvent e){ WarteZeit = 300; }
	    });
	    
	AboutBox.addActionListener(new ActionListener(){
	    public void actionPerformed(ActionEvent e){ showAboutBox(); }
	    });         
	
	//// Window Listener
	addWindowListener(new WindowAdapter() {    
            public void windowClosing(WindowEvent e) { FensterBeenden(); }
	    });
	    
	//// Jetzt Fenster zeigen!
	//setBackground(Color.lightGray);    
	setSize(1000,740);
        setVisible(true);
    }
 //// Ende des Konstruktors 
 
 
////  Grafik Routinen

  /*private void ShowArray(Graphics g, int[] A, int Lo, int Hi){
  	Dimension d = getSize();
	int XMax = d.width;
	int YMax = d.height;
	if (Hi > XMax) Hi = XMax;
	//System.out.println(XMax+" "+YMax+" "+Lo+" "+Hi);
	int YMitte = YMax/2;
	
	g.clearRect(Lo, 0, Hi, YMax);
	g.setColor(Color.black);
	
	for (int i = Lo; i <= Hi; i++){
           int YVal = A[i];
           //System.out.println(i+" "+YVal);		
           g.drawLine(i, YMitte+YVal, i, YMitte-YVal);
        }
        if (WarteZeit > 0){ // Mach mal Pause
            long t = WarteZeit + System.currentTimeMillis();
            while(System.currentTimeMillis() < t);
            }
        }*/ 
  

  private void ShowArray(Graphics g, int[] A, int Lo, int Hi, Image bild) { //Thomas Horstmeyer
  	Graphics gbild=bild.getGraphics();
	Dimension d=getSize();
	int XMax=d.width;
	int YMax = d.height;
	if (Hi > XMax) Hi = XMax;
  	int YMitte=(int) getHeight()/2;

  	gbild.clearRect(Lo, 0, Hi, YMax);
  	gbild.setColor(Color.black);
  	//folgende zwei Zeilen statt der obigen zwei helfen vielleicht beim debuggen (QuickSort)
  	//Random r=new Random(System.currentTimeMillis());
  	//gbild.setColor(new Color(r.nextInt()));
  	
  	for(int i=Lo; i<=Hi; i++) {
	  	int YVal=A[i];
  		gbild.drawLine(i, YMitte+YVal, i, YMitte-YVal);
  	}
  	
  	g.drawImage(bild, 0, 0, null);
  	 
  	if (WarteZeit > 0){ // Mach mal Pause
            long t = WarteZeit + System.currentTimeMillis();
            while(System.currentTimeMillis() < t);
        }
  }

////  Swap und minPos
 
 private static void Swap(int[] A, int i, int k){
        int h = A[i];
        A[i] = A[k];
        A[k] = h;
        }  

  private static int minPos(int[] A, int Lo, int Hi){
        int Min = Lo;
        for (int i = Lo+1; i <= Hi; i++) if (A[i] < A[Min]) Min = i;
        return Min;
        }
       
////  Es folgen: Die Sortier Routinen
	
    void doBubbleSort(){
       int [] A;
       A = AG.ArrayKopie();
       Graphics g = getGraphics();
       Image bild=createImage(getWidth(), getHeight());		//Bild zum Buffern
       int Hi = A.length-1;
       ShowArray(g, A, 0, Hi, bild);
       
       for (int k = Hi; k > 0; k--){
         boolean test = true;
         for (int i = 0; i < k; i++)
           if ( A[i] > A[i+1]) { Swap (A, i, i+1); test = false;}
         ShowArray(g, A, 0, k, bild);  
         if (test) break;
         }		

       }

    void doSelectionSort(){	
       int [] A;
       A = AG.ArrayKopie();
       Graphics g = getGraphics();
       Image bild=createImage(getWidth(), getHeight());		//Bild zum Buffern
       int Hi = A.length-1;
       ShowArray(g, A, 0, Hi, bild);
       for (int k = 0; k < Hi; k++){
         int Min = minPos(A, k, Hi);
         if ( Min != k) Swap (A, Min, k);
         ShowArray(g, A, k, Hi, bild);
         }
       }
	
    void doInsertionSort(){	
       int [] A;
       A = AG.ArrayKopie();
       Graphics g = getGraphics();
       Image bild=createImage(getWidth(), getHeight());		//Bild zum Buffern
       int Hi = A.length-1;
       ShowArray(g, A, 0, Hi, bild);
       for (int k = 1; k <= Hi; k++){
         if (A[k] < A[k-1]){
            int x = A[k];
            int i;
            for ( i = k; ( (i > 0) && (A[i-1] > x) ) ;  i-- ) A[i] = A[i-1];
            A[i] = x;
            }
        ShowArray(g, A, 0, Hi, bild);
        }
       }

    void doShellSort(){	
       int [] A;
       A = AG.ArrayKopie();
       Graphics g = getGraphics();
       Image bild=createImage(getWidth(), getHeight());		//Bild zum Buffern
       int Hi = A.length-1;
       ShowArray(g, A, 0, Hi, bild);
       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 (A[k] < A[k-h]){
                int x = A[k]; 
                int i;
                for ( i = k; ( (i > (h-1)) && (A[i-h] > x) ) ;  i-=h ) A[i] = A[i-h];
                A[i] = x;
                }
               ShowArray(g, A, 0, Hi, bild);
               }	
       }	
	
    void doQuickSort(){	
       int [] A;
       A = AG.ArrayKopie();
       Graphics g = getGraphics();
       Image bild=createImage(getWidth(), getHeight());		//Bild zum Buffern
       int Hi = A.length-1;
       RekQuickSort(g, A, 0, Hi, bild);
       ShowArray(g, A, 0, Hi, bild);
       }
       
    void RekQuickSort(Graphics g, int[] A, int Lo, int Hi, Image bild){
       //ShowArray(g, A, Lo, Hi, bild);	
       int li  = Lo; 
       int re  = Hi; 
       int mid = (li+re)/2;
       if (A[li]  > A[mid]) Swap(A, li, mid);
       if (A[mid] > A[re])  Swap(A, mid, re);
       if (A[li]  > A[mid]) Swap(A, li, mid);
       // <= 3 Elemente haben wir schon sortiert ! 
       //  > 3 Elemente müssen noch sortiert werden ! 
       if ((re - li) > 2){
          int w = A[mid];
          do{
               while (A[li] < w) li++;
               while (w < A[re]) re--;
               if (li <= re){ Swap(A, li, re); li++; re--;}
            }while (li <= re);  
          if (Lo < re) {
          	ShowArray(g, A, Lo, re, bild);	
          	RekQuickSort(g, A, Lo, re, bild); 
          	}
          if (li < Hi) {
          	ShowArray(g, A, li, Hi, bild);	
          	RekQuickSort(g, A, li, Hi, bild);
          	} 
          }
       	
       }
       
    void DownHeap(int[] A, int i, int m){
       int sonny = 2*i + 1;
       while (sonny <= m){
         if ((sonny < m) && (A[sonny] < A[sonny+1])) sonny++; // Linker oder rechter Zweig
         if (A[i] < A[sonny]) { // tauschen ?
            Swap(A, i, sonny); 
            i = sonny; 
            sonny += sonny + 1;
            } 
         else break;
         }
       }     

    void doHeapSort(){	
       int [] A;
       A = AG.ArrayKopie();
       Graphics g = getGraphics();
       Image bild=createImage(getWidth(), getHeight());		//Bild zum Buffern
       int Hi = A.length-1;
       ShowArray(g, A, 0, Hi, bild);
       
       for (int i = Hi/2; i >= 0; i--) {
       	DownHeap(A, i, Hi);
       	ShowArray(g, A, 0, Hi, bild);
       	}
       for (int i = Hi; i > 0; i--) { 
       	Swap(A, i, 0); 
       	DownHeap(A, 0, i-1);
       	ShowArray(g, A, 0, Hi, bild);
       	}	
       }

    void doDistributionSort(){	
       int [] A;
       A = AG.ArrayKopie();
       Graphics g = getGraphics();
       Image bild=createImage(getWidth(), getHeight());		//Bild zum Buffern
       int Hi = A.length-1;
       ShowArray(g, A, 0, Hi, bild);
       int[] B = new int[Hi+1];
       int[] Count = new int[256]; // per default mit 0 initialisiert
       
       // Byte 1  By1(x) = (x & 0xff)
       //for (int i=0; i < 256; i++) Count[i] = 0;
       for (int i=0; i <= Hi; i++) // Zählen
          Count[ A[i] & 0xff]++;
       for (int i=1; i < 256; i++) // Aufsummieren
          Count[i] += Count[i-1];
       for (int i = Hi; i >= 0; i--) // Verteilen
		  B[--Count[A[i]& 0xff]] = A[i];
	   // for (int i=0; i <= Hi; i++) A[i] = B[i];	 
       System.arraycopy(B, 0, A, 0, Hi+1);
       ShowArray(g, A, 0, Hi, bild);
	   
	   // Byte 2   By2(x) = ((x >>  8) & 0xff)
       for (int i=0; i < 256; i++) Count[i] = 0;
       for (int i=0; i <= Hi; i++) // Zählen
          Count[ (A[i] >>  8) & 0xff]++;
       for (int i=1; i < 256; i++) // Aufsummieren
          Count[i] += Count[i-1];
       for (int i = Hi; i >= 0; i--) // Verteilen
		  B[--Count[(A[i] >>  8) & 0xff]] = A[i];
	   // for (int i=0; i <= Hi; i++) A[i] = B[i];	 
       System.arraycopy(B, 0, A, 0, Hi+1);
       ShowArray(g, A, 0, Hi, bild);
	   
	   // Byte 3   By3(x) = ((x >>  16) & 0xff)
       for (int i=0; i < 256; i++) Count[i] = 0;
       for (int i=0; i <= Hi; i++) // Zählen
          Count[ (A[i] >>  16) & 0xff]++;
       for (int i=1; i < 256; i++) // Aufsummieren
          Count[i] += Count[i-1];
       for (int i = Hi; i >= 0; i--) // Verteilen
		  B[--Count[(A[i] >>  16) & 0xff]] = A[i];
	   // for (int i=0; i <= Hi; i++) A[i] = B[i];	 
	   System.arraycopy(B, 0, A, 0, Hi+1);
	   
	   // Byte 4   By4(x) = ((x >>  24) & 0xff)
       for (int i=0; i < 256; i++) Count[i] = 0;
       for (int i=0; i <= Hi; i++) // Zählen
          Count[ (A[i] >>  24) & 0xff]++;
       for (int i=1; i < 256; i++) // Aufsummieren
          Count[i] += Count[i-1];
       for (int i = Hi; i >= 0; i--) // Verteilen
		  B[--Count[(A[i] >>  24) & 0xff]] = A[i];
	   // for (int i=0; i <= Hi; i++) A[i] = B[i];	 
       System.arraycopy(B, 0, A, 0, Hi+1);
       ShowArray(g, A, 0, Hi, bild);
       }         


////  Implementierung der übrigen Menü Befehle	
    
   
    
 

////  About Box
	
    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("Informatik II a Vorlesung Sommersemester 2000", 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));
	f.add(new Label(" ", Label.CENTER));
	
	f.add(Ok);
	f.pack(); 
	f.setVisible(true);
	}	
	
////  Programm Beenden
    
    void FensterBeenden() {		        
	dispose();
	System.exit(0);
	}	

////  Programm Starten

    public static void main(String args[]) {
    new SortAnimation ();
    }
}