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: 21788 $
 * $Author: rjongbloed $
 * $Date: 2008-12-11 23:42:13 -0600 (Thu, 11 Dec 2008) $
 */

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

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

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

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

---