---

CdbBdbSAbsBtreeItr.cc

Go to the documentation of this file.

// File and Version Information:
//      $Id: CdbBdbSAbsBtreeItr.cc,v 1.6 2004/12/08 09:26:54 gapon Exp $

/// Implementation file for the CdbBdbSAbsBtreeItr class
/**
  * @see CdbBdbSAbsBtreeItr
  */

#include "BaBar/BaBar.hh"

#if !defined(OO_DDL_TRANSLATION)
#include "CdbBdbShared/CdbBdbSAbsBtreeItr.hh"
#endif // OO_DDL_TRANSLATION

#include "CdbBdbShared/CdbBdbSAbsBtree.hh"

#include <assert.h>

template< class K,
          class FCP,
          class ORDER >
CdbBdbSAbsBtreeItr<K,FCP,ORDER>::CdbBdbSAbsBtreeItr( const CdbBdbSAbsBtree<K,FCP,ORDER>* theTreePtr ) :
    _myTreePtr(theTreePtr),
    _isValid(false),
    _hasEverBeenAdvanced(false)
{
    assert( 0 != theTreePtr );
}

template< class K,
          class FCP,
          class ORDER >
CdbBdbSAbsBtreeItr<K,FCP,ORDER>::CdbBdbSAbsBtreeItr( const CdbBdbSAbsBtreeItr<K,FCP,ORDER>& theItr ) :
    _myTreePtr(theItr._myTreePtr),
    _isValid(theItr._isValid),
    _hasEverBeenAdvanced(theItr._hasEverBeenAdvanced),
    _node(theItr._node),
    _nodeValue(theItr._nodeValue),
    _currentElement(theItr._currentElement)
{ }

template< class K,
          class FCP,
          class ORDER >
CdbBdbSAbsBtreeItr<K,FCP,ORDER>::~CdbBdbSAbsBtreeItr( )
{ }

template< class K,
          class FCP,
          class ORDER >
CdbStatus
CdbBdbSAbsBtreeItr<K,FCP,ORDER>::reset( )
{
    _isValid             = false;
    _hasEverBeenAdvanced = false;

    return CdbStatus::Success;
}

template< class K,
          class FCP,
          class ORDER >
bool
CdbBdbSAbsBtreeItr<K,FCP,ORDER>::backToParent( )
{
    bool result = false;
    do {

      // Check if the current node has any parent the ROOT node does not).

        if( 0 == _nodeValue.parent ) break;

        d_ULong subjectNode = _node;

        _node      = _nodeValue.parent;
        _nodeValue = _myTreePtr->readNode( _node );

        for( int i = 0; i <= _nodeValue.n; ++i ) {
            if( subjectNode == _nodeValue.child[i] ) {

                if( i == _nodeValue.n ) {

                  // The subject node was the last child in the list of the parent
                  // node. It means that there is no keys next to it. Therefore we shoudl
                  // proceed up to the parent of the parent.

                    result = backToParent( );

                } else {

                  // Okay. The key right to the subject node's link is what we're
                  // loking for.
                  //
                  //        <input>
                  //           |
                  //           V
                  //  [L1]    [L2]    ...      [Ln]
                  //      [k1]    [k2]...[kn-1]
                  //                |
                  //                V
                  //             <output>

                    _currentElement = i;

                    result = true;
                }
                break;
            }
        }

    } while( false );

    return result;
}

template< class K,
          class FCP,
          class ORDER >
bool
CdbBdbSAbsBtreeItr<K,FCP,ORDER>::next( )
{
    if( _hasEverBeenAdvanced ) {

        ++_currentElement;  // Works well for both LEAF and non-LEAF nodes.

        if( _nodeValue.isLeaf ) {

          // The LEAF node

          // If we're past the end of the leaf's keys then we'll
          // try making one step back and keep searching through
          // the parent node.

            if( _currentElement >= _nodeValue.n ) {

                if( ! backToParent( )) {

                  // Okay, we've finished. Put the iterator's state beyond
                  // the last key of the tree.

                    _isValid             = false;
                    _hasEverBeenAdvanced = false;
                }
            }

        } else {

          // Not the LEAF node.

          // Then we propagate down to the child node, which is next
          // to the current key.
          //
          // NOTE: Remember that we've already incremented the index of the element
          //       above. So it refers to the appropriate child.

            _node      = _nodeValue.child[_currentElement];
            _nodeValue = _myTreePtr->readNode( _node );

          // Finally we go down to the key element at the leftmost sub-branch
          // of the tree growing from the above discovered child node.
          //
          // NOTE: The situation is almost (it's a sub-branch) exactly the same
          //       as when we just started iterating from the "root" node
          //       at the very first call to the "next".

            while( ! _nodeValue.isLeaf ) {
                _node      = _nodeValue.child[0];
                _nodeValue = _myTreePtr->readNode( _node );
            }
            _currentElement = 0;
        }

    } else {

      // The very first call to the "next"

      // Then we go down to the smaller key at the leftmost branch
      // of the tree.

        _node      = _myTreePtr->root( );
        _nodeValue = _myTreePtr->readNode( _node );

        while( ! _nodeValue.isLeaf ) {
            _node      = _nodeValue.child[0];
            _nodeValue = _myTreePtr->readNode( _node );
        }

      // The final check, which only makes sense for the ROOT node
      // if it's the only node in the tree (then ROOT also becomes
      // a LEAF node).

        if( _nodeValue.n > 0 ) {

            _isValid             = true;
            _hasEverBeenAdvanced = true;

            _currentElement = 0;
        }
    }
    return _isValid;
}

template< class K,
          class FCP,
          class ORDER >
typename CdbBdbSAbsBtreeItr<K,FCP,ORDER>::ValueType
CdbBdbSAbsBtreeItr<K,FCP,ORDER>::value( )
{
    assert( _isValid );     // Inproper use of the iterator if not advanced or beyond the end.

    return _nodeValue.key[_currentElement];
}

template< class K,
          class FCP,
          class ORDER >
bool
CdbBdbSAbsBtreeItr<K,FCP,ORDER>::isValid( )
{
    return _isValid;
}

template< class K,
          class FCP,
          class ORDER >
typename CdbBdbSAbsBtreeItr<K,FCP,ORDER>::InterfaceType*
CdbBdbSAbsBtreeItr<K,FCP,ORDER>::clone( ) const
{
    return new CdbBdbSAbsBtreeItr<K,FCP,ORDER>( *this );
}

/////////////////
// End Of File //
/////////////////

---