/*
* collect.cxx
*
* Container Classes
*
* Portable Windows Library
*
* Copyright (c) 1993-1998 Equivalence Pty. Ltd.
*
* The contents of this file are subject to the Mozilla Public License
* Version 1.0 (the "License"); you may not use this file except in
* compliance with the License. You may obtain a copy of the License at
* http://www.mozilla.org/MPL/
*
* Software distributed under the License is distributed on an "AS IS"
* basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
* the License for the specific language governing rights and limitations
* under the License.
*
* The Original Code is Portable Windows Library.
*
* The Initial Developer of the Original Code is Equivalence Pty. Ltd.
*
* Portions are Copyright (C) 1993 Free Software Foundation, Inc.
* All Rights Reserved.
*
* Contributor(s): ______________________________________.
*
* $Log: collect.cxx,v $
* Revision 1.72 2005/11/30 12:47:41 csoutheren
* Removed tabs, reformatted some code, and changed tags for Doxygen
*
* Revision 1.71 2005/11/25 01:01:15 csoutheren
* Applied patch #1351168
* PWlib various fixes
*
* Revision 1.70 2005/01/09 06:35:05 rjongbloed
* Fixed ability to make Clone() or MakeUnique() of a sorted list.
*
* Revision 1.69 2004/04/24 07:01:04 rjongbloed
* Fixed breaking of all lists with PAssertNULL chane. Oops.
*
* Revision 1.68 2004/04/24 06:27:56 rjongbloed
* Fixed GCC 3.4.0 warnings about PAssertNULL and improved recoverability on
* NULL pointer usage in various bits of code.
*
* Revision 1.67 2004/04/03 08:22:21 csoutheren
* Remove pseudo-RTTI and replaced with real RTTI
*
* Revision 1.66 2004/03/23 10:59:35 rjongbloed
* Added some extra bulletproofing of containers to avoid complaints by some
* memory checking tools, thanks Ted Szoczei
*
* Revision 1.65 2004/02/15 03:04:52 rjongbloed
* Fixed problem with PSortedList nil variable and assignment between instances,
* pointed out by Ben Lear.
*
* Revision 1.64 2004/02/09 06:23:32 csoutheren
* Added fix for gcc 3.3.1 problem. Apparently, it is unable to correctly resolve
* a function argument that is a reference to a const pointer. Changing the argument
* to be a pointer to a pointer solves the problem. Go figure
*
* Revision 1.63 2004/02/08 22:46:35 csoutheren
* Added casts to fix problems with gcc
*
* Revision 1.62 2004/02/08 11:13:20 rjongbloed
* Fixed crash in heavily loaded multi-threaded systems using simultaneous sorted
* lists, Thanks Federico Pinna, Fabrizio Ammollo and the gang at Reitek S.p.A.
*
* Revision 1.61 2003/09/24 22:13:58 dereksmithies
* Add fix for deleting an object, then readding it. Thanks Fabrizio Ammollo
*
* Revision 1.60 2003/08/31 22:11:30 dereksmithies
* Fix from Diego Tartara for the SetAt function. Many thanks.
*
* Revision 1.59 2002/12/02 04:27:37 robertj
* Added extra bullet proofing for some pathological conditions.
*
* Revision 1.58 2002/11/12 08:57:18 robertj
* Changed scope of PAbstraSortedList::Element class so descendant classes
* can get at it.
* Fixed problem with GetValuesIndex not returning first element of a certain
* value if the object was a PCaselessString.
*
* Revision 1.57 2002/06/25 02:24:59 robertj
* Improved assertion system to allow C++ class name to be displayed if
* desired, especially relevant to container classes.
*
* Revision 1.56 2002/06/12 09:40:58 robertj
* Fixed printing of a dictionary to utilise the stream fill character between
* each dictiionary element, as per general container semantics.
*
* Revision 1.55 2002/04/26 05:40:21 robertj
* Removed assumption that GetAt() on a dictionary will automatically convert
* the index to a POrdinalyKey. This breaks the PCollection semantics for
* GetAt() which is to get based on the ordinal position not the hashed position.
*
* Revision 1.54 2002/04/16 07:58:13 robertj
* Fixed MakeUnique for lists and sorted lists.
*
* Revision 1.53 2002/02/03 16:16:07 rogerh
* make nil static. Submitted by Peter Johnson <paj@chartermi.net>
*
* Revision 1.52 2002/01/31 05:02:50 robertj
* Fixed PSortedList::Remove function for removing objects with equal keys.
*
* Revision 1.51 2001/06/07 04:49:26 robertj
* Allowed for other separators than \n when printing elements of a collection.
*
* Revision 1.50 2001/01/24 06:19:14 yurik
* Windows CE port-related changes
*
* Revision 1.49 2000/11/28 12:47:13 robertj
* Added ability to separate collection entries with newline in PrintOn by using fillchar.
*
* Revision 1.48 1999/08/22 12:54:35 robertj
* Fixed warnings about inlines on older GNU compiler
*
* Revision 1.47 1999/02/16 08:08:06 robertj
* MSVC 6.0 compatibility changes.
*
* Revision 1.46 1998/11/02 12:53:52 robertj
* Fixed yet another bug in the object array SetSize() for unix systems.
*
* Revision 1.45 1998/10/31 14:01:58 robertj
* Fixed ANSI scoping of for loop variable.
*
* Revision 1.44 1998/10/30 10:41:57 robertj
* Fixed bug cause by previous bug fix in PObjectArray, deleting deleted entries.
*
* Revision 1.43 1998/10/28 00:57:43 robertj
* Fixed memory leak in PObjectArray.
* Fixed crash when doing GetValuesIndex() on array with NULL elements.
*
* Revision 1.42 1998/10/13 14:06:16 robertj
* Complete rewrite of memory leak detection code.
*
* Revision 1.41 1998/09/23 06:21:52 robertj
* Added open source copyright license.
*
* Revision 1.40 1998/09/14 12:32:45 robertj
* Fixed bug in ordinal dictionary GetAt() and SetAt() for scalar integer types.
*
* Revision 1.39 1998/08/20 05:48:51 robertj
* Fixed bug on removing entries by index from a PSet().
*
* Revision 1.38 1998/05/17 02:29:46 robertj
* Fixed GetObjectsIndex()/GetValuesIndex() finding elements that have a hash clash.
*
* Revision 1.37 1998/03/26 23:31:50 robertj
* Fixed bug in RemoveAll() deleting objects twice.
*
* Revision 1.36 1998/03/26 11:19:50 robertj
* Fix bug with unsigned PINDEX in array SetSize.
*
* Revision 1.35 1998/03/25 12:58:41 robertj
* Fixed memory leak if resize PArray
*
* Revision 1.34 1998/03/24 02:58:52 robertj
* Fixed uninitialised variable in dictionary MakeUnique() function.
*
* Revision 1.33 1998/01/26 01:41:19 robertj
* GNU compatibility.
*
* Revision 1.32 1998/01/26 00:36:10 robertj
* Fixed MakeUnique() function for dictionaries and sets.
*
* Revision 1.31 1998/01/06 12:00:15 robertj
* Fixed "typesafe" templates/macros for dictionaries, especially on GNU.
*
* Revision 1.30 1997/12/11 10:30:02 robertj
* Added type correct Contains() function to dictionaries.
*
* Revision 1.29 1997/06/08 04:48:30 robertj
* Fixed problems in sorted list with multiple identical entries.
*
* Revision 1.28 1997/04/27 05:50:14 robertj
* DLL support.
*
* Revision 1.27 1997/02/14 13:59:09 robertj
* Rewrite of sorted list to use sentinel record rather than NULL pointer.
*
* Revision 1.26 1996/08/17 09:55:23 robertj
* Optimised RemoveAll() for object arrays.
*
* Revision 1.25 1996/08/08 10:08:43 robertj
* Directory structure changes for common files.
*
* Revision 1.24 1996/07/15 10:32:52 robertj
* Fixed bug in sorted list (crash on remove).
*
* Revision 1.23 1996/05/26 03:46:24 robertj
* Compatibility to GNU 2.7.x
*
* Revision 1.22 1996/03/26 00:52:38 robertj
* Fixed bug in dictionary decrementing size when removing element even if already removed.
*
* Revision 1.21 1996/02/19 13:32:31 robertj
* Fixed yet another bug in PSortedList, not setting cache index value correctly.
*
* Revision 1.20 1996/02/08 12:24:13 robertj
* Added default print for dictionaries in form key=data\n.
* Added missing GetAt() function on PSet to be consistent with all others.
*
* Revision 1.19 1996/02/03 11:07:59 robertj
* A bit more bullet proofing of sorted list class.
*
* Revision 1.18 1996/01/30 23:30:40 robertj
* Added optimisation to sorted list GetAt() to use cached element.
*
* Revision 1.17 1996/01/28 14:11:45 robertj
* Fixed bug in sorted list for when getting entry one before last one cached.
*
* Revision 1.16 1996/01/28 02:52:45 robertj
* Added assert into all Compare functions to assure comparison between compatible objects.
*
* Revision 1.15 1996/01/23 13:18:29 robertj
* Fixed bug in sorted list GetObjectsIndex not checking if is same object
* Fixed bug in sorted list append not returning correct value.
*
* Revision 1.14 1995/01/27 11:12:38 robertj
* Fixed nasty bug in sorted lists.
*
* Revision 1.13 1995/01/09 12:31:49 robertj
* Removed unnecesary return value from I/O functions.
*
* Revision 1.12 1994/12/13 11:50:52 robertj
* Added MakeUnique() function to all container classes.
*
* Revision 1.11 1994/12/12 10:16:25 robertj
* Restructuring and documentation of container classes.
* Renaming of some macros for declaring container classes.
* Added some extra functionality to PString.
* Added start to 2 byte characters in PString.
* Fixed incorrect overrides in PCaselessString.
*
* Revision 1.10 1994/12/05 11:24:58 robertj
* Fixed bugs in InsertAt and RemoveAt in PObjectArray.
*
* Revision 1.9 1994/10/30 11:34:49 robertj
* Fixed ObjectArray to have pointer to array object pointers.
*
* Revision 1.8 1994/10/23 03:41:31 robertj
* Fixed dictionary functions that should work by index not key.
*
* Revision 1.7 1994/09/25 10:49:09 robertj
* Removed redundent PAssertNULL.
*
* Revision 1.6 1994/08/21 23:43:02 robertj
* Fixed bug in lists when inserting element.
*
* Revision 1.5 1994/07/27 05:58:07 robertj
* Synchronisation.
*
* Revision 1.4 1994/07/17 10:46:06 robertj
* Fixed searching in sorted lists.
*
* Revision 1.3 1994/07/02 03:03:49 robertj
* Added container searching facilities..
*
* Revision 1.2 1994/06/25 11:55:15 robertj
* Unix version synchronisation.
*
// Revision 1.1 1994/04/20 12:17:44 robertj
// Initial revision
//
*/
#include <ptlib.h>
#ifndef _WIN32_WCE
#define new PNEW
#undef __CLASS__
#define __CLASS__ GetClass()
#endif
///////////////////////////////////////////////////////////////////////////////
void PCollection::PrintOn(ostream &strm) const
{
char separator = strm.fill();
int width = strm.width();
for (PINDEX i = 0; i < GetSize(); i++) {
if (i > 0 && separator != ' ')
strm << separator;
PObject * obj = GetAt(i);
if (obj != NULL) {
if (separator != ' ')
strm.width(width);
strm << *obj;
}
}
if (separator == '\n')
strm << '\n';
}
void PCollection::RemoveAll()
{
while (GetSize() > 0)
RemoveAt(0);
}
///////////////////////////////////////////////////////////////////////////////
void PArrayObjects::CopyContents(const PArrayObjects & array)
{
theArray = array.theArray;
}
void PArrayObjects::DestroyContents()
{
if (reference->deleteObjects && theArray != NULL) {
for (PINDEX i = 0; i < theArray->GetSize(); i++) {
if ((*theArray)[i] != NULL)
delete (*theArray)[i];
}
}
delete theArray;
theArray = NULL;
}
void PArrayObjects::RemoveAll()
{
SetSize(0);
}
void PArrayObjects::CloneContents(const PArrayObjects * array)
{
ObjPtrArray & oldArray = *array->theArray;
theArray = new ObjPtrArray(oldArray.GetSize());
for (PINDEX i = 0; i < GetSize(); i++) {
PObject * ptr = oldArray[i];
if (ptr != NULL)
SetAt(i, ptr->Clone());
}
}
PObject::Comparison PArrayObjects::Compare(const PObject & obj) const
{
PAssert(PIsDescendant(&obj, PArrayObjects), PInvalidCast);
const PArrayObjects & other = (const PArrayObjects &)obj;
PINDEX i;
for (i = 0; i < GetSize(); i++) {
if (i >= other.GetSize() || *(*theArray)[i] < *(*other.theArray)[i])
return LessThan;
if (*(*theArray)[i] > *(*other.theArray)[i])
return GreaterThan;
}
return i < other.GetSize() ? GreaterThan : EqualTo;
}
PINDEX PArrayObjects::GetSize() const
{
return theArray->GetSize();
}
BOOL PArrayObjects::SetSize(PINDEX newSize)
{
PINDEX sz = theArray->GetSize();
if (reference->deleteObjects && sz > 0) {
for (PINDEX i = sz; i > newSize; i--) {
PObject * obj = theArray->GetAt(i-1);
if (obj != NULL)
delete obj;
}
}
return theArray->SetSize(newSize);
}
PINDEX PArrayObjects::Append(PObject * obj)
{
PINDEX where = GetSize();
SetAt(where, obj);
return where;
}
PINDEX PArrayObjects::Insert(const PObject & before, PObject * obj)
{
PINDEX where = GetObjectsIndex(&before);
InsertAt(where, obj);
return where;
}
BOOL PArrayObjects::Remove(const PObject * obj)
{
PINDEX i = GetObjectsIndex(obj);
if (i == P_MAX_INDEX)
return FALSE;
RemoveAt(i);
return TRUE;
}
PObject * PArrayObjects::GetAt(PINDEX index) const
{
return (*theArray)[index];
}
BOOL PArrayObjects::SetAt(PINDEX index, PObject * obj)
{
if (!theArray->SetMinSize(index+1))
return FALSE;
PObject * oldObj = theArray->GetAt(index);
if (oldObj != NULL && reference->deleteObjects)
delete oldObj;
(*theArray)[index] = obj;
return TRUE;
}
PINDEX PArrayObjects::InsertAt(PINDEX index, PObject * obj)
{
for (PINDEX i = GetSize(); i > index; i--)
(*theArray)[i] = (*theArray)[i-1];
(*theArray)[index] = obj;
return index;
}
PObject * PArrayObjects::RemoveAt(PINDEX index)
{
PObject * obj = (*theArray)[index];
PINDEX size = GetSize()-1;
PINDEX i;
for (i = index; i < size; i++)
(*theArray)[i] = (*theArray)[i+1];
(*theArray)[i] = NULL;
SetSize(size);
if (obj != NULL && reference->deleteObjects) {
delete obj;
obj = NULL;
}
return obj;
}
PINDEX PArrayObjects::GetObjectsIndex(const PObject * obj) const
{
for (PINDEX i = 0; i < GetSize(); i++) {
if ((*theArray)[i] == obj)
return i;
}
return P_MAX_INDEX;
}
PINDEX PArrayObjects::GetValuesIndex(const PObject & obj) const
{
for (PINDEX i = 0; i < GetSize(); i++) {
PObject * elmt = (*theArray)[i];
if (elmt != NULL && *elmt == obj)
return i;
}
return P_MAX_INDEX;
}
///////////////////////////////////////////////////////////////////////////////
void PAbstractList::DestroyContents()
{
RemoveAll();
delete info;
info = NULL;
}
void PAbstractList::CopyContents(const PAbstractList & list)
{
info = list.info;
}
void PAbstractList::CloneContents(const PAbstractList * list)
{
Element * element = list->info->head;
info = new Info;
PAssert(info != NULL, POutOfMemory);
while (element != NULL) {
Element * newElement = new Element(element->data->Clone());
if (info->head == NULL)
info->head = info->tail = newElement;
else {
newElement->prev = info->tail;
info->tail->next = newElement;
info->tail = newElement;
}
element = element->next;
}
}
PObject::Comparison PAbstractList::Compare(const PObject & obj) const
{
PAssert(PIsDescendant(&obj, PAbstractList), PInvalidCast);
Element * elmt1 = info->head;
Element * elmt2 = ((const PAbstractList &)obj).info->head;
while (elmt1 != NULL && elmt2 != NULL) {
if (elmt1 == NULL)
return LessThan;
if (elmt2 == NULL)
return GreaterThan;
if (*elmt1->data < *elmt2->data)
return LessThan;
if (*elmt1->data > *elmt2->data)
return GreaterThan;
elmt1 = elmt1->next;
elmt2 = elmt2->next;
}
return EqualTo;
}
BOOL PAbstractList::SetSize(PINDEX)
{
return TRUE;
}
PINDEX PAbstractList::Append(PObject * obj)
{
if (PAssertNULL(obj) == NULL)
return P_MAX_INDEX;
Element * element = new Element(obj);
if (info->tail != NULL)
info->tail->next = element;
element->prev = info->tail;
element->next = NULL;
if (info->head == NULL)
info->head = element;
info->tail = element;
info->lastElement = element;
info->lastIndex = GetSize();
reference->size++;
return info->lastIndex;
}
PINDEX PAbstractList::Insert(const PObject & before, PObject * obj)
{
if (PAssertNULL(obj) == NULL)
return P_MAX_INDEX;
PINDEX where = GetObjectsIndex(&before);
InsertAt(where, obj);
return where;
}
PINDEX PAbstractList::InsertAt(PINDEX index, PObject * obj)
{
if (PAssertNULL(obj) == NULL)
return P_MAX_INDEX;
if (index >= GetSize())
return Append(obj);
PAssert(SetCurrent(index), PInvalidArrayIndex);
Element * newElement = new Element(obj);
if (info->lastElement->prev != NULL)
info->lastElement->prev->next = newElement;
else
info->head = newElement;
newElement->prev = info->lastElement->prev;
newElement->next = info->lastElement;
info->lastElement->prev = newElement;
info->lastElement = newElement;
info->lastIndex = index;
reference->size++;
return index;
}
BOOL PAbstractList::Remove(const PObject * obj)
{
PINDEX i = GetObjectsIndex(obj);
if (i == P_MAX_INDEX)
return FALSE;
RemoveAt(i);
return TRUE;
}
PObject * PAbstractList::RemoveAt(PINDEX index)
{
if (!SetCurrent(index)) {
PAssertAlways(PInvalidArrayIndex);
return NULL;
}
if(info == NULL){
PAssertAlways("info is null");
return NULL;
}
Element * elmt = info->lastElement;
if(elmt == NULL){
PAssertAlways("elmt is null");
return NULL;
}
if (elmt->prev != NULL)
elmt->prev->next = elmt->next;
else {
info->head = elmt->next;
if (info->head != NULL)
info->head->prev = NULL;
}
if (elmt->next != NULL)
elmt->next->prev = elmt->prev;
else {
info->tail = elmt->prev;
if (info->tail != NULL)
info->tail->next = NULL;
}
if (elmt->next != NULL)
info->lastElement = elmt->next;
else {
info->lastElement = elmt->prev;
info->lastIndex--;
}
if((reference == NULL) || (reference->size == 0)){
PAssertAlways("reference is null or reference->size == 0");
return NULL;
}
reference->size--;
PObject * obj = elmt->data;
if (obj != NULL && reference->deleteObjects) {
delete obj;
obj = NULL;
}
delete elmt;
return obj;
}
PObject * PAbstractList::GetAt(PINDEX index) const
{
return SetCurrent(index) ? info->lastElement->data : (PObject *)NULL;
}
BOOL PAbstractList::SetAt(PINDEX index, PObject * val)
{
if (!SetCurrent(index))
return FALSE;
info->lastElement->data = val;
return TRUE;
}
BOOL PAbstractList::ReplaceAt(PINDEX index, PObject * val)
{
if (!SetCurrent(index))
return FALSE;
if (info->lastElement->data != NULL && reference->deleteObjects) {
delete info->lastElement->data;
}
info->lastElement->data = val;
return TRUE;
}
PINDEX PAbstractList::GetObjectsIndex(const PObject * obj) const
{
PINDEX index = 0;
Element * element = info->head;
while (element != NULL) {
if (element->data == obj) {
info->lastElement = element;
info->lastIndex = index;
return index;
}
element = element->next;
index++;
}
return P_MAX_INDEX;
}
PINDEX PAbstractList::GetValuesIndex(const PObject & obj) const
{
PINDEX index = 0;
Element * element = info->head;
while (element != NULL) {
if (*element->data == obj) {
info->lastElement = element;
info->lastIndex = index;
return index;
}
element = element->next;
index++;
}
return P_MAX_INDEX;
}
BOOL PAbstractList::SetCurrent(PINDEX index) const
{
if (index >= GetSize())
return FALSE;
if (info->lastElement == NULL || info->lastIndex >= GetSize() ||
index < info->lastIndex/2 || index > (info->lastIndex+GetSize())/2) {
if (index < GetSize()/2) {
info->lastIndex = 0;
info->lastElement = info->head;
}
else {
info->lastIndex = GetSize()-1;
info->lastElement = info->tail;
}
}
while (info->lastIndex < index) {
info->lastElement = info->lastElement->next;
info->lastIndex++;
}
while (info->lastIndex > index) {
info->lastElement = info->lastElement->prev;
info->lastIndex--;
}
return TRUE;
}
PAbstractList::Element::Element(PObject * theData)
{
next = prev = NULL;
data = theData;
}
///////////////////////////////////////////////////////////////////////////////
PAbstractSortedList::PAbstractSortedList()
{
info = new Info;
PAssert(info != NULL, POutOfMemory);
}
PAbstractSortedList::Info::Info()
{
root = &nil;
lastElement = NULL;
lastIndex = P_MAX_INDEX;
nil.parent = nil.left = nil.right = &nil;
nil.subTreeSize = 0;
nil.colour = Element::Black;
nil.data = NULL;
}
void PAbstractSortedList::DestroyContents()
{
RemoveAll();
delete info;
info = NULL;
}
void PAbstractSortedList::CopyContents(const PAbstractSortedList & list)
{
info = list.info;
}
void PAbstractSortedList::CloneContents(const PAbstractSortedList * list)
{
Info * otherInfo = list->info;
info = new Info;
PAssert(info != NULL, POutOfMemory);
reference->size = 0;
// Have to do this in this manner rather than just doing a for() loop
// as "this" and "list" may be the same object and we just changed info in
// "this" so we need to use the info in "list" saved previously.
Element * element = otherInfo->OrderSelect(otherInfo->root, 1);
while (element != &otherInfo->nil) {
Append(element->data->Clone());
element = otherInfo->Successor(element);
}
}
BOOL PAbstractSortedList::SetSize(PINDEX)
{
return TRUE;
}
PObject::Comparison PAbstractSortedList::Compare(const PObject & obj) const
{
PAssert(PIsDescendant(&obj, PAbstractSortedList), PInvalidCast);
Element * elmt1 = info->root;
while (elmt1->left != &info->nil)
elmt1 = elmt1->left;
Element * elmt2 = ((const PAbstractSortedList &)obj).info->root;
while (elmt2->left != &info->nil)
elmt2 = elmt2->left;
while (elmt1 != &info->nil && elmt2 != &info->nil) {
if (elmt1 == &info->nil)
return LessThan;
if (elmt2 == &info->nil)
return GreaterThan;
if (*elmt1->data < *elmt2->data)
return LessThan;
if (*elmt1->data > *elmt2->data)
return GreaterThan;
elmt1 = info->Successor(elmt1);
elmt2 = info->Successor(elmt2);
}
return EqualTo;
}
PINDEX PAbstractSortedList::Append(PObject * obj)
{
if (PAssertNULL(obj) == NULL)
return P_MAX_INDEX;
Element * z = new Element;
z->parent = z->left = z->right = &info->nil;
z->colour = Element::Black;
z->subTreeSize = 1;
z->data = obj;
Element * x = info->root;
Element * y = &info->nil;
while (x != &info->nil) {
x->subTreeSize++;
y = x;
x = *z->data < *x->data ? x->left : x->right;
}
z->parent = y;
if (y == &info->nil)
info->root = z;
else if (*z->data < *y->data)
y->left = z;
else
y->right = z;
info->lastElement = x = z;
x->colour = Element::Red;
while (x != info->root && x->parent->colour == Element::Red) {
if (x->parent == x->parent->parent->left) {
y = x->parent->parent->right;
if (y->colour == Element::Red) {
x->parent->colour = Element::Black;
y->colour = Element::Black;
x->parent->parent->colour = Element::Red;
x = x->parent->parent;
}
else {
if (x == x->parent->right) {
x = x->parent;
LeftRotate(x);
}
x->parent->colour = Element::Black;
x->parent->parent->colour = Element::Red;
RightRotate(x->parent->parent);
}
}
else {
y = x->parent->parent->left;
if (y->colour == Element::Red) {
x->parent->colour = Element::Black;
y->colour = Element::Black;
x->parent->parent->colour = Element::Red;
x = x->parent->parent;
}
else {
if (x == x->parent->left) {
x = x->parent;
RightRotate(x);
}
x->parent->colour = Element::Black;
x->parent->parent->colour = Element::Red;
LeftRotate(x->parent->parent);
}
}
}
info->root->colour = Element::Black;
x = info->lastElement;
info->lastIndex = x->left->subTreeSize;
while (x != info->root) {
if (x != x->parent->left)
info->lastIndex += x->parent->left->subTreeSize+1;
x = x->parent;
}
reference->size++;
return info->lastIndex;
}
BOOL PAbstractSortedList::Remove(const PObject * obj)
{
if (GetObjectsIndex(obj) == P_MAX_INDEX)
return FALSE;
RemoveElement(info->lastElement);
return TRUE;
}
PObject * PAbstractSortedList::RemoveAt(PINDEX index)
{
Element * node = info->OrderSelect(info->root, index+1);
if (node == &info->nil)
return NULL;
PObject * data = node->data;
RemoveElement(node);
return reference->deleteObjects ? (PObject *)NULL : data;
}
void PAbstractSortedList::RemoveAll()
{
if (info->root != &info->nil) {
DeleteSubTrees(info->root, reference->deleteObjects);
delete info->root;
info->root = &info->nil;
reference->size = 0;
}
}
PINDEX PAbstractSortedList::Insert(const PObject &, PObject * obj)
{
return Append(obj);
}
PINDEX PAbstractSortedList::InsertAt(PINDEX, PObject * obj)
{
return Append(obj);
}
BOOL PAbstractSortedList::SetAt(PINDEX, PObject *)
{
return FALSE;
}
PObject * PAbstractSortedList::GetAt(PINDEX index) const
{
if (index >= GetSize())
return NULL;
if (index != info->lastIndex) {
if (index == info->lastIndex-1) {
info->lastIndex--;
info->lastElement = info->Predecessor(info->lastElement);
}
else if (index == info->lastIndex+1 && info->lastElement != NULL) {
info->lastIndex++;
info->lastElement = info->Successor(info->lastElement);
}
else {
info->lastIndex = index;
info->lastElement = info->OrderSelect(info->root, index+1);
}
}
return PAssertNULL(info->lastElement)->data;
}
PINDEX PAbstractSortedList::GetObjectsIndex(const PObject * obj) const
{
Element * elmt = NULL;
PINDEX pos = ValueSelect(info->root, *obj, (const Element **)&elmt);
if (pos == P_MAX_INDEX)
return P_MAX_INDEX;
if (elmt->data != obj) {
PINDEX savePos = pos;
Element * saveElmt = elmt;
while (elmt->data != obj &&
(elmt = info->Predecessor(elmt)) != &info->nil &&
*obj == *elmt->data)
pos--;
if (elmt->data != obj) {
pos = savePos;
elmt = saveElmt;
while (elmt->data != obj &&
(elmt = info->Successor(elmt)) != &info->nil &&
*obj == *elmt->data)
pos++;
if (elmt->data != obj)
return P_MAX_INDEX;
}
}
info->lastIndex = pos;
info->lastElement = elmt;
return pos;
}
PINDEX PAbstractSortedList::GetValuesIndex(const PObject & obj) const
{
PINDEX pos = ValueSelect(info->root, obj, (const Element **)&info->lastElement);
if (pos == P_MAX_INDEX)
return P_MAX_INDEX;
info->lastIndex = pos;
Element * prev;
while ((prev = info->Predecessor(info->lastElement)) != &info->nil &&
prev->data->Compare(obj) == EqualTo) {
info->lastElement = prev;
info->lastIndex--;
}
return info->lastIndex;
}
void PAbstractSortedList::RemoveElement(Element * node)
{
// Don't try an remove one of the special leaf nodes!
if (PAssertNULL(node) == &info->nil)
return;
if (node->data != NULL && reference->deleteObjects)
delete node->data;
Element * y = node->left == &info->nil || node->right == &info->nil ? node : info->Successor(node);
Element * t = y;
while (t != &info->nil) {
t->subTreeSize--;
t = t->parent;
}
Element * x = y->left != &info->nil ? y->left : y->right;
x->parent = y->parent;
if (y->parent == &info->nil)
info->root = x;
else if (y == y->parent->left)
y->parent->left = x;
else
y->parent->right = x;
if (y != node)
node->data = y->data;
if (y->colour == Element::Black) {
while (x != info->root && x->colour == Element::Black) {
if (x == x->parent->left) {
Element * w = x->parent->right;
if (w->colour == Element::Red) {
w->colour = Element::Black;
x->parent->colour = Element::Red;
LeftRotate(x->parent);
w = x->parent->right;
}
if (w->left->colour == Element::Black && w->right->colour == Element::Black) {
w->colour = Element::Red;
x = x->parent;
}
else {
if (w->right->colour == Element::Black) {
w->left->colour = Element::Black;
w->colour = Element::Red;
RightRotate(w);
w = x->parent->right;
}
w->colour = x->parent->colour;
x->parent->colour = Element::Black;
w->right->colour = Element::Black;
LeftRotate(x->parent);
x = info->root;
}
}
else {
Element * w = x->parent->left;
if (w->colour == Element::Red) {
w->colour = Element::Black;
x->parent->colour = Element::Red;
RightRotate(x->parent);
w = x->parent->left;
}
if (w->right->colour == Element::Black && w->left->colour == Element::Black) {
w->colour = Element::Red;
x = x->parent;
}
else {
if (w->left->colour == Element::Black) {
w->right->colour = Element::Black;
w->colour = Element::Red;
LeftRotate(w);
w = x->parent->left;
}
w->colour = x->parent->colour;
x->parent->colour = Element::Black;
w->left->colour = Element::Black;
RightRotate(x->parent);
x = info->root;
}
}
}
x->colour = Element::Black;
}
delete y;
reference->size--;
info->lastIndex = P_MAX_INDEX;
info->lastElement = NULL;
}
void PAbstractSortedList::LeftRotate(Element * node)
{
Element * pivot = PAssertNULL(node)->right;
node->right = pivot->left;
if (pivot->left != &info->nil)
pivot->left->parent = node;
pivot->parent = node->parent;
if (node->parent == &info->nil)
info->root = pivot;
else if (node == node->parent->left)
node->parent->left = pivot;
else
node->parent->right = pivot;
pivot->left = node;
node->parent = pivot;
pivot->subTreeSize = node->subTreeSize;
node->subTreeSize = node->left->subTreeSize + node->right->subTreeSize + 1;
}
void PAbstractSortedList::RightRotate(Element * node)
{
Element * pivot = PAssertNULL(node)->left;
node->left = pivot->right;
if (pivot->right != &info->nil)
pivot->right->parent = node;
pivot->parent = node->parent;
if (node->parent == &info->nil)
info->root = pivot;
else if (node == node->parent->right)
node->parent->right = pivot;
else
node->parent->left = pivot;
pivot->right = node;
node->parent = pivot;
pivot->subTreeSize = node->subTreeSize;
node->subTreeSize = node->left->subTreeSize + node->right->subTreeSize + 1;
}
PAbstractSortedList::Element * PAbstractSortedList::Info ::Successor(const Element * node) const
{
Element * next;
if (node->right != &nil) {
next = node->right;
while (next->left != &nil)
next = next->left;
}
else {
next = node->parent;
while (next != &nil && node == next->right) {
node = next;
next = node->parent;
}
}
return next;
}
PAbstractSortedList::Element * PAbstractSortedList::Info ::Predecessor(const Element * node) const
{
Element * pred;
if (node->left != &nil) {
pred = node->left;
while (pred->right != &nil)
pred = pred->right;
}
else {
pred = node->parent;
while (pred != &nil && node == pred->left) {
node = pred;
pred = node->parent;
}
}
return pred;
}
PAbstractSortedList::Element * PAbstractSortedList::Info::OrderSelect(Element * node, PINDEX index) const
{
PINDEX r = node->left->subTreeSize+1;
if (index == r)
return node;
if (index < r) {
if (node->left != &nil)
return OrderSelect(node->left, index);
}
else {
if (node->right != &nil)
return OrderSelect(node->right, index - r);
}
PAssertAlways2("PAbstractSortedList::Element", "Order select failed!");
return (Element *)&nil;
}
PINDEX PAbstractSortedList::ValueSelect(const Element * node,
const PObject & obj,
const Element ** lastElement) const
{
if (node != &info->nil) {
switch (node->data->Compare(obj)) {
case PObject::LessThan :
{
PINDEX index = ValueSelect(node->right, obj, lastElement);
if (index != P_MAX_INDEX)
return node->left->subTreeSize + index + 1;
break;
}
case PObject::GreaterThan :
return ValueSelect(node->left, obj, lastElement);
default :
*lastElement = node;
return node->left->subTreeSize;
}
}
return P_MAX_INDEX;
}
void PAbstractSortedList::DeleteSubTrees(Element * node, BOOL deleteObject)
{
if (node->left != &info->nil) {
DeleteSubTrees(node->left, deleteObject);
delete node->left;
node->left = &info->nil;
}
if (node->right != &info->nil) {
DeleteSubTrees(node->right, deleteObject);
delete node->right;
node->right = &info->nil;
}
if (deleteObject) {
delete node->data;
node->data = NULL;
}
}
///////////////////////////////////////////////////////////////////////////////
PObject * POrdinalKey::Clone() const
{
return new POrdinalKey(theKey);
}
PObject::Comparison POrdinalKey::Compare(const PObject & obj) const
{
PAssert(PIsDescendant(&obj, POrdinalKey), PInvalidCast);
const POrdinalKey & other = (const POrdinalKey &)obj;
if (theKey < other.theKey)
return LessThan;
if (theKey > other.theKey)
return GreaterThan;
return EqualTo;
}
PINDEX POrdinalKey::HashFunction() const
{
return PABSINDEX(theKey)%23;
}
void POrdinalKey::PrintOn(ostream & strm) const
{
strm << theKey;
}
///////////////////////////////////////////////////////////////////////////////
void PHashTable::Table::DestroyContents()
{
for (PINDEX i = 0; i < GetSize(); i++) {
Element * list = GetAt(i);
if (list != NULL) {
Element * elmt = list;
do {
Element * nextElmt = elmt->next;
if (elmt->data != NULL && reference->deleteObjects)
delete elmt->data;
if (deleteKeys)
delete elmt->key;
delete elmt;
elmt = nextElmt;
} while (elmt != list);
}
}
PAbstractArray::DestroyContents();
}
PINDEX PHashTable::Table::AppendElement(PObject * key, PObject * data)
{
lastElement = NULL;
PINDEX bucket = PAssertNULL(key)->HashFunction();
Element * list = GetAt(bucket);
Element * element = new Element;
PAssert(element != NULL, POutOfMemory);
element->key = key;
element->data = data;
if (list == NULL) {
element->next = element->prev = element;
SetAt(bucket, element);
}
else if (list == list->prev) {
list->next = list->prev = element;
element->next = element->prev = list;
}
else {
element->next = list;
element->prev = list->prev;
list->prev->next = element;
list->prev = element;
}
lastElement = element;
lastIndex = P_MAX_INDEX;
return bucket;
}
PObject * PHashTable::Table::RemoveElement(const PObject & key)
{
PObject * obj = NULL;
if (GetElementAt(key) != NULL) {
if (lastElement == lastElement->prev)
SetAt(key.HashFunction(), NULL);
else {
lastElement->prev->next = lastElement->next;
lastElement->next->prev = lastElement->prev;
SetAt(key.HashFunction(), lastElement->next);
}
obj = lastElement->data;
if (deleteKeys)
delete lastElement->key;
delete lastElement;
lastElement = NULL;
}
return obj;
}
BOOL PHashTable::Table::SetLastElementAt(PINDEX index)
{
if (index == 0 || lastElement == NULL || lastIndex == P_MAX_INDEX) {
lastIndex = 0;
lastBucket = 0;
while ((lastElement = GetAt(lastBucket)) == NULL) {
if (lastBucket >= GetSize())
return FALSE;
lastBucket++;
}
}
if (lastIndex == index)
return TRUE;
if (lastIndex < index) {
while (lastIndex != index) {
if (lastElement->next != operator[](lastBucket))
lastElement = lastElement->next;
else {
do {
if (++lastBucket >= GetSize())
return FALSE;
} while ((lastElement = operator[](lastBucket)) == NULL);
}
lastIndex++;
}
}
else {
while (lastIndex != index) {
if (lastElement != operator[](lastBucket))
lastElement = lastElement->prev;
else {
do {
if (lastBucket-- == 0)
return FALSE;
} while ((lastElement = operator[](lastBucket)) == NULL);
lastElement = lastElement->prev;
}
lastIndex--;
}
}
return TRUE;
}
PHashTable::Element * PHashTable::Table::GetElementAt(const PObject & key)
{
if (lastElement != NULL && *lastElement->key == key)
return lastElement;
Element * list = GetAt(key.HashFunction());
if (list != NULL) {
Element * element = list;
do {
if (*element->key == key) {
lastElement = element;
lastIndex = P_MAX_INDEX;
return lastElement;
}
element = element->next;
} while (element != list);
}
return NULL;
}
PINDEX PHashTable::Table::GetElementsIndex(
const PObject * obj, BOOL byValue, BOOL keys) const
{
PINDEX index = 0;
for (PINDEX i = 0; i < GetSize(); i++) {
Element * list = operator[](i);
if (list != NULL) {
Element * element = list;
do {
PObject * keydata = keys ? element->key : element->data;
if (byValue ? (*keydata == *obj) : (keydata == obj))
return index;
element = element->next;
index++;
} while (element != list);
}
}
return P_MAX_INDEX;
}
///////////////////////////////////////////////////////////////////////////////
PHashTable::PHashTable()
: hashTable(new PHashTable::Table)
{
PAssert(hashTable != NULL, POutOfMemory);
hashTable->lastElement = NULL;
}
void PHashTable::DestroyContents()
{
if (hashTable != NULL) {
hashTable->reference->deleteObjects = reference->deleteObjects;
delete hashTable;
hashTable = NULL;
}
}
void PHashTable::CopyContents(const PHashTable & hash)
{
hashTable = hash.hashTable;
}
void PHashTable::CloneContents(const PHashTable * hash)
{
PINDEX sz = PAssertNULL(hash)->GetSize();
PHashTable::Table * original = PAssertNULL(hash->hashTable);
hashTable = new PHashTable::Table(original->GetSize());
PAssert(hashTable != NULL, POutOfMemory);
hashTable->lastElement = NULL;
for (PINDEX i = 0; i < sz; i++) {
original->SetLastElementAt(i);
PObject * data = original->lastElement->data;
if (data != NULL)
data = data->Clone();
hashTable->AppendElement(original->lastElement->key->Clone(), data);
}
}
PObject::Comparison PHashTable::Compare(const PObject & obj) const
{
PAssert(PIsDescendant(&obj, PHashTable), PInvalidCast);
return reference != ((const PHashTable &)obj).reference
? GreaterThan : EqualTo;
}
BOOL PHashTable::SetSize(PINDEX)
{
return TRUE;
}
PObject & PHashTable::AbstractGetDataAt(PINDEX index) const
{
PAssert(hashTable->SetLastElementAt(index), PInvalidArrayIndex);
return *hashTable->lastElement->data;
}
const PObject & PHashTable::AbstractGetKeyAt(PINDEX index) const
{
PAssert(hashTable->SetLastElementAt(index), PInvalidArrayIndex);
return *hashTable->lastElement->key;
}
///////////////////////////////////////////////////////////////////////////////
void PAbstractSet::DestroyContents()
{
hashTable->deleteKeys = reference->deleteObjects;
PHashTable::DestroyContents();
}
void PAbstractSet::CopyContents(const PAbstractSet & )
{
}
void PAbstractSet::CloneContents(const PAbstractSet * )
{
}
PINDEX PAbstractSet::Append(PObject * obj)
{
if (AbstractContains(*obj)) {
if (reference->deleteObjects)
delete obj;
return P_MAX_INDEX;
}
reference->size++;
return hashTable->AppendElement(obj, NULL);
}
PINDEX PAbstractSet::Insert(const PObject &, PObject * obj)
{
return Append(obj);
}
PINDEX PAbstractSet::InsertAt(PINDEX, PObject * obj)
{
return Append(obj);
}
BOOL PAbstractSet::Remove(const PObject * obj)
{
if (PAssertNULL(obj) == NULL)
return FALSE;
if (hashTable->GetElementAt(*obj) == NULL)
return FALSE;
hashTable->deleteKeys = hashTable->reference->deleteObjects = reference->deleteObjects;
hashTable->RemoveElement(*obj);
reference->size--;
return TRUE;
}
PObject * PAbstractSet::RemoveAt(PINDEX index)
{
if (!hashTable->SetLastElementAt(index))
return NULL;
PObject * obj = hashTable->lastElement->key;
hashTable->deleteKeys = hashTable->reference->deleteObjects = reference->deleteObjects;
hashTable->RemoveElement(*obj);
reference->size--;
return obj;
}
PINDEX PAbstractSet::GetObjectsIndex(const PObject * obj) const
{
return hashTable->GetElementsIndex(obj, FALSE, TRUE);
}
PINDEX PAbstractSet::GetValuesIndex(const PObject & obj) const
{
return hashTable->GetElementsIndex(&obj, TRUE, TRUE);
}
PObject * PAbstractSet::GetAt(PINDEX index) const
{
return (PObject *)&AbstractGetKeyAt(index);
}
BOOL PAbstractSet::SetAt(PINDEX, PObject * obj)
{
return Append(obj);
}
///////////////////////////////////////////////////////////////////////////////
PINDEX PAbstractDictionary::Append(PObject *)
{
PAssertAlways(PUnimplementedFunction);
return 0;
}
PINDEX PAbstractDictionary::Insert(const PObject & before, PObject * obj)
{
AbstractSetAt(before, obj);
return 0;
}
PINDEX PAbstractDictionary::InsertAt(PINDEX index, PObject * obj)
{
AbstractSetAt(AbstractGetKeyAt(index), obj);
return index;
}
BOOL PAbstractDictionary::Remove(const PObject * obj)
{
PINDEX idx = GetObjectsIndex(obj);
if (idx == P_MAX_INDEX)
return FALSE;
RemoveAt(idx);
return TRUE;
}
PObject * PAbstractDictionary::RemoveAt(PINDEX index)
{
PObject & obj = AbstractGetDataAt(index);
AbstractSetAt(AbstractGetKeyAt(index), NULL);
return &obj;
}
PINDEX PAbstractDictionary::GetObjectsIndex(const PObject * obj) const
{
return hashTable->GetElementsIndex(obj, FALSE, FALSE);
}
PINDEX PAbstractDictionary::GetValuesIndex(const PObject & obj) const
{
return hashTable->GetElementsIndex(&obj, TRUE, FALSE);
}
BOOL PAbstractDictionary::SetAt(PINDEX index, PObject * val)
{
return AbstractSetAt(AbstractGetKeyAt(index), val);
}
PObject * PAbstractDictionary::GetAt(PINDEX index) const
{
PAssert(hashTable->SetLastElementAt(index), PInvalidArrayIndex);
return hashTable->lastElement->data;
}
BOOL PAbstractDictionary::SetDataAt(PINDEX index, PObject * val)
{
return AbstractSetAt(AbstractGetKeyAt(index), val);
}
BOOL PAbstractDictionary::AbstractSetAt(const PObject & key, PObject * obj)
{
if (obj == NULL) {
obj = hashTable->RemoveElement(key);
if (obj != NULL) {
if (reference->deleteObjects)
delete obj;
reference->size--;
}
}
else {
Element * element = hashTable->GetElementAt(key);
if (element == NULL) {
hashTable->AppendElement(key.Clone(), obj);
reference->size++;
}
else {
if ((reference->deleteObjects) && (hashTable->lastElement->data != obj))
delete hashTable->lastElement->data;
hashTable->lastElement->data = obj;
}
}
return TRUE;
}
PObject * PAbstractDictionary::AbstractGetAt(const PObject & key) const
{
Element * element = hashTable->GetElementAt(key);
return element != NULL ? element->data : (PObject *)NULL;
}
PObject & PAbstractDictionary::GetRefAt(const PObject & key) const
{
Element * element = hashTable->GetElementAt(key);
return *PAssertNULL(element)->data;
}
void PAbstractDictionary::PrintOn(ostream &strm) const
{
char separator = strm.fill();
if (separator == ' ')
separator = '\n';
for (PINDEX i = 0; i < GetSize(); i++) {
if (i > 0)
strm << separator;
strm << AbstractGetKeyAt(i) << '=' << AbstractGetDataAt(i);
}
if (separator == '\n')
strm << separator;
}
// End Of File ///////////////////////////////////////////////////////////////
syntax highlighted by Code2HTML, v. 0.9.1