/*
 * @(#)SortItem.java   1.17f 95/04/10 James Gosling
 *
 * Copyright (c) 1994-1995 Sun Microsystems, Inc. All Rights Reserved.
 *
 * Permission to use, copy, modify, and distribute this software
 * and its documentation for NON-COMMERCIAL or COMMERCIAL purposes and
 * without fee is hereby granted. 
 * Please refer to the file http://java.sun.com/copy_trademarks.html
 * for further important copyright and trademark information and to
 * http://java.sun.com/licensing.html for further important licensing
 * information for the Java (tm) Technology.
 * 
 * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
 * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
 * TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
 * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR
 * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
 * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
 * 
 * THIS SOFTWARE IS NOT DESIGNED OR INTENDED FOR USE OR RESALE AS ON-LINE
 * CONTROL EQUIPMENT IN HAZARDOUS ENVIRONMENTS REQUIRING FAIL-SAFE
 * PERFORMANCE, SUCH AS IN THE OPERATION OF NUCLEAR FACILITIES, AIRCRAFT
 * NAVIGATION OR COMMUNICATION SYSTEMS, AIR TRAFFIC CONTROL, DIRECT LIFE
 * SUPPORT MACHINES, OR WEAPONS SYSTEMS, IN WHICH THE FAILURE OF THE
 * SOFTWARE COULD LEAD DIRECTLY TO DEATH, PERSONAL INJURY, OR SEVERE
 * PHYSICAL OR ENVIRONMENTAL DAMAGE ("HIGH RISK ACTIVITIES").  SUN
 * SPECIFICALLY DISCLAIMS ANY EXPRESS OR IMPLIED WARRANTY OF FITNESS FOR
 * HIGH RISK ACTIVITIES.
 */

import java.applet.Applet;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.awt.image.BufferedImage;
import java.util.Random;

/** Demo-Applet für Sortier-Algorithmen. <br />
 *  <br />
 *  Ein Objekt dieser Klasse kann die Arbeitsweise eines beliebigen Sortier-
 *  Algorithmus vorführen.<br />
 *  <br />
 *  Der konkrete Algorithmus wird durch Ableitung von {@link SortAlgorithm}
 *  dargestellt.<br />
 *  <br />
 *  <a name="co" id="co">&copy;</a> 
 *  Ursprüngliches Copyright James Gosling<br />
 *  für die Quellen SortItem.java  (V.1.17f 95/04/10) und 
 *  SortAlgorithm.java  (V.1.6f 95/01/31), welche weitgehend umgearbeitet
 *  in diese Quelle eingingen. Die ursprüngliche Copyright-Notiz wurde 
 *  bedingungsgemäß am Anfang jeder Quelle belassen. Sie gilt sinngemäß
 *  weiter.<br />
 *  <br />
 *  Copyright 2005, 2010 &nbsp; Albrecht Weinert<br />
 *  <br />
 *  @author   Albrecht Weinert
 *  @version  V.1, 21.01.2010
 */
public final class SortApplet extends Applet 
                                        implements Runnable, MouseListener {

/** Der Thread, der sortiert.<br />
 *  <br /<
 *  null, wenn nichts läuft.<br />
 */
    private Thread sortThread;
   
/** Das zu sortierende Array. <br />
 *  <br />
 *  Es wird von diesem Applet vorbesetzt und gemischt bereit gestellt.<br />
 *  Der konkrete Algorithmus {@link #algorithm} muss es sortieren und jeden
 *  Schritt mit {@link #pause(int, int)} melden.<br />
 *  <br />
 */
   int arr[];
   
/** Oberer Index zum aktuellen Verlauf der Sortierung.<br />
 *  <br />
 *  Rote Markierung; -1 heißt nicht vorhanden / zutreffend.<br />
 */
   protected int obItem = -1;
   
/** Unterer Index zum aktuellen Verlauf der Sortierung.<br />
 *  <br />
 *  Blaue Markierung; -1 heißt nicht vorhanden / zutreffend.<br />
 */
   protected int untItem = -1;
   
/**  Name des Algorithmus. <br />
 *   <br />
 *   Wird dem Applet-Parameter {@code alg} entnommen und mit Algorithm
 *   ergänzt. Eine so benannte Klasse wird dann im selben Verzeichnis
 *   oder .jar-File erwartet.
 */
   protected String algName;
   
/** Sortier-Algorithmus (oder null). <br />
 */
   SortAlgorithm algorithm;

/** Höhe des Applets. <br />
 *  <br />
 *  Wird bei jedem (Neu-) Mischen aktualisiert.<br />
 *  <br />
 *  Mindesthöhe 50.
 */   
   protected int hApp;
   
/** Breite des Applets. <br />     
 *  <br />
 *  Wird bei jedem (Neu-) Mischen aktualisiert.<br />
 *  <br />
 *  Mindestbreite 50.
 */   
   protected int bApp;
   

/** Länge des Sortier-Arrays. <br />     
 *  <br />
 *  Wird bei jedem (Neu-) Mischen aktualisiert. Gegebenenfalls wird 
 *  das Array {@link #arr} entsprechend neu erzeugt.<br />
 *  <br />
 *  Die Länge des Array richtet sich nach {@link #bApp}, {@link #hStrich}
 *  und {@link #hLcke}.<br />
 */   
   protected int lArr;


/** Höhe eines Array-Elements als waagrechter Strich in Pixeln. <br />
 *  <br />
 *  Hinweis: Die ursprüngliche Gosling-Klasse verwendete hier fest reinkodiert
 *  1 (Eins). Von der Frage des Programmierstils abgesehen führt dies zu
 *  teilweise sehr schlechter Erkennbarkeit auf hochauflösenden Bildschirmen
 *  und besonders bei der Vorführung mit Beamern.<br />
 *  <br />
 *  Erlaubter Wertebereich: 2..15<br />
 *  Default: 4<br />
 */   
   protected int hStrich = 4;

/** Höhe der (waagrechten) Lücke zwischen den Array-Elementen in Pixeln. <br />
 *  <br />
 *  Hinweis: Siehe {@link #hStrich}.<br />
 *  <br />
 *  Erlaubter Wertebereich: 1..6<br />
 *  Default: 3<br />
 */   
   protected int hLcke = 3;
   
/** Höhe eines waagrechten Array-Elementbalkens in der Darstellung. <br />
 *  <br />
 *  Summe aus {@link #hStrich} und {@link #hLcke}.
 */
   protected int hSum; 

/** Länge der Pause / ms. <br />
 *  <br />
 *  default: 35
 */ 
   protected long lenPau = 35;

   Random rand = new Random();
   BufferedImage buffI;
   Graphics buGr;

/** Hintergrundfarbe. <br />
 *  <br />
 *  default: helles Grau
 */   
   Color bgCol = new Color(224, 224, 224);
   
/** Bereitstellen eines zufallsbesetzten Arrays. <br />
 *  <br />
 *  Das zu sortierende Array wird passend zur Höhe des Applets
 *  ({@link #hApp}), der Striche ({@link #hStrich})und der Lücken 
 *  ({@link #hLcke})bereitgestellt.<br />
 *  <br />
 *  Es wird mit Werten von 1 bis Breite ({@link #bApp}) - 2 gefüllt.<br />
 */
   protected void scramble() {
      hApp = getHeight();
      bApp = getWidth();
      hSum = hLcke + hStrich;
      lArr = (hApp - hLcke) / hSum;
      if (arr == null || arr.length != lArr) arr = new int[lArr];
      if (buffI == null) { 
         buffI = new BufferedImage(bApp, hApp, BufferedImage.TYPE_3BYTE_BGR);
         buGr = buffI.getGraphics();
      }
      for (int i = lArr; --i >= 0;) {
         arr[i] = rand.nextInt(bApp-1) + 1;
      }
   } // scramble()

   
/** Stand der Algorithmus-Abarbeitung zeigen und Pausieren. <br />
 *  <br />
 *  Falls ein Sortieralgorithmus läuft, wird der aktuelle Inhalt des
 *  Arrays {@link #arr} mit ggf. Markierungen dargestellt und 
 *  {@link #lenPau} ms Pause gemacht.<br />
 *  @see SortAlgorithm
 *  @see #paint(Graphics)
 *  @param obItem obere Markierung (rot) Index oder -1 für keine
 *  @param untItem untere Markierung (blau) Index oder -1 für keine
 */
   public void pause(int obItem, int untItem) {
      this.obItem = obItem;
      this.untItem = untItem;
      //  System.out.println(" /// Parent pause " + sortThread);
      if (sortThread != null) {
         repaint();
      }
      try {Thread.sleep(lenPau);} catch (Exception e){}
   } // pause(int, int)
   
/** Initialisierung des Applet. <br />
 *  <br />
 *  Ausgewertete Parameter:<br />
 *  alg = Name des Algorithmus<br /> &nbsp; &nbsp;
 *   (z.B. BubleSort2); wird mit Algorithm (zu  BubleSort2Algorithm)
 *   ergänzt.<br />
 *  (Geplant Höhen der Strichdarstellung, Pausenzeit).<br />
 */
   @Override public void init() {
      String at = getParameter("alg");
      if (at != null) algName = at + "Algorithm";
      System.out.println("  //  SortApplett.init " + algName);
      scramble(); // Startbild
      addMouseListener(this);
   } 
   
/** (Neu-) Malen des Array-Inhalts als Strichestapel. <br />
 *  <br />
 *  Impl.-Hinw.: Modif. We.: Variable Höhen, Doppelpufferung.
 */
   @Override  public void paint(Graphics g) {
      buGr.setColor(bgCol);
      buGr.fillRect(0, 0,  bApp, hApp);

      buGr.setColor(Color.black);
      int y = hLcke;
      for (int i = 0; i < lArr; ++i, y += hSum) {
        final int wrt =  arr[i];
        // buGr.drawLine(0, y, arr[i], y); (Gosling)
        buGr.fillRect(0, y, wrt, hStrich);
        if (obItem != i && untItem != i) continue;
        int xT = wrt < 12 ? wrt : 12;
        if (obItem == i) { // dünner roter Strich an der Oberkante
           buGr.setColor(Color.red);
           int yT  = y + hStrich - 1;
           buGr.drawLine(xT, yT , bApp, yT);
        } // dünner roter Strich an der Oberkante
        if (untItem == i) { // dünner blauer Strich an der Unterkante
           buGr.setColor(Color.blue);
           buGr.drawLine(xT, y , bApp, y);
        }  // dünner blauer Strich an der Unterkante
        buGr.setColor(Color.black);
      } // for
      g.drawImage(buffI, 0, 0, bApp, hApp, null); // Doppelpuffer
   } // paint(Graphics)
   
/** Update ohne Löschen. <br />
 *  <br />
 *  Delegiert an {@link #paint(Graphics)}, welches flackerfreie
 *  Doppelpufferung organisiert.<br />
 */
   @Override public void update(Graphics g) { paint(g); }
   

/** Der Sortier-Thread. <br />
 *  <br />
 *  Ein Objekt dieser ({@link Applet}-Klasse {@link SortApplet} wird bei 
 *  Sortier-Demo-Start als {@link java.lang.Thread} zum Sortieren gestartet.<br />
 *  <br />
 *  Dies ist die Arbeitsmethode. Sie versucht beim ersten Lauf die Klasse des
 *  konkreten Algorithmus ({@link SortAlgorithm}-Erbe) aufgrund des Namens
 *  {@link #algName} bzw. Applet-Parameters alg, z.B.<br /> &nbsp;
 *  &lt;param name=&quot;alg&quot; value=&quot;SelectionSort&quot;&gt;<br />
 *  zu laden und bei Erfolg beliebig oft zu verwenden.<br />
 *  <br />
 *  @see java.lang.Thread#run
 *  @see #mouseReleased(MouseEvent)
 *  @see SortAlgorithm#init()
 *  @see SortAlgorithm#sort(int[])
 */
   @Override public void run() {
      try {
         if (algorithm == null) {
            algorithm = (SortAlgorithm)Class.forName(algName).newInstance();
            algorithm.parent = this;
         }
         algorithm.init();
         algorithm.sort(arr);
      } catch(Exception e) {  } // ignorieren (vorläufig)
      if (Thread.currentThread() == sortThread) sortThread = null; // fertig
   } // run() 

   
/** Applet-Stopp. <br />
 *  <br />
 *  Versucht laufende Sortierungen zu stoppen.<br />
 */
   @Override public synchronized void stop() {
      if (algorithm != null) algorithm.stop();
      if (sortThread != null) {
         sortThread.interrupt();
         sortThread = null;
      }
   } // stop()
   
   
/** Start der Sortierung. <br />
 *  <br />
 *  Wenn noch keine Sortierung läuft ({@link #sortThread}), wird sie
 *  gestartet.<br />
 *  <br />
 *  Implementierungshinweis (Gosling): This
 *  routine makes sure we do not simultaneously start several sorts if the
 *  user repeatedly clicks on the sort Applet. It needs to be synchronised
 *  with the stop() method because they both manipulate the common 
 *  {@link #sortThread} variable. (So ist es.)<br />
 */
   private synchronized void startSort() {
      if (sortThread == null || !sortThread.isAlive()) {
         scramble();
         repaint();
         sortThread = new Thread(this);
         sortThread.start();
      }
   } // startSort()
  
   
/** Mausereignis.<br />
 *  <br />
 *  Der Benutzer klickte auf das Applet.<br />
 *  Startet die Sortierung, falls sie noch nicht läuft.<br />
 */
   @Override public void mouseReleased(MouseEvent e) {
      startSort();
    } // mouseReleased(MouseEvent

   @Override public void mouseClicked(MouseEvent e) {}
   @Override public void mousePressed(MouseEvent e) {}
   @Override public void mouseEntered(MouseEvent e) {}
   @Override public void mouseExited(MouseEvent e) {}

   
//=====================================================================

/** Ein abstrakter Sortier-Algorithmus für Demonstrationen.<br />
 *  <br />
 *  Konkrete Algorithmen zur Demonstration in einem {@link SortApplet}
 *  müssen von dieser inneren Klasse {@link SortAlgorithm} abgeleitet sein.
 *  <br />
 *  <a href="SortApplet.html#co">&copy;</a> 
 *  Copyright 2005 &nbsp; Albrecht Weinert<br />
 *  Copyright- und sonstige Hinweise siehe bei der umfassenden Klasse
 *  <a href="SortApplet.html#co">SortApplet</a>.<br />
 *  <br />
 *  Hinweis: Innere Klasse (nicht static) geht nicht wegen
 *  Applet-Problemen.<br />
 *  @version siehe umfassende Klasse {@link SortApplet}
 *  @author  Albrecht Weinert
 */
    public static abstract class SortAlgorithm {

/** Stopp-Anforderung. <br />
 *  <br />
 *  Falls true, sofort mit Sortieren {@link #sort(int[])} aufhören.
 */
      protected boolean stopRequested;
        
/** Eltern-Applet. <br /> 
 *  <br />
 *  Muss in der umfassenden Klasse gesetzt werden oder der 
 *  Konstruktor 
 *  {@link SortApplet.SortAlgorithm#SortAlgorithm(SortApplet) SortAlgorithm(SortApplet)}
 *  ist zu nutzen.<br />
 */
      private SortApplet parent;

/** Konstruktor für umfassende Klasse. <br /> */
      protected SortAlgorithm() {}

/** Konstruktor für andere Anwendungen. <br /> */
      protected SortAlgorithm(SortApplet parent){ this.parent = parent;}

/** Maximal möglichen Wert für die Zufallsbesetzung des Arrays. <br />
 *  <br />
 *  Hinweis: Dies muss nicht das mit der von {@link SortApplet#scramble()}
 *  tatsächlich gesetzte Maximum sein.<br />
 *  <br />
 */
      protected int getMaxPossiVal() { return parent.bApp - 2; }         
    
/** Mach mal Pause. <br />
 *  <br />
 *  Pausiert unter Beibehaltung der bisherigen Markierungen.<br />
 *  <br />
 *  @see #pause(int, int)
 */
      protected void pause() {
         if (stopRequested) return;
         parent.pause(parent.obItem, parent.untItem);
      } // pause()
      
/** Mach mal Pause. <br />
 *  <br />
 *  Pausiert unter Beibehaltung der bisherigen unteren Markierung.<br />
 *  <br />
 *  @see #pause(int, int)
 */
    protected void pause(int item1)  {
       if (stopRequested) return;
       parent.pause(item1, parent.untItem);
    } // pause(int) /*
    
/** Eine Pause / Markierung eines Sortierschritts. <br />
 *  <br />
 *  Ist vom Sortieralgorithmus ({@link #sort(int[])}) nach jedem Schritt
 *  aufzurufen. item1 und item2 stellen einen Index im Array dar, der
 *  den aktuellen Schritt markiert.<br />
 *  <br />
 *  <br />
 *  @param item1 Index im zu sortierenden Array mit Bezug zum Schritt
 *  @param item2 Index im zu sortierenden Array mit Bezug zum Schritt
 */
      protected void pause(int item1, int item2) {
         if (stopRequested) {
          // System.out.println(" /// sort pause stop is reqesetd");
          return;
         }
       // System.out.println(" /// sort pause " + item1
          //                   + ", " + item2 + " parent " + parent);
         parent.pause(item1, item2);
      } // pause(int, int) */
    
/** Stopp des Sortierens, Abbruch. <br />
 *  <br />
 *  Diese Implementierung setzt (einfach) {@link #stopRequested} auf true.
 *  Implementierungen von {@link #sort(int[])} müssen darauf reagieren.<br />
 */
      public void stop() {
         stopRequested = true;
      }
    
/** Initialisierungen. <br /> */
      public void init() {
         stopRequested = false;
      }
    
/** Die eigentliche Sortiermethode. <br />
 *  <br />
 *  Diese Methode soll, das bereitgestellte Array sortieren und jeden
 *  (wesentlichen) Schritt mit {@link #pause(int, int)} markieren und zur 
 *  Anzeige bringen.<br />
 *  <br />
 *  Vor Aufruf dieserMethode muss {@link #init()} aufgerufen worden sein.
 */
      abstract void sort(int a[]);

   } // class SortAlgorithm  =============================================
   
} // class SortApplet ( 13.11.2005, 15.01.2010)