package PQ;

public class PQHeap implements PQ {
    private static final int CAPACITY = 100;
    private static final double RESIZE_FACTOR = 1.2;
    private static final double  RESIZE_TRIGGER = 0.9;
    private PQNode heap[];   // la coda e' uno heap
    private int count;       // totale elementi in coda

    public PQHeap()  {
        clear();
    }        


    // post: ritorna il numero di elementi della coda
    public int size() {
       return count;
    }        


    // post: ritorna true sse la coda e' vuota
    public boolean isEmpty()  {
       return (count == 0);
    }        
  


    // post: svuota la coda
    public void clear()   {
        heap = new PQNode[CAPACITY];
        count = 0;       
    }        


    // post: se il rapporto tra il numero di elementi in coda e la dimensione
    //       della coda supera RESIZE_TRIGGER incrementa la dimensione dell'array 
    //       di un fattore RESIZE_FACTOR
    private void ensureCapacity() {
	if (heap.length == count) {
	    PQNode[] supporto = new PQNode[(int)(heap.length * RESIZE_FACTOR)];
            System.arraycopy(heap, 0, supporto, 0, heap.length);
            heap = supporto;
	}
    }

 
    // pre: ob diverso da null
    // post: se il rapporto tra il numero di elementi in coda e la dimensione
    //       della coda supera RESIZE_TRIGGER incrementa la dimensione della coda
    //       di un fattore RESIZE_FACTOR. Inserisce poi ob nella coda con priorita' key 
    public void insert(int key, Object ob)   {
        ensureCapacity(); 
        heap[count] = new PQNode(key, ob);
        percolateUp(count);
        count++;
    }        


    // pre:  coda non vuota
    // post: rimuove l'elemento con priorita' max. e ne ritorna il valore
    public Object extractMax() {
        PQNode root = heap[0];
        heap[0] = heap[--count];
        maxHeapify(0);
        return root.element;
    }


    // pre:  coda non vuota
    // post: restituisce l'elemento con priorita' massima
    public Object maximum() {
	return heap[0].element;
    }


    // post: ritorna una stringa che rappresenta la coda a priorita'
    //       Dal punto di vista dell'albero che rappresenta lo heap 
    //       si tratta di effettuare una visita in ampiezza.
    //       Ogni nodo della coda viene rappresentato come coppia 
    //       (key,element). Le coppie sono separate da uno spazio.
    public String toString() {
        String s = "";
        for (int i = 0; i < count; i++)
            s = s + "(" + heap[i].key + "," + 
		(heap[i].element).toString() + ") ";
        return s;
    }
    


    // post: ritorna l'indice del padre di i
    private static int parent(int i) {
        return (i-1)/3;
    }

    // post: ritorna l'indice del primo figlio di i
    private static int primo(int i) {
        return 3*i+1;
    }

    // post: ritorna l'indice del secondo figlio di i
    private static int secondo(int i) {
        return 3*i+2;
    }


    // post: ritorna l'indice del terzo figlio di i
    private static int terzo(int i) {
        return 3*(i+1);
    }

    // pre: 0 <= i < count
    // post: ripristina la proprieta' heap a partire da un quasi-heap
    private void maxHeapify(int i) {
        int t = i;
        if (primo(i) < count && heap[primo(i)].key > heap[i].key )
            t = primo(i);

        //t e' l'indice del maggiore tra heap[i] e heap[primo(i)]
 
        if (secondo(i) < count && heap[secondo(i)].key > heap[t].key)
            t = secondo(i);

        //t e' l'indice del maggiore tra heap[i], heap[primo(i)], heap[secondo(i)]

        if (terzo(i) < count && heap[terzo(i)].key > heap[t].key)
            t = terzo(i);

        //t e' l'indice del maggiore tra heap[i], heap[primo(i)], heap[secondo(i)], heap[terzo(i)]

        if (t != i) {
	    PQNode aux = heap[i];
            heap[i] = heap[t];
            heap[t] = aux;
            maxHeapify(t);
	}
          
    }

    // pre: 0 <= leaf < count
    // post: posiziona il valore della foglia di indice leaf 
    //       in modo che l'albero risultante sia uno heap
    private void percolateUp(int leaf) {
        int parent = parent(leaf);
        PQNode value = heap[leaf];
        while (leaf > 0 && (value.key > heap[parent].key)) {
            heap[leaf] = heap[parent];
            leaf = parent;
            parent = parent(leaf);
        }
        heap[leaf] = value;
    }                                                                         


}