/*
 *  Copyright 2001 Adrian Thurston <thurston@complang.org>
 */

/*  This file is part of Aapl.
 *
 *  Aapl is free software; you can redistribute it and/or modify it under the
 *  terms of the GNU Lesser General Public License as published by the Free
 *  Software Foundation; either version 2.1 of the License, or (at your option)
 *  any later version.
 *
 *  Aapl 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 Lesser General Public License for
 *  more details.
 *
 *  You should have received a copy of the GNU Lesser General Public License
 *  along with Aapl; if not, write to the Free Software Foundation, Inc., 59
 *  Temple Place, Suite 330, Boston, MA 02111-1307 USA
 */

/* This header is not wrapped in ifndefs because it is
 * not intended to be included by users directly. */

#ifdef AAPL_NAMESPACE
namespace Aapl {
#endif

/* Binary Search Table */
template < BST_TEMPL_DECLARE > class BstTable :
		public Compare,
		public Vector< Element, Resize >
{
	typedef Vector<Element, Resize> BaseVector;
	typedef Table<Element> BaseTable;

public:
	/**
	 * \brief Default constructor.
	 *
	 * Create an empty binary search table.
	 */
	BstTable() { }

	/**
	 * \brief Construct with initial value.
	 *
	 * Constructs a binary search table with an initial item. Uses the default
	 * constructor for initializing Value.
	 */
	BstTable(const Key &key) 
		{ insert(key); }

#if defined( BSTMAP )
	/**
	 * \brief Construct with initial value.
	 *
	 * Constructs a binary search table with an initial key/value pair.
	 */
	BstTable(const Key &key, const Value &val) 
		{ insert(key, val); }
#endif

#if ! defined( BSTSET )
	/**
	 * \brief Construct with initial value.
	 *
	 * Constructs a binary search table with an initial Element.
	 */
	BstTable(const Element &el) 
		{ insert(el); }
#endif

	Element *insert(const Key &key, Element **lastFound = 0);
	Element *insertMulti(const Key &key);

	bool insert(const BstTable &other);
	void insertMulti(const BstTable &other);

#if defined( BSTMAP )
	Element *insert(const Key &key, const Value &val, 
			Element **lastFound = 0);
	Element *insertMulti(const Key &key, const Value &val );
#endif

#if ! defined( BSTSET )
	Element *insert(const Element &el, Element **lastFound = 0);
	Element *insertMulti(const Element &el);
#endif

	Element *find(const Key &key, Element **lastFound = 0) const;
	bool findMulti( const Key &key, Element *&lower,
			Element *&upper ) const;

	bool remove(const Key &key);
	bool remove(Element *item);
	long removeMulti(const Key &key);
	long removeMulti(Element *lower, Element *upper);

	/* The following provide access to the underlying insert and remove
	 * functions that my be hidden by the BST insert and remove. The insertDup
	 * and insertNew functions will never be hidden. They are provided for
	 * consistency. The difference between the non-shared and the shared
	 * tables is the documentation reference to the invoked function. */	

#if !defined( SHARED_BST )
	/*@{*/

	/** \brief Call the insert of the underlying vector. 
	 *
	 * Provides to access to the vector insert, which may become hidden. Care
	 * should be taken to ensure that after the insert the ordering of
	 * elements is preserved. 
	 * Invokes Vector::insert( long pos, const T &val ).
	 */
	void vinsert(long pos, const Element &val)
		{ Vector< Element, Resize >::insert( pos, &val, 1 ); }

	/** \brief Call the insert of the underlying vector.
	 *
	 * Provides to access to the vector insert, which may become hidden. Care
	 * should be taken to ensure that after the insert the ordering of
	 * elements is preserved. 
	 * Invokes Vector::insert( long pos, const T *val, long len ).
	 */
	void vinsert(long pos, const Element *val, long len)
		{ Vector< Element, Resize >::insert( pos, val, len ); }

	/** \brief Call the insert of the underlying vector.
	 *
	 * Provides to access to the vector insert, which may become hidden. Care
	 * should be taken to ensure that after the insert the ordering of
	 * elements is preserved. 
	 * Invokes Vector::insert( long pos, const Vector &v ).
	 */
	void vinsert(long pos, const BstTable &v)
		{ Vector< Element, Resize >::insert( pos, v.data, v.tabLen ); }

	/*@}*/

	/*@{*/

	/** \brief Call the remove of the underlying vector. 
	 *
	 * 	Provides access to the vector remove, which may become hidden.
	 * 	Invokes Vector::remove( long pos ).
	 */
	void vremove(long pos)
		{ Vector< Element, Resize >::remove( pos, 1 ); }

	/** \brief Call the remove of the underlying vector. 
	 *
	 * Proves access to the vector remove, which may become hidden.
	 * Invokes Vector::remove( long pos, long len ). 
	 */
	void vremove(long pos, long len)
		{ Vector< Element, Resize >::remove( pos, len ); }

	/*@}*/
#else /* SHARED_BST */
	/*@{*/

	/** \brief Call the insert of the underlying vector. 
	 *
	 * Provides to access to the vector insert, which may become hidden. Care
	 * should be taken to ensure that after the insert the ordering of
	 * elements is preserved. 
	 * Invokes SVector::insert( long pos, const T &val ).
	 */
	void vinsert(long pos, const Element &val)
		{ Vector< Element, Resize >::insert( pos, &val, 1 ); }

	/** \brief Call the insert of the underlying vector.
	 *
	 * Provides to access to the vector insert, which may become hidden. Care
	 * should be taken to ensure that after the insert the ordering of
	 * elements is preserved. 
	 * Invokes SVector::insert( long pos, const T *val, long len ).
	 */
	void vinsert(long pos, const Element *val, long len)
		{ Vector< Element, Resize >::insert( pos, val, len ); }

	/** \brief Call the insert of the underlying vector.
	 *
	 * Provides to access to the vector insert, which may become hidden. Care
	 * should be taken to ensure that after the insert the ordering of
	 * elements is preserved. 
	 * Invokes SVector::insert( long pos, const SVector &v ).
	 */
	void vinsert(long pos, const BstTable &v)
		{ Vector< Element, Resize >::insert( pos, v.data, v.length() ); }

	/*@}*/

	/*@{*/

	/** \brief Call the remove of the underlying vector. 
	 *
	 * 	Provides access to the vector remove, which may become hidden.
	 * 	Invokes SVector::remove( long pos ).
	 */
	void vremove(long pos)
		{ Vector< Element, Resize >::remove( pos, 1 ); }

	/** \brief Call the remove of the underlying vector. 
	 *
	 * Proves access to the vector remove, which may become hidden.
	 * Invokes SVector::remove( long pos, long len ). 
	 */
	void vremove(long pos, long len)
		{ Vector< Element, Resize >::remove( pos, len ); }

	/*@}*/

#endif /* SHARED_BST */
};


#if 0
#if defined( SHARED_BST )
/**
 * \brief Construct a binary search table with an initial amount of
 * allocation.
 *
 * The table is initialized to have room for allocLength elements. The
 * table starts empty.
 */
template <BST_TEMPL_DEF> BstTable<BST_TEMPL_USE>::
		BstTable( long allocLen ) 
{
	/* Allocate the space if we are given a positive allocLen. */
	if ( allocLen > 0 ) {
		/* Allocate the data needed. */
		STabHead *head = (STabHead*) 
				malloc( sizeof(STabHead) + sizeof(Element) * allocLen );
		if ( head == 0 )
			throw std::bad_alloc();

		/* Set up the header and save the data pointer. */
		head->refCount = 1;
		head->allocLen = allocLen;
		head->tabLen = 0;
		BaseTable::data = (Element*) (head + 1);
	}
}
#else
/**
 * \brief Construct a binary search table with an initial amount of
 * allocation.
 *
 * The table is initialized to have room for allocLength elements. The
 * table starts empty.
 */
template <BST_TEMPL_DEF> BstTable<BST_TEMPL_USE>::
		BstTable( long allocLen ) 
{
	/* Allocate the space if we are given a positive allocLen. */
	BaseTable::allocLen = allocLen;
	if ( BaseTable::allocLen > 0 ) {
		BaseTable::data = (Element*) malloc(sizeof(Element) * BaseTable::allocLen);
		if ( BaseTable::data == NULL )
			throw std::bad_alloc();
	}
}

#endif
#endif

/**
 * \brief Find the element with the given key and remove it.
 *
 * If multiple elements with the given key exist, then it is unspecified which
 * element will be removed.
 *
 * \returns True if an element is found and consequently removed, false
 * otherwise.
 */
template <BST_TEMPL_DEF> bool BstTable<BST_TEMPL_USE>::
		remove(const Key &key)
{
	Element *el = find(key);
	if ( el != 0 ) {
		Vector< Element >::remove(el - BaseTable::data);
		return true;
	}
	return false;
}

/**
 * \brief Remove the element pointed to by item.
 *
 * If item does not point to an element in the tree, then undefined behaviour
 * results. If item is null, then remove has no effect.
 *
 * \returns True if item is not null, false otherwise.
 */
template <BST_TEMPL_DEF> bool BstTable<BST_TEMPL_USE>::
		remove( Element *item )
{
	if ( item != 0 ) {
		Vector< Element >::remove(item - BaseTable::data);
		return true;
	}
	return false;
}

/**
 * \brief Find and remove the entire range of elements with the given key.
 *
 * \returns The number of elements removed.
 */
template <BST_TEMPL_DEF> long BstTable<BST_TEMPL_USE>::
		removeMulti(const Key &key)
{
	Element *low, *high;
	if ( findMulti(key, low, high) ) {
		/* Get the length of the range. */
		long num = high - low + 1;
		Vector< Element >::remove(low - BaseTable::data, num);
		return num;
	}

	return 0;
}

template <BST_TEMPL_DEF> long BstTable<BST_TEMPL_USE>::
		removeMulti(Element *lower, Element *upper)
{
	/* Get the length of the range. */
	long num = upper - lower + 1;
	Vector< Element >::remove(lower - BaseTable::data, num);
	return num;
}


/**
 * \brief Find a range of elements with the given key.
 *
 * If any elements with the given key exist then lower and upper are set to
 * the low and high ends of the continous range of elements with the key.
 * Lower and upper will point to the first and last elements with the key.
 *
 * \returns True if any elements are found, false otherwise.
 */
template <BST_TEMPL_DEF> bool BstTable<BST_TEMPL_USE>::
		findMulti(const Key &key, Element *&low, Element *&high ) const
{
	const Element *lower, *mid, *upper;
	long keyRelation;
	const long tblLen = BaseTable::length();

	if ( BaseTable::data == 0 )
		return false;

	lower = BaseTable::data;
	upper = BaseTable::data + tblLen - 1;
	while ( true ) {
		if ( upper < lower ) {
			/* Did not find the fd in the array. */
			return false;
		}

		mid = lower + ((upper-lower)>>1);
		keyRelation = this->compare(key, GET_KEY(*mid));

		if ( keyRelation < 0 )
			upper = mid - 1;
		else if ( keyRelation > 0 )
			lower = mid + 1;
		else {
			Element *lowEnd = BaseTable::data - 1;
			Element *highEnd = BaseTable::data + tblLen;

			lower = mid - 1;
			while ( lower != lowEnd && 
					this->compare(key, GET_KEY(*lower)) == 0 )
				lower--;

			upper = mid + 1;
			while ( upper != highEnd && 
					this->compare(key, GET_KEY(*upper)) == 0 )
				upper++;
			
			low = (Element*)lower + 1;
			high = (Element*)upper - 1;
			return true;
		}
	}
}

/**
 * \brief Find an element with the given key.
 *
 * If the find succeeds then lastFound is set to the element found. If the
 * find fails then lastFound is set the location where the key would be
 * inserted. If there is more than one element in the tree with the given key,
 * then it is unspecified which element is returned as the match.
 *
 * \returns The element found on success, null on failure.
 */
template <BST_TEMPL_DEF> Element *BstTable<BST_TEMPL_USE>::
		find( const Key &key, Element **lastFound ) const
{
	const Element *lower, *mid, *upper;
	long keyRelation;
	const long tblLen = BaseTable::length();

	if ( BaseTable::data == 0 )
		return 0;

	lower = BaseTable::data;
	upper = BaseTable::data + tblLen - 1;
	while ( true ) {
		if ( upper < lower ) {
			/* Did not find the key. Last found gets the insert location. */
			if ( lastFound != 0 )
				*lastFound = (Element*)lower;
			return 0;
		}

		mid = lower + ((upper-lower)>>1);
		keyRelation = this->compare(key, GET_KEY(*mid));

		if ( keyRelation < 0 )
			upper = mid - 1;
		else if ( keyRelation > 0 )
			lower = mid + 1;
		else {
			/* Key is found. Last found gets the found record. */
			if ( lastFound != 0 )
				*lastFound = (Element*)mid;
			return (Element*)mid;
		}
	}
}

template <BST_TEMPL_DEF> Element *BstTable<BST_TEMPL_USE>::
		insert(const Key &key, Element **lastFound)
{
	const Element *lower, *mid, *upper;
	long keyRelation, insertPos;
	const long tblLen = BaseTable::length();

	if ( tblLen == 0 ) {
		/* If the table is empty then go straight to insert. */
		lower = BaseTable::data;
		goto insert;
	}

	lower = BaseTable::data;
	upper = BaseTable::data + tblLen - 1;
	while ( true ) {
		if ( upper < lower ) {
			/* Did not find the key in the array.
			 * Place to insert at is lower. */
			goto insert;
		}

		mid = lower + ((upper-lower)>>1);
		keyRelation = this->compare(key, GET_KEY(*mid));

		if ( keyRelation < 0 )
			upper = mid - 1;
		else if ( keyRelation > 0 )
			lower = mid + 1;
		else {
			if ( lastFound != 0 )
				*lastFound = (Element*)mid;
			return 0;
		}
	}

insert:
	/* Get the insert pos. */
	insertPos = lower - BaseTable::data;

	/* Do the insert. After makeRawSpaceFor, lower pointer is no good. */
	BaseVector::makeRawSpaceFor(insertPos, 1);
	new(BaseTable::data + insertPos) Element(key);

	/* Set lastFound */
	if ( lastFound != 0 )
		*lastFound = BaseTable::data + insertPos;
	return BaseTable::data + insertPos;
}


template <BST_TEMPL_DEF> Element *BstTable<BST_TEMPL_USE>::
		insertMulti(const Key &key)
{
	const Element *lower, *mid, *upper;
	long keyRelation, insertPos;
	const long tblLen = BaseTable::length();

	if ( tblLen == 0 ) {
		/* If the table is empty then go straight to insert. */
		lower = BaseTable::data;
		goto insert;
	}

	lower = BaseTable::data;
	upper = BaseTable::data + tblLen - 1;
	while ( true ) {
		if ( upper < lower ) {
			/* Did not find the key in the array.
			 * Place to insert at is lower. */
			goto insert;
		}

		mid = lower + ((upper-lower)>>1);
		keyRelation = compare(key, GET_KEY(*mid));

		if ( keyRelation < 0 )
			upper = mid - 1;
		else if ( keyRelation > 0 )
			lower = mid + 1;
		else {
			lower = mid;
			goto insert;
		}
	}

insert:
	/* Get the insert pos. */
	insertPos = lower - BaseTable::data;

	/* Do the insert. */
	BaseVector::makeRawSpaceFor(insertPos, 1);
	new(BaseTable::data + insertPos) Element(key);

	/* Return the element inserted. */
	return BaseTable::data + insertPos;
}

/**
 * \brief Insert each element from other.
 *
 * Always attempts to insert all elements even if the insert of some item from
 * other fails.
 *
 * \returns True if all items inserted successfully, false if any insert
 * failed.
 */
template <BST_TEMPL_DEF> bool BstTable<BST_TEMPL_USE>::
		insert(const BstTable &other)
{
	bool allSuccess = true;
	long otherLen = other.length();
	for ( long i = 0; i < otherLen; i++ ) {
		Element *el = insert( other.data[i] );
		if ( el == 0 )
			allSuccess = false;
	}
	return allSuccess;
}

/**
 * \brief Insert each element from other even if the elements exist already.
 *
 * No individual insertMulti can fail.
 */
template <BST_TEMPL_DEF> void BstTable<BST_TEMPL_USE>::
		insertMulti(const BstTable &other)
{
	long otherLen = other.length();
	for ( long i = 0; i < otherLen; i++ )
		insertMulti( other.data[i] );
}

#if ! defined( BSTSET )

/**
 * \brief Insert the given element.
 *
 * If the key in the given element does not already exist in the table then a
 * new element is inserted. They element copy constructor is used to place the
 * element into the table. If lastFound is given, it is set to the new element
 * created. If the insert fails then lastFound is set to the existing element
 * of the same key.
 *
 * \returns The new element created upon success, null upon failure.
 */
template <BST_TEMPL_DEF> Element *BstTable<BST_TEMPL_USE>::
		insert(const Element &el, Element **lastFound )
{
	const Element *lower, *mid, *upper;
	long keyRelation, insertPos;
	const long tblLen = BaseTable::length();

	if ( tblLen == 0 ) {
		/* If the table is empty then go straight to insert. */
		lower = BaseTable::data;
		goto insert;
	}

	lower = BaseTable::data;
	upper = BaseTable::data + tblLen - 1;
	while ( true ) {
		if ( upper < lower ) {
			/* Did not find the key in the array.
			 * Place to insert at is lower. */
			goto insert;
		}

		mid = lower + ((upper-lower)>>1);
		keyRelation = compare(GET_KEY(el), GET_KEY(*mid));

		if ( keyRelation < 0 )
			upper = mid - 1;
		else if ( keyRelation > 0 )
			lower = mid + 1;
		else {
			if ( lastFound != 0 )
				*lastFound = (Element*)mid;
			return 0;
		}
	}

insert:
	/* Get the insert pos. */
	insertPos = lower - BaseTable::data;

	/* Do the insert. After makeRawSpaceFor, lower pointer is no good. */
	BaseVector::makeRawSpaceFor(insertPos, 1);
	new(BaseTable::data + insertPos) Element(el);

	/* Set lastFound */
	if ( lastFound != 0 )
		*lastFound = BaseTable::data + insertPos;
	return BaseTable::data + insertPos;
}

/**
 * \brief Insert the given element even if it exists already.
 *
 * If the key in the given element exists already then the new element is
 * placed next to some other element of the same key. InsertMulti cannot fail.
 * The element copy constructor is used to place the element in the table.
 *
 * \returns The new element created.
 */
template <BST_TEMPL_DEF> Element *BstTable<BST_TEMPL_USE>::
		insertMulti(const Element &el)
{
	const Element *lower, *mid, *upper;
	long keyRelation, insertPos;
	const long tblLen = BaseTable::length();

	if ( tblLen == 0 ) {
		/* If the table is empty then go straight to insert. */
		lower = BaseTable::data;
		goto insert;
	}

	lower = BaseTable::data;
	upper = BaseTable::data + tblLen - 1;
	while ( true ) {
		if ( upper < lower ) {
			/* Did not find the fd in the array.
			 * Place to insert at is lower. */
			goto insert;
		}

		mid = lower + ((upper-lower)>>1);
		keyRelation = this->compare(GET_KEY(el), GET_KEY(*mid));

		if ( keyRelation < 0 )
			upper = mid - 1;
		else if ( keyRelation > 0 )
			lower = mid + 1;
		else {
			lower = mid;
			goto insert;
		}
	}

insert:
	/* Get the insert pos. */
	insertPos = lower - BaseTable::data;

	/* Do the insert. */
	BaseVector::makeRawSpaceFor(insertPos, 1);
	new(BaseTable::data + insertPos) Element(el);

	/* Return the element inserted. */
	return BaseTable::data + insertPos;
}
#endif


#if defined( BSTMAP )

/**
 * \brief Insert the given key-value pair.
 *
 * If the given key does not already exist in the table then the key-value
 * pair is inserted. Copy constructors are used to place the pair in the
 * table. If lastFound is given, it is set to the new entry created. If the
 * insert fails then lastFound is set to the existing pair of the same key.
 *
 * \returns The new element created upon success, null upon failure.
 */
template <BST_TEMPL_DEF> Element *BstTable<BST_TEMPL_USE>::
		insert(const Key &key, const Value &val, Element **lastFound)
{
	const Element *lower, *mid, *upper;
	long keyRelation, insertPos;
	const long tblLen = BaseTable::length();

	if ( tblLen == 0 ) {
		/* If the table is empty then go straight to insert. */
		lower = BaseTable::data;
		goto insert;
	}

	lower = BaseTable::data;
	upper = BaseTable::data + tblLen - 1;
	while ( true ) {
		if ( upper < lower ) {
			/* Did not find the fd in the array.
			 * Place to insert at is lower. */
			goto insert;
		}

		mid = lower + ((upper-lower)>>1);
		keyRelation = Compare::compare(key, mid->key);

		if ( keyRelation < 0 )
			upper = mid - 1;
		else if ( keyRelation > 0 )
			lower = mid + 1;
		else {
			if ( lastFound != NULL )
				*lastFound = (Element*)mid;
			return 0;
		}
	}

insert:
	/* Get the insert pos. */
	insertPos = lower - BaseTable::data;

	/* Do the insert. */
	BaseVector::makeRawSpaceFor(insertPos, 1);
	new(BaseTable::data + insertPos) Element(key, val);

	/* Set lastFound */
	if ( lastFound != NULL )
		*lastFound = BaseTable::data + insertPos;
	return BaseTable::data + insertPos;
}


/**
 * \brief Insert the given key-value pair even if the key exists already.
 *
 * If the key exists already then the key-value pair is placed next to some
 * other pair of the same key. InsertMulti cannot fail. Copy constructors are
 * used to place the pair in the table.
 *
 * \returns The new element created.
 */
template <BST_TEMPL_DEF> Element *BstTable<BST_TEMPL_USE>::
		insertMulti(const Key &key, const Value &val)
{
	const Element *lower, *mid, *upper;
	long keyRelation, insertPos;
	const long tblLen = BaseTable::length();

	if ( tblLen == 0 ) {
		/* If the table is empty then go straight to insert. */
		lower = BaseTable::data;
		goto insert;
	}

	lower = BaseTable::data;
	upper = BaseTable::data + tblLen - 1;
	while ( true ) {
		if ( upper < lower ) {
			/* Did not find the key in the array. 
			 * Place to insert at is lower. */
			goto insert;
		}

		mid = lower + ((upper-lower)>>1);
		keyRelation = Compare::compare(key, mid->key);

		if ( keyRelation < 0 )
			upper = mid - 1;
		else if ( keyRelation > 0 )
			lower = mid + 1;
		else {
			lower = mid;
			goto insert;
		}
	}

insert:
	/* Get the insert pos. */
	insertPos = lower - BaseTable::data;

	/* Do the insert. */
	BaseVector::makeRawSpaceFor(insertPos, 1);
	new(BaseTable::data + insertPos) Element(key, val);

	/* Return the element inserted. */
	return BaseTable::data + insertPos;
}

#endif

#ifdef AAPL_NAMESPACE
}
#endif