gbtree.h

来自「开放源码的编译器open watcom 1.6.0版的源代码」· C头文件 代码 · 共 526 行 · 第 1/2 页

    // Shift all the keys and subtrees, beginning at position pos,
    // right by the given amount. Note that the subtree to the left of
    // key[pos] is {\it also\/} moved.

    virtual void ShiftLeftAt (short pos, short amount = 1);
    // Shift all the keys and subtrees, beginning at position pos,
    // left by the given amount. Note that the subtree to the left of
    // key[pos] is {\it also\/} moved.

    virtual void MoveSubNode (const CL_GenericBTreeNode& x, short pos,
                      short our_pos, short nkeys);
    // MoveSubNode: Move {\it nkeys\/} keys, and their left and right
    // subtrees, beginning from position pos in node $x$ into ourselves
    // beginning at position {\it our_pos}.


    // --------------------- End public protocol -----------------------


protected:

    CL_AbstractComparator& _cmp;      // Comparator must be initialized
                                      // BEFORE NodeSpace is initialized
    CL_BTreeNodeSpace*   _nodeSpace;  
    CL_BTreeNodeHandle* _subtree;     // Pointer to array of subtree handles
    CL_VoidPtr*         _item;        // Pointer to array of items
    short               _keyCount;    // # keys in node
    bool                _isLeaf;      // Is this node a leaf?
    long                _subtreeSize; // # keys in subtree rooted at this node

    CL_BTreeNodeHandle  _handle;      // Our handle
    short               _order;

    friend CL_GenericBTree;
    friend CL_GenericBTreeIterator;
    friend CL_BTreeNodeSpace;
 
    // ---------------- Construction and destruction ---------------
    
    CL_GenericBTreeNode (short order, CL_BTreeNodeSpace* space,
                         CL_AbstractComparator& cmp);
    // Constructor: create a node of the B-tree with given order.

    virtual ~CL_GenericBTreeNode();
    // Destructor.

};




// The NodeSpace is the space in which tree nodes are stored. Nodes in
// this space are accessed via handles encapsulated by the
// SubTreeHandle class. The NodeSpace functions as a kind of "node
// library" from which nodes can be "borrowed" and "returned."
// Borrowed nodes can be modified, in which case the NodeSpace must be
// informed of the modification via the NodeModified method.
//
// The BTree class assumes that the NodeSpace class provides the
// following primitives:
// \par\begin{tabular}{lp{3.5truein}}
//    RootHandle, & which returns the handle of the root of the
//                  tree \\
//    Root, &       which returns a raw C++ pointer to the root \\
//    NewRoot, &    which modifies the root handle\\
//    CreateNode, & which creates a new node in the NodeSpace and
//                  returns a handle to it. \\
//    BorrowNode, & which returns a raw C++ pointer to the node
//                  specified by the given handle. This pointer
//                  points to space owned by NodeSpace. \\
//    ReturnNode, & which informs the NodeSpace that the caller
//                  done with the node \\
//    NodeModified,&which tells the NodeSpace that the caller
//                  has modified the specified node (but is not
//                  necessarily done with that node yet) \\
//    DestroyNode,& which destroys the given node, and invalidates
//                  its handle. \\
// \end{tabular}\par
// The default implementation is for the node space on the heap, so that
// translation between node handles and pointers is trivial.


class CL_BTreeNodeSpace  {

public:
    CL_BTreeNodeSpace (short order, const CL_GenericBTree& tree,
                       CL_AbstractComparator& cmp);
    // Construct a new NodeSpace.

    virtual ~CL_BTreeNodeSpace () {};
    
    // --------------- Essential (core) functions ----------------
    
    virtual CL_BTreeNodeHandle   RootHandle () const = 0;

    virtual void                 NewRoot (CL_BTreeNodeHandle h) = 0;
    
    virtual CL_BTreeNodeHandle   CreateNode () = 0;

    virtual void                 DestroyNode (CL_GenericBTreeNode*) = 0;

    virtual CL_GenericBTreeNode* BorrowNode (CL_BTreeNodeHandle h) const = 0;
    //  Return a null pointer if the handle h is zero.
    
    virtual void                 ReturnNode (CL_GenericBTreeNode* ) const = 0;
    
    virtual void                 NodeModified (CL_GenericBTreeNode*) = 0;
    

    // -------------------- Convenience functions --------------------
    
    CL_GenericBTreeNode* BorrowRoot () const
        {return BorrowNode (RootHandle());};
    // Convenience function to borrow the root of the tree.

    void WriteBack (CL_GenericBTreeNode* node)
        { NodeModified (node); ReturnNode (node);};
    // Convenience function that calls {\small\tt NodeModified} and then
    // {\small\tt ReturnNode}.

    CL_GenericBTreeNode*  MakeNode () 
        { return BorrowNode (CreateNode());};
    // Convenience function that creates a new node and then borrows it.

    virtual void DestroyItem (CL_VoidPtr) const {};
    // Destroy the item pointed to by the parameter. This method is called
    // for each item of a node when the node is being destroyed. The default
    // implementation does nothing; derived classes may override this method.

    // --------------------- End public protocol -----------------------

protected:
    short _order;
    CL_AbstractComparator& _cmp;    // Declare _cmp before _tree, to
                                    // initialize in correct order
    const CL_GenericBTree& _tree;

    virtual CL_GenericBTreeNode* _BuildNode () const
        {return new CL_GenericBTreeNode (_order, (CL_BTreeNodeSpace*)
                                         this, _cmp);};
    // Create an empty node and return it. This method is
    // meant for use by derived classes, since the BTreeNode constructor is
    // protected.
    
    virtual void _Destroy (CL_GenericBTreeNode* node) const;
    // Call {\tt delete} on the parameter. The default implementation
    // invokes DestroyItem on each contained item, and then destroys the
    // node. This method is
    // meant for use by derived classes, since the BTreeNode destructor is
    // protected.

    virtual void _SetHandle (CL_GenericBTreeNode& node,
                             CL_BTreeNodeHandle h) const
        {node._handle = h;};
    // Set the handle of {\tt node} to {\tt h}. This method is
    // meant for use by derived classes.
    

};



inline CL_BTreeNodeSpace::CL_BTreeNodeSpace
    (short order, const CL_GenericBTree& tree, CL_AbstractComparator& cmp)
: _order (order), _cmp (cmp), _tree (tree)
{
};


 

class CL_GenericBTreeIterator {

public:
    CL_GenericBTreeIterator (const CL_GenericBTree& t);
    // Constructor: create a BTreeIterator for the given tree t.

    CL_GenericBTreeIterator (const CL_GenericBTreeIterator& itr);
    // Copy constructor. The copy inspects the same B-tree as {\tt itr}, and
    // (unless reset) begins  its iteration at the item at which {\tt itr}
    // is currently positioned.
    
    virtual ~CL_GenericBTreeIterator();
    // Destructor.
    
    void Reset();
    // Reset the iterator to the leftmost (smallest) item.
    
    void BeginFrom (CL_VoidPtr p);
    // Begin the iteration from the given item (or the one immediately
    // larger, if the given item isn't in the tree).
    
    bool More();
    // Tell whether there are more items in the iteration.
    
    CL_VoidPtr Next();
    // Return the next item in the iteration sequence. Return the NULL
    // pointer if no more items.

    long CurrentRank () const {return _index;};
    // Return the rank of the element that was returned by the most recent
    // call to Next().
    
    // --------------------- End public protocol -----------------------

 
protected:
    CL_VoidPtr                  _path;      // Stack containing path to
                                            // current element
    short                       _length;    // Length of stack
    long                        _index;     // Rank of  element most recently
                                            // returned by Next
    const      CL_GenericBTree& _tree;      // The tree being inspected
    
};










class CL_HeapBTreeNodeSpace: public CL_BTreeNodeSpace {

public:
    CL_HeapBTreeNodeSpace (short order, const CL_GenericBTree& tree,
                           CL_AbstractComparator& cmp);

    ~CL_HeapBTreeNodeSpace ();
    
    virtual CL_BTreeNodeHandle RootHandle () const { return _root; };

    virtual void NewRoot (CL_BTreeNodeHandle h) { _root = h; };
    
    virtual CL_BTreeNodeHandle CreateNode ();

    virtual CL_GenericBTreeNode* BorrowNode (CL_BTreeNodeHandle h) const;
    
    virtual void ReturnNode (CL_GenericBTreeNode* ) const;
    
    virtual void NodeModified (CL_GenericBTreeNode*) {};
    
    virtual void DestroyNode (CL_GenericBTreeNode* node);

    // --------------------- End public protocol -----------------------

protected:
    CL_BTreeNodeHandle _root;

    void               _DestroySubtree (CL_BTreeNodeHandle h);
    
};




#endif