Logo ROOT   6.16/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
32class TBtNode;
33class TBtInnerNode;
34class TBtLeafNode;
35class TBtreeIter;
36
37
38class TBtree : public TSeqCollection {
39
40friend class TBtNode;
41friend class TBtInnerNode;
42friend class TBtLeafNode;
43
44private:
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
59protected:
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
68public:
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
112class TBtNode {
113
114friend class TBtree;
115friend class TBtInnerNode;
116friend class TBtLeafNode;
117
118protected:
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
128public:
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
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
161class TBtItem {
162
163friend class TBtInnerNode;
164
165private:
166 Int_t fNofKeysInTree; // number of keys in TBtree
167 TObject *fKey; // key
168 TBtNode *fTree; //! sub-tree
169
170public:
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
186class TBtInnerNode : public TBtNode {
187
188private:
189 TBtItem *fItem; // actually fItem[MaxIndex()+1] is desired
190
191public:
192 TBtInnerNode(TBtInnerNode *parent, TBtree *t = 0);
193 TBtInnerNode(TBtInnerNode *parent, TBtree *tree, TBtNode *oldroot);
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);
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);
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
270class TBtLeafNode : public TBtNode {
271
272friend class TBtInnerNode;
273
274private:
275 TObject **fItem; // actually TObject *fItem[MaxIndex()+1] is desired
276
277public:
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);
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
334class TBtreeIter : public TIterator,
335 public std::iterator<std::bidirectional_iterator_tag,
336 TObject*, std::ptrdiff_t,
337 const TObject**, const TObject*&> {
338
339private:
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
347public:
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
372inline TObject *TBtree::At(Int_t i) const
373{
374 return (*fRoot)[i];
375}
376
377inline TObject *TBtree::First() const
378{
379 return (*fRoot)[0];
380}
381
382inline 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{
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
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
ROOT::R::TRInterface & r
Definition: Object.C:4
int Int_t
Definition: RtypesCore.h:41
bool Bool_t
Definition: RtypesCore.h:59
const char Option_t
Definition: RtypesCore.h:62
#define ClassDef(name, id)
Definition: Rtypes.h:324
const Bool_t kIterForward
Definition: TCollection.h:40
#define R__ASSERT(e)
Definition: TError.h:96
Inner node of a TBtree.
Definition: TBtree.h:186
Int_t DecNofKeys(Int_t i, Int_t n=1)
Definition: TBtree.h:410
void InformParent()
Tell the parent that we are full.
Definition: TBtree.cxx:958
void ShiftLeft(Int_t cnt)
Shift to the left.
Definition: TBtree.cxx:1263
TBtLeafNode * LastLeafNode()
Return the last leaf node.
Definition: TBtree.cxx:1113
void BalanceWithLeft(TBtInnerNode *l, Int_t idx)
THIS has more than LEFTSIB.
Definition: TBtree.cxx:812
Int_t IncNofKeys(Int_t i, Int_t n=1)
Definition: TBtree.h:405
void BalanceWithRight(TBtInnerNode *r, Int_t idx)
THIS has more than RIGHTSIB.
Definition: TBtree.cxx:826
Int_t FindRankUp(const TBtNode *n) const
FindRankUp is FindRank in reverse.
Definition: TBtree.cxx:890
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
void Append(TObject *obj, TBtNode *n)
Never called from anywhere where it might fill up THIS.
Definition: TBtree.cxx:791
void Add(const TObject *obj, Int_t idx)
This is called only from TBtree::Add().
Definition: TBtree.cxx:725
Int_t IsFull() const
Definition: TBtree.h:253
TBtItem & GetItem(Int_t i) const
Definition: TBtree.h:222
void SetKey(Int_t i, TObject *obj)
Definition: TBtree.h:211
Int_t GetNofKeys(Int_t i) const
Definition: TBtree.h:389
void AddElt(TBtItem &itm, Int_t at)
Add one element.
Definition: TBtree.cxx:735
Int_t MaxIndex() const
Definition: TBtree.h:248
Int_t Vsize() const
Definition: TBtree.h:415
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 MergeWithRight(TBtInnerNode *r, Int_t idx)
Merge the 2 part of the tree.
Definition: TBtree.cxx:1121
TBtLeafNode * FirstLeafNode()
Return the first leaf node.
Definition: TBtree.cxx:902
Int_t IsAlmostFull() const
Definition: TBtree.h:255
void SetItem(Int_t i, TBtItem &itm)
Definition: TBtree.h:212
void SetNofKeys(Int_t i, Int_t r)
Definition: TBtree.h:400
TObject * operator[](Int_t i) const
return an element.
Definition: TBtree.cxx:1147
Int_t MaxPsize() const
Definition: TBtree.h:249
void SetTree(Int_t i, TBtNode *node)
Definition: TBtree.h:210
Int_t FindRank(const TObject *obj) const
Recursively look for WHAT starting in the current node.
Definition: TBtree.cxx:863
void Remove(Int_t idx)
Remove an element.
Definition: TBtree.cxx:1233
Int_t NofKeys() const
Number of key.
Definition: TBtree.cxx:1136
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's array into the ...
Definition: TBtree.cxx:1170
void IncrNofKeys(TBtNode *np)
THAT is a child of THIS that has just grown by 1.
Definition: TBtree.cxx:932
TObject * GetKey(Int_t i) const
Definition: TBtree.h:221
void SetItem(Int_t i, TObject *obj, TBtNode *node)
Definition: TBtree.h:213
void DecrNofKeys(TBtNode *np)
THAT is a child of THIS that has just shrunk by 1.
Definition: TBtree.cxx:850
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
~TBtInnerNode()
Constructor.
Definition: TBtree.cxx:712
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
void PushRight(Int_t cnt, TBtInnerNode *rightsib, Int_t parentIdx)
The operation is three steps:
Definition: TBtree.cxx:1189
TBtNode * GetTree(Int_t i) const
Definition: TBtree.h:220
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
TObject * Found(const TObject *obj, TBtNode **which, Int_t *where)
Recursively look for WHAT starting in the current node.
Definition: TBtree.cxx:910
void RemoveItem(Int_t idx)
Remove an item.
Definition: TBtree.cxx:1244
TBtItem * fItem
Definition: TBtree.h:189
Int_t IsLow() const
Definition: TBtree.h:256
Int_t Psize() const
Definition: TBtree.h:246
Item stored in inner nodes of a TBtree.
Definition: TBtree.h:161
TBtItem()
sub-tree
Definition: TBtree.cxx:496
~TBtItem()
Delete a tree item.
Definition: TBtree.cxx:530
TObject * fKey
Definition: TBtree.h:167
Int_t fNofKeysInTree
Definition: TBtree.h:166
TBtNode * fTree
Definition: TBtree.h:168
Leaf node of a TBtree.
Definition: TBtree.h:270
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
void BalanceWithRight(TBtLeafNode *r, Int_t idx)
THIS has more than RIGHTSIB; move some items from THIS to RIGHTSIB.
Definition: TBtree.cxx:1463
Int_t Vsize() const
Definition: TBtree.h:430
TObject * GetKey(Int_t idx)
Definition: TBtree.h:292
Int_t IsAlmostFull() const
Definition: TBtree.h:320
void RemoveItem(Int_t idx)
Definition: TBtree.h:284
Int_t Psize() const
Definition: TBtree.h:312
Int_t NofKeys() const
Return the number of keys.
Definition: TBtree.cxx:1575
TObject ** fItem
Definition: TBtree.h:275
void ShiftLeft(Int_t cnt)
Shift.
Definition: TBtree.cxx:1679
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's array into the ...
Definition: TBtree.cxx:1612
Int_t MaxPsize() const
Definition: TBtree.h:315
void SplitWith(TBtLeafNode *r, Int_t idx)
Split.
Definition: TBtree.cxx:1706
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 BalanceWithLeft(TBtLeafNode *l, Int_t idx)
THIS has more than LEFTSIB; move some items from THIS to LEFTSIB.
Definition: TBtree.cxx:1452
TObject * operator[](Int_t i) const
Definition: TBtree.h:424
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's array into the ...
Definition: TBtree.cxx:1593
Int_t FindRank(const TObject *obj) const
WHAT was not in any inner node; it is either here, or it's not in the tree.
Definition: TBtree.cxx:1487
TBtLeafNode * LastLeafNode()
return the last node.
Definition: TBtree.cxx:1546
void MergeWithRight(TBtLeafNode *r, Int_t idx)
Merge.
Definition: TBtree.cxx:1554
~TBtLeafNode()
Destructor.
Definition: TBtree.cxx:1376
TObject * Found(const TObject *obj, TBtNode **which, Int_t *where)
WHAT was not in any inner node; it is either here, or it's not in the tree.
Definition: TBtree.cxx:1510
Int_t MaxIndex() const
Definition: TBtree.h:314
TBtLeafNode * FirstLeafNode()
Return the first node.
Definition: TBtree.cxx:1501
void Remove(Int_t idx)
Remove an element.
Definition: TBtree.cxx:1656
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
Int_t IsLow() const
Definition: TBtree.h:321
void Append(TObject *obj)
Never called from anywhere where it might fill up THIS does NOT handle nofKeys.
Definition: TBtree.cxx:1442
Int_t IsFull() const
Definition: TBtree.h:319
void SetKey(Int_t idx, TObject *obj)
Definition: TBtree.h:293
Int_t IndexOf(const TObject *obj) const
Returns a number in the range 0 to MaxIndex().
Definition: TBtree.cxx:1533
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
Abstract base class (ABC) of a TBtree node.
Definition: TBtree.h:112
virtual TObject * operator[](Int_t i) const =0
virtual void Add(const TObject *obj, Int_t index)=0
virtual TBtLeafNode * LastLeafNode()=0
virtual Int_t FindRank(const TObject *obj) const =0
virtual ~TBtNode()
Delete a B-tree node.
Definition: TBtree.cxx:564
virtual Int_t NofKeys() const =0
friend class TBtLeafNode
Definition: TBtree.h:116
TBtInnerNode * fParent
Definition: TBtree.h:124
friend class TBtInnerNode
Definition: TBtree.h:115
TBtNode(Int_t isleaf, TBtInnerNode *p, TBtree *t=0)
Create a B-tree node.
Definition: TBtree.cxx:541
virtual void Split()=0
TBtree * fTree
Definition: TBtree.h:125
Int_t fIsLeaf
Definition: TBtree.h:126
Int_t fLast
Definition: TBtree.h:119
virtual TBtree * GetParentTree() const
Definition: TBtree.h:134
virtual void Remove(Int_t index)=0
virtual TBtLeafNode * FirstLeafNode()=0
virtual TObject * Found(const TObject *obj, TBtNode **which, Int_t *where)=0
Iterator of btree.
Definition: TBtree.h:337
const TBtree * fTree
Definition: TBtree.h:340
TBtreeIter()
Definition: TBtree.h:345
void Reset()
Reset the B-tree iterator.
Definition: TBtree.cxx:626
Int_t fCurCursor
Definition: TBtree.h:341
~TBtreeIter()
Definition: TBtree.h:350
Bool_t operator!=(const TIterator &aIter) const
This operator compares two TIterator objects.
Definition: TBtree.cxx:655
TObject * operator*() const
Return current object or nullptr.
Definition: TBtree.cxx:675
TObject * Next()
Get next object from B-tree. Returns 0 when no more objects in tree.
Definition: TBtree.cxx:639
Bool_t fDirection
Definition: TBtree.h:343
const TCollection * GetCollection() const
Definition: TBtree.h:354
TIterator & operator=(const TIterator &rhs)
Overridden assignment operator.
Definition: TBtree.cxx:597
Int_t fCursor
Definition: TBtree.h:342
B-tree class.
Definition: TBtree.h:38
Int_t fOrder
Definition: TBtree.h:47
void Add(TObject *obj)
Add object to B-tree.
Definition: TBtree.cxx:200
Int_t fInnerMaxIndex
Definition: TBtree.h:52
Int_t IdxAdd(const TObject &obj)
Add object and return its index in the tree.
Definition: TBtree.cxx:301
Int_t Rank(const TObject *obj) const
Returns the rank of the object in the tree.
Definition: TBtree.cxx:393
void AddBefore(const TObject *, TObject *obj)
Definition: TBtree.h:85
void Delete(Option_t *option="")
Remove all objects from B-tree AND delete all heap based objects.
Definition: TBtree.cxx:260
virtual ~TBtree()
Delete B-tree.
Definition: TBtree.cxx:189
void Init(Int_t i)
Initialize a B-tree.
Definition: TBtree.cxx:344
void DecrNofKeys()
Definition: TBtree.h:61
TBtNode * fRoot
Definition: TBtree.h:45
Int_t fLeafLowWaterMark
Definition: TBtree.h:51
TObject * Before(const TObject *obj) const
May not use this method since B-tree decides order.
Definition: TBtree.cxx:237
void Clear(Option_t *option="")
Remove all objects from B-tree.
Definition: TBtree.cxx:247
TIterator * MakeIterator(Bool_t dir=kIterForward) const
Returns a B-tree iterator.
Definition: TBtree.cxx:385
Int_t fLeafMaxIndex
Definition: TBtree.h:53
void AddFirst(TObject *obj)
Definition: TBtree.h:81
void RootIsFull()
The root of the tree is full.
Definition: TBtree.cxx:430
TBtree(Int_t ordern=3)
Create a B-tree of certain order (by default 3).
Definition: TBtree.cxx:180
TBtreeIter Iterator_t
Definition: TBtree.h:69
TObject * First() const
Definition: TBtree.h:377
TObject * Remove(TObject *obj)
Remove an object from the tree.
Definition: TBtree.cxx:408
void AddAt(TObject *obj, Int_t)
Definition: TBtree.h:83
TObject * After(const TObject *obj) const
Cannot use this method since B-tree decides order.
Definition: TBtree.cxx:228
void AddLast(TObject *obj)
Definition: TBtree.h:82
Int_t Order()
Definition: TBtree.h:96
void AddAfter(const TObject *, TObject *obj)
Definition: TBtree.h:84
Int_t fOrder2
Definition: TBtree.h:48
TObject * At(Int_t idx) const
Definition: TBtree.h:372
TObject ** GetObjectRef(const TObject *) const
Definition: TBtree.h:77
TObject * FindObject(const char *name) const
Find object using its name (see object's GetName()).
Definition: TBtree.cxx:275
void RootIsEmpty()
If root is empty clean up its space.
Definition: TBtree.cxx:441
Int_t fInnerLowWaterMark
Definition: TBtree.h:50
TObject * operator[](Int_t i) const
Definition: TBtree.h:367
void IncrNofKeys()
Definition: TBtree.h:60
TObject * Last() const
Definition: TBtree.h:382
Collection abstract base class.
Definition: TCollection.h:63
Iterator abstract base class.
Definition: TIterator.h:30
Mother of all ROOT objects.
Definition: TObject.h:37
Sequenceable collection abstract base class.
const Int_t n
Definition: legend1.C:16
Definition: tree.py:1
const char * cnt
Definition: TXMLSetup.cxx:74
auto * l
Definition: textangle.C:4