Logo ROOT   6.30.04
Reference Guide
 All Namespaces Files Pages
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:
69  typedef TBtreeIter Iterator_t;
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; }
78  TIterator *MakeIterator(Bool_t dir = kIterForward) const;
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 
228  TBtLeafNode *FirstLeafNode();
229  TBtLeafNode *LastLeafNode();
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 
297  TBtLeafNode *FirstLeafNode();
298  TBtLeafNode *LastLeafNode();
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 
345  TBtreeIter() : fTree(0), fCurCursor(0), fCursor(0), fDirection(kIterForward) { }
346 
347 public:
348  TBtreeIter(const TBtree *t, Bool_t dir = kIterForward);
349  TBtreeIter(const TBtreeIter &iter);
350  ~TBtreeIter() { }
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 
367 inline TObject *TBtree::operator[](Int_t i) const
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 
389 inline Int_t TBtInnerNode::GetNofKeys(Int_t i) const
390 {
391  R__ASSERT(i >= 0 && i <= fLast);
392  return fItem[i].fNofKeysInTree;
393 }
394 
395 inline Int_t TBtInnerNode::NofKeys(Int_t idx) const
396 {
397  return GetNofKeys(idx);
398 }
399 
400 inline void TBtInnerNode::SetNofKeys(Int_t i, Int_t r)
401 {
402  fItem[i].fNofKeysInTree = r;
403 }
404 
405 inline Int_t TBtInnerNode::IncNofKeys(Int_t i, Int_t n)
406 {
407  return (fItem[i].fNofKeysInTree += n);
408 }
409 
410 inline Int_t TBtInnerNode::DecNofKeys(Int_t i, Int_t n)
411 {
412  return (fItem[i].fNofKeysInTree -= n);
413 }
414 
415 inline Int_t TBtInnerNode::Vsize() const
416 {
417  R__ASSERT(fParent != 0 && fParent->GetTree(0) != (const TBtNode *)this);
418  return Psize()+1;
419 }
420 
421 
422 //----- TBtLeafNode inlines ----------------------------------------------------
423 
424 inline TObject *TBtLeafNode::operator[](Int_t i) const
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