#ifndef _INCLUDED_L3_HEAP_H
#define _INCLUDED_L3_HEAP_H

// *Heap* Copyright (C) Krzysztof Bosak, 1998-03-21...2000-11-23.
// All rights reserved.
// kbosak@box43.pl
// http://www.kbosak.prv.pl

// _data[0] is never used due to algorithm speed and simplicity.
// fixedheap<> will not be written - push() is complicated and absence of
// one if() will not optimize significantly (-0.5% time for push+pop of 2000000 elements).

#include "l3_array.h"

template <class type>
class growing_arrayheap
{	// Roughly corresponds to std::priority_queue.
	// Storage convention: max element on top.
	// Is EXCEPTION SAFE.
private:
	autoarray<type> _data;
	int _size;

public:
	inline growing_arrayheap() // EXEPTION NEUTRAL
		: _data(1),
		_size(0)
	{
		//_data[0]=(type)(0);// To suppress false warning about uninitialized data by NuMega DevPartner? Don't because of TextString!
	}
	inline explicit growing_arrayheap(int requested_size) // EXEPTION NEUTRAL
		: _data(requested_size),
		_size(0)
	{
		//_data[0]=(type)(0);// To suppress false warning about uninitialized data by NuMega DevPartner? Don't because of TextString!
	}
	inline void swap(growing_arrayheap<type>& other) // NOTHROW
	{
		_data.swap(other._data);
		const int temp=_size;
		_size=other._size;
		other._size=temp;
	}
	inline growing_arrayheap<type>& operator=(const growing_arrayheap<type>& other) // EXEPTION NEUTRAL
	{	// A must to ensure strong exception safety.
		assert(this!=&other);// This line can be safely removed.
		growing_arrayheap<type> temp(other);
		swap(temp);
		return *this;
	}
	inline int size() const // NOTHROW
	{
		assert(_size>=0);
		return _size;
	}
	inline bool empty() const // NOTHROW
	{
		assert(_size>=0);
		return _size==0;
	}
	inline int capacity() const // NOTHROW
	{
		return _data.size()-1; // Storage for _data.size()-1 elements only!
	}
	inline void push(const type& element)
	{
		if(_size+1>=_data.size())
		{
			_data.resize(_data.size()+_data.size());
		}
		_data[_size+1]=element;
		_size++;
		int n=_size;
		int n2=_size>>1;
		while(n!=1 && _data[n2]<=element)
		{
			_data[n]=_data[n2];
			n=n2;
			n2>>=1;
		}
		_data[n]=element;
	}
	inline type& top() // NOTHROW
	{
		assert(_size>0);
		return _data[1];
	}
	inline const type& top() const // NOTHROW
	{
		assert(_size>0);
		return _data[1];
	}
	inline void pop()
	{
		assert(_size>=1);
		if(_size!=1)
		{
			_data[1]=_data[_size];
		}
		_size--;
		int i=1;
		int p;
		int p2;
		for(;;)
		{
			p=i<<1;
			if(p>_size)
			{
				return;
			}
			p2=p+1;
			if(p2<=_size)
			{
				if(_data[p]<_data[p2])
				{
					p++;
				}
			}
			if(_data[p]<=_data[i])
			{
				return;
			}
			const type temp=_data[p];
			_data[p]=_data[i];
			_data[i]=temp;
			i=p;
		}
	}
	inline void unique_push(const type& element) // not STL
	{
		if(find(element)==0)
		{
			push(element);
		}
	}
	inline int find(const type& element) const // not STL // EXCEPTION NEUTRAL
	{
		assert(_size>=0);// empty stack safe
		if(_size==0)
		{
			return 0;
		}
		if(_data[1]==element)
		{
			return 1;
		}
		return _binary_find(element, 1);
		//return _linear_find(element);// not safe against default elements finding, but sometimes faster
	}
	inline void setsize(int requested_size) // not STL // EXEPTION NEUTRAL
	{
		_data.setsize(requested_size);
		_size=0;
	}
	inline void free() // not STL // EXEPTION NEUTRAL
	{
		_data.setsize(1);
		_size=0;
	}
	inline void clear() // not STL // NOTHROW
	{
		_size=0;
	}
	/*
	#ifndef NDEBUG
	void show() // not STL
	{
		int i=1, j;
		while(i<=_size)
		{
			for(j=i, i<<=1; j<=_size && j<i; j++)
				cout<<_data[j]<<",";
			cout<<endl;
		}
	}
	#endif
	*/
private:
	/*
	inline int _linear_find(const type& element) const // not STL // EXEPTION NEUTRAL
	{
		assert(element!=_data[0]);
		// The _data array is already full of objects constructed with default constructor.
		// one must take care to not search for such element: he will be certainly found!
		// Default constructed element is at unused _data[0] position...
		// However, _linear_find is faster for simple object with trivial < and <=.
		for(int i=0; i<=_size; i++)
		{
			//cout<<'#';
			if(element==_data[i])
			{
				if(i==0)// let's take some defense against aforementioned rare limitation
					return _binary_find(element, 1);
				return i;
			}
		}
		return 0;
	}
	*/
	inline int _binary_find(const type& element, int element_index) const // not STL  // EXEPTION NEUTRAL
	{	// Warning: user should test presence of element at _data[1] before _binary_find!
		assert(element_index>=1);
		assert(element_index<=_size);
		assert(_size>0);// not empty stack safe
		//cout<<'#';
		element_index<<=1;
		if(element_index>_size)
		{
			return 0;
		}

		if(element<_data[element_index])
		{
			const int search_result=_binary_find(element, element_index);
			if(search_result!=0)
			{
				return search_result;
			}
		}
		else if(_data[element_index]==element)
		{
			return element_index;
		}

		element_index++;
		if(element_index>_size)
		{
			return 0;
		}

		if(element<_data[element_index])
		{
			const int search_result=_binary_find(element, element_index);
			if(search_result!=0)
			{
				return search_result;
			}
		}
		else if(_data[element_index]==element)
		{
			return element_index;
		}
		return 0;
	}
};

#endif // _INCLUDED_L3_HEAP_H