---

CdbBdbSTimeLineP.cc

Go to the documentation of this file.

// File and Version Information:
//      $Id: CdbBdbSTimeLineP.cc,v 1.7 2004/12/08 09:26:55 gapon Exp $

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

#include "BaBar/BaBar.hh"

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

#include "CdbBdbShared/CdbBdbSTimeLineNodeItr.hh"
using std::cout;
using std::endl;
using std::ostream;

template< class V >
CdbBdbSTimeLineP<V>::CdbBdbSTimeLineP( )
{
  // Initialize with the value built using the default
  // value's class constructor

    initialize( V( ));
}

template< class V >
CdbBdbSTimeLineP<V>::CdbBdbSTimeLineP( const V& theInitialValue )
{
  // Initialize with specified value

    initialize( theInitialValue );
}

template< class V >
CdbBdbSTimeLineP<V>::~CdbBdbSTimeLineP( ) 
{
    BdbDelete( _indexRef );
    BdbDelete( _bufRef );
}

template< class V >
CdbStatus
CdbBdbSTimeLineP<V>::insert( const BdbTime& theBeginTime,
                             const BdbTime& theEndTime,
                             const V&       theValue )
{
    const char* errorMsg = "CdbBdbSTimeLineP<V>::insert() -- ERROR";

    ooUpdate( );

    CdbStatus result = CdbStatus::Error;
    do {

      // Verify parameters.

        if( theBeginTime >= theEndTime ) {
            cout << errorMsg << endl << "    Illegal interval passed to the procedure." << endl;
            break;
        }

      // Determine the range of "timeline intervals" indexes to be affected
      // by this insertion.
      //
      // NOTE: Intervals have the following semantics: [begin,end)

        d_ULong begin = 0;
        {
            BTreeEntry e;
            if( _indexRef->fuzzySearch( BTreeEntry( theBeginTime ), e )) begin = e.value;
        }
        d_ULong end = 0;
        {
            BTreeEntry e;
            if( _indexRef->fuzzySearch( BTreeEntry( theEndTime ), e )) end = e.value;
            if( 0 == end ) end = _last;
        }
        if(( 0 == begin ) || ( 0 == end )) {
            cout << errorMsg << endl << "    Failed to find existing interval in the B-tree index." << endl;
            break;
        }
        
      // Choose among two major scenarious:
      //
      // A: the new interval only affects just one interval
      // B: there are 2 or more intervals affected

        if( begin == end ) {

            insertAndRemoveOne( begin,
                                theBeginTime,
                                theEndTime,
                                theValue );
        } else {

            insertAndRemoveMany( begin,
                                 end,
                                 theBeginTime,
                                 theEndTime,
                                 theValue );
        }

      // Done.

        result = CdbStatus::Success;

    } while( false );

    return result;
}

template< class V >
CdbStatus
CdbBdbSTimeLineP<V>::insert( const CdbBdbSTimeLineInterval< V >& theInterval )
{
    return insert( theInterval.begin,
                   theInterval.end,
                   theInterval.value );
}

template< class V >
bool
CdbBdbSTimeLineP<V>::findAtBegin( CdbBdbSTimeLineInterval< V >& theInterval,
                                  const BdbTime&                theTime ) const
{
    BTreeEntry e;

    if( _indexRef->search( BTreeEntry( theTime ), e )) {
        theInterval = (_bufRef->elementAt( e.value )).interval( );
        return true;
    }
    return false;
}

template< class V >
bool
CdbBdbSTimeLineP<V>::find( CdbBdbSTimeLineInterval< V >& theInterval,
                           const BdbTime&                theTime ) const
{
    BTreeEntry e;

    if( _indexRef->fuzzySearch( BTreeEntry( theTime ), e )) {
        theInterval = (_bufRef->elementAt( e.value )).interval( );
        return true;
    }
    return false;
}

template< class V >
CdbStatus
CdbBdbSTimeLineP<V>::first( CdbBdbSTimeLineInterval< V >& theInterval ) const
{
    theInterval = (_bufRef->elementAt( _first )).interval( );
    return CdbStatus::Success;
}

template< class V >
CdbStatus
CdbBdbSTimeLineP<V>::last( CdbBdbSTimeLineInterval< V >& theInterval ) const
{
    theInterval = (_bufRef->elementAt( _last )).interval( );
    return CdbStatus::Success;
}

template< class V >
typename CdbBdbSTimeLineP<V>::IteratorOfIntervals
CdbBdbSTimeLineP<V>::iterator( const BdbTime& theBeginTime ) const
{
  // Find out the very first element to begin iteration with.

    d_ULong firstIndex = _first;
    if( theBeginTime > BdbTime::minusInfinity ) {

      // Zero index means an empty collection. See the implementation
      // of the iterator.

        firstIndex = 0;
        if( theBeginTime < BdbTime::plusInfinity ) {

            BTreeEntry e;
            if( _indexRef->fuzzySearch( BTreeEntry( theBeginTime ), e )) {
                firstIndex = e.value;
            }
        }
    }

  // ATTENTION: This is not a memory leak - the created object
  //            will be destroyed by the iterator.

    return IteratorOfIntervals( new CdbBdbSTimeLineNodeItr<V>( _bufRef, firstIndex ));
}

template< class V >
void
CdbBdbSTimeLineP<V>::dump( ostream&       o,
                           const BdbTime& theBeginTime,
                           const BdbTime& theEndTime )
{
    const char* errorMsg = "CdbBdbSTimeLineP<V>::dump() -- ERROR";

    do {

      // Verify parameters.

        if( theBeginTime >= theEndTime ) {
            cout << errorMsg << endl << "    Illegal interval passed to the procedure." << endl;
            break;
        }

      // Determine the range of interval indexes to be included
      // into this operation.
      //
      // NOTE: Intervals have the following semantics: [begin,end)

        d_ULong begin = 0;
        {
            BTreeEntry e;
            if( _indexRef->fuzzySearch( BTreeEntry( theBeginTime ), e )) begin = e.value;
        }
        d_ULong end = 0;
        {
            BTreeEntry e;
            if( _indexRef->fuzzySearch( BTreeEntry( theEndTime ), e )) end = e.value;
            if( 0 == end ) end = _last;
        }
        if(( 0 == begin ) || ( 0 == end )) {
            cout << errorMsg << endl << "    Failed to find an interval in the B-tree index." << endl;
            break;
        }

      // Do the dump

        d_ULong next = begin;
        do {

            Node n = _bufRef->elementAt( next );

            o << next << " : [ " << n.begin.getGmtSec( ) << "." << n.begin.getGmtNsec( ) << " , "
              <<                    n.end.getGmtSec( )   << "." << n.end.getGmtNsec( )   << " ) "
              << n.prev << "< >" << n.next << " : " << n.value  << endl;

            if( next == end ) break;
            else              next = n.next;

        } while( 0 != next );

    } while( false );
}

template< class V >
CdbStatus
CdbBdbSTimeLineP<V>::clone( BdbRef(CdbBdbSTimeLineP<V>)& theRef,
                            const BdbRefAny&             theHint ) const
{
    const char* errorMsg = "CdbBdbSTimeLineP<V>::clone() -- ERROR";

  // Calculate the hint

    BdbRefAny hint = theHint;
    if( BdbIsNull(hint)) hint = ooThis( );

  // Create an empty object

    theRef = new( hint ) CdbBdbSTimeLineP<V>( );

  // Just copy the "timeline" intervals from the current object into
  // the new one.

    d_ULong next = _first;
    do {
        Node n = _bufRef->elementAt( next );

        CdbStatus status = theRef->insert( n.begin,
                                           n.end,
                                           n.value );
        if( CdbStatus::Success != status ) {
            cout << errorMsg << endl
                 << "    Failed to insert new interval: " << n.interval( ) << endl
                 << "    from input object into the output one." << endl;
            return status;
        }
        next = n.next;

    } while( 0 != next );

    return CdbStatus::Success;
}

template< class V >
void
CdbBdbSTimeLineP<V>::initialize( const V& theInitialValue )
{
  // Element 0 is never used.

    _bufRef   = new( ooThis( )) CdbBdbSPagedVarrayP< Node >( 1 );
    _indexRef = new( ooThis( )) CdbBdbSBtreeP< BTreeEntry, BTreeEntryFCP >( );

  // Initialize a list of free elements as the empty one.
  // The elements will be added as required.

    _free = 0;

  // Initialize a list by inserting specifying interval covering the whole range
  // of the timeline.

    _first = allocate( );
    {
        BdbTime beginTime = BdbTime::minusInfinity;
        BdbTime endTime   = BdbTime::plusInfinity;

        _bufRef->setElementAt( _first, Node( theInitialValue, beginTime, endTime ));
        _indexRef->insert( BTreeEntry( beginTime, endTime, _first ));
    }
    _last = _first;
}

template< class V >
void
CdbBdbSTimeLineP<V>::insertAndRemoveOne( d_ULong        begin,
                                         const BdbTime& beginTime,
                                         const BdbTime& endTime,
                                         const V&       value )
{
  // (A) Here we have four further scenarious:
  //
  // A.1: the new interval completelly replaces the old on
  // A.2: the new interval starts with the begining of the old one
  // A.3: the new interval ends up at the end of the old one
  // A.4: the new interval falls in the middle of the old one

    Node beginN = _bufRef->elementAt( begin );

    if(( beginTime == beginN.begin ) && ( endTime == beginN.end )) {

      // (A.1) Just update the value stored in this interval

        beginN.value = value;
        _bufRef->setElementAt( begin, beginN );

    } else {
        
      // Remove old interval out of the list and the B-tree.
      //
      // REMEMBER: That we still have a copy of the value of this element
      //           obtained above. So the removal operation would not affect
      //           this copy.

        _indexRef->remove( BTreeEntry( beginN.begin ));
        release( begin );

        if( beginTime == beginN.begin ) {

          // (A.2) Replace the old interval with two new ones.

            d_ULong first  = allocate( );
            d_ULong second = allocate( );

            Node firstN( value,
                         beginTime,
                         endTime,
                         beginN.prev,
                         second );
            _bufRef->setElementAt( first, firstN );

            Node secondN( beginN.value,
                          endTime,
                          beginN.end,
                          first,
                          beginN.next );
            _bufRef->setElementAt( second, secondN );

          // Update links to point onto new elements instead the old one.

            if( 0 == firstN.prev ) {
                _first = first;
            } else {
                Node prevN = _bufRef->elementAt( firstN.prev );
                { prevN.next  = first; }
                _bufRef->setElementAt( firstN.prev, prevN );
            }
            if( 0 == secondN.next ) {
                _last = second;
            } else {
                Node nextN = _bufRef->elementAt( secondN.next );
                { nextN.prev  = second; }
                _bufRef->setElementAt( secondN.next, nextN );
            }

          // Update the B-tree index

            _indexRef->insert( BTreeEntry( firstN.begin,
                                           firstN.end,
                                           first ));
            _indexRef->insert( BTreeEntry( secondN.begin,
                                           secondN.end,
                                           second ));

        } else if( endTime == beginN.end ) {

          // (A.3) Replace the old interval with two new ones.

            d_ULong first  = allocate( );
            d_ULong second = allocate( );

            Node firstN( beginN.value,
                         beginN.begin,
                         beginTime,
                         beginN.prev,
                         second );
            _bufRef->setElementAt( first, firstN );

            Node secondN( value,
                          beginTime,
                          endTime,
                          first,
                          beginN.next );
            _bufRef->setElementAt( second, secondN );

          // Update links to point onto new elements instead the old one.

            if( 0 == firstN.prev ) {
                _first = first;
            } else {
                Node prevN = _bufRef->elementAt( firstN.prev );
                { prevN.next  = first; }
                _bufRef->setElementAt( firstN.prev, prevN );
            }
            if( 0 == secondN.next ) {
                _last = second;
            } else {
                Node nextN = _bufRef->elementAt( secondN.next );
                { nextN.prev  = second; }
                _bufRef->setElementAt( secondN.next, nextN );
            }

          // Update the B-tree index

            _indexRef->insert( BTreeEntry( firstN.begin,
                                           firstN.end,
                                           first ));
            _indexRef->insert( BTreeEntry( secondN.begin,
                                           secondN.end,
                                           second ));
        } else {

          // (A.4) Replace the old interval with three new ones.

            d_ULong first  = allocate( );
            d_ULong second = allocate( );
            d_ULong third  = allocate( );

            Node firstN( beginN.value,
                         beginN.begin,
                         beginTime,
                         beginN.prev,
                         second );
            _bufRef->setElementAt( first, firstN );

            Node secondN( value,
                          beginTime,
                          endTime,
                          first,
                          third );
            _bufRef->setElementAt( second, secondN );

            Node thirdN( beginN.value,
                         endTime,
                         beginN.end,
                         second,
                         beginN.next );
            _bufRef->setElementAt( third, thirdN );

          // Update links to point onto new elements instead the old one.

            if( 0 == firstN.prev ) {
                _first = first;
            } else {
                Node prevN = _bufRef->elementAt( firstN.prev );
                { prevN.next  = first; }
                _bufRef->setElementAt( firstN.prev, prevN );
            }
            if( 0 == thirdN.next ) {
                _last = third;
            } else {
                Node nextN = _bufRef->elementAt( thirdN.next );
                { nextN.prev  = third; }
                _bufRef->setElementAt( thirdN.next, nextN );
            }

          // Update the B-tree index

            _indexRef->insert( BTreeEntry( firstN.begin,
                                           firstN.end,
                                           first ));
            _indexRef->insert( BTreeEntry( secondN.begin,
                                           secondN.end,
                                           second ));
            _indexRef->insert( BTreeEntry( thirdN.begin,
                                           thirdN.end,
                                           third ));
        }
    }
}

template< class V >
void
CdbBdbSTimeLineP<V>::insertAndRemoveMany( d_ULong        begin,
                                          d_ULong        end,
                                          const BdbTime& beginTime,
                                          const BdbTime& endTime,
                                          const V&       value )
{
  // (B) Remove two or more old intervals and replace them with:
  //
  // B.1: Just one interval if it covers everything
  // B.2: Two intervals, if the new one begins where the old begin begins
  // B.3: Two intervals, if the new one ends where the old end ends
  // B.4: Three intervals otherwise

    Node beginN = _bufRef->elementAt( begin );
    Node endN   = _bufRef->elementAt( end );

  // Remove all intervals in between (if any)

    if( beginN.next != end ) {

        d_ULong next = beginN.next;
        while(( 0 != next ) && ( next != end )) {
            Node nextN = _bufRef->elementAt( next );
            _indexRef->remove( BTreeEntry( nextN.begin ));
            release( next );
            next = nextN.next;
        }
    }

  // Then we're going to remove old begin and old end intervals

    _indexRef->remove( BTreeEntry( beginN.begin ));
    release( begin );

    _indexRef->remove( BTreeEntry( endN.begin ));
    release( end );

    if(( beginTime == beginN.begin ) && ( endTime == endN.end )) {

      // (B.1) Replace with one interval

        d_ULong first = allocate( );

        Node firstN( value,
                     beginTime,
                     endTime,
                     beginN.prev,
                     endN.next );
        _bufRef->setElementAt( first, firstN );

      // Update links to point onto new element instead the old ones.

        if( 0 == firstN.prev ) {
            _first = first;
        } else {
            Node prevN = _bufRef->elementAt( firstN.prev );
            { prevN.next  = first; }
            _bufRef->setElementAt( firstN.prev, prevN );
        }
        if( 0 == firstN.next ) {
            _last = first;
        } else {
            Node nextN = _bufRef->elementAt( firstN.next );
            { nextN.prev  = first; }
            _bufRef->setElementAt( firstN.next, nextN );
        }

      // Update the B-tree index

        _indexRef->insert( BTreeEntry( firstN.begin,
                                       firstN.end,
                                       first ));
    } else if( beginTime == beginN.begin ) {

      // (B.2) Replace with two intervals with new "original interval" index
      //       at the begining.

        d_ULong first  = allocate( );
        d_ULong second = allocate( );

        Node firstN( value,
                     beginTime,
                     endTime,
                     beginN.prev,
                     second );
        _bufRef->setElementAt( first, firstN );

        Node secondN( endN.value,
                      endTime,
                      endN.end,
                      first,
                      endN.next );
        _bufRef->setElementAt( second, secondN );

      // Update links to point onto new elements instead the old one.

        if( 0 == firstN.prev ) {
            _first = first;
        } else {
            Node prevN = _bufRef->elementAt( firstN.prev );
            { prevN.next  = first; }
            _bufRef->setElementAt( firstN.prev, prevN );
        }
        if( 0 == secondN.next ) {
            _last = second;
        } else {
            Node nextN = _bufRef->elementAt( secondN.next );
            { nextN.prev  = second; }
            _bufRef->setElementAt( secondN.next, nextN );
        }

      // Update the B-tree index

        _indexRef->insert( BTreeEntry( firstN.begin,
                                       firstN.end,
                                       first ));
        _indexRef->insert( BTreeEntry( secondN.begin,
                                       secondN.end,
                                       second ));

    } else if( endTime == endN.end ) {

      // (B.3) Replace with two intervals with new "original interval" index
      //       at the end.

        d_ULong first  = allocate( );
        d_ULong second = allocate( );

        Node firstN( beginN.value,
                     beginN.begin,
                     beginTime,
                     beginN.prev,
                     second );
        _bufRef->setElementAt( first, firstN );

        Node secondN( value,
                      beginTime,
                      endTime,
                      first,
                      endN.next );
        _bufRef->setElementAt( second, secondN );

      // Update links to point onto new elements instead the old one.

        if( 0 == firstN.prev ) {
            _first = first;
        } else {
            Node prevN = _bufRef->elementAt( firstN.prev );
            { prevN.next  = first; }
            _bufRef->setElementAt( firstN.prev, prevN );
        }
        if( 0 == secondN.next ) {
            _last = second;
        } else {
            Node nextN = _bufRef->elementAt( secondN.next );
            { nextN.prev  = second; }
            _bufRef->setElementAt( secondN.next, nextN );
        }

      // Update the B-tree index

        _indexRef->insert( BTreeEntry( firstN.begin,
                                       firstN.end,
                                       first ));
        _indexRef->insert( BTreeEntry( secondN.begin,
                                       secondN.end,
                                       second ));

    } else {

      // (B.4) Replace with three intervals with new "original interval" index
      //       in the middle.

        d_ULong first  = allocate( );
        d_ULong second = allocate( );
        d_ULong third  = allocate( );

        Node firstN( beginN.value,
                     beginN.begin,
                     beginTime,
                     beginN.prev,
                     second );
        _bufRef->setElementAt( first, firstN );

        Node secondN( value,
                      beginTime,
                      endTime,
                      first,
                      third );
        _bufRef->setElementAt( second, secondN );

        Node thirdN( endN.value,
                     endTime,
                     endN.end,
                     second,
                     endN.next );
        _bufRef->setElementAt( third, thirdN );

      // Update links to point onto new elements instead the old one.

        if( 0 == firstN.prev ) {
            _first = first;
        } else {
            Node prevN = _bufRef->elementAt( firstN.prev );
            { prevN.next  = first; }
            _bufRef->setElementAt( firstN.prev, prevN );
        }
        if( 0 == thirdN.next ) {
            _last = third;
        } else {
            Node nextN = _bufRef->elementAt( thirdN.next );
            { nextN.prev  = third; }
            _bufRef->setElementAt( thirdN.next, nextN );
        }

      // Update the B-tree index

        _indexRef->insert( BTreeEntry( firstN.begin,
                                       firstN.end,
                                       first ));
        _indexRef->insert( BTreeEntry( secondN.begin,
                                       secondN.end,
                                       second ));
        _indexRef->insert( BTreeEntry( thirdN.begin,
                                       thirdN.end,
                                       third ));
    }
}

template< class V >
d_ULong
CdbBdbSTimeLineP<V>::allocate( d_ULong next )
{
    if( _free == 0 ) extend_free_list( );

    d_ULong result = _free;
    {
        _free = _bufRef->elementAt( result ).next;
    }
    return result;
}

template< class V >
void
CdbBdbSTimeLineP<V>::release( d_ULong element )
{
    if( element ) {

        Node n = _bufRef->elementAt( element );
        { n.next = _free; }
        _bufRef->setElementAt( element, n );

        _free = element;
    }
}

template< class V >
void
CdbBdbSTimeLineP<V>::extend_free_list( )
{
    if( _free == 0 ) {

        const d_ULong sizeIncrement = 1000;

        _free = _bufRef->size( );
        _bufRef->resize( _free + sizeIncrement );

        for( d_ULong element = _free + 1; element < _free + sizeIncrement; ++element ) {

          // End Of the List

            Node endN = _bufRef->elementAt( element );
            { endN.next = 0; }
            _bufRef->setElementAt( element, endN );

          // Previous node points to the current one

            Node previousN = _bufRef->elementAt( element - 1 );
            { previousN.next = element; }
            _bufRef->setElementAt( element - 1, previousN );
        }
    }
}

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

---