/ray/src/lib/tl/tlbtree.h

Go to the documentation of this file.

/*
 * lib/tl/tlbtree.h 
 * 
 * Complete implementation of B-tree template. 
 * 
 * Copyright (c) 2004 by Wolfgang Wieser ] wwieser (a) gmx <*> de [ 
 * 
 * This file may be distributed and/or modified under the terms of the 
 * GNU General Public License version 2 as published by the Free Software 
 * Foundation. (See COPYING.GPL for details.)
 * 
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 * 
 */

#ifndef _TemplateLibrary_BTree_H_
#define _TemplateLibrary_BTree_H_ 1

#include <lib/sconfig.h>    /* MUST be first */

#include <lib/salloc.h>
#include <lib/tl/defop.h>

#ifndef TLIB_DEBUG_BTREE
#  define TLIB_DEBUG_BTREE 0
#endif

#if TLIB_DEBUG_BTREE
// See CheckTree() for this #define: 
#  define TLBT_ASSERT(x)  Assert(x)
//#define TLBT_ASSERT(x)  ++nerr
#endif

template<typename T,typename _OP=TLDefaultOperators_CDT<T> >class TLBTree
{
    public:
        struct Node
        {
            int nelem;      
            Node **down;    
            char _elem[];   
            // Note: For GCC we may use _elem[0]. (zero-length array)
            
            inline T &elem(int idx,TLBTree *bt)
                {  return(*(T*)(_elem+idx*bt->OP.size()));  }
            inline T *elemP(int idx,TLBTree *bt)
                {  return((T*)(_elem+idx*bt->OP.size()));  }
            
            template<typename K>bool _LBI(const K &e,int *idx,TLBTree *bt)
            {
                // The case nelem=0 should not happen here. 
            #if 0
                //if(!nelem)  {  *idx=0;  return(0);  }
                int a=0,b=nelem-1;
                if(bt->OP.gt(elem(0,bt),e))  {  *idx=0;  return(0);  }
                if(bt->OP.lt(elem(b,bt),e))  {  *idx=nelem;  return(0);  }
                while(b-a>1)
                {  int m=(a+b)/2;  bt->OP.lt(elem(m,bt),e) ? a=m : b=m;  }
                if(bt->OP.eq(elem(a,bt),e))  {  *idx=a;  return(1);  }
                *idx=b;  return(bt->OP.eq(elem(b,bt),e));
            #else
                /*if(nelem<=1) {  if(!nelem)  {  *idx=0;  return(0);  }
                    if(bt->OP.lt(elem(0,bt),e))  {  *idx=1;  return(0);  }
                    *idx=0;  return(bt->OP.eq(elem(0,bt),e));  }*/
                int a=0,b=nelem-1;
                while(b-a>1)
                {  int m=(a+b)/2;  bt->OP.lt(elem(m,bt),e) ? a=m : b=m;  }
                if(!a && bt->OP.gt(elem(0,bt),e))  {  *idx=0;  return(0);  }
                if(b==nelem-1 && bt->OP.lt(elem(b,bt),e))
                    {  *idx=nelem;  return(0);  }
                if(bt->OP.eq(elem(a,bt),e))  {  *idx=a;  return(1);  }
                *idx=b;  return(b && bt->OP.eq(elem(b,bt),e));
            #endif
            }
            
            inline void _INSLeafNS(int idx,const T &e,TLBTree *bt)
            {
                if(idx==nelem)  {  bt->OP.ini(elemP(nelem++,bt),e);  return;  }
                int i=nelem-1;  bt->OP.ini(elemP(nelem,bt),elem(i,bt));
                for(; i>idx; i--)  bt->OP.ass(elem(i,bt),elem(i-1,bt));
                bt->OP.ass(elem(idx,bt),e);  ++nelem;
            }
            
            inline void _INS_NS(int idx,const T &e,Node *chld,TLBTree *bt)
            {
                down[nelem+1]=down[nelem];
                if(idx==nelem)
                {  bt->OP.ini(elemP(nelem++,bt),e);  down[idx]=chld;  return;  }
                int i=nelem-1;
                bt->OP.ini(elemP(nelem,bt),elem(i,bt));  down[nelem]=down[i];
                for(; i>idx; i--)
                {  bt->OP.ass(elem(i,bt),elem(i-1,bt));  down[i]=down[i-1];  }
                bt->OP.ass(elem(idx,bt),e);  down[idx]=chld;  ++nelem;
            }
            
            inline void _DELLeaf(int idx,TLBTree *bt)
            {
                --nelem;
                for(int i=idx; i<nelem; i++)
                    bt->OP.ass(elem(i,bt),elem(i+1,bt));
                bt->OP.clr(elemP(nelem,bt));
            }
            
            inline void _DEL_L(int idx,TLBTree *bt)
            {
                --nelem;
                for(int i=idx; ; i++)
                {
                    down[i]=down[i+1];  if(i>=nelem)  break;
                    bt->OP.ass(elem(i,bt),elem(i+1,bt));
                }
                bt->OP.clr(elemP(nelem,bt));  down[nelem+1]=NULL;
            }
            inline void _DEL_R(int idx,TLBTree *bt)
            {
                --nelem;
                for(int i=idx; i<nelem; )
                {
                    bt->OP.ass(elem(i,bt),elem(i+1,bt));  ++i;
                    down[i]=down[i+1];
                }
                bt->OP.clr(elemP(nelem,bt));  down[nelem+1]=NULL;
            }
            
            inline Node() : nelem(0),down(NULL) {}
            inline ~Node()
                {  /*down=OP.free(down);must be done by higher level*/  }
        };
        
    private:
        // The actual tree data fields: 
        int m;   
        Node *root;   
        T tmp;   
        
    public:
        // These are the operators... normally, the default OPs 
        // will not occupy any place (i.e. 1byte compiler dummy or so). 
        _OP OP;
        
    private:
        // Some statistics: (Not implemented.)
        //size_t n_elems;   // Total number of elements in the tree. 
        //size_t n_nodes;   // Total number of nodes in the tree. 
        
        Node *_AllocLeaf()
        {
            void *place=OP.alloc( sizeof(Node) + OP.size()*(m+m) );
            return(new(place) Node());
        }
        Node *_AllocNonLeaf()
        {
            Node *n=_AllocLeaf();
            n->down=(Node**)OP.alloc(sizeof(Node*)*(m+m+1));
            for(int i=0,e=m+m; i<=e; i++)  n->down[i]=NULL;
            return(n);
        }
        inline Node *_FreeNode(Node *n)
            {  OP.free(n->down); n->Node::~Node(); OP.free(n); return(NULL);  }
        
        void _DeleteTree(Node *tn)
        {
            if(!tn)  return;
            if(tn->down) for(int i=0; i<=tn->nelem; i++)
                _DeleteTree(tn->down[i]);
            for(int i=0; i<tn->nelem; i++)  OP.clr(&tn->elem(i,this));
            _FreeNode(tn);
        }
        
        template<typename K>T *_Find(const K &key,Node *tn)
        {
            for(int idx; ; tn=tn->down[idx])
            {
                if(tn->_LBI(key,&idx,this))  return(&tn->elem(idx,this));
                if(!tn->down)  break;
            }
            return(NULL);
        }
        
        Node *_FindSmallestLeaf(Node *n)
            {  while(n->down) n=n->down[0];  return(n);  }
        Node *_FindLargestLeaf(Node *n)
            {  while(n->down) n=n->down[n->nelem];  return(n);  }
        T *_FindSmallest(Node *n)
            {  return(&_FindSmallestLeaf(n)->elem(0,this));  }
        T *_FindLargest(Node *n)
            {  n=_FindLargestLeaf(n);  return(&n->elem(n->nelem-1,this));  }
        
        template<typename K>T *_FindNeighbours(const K &key,Node *tn,
            T **p,T **n)
        {
            int idx;
            if(tn->_LBI(key,&idx,this))
            {  // Exact match. 
                if(p)  if(tn->down)  *p=_FindLargest(tn->down[idx]);
                       else if(idx>0)  *p=&tn->elem(idx-1,this);
                if(n)  if(tn->down)  *n=_FindSmallest(tn->down[idx+1]);
                       else if(idx+1<tn->nelem)  *n=&tn->elem(idx+1,this);
                return(&tn->elem(idx,this));
            }
            T *rv = tn->down ? _FindNeighbours(key,tn->down[idx],p,n) : NULL;
            if(p && !*p && idx>0)  *p=&tn->elem(idx-1,this);
            if(n && !*n && idx<tn->nelem)  *n=&tn->elem(idx,this);
            return(rv);
        }
        
        int _Store(Node *tn,const T &e,Node **split,bool allow_update,
            T *oldval)
        {
            int idx;
            if(tn->_LBI(e,&idx,this))
            {
                if(oldval) OP.ass(*oldval,tn->elem(idx,this));
                if(allow_update) OP.ass(tn->elem(idx,this),e);
                return(1);
            }
            if(!tn->down)
            {
                if(tn->nelem<m+m)  { tn->_INSLeafNS(idx,e,this); return(0); }
                // Split leaf node: 
                Node *l=_AllocLeaf();
                int d=0,s=0;
                // left...
                while(d<m)  OP.ini(&l->elem(d++,this),
                                   s==idx ? (idx=-1,e) : tn->elem(s++,this));
                // ...middle...
                if(s==idx)  OP.ini(&tmp,(idx=-1,e));
                else  {  OP.ini(&tmp,tn->elem(s,this));
                         if(s>=m) OP.clr(&tn->elem(s,this));  ++s;  }
                // ...right
                for(d=0; d<m; )
                    if(s==idx)  OP.ass(tn->elem(d++,this),(idx=-1,e));
                    else  {  OP.ass(tn->elem(d++,this),tn->elem(s,this));
                             OP.clr(&tn->elem(s++,this));  }
                tn->nelem=m;  l->nelem=m;  *split=l;  return(3);
            }
            Node *isplit;
            int rv=_Store(tn->down[idx],e,&isplit,allow_update,oldval);
            if(rv!=3)  return(rv);
            if(tn->nelem<m+m)
            {  tn->_INS_NS(idx,tmp,isplit,this);  OP.clr(&tmp);  return(0);  }
            // Split non-leaf node: 
            T itmp(tmp);  OP.clr(&tmp);
            Node *l=_AllocNonLeaf();
            int d=0,s=0;
            // left...
            while(d<m)
                if(s==idx)  {  OP.ini(&l->elem(d,this),(idx=-1,itmp));
                               (l->down[d++]=isplit);  }
                else  {  OP.ini(&l->elem(d,this),tn->elem(s,this));
                         (l->down[d++]=tn->down[s++]);  }
            // ...middle...
            if(s==idx)
            {
                (l->down[d]=isplit);
                OP.ini(&tmp,(idx=-1,itmp));
            } else {
                OP.ini(&tmp,tn->elem(s,this));
                if(s>=m) OP.clr(&tn->elem(s,this));
                (l->down[d]=tn->down[s++]);
            }
            // ...right
            for(d=0; d<m; )
                if(s==idx)
                {  OP.ass(tn->elem(d,this),(idx=-1,itmp));
                   tn->down[d++]=isplit;  }
                else
                {  OP.ass(tn->elem(d,this),tn->elem(s,this));
                   OP.clr(&tn->elem(s,this));
                   tn->down[d++]=tn->down[s];  tn->down[s++]=NULL;  }
            tn->down[d]=tn->down[s];  tn->down[s]=NULL;
            tn->nelem=m;  l->nelem=m;  *split=l;  return(3);
        }
        
        bool _HandleUnderflow(Node *tn,int idx)
        {
            Node *l,*r;
            if(idx<tn->nelem)
            {
                l=tn->down[idx]; r=tn->down[idx+1];
                if(r->nelem>m)  // Transfer from right brother?
                {
                    OP.ini(&l->elem(l->nelem++,this),tn->elem(idx,this));
                    OP.ass(tn->elem(idx,this),r->elem(0,this));
                    if(l->down)
                    {  (l->down[l->nelem]=r->down[0]);
                       r->_DEL_L(0,this);  }
                    else  r->_DELLeaf(0,this);
                    return(0);
                }
            } else {
                // Check left brother (since there is no right one). 
                l=tn->down[idx-1]; r=tn->down[idx];
                if(l->nelem>m)  // Transfer from left brother?
                {
                    // For m==1, I'd need an extra case for r->nelem==0 here. 
                    if(!r->down)  r->_INSLeafNS(0,tn->elem(idx-1,this),this);
                    else { r->_INS_NS(0,tn->elem(idx-1,this),l->down[l->nelem],
                                      this);  }
                    OP.ass(tn->elem(idx-1,this),l->elem(l->nelem-1,this));
                    if(l->down)  l->_DEL_R(l->nelem-1,this); 
                    else  l->_DELLeaf(l->nelem-1,this);
                    return(0);
                }  --idx;  // <-- important...
            }
            // Merge left and right brother: 
            int d=l->nelem;
            OP.ini(&l->elem(d++,this),tn->elem(idx,this));
            tn->_DEL_R(idx,this);
            for(int i=0; ; i++)
            {
                if(r->down)  (l->down[d]=r->down[i]);
                if(i>=r->nelem)  break;
                OP.ini(&l->elem(d++,this),r->elem(i,this));
                OP.clr(&r->elem(i,this));
            }
            l->nelem=d;  _FreeNode(r);  return(tn->nelem<m);
        }
        
        inline void _HandleRootUnderflow()
        {
            if(root->nelem)  return;
            if(!root->down)  {  root=_FreeNode(root);  return;  }
            Node *oroot=root;  root=root->down[0];  _FreeNode(oroot);  
        }
        
        bool _MoveSmallest(Node *tn,T *ent)
        {
            if(!tn->down)  {  OP.ass(*ent,tn->elem(0,this));
                              tn->_DELLeaf(0,this);  return(tn->nelem<m);  }
            if(_MoveSmallest(tn->down[0],ent))  // <- Underflow in tn->down[0]. 
                return(_HandleUnderflow(tn,0));
            return(0);
        }
        
        template<typename K>int _Remove(Node *tn,const K &key,T *e)
        {
            int idx;
            if(tn->_LBI(key,&idx,this))
            {   // Found it. 
                if(e)  OP.ass(*e,tn->elem(idx,this));
                if(!tn->down)
                {  tn->_DELLeaf(idx,this);  return(tn->nelem<m ? 2 : 0);  }
                if(_MoveSmallest(tn->down[idx+1],&tn->elem(idx,this)) && 
                    _HandleUnderflow(tn,idx+1))  return(2);
                return(0);
            }
            if(!tn->down)  return(1);
            int rv=_Remove(tn->down[idx],key,e);  if(rv!=2)  return(rv);
            return(_HandleUnderflow(tn,idx) ? 2 : 0);
        }
        
        int _RemoveSL(Node *tn,int sl,T *e)
        {
            if(tn->down)
            {
                int idx = sl<0 ? 0 : tn->nelem;
                int rv=_RemoveSL(tn->down[idx],sl,e);  if(rv!=2) return(rv);
                return(_HandleUnderflow(tn,idx) ? 2 : 0);
            }
            int idx = sl<0 ? 0 : (tn->nelem-1);
            if(e)  OP.ass(*e,tn->elem(idx,this));
            tn->_DELLeaf(idx,this);  return(tn->nelem<m ? 2 : 0);
        }
        
        int _DoRemoveSL(int sl,T *e)
        {
            if(!root)  return(1);
            int rv=_RemoveSL(root,sl,e);  if(rv!=2)  return(rv);
            _HandleRootUnderflow();  return(0);
        }
        
        #if TLIB_DEBUG_BTREE

        int _CheckTree(Node *tn)
        {
            int nerr=0;
            // Make sure element number is right: 
            TLBT_ASSERT(tn->nelem<=m+m);
            TLBT_ASSERT(tn==root || tn->nelem>=m);
            // Make sure elements are sorted in ascenting order: 
            for(int i=1; i<tn->nelem; i++)
                TLBT_ASSERT(OP.lt(tn->elem(i-1,this),tn->elem(i,this)));
            if(tn->down) for(int i=0,e=m+m; i<=e; i++)
            {
                Node *d=tn->down[i];
                if(i>tn->nelem)
                {   /*fprintf(stderr,"(%d,%d,%d,%p=%d)",i,tn->nelem,tn->elem(0,this),d,d ? d->elem(0,this) : 0);*/
                    TLBT_ASSERT(!d);  continue;  }
                TLBT_ASSERT(d);
                /*fprintf(stderr,"(%d,up=%p=%d,shall=%p=%d)",d->elem(0,this),d->up,d->up->elem(0,this),tn,tn->elem(0,this));*/
                if(i>0) TLBT_ASSERT(OP.lt(tn->elem(i-1,this),d->elem(0,this)));
                nerr+=_CheckTree(tn->down[i]);
                if(i<tn->nelem)
                    TLBT_ASSERT(OP.lt(d->elem(d->nelem-1,this),tn->elem(i,this)));
            }
            return(nerr);
        }
        #endif  /* TLIB_DEBUG_BTREE */
        
        size_t _CountElements(Node *tn) const
        {
            size_t c=tn->nelem;
            if(tn->down) for(int i=0; i<=tn->nelem; i++)
                c+=_CountElements(tn->down[i]);
            return(c);
        }
        
        size_t _CountNodes(Node *tn) const
        {
            size_t c=1;  // <-- this node
            if(tn->down) for(int i=0; i<=tn->nelem; i++)
                c+=_CountNodes(tn->down[i]);
            return(c);
        }
        
        TLBTree(const TLBTree &);
        void operator=(const TLBTree &);
    public:
        TLBTree(int _m=16,const _OP &op=_OP()) : 
            m(_m<2 ? 2 : _m),root(NULL),tmp(),OP(op) {}
        ~TLBTree()  {  _DeleteTree(root); root=NULL;  /*No: clr(&tmp);*/  }
        
        inline void clear()
            {  _DeleteTree(root);  root=NULL;  }
        
        inline bool IsEmpty() const
            {  return(!root);  }
        
        inline size_t CountElements() const
            {  return(root ? _CountElements(root) : 0);  }
        
        inline size_t CountNodes() const
            {  return(root ? _CountNodes(root) : 0);  }
        
        inline size_t GetNodeSize() const
            {  return(sizeof(Node)+OP.size()*(m+m));  }
        
        template<typename K>inline T *search(const K &key)
            {  return(root ? _Find(key,root) : NULL);  }
        
        template<typename K>T *SearchNeighbours(const K &key,T **prev,T **next)
        {
            if(prev) *prev=NULL;  if(next) *next=NULL;  // Important for recursion. 
            return(root ? _FindNeighbours(key,root,prev,next) : NULL);
        }
        
        inline T *GetSmallest()
            {  return(root ? _FindSmallest(root) : NULL);  }
        inline T *GetLargest()
            {  return(root ? _FindLargest(root) : NULL);  }
        
        int store(const T &e,bool allow_update,T *oldval=NULL)
        {
            if(!root)
            {
                root=_AllocLeaf();
                OP.ini(&root->elem(0,this),e);  root->nelem=1;  return(0);
            }
            Node *split;  int rv=_Store(root,e,&split,allow_update,oldval);
            if(rv!=3) return(rv);
            // Split root. 
            Node *nroot=_AllocNonLeaf();
            nroot->down[0]=split;
            nroot->down[1]=root;
            OP.ini(&nroot->elem(0,this),tmp);  OP.clr(&tmp);
            nroot->nelem=1;  root=nroot;  return(0);
        }
        
        template<typename K>int remove(const K &key,T *e=NULL)
        {
            if(!root)  return(1);
            int rv=_Remove(root,key,e);  if(rv!=2)  return(rv);
            _HandleRootUnderflow();  return(0);
        }
        
        inline int RemoveSmallest(T *e=NULL)
            {  return(_DoRemoveSL(-1,e));  }
        inline int RemoveLargest(T *e=NULL)
            {  return(_DoRemoveSL(+1,e));  }
        
        #if TLIB_DEBUG_BTREE
        void DumpTree(FILE *f,Node *tn=NULL,int lvl=0)
        {
            if(!tn && !lvl)  tn=root;  if(!tn)  return;
            for(int i=0; i<tn->nelem; i++)
            {
                if(tn->down) DumpTree(f,tn->down[i],lvl+1);
                for(int j=0; j<lvl; j++)  fprintf(f,"  ");
                fprintf(f,"%d\n",tn->elem(i,this));
            }
            if(tn->down) DumpTree(f,tn->down[tn->nelem],lvl+1);
        }
        
        int CheckTree()
        {
            if(!root)  return(0);
            int nerr=0;
            return(nerr+_CheckTree(root));
        }
        #endif  /* TLIB_DEBUG_BTREE */
};

#if TLIB_DEBUG_BTREE
#  undef TLBT_ASSERT
#endif

#endif  /* _TemplateLibrary_BTree_H_ */

---