ROOT_528-00b_version: include/TBtree.h Source File

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