Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-18 10:11:33 

0001 // @(#)root/cont:$Id$
0002 // Author: Fons Rademakers   10/10/95
0003 
0004 /*************************************************************************
0005  * Copyright (C) 1995-2000, Rene Brun and Fons Rademakers.               *
0006  * All rights reserved.                                                  *
0007  *                                                                       *
0008  * For the licensing terms see $ROOTSYS/LICENSE.                         *
0009  * For the list of contributors see $ROOTSYS/README/CREDITS.             *
0010  *************************************************************************/
0011 
0012 #ifndef ROOT_TBtree
0013 #define ROOT_TBtree
0014 
0015 
0016 //////////////////////////////////////////////////////////////////////////
0017 //                                                                      //
0018 // TBtree                                                               //
0019 //                                                                      //
0020 // Btree class. TBtree inherits from the TSeqCollection ABC.            //
0021 //                                                                      //
0022 // For a more extensive algorithmic description see the TBtree source.  //
0023 //                                                                      //
0024 //////////////////////////////////////////////////////////////////////////
0025 
0026 #include "TSeqCollection.h"
0027 #include "TError.h"
0028 
0029 #include <iterator>
0030 
0031 
0032 class TBtNode;
0033 class TBtInnerNode;
0034 class TBtLeafNode;
0035 class TBtreeIter;
0036 
0037 
0038 class TBtree : public TSeqCollection {
0039 
0040 friend class  TBtNode;
0041 friend class  TBtInnerNode;
0042 friend class  TBtLeafNode;
0043 
0044 private:
0045    TBtNode  *fRoot;              //root node of btree
0046 
0047    Int_t     fOrder;             //the order of the tree (should be > 2)
0048    Int_t     fOrder2;            //order*2+1 (assumes a memory access is
0049                                  //cheaper than a multiply and increment by one
0050    Int_t     fInnerLowWaterMark; //inner node low water mark
0051    Int_t     fLeafLowWaterMark;  //leaf low water mark
0052    Int_t     fInnerMaxIndex;     //maximum inner node index
0053    Int_t     fLeafMaxIndex;      //maximum leaf index
0054 
0055    void Init(Int_t i);        //initialize btree
0056    void RootIsFull();         //called when the root node is full
0057    void RootIsEmpty();        //called when root is empty
0058 
0059 protected:
0060    void IncrNofKeys() { fSize++; }
0061    void DecrNofKeys() { fSize--; }
0062 
0063    // add the object to the tree; return the index in the tree at which
0064    // the object was inserted. NOTE: other insertions and deletions may
0065    // change this object's index.
0066    Int_t IdxAdd(const TObject &obj);
0067 
0068 public:
0069    typedef TBtreeIter Iterator_t;
0070 
0071    TBtree(Int_t ordern = 3);  //create a TBtree of order n
0072    virtual     ~TBtree();
0073    void        Clear(Option_t *option="") override;
0074    void        Delete(Option_t *option="") override;
0075    TObject    *FindObject(const char *name) const override;
0076    TObject    *FindObject(const TObject *obj) const override;
0077    TObject   **GetObjectRef(const TObject *) const override { return nullptr; }
0078    TIterator  *MakeIterator(Bool_t dir = kIterForward) const override;
0079 
0080    void        Add(TObject *obj) override;
0081    void        AddFirst(TObject *obj) override { Add(obj); }
0082    void        AddLast(TObject *obj) override { Add(obj); }
0083    void        AddAt(TObject *obj, Int_t) override { Add(obj); }
0084    void        AddAfter(const TObject *, TObject *obj) override { Add(obj); }
0085    void        AddBefore(const TObject *, TObject *obj) override { Add(obj); }
0086    TObject    *Remove(TObject *obj) override;
0087 
0088    TObject    *At(Int_t idx) const override;
0089    TObject    *Before(const TObject *obj) const override;
0090    TObject    *After(const TObject *obj) const override;
0091    TObject    *First() const override;
0092    TObject    *Last() const override;
0093 
0094    //void PrintOn(std::ostream &os) const;
0095 
0096    Int_t       Order() { return fOrder; }
0097    TObject    *operator[](Int_t i) const;
0098    Int_t       Rank(const TObject *obj) const;
0099 
0100    ClassDefOverride(TBtree,0)  //A B-tree
0101 };
0102 
0103 
0104 //////////////////////////////////////////////////////////////////////////
0105 //                                                                      //
0106 // TBtNode                                                              //
0107 //                                                                      //
0108 // Abstract base class (ABC) of a TBtree node.                          //
0109 //                                                                      //
0110 //////////////////////////////////////////////////////////////////////////
0111 
0112 class TBtNode {
0113 
0114 friend class  TBtree;
0115 friend class  TBtInnerNode;
0116 friend class  TBtLeafNode;
0117 
0118 protected:
0119    Int_t fLast;   // for inner node 1 <= fLast <= fInnerMaxIndex
0120                   // for leaf node  1 <= fLast <= fLeafMaxIndex
0121                   // (fLast==0 only temporarily while the tree is being
0122                   // updated)
0123 
0124    TBtInnerNode *fParent;   // a parent is always an inner node (or 0 for the root)
0125    TBtree       *fTree;     // the tree of which this node is a part
0126    Int_t         fIsLeaf;   // run-time type flag
0127 
0128 public:
0129    TBtNode(Int_t isleaf, TBtInnerNode *p, TBtree *t = nullptr);
0130    virtual ~TBtNode();
0131 
0132    virtual void Add(const TObject *obj, Int_t index) = 0;
0133    virtual TBtree *GetParentTree() const {return fTree;}
0134    virtual void Remove(Int_t index) = 0;
0135 
0136    virtual TObject *operator[](Int_t i) const = 0;
0137    virtual TObject *Found(const TObject *obj, TBtNode **which, Int_t *where) = 0;
0138 
0139    virtual Int_t FindRank(const TObject *obj) const = 0;
0140    virtual Int_t NofKeys() const = 0; // # keys in or below this node
0141 
0142    virtual TBtLeafNode *FirstLeafNode() = 0;
0143    virtual TBtLeafNode *LastLeafNode() = 0;
0144 
0145    virtual void Split() = 0;
0146    // virtual void PrintOn(std::ostream &os) const = 0;
0147    // friend std::ostream &operator<<(std::ostream &os, const TBtNode &node);
0148 };
0149 
0150 
0151 //////////////////////////////////////////////////////////////////////////
0152 //                                                                      //
0153 // TBtItem                                                              //
0154 //                                                                      //
0155 // Item stored in inner nodes of a TBtree.                              //
0156 //                                                                      //
0157 //////////////////////////////////////////////////////////////////////////
0158 
0159 class TBtItem {
0160 
0161 friend class  TBtInnerNode;
0162 
0163 private:
0164    Int_t      fNofKeysInTree;   // number of keys in TBtree
0165    TObject   *fKey;             // key
0166    TBtNode   *fTree;            //! sub-tree
0167 
0168 public:
0169    TBtItem();
0170    TBtItem(TBtNode *n, TObject *o);
0171    TBtItem(TObject *o, TBtNode *n);
0172    ~TBtItem();
0173 };
0174 
0175 
0176 //////////////////////////////////////////////////////////////////////////
0177 //                                                                      //
0178 // TBtInnerNode                                                         //
0179 //                                                                      //
0180 // Inner node of a TBtree.                                              //
0181 //                                                                      //
0182 //////////////////////////////////////////////////////////////////////////
0183 
0184 class TBtInnerNode : public TBtNode {
0185 
0186 private:
0187    TBtItem    *fItem;   // actually fItem[MaxIndex()+1] is desired
0188 
0189 public:
0190    TBtInnerNode(TBtInnerNode *parent, TBtree *t = nullptr);
0191    TBtInnerNode(TBtInnerNode *parent, TBtree *tree, TBtNode *oldroot);
0192    ~TBtInnerNode();
0193 
0194    void      Add(const TObject *obj, Int_t idx) override;
0195    void      Add(TBtItem &i, Int_t idx);
0196    void      Add(Int_t at, TObject *obj, TBtNode *n);
0197    void      AddElt(TBtItem &itm, Int_t at);
0198    void      AddElt(Int_t at, TObject *obj, TBtNode *n);
0199    void      Remove(Int_t idx) override;
0200    void      RemoveItem(Int_t idx);
0201 
0202    TObject  *operator[](Int_t i) const override;
0203    TObject  *Found(const TObject *obj, TBtNode **which, Int_t *where) override;
0204 
0205    Int_t     NofKeys(Int_t idx) const;
0206    Int_t     NofKeys() const override;
0207    void      SetTree(Int_t i, TBtNode *node) { fItem[i].fTree = node; node->fParent = this; }
0208    void      SetKey(Int_t i, TObject *obj) { fItem[i].fKey = obj; }
0209    void      SetItem(Int_t i, TBtItem &itm) { fItem[i] = itm; itm.fTree->fParent = this; }
0210    void      SetItem(Int_t i, TObject *obj, TBtNode *node) { SetTree(i, node); SetKey(i, obj); }
0211    Int_t     GetNofKeys(Int_t i) const;
0212    void      SetNofKeys(Int_t i, Int_t r);
0213    Int_t     IncNofKeys(Int_t i, Int_t n=1);
0214    Int_t     DecNofKeys(Int_t i, Int_t n=1);
0215    Int_t     FindRank(const TObject *obj) const override;
0216    Int_t     FindRankUp(const TBtNode *n) const;
0217    TBtNode  *GetTree(Int_t i) const { return fItem[i].fTree; }
0218    TObject  *GetKey(Int_t i) const { return fItem[i].fKey; }
0219    TBtItem  &GetItem(Int_t i) const { return fItem[i]; }
0220 
0221    Int_t     IndexOf(const TBtNode *n) const;
0222    void      IncrNofKeys(TBtNode *np);
0223    void      DecrNofKeys(TBtNode *np);
0224 
0225    TBtLeafNode *FirstLeafNode() override;
0226    TBtLeafNode *LastLeafNode() override;
0227 
0228    void      InformParent();
0229 
0230    void      Split() override;
0231    void      SplitWith(TBtInnerNode *r, Int_t idx);
0232    void      MergeWithRight(TBtInnerNode *r, Int_t idx);
0233    void      BalanceWithLeft(TBtInnerNode *l, Int_t idx);
0234    void      BalanceWithRight(TBtInnerNode *r, Int_t idx);
0235    void      BalanceWith(TBtInnerNode *n, int idx);
0236    void      PushLeft(Int_t cnt, TBtInnerNode *leftsib, Int_t parentIdx);
0237    void      PushRight(Int_t cnt, TBtInnerNode *rightsib, Int_t parentIdx);
0238    void      AppendFrom(TBtInnerNode *src, Int_t start, Int_t stop);
0239    void      Append(TObject *obj, TBtNode *n);
0240    void      Append(TBtItem &itm);
0241    void      ShiftLeft(Int_t cnt);
0242 
0243    Int_t     Psize() const { return fLast; }
0244    Int_t     Vsize() const;
0245    Int_t     MaxIndex() const { return fTree ? fTree->fInnerMaxIndex : 0; }
0246    Int_t     MaxPsize() const { return fTree ? fTree->fInnerMaxIndex : 0; }
0247 
0248    // void      PrintOn(std::ostream &os) const;
0249 
0250    Int_t     IsFull() const { return fLast == MaxIndex(); }
0251    void      IsFull(TBtNode *n);
0252    Int_t     IsAlmostFull() const { return fLast >= MaxIndex() - 1; }
0253    Int_t     IsLow() const {  return fLast < fTree->fInnerLowWaterMark; }
0254    void      IsLow(TBtNode *n);
0255 };
0256 
0257 
0258 //////////////////////////////////////////////////////////////////////////
0259 //                                                                      //
0260 // TBtLeafNode                                                          //
0261 //                                                                      //
0262 // Leaf node of a TBtree.                                               //
0263 //                                                                      //
0264 //////////////////////////////////////////////////////////////////////////
0265 
0266 class TBtLeafNode : public TBtNode {
0267 
0268 friend class  TBtInnerNode;
0269 
0270 private:
0271    TObject **fItem; // actually TObject *fItem[MaxIndex()+1] is desired
0272 
0273 public:
0274    TBtLeafNode(TBtInnerNode *p, const TObject *obj = nullptr, TBtree *t = nullptr);
0275    ~TBtLeafNode();
0276 
0277    void       Add(const TObject *obj, Int_t idx) override;
0278    void       Remove(Int_t idx) override;
0279    void       RemoveItem(Int_t idx) { Remove(idx); }
0280 
0281    TObject   *operator[](Int_t i) const override;
0282    TObject   *Found(const TObject *obj, TBtNode **which, Int_t *where) override;
0283 
0284    Int_t      NofKeys(Int_t i) const;
0285    Int_t      NofKeys() const override;
0286    Int_t      FindRank(const TObject *obj) const override;
0287    TObject   *GetKey(Int_t idx ) { return fItem[idx]; }
0288    void       SetKey(Int_t idx, TObject *obj) { fItem[idx] = obj; }
0289 
0290    Int_t      IndexOf(const TObject *obj) const;
0291 
0292    TBtLeafNode  *FirstLeafNode() override;
0293    TBtLeafNode  *LastLeafNode() override;
0294 
0295    void       Split() override;
0296    void       SplitWith(TBtLeafNode *r, Int_t idx);
0297    void       MergeWithRight(TBtLeafNode *r, Int_t idx);
0298    void       BalanceWithLeft(TBtLeafNode *l, Int_t idx);
0299    void       BalanceWithRight(TBtLeafNode *r, Int_t idx);
0300    void       BalanceWith(TBtLeafNode *n, Int_t idx);
0301    void       PushLeft(Int_t cnt, TBtLeafNode *l, Int_t parentIndex);
0302    void       PushRight(Int_t cnt, TBtLeafNode *r, Int_t parentIndex);
0303    void       AppendFrom(TBtLeafNode *src, Int_t start, Int_t stop);
0304    void       Append(TObject *obj);
0305    void       ShiftLeft(Int_t cnt);
0306 
0307    Int_t      Psize() const { return fLast + 1; }
0308    Int_t      Vsize() const;
0309    Int_t      MaxIndex() const { return fTree ? fTree->fLeafMaxIndex : 0; }
0310    Int_t      MaxPsize() const { return fTree ? fTree->fLeafMaxIndex + 1 : 0; }
0311 
0312    // void       PrintOn(std::ostream &os) const;
0313 
0314    Int_t      IsFull() const { return fLast == MaxIndex(); }
0315    Int_t      IsAlmostFull() const { return fLast >= MaxIndex() - 1; }
0316    Int_t      IsLow() const { return fLast < fTree->fLeafLowWaterMark; }
0317 };
0318 
0319 
0320 //////////////////////////////////////////////////////////////////////////
0321 //                                                                      //
0322 // TBtreeIter                                                           //
0323 //                                                                      //
0324 // Iterator of btree.                                                   //
0325 //                                                                      //
0326 //////////////////////////////////////////////////////////////////////////
0327 
0328 class TBtreeIter : public TIterator {
0329 
0330 private:
0331    const TBtree  *fTree;      //btree being iterated
0332    Int_t          fCurCursor; //current position in btree
0333    Int_t          fCursor;    //next position in btree
0334    Bool_t         fDirection; //iteration direction
0335 
0336    TBtreeIter() : fTree(nullptr), fCurCursor(0), fCursor(0), fDirection(kIterForward) { }
0337 
0338 public:
0339    using iterator_category = std::bidirectional_iterator_tag;
0340    using value_type = TObject *;
0341    using difference_type = std::ptrdiff_t;
0342    using pointer = TObject **;
0343    using const_pointer = const TObject **;
0344    using reference = const TObject *&;
0345 
0346    TBtreeIter(const TBtree *t, Bool_t dir = kIterForward);
0347    TBtreeIter(const TBtreeIter &iter);
0348    ~TBtreeIter() { }
0349    TIterator  &operator=(const TIterator &rhs) override;
0350    TBtreeIter &operator=(const TBtreeIter &rhs);
0351 
0352    const TCollection  *GetCollection() const override { return fTree; }
0353    TObject            *Next() override;
0354    void                Reset() override;
0355    Bool_t              operator!=(const TIterator &aIter) const override;
0356    Bool_t              operator!=(const TBtreeIter &aIter) const;
0357    TObject            *operator*() const override;
0358 
0359    ClassDefOverride(TBtreeIter,0)  //B-tree iterator
0360 };
0361 
0362 //----- TBtree inlines ---------------------------------------------------------
0363 
0364 inline TObject *TBtree::operator[](Int_t i) const
0365 {
0366    return (*fRoot)[i];
0367 }
0368 
0369 inline TObject *TBtree::At(Int_t i) const
0370 {
0371    return (*fRoot)[i];
0372 }
0373 
0374 inline TObject *TBtree::First() const
0375 {
0376    return (*fRoot)[0];
0377 }
0378 
0379 inline TObject *TBtree::Last() const
0380 {
0381    return (*fRoot)[fSize-1];
0382 }
0383 
0384 //----- TBtInnerNode inlines ---------------------------------------------------
0385 
0386 inline Int_t TBtInnerNode::GetNofKeys(Int_t i) const
0387 {
0388    R__ASSERT(i >= 0 && i <= fLast);
0389    return fItem[i].fNofKeysInTree;
0390 }
0391 
0392 inline Int_t TBtInnerNode::NofKeys(Int_t idx) const
0393 {
0394    return GetNofKeys(idx);
0395 }
0396 
0397 inline void TBtInnerNode::SetNofKeys(Int_t i, Int_t r)
0398 {
0399    fItem[i].fNofKeysInTree = r;
0400 }
0401 
0402 inline Int_t TBtInnerNode::IncNofKeys(Int_t i, Int_t n)
0403 {
0404    return (fItem[i].fNofKeysInTree += n);
0405 }
0406 
0407 inline Int_t TBtInnerNode::DecNofKeys(Int_t i, Int_t n)
0408 {
0409    return (fItem[i].fNofKeysInTree -= n);
0410 }
0411 
0412 inline Int_t TBtInnerNode::Vsize() const
0413 {
0414    R__ASSERT(fParent != nullptr && fParent->GetTree(0) != (const TBtNode *)this);
0415    return Psize()+1;
0416 }
0417 
0418 
0419 //----- TBtLeafNode inlines ----------------------------------------------------
0420 
0421 inline TObject *TBtLeafNode::operator[](Int_t i) const
0422 {
0423    R__ASSERT(i >= 0 && i <= fLast);
0424    return fItem[i];
0425 }
0426 
0427 inline Int_t TBtLeafNode::Vsize() const
0428 {
0429    R__ASSERT(fParent != nullptr && fParent->GetTree(0) != (const TBtNode *)this);
0430    return Psize()+1;
0431 }
0432 
0433 //inline std::ostream &operator<<(std::ostream& outputStream, const TBtNode &aNode)
0434 //{
0435 //   aNode.PrintOn(outputStream);
0436 //   return outputStream;
0437 //}
0438 
0439 #endif
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!