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: 28339 $
 * $Author: rjongbloed $
 * $Date: 2012-09-11 17:43:32 +1000 (Tue, 11 Sep 2012) $
 */

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

    PDECLARE_POOL_ALLOCATOR();
};

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

    PDECLARE_POOL_ALLOCATOR();
};

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 void Prepend(
      PObject * obj   
    );

    virtual PINDEX Insert(
      const PObject & before,   
      PObject * obj             
    );

    P_DEPRECATED virtual PINDEX InsertAt(
      PINDEX index,   
      PObject * obj   
    );

    virtual PBoolean Remove(
      const PObject * obj   
    );

    virtual PObject * RemoveHead()
      { return RemoveElement(info->head); }

    virtual PObject * RemoveTail()
      { return RemoveElement(info->tail); }


    P_DEPRECATED virtual PObject * RemoveAt(
      PINDEX index   
    );

    P_DEPRECATED virtual PBoolean SetAt(
      PINDEX index,   
      PObject * val   
    );
    
    P_DEPRECATED virtual PBoolean ReplaceAt(
      PINDEX index,   
      PObject * val   
    );

    P_DEPRECATED 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;
    PListElement * FindElement(PINDEX index) const;
    PListElement * FindElement(const PObject & obj, PINDEX * index) const;
    void InsertElement(PListElement * element, PObject * obj);
    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); }

    typedef T value_type;

    class iterator_base : public std::iterator<std::bidirectional_iterator_tag, value_type> {
      protected:
        iterator_base(PListElement * e) : element(e) { }
        PListElement * element;

        void Next() { this->element = PAssertNULL(this->element)->next; }
        void Prev() { this->element = PAssertNULL(this->element)->prev; }
        value_type * Ptr() const { return  dynamic_cast<value_type *>(PAssertNULL(this->element)->data); }

      public:
        bool operator==(const iterator_base & it) const { return this->element == it.element; }
        bool operator!=(const iterator_base & it) const { return this->element != it.element; }

      friend class PList<T>;
    };

    class iterator : public iterator_base {
      public:
        iterator(PListElement * e = NULL) : iterator_base(e) { }

        iterator operator++()    {                      this->Next(); return *this; }
        iterator operator--()    {                      this->Prev(); return *this; }
        iterator operator++(int) { iterator it = *this; this->Next(); return it;    }
        iterator operator--(int) { iterator it = *this; this->Prev(); return it;    }

        value_type * operator->() const { return  this->Ptr(); }
        value_type & operator* () const { return *this->Ptr(); }
    };

    iterator begin()  { return this->info->head; }
    iterator end()    { return iterator(); }
    iterator rbegin() { return this->info->tail; }
    iterator rend()   { return iterator(); }
    iterator find(const value_type & obj) { return this->FindElement(obj, NULL); }
    void insert(const iterator & pos, value_type * obj) { this->InsertElement(pos.element, obj); }

    class const_iterator : public iterator_base {
      public:
        const_iterator(PListElement * e = NULL) : iterator_base(e) { }

        const_iterator operator++()    {                            this->Next(); return *this; }
        const_iterator operator--()    {                            this->Prev(); return *this; }
        const_iterator operator++(int) { const_iterator it = *this; this->Next(); return it;    }
        const_iterator operator--(int) { const_iterator it = *this; this->Prev(); return it;    }

        const value_type * operator->() const { return  this->Ptr(); }
        const value_type & operator* () const { return *this->Ptr(); }
    };

    const_iterator begin()  const { return this->info->head; }
    const_iterator end()    const { return const_iterator(); }
    const_iterator rbegin() const { return this->info->tail; }
    const_iterator rend()   const { return iterator(); }
    const_iterator find(const value_type & obj) const { return this->FindElement(obj, NULL); }

    value_type & front() const { return dynamic_cast<value_type &>(*PAssertNULL(this->info->head)->data); }
    value_type & back() const { return dynamic_cast<value_type &>(*PAssertNULL(this->info->tail)->data); }
    void erase(const iterator & it) { this->RemoveElement(it.element); }
    void erase(const const_iterator & it) { this->RemoveElement(it.element); }

    T & operator[](
      PINDEX index  
    ) const { return dynamic_cast<T &>(this->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()
      { return dynamic_cast<T *>(PAbstractList::RemoveHead()); }

  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::Prepend(obj); }

    virtual T * Pop()
      { return dynamic_cast<T *>(PAbstractList::RemoveHead()); }

    virtual T & Top()
      { PAssert(this->GetSize() > 0, PStackEmpty); return dynamic_cast<T &>(*this->info->head->data); }

  protected:
    PStack(int dummy, const PStack * c)
      : PAbstractList(dummy, c)
      { this->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(PSortedListElement * nil = NULL, PObject * obj = NULL);

  PSortedListElement * m_parent;
  PSortedListElement * m_left;
  PSortedListElement * m_right;
  PObject            * m_data;
  PINDEX               m_subTreeSize;
  enum { Red, Black }  m_colour;

  PDECLARE_POOL_ALLOCATOR();
};

struct PSortedListInfo
{
  PSortedListInfo() : m_root(&nil) { }

  PSortedListElement   nil;
  PSortedListElement * m_root;

  PSortedListElement * Successor(PSortedListElement * node) const;
  PSortedListElement * Predecessor(PSortedListElement * node) const;
  PSortedListElement * OrderSelect(PSortedListElement * node, PINDEX index) const;
  PSortedListElement * OrderSelect(PINDEX index) const { return OrderSelect(m_root, index); }
  PINDEX ValueSelect(PSortedListElement * node, const PObject & obj, PSortedListElement * & element) const;
  PINDEX ValueSelect(const PObject & obj, PSortedListElement * & element) const { return ValueSelect(m_root, obj, element); }

  PDECLARE_POOL_ALLOCATOR();
};

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;

  protected:

    // New functions for class
    void RemoveElement(PSortedListElement * node);
    void LeftRotate(PSortedListElement * node);
    void RightRotate(PSortedListElement * node);
    void DeleteSubTrees(PSortedListElement * node, bool deleteObject);
    PSortedListElement * FindElement(const PObject & obj, PINDEX * index) const;
    PSortedListElement * FindElement(const PObject * obj, PINDEX * index) const;

    // The type below cannot be nested as DevStudio 2005 AUTOEXP.DAT doesn't like it
    PSortedListInfo * m_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 dynamic_cast<T &>(*this->GetAt(index)); }

    typedef T value_type;
    friend class iterator_base;

  private:
    void NextElement(PSortedListElement * & element)
    {
      element = this->m_info->Successor(element);
      if (element == &this->m_info->nil)
        element = NULL;
    }

    void PrevElement(PSortedListElement * & element)
    {
      element = this->m_info->Predecessor(element);
      if (element == &this->m_info->nil)
        element = NULL;
    }

    class iterator_base : public std::iterator<std::bidirectional_iterator_tag, value_type> {
      protected:
        PSortedList<T>     * m_list;
        PSortedListElement * m_element;

        iterator_base(PSortedList<T> * l, PSortedListElement * e) : m_list(l), m_element(e) { }

        bool Valid() const { return PAssert(this->m_list != NULL && this->m_element != NULL && this->m_element != &m_list->m_info->nil, PInvalidArrayIndex); }
        void Next() { if (Valid()) this->m_list->NextElement(this->m_element); }
        void Prev() { if (Valid()) this->m_list->PrevElement(this->m_element); }
        value_type * Ptr() const { return dynamic_cast<value_type *>(Valid() ? this->m_element->m_data : NULL); }

      public:
        bool operator==(const iterator_base & it) const { return this->m_element == it.m_element; }
        bool operator!=(const iterator_base & it) const { return this->m_element != it.m_element; }

      friend class PSortedList<T>;
    };

  public:
    class iterator : public iterator_base {
      public:
        iterator() : iterator_base(NULL, NULL) { }
        iterator(PSortedList<T> * l, PSortedListElement * e) : iterator_base(l, e) { }

        iterator operator++()    {                      this->Next(); return *this; }
        iterator operator--()    {                      this->Prev(); return *this; }
        iterator operator++(int) { iterator it = *this; this->Next(); return it;    }
        iterator operator--(int) { iterator it = *this; this->Prev(); return it;    }

        value_type * operator->() const { return  this->Ptr(); }
        value_type & operator* () const { return *this->Ptr(); }
    };

    iterator begin()  { return IsEmpty() ? iterator() : iterator(this, this->m_info->OrderSelect(1));                 }
    iterator end()    { return             iterator();                                                                }
    iterator rbegin() { return IsEmpty() ? iterator() : iterator(this, this->m_info->OrderSelect(this->GetSize())); }
    iterator rend()   { return             iterator();                                                                }

    class const_iterator : public iterator_base {
      public:
        const_iterator() : iterator_base(NULL, NULL) { }
        const_iterator(PSortedList<T> * l, PSortedListElement * e) : iterator_base(l, e) { }

        const_iterator operator++()    {                            this->Next(); return *this; }
        const_iterator operator--()    {                            this->Prev(); return *this; }
        const_iterator operator++(int) { const_iterator it = *this; this->Next(); return it;    }
        const_iterator operator--(int) { const_iterator it = *this; this->Prev(); return it;    }

        const value_type * operator->() const { return  this->Ptr(); }
        const value_type & operator* () const { return *this->Ptr(); }
    };

    const_iterator begin()  const { return IsEmpty() ? const_iterator() : const_iterator(this, this->m_info->OrderSelect(1));                 }
    const_iterator end()    const { return             const_iterator();                                                                            }
    const_iterator rbegin() const { return IsEmpty() ? const_iterator() : const_iterator(this, this->m_info->OrderSelect(this->GetSize())); }
    const_iterator rend()   const { return             const_iterator();                                                                            }

    value_type & front() { return *this->begin(); }
    value_type & back()  { return *this->rbegin(); }
    const value_type & front() const { return *this->begin(); }
    const value_type & back()  const { return *this->rbegin(); }

          iterator find(const value_type & obj)       { return       iterator(this, this->FindElement(obj, NULL));                      }
    const_iterator find(const value_type & obj) const { return const_iterator(this, this->FindElement(obj, NULL)); }

    void erase(const iterator & it)       { PAssert(this == it.m_list, PLogicError); this->RemoveElement(it.m_element); }
    void erase(const const_iterator & it) { PAssert(this == it.m_list, PLogicError); this->RemoveElement(it.m_element); }

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