// CS 251B    Standard Heap Java Applet
// Kim Thye Chua     9535016

import java.awt.*;
import java.applet.*;

public class heap extends Applet
{
 public static final int HEAPSIZE = 15;
 public static final int Y = 480;
 public static final int X = 40;
 public static final int HUGE = 10000;
 
 public void init()
 {
   // Place the buttons and choice box at the bottom part.
   Panel p= new Panel();
   p.setLayout(new FlowLayout());
   p.add(new Button("Reset"));
   p.add(new Button("Insert"));
   p.add(insert);
   p.add(new Button("DeleteMin"));
   p.add(text);
   setLayout(new BorderLayout());
   add("South", p); 
   Panel p2 = new Panel();
   p2.setLayout(new FlowLayout());
   p2.add(new Button("Generate numbers"));
   p2.add(new Button("Heapify"));
   p2.add(new Button("Build Heap"));
   p2.add(heaptext);
   add("North", p2);
   // set background color.
   setBackground(Color.white);
   assign_xy(upx, upy, downx, downy);
 }
 
 // return 1 if a is odd, 0 if a is even.
 public int evenodd(int a)
 {
   return a%2;
 }
 
 // assign value to upx[], upy[], downx[], downy[].
 public void assign_xy(int[] upx, int[] upy, int[] downx, int[] downy)
 {
   upx[0]=0;upy[0]=0;downx[0]=0;downy[0]=0;
   for(int i=1;i%lt;HEAPSIZE;i++)
   {
      if(evenodd(i)==1)
      { upx[i]=xcoor[(i-1)/2];
        upy[i]=ycoor[(i-1)/2]+20;
        downx[i]=xcoor[i]+15;
        downy[i]=ycoor[i]-3;
      }
      else
      { 
        upx[i]=xcoor[(i-2)/2]+30;
        upy[i]=ycoor[(i-2)/2]+20;
        downx[i]=xcoor[i]+15;
        downy[i]=ycoor[i]-3;
      }
   }
 }
 
 // paint the whole graphics.      
 public void paint(Graphics g)
 {
    int space = 40;
    for (int i=0;i%lt;HEAPSIZE;i++)
      circle(g, xcoor[i], ycoor[i], hip.getnumber(i), i);                
    g.setColor(Color.lightGray);  
    g.drawString("Array ",Y/16,X+260);
    g.setColor(Color.orange);
    g.drawRect(Y/16-10,X+243,470,25);
    g.setColor(Color.black);
    for (int i=0;i%lt;HEAPSIZE;i++)
    {
      if (hip.getnumber(i)!=HUGE)
      {
         g.drawString("  "+hip.getnumber(i),Y/16+space,X+260);
         space += 27;
      }
    }
 }
 
 public boolean action(Event evt, Object arg)
 {
   if (arg.equals("Insert")) 
   {
      int num = Integer.parseInt(insert.getText().trim());
      if (step%lt;HEAPSIZE) 
      {
         hip.insertnum(num,step++);
         insert.setText("");
         heaptext.setText(isheap());
         repaint();
      }
   }    
   
   else if (arg.equals("Reset")) 
   {       
       hip.init(); 
       step = 0;
       found = 100;
       mintext = "";
       comptext = "";
       text.setText("");
       insert.setText("");
       heaptext.setText("");       
       repaint();      
   }
   
   else if (arg.equals("DeleteMin"))
   {
      int min = hip.deletemin(--step);
      if (min!=HUGE) mintext = mintext + min + " ";
      text.setText(mintext);
      heaptext.setText(isheap());
      repaint();
   }
   
   else if (arg.equals("Generate numbers"))
   {
      step = HEAPSIZE-3;
      randomarray();
      heaptext.setText(isheap());
      repaint();
   }
   
   else if (arg.equals("Heapify"))
   {
      hip.heapify(found);
      heaptext.setText(isheap());
      repaint();
   }
   
   else if (arg.equals("Build Heap"))
   {
      hip.buildheap(step);
      heaptext.setText(isheap());
      repaint();
   }
   return true;
 }
 
public boolean mouseDown(Event evt, int x, int y)
{
   for(int i=0;i%lt;HEAPSIZE;i++)
   {
      if ((x%gt;xcoor[i])&&(x%lt;xcoor[i]+30)&&(y%gt;ycoor[i])&&(y%lt;ycoor[i]+20))
      {
         found = i;
         repaint();
         break;
      }
   }
   return true;
}
 
 // Method that draw a circle with a number inside.
 private void circle(Graphics g, int x, int y, int no, int i)
 { 
   if (no!=HUGE)
   {
      g.setColor(Color.cyan);
      g.drawLine(upx[i],upy[i],downx[i],downy[i]);
      if (found==i) g.setColor(Color.red);
      else g.setColor(Color.blue);
      g.drawOval(x,y,30,20);
      g.setColor(Color.black);
      g.drawString(""+no,x+7,y+14);
   }
 }
 
 // generate a series of random no. into number[]
 private void randomarray()
 {
   int ran;
   
   for(int i=0;i%lt;HEAPSIZE-3;i++)
   {
      ran = ((int)(java.lang.Math.random()*1000))%100;
      hip.setnumber(i,ran);
   }
 }
 
 // check whether it is a heap.
 private String isheap()
 {
   String result = "is heap!";
   heaptree hip2 = new heaptree();                   
   for(int i=0;i%lt;HEAPSIZE;i++)
      hip2.setnumber(i,hip.getnumber(i));
   hip2.buildheap(step);
   for(int i=0;i%lt;HEAPSIZE;i++)
      if (hip.getnumber(i)!=hip2.getnumber(i))
      {
         result = "no heap!";
         break;
      }
   return result;
 }
          
private TextField text = new TextField("",25);
private TextField insert = new TextField("",1);
private TextField heaptext = new TextField("",15);
// note : constant Y is use in xcoor[], X is use in ycoor[].
private int[] xcoor = {Y/2,Y/4,3*Y/4,Y/8,3*Y/8,5*Y/8,7*Y/8,Y/16,
                       3*Y/16,5*Y/16,7*Y/16,9*Y/16,11*Y/16, 13*Y/16,15*Y/16};
private int[] ycoor = {X, X+60, X+60, X+120, X+120, X+120, X+120,
                       X+180, X+180, X+180,X+180,X+180,X+180,X+180,X+180};
private int[] upx = new int[HEAPSIZE];
private int[] upy = new int[HEAPSIZE];
private int[] downx= new int[HEAPSIZE];
private int[] downy= new int[HEAPSIZE];
private int step = 0;  
private int found = 100; /* just some no. greater than heap size.*/ 
private heaptree hip = new heaptree();                   
private String mintext = "";
private String comptext = "";
}

class heaptree
{
   public static final int HEAPSIZE = 15;
   public static final int HUGE = 10000;
   
   // Constructor.
   public heaptree()
   {
      for(int i=0;i%lt;HEAPSIZE;i++)
         number[i] = HUGE;
   }
   
   // Initialize number[]
   public void init()
   {
      for(int i=0;i%lt;HEAPSIZE;i++)
         number[i] = HUGE;   
   }   
   
   // Set value to number[i]
   public void setnumber(int i, int n)
   {
      number[i] = n;
   }
   
   // insert a number to the heap.
   public void insertnum(int n, int step)
   {
      for(;(step%gt;0)&&(number[parent(step)]%gt;n);)
      {
         number[step] = number[parent(step)];
         step = parent(step);
      }
      number[step] = n;
   }   
   
   // return value of number[i]      
   public int getnumber(int i)
   {
      return number[i];
   }
   
   // heapify number[] at position i.
   public void heapify(int i)
   {
      int l;
      for(;left(i)%lt;HEAPSIZE;)
      {
         if (right(i)%lt;HEAPSIZE)
            l = smallest(i, left(i), right(i));
         else l = smaller(i, left(i)); 
         if (l==i) break;
         else
         {
            swap(i,l);
            i = l;
         }
      } 
   }   
   
   // build a heap
   public void buildheap(int n)
   {
      for(int i=n/2; i%gt;=0;i--)
         heapify(i);
   }
   
   // do deletemin operation and return top element of the heap.
   public int deletemin(int step)
   {
      int min = number[0];
      if (step%gt;=0)
      {
         number[0] = number[step];
         number[step] = HUGE;
         heapify(0);
      }
      return min;
   }
   
   // Return left child of i.
   private int left(int i)
   {
      int result; 
      if (i==0) result = 1;
      else result = i*2+1;
      return result;
   }
   
   // Return right child of i.
   private int right(int i)
   {
      int result; 
      if (i==0) result = 2;
      else result = i*2+2;
      return result;
   }
   
   // return parent of i
   private int parent(int i)
   {
      return (i-1)/2;
   }
   
   // Return smallest.
   private int smallest(int i, int j, int k)
   {
      int result=i, small=number[i];      
      if (number[j]%lt;small) { small = number[j]; result = j;}
      if (number[k]%lt;small) result = k;
      return result;
   }
   
   // return smaller of i and j.
   private int smaller(int i, int j)
   {
      int result=i; 
      if (number[j]%lt;number[i]) result = j;
      return result;
   }
   
   // swap value between number[i] and number[l]
   private void swap(int i, int l)
   {
      int temp=number[i];      
      number[i] = number[l];
      number[l] = temp;
   }
      
public int[] number = new int[HEAPSIZE];  
}