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): ______________________________________.
 *
 * $Log: lists.h,v $
 * Revision 1.33  2007/08/01 05:20:48  rjongbloed
 * Changes to container classes to become compatible with advanced DevStudio 2005 "Visualizers".
 *
 * Revision 1.32  2005/11/25 03:43:47  csoutheren
 * Fixed function argument comments to be compatible with Doxygen
 *
 * Revision 1.31  2005/01/25 06:35:27  csoutheren
 * Removed warnings under MSVC
 *
 * Revision 1.30  2005/01/09 06:35:03  rjongbloed
 * Fixed ability to make Clone() or MakeUnique() of a sorted list.
 *
 * Revision 1.29  2004/04/09 03:42:34  csoutheren
 * Removed all usages of "virtual inline" and "inline virtual"
 *
 * Revision 1.28  2004/04/04 07:39:57  csoutheren
 * Fixed cut-and-paste typo in VS.net 2003 changes that made all PLists sorted. Yikes!
 *
 * Revision 1.27  2004/04/03 23:53:09  csoutheren
 * Added various changes to improce compatibility with the Sun Forte compiler
 *   Thanks to Brian Cameron
 * Added detection of readdir_r version
 *
 * Revision 1.26  2004/04/03 06:54:21  rjongbloed
 * Many and various changes to support new Visual C++ 2003
 *
 * Revision 1.25  2004/02/15 03:04:52  rjongbloed
 * Fixed problem with PSortedList nil variable and assignment between instances,
 *   pointed out by Ben Lear.
 *
 * Revision 1.24  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.23  2004/02/08 11:13:10  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.22  2003/08/31 22:11:29  dereksmithies
 * Fix from Diego Tartara for the SetAt function. Many thanks.
 *
 * Revision 1.21  2002/11/12 08:55:53  robertj
 * Changed scope of PAbstraSortedList::Element class so descendant classes
 *   can get at it.
 *
 * Revision 1.20  2002/09/16 01:08:59  robertj
 * Added #define so can select if #pragma interface/implementation is used on
 *   platform basis (eg MacOS) rather than compiler, thanks Robert Monaghan.
 *
 * Revision 1.19  2000/04/14 07:19:32  craigs
 * Fixed problem with assert when dequeueing from an empty queue
 *
 * Revision 1.18  1999/08/22 12:13:43  robertj
 * Fixed warning when using inlines on older GNU compiler
 *
 * Revision 1.17  1999/03/09 02:59:50  robertj
 * Changed comments to doc++ compatible documentation.
 *
 * Revision 1.16  1999/02/16 08:12:00  robertj
 * MSVC 6.0 compatibility changes.
 *
 * Revision 1.15  1998/09/23 06:20:49  robertj
 * Added open source copyright license.
 *
 * Revision 1.14  1997/06/08 04:49:12  robertj
 * Fixed non-template class descendent order.
 *
 * Revision 1.13  1997/04/27 05:50:10  robertj
 * DLL support.
 *
 * Revision 1.12  1997/02/14 13:53:59  robertj
 * Major rewrite of sorted list to use sentinel record instead of NULL pointers.
 *
 * Revision 1.11  1996/07/15 10:32:50  robertj
 * Fixed bug in sorted list (crash on remove).
 *
 * Revision 1.10  1996/05/26 03:25:13  robertj
 * Compatibility to GNU 2.7.x
 *
 * Revision 1.9  1996/01/23 13:13:32  robertj
 * Fixed bug in sorted list GetObjectsIndex not checking if is same object
 *
 * Revision 1.8  1995/08/24 12:35:00  robertj
 * Added assert for list index out of bounds.
 *
 * Revision 1.7  1995/06/17 11:12:43  robertj
 * Documentation update.
 *
 * Revision 1.6  1995/03/14 12:41:41  robertj
 * Updated documentation to use HTML codes.
 *
 * Revision 1.5  1995/02/22  10:50:30  robertj
 * Changes required for compiling release (optimised) version.
 *
 * Revision 1.4  1995/02/05  00:48:05  robertj
 * Fixed template version.
 *
 * Revision 1.3  1995/01/15  04:49:23  robertj
 * Fixed errors in template version.
 *
 * Revision 1.2  1994/12/21  11:53:12  robertj
 * Documentation and variable normalisation.
 *
 * Revision 1.1  1994/12/12  09:59:35  robertj
 * Initial revision
 *
 */

#ifdef P_USE_PRAGMA
#pragma interface
#endif


// PList container class

struct PListElement
{
    PListElement(PObject * theData);
    PListElement * prev;
    PListElement * next;
    PObject * data;
};

struct PListInfo
{
    PListInfo() { head = tail = lastElement = NULL; }
    PListElement * head;
    PListElement * tail;
    PListElement * lastElement;
    PINDEX    lastIndex;
};

class PAbstractList : public PCollection
{
  PCONTAINERINFO(PAbstractList, PCollection);

  public:
    PINLINE PAbstractList();

  // Overrides from class PObject
    virtual Comparison Compare(const PObject & obj) const;

    virtual BOOL SetSize(
      PINDEX newSize  
    );

    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 PObject * RemoveAt(
      PINDEX index   
    );

    virtual BOOL SetAt(
      PINDEX index,   
      PObject * val   
    );
    
    virtual BOOL 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;

    BOOL SetCurrent(
      PINDEX index  
    ) const;

    // The types below cannot be nested as DevStudio 2005 AUTOEXP.DAT doesn't like it
    typedef PListElement Element;
    PListInfo * info;
};


#ifdef PHAS_TEMPLATES

template <class T> class PList : public PAbstractList
{
  PCLASSINFO(PList, PAbstractList);

  public:
    PList()
      : PAbstractList() { }

    virtual PObject * Clone() const
      { return PNEW PList(0, this); }

    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); } \


#else // PHAS_TEMPLATES


#define PLIST(cls, T) \
  class cls : public PAbstractList { \
  PCLASSINFO(cls, PAbstractList); \
  protected: \
    inline cls(int dummy, const cls * c) \
      : PAbstractList(dummy, c) { } \
  public: \
    inline cls() \
      : PAbstractList() { } \
    virtual PObject * Clone() const \
      { return PNEW cls(0, this); } \
    inline T & operator[](PINDEX index) const \
      { return (T &)GetReferenceAt(index); } \
  }

#define PDECLARE_LIST(cls, T) \
  PLIST(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); } \


#define PQUEUE(cls, T) \
  class cls : public PAbstractList { \
  PCLASSINFO(cls, PAbstractList); \
  protected: \
    inline cls(int dummy, const cls * c) \
      : PAbstractList(dummy, c) \
      { reference->deleteObjects = c->reference->deleteObjects; } \
  public: \
    inline cls() \
      : PAbstractList() { DisallowDeleteObjects(); } \
    virtual PObject * Clone() const \
      { return PNEW cls(0, this); } \
    virtual void Enqueue(T * t) \
      { PAbstractList::Append(t); } \
    virtual T * Dequeue() \
      { if (GetSize() == 0) return NULL; else return (T *)PAbstractList::RemoveAt(0);} \
  }

#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); } \

#define PSTACK(cls, T) \
  class cls : public PAbstractList { \
  PCLASSINFO(cls, PAbstractList); \
  protected: \
    inline cls(int dummy, const cls * c) \
      : PAbstractList(dummy, c) \
      { reference->deleteObjects = c->reference->deleteObjects; } \
  public: \
    inline cls() \
      : PAbstractList() { DisallowDeleteObjects(); } \
    virtual PObject * Clone() const \
      { return PNEW cls(0, this); } \
    virtual void Push(T * t) \
      { PAbstractList::InsertAt(0, t); } \
    virtual T * Pop() \
      { PAssert(GetSize() > 0, PStackEmpty); return (T *)PAbstractList::RemoveAt(0); } \
    virtual T & Top() \
      { PAssert(GetSize() > 0, PStackEmpty); return *(T *)GetAt(0); } \
  }

#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); } \


#endif // PHAS_TEMPLATES


// Sorted List of PObjects

struct PSortedListElement
{
  PSortedListElement * parent;
  PSortedListElement * left;
  PSortedListElement * right;
  PObject            * data;
  PINDEX               subTreeSize;
  enum { Red, Black }  colour;
};

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;
};

class PAbstractSortedList : public PCollection
{
  PCONTAINERINFO(PAbstractSortedList, PCollection);

  public:
    PAbstractSortedList();

    virtual Comparison Compare(const PObject & obj) const;

    virtual BOOL 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 BOOL 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 BOOL 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 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, BOOL 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;
};


#ifdef PHAS_TEMPLATES

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); } \


#else // PHAS_TEMPLATES


#define PSORTED_LIST(cls, T) \
  class cls : public PAbstractSortedList { \
  PCLASSINFO(cls, PAbstractSortedList); \
  protected: \
    inline cls(int dummy, const cls * c) \
      : PAbstractSortedList(dummy, c) { } \
  public: \
    inline cls() \
      : PAbstractSortedList() { } \
    virtual PObject * Clone() const \
      { return PNEW cls(0, this); } \
    inline T & operator[](PINDEX index) const \
      { return *(T *)GetAt(index); } \
  }

#define PDECLARE_SORTED_LIST(cls, T) \
  PSORTED_LIST(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); } \


#endif  // PHAS_TEMPLATES


// End Of File ///////////////////////////////////////////////////////////////

---