TBtree.h Source File

00001 // @(#)root/cont:$Name:  $:$Id: TBtree.h,v 1.7 2002/07/29 09:22:28 rdm Exp $
00002 // Author: Fons Rademakers   10/10/95
00003 
00004 /*************************************************************************
00005  * Copyright (C) 1995-2000, Rene Brun and Fons Rademakers.               *
00006  * All rights reserved.                                                  *
00007  *                                                                       *
00008  * For the licensing terms see $ROOTSYS/LICENSE.                         *
00009  * For the list of contributors see $ROOTSYS/README/CREDITS.             *
00010  *************************************************************************/
00011 
00012 #ifndef ROOT_TBtree
00013 #define ROOT_TBtree
00014 
00015 
00017 //                                                                      //
00018 // TBtree                                                               //
00019 //                                                                      //
00020 // Btree class. TBtree inherits from the TSeqCollection ABC.            //
00021 //                                                                      //
00022 // For a more extensive algorithmic description see the TBtree source.  //
00023 //                                                                      //
00025 
00026 #ifndef ROOT_TSeqCollection
00027 #include "TSeqCollection.h"
00028 #endif
00029 #ifndef ROOT_TError
00030 #include "TError.h"
00031 #endif
00032 
00033 #if defined(R__MAC) && defined(SetItem)
00034 #   undef SetItem
00035 #   undef GetItem
00036 #endif
00037 
00038 
00039 class TBtNode;
00040 class TBtInnerNode;
00041 class TBtLeafNode;
00042 
00043 
00044 class TBtree : public TSeqCollection {
00045 
00046 friend class  TBtNode;
00047 friend class  TBtInnerNode;
00048 friend class  TBtLeafNode;
00049 
00050 private:
00051    TBtNode  *fRoot;              //root node of btree
00052 
00053    Int_t     fOrder;             //the order of the tree (should be > 2)
00054    Int_t     fOrder2;            //order*2+1 (assumes a memory access is
00055                                  //cheaper than a multiply and increment by one
00056    Int_t     fInnerLowWaterMark; //inner node low water mark
00057    Int_t     fLeafLowWaterMark;  //leaf low water mark
00058    Int_t     fInnerMaxIndex;     //maximum inner node index
00059    Int_t     fLeafMaxIndex;      //maximum leaf index
00060 
00061    void Init(Int_t i);        //initialize btree
00062    void RootIsFull();         //called when the root node is full
00063    void RootIsEmpty();        //called when root is empty
00064 
00065 protected:
00066 
00067    void IncrNofKeys() { fSize++; }
00068    void DecrNofKeys() { fSize--; }
00069 
00070    // add the object to the tree; return the index in the tree at which
00071    // the object was inserted. NOTE: other insertions and deletions may
00072    // change this object's index.
00073    Int_t IdxAdd(const TObject &obj);
00074 
00075 public:
00076 
00077    TBtree(Int_t ordern = 3);  //create a TBtree of order n
00078    virtual     ~TBtree();
00079    void        Clear(Option_t *option="");
00080    void        Delete(Option_t *option="");
00081    TObject    *FindObject(const char *name) const;
00082    TObject    *FindObject(const TObject *obj) const;
00083    TObject   **GetObjectRef(const TObject *) const { return 0; }
00084    TIterator  *MakeIterator(Bool_t dir = kIterForward) const;
00085 
00086    void        Add(TObject *obj);
00087    void        AddFirst(TObject *obj) { Add(obj); }
00088    void        AddLast(TObject *obj) { Add(obj); }
00089    void        AddAt(TObject *obj, Int_t) { Add(obj); }
00090    void        AddAfter(TObject *, TObject *obj) { Add(obj); }
00091    void        AddBefore(TObject *, TObject *obj) { Add(obj); }
00092    TObject    *Remove(TObject *obj);
00093 
00094    TObject    *At(Int_t idx) const;
00095    TObject    *Before(TObject *obj) const;
00096    TObject    *After(TObject *obj) const;
00097    TObject    *First() const;
00098    TObject    *Last() const;
00099 
00100    //void PrintOn(ostream &os) const;
00101 
00102    Int_t       Order() { return fOrder; }
00103    TObject    *operator[](Int_t i) const;
00104    Int_t       Rank(const TObject *obj) const;
00105 
00106    ClassDef(TBtree,1)  //A B-tree
00107 };
00108 
00109 
00111 //                                                                      //
00112 // TBtNode                                                              //
00113 //                                                                      //
00114 // Abstract base class (ABC) of a TBtree node.                          //
00115 //                                                                      //
00117 
00118 class TBtNode {
00119 
00120 friend class  TBtree;
00121 friend class  TBtInnerNode;
00122 friend class  TBtLeafNode;
00123 
00124 protected:
00125    Int_t fLast;   // for inner node 1 <= fLast <= fInnerMaxIndex
00126                   // for leaf node  1 <= fLast <= fLeafMaxIndex
00127                   // (fLast==0 only temporarily while the tree is being
00128                   // updated)
00129 
00130    TBtInnerNode *fParent;   // a parent is always an inner node (or 0 for the root)
00131    TBtree       *fTree;     // the tree of which this node is a part
00132    Int_t         fIsLeaf;   // run-time type flag
00133 
00134 public:
00135 
00136    TBtNode(Int_t isleaf, TBtInnerNode *p, TBtree *t = 0);
00137    virtual ~TBtNode();
00138 
00139    virtual void Add(const TObject *obj, Int_t index) = 0;
00140    virtual TBtree *GetParentTree() const {return fTree;}
00141    virtual void Remove(Int_t index) = 0;
00142 
00143    virtual TObject *operator[](Int_t i) const = 0;
00144    virtual TObject *Found(const TObject *obj, TBtNode **which, Int_t *where) = 0;
00145 
00146    virtual Int_t FindRank(const TObject *obj) const = 0;
00147    virtual Int_t NofKeys() const = 0; // # keys in or below this node
00148 
00149    virtual TBtLeafNode *FirstLeafNode() = 0;
00150    virtual TBtLeafNode *LastLeafNode() = 0;
00151 
00152    virtual void Split() = 0;
00153 
00154    // virtual void PrintOn(ostream &os) const = 0;
00155    // friend ostream &operator<<(ostream &os, const TBtNode &node);
00156 };
00157 
00158 
00160 //                                                                      //
00161 // TBtItem                                                              //
00162 //                                                                      //
00163 // Item stored in inner nodes of a TBtree.                              //
00164 //                                                                      //
00166 
00167 class TBtItem {
00168 
00169 friend class  TBtInnerNode;
00170 
00171 private:
00172    Int_t      fNofKeysInTree;   // number of keys in TBtree
00173    TObject   *fKey;             // key
00174    TBtNode   *fTree;            
00175 
00176 public:
00177    TBtItem();
00178    TBtItem(TBtNode *n, TObject *o);
00179    TBtItem(TObject *o, TBtNode *n);
00180    ~TBtItem();
00181 };
00182 
00183 
00185 //                                                                      //
00186 // TBtInnerNode                                                         //
00187 //                                                                      //
00188 // Inner node of a TBtree.                                              //
00189 //                                                                      //
00191 
00192 class TBtInnerNode : public TBtNode {
00193 
00194 private:
00195 
00196    TBtItem    *fItem;   // actually fItem[MaxIndex()+1] is desired
00197 
00198 public:
00199 
00200    TBtInnerNode(TBtInnerNode *parent, TBtree *t = 0);
00201    TBtInnerNode(TBtInnerNode *parent, TBtree *tree, TBtNode *oldroot);
00202    ~TBtInnerNode();
00203 
00204    void      Add(const TObject *obj, Int_t idx);
00205    void      Add(TBtItem &i, Int_t idx);
00206    void      Add(Int_t at, TObject *obj, TBtNode *n);
00207    void      AddElt(TBtItem &itm, Int_t at);
00208    void      AddElt(Int_t at, TObject *obj, TBtNode *n);
00209    void      Remove(Int_t idx);
00210    void      RemoveItem(Int_t idx);
00211 
00212    TObject  *operator[](Int_t i) const;
00213    TObject  *Found(const TObject *obj, TBtNode **which, Int_t *where);
00214 
00215    Int_t     NofKeys(Int_t idx) const;
00216    Int_t     NofKeys() const;
00217    void      SetTree(Int_t i, TBtNode *node) { fItem[i].fTree = node; node->fParent = this; }
00218    void      SetKey(Int_t i, TObject *obj) { fItem[i].fKey = obj; }
00219    void      SetItem(Int_t i, TBtItem &itm) { fItem[i] = itm; itm.fTree->fParent = this; }
00220    void      SetItem(Int_t i, TObject *obj, TBtNode *node) { SetTree(i, node); SetKey(i, obj); }
00221    Int_t     GetNofKeys(Int_t i) const;
00222    void      SetNofKeys(Int_t i, Int_t r);
00223    Int_t     IncNofKeys(Int_t i, Int_t n=1);
00224    Int_t     DecNofKeys(Int_t i, Int_t n=1);
00225    Int_t     FindRank(const TObject *obj) const;
00226    Int_t     FindRankUp(const TBtNode *n) const;
00227    TBtNode  *GetTree(Int_t i) const { return fItem[i].fTree; }
00228    TObject  *GetKey(Int_t i) const { return fItem[i].fKey; }
00229    TBtItem  &GetItem(Int_t i) const { return fItem[i]; }
00230 
00231    Int_t     IndexOf(const TBtNode *n) const;
00232    void      IncrNofKeys(TBtNode *np);
00233    void      DecrNofKeys(TBtNode *np);
00234 
00235    TBtLeafNode *FirstLeafNode();
00236    TBtLeafNode *LastLeafNode();
00237 
00238    void      InformParent();
00239 
00240    void      Split();
00241    void      SplitWith(TBtInnerNode *r, Int_t idx);
00242    void      MergeWithRight(TBtInnerNode *r, Int_t idx);
00243    void      BalanceWithLeft(TBtInnerNode *l, Int_t idx);
00244    void      BalanceWithRight(TBtInnerNode *r, Int_t idx);
00245    void      BalanceWith(TBtInnerNode *n, int idx);
00246    void      PushLeft(Int_t cnt, TBtInnerNode *leftsib, Int_t parentIdx);
00247    void      PushRight(Int_t cnt, TBtInnerNode *rightsib, Int_t parentIdx);
00248    void      AppendFrom(TBtInnerNode *src, Int_t start, Int_t stop);
00249    void      Append(TObject *obj, TBtNode *n);
00250    void      Append(TBtItem &itm);
00251    void      ShiftLeft(Int_t cnt);
00252 
00253    Int_t     Psize() const { return fLast; }
00254    Int_t     Vsize() const;
00255    Int_t     MaxIndex() const { return fTree->fInnerMaxIndex; }
00256    Int_t     MaxPsize() const { return fTree->fInnerMaxIndex; }
00257 
00258    // void      PrintOn(ostream &os) const;
00259 
00260    Int_t     IsFull() const { return fLast == MaxIndex(); }
00261    void      IsFull(TBtNode *n);
00262    Int_t     IsAlmostFull() const { return fLast >= MaxIndex() - 1; }
00263    Int_t     IsLow() const {  return fLast < fTree->fInnerLowWaterMark; }
00264    void      IsLow(TBtNode *n);
00265 };
00266 
00267 
00269 //                                                                      //
00270 // TBtLeafNode                                                          //
00271 //                                                                      //
00272 // Leaf node of a TBtree.                                               //
00273 //                                                                      //
00275 
00276 class TBtLeafNode : public TBtNode {
00277 
00278 friend class  TBtInnerNode;
00279 
00280 private:
00281    TObject **fItem; // actually TObject *fItem[MaxIndex()+1] is desired
00282 
00283 public:
00284    TBtLeafNode(TBtInnerNode *p, const TObject *obj = 0, TBtree *t = 0);
00285    ~TBtLeafNode();
00286 
00287    void       Add(const TObject *obj, Int_t idx);
00288    void       Remove(Int_t idx);
00289    void       RemoveItem(Int_t idx) { Remove(idx); }
00290 
00291    TObject   *operator[](Int_t i) const;
00292    TObject   *Found(const TObject *obj, TBtNode **which, Int_t *where);
00293 
00294    Int_t      NofKeys(Int_t i) const;
00295    Int_t      NofKeys() const;
00296    Int_t      FindRank(const TObject *obj) const;
00297    TObject   *GetKey(Int_t idx ) { return fItem[idx]; }
00298    void       SetKey(Int_t idx, TObject *obj) { fItem[idx] = obj; }
00299 
00300    Int_t      IndexOf(const TObject *obj) const;
00301 
00302    TBtLeafNode  *FirstLeafNode();
00303    TBtLeafNode  *LastLeafNode();
00304 
00305    void       Split();
00306    void       SplitWith(TBtLeafNode *r, Int_t idx);
00307    void       MergeWithRight(TBtLeafNode *r, Int_t idx);
00308    void       BalanceWithLeft(TBtLeafNode *l, Int_t idx);
00309    void       BalanceWithRight(TBtLeafNode *r, Int_t idx);
00310    void       BalanceWith(TBtLeafNode *n, Int_t idx);
00311    void       PushLeft(Int_t cnt, TBtLeafNode *l, Int_t parentIndex);
00312    void       PushRight(Int_t cnt, TBtLeafNode *r, Int_t parentIndex);
00313    void       AppendFrom(TBtLeafNode *src, Int_t start, Int_t stop);
00314    void       Append(TObject *obj);
00315    void       ShiftLeft(Int_t cnt);
00316 
00317    Int_t      Psize() const { return fLast + 1; }
00318    Int_t      Vsize() const;
00319    Int_t      MaxIndex() const { return fTree->fLeafMaxIndex; }
00320    Int_t      MaxPsize() const { return fTree->fLeafMaxIndex + 1; }
00321 
00322    // void       PrintOn(ostream &os) const;
00323 
00324    Int_t      IsFull() const { return fLast == MaxIndex(); }
00325    Int_t      IsAlmostFull() const { return fLast >= MaxIndex() - 1; }
00326    Int_t      IsLow() const { return fLast < fTree->fLeafLowWaterMark; }
00327 };
00328 
00329 
00331 //                                                                      //
00332 // TBtreeIter                                                           //
00333 //                                                                      //
00334 // Iterator of btree.                                                   //
00335 //                                                                      //
00337 
00338 class TBtreeIter : public TIterator {
00339 
00340 private:
00341    const TBtree  *fTree;      //btree being iterated
00342    Int_t          fCursor;    //current position in btree
00343    Bool_t         fDirection; //iteration direction
00344 
00345    TBtreeIter() : fTree(0), fCursor(0) { }
00346 
00347 public:
00348    TBtreeIter(const TBtree *t, Bool_t dir = kIterForward);
00349    TBtreeIter(const TBtreeIter &iter);
00350    ~TBtreeIter() { }
00351    TIterator  &operator=(const TIterator &rhs);
00352    TBtreeIter &operator=(const TBtreeIter &rhs);
00353 
00354    const TCollection  *GetCollection() const { return fTree; }
00355    TObject            *Next();
00356    void                Reset();
00357 
00358    ClassDef(TBtreeIter,0)  //B-tree iterator
00359 };
00360 
00361 
00362 //----- TBtree inlines ---------------------------------------------------------
00363 
00364 inline TObject *TBtree::operator[](Int_t i) const
00365 {
00366    return (*fRoot)[i];
00367 }
00368 
00369 inline TObject *TBtree::At(Int_t i) const
00370 {
00371    return (*fRoot)[i];
00372 }
00373 
00374 inline TObject *TBtree::First() const
00375 {
00376    return (*fRoot)[0];
00377 }
00378 
00379 inline TObject *TBtree::Last() const
00380 {
00381    return (*fRoot)[fSize-1];
00382 }
00383 
00384 //----- TBtInnerNode inlines ---------------------------------------------------
00385 
00386 inline Int_t TBtInnerNode::GetNofKeys(Int_t i) const
00387 {
00388    Assert(i >= 0 && i <= fLast);
00389    return fItem[i].fNofKeysInTree;
00390 }
00391 
00392 inline Int_t TBtInnerNode::NofKeys(Int_t idx) const
00393 {
00394    return GetNofKeys(idx);
00395 }
00396 
00397 inline void TBtInnerNode::SetNofKeys(Int_t i, Int_t r)
00398 {
00399    fItem[i].fNofKeysInTree = r;
00400 }
00401 
00402 inline Int_t TBtInnerNode::IncNofKeys(Int_t i, Int_t n)
00403 {
00404    return (fItem[i].fNofKeysInTree += n);
00405 }
00406 
00407 inline Int_t TBtInnerNode::DecNofKeys(Int_t i, Int_t n)
00408 {
00409    return (fItem[i].fNofKeysInTree -= n);
00410 }
00411 
00412 inline Int_t TBtInnerNode::Vsize() const
00413 {
00414    Assert(fParent != 0 && fParent->GetTree(0) != (TBtNode *)this);
00415    return Psize()+1;
00416 }
00417 
00418 
00419 //----- TBtLeafNode inlines ----------------------------------------------------
00420 
00421 inline TObject *TBtLeafNode::operator[](Int_t i) const
00422 {
00423    Assert(i >= 0 && i <= fLast);
00424    return fItem[i];
00425 }
00426 
00427 inline Int_t TBtLeafNode::Vsize() const
00428 {
00429    Assert(fParent != 0 && fParent->GetTree(0) != (TBtNode *)this);
00430    return Psize()+1;
00431 }
00432 
00433 //inline ostream &operator<<(ostream& outputStream, const TBtNode &aNode)
00434 //{
00435 //   aNode.PrintOn(outputStream);
00436 //   return outputStream;
00437 //}
00438 
00439 #endif