/*
 * Copyright (c) Siemens AG 2008 
 *           (c) Universität Paderborn 2008 
 * Licensed under EUPL 1.1. 
 * 
 */


/*********************************************************************
 *  Indirect entries queue.
 *
 *  The entries queue maintains its own copy of the priorities,
 *  unlike the one in Algorithms in Java.
 *
 *  This code is from "Algorithms in Java, Third Edition,
 *  by Robert Sedgewick, Addison-Wesley, 2003.

 *********************************************************************/
package vkc.clusterer;

public class IndexHeap {
    private int N;              // number of elements on PQ
    private int[] pq;           // binary heap
    private int[] qp;           //	keep the heap position corresponding to index value k 
    
    private Comparable[] entries;  // entries 

    public IndexHeap(int NMAX) {
        pq = new int[NMAX + 1];
        qp = new int[NMAX + 1];
        entries = new Comparable[NMAX + 1]; 
        N = 0;
    }

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

    public boolean isMapped(int k) {
        if (k < entries.length && k >= 0) {
            return entries[k] != null;
        }
        
        return false;
    }

    // return element
    public Comparable get(int k) { 
        if (k < entries.length && k >= 0) {
            return entries[k]; 
        }
        
        return null;
    }

    // insert element k with given entries
    public void insert(int k, Comparable entry) {
        N++;
        qp[k] = N;
        pq[N] = k;
        entries[k] = entry;
        fixUp(pq, N);
    }

    // delete and return the maximum element
    public Comparable delMax() { 
        exch(pq[1], pq[N]); 
        fixDown(pq, 1, --N); 
    
        return entries[pq[N+1]]; 
    }

    // delete and return the maximum element
    public Comparable delete(int k) { 
        int j = qp[k];
        
        exch(pq[j], pq[N]); 
        fixDown(pq, j, --N); 

        return entries[pq[N+1]]; 
    }

    // change the entries of element k to specified value
    public void update(int k, Comparable entry) {
        entries[k] = entry;
        fixUp(pq, qp[k]);
        fixDown(pq, qp[k], N);
    }


   /**************************************************************
    * General helper functions
    **************************************************************/
    private boolean smaller(int i, int j) {
        return entries[i].compareTo(entries[j]) < 0;
    }

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


   /**************************************************************
    * Heap helper functions
    **************************************************************/
    private void fixUp(int[] a, int k)  {
        while (k > 1 && smaller(a[k/2], a[k])) {
            exch(a[k], a[k/2]);
            k = k/2;
        }
    }

    private void fixDown(int[] a, int k, int N) {
        int j;
        while (2*k <= N) {
            j = 2*k;
            if (j < N && smaller(a[j], a[j+1])) j++;
            if (!smaller(a[k], a[j])) break;
            exch(a[k], a[j]);
            k = j;
        }
    }

    /**
     * @return Returns the n.
     */
    public int getSize() {
        return N;
    }
}