// Name   :
// Matric#:
// Group# :
// CS1102 Lab 10A
//
// 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/a.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, 
// - isHeap(), which verifies the property of the heap, and
// - findSecondMin(), which returns the second smallest elements in 
//   the heap.
// 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
   */

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

  /**
   * Return the second smallest key.  Must not modify heap.
   * Throw NoSuchElementException if the 2nd minimum element
   * does not exist.
   */
  public Comparable find2ndMin( )
  {
    // WRITE YOUR CODE HERE
    return null;  // For compilation, you might want to remove this.
  }

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

  /**
   * Randomly permute the heap for testing.
   */
  public void messUp( )
  {
    Random r = new Random();
    for (int i = 0; i < 3; i++)
    {
      int j = r.nextInt(currentSize);
      int k = r.nextInt(currentSize);
      Comparable temp = array[j];
      array[j] = array[k];
      array[k] = temp;
    }
  }

  /**
   * 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;
  }
  
  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 Lab10A {
  // Test program
  public static void testFind2ndMin()
  {
    BinaryHeap h = new BinaryHeap();
    Random r = new Random();

    for (int i = 0; i < 2; i++)
    {
      try 
      {
        h.find2ndMin();
      } 
      catch (NoSuchElementException e) 
      {
        System.out.println("find2ndMin() on heap with < 2 items caused an exception.. OK");
      } 
      catch (Exception e) 
      {
        System.out.println("find2ndMin() on heap with < 2 items caused an exception.. NOT OK");
        System.out.println("Heap is " + h);
        System.out.println(e);
      }
      h.insert(new Integer(r.nextInt(20)));
    }

    for (int k = 0; k < 9; k++)
    {
      h.insert(new Integer(r.nextInt(20)));
      h.insert(new Integer(r.nextInt(20)));
      try 
      {
        Integer i = (Integer)h.find2ndMin();
        h.deleteMin();
        Integer j = (Integer)h.findMin();
        if (i.equals(j)) 
        {
          System.out.println("find2ndMin() returned " + i + ".. OK");
        } 
        else 
        {
          System.out.println("find2ndMin() returned " + i + 
          "but should have returned " + j + ".. NOT OK");
          System.out.println("Heap is " + h);
        }
      } 
      catch (Exception e) 
      {
        System.out.println("find2ndMin() on 2-items heap caused an exception.. NOT OK");
        System.out.println("Heap is " + h);
        System.out.println(e);
      }
    }
  }


  public static void testIsHeap()
  {
    Random r = new Random();
    BinaryHeap h = new BinaryHeap( );

    for (int i = 0; i < 12; i++)
    {
      // Test with 1 item.
      try 
      {
        boolean b = h.isHeap();
        if (b)
          System.out.println("isHeap() on heap returned " + b + ".. OK");
        else 
        {
          System.out.println("isHeap() on heap returned " + b + ".. NOT OK");
          System.out.println("Heap is " + h);
        }
      } 
      catch (Exception e) 
      {
        System.out.println("isHeap() caused an exception.. NOT OK");
        System.out.println("Heap is " + h);
        System.out.println(e);
      }
      h.insert(new Integer(r.nextInt(20)));
    }

    // Test with invalid heap
    while (h.isHeap())
    {
      h.messUp();
    }
    System.out.println("isHeap() returns false on the following.. OK?" );
    System.out.println(h);
  }

  public static void main( String [ ] args )
  {
    testFind2ndMin();
    testIsHeap();
  }
}