Logo ROOT  
Reference Guide
 
Loading...
Searching...
No Matches
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="") override;
74 void Delete(Option_t *option="") override;
75 TObject *FindObject(const char *name) const override;
76 TObject *FindObject(const TObject *obj) const override;
77 TObject **GetObjectRef(const TObject *) const override { return nullptr; }
78 TIterator *MakeIterator(Bool_t dir = kIterForward) const override;
79
80 void Add(TObject *obj) override;
81 void AddFirst(TObject *obj) override { Add(obj); }
82 void AddLast(TObject *obj) override { Add(obj); }
83 void AddAt(TObject *obj, Int_t) override { Add(obj); }
84 void AddAfter(const TObject *, TObject *obj) override { Add(obj); }
85 void AddBefore(const TObject *, TObject *obj) override { Add(obj); }
86 TObject *Remove(TObject *obj) override;
87
88 TObject *At(Int_t idx) const override;
89 TObject *Before(const TObject *obj) const override;
90 TObject *After(const TObject *obj) const override;
91 TObject *First() const override;
92 TObject *Last() const override;
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
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 = nullptr);
130 virtual ~TBtNode();
131
132 virtual void Add(const TObject *obj, Int_t index) = 0;
133 virtual TBtree *GetParentTree() const {return fTree;}
134 virtual void Remove(Int_t index) = 0;
135
136 virtual TObject *operator[](Int_t i) const = 0;
137 virtual TObject *Found(const TObject *obj, TBtNode **which, Int_t *where) = 0;
138
139 virtual Int_t FindRank(const TObject *obj) const = 0;
140 virtual Int_t NofKeys() const = 0; // # keys in or below this node
141
143 virtual TBtLeafNode *LastLeafNode() = 0;
144
145 virtual void Split() = 0;
146 // virtual void PrintOn(std::ostream &os) const = 0;
147 // friend std::ostream &operator<<(std::ostream &os, const TBtNode &node);
148};
149
150
151//////////////////////////////////////////////////////////////////////////
152// //
153// TBtItem //
154// //
155// Item stored in inner nodes of a TBtree. //
156// //
157//////////////////////////////////////////////////////////////////////////
158
159class TBtItem {
160
161friend class TBtInnerNode;
162
163private:
164 Int_t fNofKeysInTree; // number of keys in TBtree
165 TObject *fKey; // key
166 TBtNode *fTree; //! sub-tree
167
168public:
169 TBtItem();
170 TBtItem(TBtNode *n, TObject *o);
171 TBtItem(TObject *o, TBtNode *n);
172 ~TBtItem();
173};
174
175
176//////////////////////////////////////////////////////////////////////////
177// //
178// TBtInnerNode //
179// //
180// Inner node of a TBtree. //
181// //
182//////////////////////////////////////////////////////////////////////////
183
184class TBtInnerNode : public TBtNode {
185
186private:
187 TBtItem *fItem; // actually fItem[MaxIndex()+1] is desired
188
189public:
190 TBtInnerNode(TBtInnerNode *parent, TBtree *t = nullptr);
191 TBtInnerNode(TBtInnerNode *parent, TBtree *tree, TBtNode *oldroot);
193
194 void Add(const TObject *obj, Int_t idx) override;
195 void Add(TBtItem &i, Int_t idx);
196 void Add(Int_t at, TObject *obj, TBtNode *n);
197 void AddElt(TBtItem &itm, Int_t at);
198 void AddElt(Int_t at, TObject *obj, TBtNode *n);
199 void Remove(Int_t idx) override;
200 void RemoveItem(Int_t idx);
201
202 TObject *operator[](Int_t i) const override;
203 TObject *Found(const TObject *obj, TBtNode **which, Int_t *where) override;
204
205 Int_t NofKeys(Int_t idx) const;
206 Int_t NofKeys() const override;
207 void SetTree(Int_t i, TBtNode *node) { fItem[i].fTree = node; node->fParent = this; }
208 void SetKey(Int_t i, TObject *obj) { fItem[i].fKey = obj; }
209 void SetItem(Int_t i, TBtItem &itm) { fItem[i] = itm; itm.fTree->fParent = this; }
210 void SetItem(Int_t i, TObject *obj, TBtNode *node) { SetTree(i, node); SetKey(i, obj); }
211 Int_t GetNofKeys(Int_t i) const;
212 void SetNofKeys(Int_t i, Int_t r);
215 Int_t FindRank(const TObject *obj) const override;
216 Int_t FindRankUp(const TBtNode *n) const;
217 TBtNode *GetTree(Int_t i) const { return fItem[i].fTree; }
218 TObject *GetKey(Int_t i) const { return fItem[i].fKey; }
219 TBtItem &GetItem(Int_t i) const { return fItem[i]; }
220
221 Int_t IndexOf(const TBtNode *n) const;
222 void IncrNofKeys(TBtNode *np);
223 void DecrNofKeys(TBtNode *np);
224
225 TBtLeafNode *FirstLeafNode() override;
226 TBtLeafNode *LastLeafNode() override;
227
228 void InformParent();
229
230 void Split() override;
231 void SplitWith(TBtInnerNode *r, Int_t idx);
235 void BalanceWith(TBtInnerNode *n, int idx);
236 void PushLeft(Int_t cnt, TBtInnerNode *leftsib, Int_t parentIdx);
237 void PushRight(Int_t cnt, TBtInnerNode *rightsib, Int_t parentIdx);
238 void AppendFrom(TBtInnerNode *src, Int_t start, Int_t stop);
239 void Append(TObject *obj, TBtNode *n);
240 void Append(TBtItem &itm);
241 void ShiftLeft(Int_t cnt);
242
243 Int_t Psize() const { return fLast; }
244 Int_t Vsize() const;
245 Int_t MaxIndex() const { return fTree ? fTree->fInnerMaxIndex : 0; }
246 Int_t MaxPsize() const { return fTree ? fTree->fInnerMaxIndex : 0; }
247
248 // void PrintOn(std::ostream &os) const;
249
250 Int_t IsFull() const { return fLast == MaxIndex(); }
251 void IsFull(TBtNode *n);
252 Int_t IsAlmostFull() const { return fLast >= MaxIndex() - 1; }
253 Int_t IsLow() const { return fLast < fTree->fInnerLowWaterMark; }
254 void IsLow(TBtNode *n);
255};
256
257
258//////////////////////////////////////////////////////////////////////////
259// //
260// TBtLeafNode //
261// //
262// Leaf node of a TBtree. //
263// //
264//////////////////////////////////////////////////////////////////////////
265
266class TBtLeafNode : public TBtNode {
267
268friend class TBtInnerNode;
269
270private:
271 TObject **fItem; // actually TObject *fItem[MaxIndex()+1] is desired
272
273public:
274 TBtLeafNode(TBtInnerNode *p, const TObject *obj = nullptr, TBtree *t = nullptr);
275 ~TBtLeafNode();
276
277 void Add(const TObject *obj, Int_t idx) override;
278 void Remove(Int_t idx) override;
279 void RemoveItem(Int_t idx) { Remove(idx); }
280
281 TObject *operator[](Int_t i) const override;
282 TObject *Found(const TObject *obj, TBtNode **which, Int_t *where) override;
283
284 Int_t NofKeys(Int_t i) const;
285 Int_t NofKeys() const override;
286 Int_t FindRank(const TObject *obj) const override;
287 TObject *GetKey(Int_t idx ) { return fItem[idx]; }
288 void SetKey(Int_t idx, TObject *obj) { fItem[idx] = obj; }
289
290 Int_t IndexOf(const TObject *obj) const;
291
292 TBtLeafNode *FirstLeafNode() override;
293 TBtLeafNode *LastLeafNode() override;
294
295 void Split() override;
296 void SplitWith(TBtLeafNode *r, Int_t idx);
297 void MergeWithRight(TBtLeafNode *r, Int_t idx);
300 void BalanceWith(TBtLeafNode *n, Int_t idx);
301 void PushLeft(Int_t cnt, TBtLeafNode *l, Int_t parentIndex);
302 void PushRight(Int_t cnt, TBtLeafNode *r, Int_t parentIndex);
303 void AppendFrom(TBtLeafNode *src, Int_t start, Int_t stop);
304 void Append(TObject *obj);
305 void ShiftLeft(Int_t cnt);
306
307 Int_t Psize() const { return fLast + 1; }
308 Int_t Vsize() const;
309 Int_t MaxIndex() const { return fTree ? fTree->fLeafMaxIndex : 0; }
310 Int_t MaxPsize() const { return fTree ? fTree->fLeafMaxIndex + 1 : 0; }
311
312 // void PrintOn(std::ostream &os) const;
313
314 Int_t IsFull() const { return fLast == MaxIndex(); }
315 Int_t IsAlmostFull() const { return fLast >= MaxIndex() - 1; }
316 Int_t IsLow() const { return fLast < fTree->fLeafLowWaterMark; }
317};
318
319
320//////////////////////////////////////////////////////////////////////////
321// //
322// TBtreeIter //
323// //
324// Iterator of btree. //
325// //
326//////////////////////////////////////////////////////////////////////////
327
328class TBtreeIter : public TIterator {
329
330private:
331 const TBtree *fTree; //btree being iterated
332 Int_t fCurCursor; //current position in btree
333 Int_t fCursor; //next position in btree
334 Bool_t fDirection; //iteration direction
335
337
338public:
339 using iterator_category = std::bidirectional_iterator_tag;
341 using difference_type = std::ptrdiff_t;
342 using pointer = TObject **;
343 using const_pointer = const TObject **;
344 using reference = const TObject *&;
345
346 TBtreeIter(const TBtree *t, Bool_t dir = kIterForward);
347 TBtreeIter(const TBtreeIter &iter);
349 TIterator &operator=(const TIterator &rhs) override;
350 TBtreeIter &operator=(const TBtreeIter &rhs);
351
352 const TCollection *GetCollection() const override { return fTree; }
353 TObject *Next() override;
354 void Reset() override;
355 Bool_t operator!=(const TIterator &aIter) const override;
356 Bool_t operator!=(const TBtreeIter &aIter) const;
357 TObject *operator*() const override;
358
359 ClassDefOverride(TBtreeIter,0) //B-tree iterator
360};
361
362//----- TBtree inlines ---------------------------------------------------------
363
365{
366 return (*fRoot)[i];
367}
368
369inline TObject *TBtree::At(Int_t i) const
370{
371 return (*fRoot)[i];
372}
373
374inline TObject *TBtree::First() const
375{
376 return (*fRoot)[0];
377}
378
379inline TObject *TBtree::Last() const
380{
381 return (*fRoot)[fSize-1];
382}
383
384//----- TBtInnerNode inlines ---------------------------------------------------
385
387{
388 R__ASSERT(i >= 0 && i <= fLast);
389 return fItem[i].fNofKeysInTree;
390}
391
393{
394 return GetNofKeys(idx);
395}
396
398{
400}
401
403{
404 return (fItem[i].fNofKeysInTree += n);
405}
406
408{
409 return (fItem[i].fNofKeysInTree -= n);
410}
411
413{
414 R__ASSERT(fParent != nullptr && fParent->GetTree(0) != (const TBtNode *)this);
415 return Psize()+1;
416}
417
418
419//----- TBtLeafNode inlines ----------------------------------------------------
420
422{
423 R__ASSERT(i >= 0 && i <= fLast);
424 return fItem[i];
425}
426
428{
429 R__ASSERT(fParent != nullptr && fParent->GetTree(0) != (const TBtNode *)this);
430 return Psize()+1;
431}
432
433//inline std::ostream &operator<<(std::ostream& outputStream, const TBtNode &aNode)
434//{
435// aNode.PrintOn(outputStream);
436// return outputStream;
437//}
438
439#endif
bool Bool_t
Definition RtypesCore.h:63
int Int_t
Definition RtypesCore.h:45
const char Option_t
Definition RtypesCore.h:66
#define ClassDefOverride(name, id)
Definition Rtypes.h:341
const Bool_t kIterForward
Definition TCollection.h:42
#define R__ASSERT(e)
Definition TError.h:118
winID h TVirtualViewer3D TVirtualGLPainter p
Option_t Option_t option
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void char Point_t Rectangle_t WindowAttributes_t Float_t Float_t Float_t Int_t Int_t UInt_t UInt_t Rectangle_t Int_t Int_t Window_t TString Int_t GCValues_t GetPrimarySelectionOwner GetDisplay GetScreen GetColormap GetNativeEvent const char const char dpyName wid window const char font_name cursor keysym reg const char only_if_exist regb h Point_t np
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void char Point_t Rectangle_t WindowAttributes_t Float_t r
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void char Point_t Rectangle_t WindowAttributes_t index
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void char Point_t Rectangle_t src
char name[80]
Definition TGX11.cxx:110
Inner node of a TBtree.
Definition TBtree.h:184
Int_t DecNofKeys(Int_t i, Int_t n=1)
Definition TBtree.h:407
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
Int_t NofKeys() const override
Number of key.
Definition TBtree.cxx:1136
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:402
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
Int_t IsFull() const
Definition TBtree.h:250
TBtItem & GetItem(Int_t i) const
Definition TBtree.h:219
void SetKey(Int_t i, TObject *obj)
Definition TBtree.h:208
Int_t GetNofKeys(Int_t i) const
Definition TBtree.h:386
void AddElt(TBtItem &itm, Int_t at)
Add one element.
Definition TBtree.cxx:735
Int_t MaxIndex() const
Definition TBtree.h:245
Int_t Vsize() const
Definition TBtree.h:412
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
Int_t FindRank(const TObject *obj) const override
Recursively look for WHAT starting in the current node.
Definition TBtree.cxx:863
void Add(const TObject *obj, Int_t idx) override
This is called only from TBtree::Add().
Definition TBtree.cxx:725
void MergeWithRight(TBtInnerNode *r, Int_t idx)
Merge the 2 part of the tree.
Definition TBtree.cxx:1121
Int_t IsAlmostFull() const
Definition TBtree.h:252
void SetItem(Int_t i, TBtItem &itm)
Definition TBtree.h:209
void SetNofKeys(Int_t i, Int_t r)
Definition TBtree.h:397
Int_t MaxPsize() const
Definition TBtree.h:246
void SetTree(Int_t i, TBtNode *node)
Definition TBtree.h:207
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:218
void SetItem(Int_t i, TObject *obj, TBtNode *node)
Definition TBtree.h:210
void DecrNofKeys(TBtNode *np)
THAT is a child of THIS that has just shrunk by 1.
Definition TBtree.cxx:850
void Remove(Int_t idx) override
Remove an element.
Definition TBtree.cxx:1233
~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 Split() override
This function is called only when THIS is the only descendent of the root node, and THIS needs to be ...
Definition TBtree.cxx:1277
void PushRight(Int_t cnt, TBtInnerNode *rightsib, Int_t parentIdx)
The operation is three steps:
Definition TBtree.cxx:1189
TObject * operator[](Int_t i) const override
return an element.
Definition TBtree.cxx:1147
TBtNode * GetTree(Int_t i) const
Definition TBtree.h:217
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
void RemoveItem(Int_t idx)
Remove an item.
Definition TBtree.cxx:1244
TBtItem * fItem
Definition TBtree.h:187
TBtLeafNode * FirstLeafNode() override
Return the first leaf node.
Definition TBtree.cxx:902
TObject * Found(const TObject *obj, TBtNode **which, Int_t *where) override
Recursively look for WHAT starting in the current node.
Definition TBtree.cxx:910
Int_t IsLow() const
Definition TBtree.h:253
TBtLeafNode * LastLeafNode() override
Return the last leaf node.
Definition TBtree.cxx:1113
Int_t Psize() const
Definition TBtree.h:243
Item stored in inner nodes of a TBtree.
Definition TBtree.h:159
TBtItem()
sub-tree
Definition TBtree.cxx:496
~TBtItem()
Delete a tree item.
Definition TBtree.cxx:530
TObject * fKey
Definition TBtree.h:165
Int_t fNofKeysInTree
Definition TBtree.h:164
TBtNode * fTree
Definition TBtree.h:166
Leaf node of a TBtree.
Definition TBtree.h:266
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
TObject * operator[](Int_t i) const override
Definition TBtree.h:421
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:427
TObject * GetKey(Int_t idx)
Definition TBtree.h:287
void Split() override
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 IsAlmostFull() const
Definition TBtree.h:315
void RemoveItem(Int_t idx)
Definition TBtree.h:279
Int_t Psize() const
Definition TBtree.h:307
TObject ** fItem
Definition TBtree.h:271
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:310
void SplitWith(TBtLeafNode *r, Int_t idx)
Split.
Definition TBtree.cxx:1706
TObject * Found(const TObject *obj, TBtNode **which, Int_t *where) override
WHAT was not in any inner node; it is either here, or it's not in the tree.
Definition TBtree.cxx:1510
TBtLeafNode * FirstLeafNode() override
Return the first node.
Definition TBtree.cxx:1501
void Remove(Int_t idx) override
Remove an element.
Definition TBtree.cxx:1656
void BalanceWithLeft(TBtLeafNode *l, Int_t idx)
THIS has more than LEFTSIB; move some items from THIS to LEFTSIB.
Definition TBtree.cxx:1452
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
void Add(const TObject *obj, Int_t idx) override
Add the object OBJ to the leaf node, inserting it at location INDEX in the fItem array.
Definition TBtree.cxx:1385
void MergeWithRight(TBtLeafNode *r, Int_t idx)
Merge.
Definition TBtree.cxx:1554
~TBtLeafNode()
Destructor.
Definition TBtree.cxx:1376
Int_t NofKeys() const override
Return the number of keys.
Definition TBtree.cxx:1575
Int_t MaxIndex() const
Definition TBtree.h:309
TBtLeafNode * LastLeafNode() override
return the last node.
Definition TBtree.cxx:1546
Int_t IsLow() const
Definition TBtree.h:316
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:314
Int_t FindRank(const TObject *obj) const override
WHAT was not in any inner node; it is either here, or it's not in the tree.
Definition TBtree.cxx:1487
void SetKey(Int_t idx, TObject *obj)
Definition TBtree.h:288
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
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:133
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:328
std::bidirectional_iterator_tag iterator_category
Definition TBtree.h:339
const TBtree * fTree
Definition TBtree.h:331
const TCollection * GetCollection() const override
Definition TBtree.h:352
TBtreeIter()
Definition TBtree.h:336
Int_t fCurCursor
Definition TBtree.h:332
~TBtreeIter()
Definition TBtree.h:348
Bool_t operator!=(const TIterator &aIter) const override
This operator compares two TIterator objects.
Definition TBtree.cxx:655
TIterator & operator=(const TIterator &rhs) override
Overridden assignment operator.
Definition TBtree.cxx:597
Bool_t fDirection
Definition TBtree.h:334
std::ptrdiff_t difference_type
Definition TBtree.h:341
TObject * Next() override
Get next object from B-tree. Returns 0 when no more objects in tree.
Definition TBtree.cxx:639
void Reset() override
Reset the B-tree iterator.
Definition TBtree.cxx:626
Int_t fCursor
Definition TBtree.h:333
TObject * operator*() const override
Return current object or nullptr.
Definition TBtree.cxx:675
B-tree class.
Definition TBtree.h:38
Int_t fOrder
Definition TBtree.h:47
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 Delete(Option_t *option="") override
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
Int_t fLeafMaxIndex
Definition TBtree.h:53
TObject * Before(const TObject *obj) const override
May not use this method since B-tree decides order.
Definition TBtree.cxx:237
TObject * Remove(TObject *obj) override
Remove an object from the tree.
Definition TBtree.cxx:408
void RootIsFull()
The root of the tree is full.
Definition TBtree.cxx:430
TObject * First() const override
Definition TBtree.h:374
TBtreeIter Iterator_t
Definition TBtree.h:69
void AddAt(TObject *obj, Int_t) override
Definition TBtree.h:83
void Add(TObject *obj) override
Add object to B-tree.
Definition TBtree.cxx:200
void Clear(Option_t *option="") override
Remove all objects from B-tree.
Definition TBtree.cxx:247
TObject * Last() const override
Definition TBtree.h:379
Int_t Order()
Definition TBtree.h:96
TObject * After(const TObject *obj) const override
Cannot use this method since B-tree decides order.
Definition TBtree.cxx:228
void AddAfter(const TObject *, TObject *obj) override
Definition TBtree.h:84
void AddLast(TObject *obj) override
Definition TBtree.h:82
Int_t fOrder2
Definition TBtree.h:48
TObject ** GetObjectRef(const TObject *) const override
Definition TBtree.h:77
TIterator * MakeIterator(Bool_t dir=kIterForward) const override
Returns a B-tree iterator.
Definition TBtree.cxx:385
void RootIsEmpty()
If root is empty clean up its space.
Definition TBtree.cxx:441
void AddFirst(TObject *obj) override
Definition TBtree.h:81
void AddBefore(const TObject *, TObject *obj) override
Definition TBtree.h:85
Int_t fInnerLowWaterMark
Definition TBtree.h:50
TObject * At(Int_t idx) const override
Definition TBtree.h:369
TObject * FindObject(const char *name) const override
Find object using its name (see object's GetName()).
Definition TBtree.cxx:275
TObject * operator[](Int_t i) const
Definition TBtree.h:364
void IncrNofKeys()
Definition TBtree.h:60
Collection abstract base class.
Definition TCollection.h:65
Iterator abstract base class.
Definition TIterator.h:30
Mother of all ROOT objects.
Definition TObject.h:41
Sequenceable collection abstract base class.
const Int_t n
Definition legend1.C:16
TLine l
Definition textangle.C:4