// Name   :
// Matric#:
// Group# :
// CS1102 Lab 10C
//
// 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/c.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, 
// - printLessThan(c), which output all elements in the heap with values 
//   less than c.
// - findMax(), which finds the maximum value in the heap.
//
// You are to make use of the heap property to make your method as 
// efficient as possible.  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
{
  /**
   * YOUR METHODS BEGIN HERE
   */

  /**
   * Print all elements in the heap with values less than the
   * given upperBound.  Your program must run in O(k), where
   * k is the size of the output.
   */
  public void printLessThan( Comparable upperBound )
  {
    System.out.println("BEGIN output of printLessThan " + upperBound);
    // WRITE YOUR CODE HERE
    System.out.println("END of output");
  }


  /**
   * Find Largest element.  You methods must examine as few elements
   * as possible. Throw NoSuchElementException if maximum element
   * does not exist.
   */
  public Comparable findMax( )
  {
    // WRITE YOUR CODE HERE
  }

  /**
   * 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;
  }

  /**
   * 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;
  }


}

public class Lab10C {

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

    System.out.println("printLessThan() on empty heap => shouldn't see output");
    h.printLessThan(new Integer(r.nextInt(30)));

    try 
    {
      Integer i = (Integer)h.findMax();
    } 
    catch (NoSuchElementException e)
    {
      System.out.println("findMax() on empty heap => exception. OK");
    }

    for (int k = 0; k < 10; k++)
    {
      h.insert(new Integer(r.nextInt(25)));
      System.out.println();
      System.out.println("Heap is " + h);
      h.printLessThan(new Integer(r.nextInt(30)));
      Integer i = (Integer)h.findMax();
      System.out.println("Max is " + i);
    }
  }
}