Logo ROOT   6.21/01
Reference Guide
TBtree.h
Go to the documentation of this file.
1 // @(#)root/cont:$Id$
2 // Author: Fons Rademakers 10/10/95
3 
4 /*************************************************************************
5  * Copyright (C) 1995-2000, Rene Brun and Fons Rademakers. *
6  * All rights reserved. *
7  * *
8  * For the licensing terms see $ROOTSYS/LICENSE. *
9  * For the list of contributors see $ROOTSYS/README/CREDITS. *
10  *************************************************************************/
11 
12 #ifndef ROOT_TBtree
13 #define ROOT_TBtree
14 
15 
16 //////////////////////////////////////////////////////////////////////////
17 // //
18 // TBtree //
19 // //
20 // Btree class. TBtree inherits from the TSeqCollection ABC. //
21 // //
22 // For a more extensive algorithmic description see the TBtree source. //
23 // //
24 //////////////////////////////////////////////////////////////////////////
25 
26 #include "TSeqCollection.h"
27 #include "TError.h"
28 
29 #include <iterator>
30 
31 
32 class TBtNode;
33 class TBtInnerNode;
34 class TBtLeafNode;
35 class TBtreeIter;
36 
37 
38 class TBtree : public TSeqCollection {
39 
40 friend class TBtNode;
41 friend class TBtInnerNode;
42 friend class TBtLeafNode;
43 
44 private:
45  TBtNode *fRoot; //root node of btree
46 
47  Int_t fOrder; //the order of the tree (should be > 2)
48  Int_t fOrder2; //order*2+1 (assumes a memory access is
49  //cheaper than a multiply and increment by one
50  Int_t fInnerLowWaterMark; //inner node low water mark
51  Int_t fLeafLowWaterMark; //leaf low water mark
52  Int_t fInnerMaxIndex; //maximum inner node index
53  Int_t fLeafMaxIndex; //maximum leaf index
54 
55  void Init(Int_t i); //initialize btree
56  void RootIsFull(); //called when the root node is full
57  void RootIsEmpty(); //called when root is empty
58 
59 protected:
60  void IncrNofKeys() { fSize++; }
61  void DecrNofKeys() { fSize--; }
62 
63  // add the object to the tree; return the index in the tree at which
64  // the object was inserted. NOTE: other insertions and deletions may
65  // change this object's index.
66  Int_t IdxAdd(const TObject &obj);
67 
68 public:
70 
71  TBtree(Int_t ordern = 3); //create a TBtree of order n
72  virtual ~TBtree();
73  void Clear(Option_t *option="");
74  void Delete(Option_t *option="");
75  TObject *FindObject(const char *name) const;
76  TObject *FindObject(const TObject *obj) const;
77  TObject **GetObjectRef(const TObject *) const { return 0; }
79 
80  void Add(TObject *obj);
81  void AddFirst(TObject *obj) { Add(obj); }
82  void AddLast(TObject *obj) { Add(obj); }
83  void AddAt(TObject *obj, Int_t) { Add(obj); }
84  void AddAfter(const TObject *, TObject *obj) { Add(obj); }
85  void AddBefore(const TObject *, TObject *obj) { Add(obj); }
86  TObject *Remove(TObject *obj);
87 
88  TObject *At(Int_t idx) const;
89  TObject *Before(const TObject *obj) const;
90  TObject *After(const TObject *obj) const;
91  TObject *First() const;
92  TObject *Last() const;
93 
94  //void PrintOn(std::ostream &os) const;
95 
96  Int_t Order() { return fOrder; }
97  TObject *operator[](Int_t i) const;
98  Int_t Rank(const TObject *obj) const;
99 
100  ClassDef(TBtree,0) //A B-tree
101 };
102 
103 
104 //////////////////////////////////////////////////////////////////////////
105 // //
106 // TBtNode //
107 // //
108 // Abstract base class (ABC) of a TBtree node. //
109 // //
110 //////////////////////////////////////////////////////////////////////////
111 
112 class TBtNode {
113 
114 friend class TBtree;
115 friend class TBtInnerNode;
116 friend class TBtLeafNode;
117 
118 protected:
119  Int_t fLast; // for inner node 1 <= fLast <= fInnerMaxIndex
120  // for leaf node 1 <= fLast <= fLeafMaxIndex
121  // (fLast==0 only temporarily while the tree is being
122  // updated)
123 
124  TBtInnerNode *fParent; // a parent is always an inner node (or 0 for the root)
125  TBtree *fTree; // the tree of which this node is a part
126  Int_t fIsLeaf; // run-time type flag
127 
128 public:
129  TBtNode(Int_t isleaf, TBtInnerNode *p, TBtree *t = 0);
130  virtual ~TBtNode();
131 
132  virtual void Add(const TObject *obj, Int_t index) = 0;
133 #ifndef __CINT__
134  virtual TBtree *GetParentTree() const {return fTree;}
135  virtual void Remove(Int_t index) = 0;
136 
137  virtual TObject *operator[](Int_t i) const = 0;
138  virtual TObject *Found(const TObject *obj, TBtNode **which, Int_t *where) = 0;
139 
140  virtual Int_t FindRank(const TObject *obj) const = 0;
141  virtual Int_t NofKeys() const = 0; // # keys in or below this node
142 
143  virtual TBtLeafNode *FirstLeafNode() = 0;
144  virtual TBtLeafNode *LastLeafNode() = 0;
145 
146  virtual void Split() = 0;
147 #endif
148  // virtual void PrintOn(std::ostream &os) const = 0;
149  // friend std::ostream &operator<<(std::ostream &os, const TBtNode &node);
150 };
151 
152 
153 //////////////////////////////////////////////////////////////////////////
154 // //
155 // TBtItem //
156 // //
157 // Item stored in inner nodes of a TBtree. //
158 // //
159 //////////////////////////////////////////////////////////////////////////
160 
161 class TBtItem {
162 
163 friend class TBtInnerNode;
164 
165 private:
166  Int_t fNofKeysInTree; // number of keys in TBtree
167  TObject *fKey; // key
168  TBtNode *fTree; //! sub-tree
169 
170 public:
171  TBtItem();
172  TBtItem(TBtNode *n, TObject *o);
173  TBtItem(TObject *o, TBtNode *n);
174  ~TBtItem();
175 };
176 
177 
178 //////////////////////////////////////////////////////////////////////////
179 // //
180 // TBtInnerNode //
181 // //
182 // Inner node of a TBtree. //
183 // //
184 //////////////////////////////////////////////////////////////////////////
185 
186 class TBtInnerNode : public TBtNode {
187 
188 private:
189  TBtItem *fItem; // actually fItem[MaxIndex()+1] is desired
190 
191 public:
192  TBtInnerNode(TBtInnerNode *parent, TBtree *t = 0);
193  TBtInnerNode(TBtInnerNode *parent, TBtree *tree, TBtNode *oldroot);
194  ~TBtInnerNode();
195 
196 #ifndef __CINT__
197  void Add(const TObject *obj, Int_t idx);
198  void Add(TBtItem &i, Int_t idx);
199  void Add(Int_t at, TObject *obj, TBtNode *n);
200  void AddElt(TBtItem &itm, Int_t at);
201  void AddElt(Int_t at, TObject *obj, TBtNode *n);
202  void Remove(Int_t idx);
203  void RemoveItem(Int_t idx);
204 
205  TObject *operator[](Int_t i) const;
206  TObject *Found(const TObject *obj, TBtNode **which, Int_t *where);
207 
208  Int_t NofKeys(Int_t idx) const;
209  Int_t NofKeys() const;
210  void SetTree(Int_t i, TBtNode *node) { fItem[i].fTree = node; node->fParent = this; }
211  void SetKey(Int_t i, TObject *obj) { fItem[i].fKey = obj; }
212  void SetItem(Int_t i, TBtItem &itm) { fItem[i] = itm; itm.fTree->fParent = this; }
213  void SetItem(Int_t i, TObject *obj, TBtNode *node) { SetTree(i, node); SetKey(i, obj); }
214  Int_t GetNofKeys(Int_t i) const;
215  void SetNofKeys(Int_t i, Int_t r);
216  Int_t IncNofKeys(Int_t i, Int_t n=1);
217  Int_t DecNofKeys(Int_t i, Int_t n=1);
218  Int_t FindRank(const TObject *obj) const;
219  Int_t FindRankUp(const TBtNode *n) const;
220  TBtNode *GetTree(Int_t i) const { return fItem[i].fTree; }
221  TObject *GetKey(Int_t i) const { return fItem[i].fKey; }
222  TBtItem &GetItem(Int_t i) const { return fItem[i]; }
223 
224  Int_t IndexOf(const TBtNode *n) const;
225  void IncrNofKeys(TBtNode *np);
226  void DecrNofKeys(TBtNode *np);
227 
230 
231  void InformParent();
232 
233  void Split();
234  void SplitWith(TBtInnerNode *r, Int_t idx);
235  void MergeWithRight(TBtInnerNode *r, Int_t idx);
236  void BalanceWithLeft(TBtInnerNode *l, Int_t idx);
237  void BalanceWithRight(TBtInnerNode *r, Int_t idx);
238  void BalanceWith(TBtInnerNode *n, int idx);
239  void PushLeft(Int_t cnt, TBtInnerNode *leftsib, Int_t parentIdx);
240  void PushRight(Int_t cnt, TBtInnerNode *rightsib, Int_t parentIdx);
241  void AppendFrom(TBtInnerNode *src, Int_t start, Int_t stop);
242  void Append(TObject *obj, TBtNode *n);
243  void Append(TBtItem &itm);
244  void ShiftLeft(Int_t cnt);
245 
246  Int_t Psize() const { return fLast; }
247  Int_t Vsize() const;
248  Int_t MaxIndex() const { return fTree->fInnerMaxIndex; }
249  Int_t MaxPsize() const { return fTree->fInnerMaxIndex; }
250 
251  // void PrintOn(std::ostream &os) const;
252 
253  Int_t IsFull() const { return fLast == MaxIndex(); }
254  void IsFull(TBtNode *n);
255  Int_t IsAlmostFull() const { return fLast >= MaxIndex() - 1; }
256  Int_t IsLow() const { return fLast < fTree->fInnerLowWaterMark; }
257  void IsLow(TBtNode *n);
258 #endif
259 };
260 
261 
262 //////////////////////////////////////////////////////////////////////////
263 // //
264 // TBtLeafNode //
265 // //
266 // Leaf node of a TBtree. //
267 // //
268 //////////////////////////////////////////////////////////////////////////
269 
270 class TBtLeafNode : public TBtNode {
271 
272 friend class TBtInnerNode;
273 
274 private:
275  TObject **fItem; // actually TObject *fItem[MaxIndex()+1] is desired
276 
277 public:
278  TBtLeafNode(TBtInnerNode *p, const TObject *obj = 0, TBtree *t = 0);
279  ~TBtLeafNode();
280 
281 #ifndef __CINT__
282  void Add(const TObject *obj, Int_t idx);
283  void Remove(Int_t idx);
284  void RemoveItem(Int_t idx) { Remove(idx); }
285 
286  TObject *operator[](Int_t i) const;
287  TObject *Found(const TObject *obj, TBtNode **which, Int_t *where);
288 
289  Int_t NofKeys(Int_t i) const;
290  Int_t NofKeys() const;
291  Int_t FindRank(const TObject *obj) const;
292  TObject *GetKey(Int_t idx ) { return fItem[idx]; }
293  void SetKey(Int_t idx, TObject *obj) { fItem[idx] = obj; }
294 
295  Int_t IndexOf(const TObject *obj) const;
296 
299 
300  void Split();
301  void SplitWith(TBtLeafNode *r, Int_t idx);
302  void MergeWithRight(TBtLeafNode *r, Int_t idx);
303  void BalanceWithLeft(TBtLeafNode *l, Int_t idx);
304  void BalanceWithRight(TBtLeafNode *r, Int_t idx);
305  void BalanceWith(TBtLeafNode *n, Int_t idx);
306  void PushLeft(Int_t cnt, TBtLeafNode *l, Int_t parentIndex);
307  void PushRight(Int_t cnt, TBtLeafNode *r, Int_t parentIndex);
308  void AppendFrom(TBtLeafNode *src, Int_t start, Int_t stop);
309  void Append(TObject *obj);
310  void ShiftLeft(Int_t cnt);
311 
312  Int_t Psize() const { return fLast + 1; }
313  Int_t Vsize() const;
314  Int_t MaxIndex() const { return fTree->fLeafMaxIndex; }
315  Int_t MaxPsize() const { return fTree->fLeafMaxIndex + 1; }
316 
317  // void PrintOn(std::ostream &os) const;
318 
319  Int_t IsFull() const { return fLast == MaxIndex(); }
320  Int_t IsAlmostFull() const { return fLast >= MaxIndex() - 1; }
321  Int_t IsLow() const { return fLast < fTree->fLeafLowWaterMark; }
322 #endif
323 };
324 
325 
326 //////////////////////////////////////////////////////////////////////////
327 // //
328 // TBtreeIter //
329 // //
330 // Iterator of btree. //
331 // //
332 //////////////////////////////////////////////////////////////////////////
333 
334 class TBtreeIter : public TIterator,
335  public std::iterator<std::bidirectional_iterator_tag,
336  TObject*, std::ptrdiff_t,
337  const TObject**, const TObject*&> {
338 
339 private:
340  const TBtree *fTree; //btree being iterated
341  Int_t fCurCursor; //current position in btree
342  Int_t fCursor; //next position in btree
343  Bool_t fDirection; //iteration direction
344 
346 
347 public:
348  TBtreeIter(const TBtree *t, Bool_t dir = kIterForward);
349  TBtreeIter(const TBtreeIter &iter);
351  TIterator &operator=(const TIterator &rhs);
352  TBtreeIter &operator=(const TBtreeIter &rhs);
353 
354  const TCollection *GetCollection() const { return fTree; }
355  TObject *Next();
356  void Reset();
357  Bool_t operator!=(const TIterator &aIter) const;
358  Bool_t operator!=(const TBtreeIter &aIter) const;
359  TObject *operator*() const;
360 
361  ClassDef(TBtreeIter,0) //B-tree iterator
362 };
363 
364 
365 //----- TBtree inlines ---------------------------------------------------------
366 
368 {
369  return (*fRoot)[i];
370 }
371 
372 inline TObject *TBtree::At(Int_t i) const
373 {
374  return (*fRoot)[i];
375 }
376 
377 inline TObject *TBtree::First() const
378 {
379  return (*fRoot)[0];
380 }
381 
382 inline TObject *TBtree::Last() const
383 {
384  return (*fRoot)[fSize-1];
385 }
386 
387 //----- TBtInnerNode inlines ---------------------------------------------------
388 
390 {
391  R__ASSERT(i >= 0 && i <= fLast);
392  return fItem[i].fNofKeysInTree;
393 }
394 
396 {
397  return GetNofKeys(idx);
398 }
399 
401 {
402  fItem[i].fNofKeysInTree = r;
403 }
404 
406 {
407  return (fItem[i].fNofKeysInTree += n);
408 }
409 
411 {
412  return (fItem[i].fNofKeysInTree -= n);
413 }
414 
416 {
417  R__ASSERT(fParent != 0 && fParent->GetTree(0) != (const TBtNode *)this);
418  return Psize()+1;
419 }
420 
421 
422 //----- TBtLeafNode inlines ----------------------------------------------------
423 
425 {
426  R__ASSERT(i >= 0 && i <= fLast);
427  return fItem[i];
428 }
429 
430 inline Int_t TBtLeafNode::Vsize() const
431 {
432  R__ASSERT(fParent != 0 && fParent->GetTree(0) != (const TBtNode *)this);
433  return Psize()+1;
434 }
435 
436 //inline std::ostream &operator<<(std::ostream& outputStream, const TBtNode &aNode)
437 //{
438 // aNode.PrintOn(outputStream);
439 // return outputStream;
440 //}
441 
442 #endif
TBtLeafNode(TBtInnerNode *p, const TObject *obj=0, TBtree *t=0)
Constructor.
Definition: TBtree.cxx:1363
void SetItem(Int_t i, TBtItem &itm)
Definition: TBtree.h:212
TObject * Before(const TObject *obj) const
May not use this method since B-tree decides order.
Definition: TBtree.cxx:237
void BalanceWithLeft(TBtLeafNode *l, Int_t idx)
THIS has more than LEFTSIB; move some items from THIS to LEFTSIB.
Definition: TBtree.cxx:1452
void InformParent()
Tell the parent that we are full.
Definition: TBtree.cxx:958
void SetKey(Int_t idx, TObject *obj)
Definition: TBtree.h:293
const TBtree * fTree
Definition: TBtree.h:340
Int_t IsFull() const
Definition: TBtree.h:253
Int_t fLeafMaxIndex
Definition: TBtree.h:53
void SetItem(Int_t i, TObject *obj, TBtNode *node)
Definition: TBtree.h:213
TBtItem * fItem
Definition: TBtree.h:189
void ShiftLeft(Int_t cnt)
Shift.
Definition: TBtree.cxx:1679
Int_t GetNofKeys(Int_t i) const
Definition: TBtree.h:389
void AddLast(TObject *obj)
Definition: TBtree.h:82
TObject * GetKey(Int_t i) const
Definition: TBtree.h:221
Int_t DecNofKeys(Int_t i, Int_t n=1)
Definition: TBtree.h:410
void AppendFrom(TBtInnerNode *src, Int_t start, Int_t stop)
This should never create a full node that is, it is not used anywhere where THIS could possibly be ne...
Definition: TBtree.cxx:777
Leaf node of a TBtree.
Definition: TBtree.h:270
TBtreeIter Iterator_t
Definition: TBtree.h:69
~TBtItem()
Delete a tree item.
Definition: TBtree.cxx:530
TObject * operator[](Int_t i) const
Definition: TBtree.h:367
Int_t fLeafLowWaterMark
Definition: TBtree.h:51
void SetNofKeys(Int_t i, Int_t r)
Definition: TBtree.h:400
virtual TBtree * GetParentTree() const
Definition: TBtree.h:134
const char Option_t
Definition: RtypesCore.h:62
TBtInnerNode(TBtInnerNode *parent, TBtree *t=0)
Create a B-tree innernode.
Definition: TBtree.cxx:688
Int_t fInnerMaxIndex
Definition: TBtree.h:52
Int_t Rank(const TObject *obj) const
Returns the rank of the object in the tree.
Definition: TBtree.cxx:393
TObject * FindObject(const char *name) const
Find object using its name (see object&#39;s GetName()).
Definition: TBtree.cxx:275
Int_t MaxPsize() const
Definition: TBtree.h:249
Int_t NofKeys() const
Return the number of keys.
Definition: TBtree.cxx:1575
void RemoveItem(Int_t idx)
Definition: TBtree.h:284
void Add(TObject *obj)
Add object to B-tree.
Definition: TBtree.cxx:200
Int_t Psize() const
Definition: TBtree.h:312
virtual ~TBtree()
Delete B-tree.
Definition: TBtree.cxx:189
Abstract base class (ABC) of a TBtree node.
Definition: TBtree.h:112
TBtLeafNode * FirstLeafNode()
Return the first node.
Definition: TBtree.cxx:1501
void AddAfter(const TObject *, TObject *obj)
Definition: TBtree.h:84
TBtree * fTree
Definition: TBtree.h:125
#define R__ASSERT(e)
Definition: TError.h:96
virtual TObject * operator[](Int_t i) const =0
void RootIsEmpty()
If root is empty clean up its space.
Definition: TBtree.cxx:441
Int_t NofKeys() const
Number of key.
Definition: TBtree.cxx:1136
Int_t Order()
Definition: TBtree.h:96
int Int_t
Definition: RtypesCore.h:41
bool Bool_t
Definition: RtypesCore.h:59
void Clear(Option_t *option="")
Remove all objects from B-tree.
Definition: TBtree.cxx:247
~TBtreeIter()
Definition: TBtree.h:350
virtual TObject * Found(const TObject *obj, TBtNode **which, Int_t *where)=0
void DecrNofKeys()
Definition: TBtree.h:61
virtual ~TBtNode()
Delete a B-tree node.
Definition: TBtree.cxx:564
TBtNode * fRoot
Definition: TBtree.h:45
void BalanceWithRight(TBtInnerNode *r, Int_t idx)
THIS has more than RIGHTSIB.
Definition: TBtree.cxx:826
Int_t IdxAdd(const TObject &obj)
Add object and return its index in the tree.
Definition: TBtree.cxx:301
TObject * operator[](Int_t i) const
return an element.
Definition: TBtree.cxx:1147
TObject * operator*() const
Return current object or nullptr.
Definition: TBtree.cxx:675
Int_t FindRankUp(const TBtNode *n) const
FindRankUp is FindRank in reverse.
Definition: TBtree.cxx:890
Iterator abstract base class.
Definition: TIterator.h:30
TObject * operator[](Int_t i) const
Definition: TBtree.h:424
void AddElt(TBtItem &itm, Int_t at)
Add one element.
Definition: TBtree.cxx:735
virtual void Add(const TObject *obj, Int_t index)=0
void PushLeft(Int_t cnt, TBtInnerNode *leftsib, Int_t parentIdx)
noFromThis==1 => moves the parent item into the leftsib, and the first item in this&#39;s array into the ...
Definition: TBtree.cxx:1170
Bool_t fDirection
Definition: TBtree.h:343
TObject * Next()
Get next object from B-tree. Returns 0 when no more objects in tree.
Definition: TBtree.cxx:639
Sequenceable collection abstract base class.
void SetTree(Int_t i, TBtNode *node)
Definition: TBtree.h:210
Int_t IsFull() const
Definition: TBtree.h:319
#define ClassDef(name, id)
Definition: Rtypes.h:326
Int_t fCursor
Definition: TBtree.h:342
void Remove(Int_t idx)
Remove an element.
Definition: TBtree.cxx:1656
void MergeWithRight(TBtLeafNode *r, Int_t idx)
Merge.
Definition: TBtree.cxx:1554
void Reset()
Reset the B-tree iterator.
Definition: TBtree.cxx:626
TObject * Found(const TObject *obj, TBtNode **which, Int_t *where)
Recursively look for WHAT starting in the current node.
Definition: TBtree.cxx:910
Item stored in inner nodes of a TBtree.
Definition: TBtree.h:161
TObject * GetKey(Int_t idx)
Definition: TBtree.h:292
TIterator & operator=(const TIterator &rhs)
Overridden assignment operator.
Definition: TBtree.cxx:597
TBtLeafNode * LastLeafNode()
Return the last leaf node.
Definition: TBtree.cxx:1113
const Bool_t kIterForward
Definition: TCollection.h:40
TBtNode(Int_t isleaf, TBtInnerNode *p, TBtree *t=0)
Create a B-tree node.
Definition: TBtree.cxx:541
TObject * Last() const
Definition: TBtree.h:382
void BalanceWith(TBtLeafNode *n, Int_t idx)
PITEM is the parent item whose key will change when keys are shifted from one LeafNode to the other...
Definition: TBtree.cxx:1475
Int_t FindRank(const TObject *obj) const
WHAT was not in any inner node; it is either here, or it&#39;s not in the tree.
Definition: TBtree.cxx:1487
Int_t MaxIndex() const
Definition: TBtree.h:314
TBtItem & GetItem(Int_t i) const
Definition: TBtree.h:222
TBtNode * fTree
Definition: TBtree.h:168
TBtLeafNode * LastLeafNode()
return the last node.
Definition: TBtree.cxx:1546
Int_t fNofKeysInTree
Definition: TBtree.h:166
void MergeWithRight(TBtInnerNode *r, Int_t idx)
Merge the 2 part of the tree.
Definition: TBtree.cxx:1121
Int_t fOrder2
Definition: TBtree.h:48
Int_t fOrder
Definition: TBtree.h:47
TIterator * MakeIterator(Bool_t dir=kIterForward) const
Returns a B-tree iterator.
Definition: TBtree.cxx:385
Int_t Vsize() const
Definition: TBtree.h:430
Int_t MaxPsize() const
Definition: TBtree.h:315
virtual TBtLeafNode * LastLeafNode()=0
void Split()
This function is called only when THIS is the only descendent of the root node, and THIS needs to be ...
Definition: TBtree.cxx:1277
ROOT::R::TRInterface & r
Definition: Object.C:4
Int_t fCurCursor
Definition: TBtree.h:341
void PushRight(Int_t cnt, TBtLeafNode *r, Int_t parentIndex)
noFromThis==1 => moves the parent item into the rightsib, and the last item in this&#39;s array into the ...
Definition: TBtree.cxx:1612
virtual void Split()=0
void PushLeft(Int_t cnt, TBtLeafNode *l, Int_t parentIndex)
noFromThis==1 => moves the parent item into the leftsib, and the first item in this&#39;s array into the ...
Definition: TBtree.cxx:1593
Int_t fIsLeaf
Definition: TBtree.h:126
void Append(TObject *obj, TBtNode *n)
Never called from anywhere where it might fill up THIS.
Definition: TBtree.cxx:791
void AppendFrom(TBtLeafNode *src, Int_t start, Int_t stop)
A convenience function, does not worry about the element in the parent, simply moves elements from SR...
Definition: TBtree.cxx:1426
TObject * fKey
Definition: TBtree.h:167
void BalanceWithRight(TBtLeafNode *r, Int_t idx)
THIS has more than RIGHTSIB; move some items from THIS to RIGHTSIB.
Definition: TBtree.cxx:1463
Collection abstract base class.
Definition: TCollection.h:63
Int_t IsLow() const
Definition: TBtree.h:256
TObject ** GetObjectRef(const TObject *) const
Definition: TBtree.h:77
void DecrNofKeys(TBtNode *np)
THAT is a child of THIS that has just shrunk by 1.
Definition: TBtree.cxx:850
void RootIsFull()
The root of the tree is full.
Definition: TBtree.cxx:430
Int_t fLast
Definition: TBtree.h:119
void Append(TObject *obj)
Never called from anywhere where it might fill up THIS does NOT handle nofKeys.
Definition: TBtree.cxx:1442
void IncrNofKeys(TBtNode *np)
THAT is a child of THIS that has just grown by 1.
Definition: TBtree.cxx:932
TObject * At(Int_t idx) const
Definition: TBtree.h:372
TObject * After(const TObject *obj) const
Cannot use this method since B-tree decides order.
Definition: TBtree.cxx:228
void Init(Int_t i)
Initialize a B-tree.
Definition: TBtree.cxx:344
TBtree(Int_t ordern=3)
Create a B-tree of certain order (by default 3).
Definition: TBtree.cxx:180
void Remove(Int_t idx)
Remove an element.
Definition: TBtree.cxx:1233
virtual void Remove(Int_t index)=0
Int_t Psize() const
Definition: TBtree.h:246
virtual Int_t FindRank(const TObject *obj) const =0
Int_t IsAlmostFull() const
Definition: TBtree.h:320
~TBtLeafNode()
Destructor.
Definition: TBtree.cxx:1376
void AddAt(TObject *obj, Int_t)
Definition: TBtree.h:83
~TBtInnerNode()
Constructor.
Definition: TBtree.cxx:712
Iterator of btree.
Definition: TBtree.h:334
Int_t IndexOf(const TBtNode *n) const
Returns a number in the range 0 to this->fLast 0 is returned if THAT == fTree[0]. ...
Definition: TBtree.cxx:946
void AddFirst(TObject *obj)
Definition: TBtree.h:81
Int_t IndexOf(const TObject *obj) const
Returns a number in the range 0 to MaxIndex().
Definition: TBtree.cxx:1533
void SplitWith(TBtLeafNode *r, Int_t idx)
Split.
Definition: TBtree.cxx:1706
TBtreeIter()
Definition: TBtree.h:345
TObject * Remove(TObject *obj)
Remove an object from the tree.
Definition: TBtree.cxx:408
Int_t IncNofKeys(Int_t i, Int_t n=1)
Definition: TBtree.h:405
Int_t IsAlmostFull() const
Definition: TBtree.h:255
void IncrNofKeys()
Definition: TBtree.h:60
void SetKey(Int_t i, TObject *obj)
Definition: TBtree.h:211
void Delete(Option_t *option="")
Remove all objects from B-tree AND delete all heap based objects.
Definition: TBtree.cxx:260
void BalanceWithLeft(TBtInnerNode *l, Int_t idx)
THIS has more than LEFTSIB.
Definition: TBtree.cxx:812
const TCollection * GetCollection() const
Definition: TBtree.h:354
Int_t FindRank(const TObject *obj) const
Recursively look for WHAT starting in the current node.
Definition: TBtree.cxx:863
void PushRight(Int_t cnt, TBtInnerNode *rightsib, Int_t parentIdx)
The operation is three steps:
Definition: TBtree.cxx:1189
TObject * First() const
Definition: TBtree.h:377
void AddBefore(const TObject *, TObject *obj)
Definition: TBtree.h:85
Mother of all ROOT objects.
Definition: TObject.h:37
void RemoveItem(Int_t idx)
Remove an item.
Definition: TBtree.cxx:1244
Int_t Vsize() const
Definition: TBtree.h:415
TObject * Found(const TObject *obj, TBtNode **which, Int_t *where)
WHAT was not in any inner node; it is either here, or it&#39;s not in the tree.
Definition: TBtree.cxx:1510
TBtLeafNode * FirstLeafNode()
Return the first leaf node.
Definition: TBtree.cxx:902
auto * l
Definition: textangle.C:4
void ShiftLeft(Int_t cnt)
Shift to the left.
Definition: TBtree.cxx:1263
Bool_t operator!=(const TIterator &aIter) const
This operator compares two TIterator objects.
Definition: TBtree.cxx:655
Definition: tree.py:1
Int_t MaxIndex() const
Definition: TBtree.h:248
void SplitWith(TBtInnerNode *r, Int_t idx)
THIS and SIB are too full; create a NEWNODE, and balance the number of keys between the three of them...
Definition: TBtree.cxx:1316
virtual TBtLeafNode * FirstLeafNode()=0
Inner node of a TBtree.
Definition: TBtree.h:186
void Split()
This function is called only when THIS is the only descendent of the root node, and THIS needs to be ...
Definition: TBtree.cxx:1693
virtual Int_t NofKeys() const =0
TBtNode * GetTree(Int_t i) const
Definition: TBtree.h:220
TObject ** fItem
Definition: TBtree.h:275
Int_t fInnerLowWaterMark
Definition: TBtree.h:50
const Int_t n
Definition: legend1.C:16
B-tree class.
Definition: TBtree.h:38
char name[80]
Definition: TGX11.cxx:109
const char * cnt
Definition: TXMLSetup.cxx:74
TBtInnerNode * fParent
Definition: TBtree.h:124
void Add(const TObject *obj, Int_t idx)
This is called only from TBtree::Add().
Definition: TBtree.cxx:725
Int_t IsLow() const
Definition: TBtree.h:321
void Add(const TObject *obj, Int_t idx)
Add the object OBJ to the leaf node, inserting it at location INDEX in the fItem array.
Definition: TBtree.cxx:1385
void BalanceWith(TBtInnerNode *n, int idx)
PINDX is the index of the parent item whose key will change when keys are shifted from one InnerNode ...
Definition: TBtree.cxx:839
TBtItem()
sub-tree
Definition: TBtree.cxx:496