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

Classes | Protected Member Functions | Protected Attributes | Private Member Functions

PAbstractSortedList Class Reference

#include <lists.h>

Inheritance diagram for PAbstractSortedList:
Inheritance graph
Collaboration diagram for PAbstractSortedList:
Collaboration graph

List of all members.


struct  Element
struct  Info

Public Member Functions

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

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::Infoinfo
class PContainer::Referencereference

Private Member Functions

 PCONTAINERINFO (PAbstractSortedList, PCollection)

Run Time Type functions

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

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 }

I/O functions

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

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.

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

Generated by  Doxygen 1.6.0   Back to index