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: 19008 $
 * $Author: rjongbloed $
 * $Date: 2007-11-29 09:17:41 +0000 (Thu, 29 Nov 2007) $
 */

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


#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 ///////////////////////////////////////////////////////////////

---