// BinaryHeap class
//
// CONSTRUCTION: with optional capacity (that defaults to 100)
//               or an array containing initial items
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x )       --> Insert x
// Comparable deleteMin( )--> Return and remove smallest item
// Comparable findMin( )  --> Return smallest item
// boolean isEmpty( )     --> Return true if empty; else false
// void makeEmpty( )      --> Remove all items
// void delete( x )          --> Deletes x from the Binary Heap
// ******************ERRORS**************************************
// Throws UnderflowException as appropriate

/**
 * Implements a binary heap.
 * Note that all "matching" is based on the compareTo method.
 * @author Mark Allen Weiss
 * EDITED 
 */
public class BinaryHeap<AnyType extends Comparable<? super AnyType>>
{
    /**
     * Construct the binary heap.
     */
    public BinaryHeap( )
    {
        this( DEFAULT_CAPACITY );
    }

    /**
     * Construct the binary heap.
     * @param capacity the capacity of the binary heap.
     */
    public BinaryHeap( int capacity )
    {
        currentSize = 0;
        array = (AnyType[]) new Comparable[ capacity + 1 ];
        // initializes a new hash table to store locations of values
        locationsTable = new SeparateChainingHashTable<Foo>(array.length);
    }
    
    /**
     * Construct the binary heap given an array of items.
     */
    public BinaryHeap( AnyType [ ] items )
    {
        currentSize = items.length;
        array = (AnyType[]) new Comparable[ ( currentSize + 2 ) * 11 / 10 ];
        // initializes a new hash table to store locations of values
        locationsTable = new SeparateChainingHashTable<Foo>(array.length);
        
        int i = 1;
        for( AnyType item : items ){
        	
            array[ i++ ] = item;
            locationsTable.insert(new Foo(item,i-1));  // sets each new item into the hash table
            											  // with its associated array location
        }
        buildHeap( );
    }

    /**
     * Insert into the priority queue, maintaining heap order.
	 * Update the hashtable each time an element is entered into 
	 * the array. The hashtable is a map of the heap array.
     * Duplicates are not allowed.
     * @param x the item to insert.
     */
    public void insert( AnyType x )
    {
    	if(!isPresent(x)){  // makes the heap NOT allow for duplicates so the hash table will work
	        if( currentSize == array.length - 1 )
	            enlargeArray( array.length * 2 + 1 );
	
	            // Percolate up
	        int hole = ++currentSize;
	        for( ; hole > 1 && x.compareTo( array[ hole / 2 ] ) < 0; hole /= 2 ){
	            array[ hole ] = array[ hole / 2 ];
	            locationsTable.remove(new Foo(array[hole]));
	            locationsTable.insert(new Foo(array[hole],hole)); // updates location by reinserting into hash table
	        }	
	        array[ hole ] = x;
	        locationsTable.insert(new Foo(array[hole],hole));  // updates the location in the hashtable
    	}
    }


    private void enlargeArray( int newSize )
    {
        AnyType [] old = array;
        array = (AnyType []) new Comparable[ newSize ];
        for( int i = 0; i < old.length; i++ )
            array[ i ] = old[ i ];        
    }
    
    /**
     * Find the smallest item in the priority queue.
     * @return the smallest item, or throw an UnderflowException if empty.
     */
    public AnyType findMin( )
    {
        if( isEmpty( ) ){
            //throw new UnderflowException( );
        	return null;
        }
        return array[ 1 ];
        
    }

    /**
     * Remove the smallest item from the priority queue.
	 * Update the hashtable after removing an element.
	 * Delete that element from the hashtable.
     * @return the smallest item, or throw an UnderflowException if empty.
     */
    public AnyType deleteMin( )
    {
        if( isEmpty( ) ){
            //throw new UnderflowException( );
        	return null;
        }
        AnyType minItem = findMin();
        if(minItem == null){  // if item not in heap, do nothing
        	return null;
        }
        locationsTable.remove(new Foo(array[1]));  // removes the element we're deleting from the hash table
        array[ 1 ] = array[ currentSize-- ]; 
        locationsTable.remove(new Foo(array[1]));  // removes the element we moved into the root
        											  // position from the hash table so we can
        											  // update its position during percolation
        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;
    }

    /**
     * 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 AnyType [ ] array; // The heap array
    private SeparateChainingHashTable<Foo> locationsTable;  // hash table for storing elements and
    														   // their locations using HashEl objects

    /**
     * Internal method to percolate down in the heap.
     * @param hole the index at which the percolate begins.
     */
    private void percolateDown( int hole )
    {
    	if(currentSize>0){
	        int child;
	        AnyType 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 ){
	            	locationsTable.remove(new Foo(array[hole]));  // removes the element we're
	                array[ hole ] = array[ child ];					 // deleting from the hash table
	            	locationsTable.remove(new Foo(array[child]));  
	            	locationsTable.insert(new Foo(array[hole],hole));  // updates the location of
	            }else													  // the element being percolated up			
	                break;												  // by re-adding it to the hash table
	        }
	        array[ hole ] = tmp;
	        locationsTable.insert(new Foo(array[hole],hole));
    	}
    }
    
    
    // public delete method that deletes the input x from the Binary Heap if it is
    // present somewhere in the heap
    public boolean delete(AnyType x){
    	if(this.isEmpty()){  //returns false if no elements in the heap
    		return false;
    	}else if(currentSize == 1){  // if there is only one element in the heap
    		if(array[1].equals(x)){
    			deleteMin();  // uses deleteMin() to remove the only element if it is
    			return true;  // equal to the element we're looking for
    		}else{
    			return false;
    		}
    	}else if(isPresent(x)){  // if the size of the heap is > 1 and the element is in the heap
    		if(array[1].equals(x)){
    			deleteMin();  // deletes the first element if that element is the one we're
    			return true;  // looking for
    		}else{
	    		int location = getLocation(x);  // location of the element in the heap array
		        int hole = location;  // placeholder that holds the location while percolating
		        
		        // percolates the element we were looking for up to the root position
		        for( ; hole > 1 ; hole /= 2 ){
		        	AnyType temp = array[hole];  //saves the element previously in this location
		            array[ hole ] = array[ hole / 2 ];
		            locationsTable.remove(new Foo(array[hole]));
		            locationsTable.insert(new Foo(array[hole],hole)); //updates location of element
		            array[hole/2] = temp;  // finishes the swap as the element is percolated up
		            locationsTable.remove(new Foo(array[hole/2]));
		            locationsTable.insert(new Foo(array[hole/2],hole/2)); // updates location of element
		        }
		        deleteMin();  // deletes the element now that it is in the root position
		        			  // even though it is not really the 'min'
		        buildHeap();  //re-sorts elements of heap to ensure the Heap Ordering Property
		        return true;
    		}
    	}
    	return false;
    }
    
    // retrieves location of given element x in the current BinaryHeap using newly-created method
    // in the SeparateChainingHashTable class
    public int getLocation(AnyType x){
    	return locationsTable.getHeapLocation(new Foo(x));
    }
    
    // returns boolean value that indicates whether the given object x
    // is in the current BinaryHeap
    public boolean isPresent(AnyType x){
    	return locationsTable.contains(new Foo(x));
    }

    // Test program
    public static void main( String [ ] args )
    {
        int numItems = 10000;
        BinaryHeap<Integer> h = new BinaryHeap<Integer>( );
		
        /*int i = 37;

        for( i = 37; i != 0; i = ( i + 37 ) % numItems )
            h.insert( i );
        for( i = 1; i < numItems; i++ )
            if( h.deleteMin( ) != i )
                System.out.println( "Oops! " + i );*/
        
        // inserts and deletes several elements over and over again
		
		h.insert(13);
		h.insert(21);
		h.insert(16);
		h.insert(24);
		h.insert(31);
		h.insert(19);
		h.insert(68);
		h.insert(65);
		h.insert(26);
		h.insert(32);

        // prints out the resulting locations of inserted numbers to ensure the delete
        // method is working properly (a location value of 0 indicates not present)

		System.out.println(h.getLocation(13));
		System.out.println(h.getLocation(24));
		System.out.println(h.getLocation(31));
		System.out.println(h.getLocation(68));
		System.out.println(h.getLocation(26));
		
    }
}