Logo ROOT  
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="") 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#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 = nullptr);
193 TBtInnerNode(TBtInnerNode *parent, TBtree *tree, TBtNode *oldroot);
195
196#ifndef __CINT__
197 void Add(const TObject *obj, Int_t idx) override;
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) override;
203 void RemoveItem(Int_t idx);
204
205 TObject *operator[](Int_t i) const override;
206 TObject *Found(const TObject *obj, TBtNode **which, Int_t *where) override;
207
208 Int_t NofKeys(Int_t idx) const;
209 Int_t NofKeys() const override;
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 override;
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
228 TBtLeafNode *FirstLeafNode() override;
229 TBtLeafNode *LastLeafNode() override;
230
231 void InformParent();
232
233 void Split() override;
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 ? fTree->fInnerMaxIndex : 0; }
249 Int_t MaxPsize() const { return fTree ? fTree->fInnerMaxIndex : 0; }
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 = nullptr, TBtree *t = nullptr);
279 ~TBtLeafNode();
280
281#ifndef __CINT__
282 void Add(const TObject *obj, Int_t idx) override;
283 void Remove(Int_t idx) override;
284 void RemoveItem(Int_t idx) { Remove(idx); }
285
286 TObject *operator[](Int_t i) const override;
287 TObject *Found(const TObject *obj, TBtNode **which, Int_t *where) override;
288
289 Int_t NofKeys(Int_t i) const;
290 Int_t NofKeys() const override;
291 Int_t FindRank(const TObject *obj) const override;
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
297 TBtLeafNode *FirstLeafNode() override;
298 TBtLeafNode *LastLeafNode() override;
299
300 void Split() override;
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 ? fTree->fLeafMaxIndex : 0; }
315 Int_t MaxPsize() const { return fTree ? fTree->fLeafMaxIndex + 1 : 0; }
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
336private:
337 const TBtree *fTree; //btree being iterated
338 Int_t fCurCursor; //current position in btree
339 Int_t fCursor; //next position in btree
340 Bool_t fDirection; //iteration direction
341
343
344public:
345 using iterator_category = std::bidirectional_iterator_tag;
347 using difference_type = std::ptrdiff_t;
348 using pointer = TObject **;
349 using const_pointer = const TObject **;
350 using reference = const TObject *&;
351
352 TBtreeIter(const TBtree *t, Bool_t dir = kIterForward);
353 TBtreeIter(const TBtreeIter &iter);
355 TIterator &operator=(const TIterator &rhs) override;
356 TBtreeIter &operator=(const TBtreeIter &rhs);
357
358 const TCollection *GetCollection() const override { return fTree; }
359 TObject *Next() override;
360 void Reset() override;
361 Bool_t operator!=(const TIterator &aIter) const override;
362 Bool_t operator!=(const TBtreeIter &aIter) const;
363 TObject *operator*() const override;
364
365 ClassDefOverride(TBtreeIter,0) //B-tree iterator
366};
367
368//----- TBtree inlines ---------------------------------------------------------
369
371{
372 return (*fRoot)[i];
373}
374
375inline TObject *TBtree::At(Int_t i) const
376{
377 return (*fRoot)[i];
378}
379
380inline TObject *TBtree::First() const
381{
382 return (*fRoot)[0];
383}
384
385inline TObject *TBtree::Last() const
386{
387 return (*fRoot)[fSize-1];
388}
389
390//----- TBtInnerNode inlines ---------------------------------------------------
391
393{
394 R__ASSERT(i >= 0 && i <= fLast);
395 return fItem[i].fNofKeysInTree;
396}
397
399{
400 return GetNofKeys(idx);
401}
402
404{
406}
407
409{
410 return (fItem[i].fNofKeysInTree += n);
411}
412
414{
415 return (fItem[i].fNofKeysInTree -= n);
416}
417
419{
420 R__ASSERT(fParent != 0 && fParent->GetTree(0) != (const TBtNode *)this);
421 return Psize()+1;
422}
423
424
425//----- TBtLeafNode inlines ----------------------------------------------------
426
428{
429 R__ASSERT(i >= 0 && i <= fLast);
430 return fItem[i];
431}
432
434{
435 R__ASSERT(fParent != 0 && fParent->GetTree(0) != (const TBtNode *)this);
436 return Psize()+1;
437}
438
439//inline std::ostream &operator<<(std::ostream& outputStream, const TBtNode &aNode)
440//{
441// aNode.PrintOn(outputStream);
442// return outputStream;
443//}
444
445#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:339
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:186
Int_t DecNofKeys(Int_t i, Int_t n=1)
Definition: TBtree.h:413
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:408
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: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:392
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:418
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:255
void SetItem(Int_t i, TBtItem &itm)
Definition: TBtree.h:212
void SetNofKeys(Int_t i, Int_t r)
Definition: TBtree.h:403
Int_t MaxPsize() const
Definition: TBtree.h:249
void SetTree(Int_t i, TBtNode *node)
Definition: TBtree.h:210
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 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: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
void RemoveItem(Int_t idx)
Remove an item.
Definition: TBtree.cxx:1244
TBtItem * fItem
Definition: TBtree.h:189
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:256
TBtLeafNode * LastLeafNode() override
Return the last leaf node.
Definition: TBtree.cxx:1113
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
TObject * operator[](Int_t i) const override
Definition: TBtree.h:427
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:433
TObject * GetKey(Int_t idx)
Definition: TBtree.h:292
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:320
void RemoveItem(Int_t idx)
Definition: TBtree.h:284
Int_t Psize() const
Definition: TBtree.h:312
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
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:314
TBtLeafNode * LastLeafNode() override
return the last node.
Definition: TBtree.cxx:1546
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
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: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
TBtNode(Int_t isleaf, TBtInnerNode *p, TBtree *t=nullptr)
Create a B-tree node.
Definition: TBtree.cxx:541
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: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:334
std::bidirectional_iterator_tag iterator_category
Definition: TBtree.h:345
const TBtree * fTree
Definition: TBtree.h:337
const TCollection * GetCollection() const override
Definition: TBtree.h:358
TBtreeIter()
Definition: TBtree.h:342
Int_t fCurCursor
Definition: TBtree.h:338
~TBtreeIter()
Definition: TBtree.h:354
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:340
std::ptrdiff_t difference_type
Definition: TBtree.h:347
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:339
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:380
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
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:385
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:375
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:370
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:37
Sequenceable collection abstract base class.
const Int_t n
Definition: legend1.C:16
Definition: tree.py:1
const char * cnt
Definition: TXMLSetup.cxx:75
TLine l
Definition: textangle.C:4