package trials;

import java.util.HashMap;

import java.util.Stack;

public class PQWithSearch {

	private Phrase[] pq;
	private HashMap<Phrase, Integer> positionsMap = new HashMap<Phrase, Integer>();
	public int size = 0;

	public PQWithSearch(int maxLength){
		pq = new Phrase[maxLength+1];
	}

	public void stringInsert(String text){
		System.out.println("Trying to insert text: " + text);
		Phrase ph = new Phrase(text);
		if (positionsMap.containsKey(ph)){
			System.out.println("found it: " + ph);
			int phraseIndex = positionsMap.get(ph);
			pq[phraseIndex].incrementCount();
		} else {
			System.out.println("Didn't find it, adding it");
			insert(ph);
		}

	}
	public void insert(Phrase k){
		size++;
		assign(size, k);
		swim(size);
	}

	public Phrase delMin(){
		Phrase min = pq[1];
		size--;
		exch(1, size);
		assign(size+1, null);
		sink(1);
		removeFromPositionsMap(min);
		return min;
	}

	public boolean isEmpty(){
		return size == 0;
	}

	private void assign(int index, Phrase value){

		pq[index] = value;
		if(value != null){
			positionsMap.put(value, index);
		}
	}
	private void removeFromPositionsMap(Phrase phrase){
		positionsMap.remove(phrase);
	}

	private void swim(int k){
		while(k>1 && greater(k/2, k)){
			exch(k,k/2);
			k = k/2;
		}
	}
	private void sink(int k){
		while(2*k <= size){
			int j = 2 *k;
			if (j < size && greater(j,j+1)){
				j++;
			}
			if (greater(k,j)){
				exch(k,j);
				k = j;
			} else {
				break;
			}
		}
	}

	private boolean less(int i, int j){
		if (pq[i].compareTo(pq[j]) < 0){
			return true;
		}
		return false;
	}


	private boolean greater(int i, int j){
		if (pq[i].compareTo(pq[j]) > 0){
			return true;
		}
		return false;
	}

	private void exch(int i, int j) {
		Phrase t = pq[i];
		assign(i, pq[j]);
		assign(j, t);
	}

	public static void main(String[] args) {

		int maxSize = 5;
		PQWithSearch pq = new PQWithSearch(maxSize+1);

		String [] fileContents = new String[]{"a","a","c","d","e","f","g","a","b","b","c"};

		for (String text : fileContents){
			pq.stringInsert(text);
			if (pq.size > maxSize){
				pq.delMin();
			}
		}

		Stack<Phrase> stack = new Stack<Phrase>();
		while (!pq.isEmpty()) stack.push(pq.delMin());
		for (Phrase t : stack)
			System.out.println(t);
	}

}

class Phrase implements Comparable<Phrase>{

	private String text;
	private int count = 1;
	public Phrase(String text){
		this.text = text;
	}
	@Override
	public int compareTo(Phrase o) {
		if (this.count < o.count){
			return -1;
		}
		else if (this.count > o.count){
			return 1;
		}
		return 0;
	}
	public int hashCode(){
		return this.text.hashCode();
	}

	public boolean equals(Object other){
		Phrase otherPhrase = (Phrase) other;
		boolean isEqual = this.text.equals(otherPhrase.text);
		return isEqual;
	}
	public void incrementCount(){
		this.count += 1;
	}

	public String toString(){
		return this.text + ": " + this.count;
	}
}