Disk-Based Container Objects

Listing 2: bintree.h — Disk-based binary search tree

#ifndef __BINTREE_H
#define __BINTREE_H
#include "listman.h"
#include "vector.h"

/* Select node type and file management scheme */
#define Nd   TDBinarySearchTreeNode
#ifndef FM
#define FM   DirectFile  /* CachedFile on code disk */
#endif
#define CACHESIZE   25  /* #default cache nodes */

template <class T> class TDBinarySearchTree
{
    TDListManager<Nd<T>, FM> *_Lm;
  public:
    TDBinarySearchTree( const char *fname = 0,
                        int nn = CACHESIZE)    {
        _Lm = new TDListManager
               <Nd<T>, FM> (fname, nn, 0);
    }
    ~TDBinarySearchTree() { delete _Lm; }
    ulong ItemCount() const
        { return _Lm->ItemCount(); }
    void ItemCount( ulong c )
        { _Lm->ItemCount( c ); }
    ulong ListSize() const
        { return _Lm->ListSize(); }
    int Add( const T& );
    void ForEach( int (*)(T&, void *), void * );
    friend TDBinarySearchTree<T>& operator <<
      ( TDBinarySearchTree<T>& bt, const T& obj )
        {   bt.Add( obj );
            return bt;
        }
};

template <class T>
int TDBinarySearchTree<T>::Add( const T& item )
{   Nd<T> newnode, pnode;
    filepos p, q;
    int addleft;
    _Lm->GetFree( newnode );
    q = _Lm->Head();
    while( q )  {
        p = q;
        _Lm->ReadNode( pnode, p );
        addleft = 0;
        if( item < pnode.Data )     {
            q = pnode.Left;
            addleft = 1;
        }
        else
            q = pnode.Right;
    }
    if( _Lm->Head() == 0 )
        _Lm->Head( newnode.Free );
    else  {
        if( addleft )
            pnode.Left = newnode.Free;
        else
            pnode.Right = newnode.Free;
        _Lm->WriteNode( pnode, pnode.Free );
    }
    newnode.Left = newnode.Right = 0;
    newnode.Data = item;
    _Lm->WriteNode( newnode, newnode.Free );
    ItemCount( ItemCount() + 1 );
    return 1;
}

template <class T> void TDBinarySearchTree<T>::
ForEach( int (*ifn)(T&, void *), void *args )
{  /* Do an inorder traversal. ifn() returns !0 if
    * node was modified and must be updated.
    */
    Nd<T> node;
    filepos p;
    TDStackAsVector<filepos> stk;  /* temp stack */
    p = _Lm->Head();
    while( 1 )  {
        while( p )  {  /* traverse left subtree */
            _Lm->ReadNode(node, p);
            stk.Push(p);
            p = node.Left;
        }
        if( stk.Pop(p) == 0 )
            break;
        _Lm->ReadNode(node, p);
        if( ifn( node.Data, args ) )  /* update node */
            _Lm->WriteNode(node, p);  /* if modified */
        p = node.Right;   /* goto right subtree */
    }
}
#endif  // EOF