/*------------------------------------------------------------------------------
* Copyright (C) 2003-2006 Ben van Klinken and the CLucene Team
* 
* Distributable under the terms of either the Apache License (Version 2.0) or 
* the GNU Lesser General Public License, as specified in the COPYING file.
------------------------------------------------------------------------------*/
#ifndef _lucene_util_PriorityQueue_
#define _lucene_util_PriorityQueue_

#if defined(_LUCENE_PRAGMA_ONCE)
# pragma once
#endif
CL_NS_DEF(util)

// A PriorityQueue maintains a partial ordering of its elements such that the
// least element can always be found in constant time.  Put()'s and pop()'s
//  require log(size) time. 
template <class _type,typename _valueDeletor> class PriorityQueue:LUCENE_BASE {
	private:
		_type* heap; //(was object[])
		size_t _size;
		bool dk;
		size_t maxSize;

		void upHeap(){
			size_t i = _size;
			_type node = heap[i];			  // save bottom node (WAS object)
			int32_t j = ((uint32_t)i) >> 1;
			while (j > 0 && lessThan(node,heap[j])) {
				heap[i] = heap[j];			  // shift parents down
				i = j;
				j = ((uint32_t)j) >> 1;
			}
			heap[i] = node;				  // install saved node
		}
		void downHeap(){
			size_t i = 1;
			_type node = heap[i];			  // save top node
			size_t j = i << 1;				  // find smaller child
			size_t k = j + 1;
			if (k <= _size && lessThan(heap[k], heap[j])) {
				j = k;
			}
			while (j <= _size && lessThan(heap[j],node)) {
				heap[i] = heap[j];			  // shift up child
				i = j;
				j = i << 1;
				k = j + 1;
				if (k <= _size && lessThan(heap[k], heap[j])) {
					j = k;
				}
			}
			heap[i] = node;				  // install saved node
		}

	protected:
		PriorityQueue(){
			this->_size = 0;
			this->dk = false;
			this->heap = NULL;
            this->maxSize = 0;
		}

		// Determines the ordering of objects in this priority queue.  Subclasses
		//	must define this one method. 
		virtual bool lessThan(_type a, _type b)=0;

		// Subclass constructors must call this. 
		void initialize(const int32_t maxSize, bool deleteOnClear){
			_size = 0;
			dk = deleteOnClear;
			int32_t heapSize = maxSize + 1;
			heap = _CL_NEWARRAY(_type,heapSize);
            this->maxSize = maxSize;
		}

	public:
		virtual ~PriorityQueue(){
			clear();
			_CLDELETE_ARRAY(heap);
		}

	 /**
      * Adds an Object to a PriorityQueue in log(size) time.
      * If one tries to add more objects than maxSize from initialize
      * a RuntimeException (ArrayIndexOutOfBound) is thrown.
      */
      void put(_type element){
      		if ( _size>=maxSize )
				_CLTHROWA(CL_ERR_IndexOutOfBounds,"add is out of bounds");

			++_size;	
			heap[_size] = element;		
			upHeap();
		}

      /**
      * Adds element to the PriorityQueue in log(size) time if either
      * the PriorityQueue is not full, or not lessThan(element, top()).
      * @param element
      * @return true if element is added, false otherwise.
      */
      bool insert(_type element){
         if(_size < maxSize){
            put(element);
            return true;
        }else if(_size > 0 && !lessThan(element, top())){
			if ( dk ){
				_valueDeletor::doDelete(heap[1]);
			}
            heap[1] = element;
            adjustTop();
            return true;
         }else
            return false;
      }

		/**
		* Returns the least element of the PriorityQueue in constant time. 
		*/
		_type top(){
			if (_size > 0)
				return heap[1];
			else
				return NULL;
		}

		/** Removes and returns the least element of the PriorityQueue in log(size)
		*	time.  
		*/
		_type pop(){
			if (_size > 0) {
				_type result = heap[1];			  // save first value
				heap[1] = heap[_size];			  // move last to first

				heap[_size] = (_type)0;			  // permit GC of objects
				--_size;
				downHeap();				  // adjust heap
				return result;
			} else
				return (_type)NULL;
		}

		/**Should be called when the object at top changes values.  Still log(n)
		   worst case, but it's at least twice as fast to <pre>
		    { pq.top().change(); pq.adjustTop(); }
		   </pre> instead of <pre>
		    { o = pq.pop(); o.change(); pq.push(o); }
		   </pre>
		*/
		void adjustTop(){
			downHeap();
		}
		    

		/**
		* Returns the number of elements currently stored in the PriorityQueue.
		*/ 
		size_t size(){
			return _size;
		}
		  
		/** 
		* Removes all entries from the PriorityQueue. 
		*/
		void clear(){
			for (size_t i = 1; i <= _size; ++i){
				if ( dk ){
					_valueDeletor::doDelete(heap[i]);
				}
			}
			_size = 0;
		}
	};

CL_NS_END
#endif