lists.h

mgcp协议源代码。支持多种编码：g711

   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[]#).
 */
class PAbstractSortedList : public PCollection
{
  PCONTAINERINFO(PAbstractSortedList, PCollection);

  public:
  /**@name Construction */
  //@{
    /**Create a new, empty, sorted list.

       Note that by default, objects placed into the list will be deleted when
       removed or when all references to the list are destroyed.
     */
    PAbstractSortedList();
  //@}

  /**@name Overrides from class PObject */
  //@{
    /**Get the relative rank of the two lists. The following algorithm is
       employed for the comparison:
\begin{descriptions}
       \item[#EqualTo#] if the two lists are identical in length
       and each objects values, not pointer, are equal.

       \item[#LessThan#] if the instances object value at an
       ordinal position is less than the corresponding objects value in the
       #obj# parameters list.
                          
       This is also returned if all objects are equal and the instances list
       length is less than the #obj# parameters list length.

       \item[#GreaterThan#] if the instances object value at an
       ordinal position is greater than the corresponding objects value in the
       #obj# parameters list.
                          
       This is also returned if all objects are equal and the instances list
       length is greater than the #obj# parameters list length.
\end{descriptions}

       @return
       comparison of the two objects, #EqualTo# for same,
       #LessThan# for #obj# logically less than the
       object and #GreaterThan# for #obj# logically
       greater than the object.
     */
    virtual Comparison Compare(const PObject & obj) const;
  //@}

  /**@name Overrides from class PContainer */
  //@{
    /**This function is meaningless for lists. The size of the collection is
       determined by the addition and removal of objects. The size cannot be
       set in any other way.

       @return
       Always TRUE.
     */
    virtual BOOL SetSize(
      PINDEX newSize  // New size for the sorted list, this is ignored.
    );
  //@}

  /**@name Overrides from class PCollection */
  //@{
    /**Add a new object to the collection. The object is always placed in the
       correct ordinal position in the list. It is not placed at the "end".

       @return
       index of the newly added object.
     */
    virtual PINDEX Append(
      PObject * obj   // New object to place into the collection.
    );

    /**Add a new object to the collection.
    
       The object is always placed in the correct ordinal position in the list.
       It is not placed at the specified position. The #before#
       parameter is ignored.

       @return
       index of the newly inserted object.
     */
    virtual PINDEX Insert(
      const PObject & before,   // Object value to insert before.
      PObject * obj             // New object to place into the collection.
    );

    /**Add a new object to the collection.
    
       The object is always placed in the correct ordinal position in the list.
       It is not placed at the specified position. The #index#
       parameter is ignored.

       @return
       index of the newly inserted object.
     */
    virtual PINDEX InsertAt(
      PINDEX index,   // Index position in collection to place the object.
      PObject * obj   // New object to place into the collection.
    );

    /**Remove the object from the collection. If the AllowDeleteObjects option
       is set then the object is also deleted.

       Note that the comparison for searching for the object in collection is
       made by pointer, not by value. Thus the parameter must point to the
       same instance of the object that is in the collection.

       @return
       TRUE if the object was in the collection.
     */
    virtual BOOL Remove(
      const PObject * obj   // Existing object to remove from the collection.
    );

    /**Remove the object at the specified ordinal index from the collection.
       If the AllowDeleteObjects option is set then the object is also deleted.

       Note if the index is beyond the size of the collection then the
       function will assert.

       @return
       pointer to the object being removed, or NULL if it was deleted.
     */
    virtual PObject * RemoveAt(
      PINDEX index   // Index position in collection to place the object.
    );

    /**Remove all of the elements in the collection. This operates by
       continually calling #RemoveAt()# until there are no objects left.

       The objects are removed from the last, at index
       #(GetSize()-1)# toward the first at index zero.
     */
    virtual void RemoveAll();

    /**Set the object at the specified ordinal position to the new value. This
       will overwrite the existing entry. If the AllowDeleteObjects option is
       set then the old object is also deleted.

       Note, the object placed at #index# will not stay at that
       ordinal position. It is actually placed at the correct position for its
       rank.

       @return
       TRUE if the object was successfully added.
     */
    virtual BOOL SetAt(
      PINDEX index,   // Index position in collection to set.
      PObject * val   // New value to place into the collection.
    );

    /**Get the object at the specified ordinal position. If the index was
       greater than the size of the collection then NULL is returned.

       @return
       pointer to object at the specified index.
     */
    virtual PObject * GetAt(
      PINDEX index  // Index position in the collection of the object.
    ) const;

    /**Search the collection for the specific instance of the object. The
       object pointers are compared, not the values. A binary search is
       employed to locate the entry.
       
       Note that that will require value comparisons to be made to find the
       equivalent entry and then a final check is made with the pointers to
       see if they are the same instance.

       @return
       ordinal index position of the object, or P_MAX_INDEX.
     */
    virtual PINDEX GetObjectsIndex(
      const PObject * obj
    ) const;

    /**Search the collection for the specified value of the object. The object
       values are compared, not the pointers.  So the objects in the
       collection must correctly implement the #PObject::Compare()#
       function. A binary search is employed to locate the entry.

       @return
       ordinal index position of the object, or P_MAX_INDEX.
     */
    virtual PINDEX GetValuesIndex(
      const PObject & obj
    ) const;
  //@}


    class Element {
      public:
        Element(PObject * theData);

      private:
        void DeleteSubTrees(BOOL deleteObject);
        Element * Successor() const;
        Element * Predecessor() const;
        Element * OrderSelect(PINDEX index);
        PINDEX ValueSelect(const PObject & obj, Element * & lastElement);

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

      friend class PAbstractSortedList;
    };
    friend class Element;

  protected:

    class Info {
      public:
        Info();
        Element * root;
        Element * lastElement;
        PINDEX    lastIndex;
    } * info;
    friend class Info;

    // New functions for class
    void RemoveElement(Element * node);
    void LeftRotate(Element * node);
    void RightRotate(Element * node);
};


#ifdef PHAS_TEMPLATES

/**This template class maps the PAbstractSortedList to a specific object type.
   The functions in this class primarily do all the appropriate casting of
   types.

   Note that if templates are not used the #PDECLARE_SORTED_LIST# macro
   will simulate the template instantiation.
 */
template <class T> class PSortedList : public PAbstractSortedList
{
  PCLASSINFO(PSortedList, PAbstractSortedList);

  public:
  /**@name Construction */
  //@{
    /**Create a new, empty, sorted list.

       Note that by default, objects placed into the list will be deleted when
       removed or when all references to the list are destroyed.
     */
    PSortedList()
      : PAbstractSortedList() { }
  //@}

  /**@name Overrides from class PObject */
  //@{
    /**Make a complete duplicate of the list. Note that all objects in the
       array are also cloned, so this will make a complete copy of the list.
     */
    virtual PObject * Clone() const
      { return PNEW PSortedList(0, this); }
  //@}

  /**@name New functions for class */
  //@{
    /**Retrieve a reference  to the object in the list. If there was not an
       object at that ordinal position or the index was beyond the size of the
       array then the function asserts.

       The object accessed in this way is remembered by the class and further
       access will be fast.

       @return
       reference to the object at #index# position.
     */
    T & operator[](PINDEX index) const
      { return *(T *)GetAt(index); }
  //@}

  protected:
    PSortedList(int dummy, const PSortedList * c)
      : PAbstractSortedList(dummy, c) { }
};


/**Declare a sorted list class.
   This macro is used to declare a descendent of PAbstractSortedList class,
   customised for a particular object type {\bf T}. This macro closes the
   class declaration off so no additional members can be added.

   If the compilation is using templates then this macro produces a typedef
   of the #PSortedList# template class.

   See the #PSortedList# class and #PDECLARE_SORTED_LIST# macro for
   more information.
 */
#define PSORTED_LIST(cls, T) typedef PSortedList<T> cls


/**Begin declaration of a sorted list class.
   This macro is used to declare a descendent of PAbstractSortedList class,
   customised for a particular object type {\bf T}.

   If the compilation is using templates then this macro produces a descendent
   of the #PSortedList# template class. If templates are not being used
   then the macro defines a set of inline functions to do all casting of types.
   The resultant classes have an identical set of functions in either case.

   See the #PSortedList# and #PAbstractSortedList# classes for more
   information.
 */
#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); } \


#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() { } \
    inline 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 ///////////////////////////////////////////////////////////////