/*********************************************************************
 * This file is part of the cpplibs suite.
 *
 * Copyright (C) 2001 Topi Mäenpää and Jaakko Viertola
 * All rights reserved.
 *
 * This program is free software. You can redistribute and/or modify
 * it under the terms of the free software licence found in the
 * accompanying file "COPYING". The licence terms must always be
 * redistributed with this source file. The above copyright notice
 * must be reproduced in all modified and unmodified copies of this
 * source file.
 *
 * $Revision: 1.8 $
 *********************************************************************/

#ifndef _HEAP_H
#define _HEAP_H

#include "List.h"
#include <functional>

#define HEAP_PARENT_INDEX(i)		((i-1)>>1)
#define HEAP_CHILD_INDEX(i)			((i<<1)+1)

namespace util
{
	/**
	 * Heap is an implementation of a binary tree with the properties listed below.
	 * <ul>
	 * <li>It is complete.
	 * <ul>
	 * <li>All leaf nodes reside in at most two adjacent levels.
	 * <li>It is filled from left.
	 * </ul>
	 * <li>It has the heap property.
	 * <ul>
	 * <li>No child node in the tree is greater than its parent.<sup>(1)</sup>
	 * </ul>
	 * </ul>
	 *
	 * Elements can be added to a heap as they are added to any list
	 * using the += operator or the addElement method. The binary tree
	 * is stored as a list in breadth-first order.<p>
	 *
	 * To obtain a sorted list out of a heap one may do something like
	 * this:
	 * <pre>
	 * //Create a heap with an intial capacity of 100 elements.
	 * Heap&lt;double,greater&lt;double&gt; &gt; heap(100);
	 * //greater&lt;double&gt; isn't actually needed, it's the default
	 *
	 * //Fill the heap with 100 random numbers
	 * for (int i=0;i&lt;100;i++)
	 *   heap += drand48();
	 *
	 * //Print out the elements in descending order.
	 * cerr &lt;&lt; heap.removeElementAt(0) &lt;&lt; " ";
	 * </pre>
	 *
	 * Heap quarantees O(log(N)) complexity for insertion and deletion.
	 * The complexity for sorting N items, as in the previous example,
	 * is O(N*log(N)).<p>
	 *
	 * Note that if you use the insertElementAt method or alter the data
	 * directly, the order of the elements in the heap is undefined.<p>
	 *
	 * <sup>(1)</sup> One may construct a reverse heap by supplying
	 * <i>less&lt;T&gt;</i> as the second template parameter. Please note that
	 * in this case <i>sort()</i> produces a list in descending order.
	 **/
	template <class T, class comparator = std::greater<T> > class Heap : public List<T>
	{
	public:
		/**
		 * Create a heap with the given initial capacity and block size.
		 *
		 * @param capacity the number of elements this heap will hold
		 * without expanding.
		 * @param blockSize the amount of items to grow when expanding
		 **/
		Heap(int capacity=16, int blockSize=16) : List<T>(capacity,blockSize) {}
		/**
		 * The copy constructor.
		 **/
		Heap(const Heap& other) : List<T>(other) {}

		/**
		 * Add an element to the heap. This method guarantees that the
		 * heap order is always preserved.
		 **/
		void addElement(const T& element);
		/**
		 * Remove an element at the given index. The list will be
		 * heapified automatically.
		 **/
		T removeElementAt(int index);

		/**
		 * Sort the heap in place. After this method call, the elements in
		 * the list are in ascending order. Note that the heap does not
		 * have the heap property any more. (In fact it does have an
		 * inverse heap property.)<p>
		 *
		 * Note that the sort order can be changed by supplying different
		 * template parameters. The default, <i>greater&lt;T&gt;</i>,
		 * means that each parent in the tree is <i>greater</i> that its
		 * children. sort() sequentially removes the top of the tree and
		 * moves it to the end of the list. Therefore, by default, sort
		 * order is ascending.
		 **/
		void sort();

	private:
		comparator _comparator;
		inline void swap(int i, int t);
	};

	template <class T, class comparator> void Heap<T,comparator>::sort()
	{
		int size = _iCurrentItems;
		while (_iCurrentItems > 1)
			{
				//The value returned by removeElementAt(0) cannot be directly
				//assigned to _internalArray[_iCurrentItems] because (at least
				//the GNU) C++ compiler evaluates
				//_internalArray[_iCurrentItems] either before or after
				//removeElement(0) call depending on the type handled. For
				//elementary types, direct assignment works, but for complex
				//ones it does not.
				T tmp(removeElementAt(0));
				_internalArray[_iCurrentItems] = tmp;
			}
		_iCurrentItems = size;
	}

	template <class T, class comparator> void Heap<T,comparator>::swap(int i, int t)
	{
		T tmp(_internalArray[i]);
		_internalArray[i] = _internalArray[t];
		_internalArray[t] = tmp;
	}

	template <class T, class comparator> void Heap<T,comparator>::addElement(const T& element)
	{
		List<T>::addElement(element);
		int childIndex = _iCurrentItems-1;
		int parentIndex = HEAP_PARENT_INDEX(childIndex);
		while (parentIndex >=0 && _comparator(_internalArray[childIndex],_internalArray[parentIndex]))
			{
				swap(parentIndex,childIndex);
				childIndex = parentIndex;
				parentIndex = HEAP_PARENT_INDEX(childIndex);
			}
	}

	template <class T, class comparator> T Heap<T,comparator>::removeElementAt(int index)
	{
		//Store the removed element.
		T tmp(_internalArray[index]);
		_iCurrentItems--;

		//Check if we need to heapize the list
		if (index < _iCurrentItems)
			{
				//Move the last element to the free place.
				_internalArray[index] = _internalArray[_iCurrentItems];

				//Update the heap downwards. If the new parent for a child
				//node is smaller than a child, then swap the parent with
				//larger of its children.
				int parentIndex = index;
				int childIndex = HEAP_CHILD_INDEX(index);
				while ((_iCurrentItems > childIndex && _comparator(_internalArray[childIndex],_internalArray[parentIndex])) ||
							 (_iCurrentItems > childIndex+1 && _comparator(_internalArray[childIndex+1],_internalArray[parentIndex])))
					{
						if (_iCurrentItems > childIndex+1 && _comparator(_internalArray[childIndex+1], _internalArray[childIndex]))
							childIndex++;
						swap(parentIndex,childIndex);
						parentIndex = childIndex;
						childIndex = HEAP_CHILD_INDEX(parentIndex);
					}

				//Update upwards. If a child node is larger than its parent,
				//swap the two.
				childIndex = index;
				parentIndex = HEAP_PARENT_INDEX(childIndex);
				while (parentIndex >=0 && _comparator(_internalArray[childIndex],_internalArray[parentIndex]))
					{
						swap(parentIndex,childIndex);
						childIndex = parentIndex;
						parentIndex = HEAP_PARENT_INDEX(childIndex);
					}
			}
			
		return tmp;
	}
}


#endif