/*
Copyright (C) 2003 Rice1964

This program 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 2
of the License, or (at your option) any later version.

This program 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 this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
*/

#ifndef _SORTED_LIST_H_
#define _SORTED_LIST_H_

template<class Key, class Element>
class CSortedList
{
private:
	Key *keys;
	Element *elements;
	int curSize;
	int maxSize;

public:
	CSortedList(int size=1000)
	{
		maxSize = size;
		curSize = 0;
		keys = new Key[size];
		elements = new Element[size];
	}

	~CSortedList()
	{
		delete [] keys;
		delete [] elements;
	}

	int size()
	{
		return curSize;
	}

	void clear()
	{
		curSize = 0;
	}

	void add(Key key, Element ele)
	{
		int i = find(key);
		if( i >= 0 )
		{
			elements[i] = ele;
			return;
		}

		if( curSize < maxSize )
		{
			for( i=0; i<curSize; i++ )
			{
				if( keys[i] > key )
				{
					// Found the spot
					break;
				}
			}

			for( int j=curSize; j>i; j-- )
			{
				keys[j] = keys[j-1];
				elements[j] = elements[j-1];
			}

			keys[i] = key;
			elements[i] = ele;
			curSize++;
		}
		else
		{
		}
	}

	Element operator[](int index)
	{
		if( index >= curSize )
			index = curSize-1;
		else if( index < 0 )
			index = 0;

		return elements[index];
	}

	Element get(Key key)
	{
		int index = Find(key);
		return this->[](index);
	}

	// Binary search
	int find(Key key)
	{
		if( curSize <= 0 )
			return -1;

		int dwMin = 0;
		int dwMax = curSize - 1;
		int index = -1;

		int dwRange;
		int dwIndex;

		while (true)
		{
			dwRange = dwMax - dwMin;
			dwIndex = dwMin + (dwRange/2);

			if( keys[dwIndex] == key )
			{
				index = dwIndex;
				break;
			}

			// If the range is 0, and we didn't match above, then it must be unmatched
			if (dwRange == 0) 
				break;

			// If lower, check from min..index
			// If higher, check from index..max
			if (key < keys[dwIndex])
			{
				// Lower
				dwMax = dwIndex;
			}
			else
			{
				// Higher
				dwMin = dwIndex + 1;
			}
		}

		return index;
	}
};

#endif

