/* 
  ________________________________
 |          Asma H. Al-Rawi       | 
 |________________________________|
 |           COP 3503c            |
 |          Section 0014          |
 |________________________________| 
 |         Assignment #5:         |
 |       Heap Manipulation        |  
 |________________________________| 
 |        Due Apr 8, 2014         |
 |________________________________|
  
*/

import java.io.*;
import java.util.*;

public class Heap {
	public static void main(String[] args) throws IOException{

		List<Integer> heap = new ArrayList<Integer>();
		String command;

		//Read in file
		Scanner sin = new Scanner(new File("heapops.txt"));
		//Read in command, call proper function
		while(sin.hasNext()){
			command = sin.next();
			
			switch(command){
				case "load":
					heap = load(heap, sin);
					break;
				case "print":
					print(heap);
					break;
				case "build-heap":
					heap = buildHeap(heap);
					break;
				case "delete-max":
					heap = deleteMax(heap);
					break;
				case "insert":
					int toIns = sin.nextInt();
					heap = insert(heap, toIns);
					break;
				case "heapsort":
					heap = heapSort(heap);
					break;
				default:
					System.out.println("Error: Cannot parse \"" + command + "\".");
					return;
			}
		}
		return;
	}//end main

	/*-----Loads ints from file into heap list (in original order)-----*/
	public static List<Integer> load(List<Integer> heap, Scanner sin){
		heap.clear();

			while(sin.hasNextInt())
				heap.add(sin.nextInt());
		return heap;	
	}

	/*-----Prints heap-----*/
	public static void print(List<Integer> heap){
		if(heap.size() == 0){
			System.out.println("(empty)");
			return;
		}
		System.out.print(heap.get(0));
		for(int i=1; i<heap.size(); i++)
			System.out.print(" " + heap.get(i));
		System.out.println();
		return;
	}
	
	/*-----Builds heap structure using bottom up algorithm-----*/
	public static List<Integer> buildHeap(List<Integer> heap){
		if(heap.isEmpty()) return heap;

		for(int i= (heap.size()-1)/2; i>=0; i--)
			heap = percolateDown(heap, i);
		return heap;
	}

	/*-----Checks/Adjusts Heap Sort at position i in heap (used in Bottom Up)-----*/
	public static List<Integer> percolateDown(List<Integer> heap, int i){
		//No children
		if(2*i+1 >= heap.size()) return heap;

		//Index of max b/w i and children of i
		int maxIndex = heap.indexOf(Math.max(heap.get(i), heap.get(2*i+1)));
		if(2*i+2 < heap.size())
			maxIndex = heap.indexOf(Math.max(heap.get(2*i+2), heap.get(maxIndex))); 
		if(maxIndex == i) return heap;

		//Switch parent with largest child, check new child
		return percolateDown(swap(heap, i, maxIndex), maxIndex);
	}

	/*-----Swap numbers in position a and b within heap-----*/
	public static List<Integer> swap(List<Integer> heap, int a, int b){
		if(a==b) return heap;
		if(heap.size() < a || heap.size() < b) return heap;

		int temp = heap.get(a);

		heap.remove(a);
		heap.add(a, heap.get(b-1));
		heap.remove(b);
		heap.add(b, temp);

		return heap;
	}

	/*-----Deletes max value in heap-----*/
	public static List<Integer> deleteMax(List<Integer> heap){
		if(heap.isEmpty()) return heap;
		if(heap.size() == 1){
			heap.clear();
			return heap;
		}
		//Delete max, put last node in its place
		heap.remove(0);
		heap.add(0, heap.get(heap.size()-1));
		heap.remove(heap.size()-1);
		//Percolate down to put new head node in proper place
		return percolateDown(heap, 0);
	}

	/*-----Inserts value into heap-----*/
	public static List<Integer> insert(List<Integer> heap, int toIns){
		heap.add(toIns);

		if(heap.size() <= 1) return heap;

		int i = heap.size()-1; //position of new value

		while(i > 0 && heap.get(i) > heap.get(i/2)){
			heap = swap(heap, i/2, i);
			i = i/2;
		}

		return heap;
	}

	/*-----Sorts values by printing & removing max until heap is empty-----*/
	public static List<Integer> heapSort(List<Integer> heap){
		while(!heap.isEmpty()){
			System.out.print(heap.get(0) + " ");
			heap = deleteMax(heap);
		}
		System.out.println();
		return heap;
	}

}//end Heap