---

CTBbtree.hxx

Go to the documentation of this file.

#ifndef _CTBbtree_HXX
#define _CTBbtree_HXX 1

/*----------------------------------------------------------------------------*/
/* C Tool Box: Designed and implemented by:                                   */
/*    Walter F.J. Mueller   Gesellschaft fuer Schwerionenforschung (GSI)      */
/*                          Planckstrasse 1, D-64291 Darmstadt, Germany       */
/*                  Email:  W.F.J.Mueller@gsi.de                              */
/*                  WWW:    http://www-kp3.gsi.de/www/kp3/people/mueller.html */
/*------------------------------------------+---------------------------------*/

#include "CTBclone.hxx"

class CTBbtreeNode;                         // forward dcl of node class

class CTBbtree {

  friend class CTBbtreeNode;

  public:

                    CTBbtree();
                    CTBbtree(const CTBbtree& rhs);

    virtual         ~CTBbtree();

    CTBbtreeNode*   RNode() const;
    CTBbtreeNode*   First() const;
    CTBbtreeNode*   Last() const;
    CTBsize         Size() const;

    void            Clear();

    void            TreeHeight(int& i_minh,int& i_maxh,float& f_avrp) const;
    bool            TreeCheck(ostream* p_os = 0) const;
  
    void            Dump(int i_indent=0, ostream& os=cout,
                         const char* p_text=0) const;
  
    CTBbtreeNode*   operator[](CTBint i_ind) const;

    CTBbtree&       operator=(const CTBbtree& rhs);

  private:

    CTBbtreeNode*   mp_rnode;               
    CTBbtreeNode*   mp_first;               
    CTBbtreeNode*   mp_last;                
    CTBint          mi_size;                
};

class CTBbtreeNode {

  friend class CTBbtree;

  public:

                    CTBbtreeNode();
    virtual         ~CTBbtreeNode();

    virtual CTBbtreeNode* Clone() const;

    CTBbtree*       Head() const;
    CTBbtreeNode*   Left() const;
    CTBbtreeNode*   Right() const;
    CTBbtreeNode*   Up() const;
    CTBbtreeNode*   Next() const;
    CTBbtreeNode*   Prev() const;

    CTBbtreeNode*   Skip(CTBint i_offset) const;

    CTBint          Rank() const;

    CTBint          LWeight() const;

    bool            IsRNode() const;
    bool            IsLeftChild() const;
    bool            IsRightChild() const;

    bool            IsBalanced() const;
    bool            IsLeftHeavy() const;
    bool            IsRightHeavy() const;

    void            Insert(CTBbtree& head,CTBbtreeNode* p_parent,int i_ctype);

    void            Remove();

  private:

    void            LWeight(                // set left tree weight
                      CTBint i_weight);
    void            IncLWeight();           // increment left tree weight
    void            DecLWeight();           // decrement left tree weight

    void            SetRNode();             // set child status to rnode
    void            SetLeftChild();         // set child status to left
    void            SetRightChild();        // set child status to right

    void            SetBalanced();          // set bfactor to balanced
    void            SetLeftHeavy();         // set bfactor to left heavy
    void            SetRightHeavy();        // set bfactor to right heavy

    void            RotateLeft();           // single rotation, left
    void            RotateRight();          // single rotation, right
    void            RotateLeftRight();      // double rotation, left-right
    void            RotateRightLeft();      // double rotation, right-left
  
    void            InsertFixup();          // all fixup's after insertion
    void            RemoveFixup();          // all fixup's before removal

    void            SubTreeHeight(          // determine subtree properties
                      int& i_minh,          //   minimal height to leave node
                      int& i_maxh,          //   maximal height to leave node
                      double& d_nnode,      //   number of nodes
                      double& d_ncomp) const; //   number of compares
    bool            SubTreeCheck(           // check whether subtree is balanced
                      ostream* p_os,
                      int& i_maxh) const;

                    CTBbtreeNode(           // copy constructor DUMMY
                      const CTBbtreeNode& rhs);
    CTBbtreeNode&   operator=(              // assignment operator DUMMY
                      const CTBbtreeNode& rhs);

  private:

    static const CTBuint32 status_lchild    = 0x2;
    static const CTBuint32 status_rchild    = 0x1;
    static const CTBuint32 status_childmask = status_lchild | status_rchild;
    static const CTBuint32 status_lheavy    = 0x8;
    static const CTBuint32 status_rheavy    = 0x4;
    static const CTBuint32 status_heavymask = status_lheavy | status_rheavy;
    static const CTBuint32 status_bitmask   = status_childmask|status_heavymask;
    static const CTBuint32 status_deltaw    = 16;
  
    CTBbtree*       mp_head;                
    CTBbtreeNode*   mp_up;                  
    CTBbtreeNode*   mp_left;                
    CTBbtreeNode*   mp_right;               
    CTBuint32       mi_status;              
};

class CTBclone<CTBbtreeNode> : public CTBcloneable<CTBbtreeNode> {};

// Notes:
// 1. The mi_combo member variable holds 3 different pieces of status info:
//      child mode bits:        bit 0: right child;   bit 1: left child
//      balance factor bits     bit 2: right heavy;   bit 3: left heavy
//      left tree weight (rank) is stored in the bits 4,...,31
//
// 2. The maximum number of nodes is limited to about 2^28 because the left
//    tree weight is stored in only 28 bits. 
//
// 3. The Next() and Prev() member functions clearly allow to break const-ness
//    of a pointer. This is behaviour is uncritical because the functions are
//    only indirectly called through Iterators and Browsers which take care
//    of proper const-ness.

#if !(defined(CTB__OutLine) || defined(CTBbtree__OutLine))
#include "CTBbtree.icc"
#endif

#endif

---