Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2026-09-22 09:07:23 

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        Add(TObject *obj, Option_t *) override { Add(obj); };
0082    void        AddFirst(TObject *obj) override { Add(obj); }
0083    void        AddFirst(TObject *obj, Option_t *) override { Add(obj); }
0084    void        AddLast(TObject *obj) override { Add(obj); }
0085    void        AddLast(TObject *obj, Option_t *) override { Add(obj); }
0086    void        AddAt(TObject *obj, Int_t) override { Add(obj); }
0087    void        AddAt(TObject *obj, Int_t, Option_t *) override { Add(obj); }
0088    void        AddAfter(const TObject *, TObject *obj) override { Add(obj); }
0089    void        AddAfter(const TObject *, TObject *obj, Option_t *) override { Add(obj); }
0090    void        AddBefore(const TObject *, TObject *obj) override { Add(obj); }
0091    void        AddBefore(const TObject *, TObject *obj, Option_t *) override { Add(obj); }
0092    TObject    *Remove(TObject *obj) override;
0093 
0094    TObject    *At(Int_t idx) const override;
0095    TObject    *Before(const TObject *obj) const override;
0096    TObject    *After(const TObject *obj) const override;
0097    TObject    *First() const override;
0098    TObject    *Last() const override;
0099 
0100    //void PrintOn(std::ostream &os) const;
0101 
0102    Int_t       Order() { return fOrder; }
0103    TObject    *operator[](Int_t i) const;
0104    Int_t       Rank(const TObject *obj) const;
0105 
0106    ClassDefOverride(TBtree,0)  //A B-tree
0107 };
0108 
0109 
0110 //////////////////////////////////////////////////////////////////////////
0111 //                                                                      //
0112 // TBtNode                                                              //
0113 //                                                                      //
0114 // Abstract base class (ABC) of a TBtree node.                          //
0115 //                                                                      //
0116 //////////////////////////////////////////////////////////////////////////
0117 
0118 class TBtNode {
0119 
0120 friend class  TBtree;
0121 friend class  TBtInnerNode;
0122 friend class  TBtLeafNode;
0123 
0124 protected:
0125    Int_t fLast;   // for inner node 1 <= fLast <= fInnerMaxIndex
0126                   // for leaf node  1 <= fLast <= fLeafMaxIndex
0127                   // (fLast==0 only temporarily while the tree is being
0128                   // updated)
0129 
0130    TBtInnerNode *fParent;   // a parent is always an inner node (or 0 for the root)
0131    TBtree       *fTree;     // the tree of which this node is a part
0132    Int_t         fIsLeaf;   // run-time type flag
0133 
0134 public:
0135    TBtNode(Int_t isleaf, TBtInnerNode *p, TBtree *t = nullptr);
0136    virtual ~TBtNode();
0137 
0138    virtual void Add(const TObject *obj, Int_t index) = 0;
0139    virtual TBtree *GetParentTree() const {return fTree;}
0140    virtual void Remove(Int_t index) = 0;
0141 
0142    virtual TObject *operator[](Int_t i) const = 0;
0143    virtual TObject *Found(const TObject *obj, TBtNode **which, Int_t *where) = 0;
0144 
0145    virtual Int_t FindRank(const TObject *obj) const = 0;
0146    virtual Int_t NofKeys() const = 0; // # keys in or below this node
0147 
0148    virtual TBtLeafNode *FirstLeafNode() = 0;
0149    virtual TBtLeafNode *LastLeafNode() = 0;
0150 
0151    virtual void Split() = 0;
0152    // virtual void PrintOn(std::ostream &os) const = 0;
0153    // friend std::ostream &operator<<(std::ostream &os, const TBtNode &node);
0154 };
0155 
0156 
0157 //////////////////////////////////////////////////////////////////////////
0158 //                                                                      //
0159 // TBtItem                                                              //
0160 //                                                                      //
0161 // Item stored in inner nodes of a TBtree.                              //
0162 //                                                                      //
0163 //////////////////////////////////////////////////////////////////////////
0164 
0165 class TBtItem {
0166 
0167 friend class  TBtInnerNode;
0168 
0169 private:
0170    Int_t      fNofKeysInTree;   // number of keys in TBtree
0171    TObject   *fKey;             // key
0172    TBtNode   *fTree;            ///<! sub-tree
0173 
0174 public:
0175    TBtItem();
0176    TBtItem(TBtNode *n, TObject *o);
0177    TBtItem(TObject *o, TBtNode *n);
0178    ~TBtItem();
0179 };
0180 
0181 
0182 //////////////////////////////////////////////////////////////////////////
0183 //                                                                      //
0184 // TBtInnerNode                                                         //
0185 //                                                                      //
0186 // Inner node of a TBtree.                                              //
0187 //                                                                      //
0188 //////////////////////////////////////////////////////////////////////////
0189 
0190 class TBtInnerNode : public TBtNode {
0191 
0192 private:
0193    TBtItem    *fItem;   // actually fItem[MaxIndex()+1] is desired
0194 
0195 public:
0196    TBtInnerNode(TBtInnerNode *parent, TBtree *t = nullptr);
0197    TBtInnerNode(TBtInnerNode *parent, TBtree *tree, TBtNode *oldroot);
0198    ~TBtInnerNode();
0199 
0200    void      Add(const TObject *obj, Int_t idx) override;
0201    void      Add(TBtItem &i, Int_t idx);
0202    void      Add(Int_t at, TObject *obj, TBtNode *n);
0203    void      AddElt(TBtItem &itm, Int_t at);
0204    void      AddElt(Int_t at, TObject *obj, TBtNode *n);
0205    void      Remove(Int_t idx) override;
0206    void      RemoveItem(Int_t idx);
0207 
0208    TObject  *operator[](Int_t i) const override;
0209    TObject  *Found(const TObject *obj, TBtNode **which, Int_t *where) override;
0210 
0211    Int_t     NofKeys(Int_t idx) const;
0212    Int_t     NofKeys() const override;
0213    void      SetTree(Int_t i, TBtNode *node) { fItem[i].fTree = node; node->fParent = this; }
0214    void      SetKey(Int_t i, TObject *obj) { fItem[i].fKey = obj; }
0215    void      SetItem(Int_t i, TBtItem &itm) { fItem[i] = itm; itm.fTree->fParent = this; }
0216    void      SetItem(Int_t i, TObject *obj, TBtNode *node) { SetTree(i, node); SetKey(i, obj); }
0217    Int_t     GetNofKeys(Int_t i) const;
0218    void      SetNofKeys(Int_t i, Int_t r);
0219    Int_t     IncNofKeys(Int_t i, Int_t n=1);
0220    Int_t     DecNofKeys(Int_t i, Int_t n=1);
0221    Int_t     FindRank(const TObject *obj) const override;
0222    Int_t     FindRankUp(const TBtNode *n) const;
0223    TBtNode  *GetTree(Int_t i) const { return fItem[i].fTree; }
0224    TObject  *GetKey(Int_t i) const { return fItem[i].fKey; }
0225    TBtItem  &GetItem(Int_t i) const { return fItem[i]; }
0226 
0227    Int_t     IndexOf(const TBtNode *n) const;
0228    void      IncrNofKeys(TBtNode *np);
0229    void      DecrNofKeys(TBtNode *np);
0230 
0231    TBtLeafNode *FirstLeafNode() override;
0232    TBtLeafNode *LastLeafNode() override;
0233 
0234    void      InformParent();
0235 
0236    void      Split() override;
0237    void      SplitWith(TBtInnerNode *r, Int_t idx);
0238    void      MergeWithRight(TBtInnerNode *r, Int_t idx);
0239    void      BalanceWithLeft(TBtInnerNode *l, Int_t idx);
0240    void      BalanceWithRight(TBtInnerNode *r, Int_t idx);
0241    void      BalanceWith(TBtInnerNode *n, int idx);
0242    void      PushLeft(Int_t cnt, TBtInnerNode *leftsib, Int_t parentIdx);
0243    void      PushRight(Int_t cnt, TBtInnerNode *rightsib, Int_t parentIdx);
0244    void      AppendFrom(TBtInnerNode *src, Int_t start, Int_t stop);
0245    void      Append(TObject *obj, TBtNode *n);
0246    void      Append(TBtItem &itm);
0247    void      ShiftLeft(Int_t cnt);
0248 
0249    Int_t     Psize() const { return fLast; }
0250    Int_t     Vsize() const;
0251    Int_t     MaxIndex() const { return fTree ? fTree->fInnerMaxIndex : 0; }
0252    Int_t     MaxPsize() const { return fTree ? fTree->fInnerMaxIndex : 0; }
0253 
0254    // void      PrintOn(std::ostream &os) const;
0255 
0256    Int_t     IsFull() const { return fLast == MaxIndex(); }
0257    void      IsFull(TBtNode *n);
0258    Int_t     IsAlmostFull() const { return fLast >= MaxIndex() - 1; }
0259    Int_t     IsLow() const {  return fLast < fTree->fInnerLowWaterMark; }
0260    void      IsLow(TBtNode *n);
0261 };
0262 
0263 
0264 //////////////////////////////////////////////////////////////////////////
0265 //                                                                      //
0266 // TBtLeafNode                                                          //
0267 //                                                                      //
0268 // Leaf node of a TBtree.                                               //
0269 //                                                                      //
0270 //////////////////////////////////////////////////////////////////////////
0271 
0272 class TBtLeafNode : public TBtNode {
0273 
0274 friend class  TBtInnerNode;
0275 
0276 private:
0277    TObject **fItem; // actually TObject *fItem[MaxIndex()+1] is desired
0278 
0279 public:
0280    TBtLeafNode(TBtInnerNode *p, const TObject *obj = nullptr, TBtree *t = nullptr);
0281    ~TBtLeafNode();
0282 
0283    void       Add(const TObject *obj, Int_t idx) override;
0284    void       Remove(Int_t idx) override;
0285    void       RemoveItem(Int_t idx) { Remove(idx); }
0286 
0287    TObject   *operator[](Int_t i) const override;
0288    TObject   *Found(const TObject *obj, TBtNode **which, Int_t *where) override;
0289 
0290    Int_t      NofKeys(Int_t i) const;
0291    Int_t      NofKeys() const override;
0292    Int_t      FindRank(const TObject *obj) const override;
0293    TObject   *GetKey(Int_t idx ) { return fItem[idx]; }
0294    void       SetKey(Int_t idx, TObject *obj) { fItem[idx] = obj; }
0295 
0296    Int_t      IndexOf(const TObject *obj) const;
0297 
0298    TBtLeafNode  *FirstLeafNode() override;
0299    TBtLeafNode  *LastLeafNode() override;
0300 
0301    void       Split() override;
0302    void       SplitWith(TBtLeafNode *r, Int_t idx);
0303    void       MergeWithRight(TBtLeafNode *r, Int_t idx);
0304    void       BalanceWithLeft(TBtLeafNode *l, Int_t idx);
0305    void       BalanceWithRight(TBtLeafNode *r, Int_t idx);
0306    void       BalanceWith(TBtLeafNode *n, Int_t idx);
0307    void       PushLeft(Int_t cnt, TBtLeafNode *l, Int_t parentIndex);
0308    void       PushRight(Int_t cnt, TBtLeafNode *r, Int_t parentIndex);
0309    void       AppendFrom(TBtLeafNode *src, Int_t start, Int_t stop);
0310    void       Append(TObject *obj);
0311    void       ShiftLeft(Int_t cnt);
0312 
0313    Int_t      Psize() const { return fLast + 1; }
0314    Int_t      Vsize() const;
0315    Int_t      MaxIndex() const { return fTree ? fTree->fLeafMaxIndex : 0; }
0316    Int_t      MaxPsize() const { return fTree ? fTree->fLeafMaxIndex + 1 : 0; }
0317 
0318    // void       PrintOn(std::ostream &os) const;
0319 
0320    Int_t      IsFull() const { return fLast == MaxIndex(); }
0321    Int_t      IsAlmostFull() const { return fLast >= MaxIndex() - 1; }
0322    Int_t      IsLow() const { return fLast < fTree->fLeafLowWaterMark; }
0323 };
0324 
0325 
0326 //////////////////////////////////////////////////////////////////////////
0327 //                                                                      //
0328 // TBtreeIter                                                           //
0329 //                                                                      //
0330 // Iterator of btree.                                                   //
0331 //                                                                      //
0332 //////////////////////////////////////////////////////////////////////////
0333 
0334 class TBtreeIter : public TIterator {
0335 
0336 private:
0337    const TBtree  *fTree;      //btree being iterated
0338    Int_t          fCurCursor; //current position in btree
0339    Int_t          fCursor;    //next position in btree
0340    Bool_t         fDirection; //iteration direction
0341 
0342    TBtreeIter() : fTree(nullptr), fCurCursor(0), fCursor(0), fDirection(kIterForward) { }
0343 
0344 public:
0345    using iterator_category = std::bidirectional_iterator_tag;
0346    using value_type = TObject *;
0347    using difference_type = std::ptrdiff_t;
0348    using pointer = TObject **;
0349    using const_pointer = const TObject **;
0350    using reference = const TObject *&;
0351 
0352    TBtreeIter(const TBtree *t, Bool_t dir = kIterForward);
0353    TBtreeIter(const TBtreeIter &iter);
0354    ~TBtreeIter() { }
0355    TIterator  &operator=(const TIterator &rhs) override;
0356    TBtreeIter &operator=(const TBtreeIter &rhs);
0357 
0358    const TCollection  *GetCollection() const override { return fTree; }
0359    TObject            *Next() override;
0360    void                Reset() override;
0361    Bool_t              operator!=(const TIterator &aIter) const override;
0362    Bool_t              operator!=(const TBtreeIter &aIter) const;
0363    TObject            *operator*() const override;
0364 
0365    ClassDefOverride(TBtreeIter,0)  //B-tree iterator
0366 };
0367 
0368 //----- TBtree inlines ---------------------------------------------------------
0369 
0370 inline TObject *TBtree::operator[](Int_t i) const
0371 {
0372    return (*fRoot)[i];
0373 }
0374 
0375 inline TObject *TBtree::At(Int_t i) const
0376 {
0377    return (*fRoot)[i];
0378 }
0379 
0380 inline TObject *TBtree::First() const
0381 {
0382    return (*fRoot)[0];
0383 }
0384 
0385 inline TObject *TBtree::Last() const
0386 {
0387    return (*fRoot)[fSize-1];
0388 }
0389 
0390 //----- TBtInnerNode inlines ---------------------------------------------------
0391 
0392 inline Int_t TBtInnerNode::GetNofKeys(Int_t i) const
0393 {
0394    R__ASSERT(i >= 0 && i <= fLast);
0395    return fItem[i].fNofKeysInTree;
0396 }
0397 
0398 inline Int_t TBtInnerNode::NofKeys(Int_t idx) const
0399 {
0400    return GetNofKeys(idx);
0401 }
0402 
0403 inline void TBtInnerNode::SetNofKeys(Int_t i, Int_t r)
0404 {
0405    fItem[i].fNofKeysInTree = r;
0406 }
0407 
0408 inline Int_t TBtInnerNode::IncNofKeys(Int_t i, Int_t n)
0409 {
0410    return (fItem[i].fNofKeysInTree += n);
0411 }
0412 
0413 inline Int_t TBtInnerNode::DecNofKeys(Int_t i, Int_t n)
0414 {
0415    return (fItem[i].fNofKeysInTree -= n);
0416 }
0417 
0418 inline Int_t TBtInnerNode::Vsize() const
0419 {
0420    R__ASSERT(fParent != nullptr && fParent->GetTree(0) != (const TBtNode *)this);
0421    return Psize()+1;
0422 }
0423 
0424 
0425 //----- TBtLeafNode inlines ----------------------------------------------------
0426 
0427 inline TObject *TBtLeafNode::operator[](Int_t i) const
0428 {
0429    R__ASSERT(i >= 0 && i <= fLast);
0430    return fItem[i];
0431 }
0432 
0433 inline Int_t TBtLeafNode::Vsize() const
0434 {
0435    R__ASSERT(fParent != nullptr && fParent->GetTree(0) != (const TBtNode *)this);
0436    return Psize()+1;
0437 }
0438 
0439 //inline std::ostream &operator<<(std::ostream& outputStream, const TBtNode &aNode)
0440 //{
0441 //   aNode.PrintOn(outputStream);
0442 //   return outputStream;
0443 //}
0444 
0445 #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!