Logo Search packages:      
Sourcecode: pwlib version File versions  Download package

PAbstractSortedList Class Reference

#include <lists.h>

Inheritance diagram for PAbstractSortedList:

PCollection PContainer PObject

List of all members.


Detailed Description

This class is a collection of objects which are descendents of the PObject# class. It is implemeted as a Red-Black binary tree to maintain the objects in rank order. Note that this requires that the PObject::Compare()# function be fully implemented oin objects contained in the collection.

The implementation of a sorted list allows fast inserting and deleting as well as random access of objects in the collection. As the objects are being kept sorted, "fast" is a relative term. All operations take o(lg n) unless a particular object is repeatedly accessed.

The class remembers the last accessed element. This state information is used to optimise access by the "virtual array" model of collections. If repeated access via ordinal index is made there is little overhead. All other access incurs a minimum overhead, but not insignificant.

The PAbstractSortedList class would very rarely be descended from directly by the user. The PDECLARE_LIST# and PLIST# macros would normally be used to create descendent classes. They will instantiate the template based on PSortedList# or directly declare and define the class (using inline functions) if templates are not being used.

The PSortedList# class or PDECLARE_SORTED_LIST# macro will define the correctly typed operators for subscript access (operator[]#).

Definition at line 839 of file lists.h.


Comparison functions

virtual Comparison CompareObjectMemoryDirect (const PObject &obj) const
bool operator!= (const PObject &obj) const
bool operator< (const PObject &obj) const
bool operator<= (const PObject &obj) const
bool operator== (const PObject &obj) const
bool operator> (const PObject &obj) const
bool operator>= (const PObject &obj) const
enum  Comparison { LessThan = -1, EqualTo = 0, GreaterThan = 1 }

Run Time Type functions

virtual const char * GetClass (unsigned=0) const
virtual BOOL InternalIsDescendant (const char *clsName) const
BOOL IsClass (const char *cls) const
static const char * Class ()

I/O functions

virtual void ReadFrom (istream &strm)
ostream & operator<< (ostream &strm, const PObject &obj)
istream & operator>> (istream &strm, PObject &obj)

Public Member Functions

Common functions for collections
PINLINE void AllowDeleteObjects (BOOL yes=TRUE)
void DisallowDeleteObjects ()
Overrides from class PCollection
virtual PINDEX Append (PObject *obj)
virtual PObjectGetAt (PINDEX index) const
virtual PINDEX GetObjectsIndex (const PObject *obj) const
virtual PINDEX GetValuesIndex (const PObject &obj) const
virtual PINDEX Insert (const PObject &before, PObject *obj)
virtual PINDEX InsertAt (PINDEX index, PObject *obj)
virtual BOOL Remove (const PObject *obj)
virtual void RemoveAll ()
virtual PObjectRemoveAt (PINDEX index)
virtual BOOL SetAt (PINDEX index, PObject *val)
Miscellaneous functions
virtual PObjectClone () const
virtual PINDEX HashFunction () const
Overrides from class PObject
virtual Comparison Compare (const PObject &obj) const
Common functions for containers
virtual PINDEX GetSize () const
virtual BOOL IsEmpty () const
BOOL IsUnique () const
virtual BOOL MakeUnique ()
BOOL SetMinSize (PINDEX minSize)
Construction
 PAbstractSortedList ()
Overrides from class PObject
virtual void PrintOn (ostream &strm) const
Overrides from class PContainer
virtual BOOL SetSize (PINDEX newSize)

Protected Member Functions

virtual void AssignContents (const PContainer &c)
void CloneContents (const PContainer *src)
void CopyContents (const PContainer &c)
void DeleteSubTrees (Element *node, BOOL deleteObject)
virtual void DestroyContents ()=0
void Destruct ()
void LeftRotate (Element *node)
void RemoveElement (Element *node)
void RightRotate (Element *node)
PINDEX ValueSelect (const Element *node, const PObject &obj, const Element **lastElement) const

Protected Attributes

struct PAbstractSortedList::Info * info
class PContainer::Reference * reference

Private Member Functions

 PCONTAINERINFO (PAbstractSortedList, PCollection)

Classes

struct  Element
struct  Info

The documentation for this class was generated from the following files:

Generated by  Doxygen 1.6.0   Back to index