lists.h
Go to the documentation of this file.
/*
* lists.h
*
* List 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): ______________________________________.
*
* $Revision: 24177 $
* $Author: rjongbloed $
* $Date: 2010-04-05 06:52:04 -0500 (Mon, 05 Apr 2010) $
*/
#ifndef PTLIB_LISTS_H
#define PTLIB_LISTS_H
#ifdef P_USE_PRAGMA
#pragma interface
#endif
// PList container class
struct PListElement
{
PListElement(PObject * theData);
PListElement * prev;
PListElement * next;
PObject * data;
PDECLARE_POOL_ALLOCATOR();
};
struct PListInfo
{
PListInfo() { head = tail = NULL; }
PListElement * head;
PListElement * tail;
PDECLARE_POOL_ALLOCATOR();
};
class PAbstractList : public PCollection
{
PCONTAINERINFO(PAbstractList, PCollection);
public:
PINLINE PAbstractList();
// Overrides from class PObject
virtual Comparison Compare(
const PObject & obj
) const;
virtual PBoolean SetSize(
PINDEX newSize
);
virtual PINDEX Append(
PObject * obj
);
virtual PINDEX Insert(
const PObject & before,
PObject * obj
);
virtual PINDEX InsertAt(
PINDEX index,
PObject * obj
);
virtual PBoolean Remove(
const PObject * obj
);
virtual PObject * RemoveAt(
PINDEX index
);
virtual PBoolean SetAt(
PINDEX index,
PObject * val
);
virtual PBoolean ReplaceAt(
PINDEX index,
PObject * val
);
virtual PObject * GetAt(
PINDEX index
) const;
virtual PINDEX GetObjectsIndex(
const PObject * obj
) const;
virtual PINDEX GetValuesIndex(
const PObject & obj
) const;
protected:
PINLINE PObject & GetReferenceAt(
PINDEX index
) const;
PBoolean SetCurrent(
PINDEX index,
PListElement * & lastElement
) const;
PObject * RemoveElement(PListElement * element);
// The types below cannot be nested as DevStudio 2005 AUTOEXP.DAT doesn't like it
typedef PListElement Element;
PListInfo * info;
};
template <class T> class PList : public PAbstractList
{
PCLASSINFO(PList, PAbstractList);
public:
PList()
: PAbstractList() { }
virtual PObject * Clone() const
{ return PNEW PList(0, this); }
class iterator_base : public std::iterator<std::bidirectional_iterator_tag, T> {
protected:
iterator_base(PListElement * e) : element(e) { }
PListElement * element;
void Next() { element = PAssertNULL(element)->next; }
void Prev() { element = PAssertNULL(element)->prev; }
T * Ptr() const { return (T *)PAssertNULL(element)->data; }
public:
bool operator==(const iterator_base & it) const { return element == it.element; }
bool operator!=(const iterator_base & it) const { return element != it.element; }
};
class iterator : public iterator_base {
public:
iterator(PListElement * e = NULL) : iterator_base(e) { }
iterator operator++() { iterator_base::Next(); return *this; }
iterator operator--() { iterator_base::Prev(); return *this; }
iterator operator++(int) { iterator it = *this; iterator_base::Next(); return it; }
iterator operator--(int) { iterator it = *this; iterator_base::Prev(); return it; }
T * operator->() const { return iterator_base::Ptr(); }
T & operator* () const { return *iterator_base::Ptr(); }
};
iterator begin() { return info->head; }
iterator end() { return iterator(); }
iterator rbegin() { return info->tail; }
iterator rend() { return iterator(); }
class const_iterator : public iterator_base {
public:
const_iterator(PListElement * e = NULL) : iterator_base(e) { }
const_iterator operator++() { iterator_base::Next(); return *this; }
const_iterator operator--() { iterator_base::Prev(); return *this; }
const_iterator operator++(int) { const_iterator it = *this; iterator_base::Next(); return it; }
const_iterator operator--(int) { const_iterator it = *this; iterator_base::Prev(); return it; }
const T * operator->() const { return iterator_base::Ptr(); }
const T & operator* () const { return *iterator_base::Ptr(); }
};
const_iterator begin() const { return info->head; }
const_iterator end() const { return const_iterator(); }
const_iterator rbegin() const { return info->tail; }
const_iterator rend() const { return iterator(); }
T & front() const { return *(T *)PAssertNULL(info->head)->data; }
T & back() const { return *(T *)PAssertNULL(info->tail)->data; }
void erase(const iterator & it) { Remove(&*it); }
void erase(const const_iterator & it) { Remove(&*it); }
typedef T value_type;
T & operator[](
PINDEX index
) const { return (T &)GetReferenceAt(index); }
protected:
PList(int dummy, const PList * c)
: PAbstractList(dummy, c) { }
};
#define PLIST(cls, T) typedef PList<T> cls
#define PDECLARE_LIST(cls, T) \
PLIST(cls##_PTemplate, T); \
PDECLARE_CLASS(cls, PList<T>) \
protected: \
cls(int dummy, const cls * c) \
: PList<T>(dummy, c) { } \
public: \
cls() \
: PList<T>() { } \
virtual PObject * Clone() const \
{ return PNEW cls(0, this); } \
template <class T> class PQueue : public PAbstractList
{
PCLASSINFO(PQueue, PAbstractList);
public:
PQueue()
: PAbstractList() { DisallowDeleteObjects(); }
virtual PObject * Clone() const
{ return PNEW PQueue(0, this); }
virtual void Enqueue(
T * obj
) { PAbstractList::Append(obj); }
virtual T * Dequeue()
{ if (GetSize() == 0) return NULL; else return (T *)PAbstractList::RemoveAt(0);}
protected:
PQueue(int dummy, const PQueue * c)
: PAbstractList(dummy, c)
{ reference->deleteObjects = c->reference->deleteObjects; }
};
#define PQUEUE(cls, T) typedef PQueue<T> cls
#define PDECLARE_QUEUE(cls, T) \
PQUEUE(cls##_PTemplate, T); \
PDECLARE_CLASS(cls, cls##_PTemplate) \
protected: \
cls(int dummy, const cls * c) \
: cls##_PTemplate(dummy, c) { } \
public: \
cls() \
: cls##_PTemplate() { } \
virtual PObject * Clone() const \
{ return PNEW cls(0, this); } \
template <class T> class PStack : public PAbstractList
{
PCLASSINFO(PStack, PAbstractList);
public:
PStack()
: PAbstractList() { DisallowDeleteObjects(); }
virtual PObject * Clone() const
{ return PNEW PStack(0, this); }
virtual void Push(
T * obj
) { PAbstractList::InsertAt(0, obj); }
virtual T * Pop()
{ return (T *)PAbstractList::RemoveAt(0); }
virtual T & Top()
{ PAssert(GetSize() > 0, PStackEmpty); return *(T *)GetAt(0); }
protected:
PStack(int dummy, const PStack * c)
: PAbstractList(dummy, c)
{ reference->deleteObjects = c->reference->deleteObjects; }
};
#define PSTACK(cls, T) typedef PStack<T> cls
#define PDECLARE_STACK(cls, T) \
PSTACK(cls##_PTemplate, T); \
PDECLARE_CLASS(cls, cls##_PTemplate) \
protected: \
cls(int dummy, const cls * c) \
: cls##_PTemplate(dummy, c) { } \
public: \
cls() \
: cls##_PTemplate() { } \
virtual PObject * Clone() const \
{ return PNEW cls(0, this); } \
// Sorted List of PObjects
struct PSortedListElement
{
PSortedListElement * parent;
PSortedListElement * left;
PSortedListElement * right;
PObject * data;
PINDEX subTreeSize;
enum { Red, Black } colour;
PDECLARE_POOL_ALLOCATOR();
};
struct PSortedListInfo
{
PSortedListInfo();
PSortedListElement * root;
//PSortedListElement * lastElement;
//PINDEX lastIndex;
PSortedListElement nil;
PSortedListElement * Successor(const PSortedListElement * node) const;
PSortedListElement * Predecessor(const PSortedListElement * node) const;
PSortedListElement * OrderSelect(PSortedListElement * node, PINDEX index) const;
typedef PSortedListElement Element;
PDECLARE_POOL_ALLOCATOR();
};
class PAbstractSortedList : public PCollection
{
PCONTAINERINFO(PAbstractSortedList, PCollection);
public:
PAbstractSortedList();
virtual Comparison Compare(const PObject & obj) const;
virtual PBoolean SetSize(
PINDEX newSize // New size for the sorted list, this is ignored.
);
virtual PINDEX Append(
PObject * obj // New object to place into the collection.
);
virtual PINDEX Insert(
const PObject & before, // Object value to insert before.
PObject * obj // New object to place into the collection.
);
virtual PINDEX InsertAt(
PINDEX index, // Index position in collection to place the object.
PObject * obj // New object to place into the collection.
);
virtual PBoolean Remove(
const PObject * obj // Existing object to remove from the collection.
);
virtual PObject * RemoveAt(
PINDEX index // Index position in collection to place the object.
);
virtual void RemoveAll();
virtual PBoolean SetAt(
PINDEX index, // Index position in collection to set.
PObject * val // New value to place into the collection.
);
virtual PObject * GetAt(
PINDEX index // Index position in the collection of the object.
) const;
virtual PINDEX GetObjectsIndex(
const PObject * obj
) const;
virtual PINDEX GetObjectsIndex(
const PObject * obj,
PSortedListElement * & lastElement
) const;
virtual PINDEX GetValuesIndex(
const PObject & obj
) const;
// The type below cannot be nested as DevStudio 2005 AUTOEXP.DAT doesn't like it
typedef PSortedListElement Element;
protected:
// New functions for class
void RemoveElement(Element * node);
void LeftRotate(Element * node);
void RightRotate(Element * node);
void DeleteSubTrees(Element * node, PBoolean deleteObject);
PINDEX ValueSelect(const Element * node, const PObject & obj, const Element ** lastElement) const;
// The type below cannot be nested as DevStudio 2005 AUTOEXP.DAT doesn't like it
PSortedListInfo * info;
};
template <class T> class PSortedList : public PAbstractSortedList
{
PCLASSINFO(PSortedList, PAbstractSortedList);
public:
PSortedList()
: PAbstractSortedList() { }
virtual PObject * Clone() const
{ return PNEW PSortedList(0, this); }
T & operator[](
PINDEX index
) const { return *(T *)GetAt(index); }
protected:
PSortedList(int dummy, const PSortedList * c)
: PAbstractSortedList(dummy, c) { }
};
#define PSORTED_LIST(cls, T) typedef PSortedList<T> cls
#define PDECLARE_SORTED_LIST(cls, T) \
PSORTED_LIST(cls##_PTemplate, T); \
PDECLARE_CLASS(cls, PSortedList<T>) \
protected: \
cls(int dummy, const cls * c) \
: PSortedList<T>(dummy, c) { } \
public: \
cls() \
: PSortedList<T>() { } \
virtual PObject * Clone() const \
{ return PNEW cls(0, this); } \
#endif // PTLIB_LISTS_H
// End Of File ///////////////////////////////////////////////////////////////
PAbstractList::info
PListInfo * info
Definition: lists.h:311
PList::iterator_base::operator!=
bool operator!=(const iterator_base &it) const
Definition: lists.h:359
PStack::Top
virtual T & Top()
Get the element that is currently on top of the stack without removing it.
Definition: lists.h:632
PList::end
iterator end()
Definition: lists.h:376
PList::const_iterator::operator->
const T * operator->() const
Definition: lists.h:390
PSortedListElement::left
PSortedListElement * left
Definition: lists.h:689
PSortedListInfo::Element
PSortedListElement Element
Definition: lists.h:711
PList::begin
const_iterator begin() const
Definition: lists.h:394
PQueue::PQueue
PQueue(int dummy, const PQueue *c)
Definition: lists.h:524
PStack::Clone
virtual PObject * Clone() const
Make a complete duplicate of the stack.
Definition: lists.h:604
PSortedListElement
Definition: lists.h:686
PList::operator[]
T & operator[](PINDEX index) const
Retrieve a reference to the object in the list.
Definition: lists.h:420
PSortedListInfo::root
PSortedListElement * root
Definition: lists.h:702
PList::rbegin
iterator rbegin()
Definition: lists.h:377
PCLASSINFO
#define PCLASSINFO(cls, par)
Declare all the standard PTLib class information.
Definition: object.h:1049
PList::const_iterator::operator--
const_iterator operator--()
Definition: lists.h:386
PListElement
Definition: lists.h:45
PList::iterator::iterator
iterator(PListElement *e=NULL)
Definition: lists.h:364
PList::end
const_iterator end() const
Definition: lists.h:395
PList::rend
iterator rend()
Definition: lists.h:378
PList::value_type
T value_type
Definition: lists.h:404
PINLINE
#define PINLINE
Definition: object.h:127
PList::iterator::operator++
iterator operator++()
Definition: lists.h:366
PList::const_iterator::operator++
const_iterator operator++(int)
Definition: lists.h:387
PSortedList::PSortedList
PSortedList()
Create a new, empty, sorted list.
Definition: lists.h:966
PList::front
T & front() const
Definition: lists.h:399
PObject::Comparison
Comparison
Result of the comparison operation performed by the Compare() function.
Definition: object.h:1184
PSortedList::PSortedList
PSortedList(int dummy, const PSortedList *c)
Definition: lists.h:997
PStackEmpty
A Pop() was made of a stack with no elements.
Definition: object.h:157
PAbstractSortedList::info
PSortedListInfo * info
Definition: lists.h:943
PList::iterator_base::iterator_base
iterator_base(PListElement *e)
Definition: lists.h:350
PList::const_iterator::const_iterator
const_iterator(PListElement *e=NULL)
Definition: lists.h:383
PList::iterator_base::Next
void Next()
Definition: lists.h:353
PList::erase
void erase(const iterator &it)
Definition: lists.h:401
PAbstractList::Element
PListElement Element
Definition: lists.h:310
PAbstractList::Append
virtual PINDEX Append(PObject *obj)
Append a new object to the collection.
PAbstractList::InsertAt
virtual PINDEX InsertAt(PINDEX index, PObject *obj)
Insert a new object at the specified ordinal index.
PQueue::PQueue
PQueue()
Create a new, empty, queue.
Definition: lists.h:493
PList::PList
PList()
Create a new, empty, list.
Definition: lists.h:333
PList::iterator
Definition: lists.h:362
PList
This template class maps the PAbstractList to a specific object type.
Definition: lists.h:321
PListInfo::PListInfo
PListInfo()
Definition: lists.h:57
PBoolean
BOOL PBoolean
Definition: object.h:102
PListElement::PDECLARE_POOL_ALLOCATOR
PDECLARE_POOL_ALLOCATOR()
PQueue::Dequeue
virtual T * Dequeue()
Remove an object that was added to the queue.
Definition: lists.h:519
PList::iterator::operator--
iterator operator--()
Definition: lists.h:367
PQueue::Enqueue
virtual void Enqueue(T *obj)
Add a new object to the queue.
Definition: lists.h:511
PList::const_iterator::operator--
const_iterator operator--(int)
Definition: lists.h:388
PList::PList
PList(int dummy, const PList *c)
Definition: lists.h:426
PStack::Pop
virtual T * Pop()
Remove the last object pushed onto the stack.
Definition: lists.h:623
PSortedListInfo::nil
PSortedListElement nil
Definition: lists.h:705
PAbstractList::RemoveAt
virtual PObject * RemoveAt(PINDEX index)
Remove the object at the specified ordinal index from the collection.
PAssertNULL
#define PAssertNULL(ptr)
This macro is used to assert that a pointer must be non-null.
Definition: object.h:220
PStack::Push
virtual void Push(T *obj)
Add an object to the stack.
Definition: lists.h:614
PListInfo
Definition: lists.h:55
PSortedList::Clone
virtual PObject * Clone() const
Make a complete duplicate of the list.
Definition: lists.h:975
PAbstractList
This class is a collection of objects which are descendents of the PObject class. ...
Definition: lists.h:84
PList::erase
void erase(const const_iterator &it)
Definition: lists.h:402
PSortedListElement::parent
PSortedListElement * parent
Definition: lists.h:688
PListElement::data
PObject * data
Definition: lists.h:50
PList::begin
iterator begin()
Definition: lists.h:375
PList::iterator_base::operator==
bool operator==(const iterator_base &it) const
Definition: lists.h:358
PSortedListElement::data
PObject * data
Definition: lists.h:691
PStack::PStack
PStack(int dummy, const PStack *c)
Definition: lists.h:637
PQueue
This template class maps the PAbstractList to a specific object type, and adds functionality that all...
Definition: lists.h:480
PListElement::prev
PListElement * prev
Definition: lists.h:48
PContainerReference::deleteObjects
bool deleteObjects
Definition: contain.h:72
PList::iterator::operator--
iterator operator--(int)
Definition: lists.h:369
PCONTAINERINFO
#define PCONTAINERINFO(cls, par)
Macro to declare funtions required in a container.
Definition: contain.h:343
PList::iterator_base::Ptr
T * Ptr() const
Definition: lists.h:355
PSortedListInfo
Definition: lists.h:698
PStack::PStack
PStack()
Create a new, empty, stack.
Definition: lists.h:595
PList::iterator::operator++
iterator operator++(int)
Definition: lists.h:368
PListElement::PListElement
PListElement(PObject *theData)
PSortedList
This template class maps the PAbstractSortedList to a specific object type.
Definition: lists.h:954
PSortedListElement::right
PSortedListElement * right
Definition: lists.h:690
PStack
This template class maps the PAbstractList to a specific object type, and adds functionality that all...
Definition: lists.h:582
PListInfo::tail
PListElement * tail
Definition: lists.h:59
PListInfo::head
PListElement * head
Definition: lists.h:58
PAssert
#define PAssert(b, msg)
This macro is used to assert that a condition must be true.
Definition: object.h:192
PList::iterator::operator->
T * operator->() const
Definition: lists.h:371
PList::rend
const_iterator rend() const
Definition: lists.h:397
PAbstractSortedList::Element
PSortedListElement Element
Definition: lists.h:931
PSortedListElement::subTreeSize
PINDEX subTreeSize
Definition: lists.h:692
PList::rbegin
const_iterator rbegin() const
Definition: lists.h:396
PList::const_iterator::operator++
const_iterator operator++()
Definition: lists.h:385
PAbstractSortedList
This class is a collection of objects which are descendents of the PObject class. ...
Definition: lists.h:742
PQueue::Clone
virtual PObject * Clone() const
Make a complete duplicate of the list.
Definition: lists.h:502
PList::back
T & back() const
Definition: lists.h:400
PContainer::reference
PContainerReference * reference
Definition: contain.h:291
PList::iterator_base
Definition: lists.h:348
PListElement::next
PListElement * next
Definition: lists.h:49
RemoveElement
PObject * RemoveElement(const PObject &key)
PObject
Ultimate parent class for all objects in the class library.
Definition: object.h:1118
PCollection
A collection is a container that collects together descendents of the PObject class.
Definition: contain.h:395
PList::iterator_base::element
PListElement * element
Definition: lists.h:351
PSortedListElement::Red
Definition: lists.h:693
PList::const_iterator
Definition: lists.h:381
PList::iterator_base::Prev
void Prev()
Definition: lists.h:354
PNEW
#define PNEW
Macro for overriding system default new operator.
Definition: object.h:890
PList::Clone
virtual PObject * Clone() const
Make a complete duplicate of the list.
Definition: lists.h:342
PSortedList::operator[]
T & operator[](PINDEX index) const
Retrieve a reference to the object in the list.
Definition: lists.h:991