开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 多媒体 > IP电话/视频会议 > 查看源码
collect.cxx
资源名称：pwlib_1.1pl17.zip　[点击查看]
上传用户：hzhsqp
上传日期：2007-01-06
资源大小：1600k
文件大小：38k
源码类别：

IP电话/视频会议

开发平台：

Visual C++

collect.cxx：源码内容
  1. /*
  2.  * collect.cxx
  3.  *
  4.  * Container Classes
  5.  *
  6.  * Portable Windows Library
  7.  *
  8.  * Copyright (c) 1993-1998 Equivalence Pty. Ltd.
  9.  *
  10.  * The contents of this file are subject to the Mozilla Public License
  11.  * Version 1.0 (the "License"); you may not use this file except in
  12.  * compliance with the License. You may obtain a copy of the License at
  13.  * http://www.mozilla.org/MPL/
  14.  *
  15.  * Software distributed under the License is distributed on an "AS IS"
  16.  * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
  17.  * the License for the specific language governing rights and limitations
  18.  * under the License.
  19.  *
  20.  * The Original Code is Portable Windows Library.
  21.  *
  22.  * The Initial Developer of the Original Code is Equivalence Pty. Ltd.
  23.  *
  24.  * Portions are Copyright (C) 1993 Free Software Foundation, Inc.
  25.  * All Rights Reserved.
  26.  *
  27.  * Contributor(s): ______________________________________.
  28.  *
  29.  * $Log: collect.cxx,v $
  30.  * Revision 1.48  1999/08/22 12:54:35  robertj
  31.  * Fixed warnings about inlines on older GNU compiler
  32.  *
  33.  * Revision 1.47  1999/02/16 08:08:06  robertj
  34.  * MSVC 6.0 compatibility changes.
  35.  *
  36.  * Revision 1.46  1998/11/02 12:53:52  robertj
  37.  * Fixed yet another bug in the object array SetSize() for unix systems.
  38.  *
  39.  * Revision 1.45  1998/10/31 14:01:58  robertj
  40.  * Fixed ANSI scoping of for loop variable.
  41.  *
  42.  * Revision 1.44  1998/10/30 10:41:57  robertj
  43.  * Fixed bug cause by previous bug fix in PObjectArray, deleting deleted entries.
  44.  *
  45.  * Revision 1.43  1998/10/28 00:57:43  robertj
  46.  * Fixed memory leak in PObjectArray.
  47.  * Fixed crash when doing GetValuesIndex() on array with NULL elements.
  48.  *
  49.  * Revision 1.42  1998/10/13 14:06:16  robertj
  50.  * Complete rewrite of memory leak detection code.
  51.  *
  52.  * Revision 1.41  1998/09/23 06:21:52  robertj
  53.  * Added open source copyright license.
  54.  *
  55.  * Revision 1.40  1998/09/14 12:32:45  robertj
  56.  * Fixed bug in ordinal dictionary GetAt() and SetAt() for scalar integer types.
  57.  *
  58.  * Revision 1.39  1998/08/20 05:48:51  robertj
  59.  * Fixed bug on removing entries by index from a PSet().
  60.  *
  61.  * Revision 1.38  1998/05/17 02:29:46  robertj
  62.  * Fixed GetObjectsIndex()/GetValuesIndex() finding elements that have a hash clash.
  63.  *
  64.  * Revision 1.37  1998/03/26 23:31:50  robertj
  65.  * Fixed bug in RemoveAll() deleting objects twice.
  66.  *
  67.  * Revision 1.36  1998/03/26 11:19:50  robertj
  68.  * Fix bug with unsigned PINDEX in array SetSize.
  69.  *
  70.  * Revision 1.35  1998/03/25 12:58:41  robertj
  71.  * Fixed memory leak if resize PArray
  72.  *
  73.  * Revision 1.34  1998/03/24 02:58:52  robertj
  74.  * Fixed uninitialised variable in dictionary MakeUnique() function.
  75.  *
  76.  * Revision 1.33  1998/01/26 01:41:19  robertj
  77.  * GNU compatibility.
  78.  *
  79.  * Revision 1.32  1998/01/26 00:36:10  robertj
  80.  * Fixed MakeUnique() function for dictionaries and sets.
  81.  *
  82.  * Revision 1.31  1998/01/06 12:00:15  robertj
  83.  * Fixed "typesafe" templates/macros for dictionaries, especially on GNU.
  84.  *
  85.  * Revision 1.30  1997/12/11 10:30:02  robertj
  86.  * Added type correct Contains() function to dictionaries.
  87.  *
  88.  * Revision 1.29  1997/06/08 04:48:30  robertj
  89.  * Fixed problems in sorted list with multiple identical entries.
  90.  *
  91.  * Revision 1.28  1997/04/27 05:50:14  robertj
  92.  * DLL support.
  93.  *
  94.  * Revision 1.27  1997/02/14 13:59:09  robertj
  95.  * Rewrite of sorted list to use sentinel record rather than NULL pointer.
  96.  *
  97.  * Revision 1.26  1996/08/17 09:55:23  robertj
  98.  * Optimised RemoveAll() for object arrays.
  99.  *
  100.  * Revision 1.25  1996/08/08 10:08:43  robertj
  101.  * Directory structure changes for common files.
  102.  *
  103.  * Revision 1.24  1996/07/15 10:32:52  robertj
  104.  * Fixed bug in sorted list (crash on remove).
  105.  *
  106.  * Revision 1.23  1996/05/26 03:46:24  robertj
  107.  * Compatibility to GNU 2.7.x
  108.  *
  109.  * Revision 1.22  1996/03/26 00:52:38  robertj
  110.  * Fixed bug in dictionary decrementing size when removing element even if already removed.
  111.  *
  112.  * Revision 1.21  1996/02/19 13:32:31  robertj
  113.  * Fixed yet another bug in PSortedList, not setting cache index value correctly.
  114.  *
  115.  * Revision 1.20  1996/02/08 12:24:13  robertj
  116.  * Added default print for dictionaries in form key=datan.
  117.  * Added missing GetAt() function on PSet to be consistent with all others.
  118.  *
  119.  * Revision 1.19  1996/02/03 11:07:59  robertj
  120.  * A bit more bullet proofing of sorted list class.
  121.  *
  122.  * Revision 1.18  1996/01/30 23:30:40  robertj
  123.  * Added optimisation to sorted list GetAt() to use cached element.
  124.  *
  125.  * Revision 1.17  1996/01/28 14:11:45  robertj
  126.  * Fixed bug in sorted list for when getting entry one before last one cached.
  127.  *
  128.  * Revision 1.16  1996/01/28 02:52:45  robertj
  129.  * Added assert into all Compare functions to assure comparison between compatible objects.
  130.  *
  131.  * Revision 1.15  1996/01/23 13:18:29  robertj
  132.  * Fixed bug in sorted list GetObjectsIndex not checking if is same object
  133.  * Fixed bug in sorted list append not returning correct value.
  134.  *
  135.  * Revision 1.14  1995/01/27 11:12:38  robertj
  136.  * Fixed nasty bug in sorted lists.
  137.  *
  138.  * Revision 1.13  1995/01/09  12:31:49  robertj
  139.  * Removed unnecesary return value from I/O functions.
  140.  *
  141.  * Revision 1.12  1994/12/13  11:50:52  robertj
  142.  * Added MakeUnique() function to all container classes.
  143.  *
  144.  * Revision 1.11  1994/12/12  10:16:25  robertj
  145.  * Restructuring and documentation of container classes.
  146.  * Renaming of some macros for declaring container classes.
  147.  * Added some extra functionality to PString.
  148.  * Added start to 2 byte characters in PString.
  149.  * Fixed incorrect overrides in PCaselessString.
  150.  *
  151.  * Revision 1.10  1994/12/05  11:24:58  robertj
  152.  * Fixed bugs in InsertAt and RemoveAt in PObjectArray.
  153.  *
  154.  * Revision 1.9  1994/10/30  11:34:49  robertj
  155.  * Fixed ObjectArray to have pointer to array object pointers.
  156.  *
  157.  * Revision 1.8  1994/10/23  03:41:31  robertj
  158.  * Fixed dictionary functions that should work by index not key.
  159.  *
  160.  * Revision 1.7  1994/09/25  10:49:09  robertj
  161.  * Removed redundent PAssertNULL.
  162.  *
  163.  * Revision 1.6  1994/08/21  23:43:02  robertj
  164.  * Fixed bug in lists when inserting element.
  165.  *
  166.  * Revision 1.5  1994/07/27  05:58:07  robertj
  167.  * Synchronisation.
  168.  *
  169.  * Revision 1.4  1994/07/17  10:46:06  robertj
  170.  * Fixed searching in sorted lists.
  171.  *
  172.  * Revision 1.3  1994/07/02  03:03:49  robertj
  173.  * Added container searching facilities..
  174.  *
  175.  * Revision 1.2  1994/06/25  11:55:15  robertj
  176.  * Unix version synchronisation.
  177.  *
  178. // Revision 1.1  1994/04/20  12:17:44  robertj
  179. // Initial revision
  180. //
  181.  */
  183. #include <ptlib.h>
  185. #define new PNEW
  188. ///////////////////////////////////////////////////////////////////////////////
  190. void PCollection::PrintOn(ostream &strm) const
  191. {
  192.   for (PINDEX  i = 0; i < GetSize(); i++) {
  193.     PObject * obj = GetAt(i);
  194.     if (obj != NULL)
  195.       strm << *obj;
  196.   }
  197. }
  200. void PCollection::RemoveAll()
  201. {
  202.   while (GetSize() > 0)
  203.     RemoveAt(0);
  204. }
  207. ///////////////////////////////////////////////////////////////////////////////
  209. void PArrayObjects::CopyContents(const PArrayObjects & array)
  210. {
  211.   theArray = array.theArray;
  212. }
  215. void PArrayObjects::DestroyContents()
  216. {
  217.   if (reference->deleteObjects) {
  218.     for (PINDEX i = 0; i < theArray->GetSize(); i++) {
  219.       if ((*theArray)[i] != NULL)
  220.         delete (*theArray)[i];
  221.     }
  222.   }
  223.   delete theArray;
  224. }
  227. void PArrayObjects::RemoveAll()
  228. {
  229.   SetSize(0);
  230. }
  233. void PArrayObjects::CloneContents(const PArrayObjects * array)
  234. {
  235.   ObjPtrArray & oldArray = *array->theArray;
  236.   theArray = new ObjPtrArray(oldArray.GetSize());
  237.   for (PINDEX i = 0; i < GetSize(); i++) {
  238.     PObject * ptr = oldArray[i];
  239.     if (ptr != NULL)
  240.       SetAt(i, ptr->Clone());
  241.   }
  242. }
  245. PObject::Comparison PArrayObjects::Compare(const PObject & obj) const
  246. {
  247.   PAssert(obj.IsDescendant(PArrayObjects::Class()), PInvalidCast);
  248.   const PArrayObjects & other = (const PArrayObjects &)obj;
  249.   PINDEX i;
  250.   for (i = 0; i < GetSize(); i++) {
  251.     if (i >= other.GetSize() || *(*theArray)[i] < *(*other.theArray)[i])
  252.       return LessThan;
  253.     if (*(*theArray)[i] > *(*other.theArray)[i])
  254.       return GreaterThan;
  255.   }
  256.   return i < other.GetSize() ? GreaterThan : EqualTo;
  257. }
  260. PINDEX PArrayObjects::GetSize() const
  261. {
  262.   return theArray->GetSize();
  263. }
  266. BOOL PArrayObjects::SetSize(PINDEX newSize)
  267. {
  268.   PINDEX sz = theArray->GetSize();
  269.   if (reference->deleteObjects && sz > 0) {
  270.     for (PINDEX i = sz; i > newSize; i--) {
  271.       PObject * obj = theArray->GetAt(i-1);
  272.       if (obj != NULL)
  273.         delete obj;
  274.     }
  275.   }
  276.   return theArray->SetSize(newSize);
  277. }
  280. PINDEX PArrayObjects::Append(PObject * obj)
  281. {
  282.   PINDEX where = GetSize();
  283.   SetAt(where, obj);
  284.   return where;
  285. }
  288. PINDEX PArrayObjects::Insert(const PObject & before, PObject * obj)
  289. {
  290.   PINDEX where = GetObjectsIndex(&before);
  291.   InsertAt(where, obj);
  292.   return where;
  293. }
  296. BOOL PArrayObjects::Remove(const PObject * obj)
  297. {
  298.   PINDEX i = GetObjectsIndex(obj);
  299.   if (i == P_MAX_INDEX)
  300.     return FALSE;
  301.   RemoveAt(i);
  302.   return TRUE;
  303. }
  306. PObject * PArrayObjects::GetAt(PINDEX index) const
  307. {
  308.   return (*theArray)[index];
  309. }
  312. BOOL PArrayObjects::SetAt(PINDEX index, PObject * obj)
  313. {
  314.   if (!theArray->SetMinSize(index+1))
  315.     return FALSE;
  316.   PObject * oldObj = theArray->GetAt(index);
  317.   if (oldObj != NULL && reference->deleteObjects)
  318.     delete oldObj;
  319.   (*theArray)[index] = obj;
  320.   return TRUE;
  321. }
  324. PINDEX PArrayObjects::InsertAt(PINDEX index, PObject * obj)
  325. {
  326.   for (PINDEX i = GetSize(); i > index; i--)
  327.     (*theArray)[i] = (*theArray)[i-1];
  328.   (*theArray)[index] = obj;
  329.   return index;
  330. }
  333. PObject * PArrayObjects::RemoveAt(PINDEX index)
  334. {
  335.   PObject * obj = (*theArray)[index];
  337.   PINDEX size = GetSize()-1;
  338.   PINDEX i;
  339.   for (i = index; i < size; i++)
  340.     (*theArray)[i] = (*theArray)[i+1];
  341.   (*theArray)[i] = NULL;
  343.   SetSize(size);
  345.   if (obj != NULL && reference->deleteObjects) {
  346.     delete obj;
  347.     obj = NULL;
  348.   }
  350.   return obj;
  351. }
  354. PINDEX PArrayObjects::GetObjectsIndex(const PObject * obj) const
  355. {
  356.   for (PINDEX i = 0; i < GetSize(); i++) {
  357.     if ((*theArray)[i] == obj)
  358.       return i;
  359.   }
  360.   return P_MAX_INDEX;
  361. }
  364. PINDEX PArrayObjects::GetValuesIndex(const PObject & obj) const
  365. {
  366.   for (PINDEX i = 0; i < GetSize(); i++) {
  367.     PObject * elmt = (*theArray)[i];
  368.     if (elmt != NULL && *elmt == obj)
  369.       return i;
  370.   }
  371.   return P_MAX_INDEX;
  372. }
  375. ///////////////////////////////////////////////////////////////////////////////
  377. void PAbstractList::DestroyContents()
  378. {
  379.   RemoveAll();
  380.   delete info;
  381. }
  384. void PAbstractList::CopyContents(const PAbstractList & list)
  385. {
  386.   info = list.info;
  387. }
  390. void PAbstractList::CloneContents(const PAbstractList * list)
  391. {
  392.   Element * element = list->info->head;
  394.   info = new Info;
  395.   PAssertNULL(info);
  397.   while (element != NULL) {
  398.     Append(element->data->Clone());
  399.     element = element->next;
  400.   }
  401. }
  404. PObject::Comparison PAbstractList::Compare(const PObject & obj) const
  405. {
  406.   PAssert(obj.IsDescendant(PAbstractList::Class()), PInvalidCast);
  407.   Element * elmt1 = info->head;
  408.   Element * elmt2 = ((const PAbstractList &)obj).info->head;
  409.   while (elmt1 != NULL && elmt2 != NULL) {
  410.     if (elmt1 == NULL)
  411.       return LessThan;
  412.     if (elmt2 == NULL)
  413.       return GreaterThan;
  414.     if (*elmt1->data < *elmt2->data)
  415.       return LessThan;
  416.     if (*elmt1->data > *elmt2->data)
  417.       return GreaterThan;
  418.     elmt1 = elmt1->next;
  419.     elmt2 = elmt2->next;
  420.   }
  421.   return EqualTo;
  422. }
  425. BOOL PAbstractList::SetSize(PINDEX)
  426. {
  427.   return TRUE;
  428. }
  431. PINDEX PAbstractList::Append(PObject * obj)
  432. {
  433.   Element * element = new Element(PAssertNULL(obj));
  434.   if (info->tail != NULL)
  435.     info->tail->next = element;
  436.   element->prev = info->tail;
  437.   element->next = NULL;
  438.   if (info->head == NULL)
  439.     info->head = element;
  440.   info->tail = element;
  441.   info->lastElement = element;
  442.   info->lastIndex = GetSize();
  443.   reference->size++;
  444.   return info->lastIndex;
  445. }
  448. PINDEX PAbstractList::Insert(const PObject & before, PObject * obj)
  449. {
  450.   PAssertNULL(obj);
  451.   
  452.   PINDEX where = GetObjectsIndex(&before);
  453.   InsertAt(where, obj);
  454.   return where;
  455. }
  458. PINDEX PAbstractList::InsertAt(PINDEX index, PObject * obj)
  459. {
  460.   PAssertNULL(obj);
  462.   if (index >= GetSize())
  463.     return Append(obj);
  465.   PAssert(SetCurrent(index), PInvalidArrayIndex);
  467.   Element * newElement = new Element(obj);
  468.   if (info->lastElement->prev != NULL)
  469.     info->lastElement->prev->next = newElement;
  470.   else
  471.     info->head = newElement;
  472.   newElement->prev = info->lastElement->prev;
  473.   newElement->next = info->lastElement;
  474.   info->lastElement->prev = newElement;
  475.   info->lastElement = newElement;
  476.   info->lastIndex = index;
  477.   reference->size++;
  478.   return index;
  479. }
  482. BOOL PAbstractList::Remove(const PObject * obj)
  483. {
  484.   PINDEX i = GetObjectsIndex(obj);
  485.   if (i == P_MAX_INDEX)
  486.     return FALSE;
  487.   RemoveAt(i);
  488.   return TRUE;
  489. }
  492. PObject * PAbstractList::RemoveAt(PINDEX index)
  493. {
  494.   PAssert(SetCurrent(index), PInvalidArrayIndex);
  496.   Element * elmt = info->lastElement;
  498.   if (elmt->prev != NULL)
  499.     elmt->prev->next = elmt->next;
  500.   else {
  501.     info->head = elmt->next;
  502.     if (info->head != NULL)
  503.       info->head->prev = NULL;
  504.   }
  506.   if (elmt->next != NULL)
  507.     elmt->next->prev = elmt->prev;
  508.   else {
  509.     info->tail = elmt->prev;
  510.     if (info->tail != NULL)
  511.       info->tail->next = NULL;
  512.   }
  514.   if (elmt->next != NULL)
  515.     info->lastElement = elmt->next;
  516.   else {
  517.     info->lastElement = elmt->prev;
  518.     info->lastIndex--;
  519.   }
  520.   reference->size--;
  522.   PObject * obj = elmt->data;
  523.   if (obj != NULL && reference->deleteObjects) {
  524.     delete obj;
  525.     obj = NULL;
  526.   }
  527.   delete elmt;
  528.   return obj;
  529. }
  532. PObject * PAbstractList::GetAt(PINDEX index) const
  533. {
  534.   return SetCurrent(index) ? info->lastElement->data : (PObject *)NULL;
  535. }
  538. BOOL PAbstractList::SetAt(PINDEX index, PObject * val)
  539. {
  540.   if (!SetCurrent(index))
  541.     return FALSE;
  542.   info->lastElement->data = val;
  543.   return TRUE;
  544. }
  547. PINDEX PAbstractList::GetObjectsIndex(const PObject * obj) const
  548. {
  549.   PINDEX index = 0;
  550.   Element * element = info->head;
  551.   while (element != NULL) {
  552.     if (element->data == obj) {
  553.       info->lastElement = element;
  554.       info->lastIndex = index;
  555.       return index;
  556.     }
  557.     element = element->next;
  558.     index++;
  559.   }
  561.   return P_MAX_INDEX;
  562. }
  565. PINDEX PAbstractList::GetValuesIndex(const PObject & obj) const
  566. {
  567.   PINDEX index = 0;
  568.   Element * element = info->head;
  569.   while (element != NULL) {
  570.     if (*element->data == obj) {
  571.       info->lastElement = element;
  572.       info->lastIndex = index;
  573.       return index;
  574.     }
  575.     element = element->next;
  576.     index++;
  577.   }
  579.   return P_MAX_INDEX;
  580. }
  583. BOOL PAbstractList::SetCurrent(PINDEX index) const
  584. {
  585.   if (index >= GetSize())
  586.     return FALSE;
  588.   if (info->lastElement == NULL || info->lastIndex >= GetSize() || 
  589.       index < info->lastIndex/2 || index > (info->lastIndex+GetSize())/2) {
  590.     if (index < GetSize()/2) {
  591.       info->lastIndex = 0;
  592.       info->lastElement = info->head;
  593.     }
  594.     else {
  595.       info->lastIndex = GetSize()-1;
  596.       info->lastElement = info->tail;
  597.     }
  598.   }
  600.   while (info->lastIndex < index) {
  601.     info->lastElement = info->lastElement->next;
  602.     info->lastIndex++;
  603.   }
  605.   while (info->lastIndex > index) {
  606.     info->lastElement = info->lastElement->prev;
  607.     info->lastIndex--;
  608.   }
  610.   return TRUE;
  611. }
  614. PAbstractList::Element::Element(PObject * theData)
  615. {
  616.   next = prev = NULL;
  617.   data = theData;
  618. }
  621. ///////////////////////////////////////////////////////////////////////////////
  623. PAbstractSortedList::Element nil = NULL;
  625. PAbstractSortedList::PAbstractSortedList()
  626. {
  627.   info = new Info;
  628.   PAssert(info != NULL, POutOfMemory);
  629. }
  632. void PAbstractSortedList::DestroyContents()
  633. {
  634.   RemoveAll();
  635.   delete info;
  636. }
  639. void PAbstractSortedList::CopyContents(const PAbstractSortedList & list)
  640. {
  641.   info = list.info;
  642. }
  645. void PAbstractSortedList::CloneContents(const PAbstractSortedList * list)
  646. {
  647.   Element * element = list->info->root;
  648.   while (element->left != &nil)
  649.     element = element->left;
  651.   info = new Info;
  652.   PAssertNULL(info);
  654.   while (element != &nil) {
  655.     Append(element->data->Clone());
  656.     element = element->Successor();
  657.   }
  658. }
  661. BOOL PAbstractSortedList::SetSize(PINDEX)
  662. {
  663.   return TRUE;
  664. }
  667. PObject::Comparison PAbstractSortedList::Compare(const PObject & obj) const
  668. {
  669.   PAssert(obj.IsDescendant(PAbstractSortedList::Class()), PInvalidCast);
  670.   Element * elmt1 = info->root;
  671.   while (elmt1->left != &nil)
  672.     elmt1 = elmt1->left;
  674.   Element * elmt2 = ((const PAbstractSortedList &)obj).info->root;
  675.   while (elmt2->left != &nil)
  676.     elmt2 = elmt2->left;
  678.   while (elmt1 != &nil && elmt2 != &nil) {
  679.     if (elmt1 == &nil)
  680.       return LessThan;
  681.     if (elmt2 == &nil)
  682.       return GreaterThan;
  683.     if (*elmt1->data < *elmt2->data)
  684.       return LessThan;
  685.     if (*elmt1->data > *elmt2->data)
  686.       return GreaterThan;
  687.     elmt1 = elmt1->Successor();
  688.     elmt2 = elmt2->Successor();
  689.   }
  690.   return EqualTo;
  691. }
  694. PINDEX PAbstractSortedList::Append(PObject * obj)
  695. {
  696.   Element * z = new Element(PAssertNULL(obj));
  697.   Element * x = info->root;
  698.   Element * y = &nil;
  699.   while (x != &nil) {
  700.     x->subTreeSize++;
  701.     y = x;
  702.     x = *z->data < *x->data ? x->left : x->right;
  703.   }
  704.   z->parent = y;
  705.   if (y == &nil)
  706.     info->root = z;
  707.   else if (*z->data < *y->data)
  708.     y->left = z;
  709.   else
  710.     y->right = z;
  712.   info->lastElement = x = z;
  714.   x->colour = Element::Red;
  715.   while (x != info->root && x->parent->colour == Element::Red) {
  716.     if (x->parent == x->parent->parent->left) {
  717.       y = x->parent->parent->right;
  718.       if (y->colour == Element::Red) {
  719.         x->parent->colour = Element::Black;
  720.         y->colour = Element::Black;
  721.         x->parent->parent->colour = Element::Red;
  722.         x = x->parent->parent;
  723.       }
  724.       else {
  725.         if (x == x->parent->right) {
  726.           x = x->parent;
  727.           LeftRotate(x);
  728.         }
  729.         x->parent->colour = Element::Black;
  730.         x->parent->parent->colour = Element::Red;
  731.         RightRotate(x->parent->parent);
  732.       }
  733.     }
  734.     else {
  735.       y = x->parent->parent->left;
  736.       if (y->colour == Element::Red) {
  737.         x->parent->colour = Element::Black;
  738.         y->colour = Element::Black;
  739.         x->parent->parent->colour = Element::Red;
  740.         x = x->parent->parent;
  741.       }
  742.       else {
  743.         if (x == x->parent->left) {
  744.           x = x->parent;
  745.           RightRotate(x);
  746.         }
  747.         x->parent->colour = Element::Black;
  748.         x->parent->parent->colour = Element::Red;
  749.         LeftRotate(x->parent->parent);
  750.       }
  751.     }
  752.   }
  754.   info->root->colour = Element::Black;
  756.   x = info->lastElement;
  757.   info->lastIndex = x->left->subTreeSize;
  758.   while (x != info->root) {
  759.     if (x != x->parent->left)
  760.       info->lastIndex += x->parent->left->subTreeSize+1;
  761.     x = x->parent;
  762.   }
  764.   reference->size++;
  765.   return info->lastIndex;
  766. }
  769. BOOL PAbstractSortedList::Remove(const PObject * obj)
  770. {
  771.   Element * element = info->root;
  772.   while (element != &nil && element->data != obj)
  773.     element = *obj < *element->data ? element->left : element->right;
  774.   if (element == &nil)
  775.     return FALSE;
  777.   RemoveElement(element);
  778.   return TRUE;
  779. }
  782. PObject * PAbstractSortedList::RemoveAt(PINDEX index)
  783. {
  784.   Element * node = info->root->OrderSelect(index+1);
  785.   PObject * data = node->data;
  786.   RemoveElement(node);
  787.   return reference->deleteObjects ? (PObject *)NULL : data;
  788. }
  791. void PAbstractSortedList::RemoveAll()
  792. {
  793.   if (info->root != &nil) {
  794.     info->root->DeleteSubTrees(reference->deleteObjects);
  795.     delete info->root;
  796.     info->root = &nil;
  797.     reference->size = 0;
  798.   }
  799. }
  802. PINDEX PAbstractSortedList::Insert(const PObject &, PObject * obj)
  803. {
  804.   return Append(obj);
  805. }
  808. PINDEX PAbstractSortedList::InsertAt(PINDEX, PObject * obj)
  809. {
  810.   return Append(obj);
  811. }
  814. BOOL PAbstractSortedList::SetAt(PINDEX, PObject *)
  815. {
  816.   return FALSE;
  817. }
  820. PObject * PAbstractSortedList::GetAt(PINDEX index) const
  821. {
  822.   if (index >= GetSize())
  823.     return NULL;
  825.   if (index != info->lastIndex) {
  826.     if (index == info->lastIndex-1) {
  827.       info->lastIndex--;
  828.       info->lastElement = info->lastElement->Predecessor();
  829.     }
  830.     else if (index == info->lastIndex+1 && info->lastElement != NULL) {
  831.       info->lastIndex++;
  832.       info->lastElement = info->lastElement->Successor();
  833.     }
  834.     else {
  835.       info->lastIndex = index;
  836.       info->lastElement = info->root->OrderSelect(index+1);
  837.     }
  838.   }
  840.   return PAssertNULL(info->lastElement)->data;
  841. }
  844. PINDEX PAbstractSortedList::GetObjectsIndex(const PObject * obj) const
  845. {
  846.   Element * elmt = NULL;
  847.   PINDEX pos = info->root->ValueSelect(*obj, elmt);
  848.   if (pos == P_MAX_INDEX)
  849.     return P_MAX_INDEX;
  851.   if (elmt->data != obj) {
  852.     PINDEX savePos = pos;
  853.     Element * saveElmt = elmt;
  854.     while (elmt->data != obj &&
  855.             (elmt = elmt->Predecessor()) != &nil &&
  856.             *obj == *elmt->data)
  857.       pos--;
  858.     if (elmt->data != obj) {
  859.       pos = savePos;
  860.       elmt = saveElmt;
  861.       while (elmt->data != obj &&
  862.               (elmt = elmt->Successor()) != &nil &&
  863.               *obj == *elmt->data)
  864.         pos++;
  865.       if (elmt->data != obj)
  866.         return P_MAX_INDEX;
  867.     }
  868.   }
  870.   info->lastIndex = pos;
  871.   info->lastElement = elmt;
  873.   return pos;
  874. }
  877. PINDEX PAbstractSortedList::GetValuesIndex(const PObject & obj) const
  878. {
  879.   PINDEX pos = info->root->ValueSelect(obj, info->lastElement);
  880.   if (pos == P_MAX_INDEX)
  881.     return P_MAX_INDEX;
  883.   info->lastIndex = pos;
  885.   Element * prev;
  886.   while ((prev = info->lastElement->Predecessor()) != &nil && obj == *prev->data) {
  887.     info->lastElement = prev;
  888.     info->lastIndex--;
  889.   }
  891.   return info->lastIndex;
  892. }
  895. void PAbstractSortedList::RemoveElement(Element * node)
  896. {
  897.   PAssertNULL(node);
  899.   if (node->data != NULL && reference->deleteObjects)
  900.     delete node->data;
  902.   Element * y = node->left == &nil || node->right == &nil ? node : node->Successor();
  904.   Element * t = y;
  905.   while (t != &nil) {
  906.     t->subTreeSize--;
  907.     t = t->parent;
  908.   }
  910.   Element * x = y->left != &nil ? y->left : y->right;
  911.   x->parent = y->parent;
  913.   if (y->parent == &nil)
  914.     info->root = x;
  915.   else if (y == y->parent->left)
  916.     y->parent->left = x;
  917.   else
  918.     y->parent->right = x;
  920.   if (y != node)
  921.     node->data = y->data;
  923.   if (y->colour == Element::Black) {
  924.     while (x != info->root && x->colour == Element::Black) {
  925.       if (x == x->parent->left) {
  926.         Element * w = x->parent->right;
  927.         if (w->colour == Element::Red) {
  928.           w->colour = Element::Black;
  929.           x->parent->colour = Element::Red;
  930.           LeftRotate(x->parent);
  931.           w = x->parent->right;
  932.         }
  933.         if (w->left->colour == Element::Black && w->right->colour == Element::Black) {
  934.           w->colour = Element::Red;
  935.           x = x->parent;
  936.         }
  937.         else {
  938.           if (w->right->colour == Element::Black) {
  939.             w->left->colour = Element::Black;
  940.             w->colour = Element::Red;
  941.             RightRotate(w);
  942.             w = x->parent->right;
  943.           }
  944.           w->colour = x->parent->colour;
  945.           x->parent->colour = Element::Black;
  946.           w->right->colour = Element::Black;
  947.           LeftRotate(x->parent);
  948.           x = info->root;
  949.         }
  950.       }
  951.       else {
  952.         Element * w = x->parent->left;
  953.         if (w->colour == Element::Red) {
  954.           w->colour = Element::Black;
  955.           x->parent->colour = Element::Red;
  956.           RightRotate(x->parent);
  957.           w = x->parent->left;
  958.         }
  959.         if (w->right->colour == Element::Black && w->left->colour == Element::Black) {
  960.           w->colour = Element::Red;
  961.           x = x->parent;
  962.         }
  963.         else {
  964.           if (w->left->colour == Element::Black) {
  965.             w->right->colour = Element::Black;
  966.             w->colour = Element::Red;
  967.             LeftRotate(w);
  968.             w = x->parent->left;
  969.           }
  970.           w->colour = x->parent->colour;
  971.           x->parent->colour = Element::Black;
  972.           w->left->colour = Element::Black;
  973.           RightRotate(x->parent);
  974.           x = info->root;
  975.         }
  976.       }
  977.     }
  978.     x->colour = Element::Black;
  979.   }
  981.   delete y;
  983.   reference->size--;
  984.   info->lastIndex = P_MAX_INDEX;
  985.   info->lastElement = NULL;
  986. }
  989. void PAbstractSortedList::LeftRotate(Element * node)
  990. {
  991.   Element * pivot = PAssertNULL(node)->right;
  992.   node->right = pivot->left;
  993.   if (pivot->left != &nil)
  994.     pivot->left->parent = node;
  995.   pivot->parent = node->parent;
  996.   if (node->parent == &nil)
  997.     info->root = pivot;
  998.   else if (node == node->parent->left)
  999.     node->parent->left = pivot;
  1000.   else
  1001.     node->parent->right = pivot;
  1002.   pivot->left = node;
  1003.   node->parent = pivot;
  1004.   pivot->subTreeSize = node->subTreeSize;
  1005.   node->subTreeSize = node->left->subTreeSize + node->right->subTreeSize + 1;
  1006. }
  1009. void PAbstractSortedList::RightRotate(Element * node)
  1010. {
  1011.   Element * pivot = PAssertNULL(node)->left;
  1012.   node->left = pivot->right;
  1013.   if (pivot->right != &nil)
  1014.     pivot->right->parent = node;
  1015.   pivot->parent = node->parent;
  1016.   if (node->parent == &nil)
  1017.     info->root = pivot;
  1018.   else if (node == node->parent->right)
  1019.     node->parent->right = pivot;
  1020.   else
  1021.     node->parent->left = pivot;
  1022.   pivot->right = node;
  1023.   node->parent = pivot;
  1024.   pivot->subTreeSize = node->subTreeSize;
  1025.   node->subTreeSize = node->left->subTreeSize + node->right->subTreeSize + 1;
  1026. }
  1029. PAbstractSortedList::Element::Element(PObject * theData)
  1030. {
  1031.   parent = left = right = &nil;
  1032.   colour = Black;
  1033.   subTreeSize = theData != NULL ? 1 : 0;
  1034.   data = theData;
  1035. }
  1038. PAbstractSortedList::Element * PAbstractSortedList::Element::Successor() const
  1039. {
  1040.   Element * next;
  1041.   if (right != &nil) {
  1042.     next = right;
  1043.     while (next->left != &nil)
  1044.       next = next->left;
  1045.   }
  1046.   else {
  1047.     next = parent;
  1048.     const Element * node = this;
  1049.     while (next != &nil && node == next->right) {
  1050.       node = next;
  1051.       next = node->parent;
  1052.     }
  1053.   }
  1054.   return next;
  1055. }
  1058. PAbstractSortedList::Element*PAbstractSortedList::Element::Predecessor() const
  1059. {
  1060.   Element * pred;
  1061.   if (left != &nil) {
  1062.     pred = left;
  1063.     while (pred->right != &nil)
  1064.       pred = pred->right;
  1065.   }
  1066.   else {
  1067.     pred = parent;
  1068.     const Element * node = this;
  1069.     while (pred != &nil && node == pred->left) {
  1070.       node = pred;
  1071.       pred = node->parent;
  1072.     }
  1073.   }
  1074.   return pred;
  1075. }
  1078. PAbstractSortedList::Element * PAbstractSortedList::Element::OrderSelect(PINDEX index)
  1079. {
  1080.   PINDEX r = left->subTreeSize+1;
  1081.   if (index == r)
  1082.     return this;
  1084.   if (index < r) {
  1085.     if (left != &nil)
  1086.       return left->OrderSelect(index);
  1087.   }
  1088.   else {
  1089.     if (right != &nil)
  1090.       return right->OrderSelect(index - r);
  1091.   }
  1093.   PAssertAlways("Order select failed!");
  1094.   return &nil;
  1095. }
  1098. PINDEX PAbstractSortedList::Element::ValueSelect(const PObject & obj,
  1099.                                                  Element * & lastElement)
  1100. {
  1101.   if (this != &nil) {
  1102.     switch (data->Compare(obj)) {
  1103.       case PObject::LessThan :
  1104.       {
  1105.         PINDEX index = right->ValueSelect(obj, lastElement);
  1106.         if (index != P_MAX_INDEX)
  1107.           return left->subTreeSize + index + 1;
  1108.         break;
  1109.       }
  1111.       case PObject::GreaterThan :
  1112.         return left->ValueSelect(obj, lastElement);
  1114.       default :
  1115.         lastElement = this;
  1116.         return left->subTreeSize;
  1117.     }
  1118.   }
  1120.   return P_MAX_INDEX;
  1121. }
  1124. void PAbstractSortedList::Element::DeleteSubTrees(BOOL deleteObject)
  1125. {
  1126.   if (left != &nil) {
  1127.     left->DeleteSubTrees(deleteObject);
  1128.     delete left;
  1129.     left = &nil;
  1130.   }
  1131.   if (right != &nil) {
  1132.     right->DeleteSubTrees(deleteObject);
  1133.     delete right;
  1134.     right = &nil;
  1135.   }
  1136.   if (deleteObject) {
  1137.     delete data;
  1138.     data = NULL;
  1139.   }
  1140. }
  1143. PAbstractSortedList::Info::Info()
  1144. {
  1145.   root = &nil;
  1146.   lastElement = NULL;
  1147.   lastIndex = P_MAX_INDEX;
  1148. }
  1151. ///////////////////////////////////////////////////////////////////////////////
  1153. PObject * POrdinalKey::Clone() const
  1154. {
  1155.   return new POrdinalKey(theKey);
  1156. }
  1159. PObject::Comparison POrdinalKey::Compare(const PObject & obj) const
  1160. {
  1161.   PAssert(obj.IsDescendant(POrdinalKey::Class()), PInvalidCast);
  1162.   const POrdinalKey & other = (const POrdinalKey &)obj;
  1163.   
  1164.   if (theKey < other.theKey)
  1165.     return LessThan;
  1167.   if (theKey > other.theKey)
  1168.     return GreaterThan;
  1170.   return EqualTo;
  1171. }
  1174. PINDEX POrdinalKey::HashFunction() const
  1175. {
  1176.   return PABSINDEX(theKey)%23;
  1177. }
  1180. void POrdinalKey::PrintOn(ostream & strm) const
  1181. {
  1182.   strm << theKey;
  1183. }
  1186. ///////////////////////////////////////////////////////////////////////////////
  1188. void PHashTable::Table::DestroyContents()
  1189. {
  1190.   for (PINDEX i = 0; i < GetSize(); i++) {
  1191.     Element * list = GetAt(i);
  1192.     if (list != NULL) {
  1193.       Element * elmt = list;
  1194.       do {
  1195.         Element * nextElmt = elmt->next;
  1196.         if (elmt->data != NULL && reference->deleteObjects)
  1197.           delete elmt->data;
  1198.         if (deleteKeys)
  1199.           delete elmt->key;
  1200.         delete elmt;
  1201.         elmt = nextElmt;
  1202.       } while (elmt != list);
  1203.     }
  1204.   }
  1205.   PAbstractArray::DestroyContents();
  1206. }
  1209. PINDEX PHashTable::Table::AppendElement(PObject * key, PObject * data)
  1210. {
  1211.   lastElement = NULL;
  1213.   PINDEX bucket = PAssertNULL(key)->HashFunction();
  1214.   Element * list = GetAt(bucket);
  1215.   Element * element = new Element;
  1216.   PAssertNULL(element);
  1217.   element->key = key;
  1218.   element->data = data;
  1219.   if (list == NULL) {
  1220.     element->next = element->prev = element;
  1221.     SetAt(bucket, element);
  1222.   }
  1223.   else if (list == list->prev) {
  1224.     list->next = list->prev = element;
  1225.     element->next = element->prev = list;
  1226.   }
  1227.   else {
  1228.     element->next = list;
  1229.     element->prev = list->prev;
  1230.     list->prev->next = element;
  1231.     list->prev = element;
  1232.   }
  1233.   lastElement = element;
  1234.   lastIndex = P_MAX_INDEX;
  1235.   return bucket;
  1236. }
  1239. PObject * PHashTable::Table::RemoveElement(const PObject & key)
  1240. {
  1241.   PObject * obj = NULL;
  1242.   if (GetElementAt(key) != NULL) {
  1243.     if (lastElement == lastElement->prev)
  1244.       SetAt(key.HashFunction(), NULL);
  1245.     else {
  1246.       lastElement->prev->next = lastElement->next;
  1247.       lastElement->next->prev = lastElement->prev;
  1248.       SetAt(key.HashFunction(), lastElement->next);
  1249.     }
  1250.     obj = lastElement->data;
  1251.     if (deleteKeys)
  1252.       delete lastElement->key;
  1253.     delete lastElement;
  1254.     lastElement = NULL;
  1255.   }
  1256.   return obj;
  1257. }
  1260. BOOL PHashTable::Table::SetLastElementAt(PINDEX index)
  1261. {
  1262.   if (index == 0 || lastElement == NULL || lastIndex == P_MAX_INDEX) {
  1263.     lastIndex = 0;
  1264.     lastBucket = 0;
  1265.     while ((lastElement = GetAt(lastBucket)) == NULL) {
  1266.       if (lastBucket >= GetSize())
  1267.         return FALSE;
  1268.       lastBucket++;
  1269.     }
  1270.   }
  1272.   if (lastIndex == index)
  1273.     return TRUE;
  1275.   if (lastIndex < index) {
  1276.     while (lastIndex != index) {
  1277.       if (lastElement->next != operator[](lastBucket))
  1278.         lastElement = lastElement->next;
  1279.       else {
  1280.         do {
  1281.           if (++lastBucket >= GetSize())
  1282.             return FALSE;
  1283.         } while ((lastElement = operator[](lastBucket)) == NULL);
  1284.       }
  1285.       lastIndex++;
  1286.     }
  1287.   }
  1288.   else {
  1289.     while (lastIndex != index) {
  1290.       if (lastElement != operator[](lastBucket))
  1291.         lastElement = lastElement->prev;
  1292.       else {
  1293.         do {
  1294.           if (lastBucket-- == 0)
  1295.             return FALSE;
  1296.         } while ((lastElement = operator[](lastBucket)) == NULL);
  1297.         lastElement = lastElement->prev;
  1298.       }
  1299.       lastIndex--;
  1300.     }
  1301.   }
  1303.   return TRUE;
  1304. }
  1307. PHashTable::Element * PHashTable::Table::GetElementAt(const PObject & key)
  1308. {
  1309.   if (lastElement != NULL && *lastElement->key == key)
  1310.     return lastElement;
  1312.   Element * list = GetAt(key.HashFunction());
  1313.   if (list != NULL) {
  1314.     Element * element = list;
  1315.     do {
  1316.       if (*element->key == key) {
  1317.         lastElement = element;
  1318.         lastIndex = P_MAX_INDEX;
  1319.         return lastElement;
  1320.       }
  1321.       element = element->next;
  1322.     } while (element != list);
  1323.   }
  1324.   return NULL;
  1325. }
  1328. PINDEX PHashTable::Table::GetElementsIndex(
  1329.                            const PObject * obj, BOOL byValue, BOOL keys) const
  1330. {
  1331.   PINDEX index = 0;
  1332.   for (PINDEX i = 0; i < GetSize(); i++) {
  1333.     Element * list = operator[](i);
  1334.     if (list != NULL) {
  1335.       Element * element = list;
  1336.       do {
  1337.         PObject * keydata = keys ? element->key : element->data;
  1338.         if (byValue ? (*keydata == *obj) : (keydata == obj))
  1339.           return index;
  1340.         element = element->next;
  1341.         index++;
  1342.       } while (element != list);
  1343.     }
  1344.   }
  1345.   return P_MAX_INDEX;
  1346. }
  1349. ///////////////////////////////////////////////////////////////////////////////
  1351. PHashTable::PHashTable()
  1352.   : hashTable(new PHashTable::Table)
  1353. {
  1354.   PAssertNULL(hashTable);
  1355.   hashTable->lastElement = NULL;
  1356. }
  1359. void PHashTable::DestroyContents()
  1360. {
  1361.   hashTable->reference->deleteObjects = reference->deleteObjects;
  1362.   delete hashTable;
  1363. }
  1366. void PHashTable::CopyContents(const PHashTable & hash)
  1367. {
  1368.   hashTable = hash.hashTable;
  1369. }
  1371.   
  1372. void PHashTable::CloneContents(const PHashTable * hash)
  1373. {
  1374.   PAssertNULL(hash);
  1375.   PINDEX sz = hash->GetSize();
  1376.   PAssertNULL(hash->hashTable);
  1377.   PHashTable::Table * original = hash->hashTable;
  1379.   hashTable = new PHashTable::Table(original->GetSize());
  1380.   PAssertNULL(hashTable);
  1381.   hashTable->lastElement = NULL;
  1383.   for (PINDEX i = 0; i < sz; i++) {
  1384.     original->SetLastElementAt(i);
  1385.     PObject * data = original->lastElement->data;
  1386.     if (data != NULL)
  1387.       data = data->Clone();
  1388.     hashTable->AppendElement(original->lastElement->key->Clone(), data);
  1389.   }
  1390. }
  1393. PObject::Comparison PHashTable::Compare(const PObject & obj) const
  1394. {
  1395.   PAssert(obj.IsDescendant(PHashTable::Class()), PInvalidCast);
  1396.   return reference != ((const PHashTable &)obj).reference
  1397.                                                       ? GreaterThan : EqualTo;
  1398. }
  1401. BOOL PHashTable::SetSize(PINDEX)
  1402. {
  1403.   return TRUE;
  1404. }
  1407. PObject & PHashTable::AbstractGetDataAt(PINDEX index) const
  1408. {
  1409.   PAssert(hashTable->SetLastElementAt(index), PInvalidArrayIndex);
  1410.   return *hashTable->lastElement->data;
  1411. }
  1414. const PObject & PHashTable::AbstractGetKeyAt(PINDEX index) const
  1415. {
  1416.   PAssert(hashTable->SetLastElementAt(index), PInvalidArrayIndex);
  1417.   return *hashTable->lastElement->key;
  1418. }
  1421. ///////////////////////////////////////////////////////////////////////////////
  1423. void PAbstractSet::DestroyContents()
  1424. {
  1425.   hashTable->deleteKeys = reference->deleteObjects;
  1426.   PHashTable::DestroyContents();
  1427. }
  1430. void PAbstractSet::CopyContents(const PAbstractSet & )
  1431. {
  1432. }
  1434.   
  1435. void PAbstractSet::CloneContents(const PAbstractSet * )
  1436. {
  1437. }
  1440. PINDEX PAbstractSet::Append(PObject * obj)
  1441. {
  1442.   if (AbstractContains(*obj)) {
  1443.     if (reference->deleteObjects)
  1444.       delete obj;
  1445.     return P_MAX_INDEX;
  1446.   }
  1448.   reference->size++;
  1449.   return hashTable->AppendElement(obj, NULL);
  1450. }
  1453. PINDEX PAbstractSet::Insert(const PObject &, PObject * obj)
  1454. {
  1455.   return Append(obj);
  1456. }
  1459. PINDEX PAbstractSet::InsertAt(PINDEX, PObject * obj)
  1460. {
  1461.   return Append(obj);
  1462. }
  1465. BOOL PAbstractSet::Remove(const PObject * obj)
  1466. {
  1467.   if (hashTable->GetElementAt(*PAssertNULL(obj)) == NULL)
  1468.     return FALSE;
  1470.   hashTable->deleteKeys = hashTable->reference->deleteObjects = reference->deleteObjects;
  1471.   hashTable->RemoveElement(*obj);
  1472.   reference->size--;
  1473.   return TRUE;
  1474. }
  1477. PObject * PAbstractSet::RemoveAt(PINDEX index)
  1478. {
  1479.   if (!hashTable->SetLastElementAt(index))
  1480.     return NULL;
  1482.   PObject * obj = hashTable->lastElement->key;
  1483.   hashTable->deleteKeys = hashTable->reference->deleteObjects = reference->deleteObjects;
  1484.   hashTable->RemoveElement(*obj);
  1485.   reference->size--;
  1486.   return obj;
  1487. }
  1490. PINDEX PAbstractSet::GetObjectsIndex(const PObject * obj) const
  1491. {
  1492.   return hashTable->GetElementsIndex(obj, FALSE, TRUE);
  1493. }
  1496. PINDEX PAbstractSet::GetValuesIndex(const PObject & obj) const
  1497. {
  1498.   return hashTable->GetElementsIndex(&obj, TRUE, TRUE);
  1499. }
  1502. PObject * PAbstractSet::GetAt(PINDEX index) const
  1503. {
  1504.   return (PObject *)&AbstractGetKeyAt(index);
  1505. }
  1508. BOOL PAbstractSet::SetAt(PINDEX, PObject * obj)
  1509. {
  1510.   return Append(obj);
  1511. }
  1514. ///////////////////////////////////////////////////////////////////////////////
  1516. PINDEX PAbstractDictionary::Append(PObject *)
  1517. {
  1518.   PAssertAlways(PUnimplementedFunction);
  1519.   return 0;
  1520. }
  1523. PINDEX PAbstractDictionary::Insert(const PObject & before, PObject * obj)
  1524. {
  1525.   AbstractSetAt(before, obj);
  1526.   return 0;
  1527. }
  1530. PINDEX PAbstractDictionary::InsertAt(PINDEX index, PObject * obj)
  1531. {
  1532.   AbstractSetAt(AbstractGetKeyAt(index), obj);
  1533.   return index;
  1534. }
  1535.  
  1536.  
  1537. BOOL PAbstractDictionary::Remove(const PObject *)
  1538. {
  1539.   PAssertAlways(PUnimplementedFunction);
  1540.   return FALSE;
  1541. }
  1544. PObject * PAbstractDictionary::RemoveAt(PINDEX index)
  1545. {
  1546.   PObject & obj = AbstractGetDataAt(index);
  1547.   AbstractSetAt(AbstractGetKeyAt(index), NULL);
  1548.   return &obj;
  1549. }
  1552. PINDEX PAbstractDictionary::GetObjectsIndex(const PObject * obj) const
  1553. {
  1554.   return hashTable->GetElementsIndex(obj, FALSE, FALSE);
  1555. }
  1558. PINDEX PAbstractDictionary::GetValuesIndex(const PObject & obj) const
  1559. {
  1560.   return hashTable->GetElementsIndex(&obj, TRUE, FALSE);
  1561. }
  1564. BOOL PAbstractDictionary::SetAt(PINDEX index, PObject * val)
  1565. {
  1566.   return AbstractSetAt(POrdinalKey(index), val);
  1567. }
  1570. PObject * PAbstractDictionary::GetAt(PINDEX index) const
  1571. {
  1572.   return AbstractGetAt(POrdinalKey(index));
  1573. }
  1574.  
  1575.  
  1576. BOOL PAbstractDictionary::SetDataAt(PINDEX index, PObject * val)
  1577. {
  1578.   return AbstractSetAt(AbstractGetKeyAt(index), val);
  1579. }
  1582. BOOL PAbstractDictionary::AbstractSetAt(const PObject & key, PObject * obj)
  1583. {
  1584.   if (obj == NULL) {
  1585.     obj = hashTable->RemoveElement(key);
  1586.     if (obj != NULL) {
  1587.       if (reference->deleteObjects)
  1588.         delete obj;
  1589.       reference->size--;
  1590.     }
  1591.   }
  1592.   else {
  1593.     Element * element = hashTable->GetElementAt(key);
  1594.     if (element == NULL) {
  1595.       hashTable->AppendElement(key.Clone(), obj);
  1596.       reference->size++;
  1597.     }
  1598.     else {
  1599.       if (reference->deleteObjects)
  1600.         delete hashTable->lastElement->data;
  1601.       hashTable->lastElement->data = obj;
  1602.     }
  1603.   }
  1604.   return TRUE;
  1605. }
  1608. PObject * PAbstractDictionary::AbstractGetAt(const PObject & key) const
  1609. {
  1610.   Element * element = hashTable->GetElementAt(key);
  1611.   return element != NULL ? element->data : (PObject *)NULL;
  1612. }
  1615. PObject & PAbstractDictionary::GetRefAt(const PObject & key) const
  1616. {
  1617.   Element * element = hashTable->GetElementAt(key);
  1618.   return *PAssertNULL(element)->data;
  1619. }
  1622. void PAbstractDictionary::PrintOn(ostream &strm) const
  1623. {
  1624.   for (PINDEX  i = 0; i < GetSize(); i++)
  1625.     strm << AbstractGetKeyAt(i) << '=' << AbstractGetDataAt(i) << endl;
  1626. }
  1629. // End Of File ///////////////////////////////////////////////////////////////