---

CdbRooRoAbsBtreeR.rdl

Go to the documentation of this file.

#ifndef CDBROOREADONLY_ABS_BTREE_R_RDL
#define CDBROOREADONLY_ABS_BTREE_R_RDL

// File and Version Information:
//      $Id: CdbRooRoAbsBtreeR.rdl,v 1.1 2004/11/09 20:33:04 gapon Exp $

#include "Rtypes.h"

#include <iostream>

/// An embeddable node class for the persistent capable B-tree.
/**
  * This template class implement nodes for the corresponding B-tree
  * data structures and related algorithms.
  *
  * The template is parametrized by mean of the following parameters:
  *
  *     K - is a type of keys. This type has to provide the following
  *         methods:
  *
  *             default constructor
  *             copy constructor
  *             destructor
  *
  *         and operators:
  *
  *             =
  *             ==
  *             <
  *             <<    (into std::ostream)
  *
  *     ORDER - is an order of the tree.
  */
template< class  K,
          UInt_t ORDER >
class CdbRooRoBtreeNodeR {

public:

  // The default constructor will create an empty leaf node w/o a parent,
  // with no values and no children. The normal constructor will setup
  // a parent of the node.

    CdbRooRoBtreeNodeR( )          : parent(0), isLeaf(true), n(0) { }
    CdbRooRoBtreeNodeR( UInt_t p ) : parent(p), isLeaf(true), n(0) { }

  // The copy constructor
  /**
    */
    CdbRooRoBtreeNodeR( const CdbRooRoBtreeNodeR<K,ORDER>& theNode )
    {
        copySelf( theNode );
    }

  /// The destructor
  /**
    * NOTE: The destructor is NOT virtual because this is an embedded
    *       class.
    */
    virtual ~CdbRooRoBtreeNodeR( )
    { }

  // The assignment operator
  /**
    */
    CdbRooRoBtreeNodeR<K,ORDER>& operator=( const CdbRooRoBtreeNodeR<K,ORDER>& theNode )
    {
        if( this != &theNode ) copySelf( theNode );
        return *this;
    }

private:

  /// Set up own context from specified one
  /**
    * This helper method is used by constructors and assignment operator.
    */
    void copySelf( const CdbRooRoBtreeNodeR<K,ORDER>& theNode )
    {
        parent = theNode.parent;
        isLeaf = theNode.isLeaf;
        n      = theNode.n;
        for( unsigned int i = 0; i <= 2 * ORDER; ++i ) child[i] = theNode.child[i];
        for( unsigned int i = 0; i <  2 * ORDER; ++i ) key  [i] = theNode.key  [i];
    }

public:

  // Back link to the parent

    UInt_t parent;

  // There are 'n+1' pointers to child nodes.

    UInt_t child[ 2 * ORDER + 1 ];

  // There are 'n' keys in the node. The keys are sorted.

    K key[ 2 * ORDER ];

  // The leaf node does not have any children.

    Bool_t isLeaf;

  // Occupancy for "root" node:     0 .. 2 * ORDER
  //               other nodes: ORDER .. 2 * ORDER

    UInt_t n;

    typedef CdbRooRoBtreeNodeR<K,ORDER> MyType;

    ClassDef(MyType,1);

};

template< class  K,
          UInt_t ORDER >
std::ostream&
operator<<( std::ostream&                      o,
            const CdbRooRoBtreeNodeR<K,ORDER>& theNode )
{
    return o << theNode.parent;
}

/// Default "fuzzy" search logic for entries
/**
  * By default exact match is expected.
  */
template< class K >
class CdbRooRoBtreeDefaultFCPR {

public:

    static bool match( const K& object,
                       const K& subject )
    {
        return object == subject;
    }
};

/// An abstract class for B-tree (balanced tree)
/**
  * This template class implements the corresponding B-tree algorithms
  * for embedded classes. The concrete storage for the B-tree
  * data structures is provided by derived classes.
  *
  * The template is parametrized by mean of the following parameters:
  *
  *     K - is a type of keys. This type has to provide the following
  *         methods:
  *
  *             default constructor
  *             copy constructor
  *             destructor
  *
  *         and operators:
  *
  *             =
  *             ==
  *             <=
  *             >
  *             <<    (into std::ostream)
  *
  *     FCP - this is a policy class that is expected
  *           to provide the only method:
  *
  *         class <name> ... {
  *         public:
  *             static bool match( const K& source,
  *                                const K& target );
  *         };
  *
  *         This meathod is used for one-directional comparision of two
  *         keys. This operation is meant to answer a question if specified
  *         "source" key matches the "target" one.
  *
  *         It's not nessesary true that if "source" matches the "target"
  *         then the "targed" would match the "source" one.
  *
  *         The meaning of the "match" is up to the implementation
  *         of a concrete policy and type of keys (K).
  *
  *     ORDER - is an order of the tree.
  */
template< class  K,
          class  FCP   = CdbRooRoBtreeDefaultFCPR<K>,
          UInt_t ORDER = 4  >
class CdbRooRoAbsBtreeR {

public:

  /// Default constructor.
  /**
    * Creates an empty tree.
    */
    CdbRooRoAbsBtreeR( ) { }

  /// Destructor
  /**
    * Destroys the tree.
    */
    virtual ~CdbRooRoAbsBtreeR( ) { }

  /// Dump the tree
  /**
    * The dump is done onto a stream specified through the only parameter
    * of the method.
    */
    void dump( std::ostream& o ) const
    {
        dump( o, root( ), 0 );
    }

  /// Insert a key into the tree
  /**
    * Insert specified key into the tree. If the tree alredy has
    * such an element then just ignore it.
    */
    void insert( const K& key );

  /// Remove a key from the tree
  /**
    * Remove specified key from the tree. If the tree does not have
    * such an element then just ignore it.
    */
    void remove( const K& key );

  /// Search a key in the tree
  /**
    * This method will only look for the presence of specified
    * key in the tree. If there is such an entry it will just
    * return "true".
    */
    bool search( const K& key ) const
    {
        return 0 != doSearch( root( ),
                              key );
    }

  /// Extended search for a key in the tree
  /**
    * This method will look for the presence of specified
    * key in the tree.
    *
    * If there is such an entry then the method will return "true"
    * and a value of the found ("similar") key.
    */
    bool search( const K& key,
                 K&       result ) const;

  /// Search a key in the tree using "fuzzy" search logic
  /**
    * This method will use "fuzzy" logic to search for a key, which
    * is very similar to the one specified on the input. The "similarity"
    * is defined throught this (Btree) class template parameter.
    *
    * If there is such an entry then the method will return "true"
    * and a value of the found ("similar") key.
    */
    bool fuzzySearch( const K& key,
                      K&       result ) const
    {
        return 0 != doFuzzySearch( root( ),
                                   key,
                                   result );
    }

  /// Reset the tree
  /**
    * This operation will remove all elements from the tree
    * except it's root node. The root node will get 0 keys.
    */
    void reset( )
    {
        reset( root( ));
    }

protected:

  /// Get a root node of the B-tree
  /**
    * To be implemented by a storage provider of a derived class.
    */
    virtual UInt_t root( ) const = 0;

  /// Set new root node of the B-tree
  /**
    * To be implemented by a storage provider of a derived class.
    */
    virtual void set_root( UInt_t node ) = 0;

  /// Get a copy of specified node
  /**
    * To be implemented by a storage provider of a derived class.
    */
    virtual CdbRooRoBtreeNodeR<K,ORDER> readNode( UInt_t node ) const = 0;

  /// Save back the value of specified node
  /**
    * To be implemented by a storage provider of a derived class.
    */
    virtual void updateNode( UInt_t                             node,
                             const CdbRooRoBtreeNodeR<K,ORDER>& value ) = 0;

  /// Allocator
  /**
    * To be implemented by a storage provider of a derived class.
    */
    virtual UInt_t allocate( UInt_t parent = 0 ) = 0;

  /// Disposer
  /**
    * To be implemented by a storage provider of a derived class.
    */
    virtual void release( UInt_t node ) = 0;

private:

    /// A helper for the dump
    /**
      * Insert certain number of spaces into an output stream.
      */
    void spaces( std::ostream& o,
                 unsigned int  level ) const
    {
        for( int i = 0; i < 2*level; ++i ) o << ' ';
    }

    /// Dump a node in the tree (recursive)
    /**
      * This is a recursive method. It will make a dump from specified
      * node through its dircet and indircet leaves.
      */
    void dump( std::ostream& o,
               UInt_t        node,
               unsigned int  level ) const;

    /// The implementation of the search algorithm (recursive)
    /**
      * This method has the following communications:
      *
      * INPUT: A node to start the search with and the value of the key
      *        to look for.
      *
      * OUTPUT: Will return a non 0 address of a node containg the key if
      *         the one was found.
      */
    UInt_t doSearch( UInt_t   node,
                     const K& key ) const;

    /// The "fuzzy" logic implementation of the search algorithm (recursive)
    /**
      * This method has the following communications:
      *
      * INPUT: A node to start the search with and the value of the key
      *        to look for.
      *
      * OUTPUT: Will return a non 0 address of a node cotainig the key if
      *         the one was found. In this case the method will also return
      *         the value of the "approximate" key.
      */
    UInt_t doFuzzySearch( UInt_t   node,
                          const K& key,
                          K&       result ) const;

   /// Search for the leaf node
   /**
     * This algorithm will go down to a node where the specified key is supposed
     * to be insert. An address of that node will be returned.
     */
    UInt_t searchLeafForInsert( UInt_t   node,
                                const K& key ) const;

   /// Insert only a key into a node
   /**
    * This method is equally applied to both leaf and non-leaf nodes.
    */
    void insertKeyOnly( UInt_t   node,
                        const K& key );

   /// Insert a key and replace old link at a node
   /**
    * This method can only be applied to non-leaf nodes that have enough room
    * for one more key. The method will also replace specified old link to a child
    * with two new ones.
    */
    void insertNoSplit( UInt_t   parent,
                        const K& key,
                        UInt_t   old,
                        UInt_t   left,
                        UInt_t   right );

   /// Insert a key, replace old link at a node, then split the node (recursive)
   /**
    * This method can only be applied to non-leaf nodes that is already full.
    */
    void insertAndSplit( UInt_t   parent,
                         const K& key,
                         UInt_t   old,
                         UInt_t   left,
                         UInt_t   right );

   /// Remove a key from a leaf node (recursive)
   /**
    * This method may also rebalance the tree if the number of element
    * in the node is less than allowed (ORDER).
    *
    * NOTE: The minimum restriction of ORDER does not apply to the root node
    *       if it's the only node in the tree.
    */
    void removeFromLeaf( UInt_t   node,
                         const K& key );

   /// Rebalance the tree starting from specified node (recursive)
   /**
    * A node passed to the method is the one having "underflow".
    */
    void rebalance( UInt_t node );

   /// Rebalance the tree by borrowing from a left node (recursive)
   /**
    * This "try" method is used to attemp borrowing a spare key
    * from any node left from the specified one.
    *
    * CONDITION: There's at least one node on the left possesing more
    *            than ORDER keys.
    */
    bool borrowFromLeft( UInt_t right );

   /// Rebalance the tree by borrowing from a right node (recursive)
   /**
    * This "try" method is used to attemp borrowing a spare key
    * from any node right from the specified one.
    *
    * CONDITION: There's at least one node on the right possesing more
    *            than ORDER keys.
    */
    bool borrowFromRight( UInt_t left );

   /// Rebalance the tree by joining with a neighbor node of the same parent
   /**
    * This "force" method will join with either neighbor,
    */
    void join( UInt_t node );

  /// Reset a sub-tree beneath (excluding) specified node (recursive)
  /**
    * This is a helper method.
    */
    void reset( UInt_t node );
};

// Template class implementation

#ifndef __CINT__
#include "CdbRooReadonly/CdbRooRoAbsBtreeR.cc"
#endif
#endif  // CDBROOREADONLY_ABS_BTREE_R_RDL

---