/*
* 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