// Name   :
// Matric#:
// Group# :
// CS1102 Lab 10B
//
// This is a graded lab.  No discussion are allowed.
//
// A copy of this program can also be found at:
// http://www.comp.nus.edu.sg/~cs1102/B/b.html
//
// You are given a copy of textbook's implementation of BinaryHeap.
// It has been mildly simplified, but they should look familiar to 
// you.
//
// In this lab, you are required to write two methods, 
// - delete(p), which deletes the key at position p of the heap,
// - updateKey(p, v), which change the value of the key at position p to v.
// See the comments above these methods for details.
// 
// You are free to use the existing heap methods to help you.

import java.util.*;

class UnderflowException extends RuntimeException {
  public UnderflowException (String msg)
  {
  }
}

/**
 * Implements a binary heap.
 * Note that all "matching" is based on the compareTo method.
 * @author Mark Allen Weiss
 */
class BinaryHeap
{
  /**
   * Modify the key of element at position p to newValue.
   * Must maintain heap property.  Throws NoSuchElementException()
   * if element at position p does not exist.
   */
  public void updateKey( int p, Comparable newVal )
  {
    // WRITE YOUR METHOD HERE
  }


  /**
   * Delete the key at position p.  Throw NoSuchElementException if 
   * no such element at position p.
   */
  public void delete( int p )
  {
    // WRITE YOUR METHOD HERE
  }

  /**
   * Return true if array satisfy the Heap property.  Return false
   * otherwise.
   */
  public boolean isHeap()
  {
    return isHeap(1);
  }

  private boolean isHeap(int k)
  {
    if (k*2 > currentSize)
    {
      return true;
    }

    if (array[k].compareTo(array[k*2]) <= 0)
    {
      if (k*2 + 1 <= currentSize)
      {
        if (array[k].compareTo(array[k*2 + 1]) <= 0)
        {
          return isHeap(k*2) && isHeap(k*2+1);
        }
        else
          return false;
      }
      else // k*2 == currentSize!
      {
        return true;
      }
    }
    else
      return false;
  }

  /**
   * Returns a string representation of this heap.
   */
  public String toString( )
  {
    if (currentSize == 0)
      return "empty";
    String s = "";

    for (int i = 1; i <= currentSize; i++)
    {
      s = s + array[i] + " ";
    }
    return s;
  }

  /**
   * Construct the binary heap.
   */
  public BinaryHeap( )
  {
    currentSize = 0;
    array = new Comparable[ DEFAULT_CAPACITY + 1 ];
  }

  /**
   * Construct the binary heap from an array.
   * @param items the inital items in the binary heap.
   */
  public BinaryHeap( Comparable [ ] items )
  {
    currentSize = items.length;
    array = new Comparable[ items.length + 1 ];
    
    for( int i = 0; i < items.length; i++ )
      array[ i + 1 ] = items[ i ];
    buildHeap( );  
  }
  
  /**
   * Insert into the priority queue.
   * Duplicates are allowed.
   * @param x the item to insert.
   */
  public void insert( Comparable x )
  {
    if( currentSize + 1 == array.length )
      doubleArray( );

    // Percolate up
    int hole = ++currentSize;
    array[ 0 ] = x;
    
    for( ; x.compareTo( array[ hole / 2 ] ) < 0; hole /= 2 )
      array[ hole ] = array[ hole / 2 ];
    array[ hole ] = x;
  }
    
  /**
   * Find the smallest item in the priority queue.
   * @return the smallest item.
   * @throws UnderflowException if empty.
   */
  public Comparable findMin( )
  {
    if( isEmpty( ) )
      throw new UnderflowException( "Empty binary heap" );
    return array[ 1 ];
  }

  /**
   * Remove the smallest item from the priority queue.
   * @return the smallest item.
   * @throws UnderflowException if empty.
   */
  public Comparable deleteMin( )
  {
    Comparable minItem = findMin( );
    array[ 1 ] = array[ currentSize-- ];
    percolateDown( 1 );

    return minItem;
  }

  /**
   * Establish heap order property from an arbitrary
   * arrangement of items. Runs in linear time.
   */
  private void buildHeap( )
  {
    for( int i = currentSize / 2; i > 0; i-- )
      percolateDown( i );
  }

  /**
   * Test if the priority queue is logically empty.
   * @return true if empty, false otherwise.
   */
  public boolean isEmpty( )
  {
    return currentSize == 0;
  }

  /**
   * Returns size.
   * @return current size.
   */
  public int size( )
  {
    return currentSize;
  }
  
  /**
   * Make the priority queue logically empty.
   */
  public void makeEmpty( )
  {
    currentSize = 0;
  }

  private static final int DEFAULT_CAPACITY = 10;

  private int currentSize;    // Number of elements in heap
  private Comparable [ ] array; // The heap array

  /**
   * Internal method to percolate down in the heap.
   * @param hole the index at which the percolate begins.
   */
  private void percolateDown( int hole )
  {
    int child;
    Comparable tmp = array[ hole ];

    for( ; hole * 2 <= currentSize; hole = child )
    {
      child = hole * 2;
      if( child != currentSize &&
          array[ child + 1 ].compareTo( array[ child ] ) < 0 )
        child++;
      if( array[ child ].compareTo( tmp ) < 0 )
        array[ hole ] = array[ child ];
      else
        break;
    }
    array[ hole ] = tmp;
  }
  
  /**
   * Internal method to extend array.
   */
  private void doubleArray( )
  {
    Comparable [ ] newArray;

    newArray = new Comparable[ array.length * 2 ];
    for( int i = 0; i < array.length; i++ )
      newArray[ i ] = array[ i ];
    array = newArray;
  }
}

public class Lab10B
{
  // Test program
  public static void main( String [ ] args )
  {
    Random r = new Random();
    BinaryHeap h = new BinaryHeap();

    for (int i = 0; i < 10; i++)
    {
      h.insert(new Integer(r.nextInt(24)));
    }

    // Delete some keys.
    int count = 10;
    for (int i = 0; i < 3; i++)
    {
      h.delete(r.nextInt(count--) + 1);
    }

    if (h.isHeap() && h.size() == 7)
    {
      System.out.println("After deleting some keys, h is still a heap.. OK");
    }
    else
    {
      System.out.println("delete() fails to update the heap properly.. NOT OK");
      System.out.println("Heap is " + h);
    }

    h.insert(new Integer(r.nextInt(24)));
    h.insert(new Integer(r.nextInt(24)));
    h.insert(new Integer(r.nextInt(24)));

    System.out.println("Before update, heap is " + h);
    // Update some keys.
    for (int i = 0; i < 20; i++)
    {
      h.updateKey(r.nextInt(10) + 1, new Integer(r.nextInt(30) + 4));
    }
    System.out.println("After update, heap is " + h);

    if (h.isHeap() && h.size() == 10)
    {
      System.out.println("After updating some keys, h is still a heap.. OK");
    }
    else
    {
      System.out.println("updateKey() fails to update the heap properly.. NOT OK");
    }
    h = new BinaryHeap();
    try 
    {
      h.updateKey(r.nextInt(4), new Integer(r.nextInt(24)));
    } 
    catch (NoSuchElementException e)
    {
      System.out.println("updateKey() on empty heap => exception. OK");
    }

    try 
    {
      h.delete(r.nextInt(10));
    } 
    catch (NoSuchElementException e)
    {
      System.out.println("delete() on empty heap => exception. OK");
    }
  }
}