btree.cpp

uc/os 很好的学习代码

}

Object& Btree::findMember( Object& o ) const
{
    if( !o.isSortable() )
        ClassLib_error(__ENOTSORT);
    if( root == 0 )
        return NOOBJECT;
    else
        {
        Node* loc;
        int idx;
        return root->found(&(Sortable&)o, &loc, &idx);
        }
}

void Btree::printOn( ostream& out ) const
{
    if( root == 0 )
        out << "<empty>" ;
    else
        root->printOn(out);
}

extern "C" void __ErrorMessage( const char * );

int Btree::isEqual( const Object& obj ) const
{
    if( obj.isA() == btreeClass )
        {
        __ErrorMessage( "Btree isEqual not implemented\n" );
        exit(1);
        }
    return 0;

    // two btrees are equal only if they have the same number of
    // elements, and they are all equal.  The structure of the tree
    // itself doesn't enter into it.
}


long Btree::i_add( const Object& o )
{
    long r;
    if( !o.isSortable() )
        ClassLib_error( __ENOTSORT );
    if( root == 0 )
        {
        root = new LeafNode( 0, &(Sortable&)o, this );
        CHECK( root != 0 );
        incrNofKeys();
        r = 0;
        }
    else
        {
        Node* loc;
        int idx;
        if( root->found(&(Sortable&)o, &loc, &idx) != NOOBJECT )
            {
            // loc and idx are set to either where the object
            // was found, or where it should go in the Btree.
            // Nothing is here now, but later we might give the user
            // the ability to declare a B-tree as `unique elements only',
            // in which case we would handle an exception here.
            // cerr << "Multiple entry warning\n";
            }
        else
            {
            CHECK( loc->isLeaf );
            }
        if( loc->isLeaf )
            {
            if( loc->parent == 0 )
                r = idx;
            else
                r = idx + loc->parent->findRank_bu( loc );
            }
        else
            {
            InnerNode *iloc = (InnerNode*)loc;
            r = iloc->findRank_bu( iloc->getTree( idx ) );
            }
        loc->add( &(Sortable&)o, idx );
        }
    CHECK( r == rank( (Sortable&)o ) || (Sortable&)o == (*this)[r] );
    return r;
}

void Btree::add( Object& o )
{
    if( !o.isSortable() )
        ClassLib_error( __ENOTSORT );
    if (root == 0)
        {
        root = new LeafNode( 0, &(Sortable&)o, this );
        CHECK( root != 0 );
        incrNofKeys();
        }
    else
        {
        Node* loc;
        int idx;
        if( root->found(&(Sortable&)o, &loc, &idx) != NOOBJECT )
            {
            // loc and idx are set to either where the object
            // was found, or where it should go in the Btree.
            // Nothing is here now, but later we might give the user
            // the ability to declare a B-tree as `unique elements only',
            // in which case we would handle an exception here.
            }
        loc->add( &(Sortable&)o, idx );
        }
}

void Btree::detach( Object& o, DeleteType dt )
{
    if( !o.isSortable() )
        ClassLib_error(__ENOTSORT);
    if( root == 0 )
        return;

    Node* loc;
    int idx;
    Object* obj = &(root->found( &(Sortable&)o, &loc, &idx ));
    if( *obj == NOOBJECT )
        return;
    loc->remove( idx );
    if( delObj(dt) )
        delete obj;
}

void Btree::rootIsFull()
{
    // the root of the tree is full; create an InnerNode that
    // points to it, and then inform the InnerNode that it is full.
    Node* oldroot = root;
    root = new InnerNode( 0, this, oldroot );
    CHECK( root != 0 );
    oldroot->split();
}

void Btree::rootIsEmpty()
{
    if( root->isLeaf )
        {
        LeafNode* lroot = (LeafNode*)root;
        CHECK( lroot->Psize() == 0 );
        delete lroot;
        root = 0;
        }
    else {
        InnerNode* iroot = (InnerNode*)root;
        CHECK(iroot->Psize() == 0);
        root = iroot->getTree(0);
        root->parent = 0;
        delete iroot;
        }
}

Item::Item()
{
    nofKeysInTree = 0;
    tree = 0;
    key = 0;
}

Item::Item(Node* n, Sortable* o)
{
    nofKeysInTree = n->nofKeys()+1;
    tree = n;
    key = o;
}

Item::Item(Sortable* o, Node* n)
{
    nofKeysInTree = n->nofKeys()+1;
    tree = n;
    key = o;
}

Item::~Item()
{
}

//
//====== Node functions ======
//

Node::Node(int isleaf, InnerNode* P, Btree* T)
{
    // nofElts = 0;
    last = -1;
    /*dbg*/debugKey = 1017; // !*!*!* not for distribution
    isLeaf = isleaf;
    parent = P;
    if( P == 0 )
        {
        CHECK( T != 0 );
        tree = T;
        }
    else
        tree = P->tree;
}

Node::~Node()
{
}

//
//===== BtreeIterator methods =====
//

void BtreeIterator::restart()
{
    index = 0;
}

Object& BtreeIterator::operator++()
{
    return beingIterated[++index];
}

Object& BtreeIterator::operator++( int )
{
    return beingIterated[index++];
}

Object& BtreeIterator::current()
{
    return beingIterated[index];
}


ContainerIterator&
Btree::initIterator() const
{
    return *( (ContainerIterator *)new BtreeIterator( *this ) );
}

BtreeIterator::~BtreeIterator()
{
}


BtreeIterator::operator int()
{
    return index < beingIterated.getItemsInContainer();
}