//****************************************************************************
// Hsort.java:	Applet
//
//****************************************************************************
import java.applet.*;
import java.awt.*;

//===========================================================================
// Main Class for applet Hsort
//
//===========================================================================
public class Hsort extends Applet 
{
  final int MAXHEAP = 100;
  final int RWSIZE = 50;
  final int CLSIZE = 600;
  Color bgcol;
  HeapAction theAction;
  int[] heap;
  Panel control;
  HeapCanvas theHeap;
  Button addHeap, delHeap
	  ;
  TextField addVal;
  Label message;

  // Hsort Class Constructor
  //-----------------------------------------------------------------------
  public Hsort()
  {
    heap = new int[MAXHEAP];
    for (int i = 0; i < MAXHEAP; i++) heap[i] = -1;
    for (int i = 0; i < 13; i++) heap[i] = i*10;
  }
  
  // APPLET INFO SUPPORT:
  //	The getAppletInfo() method returns a string describing the applet's
  // author, copyright date, or miscellaneous information.
  //-----------------------------------------------------------------------
  public String getAppletInfo()
  {
    return "Name: Hsort\r\n" +
      "Author: Richard Salter\r\n" +
      "Created with Microsoft Visual J++ Version 1.0";
  }
  
  
  // The init() method is called by the AWT when an applet is first loaded
  // or reloaded.  Override this method to perform whatever initialization
  // your applet needs, such as initializing data structures, loading 
  // images or fonts, creating frame windows, setting the layout manager, 
  // or adding UI components.
  //-----------------------------------------------------------------------
  public void init()
  {
    // If you use a ResourceWizard-generated "control creator" class to
    // arrange controls in your applet, you may want to call its
    // CreateControls() method from within this method. Remove 
    // the following
    // call to resize() before adding the call to CreateControls();
    // CreateControls() does its own resizing.
    //-------------------------------------------------------------------
    resize(600, 400);

    // TODO: Place additional initialization code here
    
    if (getParameter("0") != null) {
      String val;
      int n;
      for (n = 0; (val = getParameter(Integer.toString(n))) != null; n++) {
	try {
	  heap[n] = Integer.parseInt(val);
	} catch (Exception e) {heap[n] = n * 10;}
      }
      for (; n < MAXHEAP; n++) heap[n] = -1;
    }

    String bgcolor = getParameter("bgcolor");
    if (bgcolor == null) {bgcol = Color.white;}
    else {
      try {
	bgcol = new Color(Integer.parseInt(bgcolor.substring(0,2), 16),
			  Integer.parseInt(bgcolor.substring(2,4), 16),
			  Integer.parseInt(bgcolor.substring(4,6), 16));
      } catch (Exception e) {bgcol = Color.white;}
    } 
    setBackground(bgcol);
    theHeap = new HeapCanvas(600, 350, this);
    theHeap.setBackground(bgcol);
    theAction = new HeapAction(heap, this);
    int sz = theAction.heapsize()-1;
    message = new Label
      ("This is array a[0] = "+heap[0]+", a[1] = "+heap[1]+
       ", .. a["+sz+"] = "+heap[sz]);
    message.setBackground(bgcol);
    control = new Panel();
    control.setBackground(bgcol);
    addHeap = new HeapButton("Heapify array", this);
    addHeap.setBackground(bgcol);
    delHeap = new HeapButton("Delete Root", this);
    delHeap.setBackground(bgcol);
    delHeap.disable();
    addVal = new TextField(5);
    addVal.disable();
    control.add(addHeap);
    control.add(addVal);
    control.add(message);
    control.add(delHeap);
    add(control);
    add(theHeap);
    repaint();
  }
  
  // Place additional applet clean up code here.  destroy() is called when
  // when you applet is terminating and being unloaded.
  //----------------------------------------------------------------------
  public void destroy()
  {
    // TODO: Place applet cleanup code here
  }
  
  // Hsort Paint Handler
  /*  public void paint(Graphics g)
  {
    theHeap.paint(g);
  }
  */
  //-----------------------------------------------------------------------
  //	The start() method is called when the page containing the applet
  // first appears on the screen. The AppletWizard's initial implementation
  // of this method starts execution of the applet's thread.
  //-----------------------------------------------------------------------
  public void start()
  {
    // TODO: Place additional applet start code here
  }
  
  //	The stop() method is called when the page containing the applet is
  // no longer on the screen. The AppletWizard's initial implementation of
  // this method stops execution of the applet's thread.
  //-----------------------------------------------------------------------
  public void stop()
  {
  }
  
  // TODO: Place additional applet code here
  
  public void run()
  {
  }
}

class HeapAction implements Runnable {
  
  final static int HEAPEXTRACT = 0;
  final static int HEAPINSERT = 1;
  final static int BUILDHEAP = 2;
  final static int radius = HeapCanvas.RADIUS;
  final static int rwsize = HeapCanvas.RWSIZE;
  final static int clsize = HeapCanvas.CLSIZE;
  final static int SHOWLEN = 750;

  int[] heap;
  Hsort theApplet;
  int key;
  int command;

  HeapAction(int[] heap, Hsort theApplet)
  {this.heap = heap; this.theApplet = theApplet; command = -1;}

  public void run()
  {
    switch (command) {
    case HEAPEXTRACT:
      if (heap[0] == -1) break;
      theApplet.message.setText("Deleting "+heap[0]+" ...");
      theApplet.control.repaint();
      heapExtract(true);
      break;
    case HEAPINSERT:
      theApplet.message.setText("Inserting "+key+" ...");
      theApplet.control.repaint();
      heapInsert(key, true);
      break;
    case BUILDHEAP:
      theApplet.message.setText("Building the Heap ...");
      theApplet.control.repaint();
      buildHeap(true);
      theApplet.addHeap.setLabel("Add to Heap");
      theApplet.addVal.enable();
      break;
    }
    theApplet.theHeap.insertHilite = -1;
    theApplet.theHeap.fillHilite = -1;
    theApplet.theHeap.nodeHilite = -1;
    theApplet.theHeap.repaint();
    theApplet.addHeap.enable();
    if (heapsize() > 0) theApplet.delHeap.enable();
    theApplet.message.setText("");
    theApplet.control.repaint();
  }

  void heapify(int i, boolean show)
  {
    int sz = heapsize();
    if (i >= sz) return;
    int largest = i;
    int l = lson(i);
    int r = rson(i);
    if (l <= sz && heap[l] > heap[i]) largest = l;
    if (r <= sz && heap[r] > heap[largest]) largest = r;
    if (largest != i) {
      if (show) animate(-largest);
      exchange(i, largest);
      if (show) animate(largest);
      heapify(largest, show);
    }
    theApplet.theHeap.repaint();
  }

  void heapInsert(int key, boolean show)
  {
    int i = heapsize();
    heap[i] = key;
    while (i > 0 && heap[parent(i)] < key) {
      if (show) animate(i);
      exchange(i, parent(i));
      if (show) animate(-i);
      i = parent(i);
    }
  }

  void heapExtract(boolean show)
  {
    int sz = heapsize();
    theApplet.theHeap.nodeHilite = sz-1;
    theApplet.theHeap.repaint();
    try {
      Thread.currentThread().sleep((SHOWLEN * 3)/2);
    } catch (Exception e) {}
    theApplet.theHeap.nodeHilite = -1;
    heap[0] = heap[sz-1];
    heap[sz-1] = -1;
    theApplet.theHeap.repaint();
    theApplet.theHeap.nodeHilite = 0;
    animate(0);
    heapify(0, show);
  }

  void buildHeap(boolean show)
  {
    for (int i = heapsize()/2; i >= 0; i--) {
      theApplet.theHeap.nodeHilite = i;
      heapify(i, show);
    }
  }

  void animate(int i) {animate(i, SHOWLEN);}
  void animate(int i, int sleeplen)
  {
    if (i < 0) {
      i = -i;
      theApplet.theHeap.fillHilite = parent(i);
    } else theApplet.theHeap.fillHilite = i;
    theApplet.theHeap.insertHilite = i;
    theApplet.theHeap.repaint();
    try {
      Thread.currentThread().sleep(sleeplen);
    } catch (Exception e) {}
  }

  static int lson(int i) {return 2*i+1;}
  static int rson(int i) {return 2*i+2;}
  static int parent(int i) {return ((i+1)/2)-1;}

  int heapsize()
  {
    int i;
    for (i = 0; heap[i] != -1; i++);
    return i;
  }

  void exchange(int i, int j)
  {
    int tmp = heap[i];
    heap[i] = heap[j];
    heap[j] = tmp;
  }
}