/*
    * Copyright (c) 2003-2008 by Cosylab d. d.
    *
    * This file is part of Java-Common.
    *
    * Java-Common is free software: you can redistribute it and/or modify
    * it under the terms of the GNU General Public License as published by
    * the Free Software Foundation, either version 3 of the License, or
    * (at your option) any later version.
   *
   * Java-Common is distributed in the hope that it will be useful,
   * but WITHOUT ANY WARRANTY; without even the implied warranty of
   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   * GNU General Public License for more details.
   *
   * You should have received a copy of the GNU General Public License
   * along with Java-Common.  If not, see <http://www.gnu.org/licenses/>.
   */
  
  package com.cosylab.util;
  
  /**
   * Simple heap implementation. This implementation uses <code>Comparable</code>
   * interface to maintain ascending order. Heap will grow and shrink based on
   * number of elements. If total number of elements equals internal array size,
   * this array is expanded by factor of 2. If number of elements is less than
   * one quarter the array size, array will be shrunk to by half.<br>
   * Implementation is synchronized and can be considered thread-safe.
   *
   * @author <a href="mailto:ales.pucelj@cosylab.com">Ales Pucelj</a>
   * @version $id$
   */
  public class Heap
  {
  	/*
  	 * Internal array of elements.
  	 */
  	private Comparable[] elements;
  
  	/*
  	 * Number of elements in heap.
  	 */
  	private int size;
  
  	/**
  	 * Default constructor for Heap(). Creates new heap with 16 elements.
  	 */
  	public Heap()
  	{
  		this(16);
  	}
  
  	/**
  	 * Alternate constructor for heap that allows specification of initial
  	 * size.
  	 *
  	 * @param initialSize
  	 */
  	public Heap(int initialSize)
  	{
  		elements = new Comparable[Math.max(8, initialSize)];
  	}
  
  	/**
  	 * Calculates optimal size.
  	 *
  	 * @return optimal size for this heap.
  	 */
  	private int getOptimalSize()
  	{
  		int n = elements.length;
  
  		if (size == n) {
  			return 2 * n;
  		}
  
  		if (n < 8) {
  			return size;
  		}
  
  		if (size < n / 4) {
  			return n / 2;
  		}
  
  		return size;
  	}
  
  	/**
  	 * Checks the size of the internal array and adjusts it if neccessary.
  	 */
  	private void checkSize()
  	{
  		int n = getOptimalSize();
  
  		if (n == size) {
  			return;
  		}
  
  		Comparable[] newElements = new Comparable[n];
 
 		for (int i = 0; i < size; i++) {
 			newElements[i] = elements[i];
 		}
 
 		elements = newElements;
 	}
 
 	/**
 	 * Adds new element to the heap.
 	 *
 	 * @param c Element to add.
 	 */
 	public synchronized void add(Comparable c)
 	{
 		checkSize();
 
 		int curr = size;
 		int parent = (size + 1) / 2 - 1;
 
 		while ((parent >= 0) && (elements[parent].compareTo(c) > 0)) {
 			elements[curr] = elements[parent];
 			curr = parent;
 			parent = (parent + 1) / 2 - 1;
 		}
 
 		elements[curr] = c;
 
 		size++;
 	}
 
 	/**
 	 * Helper routine used be remove.
 	 *
 	 * @param index Index of the element.
 	 *
 	 * @return Largest of the children for the element at index or -1 if
 	 *         invalid.
 	 */
 	private int getChild(int index)
 	{
 		int left = 2 * index + 1;
 		int right = 2 * index + 2;
 
 		if (right < size) {
 			if (elements[left].compareTo(elements[right]) < 0) {
 				return left;
 			} else {
 				return right;
 			}
 		}
 
 		if (left < size) {
 			return left;
 		}
 
 		return -1;
 	}
 
 	/**
 	 * Removes smallest element.
 	 *
 	 * @return Element or null if empty.
 	 */
 	public synchronized Comparable remove()
 	{
 		if (size == 0) {
 			return null;
 		}
 
 		Comparable result = elements[0];
 
 		int curr = 0;
 		int child = getChild(curr);
 
 		Comparable last = elements[size - 1];
 
 		while ((child > -1) && (elements[child].compareTo(last) < 0)) {
 			elements[curr] = elements[child];
 			curr = child;
 			child = getChild(curr);
 		}
 
 		elements[curr] = last;
 		size--;
 
 		return result;
 	}
 
 	/**
 	 * Returns element at index.
 	 *
 	 * @param index Index of the element.
 	 *
 	 * @return synchronized
 	 */
 	public synchronized Comparable get(int index)
 	{
 		return elements[index];
 	}
 
 	/**
 	 * Size of the heap.
 	 *
 	 * @return synchronized
 	 */
 	public synchronized int size()
 	{
 		return size;
 	}
 
 	/**
 	 * True if heap is empty.
 	 *
 	 * @return synchronized
 	 */
 	public synchronized boolean isEmpty()
 	{
 		return size == 0;
 	}
 
 	/**
 	 * Returns smallest element or null if empty.
 	 *
 	 * @return synchronized
 	 */
 	public synchronized Comparable getFirst()
 	{
 		if (isEmpty()) {
 			return null;
 		}
 
 		return elements[0];
 	}
 
 	/**
 	 * DOCUMENT ME!
 	 *
 	 * @return DOCUMENT ME!
 	 */
 	public synchronized String toString()
 	{
 		StringBuffer sb = new StringBuffer(size() * 5);
 		sb.append("Heap = { ");
 
 		int n = Math.min(size, 30);
 		boolean first = true;
 
 		for (int i = 0; i < n; i++) {
 			if (first) {
 				first = false;
 			} else {
 				sb.append(", ");
 			}
 
 			sb.append(elements[i]);
 		}
 
 		sb.append(" }");
 
 		return sb.toString();
 	}
 
 	/**
 	 * Run test applet.
 	 *
 	 * @param args command line parameters
 	 */
 	public static void main(String[] args)
 	{
 		Heap h = new Heap();
 
 		for (int k = 0; k < 3; k++) {
 			for (int i = 0; i < 10; i++) {
 				h.add(new Integer((int)(Math.random() * 100.0)));
 			}
 
 			System.out.println(h.toString());
 
 			for (int i = 0; i < 5; i++) {
 				System.out.print(h.remove() + " ");
 			}
 
 			System.out.println();
 		}
 	}
 }
 
 /* __oOo__ */