Logo ROOT   6.10/09
Reference Guide
TBtree.cxx
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 /** \class TBtree
13 \ingroup Containers
14 B-tree class. TBtree inherits from the TSeqCollection ABC.
15 
16 ## B-tree Implementation notes
17 
18 This implements B-trees with several refinements. Most of them can be found
19 in Knuth Vol 3, but some were developed to adapt to restrictions imposed
20 by C++. First, a restatement of Knuth's properties that a B-tree must
21 satisfy, assuming we make the enhancement he suggests in the paragraph
22 at the bottom of page 476. Instead of storing null pointers to non-existent
23 nodes (which Knuth calls the leaves) we utilize the space to store keys.
24 Therefore, what Knuth calls level (l-1) is the bottom of our tree, and
25 we call the nodes at this level LeafNodes. Other nodes are called InnerNodes.
26 The other enhancement we have adopted is in the paragraph at the bottom of
27 page 477: overflow control.
28 
29 The following are modifications of Knuth's properties on page 478:
30 
31  1. Every InnerNode has at most Order keys, and at most Order+1 sub-trees.
32  2. Every LeafNode has at most 2*(Order+1) keys.
33  3. An InnerNode with k keys has k+1 sub-trees.
34  4. Every InnerNode that is not the root has at least InnerLowWaterMark keys.
35  5. Every LeafNode that is not the root has at least LeafLowWaterMark keys.
36  6. If the root is a LeafNode, it has at least one key.
37  7. If the root is an InnerNode, it has at least one key and two sub-trees.
38  8. All LeafNodes are the same distance from the root as all the other
39  LeafNodes.
40  9. For InnerNode n with key n[i].key, then sub-tree n[i-1].tree contains
41  all keys < n[i].key, and sub-tree n[i].tree contains all keys
42  >= n[i].key.
43  10. Order is at least 3.
44 
45 The values of InnerLowWaterMark and LeafLowWaterMark may actually be set
46 by the user when the tree is initialized, but currently they are set
47 automatically to:
48 ~~~ {.cpp}
49  InnerLowWaterMark = ceiling(Order/2)
50  LeafLowWaterMark = Order - 1
51 ~~~
52 If the tree is only filled, then all the nodes will be at least 2/3 full.
53 They will almost all be exactly 2/3 full if the elements are added to the
54 tree in order (either increasing or decreasing). [Knuth says McCreight's
55 experiments showed almost 100% memory utilization. I don't see how that
56 can be given the algorithms that Knuth gives. McCreight must have used
57 a different scheme for balancing. [No, he used a different scheme for
58 splitting: he did a two-way split instead of the three way split as we do
59 here. Which means that McCreight does better on insertion of ordered data,
60 but we should do better on insertion of random data.]]
61 
62 It must also be noted that B-trees were designed for DISK access algorithms,
63 not necessarily in-memory sorting, as we intend it to be used here. However,
64 if the order is kept small (< 6?) any inefficiency is negligible for
65 in-memory sorting. Knuth points out that balanced trees are actually
66 preferable for memory sorting. I'm not sure that I believe this, but
67 it's interesting. Also, deleting elements from balanced binary trees, being
68 beyond the scope of Knuth's book (p. 465), is beyond my scope. B-trees
69 are good enough.
70 
71 A B-tree is declared to be of a certain ORDER (3 by default). This number
72 determines the number of keys contained in any interior node of the tree.
73 Each interior node will contain ORDER keys, and therefore ORDER+1 pointers
74 to sub-trees. The keys are numbered and indexed 1 to ORDER while the
75 pointers are numbered and indexed 0 to ORDER. The 0th ptr points to the
76 sub-tree of all elements that are less than key[1]. Ptr[1] points to the
77 sub-tree that contains all the elements greater than key[1] and less than
78 key[2]. etc. The array of pointers and keys is allocated as ORDER+1
79 pairs of keys and nodes, meaning that one key field (key[0]) is not used
80 and therefore wasted. Given that the number of interior nodes is
81 small, that this waste allows fewer cases of special code, and that it
82 is useful in certain of the methods, it was felt to be a worthwhile waste.
83 
84 The size of the exterior nodes (leaf nodes) does not need to be related to
85 the size of the interior nodes at all. Since leaf nodes contain only
86 keys, they may be as large or small as we like independent of the size
87 of the interior nodes. For no particular reason other than it seems like
88 a good idea, we will allocate 2*(ORDER+1) keys in each leaf node, and they
89 will be numbered and indexed from 0 to 2*ORDER+1. It does have the advantage
90 of keeping the size of the leaf and interior arrays the same, so that if we
91 find allocation and de-allocation of these arrays expensive, we can modify
92 their allocation to use a garbage ring, or something.
93 
94 Both of these numbers will be run-time constants associated with each tree
95 (each tree at run-time can be of a different order). The variable "order"
96 is the order of the tree, and the inclusive upper limit on the indices of
97 the keys in the interior nodes. The variable "order2" is the inclusive
98 upper limit on the indices of the leaf nodes, and is designed
99 ~~~ {.cpp}
100  (1) to keep the sizes of the two kinds of nodes the same;
101  (2) to keep the expressions involving the arrays of keys looking
102  somewhat the same: lower limit upper limit
103  for inner nodes: 1 order
104  for leaf nodes: 0 order2
105  Remember that index 0 of the inner nodes is special.
106 ~~~
107 Currently, order2 = 2*(order+1).
108 ~~~ {.cpp}
109  Picture: (also see Knuth Vol 3 pg 478)
110 
111  +--+--+--+--+--+--...
112  | | | | | |
113  parent--->| | | |
114  | | | |
115  +*-+*-+*-+--+--+--...
116  | | |
117  +----+ | +-----+
118  | +-----+ |
119  V | V
120  +----------+ | +----------+
121  | | | | |
122  this->| | | | |<--sib
123  +----------+ | +----------+
124  V
125  data
126 ~~~
127 It is conceptually VERY convenient to think of the data as being the
128 very first element of the sib node. Any primitive that tells sib to
129 perform some action on n nodes should include this 'hidden' element.
130 For InnerNodes, the hidden element has (physical) index 0 in the array,
131 and in LeafNodes, the hidden element has (virtual) index -1 in the array.
132 Therefore, there are two 'size' primitives for nodes:
133 ~~~ {.cpp}
134 Psize - the physical size: how many elements are contained in the
135  array in the node.
136 Vsize - the 'virtual' size; if the node is pointed to by
137  element 0 of the parent node, then Vsize == Psize;
138  otherwise the element in the parent item that points to this
139  node 'belongs' to this node, and Vsize == Psize+1;
140 ~~~
141 Parent nodes are always InnerNodes.
142 
143 These are the primitive operations on Nodes:
144 ~~~ {.cpp}
145 Append(elt) - adds an element to the end of the array of elements in a
146  node. It must never be called where appending the element
147  would fill the node.
148 Split() - divide a node in two, and create two new nodes.
149 SplitWith(sib) - create a third node between this node and the sib node,
150  divvying up the elements of their arrays.
151 PushLeft(n) - move n elements into the left sibling
152 PushRight(n) - move n elements into the right sibling
153 BalanceWithRight() - even up the number of elements in the two nodes.
154 BalanceWithLeft() - ditto
155 ~~~
156 To allow this implementation of btrees to also be an implementation of
157 sorted arrays/lists, the overhead is included to allow O(log n) access
158 of elements by their rank (`give me the 5th largest element').
159 Therefore, each Item keeps track of the number of keys in and below it
160 in the tree (remember, each item's tree is all keys to the RIGHT of the
161 item's own key).
162 ~~~ {.cpp}
163 [ [ < 0 1 2 3 > 4 < 5 6 7 > 8 < 9 10 11 12 > ] 13 [ < 14 15 16 > 17 < 18 19 20 > ] ]
164  4 1 1 1 1 4 1 1 1 5 1 1 1 1 7 3 1 1 1 4 1 1 1
165 ~~~
166 */
167 
168 #include "TBtree.h"
169 #include "TBuffer.h"
170 #include "TObject.h"
171 
172 #include <stdlib.h>
173 
174 
176 
177 ////////////////////////////////////////////////////////////////////////////////
178 /// Create a B-tree of certain order (by default 3).
179 
180 TBtree::TBtree(int order)
181 {
182  Init(order);
183 }
184 
185 ////////////////////////////////////////////////////////////////////////////////
186 /// Delete B-tree. Objects are not deleted unless the TBtree is the
187 /// owner (set via SetOwner()).
188 
190 {
191  if (fRoot) {
192  Clear();
193  SafeDelete(fRoot);
194  }
195 }
196 
197 ////////////////////////////////////////////////////////////////////////////////
198 /// Add object to B-tree.
199 
201 {
202  if (IsArgNull("Add", obj)) return;
203  if (!obj->IsSortable()) {
204  Error("Add", "object must be sortable");
205  return;
206  }
207  if (!fRoot) {
208  fRoot = new TBtLeafNode(0, obj, this);
209  R__CHECK(fRoot != 0);
210  IncrNofKeys();
211  } else {
212  TBtNode *loc;
213  Int_t idx;
214  if (fRoot->Found(obj, &loc, &idx) != 0) {
215  // loc and idx are set to either where the object
216  // was found, or where it should go in the Btree.
217  // Nothing is here now, but later we might give the user
218  // the ability to declare a B-tree as `unique elements only',
219  // in which case we would handle an exception here.
220  }
221  loc->Add(obj, idx);
222  }
223 }
224 
225 ////////////////////////////////////////////////////////////////////////////////
226 /// Cannot use this method since B-tree decides order.
227 
229 {
230  MayNotUse("After");
231  return 0;
232 }
233 
234 ////////////////////////////////////////////////////////////////////////////////
235 /// May not use this method since B-tree decides order.
236 
238 {
239  MayNotUse("Before");
240  return 0;
241 }
242 
243 ////////////////////////////////////////////////////////////////////////////////
244 /// Remove all objects from B-tree. Does NOT delete objects unless the TBtree
245 /// is the owner (set via SetOwner()).
246 
248 {
249  if (IsOwner())
250  Delete();
251  else {
252  SafeDelete(fRoot);
253  fSize = 0;
254  }
255 }
256 
257 ////////////////////////////////////////////////////////////////////////////////
258 /// Remove all objects from B-tree AND delete all heap based objects.
259 
261 {
262  for (Int_t i = 0; i < fSize; i++) {
263  TObject *obj = At(i);
264  if (obj && obj->IsOnHeap())
266  }
267  SafeDelete(fRoot);
268  fSize = 0;
269 }
270 
271 ////////////////////////////////////////////////////////////////////////////////
272 /// Find object using its name (see object's GetName()). Requires sequential
273 /// search of complete tree till object is found.
274 
275 TObject *TBtree::FindObject(const char *name) const
276 {
277  return TCollection::FindObject(name);
278 }
279 
280 ////////////////////////////////////////////////////////////////////////////////
281 /// Find object using the objects Compare() member function.
282 
284 {
285  if (!obj->IsSortable()) {
286  Error("FindObject", "object must be sortable");
287  return 0;
288  }
289  if (!fRoot)
290  return 0;
291  else {
292  TBtNode *loc;
293  Int_t idx;
294  return fRoot->Found(obj, &loc, &idx);
295  }
296 }
297 
298 ////////////////////////////////////////////////////////////////////////////////
299 /// Add object and return its index in the tree.
300 
302 {
303  Int_t r;
304  if (!obj.IsSortable()) {
305  Error("IdxAdd", "object must be sortable");
306  return -1;
307  }
308  if (!fRoot) {
309  fRoot = new TBtLeafNode(0, &obj, this);
310  R__ASSERT(fRoot != 0);
311  IncrNofKeys();
312  r = 0;
313  } else {
314  TBtNode *loc;
315  int idx;
316  if (fRoot->Found(&obj, &loc, &idx) != 0) {
317  // loc and idx are set to either where the object
318  // was found, or where it should go in the Btree.
319  // Nothing is here now, but later we might give the user
320  // the ability to declare a B-tree as `unique elements only',
321  // in which case we would handle an exception here.
322  // std::cerr << "Multiple entry warning\n";
323  } else {
324  R__CHECK(loc->fIsLeaf);
325  }
326  if (loc->fIsLeaf) {
327  if (loc->fParent == 0)
328  r = idx;
329  else
330  r = idx + loc->fParent->FindRankUp(loc);
331  } else {
332  TBtInnerNode *iloc = (TBtInnerNode*) loc;
333  r = iloc->FindRankUp(iloc->GetTree(idx));
334  }
335  loc->Add(&obj, idx);
336  }
337  R__CHECK(r == Rank(&obj) || &obj == (*this)[r]);
338  return r;
339 }
340 
341 ////////////////////////////////////////////////////////////////////////////////
342 /// Initialize a B-tree.
343 
344 void TBtree::Init(Int_t order)
345 {
346  if (order < 3) {
347  Warning("Init", "order must be at least 3");
348  order = 3;
349  }
350  fRoot = 0;
351  fOrder = order;
352  fOrder2 = 2 * (fOrder+1);
353  fLeafMaxIndex = fOrder2 - 1; // fItem[0..fOrder2-1]
354  fInnerMaxIndex = fOrder; // fItem[1..fOrder]
355  //
356  // the low water marks trigger an exploration for balancing
357  // or merging nodes.
358  // When the size of a node falls below X, then it must be possible to
359  // either balance this node with another node, or it must be possible
360  // to merge this node with another node.
361  // This can be guaranteed only if (this->Size() < (MaxSize()-1)/2).
362  //
363  //
364 
365  // == MaxSize() satisfies the above because we compare
366  // lowwatermark with fLast
367  fLeafLowWaterMark = ((fLeafMaxIndex+1)-1) / 2 - 1;
368  fInnerLowWaterMark = (fOrder-1) / 2;
369 }
370 
371 //______________________________________________________________________________
372 //void TBtree::PrintOn(std::ostream& out) const
373 //{
374 // // Print a B-tree.
375 //
376 // if (!fRoot)
377 // out << "<empty>";
378 // else
379 // fRoot->PrintOn(out);
380 //}
381 
382 ////////////////////////////////////////////////////////////////////////////////
383 /// Returns a B-tree iterator.
384 
386 {
387  return new TBtreeIter(this, dir);
388 }
389 
390 ////////////////////////////////////////////////////////////////////////////////
391 /// Returns the rank of the object in the tree.
392 
393 Int_t TBtree::Rank(const TObject *obj) const
394 {
395  if (!obj->IsSortable()) {
396  Error("Rank", "object must be sortable");
397  return -1;
398  }
399  if (!fRoot)
400  return -1;
401  else
402  return fRoot->FindRank(obj);
403 }
404 
405 ////////////////////////////////////////////////////////////////////////////////
406 /// Remove an object from the tree.
407 
409 {
410  if (!obj->IsSortable()) {
411  Error("Remove", "object must be sortable");
412  return 0;
413  }
414  if (!fRoot)
415  return 0;
416 
417  TBtNode *loc;
418  Int_t idx;
419  TObject *ob = fRoot->Found(obj, &loc, &idx);
420  if (!ob)
421  return 0;
422  loc->Remove(idx);
423  return ob;
424 }
425 
426 ////////////////////////////////////////////////////////////////////////////////
427 /// The root of the tree is full. Create an InnerNode that
428 /// points to it, and then inform the InnerNode that it is full.
429 
431 {
432  TBtNode *oldroot = fRoot;
433  fRoot = new TBtInnerNode(0, this, oldroot);
434  R__ASSERT(fRoot != 0);
435  oldroot->Split();
436 }
437 
438 ////////////////////////////////////////////////////////////////////////////////
439 /// If root is empty clean up its space.
440 
442 {
443  if (fRoot->fIsLeaf) {
444  TBtLeafNode *lroot = (TBtLeafNode*)fRoot;
445  R__CHECK(lroot->Psize() == 0);
446  delete lroot;
447  fRoot = 0;
448  } else {
449  TBtInnerNode *iroot = (TBtInnerNode*)fRoot;
450  R__CHECK(iroot->Psize() == 0);
451  fRoot = iroot->GetTree(0);
452  fRoot->fParent = 0;
453  delete iroot;
454  }
455 }
456 
457 ////////////////////////////////////////////////////////////////////////////////
458 /// Stream all objects in the btree to or from the I/O buffer.
459 
460 void TBtree::Streamer(TBuffer &b)
461 {
462  UInt_t R__s, R__c;
463  if (b.IsReading()) {
464  b.ReadVersion(&R__s, &R__c); //Version_t v = b.ReadVersion();
465  b >> fOrder;
466  b >> fOrder2;
467  b >> fInnerLowWaterMark;
468  b >> fLeafLowWaterMark;
469  b >> fInnerMaxIndex;
470  b >> fLeafMaxIndex;
471  TSeqCollection::Streamer(b);
472  b.CheckByteCount(R__s, R__c,TBtree::IsA());
473  } else {
474  R__c = b.WriteVersion(TBtree::IsA(), kTRUE);
475  b << fOrder;
476  b << fOrder2;
477  b << fInnerLowWaterMark;
478  b << fLeafLowWaterMark;
479  b << fInnerMaxIndex;
480  b << fLeafMaxIndex;
481  TSeqCollection::Streamer(b);
482  b.SetByteCount(R__c, kTRUE);
483  }
484 }
485 
486 
487 /** \class TBtItem
488 Item stored in inner nodes of a TBtree.
489 */
490 
491 ////////////////////////////////////////////////////////////////////////////////
492 /// Create an item to be stored in the tree. An item contains a counter
493 /// of the number of keys (i.e. objects) in the node. A pointer to the
494 /// node and a pointer to the object being stored.
495 
497 {
498  fNofKeysInTree = 0;
499  fTree = 0;
500  fKey = 0;
501 }
502 
503 ////////////////////////////////////////////////////////////////////////////////
504 /// Create an item to be stored in the tree. An item contains a counter
505 /// of the number of keys (i.e. objects) in the node. A pointer to the
506 /// node and a pointer to the object being stored.
507 
509 {
510  fNofKeysInTree = n->NofKeys()+1;
511  fTree = n;
512  fKey = obj;
513 }
514 
515 ////////////////////////////////////////////////////////////////////////////////
516 /// Create an item to be stored in the tree. An item contains a counter
517 /// of the number of keys (i.e. objects) in the node. A pointer to the
518 /// node and a pointer to the object being stored.
519 
521 {
522  fNofKeysInTree = n->NofKeys()+1;
523  fTree = n;
524  fKey = obj;
525 }
526 
527 ////////////////////////////////////////////////////////////////////////////////
528 /// Delete a tree item.
529 
531 {
532 }
533 
534 /** \class TBtNode
535 Abstract base class (ABC) of a TBtree node.
536 */
537 
538 ////////////////////////////////////////////////////////////////////////////////
539 /// Create a B-tree node.
540 
542 {
543  fLast = -1;
544  fIsLeaf = isleaf;
545  fParent = p;
546  if (p == 0) {
547  R__CHECK(t != 0);
548  fTree = t;
549  } else
550 #ifdef cxxbug
551 // BUG in the cxx compiler. cxx complains that it cannot access fTree
552 // from TBtInnerNode. To reproduce the cxx bug uncomment the following line
553 // and delete the line after.
554 // fTree = p->fTree;
555  fTree = p->GetParentTree();
556 #else
557  fTree = p->fTree;
558 #endif
559 }
560 
561 ////////////////////////////////////////////////////////////////////////////////
562 /// Delete a B-tree node.
563 
565 {
566 }
567 
568 /** \class TBtreeIter
569 // Iterator of btree.
570 */
571 
573 
574 ////////////////////////////////////////////////////////////////////////////////
575 /// Create a B-tree iterator.
576 
578  : fTree(t), fCurCursor(0), fCursor(0), fDirection(dir)
579 {
580  Reset();
581 }
582 
583 ////////////////////////////////////////////////////////////////////////////////
584 /// Copy ctor.
585 
587 {
588  fTree = iter.fTree;
589  fCursor = iter.fCursor;
590  fCurCursor = iter.fCurCursor;
591  fDirection = iter.fDirection;
592 }
593 
594 ////////////////////////////////////////////////////////////////////////////////
595 /// Overridden assignment operator.
596 
598 {
599  if (this != &rhs && rhs.IsA() == TBtreeIter::Class()) {
600  const TBtreeIter &rhs1 = (const TBtreeIter &)rhs;
601  fTree = rhs1.fTree;
602  fCursor = rhs1.fCursor;
603  fCurCursor = rhs1.fCurCursor;
604  fDirection = rhs1.fDirection;
605  }
606  return *this;
607 }
608 
609 ////////////////////////////////////////////////////////////////////////////////
610 /// Overloaded assignment operator.
611 
613 {
614  if (this != &rhs) {
615  fTree = rhs.fTree;
616  fCursor = rhs.fCursor;
617  fCurCursor = rhs.fCurCursor;
618  fDirection = rhs.fDirection;
619  }
620  return *this;
621 }
622 
623 ////////////////////////////////////////////////////////////////////////////////
624 /// Reset the B-tree iterator.
625 
627 {
628  if (fDirection == kIterForward)
629  fCursor = 0;
630  else
631  fCursor = fTree->GetSize() - 1;
632 
634 }
635 
636 ////////////////////////////////////////////////////////////////////////////////
637 /// Get next object from B-tree. Returns 0 when no more objects in tree.
638 
640 {
642  if (fDirection == kIterForward) {
643  if (fCursor < fTree->GetSize())
644  return (*fTree)[fCursor++];
645  } else {
646  if (fCursor >= 0)
647  return (*fTree)[fCursor--];
648  }
649  return 0;
650 }
651 
652 ////////////////////////////////////////////////////////////////////////////////
653 /// This operator compares two TIterator objects.
654 
656 {
657  if (aIter.IsA() == TBtreeIter::Class()) {
658  const TBtreeIter &iter(dynamic_cast<const TBtreeIter &>(aIter));
659  return (fCurCursor != iter.fCurCursor);
660  }
661  return false; // for base class we don't implement a comparison
662 }
663 
664 ////////////////////////////////////////////////////////////////////////////////
665 /// This operator compares two TBtreeIter objects.
666 
668 {
669  return (fCurCursor != aIter.fCurCursor);
670 }
671 
672 ////////////////////////////////////////////////////////////////////////////////
673 /// Return current object or nullptr.
674 
676 {
677  return (((fCurCursor >= 0) && (fCurCursor < fTree->GetSize())) ?
678  (*fTree)[fCurCursor] : nullptr);
679 }
680 
681 /** \class TBtInnerNode
682 // Inner node of a TBtree.
683 */
684 
685 ////////////////////////////////////////////////////////////////////////////////
686 /// Create a B-tree innernode.
687 
689 {
690  const Int_t index = MaxIndex() + 1;
691  fItem = new TBtItem[ index ];
692  if (fItem == 0)
693  ::Fatal("TBtInnerNode::TBtInnerNode", "no more memory");
694 }
695 
696 ////////////////////////////////////////////////////////////////////////////////
697 /// Called only by TBtree to initialize the TBtInnerNode that is
698 /// about to become the root.
699 
701  : TBtNode(0, parent, tree)
702 {
703  fItem = new TBtItem[MaxIndex()+1];
704  if (fItem == 0)
705  ::Fatal("TBtInnerNode::TBtInnerNode", "no more memory");
706  Append(0, oldroot);
707 }
708 
709 ////////////////////////////////////////////////////////////////////////////////
710 /// Constructor.
711 
713 {
714  if (fLast > 0)
715  delete fItem[0].fTree;
716  for (Int_t i = 1; i <= fLast; i++)
717  delete fItem[i].fTree;
718 
719  delete [] fItem;
720 }
721 
722 ////////////////////////////////////////////////////////////////////////////////
723 /// This is called only from TBtree::Add().
724 
725 void TBtInnerNode::Add(const TObject *obj, Int_t index)
726 {
727  R__ASSERT(index >= 1 && obj->IsSortable());
728  TBtLeafNode *ln = GetTree(index-1)->LastLeafNode();
729  ln->Add(obj, ln->fLast+1);
730 }
731 
732 ////////////////////////////////////////////////////////////////////////////////
733 /// Add one element.
734 
736 {
737  R__ASSERT(0 <= at && at <= fLast+1);
738  R__ASSERT(fLast < MaxIndex());
739  for (Int_t i = fLast+1; i > at ; i--)
740  GetItem(i) = GetItem(i-1);
741  SetItem(at, itm);
742  fLast++;
743 }
744 
745 ////////////////////////////////////////////////////////////////////////////////
746 /// Add one element.
747 
749 {
750  TBtItem newitem(k, t);
751  AddElt(newitem, at);
752 }
753 
754 ////////////////////////////////////////////////////////////////////////////////
755 /// Add one element.
756 
758 {
759  AddElt(itm, at);
760  if (IsFull())
761  InformParent();
762 }
763 
764 ////////////////////////////////////////////////////////////////////////////////
765 /// Add one element.
766 
768 {
769  TBtItem newitem(k, t);
770  Add(newitem, at);
771 }
772 
773 ////////////////////////////////////////////////////////////////////////////////
774 /// This should never create a full node that is, it is not used
775 /// anywhere where THIS could possibly be near full.
776 
778 {
779  if (start > stop)
780  return;
781  R__ASSERT(0 <= start && start <= src->fLast);
782  R__ASSERT(0 <= stop && stop <= src->fLast );
783  R__ASSERT(fLast + stop - start + 1 < MaxIndex()); // full-node check
784  for (Int_t i = start; i <= stop; i++)
785  SetItem(++fLast, src->GetItem(i));
786 }
787 
788 ////////////////////////////////////////////////////////////////////////////////
789 /// Never called from anywhere where it might fill up THIS.
790 
792 {
793  R__ASSERT(fLast < MaxIndex());
794  if (d) R__ASSERT(d->IsSortable());
795  SetItem(++fLast, d, n);
796 }
797 
798 ////////////////////////////////////////////////////////////////////////////////
799 /// Append itm to this tree.
800 
802 {
803  R__ASSERT(fLast < MaxIndex());
804  SetItem(++fLast, itm);
805 }
806 
807 ////////////////////////////////////////////////////////////////////////////////
808 /// THIS has more than LEFTSIB. Move some item from THIS to LEFTSIB.
809 /// PIDX is the index of the parent item that will change when keys
810 /// are moved.
811 
813 {
814  R__ASSERT(Vsize() >= leftsib->Psize());
815  R__ASSERT(fParent->GetTree(pidx) == this);
816  Int_t newThisSize = (Vsize() + leftsib->Psize())/2;
817  Int_t noFromThis = Psize() - newThisSize;
818  PushLeft(noFromThis, leftsib, pidx);
819 }
820 
821 ////////////////////////////////////////////////////////////////////////////////
822 /// THIS has more than RIGHTSIB. Move some items from THIS to RIGHTSIB.
823 /// PIDX is the index of the parent item that will change when keys
824 /// are moved.
825 
827 {
828  R__ASSERT(Psize() >= rightsib->Vsize());
829  R__ASSERT(fParent->GetTree(pidx) == rightsib);
830  Int_t newThisSize = (Psize() + rightsib->Vsize())/2;
831  Int_t noFromThis = Psize() - newThisSize;
832  PushRight(noFromThis, rightsib, pidx);
833 }
834 
835 ////////////////////////////////////////////////////////////////////////////////
836 /// PINDX is the index of the parent item whose key will change when
837 /// keys are shifted from one InnerNode to the other.
838 
840 {
841  if (Psize() < rightsib->Vsize())
842  rightsib->BalanceWithLeft(this, pindx);
843  else
844  BalanceWithRight(rightsib, pindx);
845 }
846 
847 ////////////////////////////////////////////////////////////////////////////////
848 /// THAT is a child of THIS that has just shrunk by 1.
849 
851 {
852  Int_t i = IndexOf(that);
853  fItem[i].fNofKeysInTree--;
854  if (fParent != 0)
855  fParent->DecrNofKeys(this);
856  else
857  fTree->DecrNofKeys();
858 }
859 
860 ////////////////////////////////////////////////////////////////////////////////
861 /// Recursively look for WHAT starting in the current node.
862 
864 {
865  if (((TObject *)what)->Compare(GetKey(1)) < 0)
866  return GetTree(0)->FindRank(what);
867  Int_t sum = GetNofKeys(0);
868  for (Int_t i = 1; i < fLast; i++) {
869  if (((TObject*)what)->Compare(GetKey(i)) == 0)
870  return sum;
871  sum++;
872  if (((TObject *)what)->Compare(GetKey(i+1)) < 0)
873  return sum + GetTree(i)->FindRank(what);
874  sum += GetNofKeys(i);
875  }
876  if (((TObject*)what)->Compare(GetKey(fLast)) == 0)
877  return sum;
878  sum++;
879  // *what > GetKey(fLast), so recurse on last fItem.fTree
880  return sum + GetTree(fLast)->FindRank(what);
881 }
882 
883 ////////////////////////////////////////////////////////////////////////////////
884 /// FindRankUp is FindRank in reverse.
885 /// Whereas FindRank looks for the object and computes the rank
886 /// along the way while walking DOWN the tree, FindRankUp already
887 /// knows where the object is and has to walk UP the tree from the
888 /// object to compute the rank.
889 
891 {
892  Int_t l = IndexOf(that);
893  Int_t sum = 0;
894  for (Int_t i = 0; i < l; i++)
895  sum += GetNofKeys(i);
896  return sum + l + (fParent == 0 ? 0 : fParent->FindRankUp(this));
897 }
898 
899 ////////////////////////////////////////////////////////////////////////////////
900 /// Return the first leaf node.
901 
903 {
904  return GetTree(0)->FirstLeafNode();
905 }
906 
907 ////////////////////////////////////////////////////////////////////////////////
908 /// Recursively look for WHAT starting in the current node.
909 
910 TObject *TBtInnerNode::Found(const TObject *what, TBtNode **which, Int_t *where)
911 {
912  R__ASSERT(what->IsSortable());
913  for (Int_t i = 1 ; i <= fLast; i++) {
914  if (GetKey(i)->Compare(what) == 0) {
915  // then could go in either fItem[i].fTree or fItem[i-1].fTree
916  // should go in one with the most room, but that's kinda
917  // hard to calculate, so we'll stick it in fItem[i].fTree
918  *which = this;
919  *where = i;
920  return GetKey(i);
921  }
922  if (GetKey(i)->Compare(what) > 0)
923  return GetTree(i-1)->Found(what, which, where);
924  }
925  // *what > *(*this)[fLast].fKey, so recurse on last fItem.fTree
926  return GetTree(fLast)->Found(what, which, where);
927 }
928 
929 ////////////////////////////////////////////////////////////////////////////////
930 /// THAT is a child of THIS that has just grown by 1.
931 
933 {
934  Int_t i = IndexOf(that);
935  fItem[i].fNofKeysInTree++;
936  if (fParent != 0)
937  fParent->IncrNofKeys(this);
938  else
939  fTree->IncrNofKeys();
940 }
941 
942 ////////////////////////////////////////////////////////////////////////////////
943 /// Returns a number in the range 0 to this->fLast
944 /// 0 is returned if THAT == fTree[0].
945 
947 {
948  for (Int_t i = 0; i <= fLast; i++)
949  if (GetTree(i) == that)
950  return i;
951  R__CHECK(0);
952  return 0;
953 }
954 
955 ////////////////////////////////////////////////////////////////////////////////
956 /// Tell the parent that we are full.
957 
959 {
960  if (fParent == 0) {
961  // then this is the root of the tree and needs to be split
962  // inform the btree.
963  R__ASSERT(fTree->fRoot == this);
964  fTree->RootIsFull();
965  } else
966  fParent->IsFull(this);
967 }
968 
969 ////////////////////////////////////////////////////////////////////////////////
970 /// The child node THAT is full. We will either redistribute elements
971 /// or create a new node and then redistribute.
972 /// In an attempt to minimize the number of splits, we adopt the following
973 /// strategy:
974 /// - redistribute if possible
975 /// - if not possible, then split with a sibling
976 
978 {
979  if (that->fIsLeaf) {
980  TBtLeafNode *leaf = (TBtLeafNode *)that;
981  TBtLeafNode *left = 0;
982  TBtLeafNode *right= 0;
983  // split LEAF only if both sibling nodes are full.
984  Int_t leafidx = IndexOf(leaf);
985  Int_t hasRightSib = (leafidx < fLast) &&
986  ((right = (TBtLeafNode*)GetTree(leafidx+1)) != 0);
987  Int_t hasLeftSib = (leafidx > 0) &&
988  ((left = (TBtLeafNode*)GetTree(leafidx-1)) != 0);
989  Int_t rightSibFull = (hasRightSib && right->IsAlmostFull());
990  Int_t leftSibFull = (hasLeftSib && left->IsAlmostFull());
991  if (rightSibFull) {
992  if (leftSibFull) {
993  // both full, so pick one to split with
994  left->SplitWith(leaf, leafidx);
995  } else if (hasLeftSib) {
996  // left sib not full, so balance with it
997  leaf->BalanceWithLeft(left, leafidx);
998  } else {
999  // there is no left sibling, so split with right
1000  leaf->SplitWith(right, leafidx+1);
1001  }
1002  } else if (hasRightSib) {
1003  // right sib not full, so balance with it
1004  leaf->BalanceWithRight(right, leafidx+1);
1005  } else if (leftSibFull) {
1006  // no right sib, and left sib is full, so split with it
1007  left->SplitWith(leaf, leafidx);
1008  } else if (hasLeftSib) {
1009  // left sib not full so balance with it
1010  leaf->BalanceWithLeft(left, leafidx);
1011  } else {
1012  // neither a left or right sib; should never happen
1013  R__CHECK(0);
1014  }
1015  } else {
1016  TBtInnerNode *inner = (TBtInnerNode *)that;
1017  // split INNER only if both sibling nodes are full
1018  Int_t inneridx = IndexOf(inner);
1019  TBtInnerNode *left = 0;
1020  TBtInnerNode *right= 0;
1021  Int_t hasRightSib = (inneridx < fLast) &&
1022  ((right = (TBtInnerNode*)GetTree(inneridx+1)) != 0);
1023  Int_t hasLeftSib = (inneridx > 0) &&
1024  ((left=(TBtInnerNode*)GetTree(inneridx-1)) != 0);
1025  Int_t rightSibFull = (hasRightSib && right->IsAlmostFull());
1026  Int_t leftSibFull = (hasLeftSib && left->IsAlmostFull());
1027  if (rightSibFull) {
1028  if (leftSibFull) {
1029  left->SplitWith(inner, inneridx);
1030  } else if (hasLeftSib) {
1031  inner->BalanceWithLeft(left, inneridx);
1032  } else {
1033  // there is no left sibling
1034  inner->SplitWith(right, inneridx+1);
1035  }
1036  } else if (hasRightSib) {
1037  inner->BalanceWithRight(right, inneridx+1);
1038  } else if (leftSibFull) {
1039  left->SplitWith(inner, inneridx);
1040  } else if (hasLeftSib) {
1041  inner->BalanceWithLeft(left, inneridx);
1042  } else {
1043  R__CHECK(0);
1044  }
1045  }
1046 }
1047 
1048 ////////////////////////////////////////////////////////////////////////////////
1049 /// The child node THAT is <= half full. We will either redistribute
1050 /// elements between children, or THAT will be merged with another child.
1051 /// In an attempt to minimize the number of mergers, we adopt the following
1052 /// strategy:
1053 /// - redistribute if possible
1054 /// - if not possible, then merge with a sibling
1055 
1057 {
1058  if (that->fIsLeaf) {
1059  TBtLeafNode *leaf = (TBtLeafNode *)that;
1060  TBtLeafNode *left = 0;
1061  TBtLeafNode *right= 0;
1062  // split LEAF only if both sibling nodes are full.
1063  Int_t leafidx = IndexOf(leaf);
1064  Int_t hasRightSib = (leafidx < fLast) &&
1065  ((right = (TBtLeafNode*)GetTree(leafidx+1)) != 0);
1066  Int_t hasLeftSib = (leafidx > 0) &&
1067  ((left = (TBtLeafNode*)GetTree(leafidx-1)) != 0);
1068  if (hasRightSib && (leaf->Psize() + right->Vsize()) >= leaf->MaxPsize()) {
1069  // then cannot merge,
1070  // and balancing this and rightsib will leave them both
1071  // more than half full
1072  leaf->BalanceWith(right, leafidx+1);
1073  } else if (hasLeftSib && (leaf->Vsize() + left->Psize()) >= leaf->MaxPsize()) {
1074  // ditto
1075  left->BalanceWith(leaf, leafidx);
1076  } else if (hasLeftSib) {
1077  // then they should be merged
1078  left->MergeWithRight(leaf, leafidx);
1079  } else if (hasRightSib) {
1080  leaf->MergeWithRight(right, leafidx+1);
1081  } else {
1082  R__CHECK(0); // should never happen
1083  }
1084  } else {
1085  TBtInnerNode *inner = (TBtInnerNode *)that;
1086 
1087  Int_t inneridx = IndexOf(inner);
1088  TBtInnerNode *left = 0;
1089  TBtInnerNode *right= 0;
1090  Int_t hasRightSib = (inneridx < fLast) &&
1091  ((right = (TBtInnerNode*)GetTree(inneridx+1)) != 0);
1092  Int_t hasLeftSib = (inneridx > 0) &&
1093  ((left = (TBtInnerNode*)GetTree(inneridx-1)) != 0);
1094  if (hasRightSib && (inner->Psize() + right->Vsize()) >= inner->MaxPsize()) {
1095  // cannot merge
1096  inner->BalanceWith(right, inneridx+1);
1097  } else if (hasLeftSib && (inner->Vsize() + left->Psize()) >= inner->MaxPsize()) {
1098  // cannot merge
1099  left->BalanceWith(inner, inneridx);
1100  } else if (hasLeftSib) {
1101  left->MergeWithRight(inner, inneridx);
1102  } else if (hasRightSib) {
1103  inner->MergeWithRight(right, inneridx+1);
1104  } else {
1105  R__CHECK(0);
1106  }
1107  }
1108 }
1109 
1110 ////////////////////////////////////////////////////////////////////////////////
1111 /// Return the last leaf node.
1112 
1114 {
1115  return GetTree(fLast)->LastLeafNode();
1116 }
1117 
1118 ////////////////////////////////////////////////////////////////////////////////
1119 /// Merge the 2 part of the tree.
1120 
1122 {
1123  R__ASSERT(Psize() + rightsib->Vsize() < MaxIndex());
1124  if (rightsib->Psize() > 0)
1125  rightsib->PushLeft(rightsib->Psize(), this, pidx);
1126  rightsib->SetKey(0, fParent->GetKey(pidx));
1127  AppendFrom(rightsib, 0, 0);
1128  fParent->IncNofKeys(pidx-1, rightsib->GetNofKeys(0)+1);
1129  fParent->RemoveItem(pidx);
1130  delete rightsib;
1131 }
1132 
1133 ////////////////////////////////////////////////////////////////////////////////
1134 /// Number of key.
1135 
1137 {
1138  Int_t sum = 0;
1139  for (Int_t i = 0; i <= fLast; i++)
1140  sum += GetNofKeys(i);
1141  return sum + Psize();
1142 }
1143 
1144 ////////////////////////////////////////////////////////////////////////////////
1145 /// return an element.
1146 
1148 {
1149  for (Int_t j = 0; j <= fLast; j++) {
1150  Int_t r;
1151  if (idx < (r = GetNofKeys(j)))
1152  return (*GetTree(j))[idx];
1153  if (idx == r) {
1154  if (j == fLast) {
1155  ::Error("TBtInnerNode::operator[]", "should not happen, 0 returned");
1156  return 0;
1157  } else
1158  return GetKey(j+1);
1159  }
1160  idx -= r+1; // +1 because of the key in the node
1161  }
1162  ::Error("TBtInnerNode::operator[]", "should not happen, 0 returned");
1163  return 0;
1164 }
1165 
1166 ////////////////////////////////////////////////////////////////////////////////
1167 /// noFromThis==1 => moves the parent item into the leftsib,
1168 /// and the first item in this's array into the parent item.
1169 
1170 void TBtInnerNode::PushLeft(Int_t noFromThis, TBtInnerNode *leftsib, Int_t pidx)
1171 {
1172  R__ASSERT(fParent->GetTree(pidx) == this);
1173  R__ASSERT(noFromThis > 0 && noFromThis <= Psize());
1174  R__ASSERT(noFromThis + leftsib->Psize() < MaxPsize());
1175  SetKey(0, fParent->GetKey(pidx)); // makes AppendFrom's job easier
1176  leftsib->AppendFrom(this, 0, noFromThis-1);
1177  ShiftLeft(noFromThis);
1178  fParent->SetKey(pidx, GetKey(0));
1179  fParent->SetNofKeys(pidx-1, leftsib->NofKeys());
1180  fParent->SetNofKeys(pidx, NofKeys());
1181 }
1182 
1183 ////////////////////////////////////////////////////////////////////////////////
1184 /// The operation is three steps:
1185 /// - Step I. Make room for the incoming keys in RIGHTSIB.
1186 /// - Step II. Move the items from THIS into RIGHTSIB.
1187 /// - Step III. Update the length of THIS.
1188 
1189 void TBtInnerNode::PushRight(Int_t noFromThis, TBtInnerNode *rightsib, Int_t pidx)
1190 {
1191  R__ASSERT(noFromThis > 0 && noFromThis <= Psize());
1192  R__ASSERT(noFromThis + rightsib->Psize() < rightsib->MaxPsize());
1193  R__ASSERT(fParent->GetTree(pidx) == rightsib);
1194 
1195  //
1196  // Step I. Make space for noFromThis items
1197  //
1198  Int_t start = fLast - noFromThis + 1;
1199  Int_t tgt, src;
1200  tgt = rightsib->fLast + noFromThis;
1201  src = rightsib->fLast;
1202  rightsib->fLast = tgt;
1203  rightsib->SetKey(0, fParent->GetKey(pidx));
1204  IncNofKeys(0);
1205  while (src >= 0) {
1206  // do this kind of assignment on TBtInnerNode items only when
1207  // the parent fields of the moved items do not change, as they
1208  // don't here.
1209  // Otherwise, use SetItem so the parents are updated appropriately.
1210  rightsib->GetItem(tgt--) = rightsib->GetItem(src--);
1211  }
1212 
1213  // Step II. Move the items from THIS into RIGHTSIB
1214  for (Int_t i = fLast; i >= start; i-- ) {
1215  // this is the kind of assignment to use when parents change
1216  rightsib->SetItem(tgt--, GetItem(i));
1217  }
1218  fParent->SetKey(pidx, rightsib->GetKey(0));
1219  DecNofKeys(0);
1220  R__CHECK(tgt == -1);
1221 
1222  // Step III.
1223  fLast -= noFromThis;
1224 
1225  // Step VI. update NofKeys
1226  fParent->SetNofKeys(pidx-1, NofKeys());
1227  fParent->SetNofKeys(pidx, rightsib->NofKeys());
1228 }
1229 
1230 ////////////////////////////////////////////////////////////////////////////////
1231 /// Remove an element.
1232 
1234 {
1235  R__ASSERT(index >= 1 && index <= fLast);
1236  TBtLeafNode *lf = GetTree(index)->FirstLeafNode();
1237  SetKey(index, lf->fItem[0]);
1238  lf->RemoveItem(0);
1239 }
1240 
1241 ////////////////////////////////////////////////////////////////////////////////
1242 /// Remove an item.
1243 
1245 {
1246  R__ASSERT(index >= 1 && index <= fLast);
1247  for (Int_t to = index; to < fLast; to++)
1248  fItem[to] = fItem[to+1];
1249  fLast--;
1250  if (IsLow()) {
1251  if (fParent == 0) {
1252  // then this is the root; when only one child, make the child the root
1253  if (Psize() == 0)
1254  fTree->RootIsEmpty();
1255  } else
1256  fParent->IsLow(this);
1257  }
1258 }
1259 
1260 ////////////////////////////////////////////////////////////////////////////////
1261 /// Shift to the left.
1262 
1264 {
1265  if (cnt <= 0)
1266  return;
1267  for (Int_t i = cnt; i <= fLast; i++)
1268  GetItem(i-cnt) = GetItem(i);
1269  fLast -= cnt;
1270 }
1271 
1272 ////////////////////////////////////////////////////////////////////////////////
1273 /// This function is called only when THIS is the only descendent
1274 /// of the root node, and THIS needs to be split.
1275 /// Assumes that idx of THIS in fParent is 0.
1276 
1278 {
1279  TBtInnerNode *newnode = new TBtInnerNode(fParent);
1280  R__CHECK(newnode != 0);
1281  fParent->Append(GetKey(fLast), newnode);
1282  newnode->AppendFrom(this, fLast, fLast);
1283  fLast--;
1284  fParent->IncNofKeys(1, newnode->GetNofKeys(0));
1285  fParent->DecNofKeys(0, newnode->GetNofKeys(0));
1286  BalanceWithRight(newnode, 1);
1287 }
1288 
1289 ////////////////////////////////////////////////////////////////////////////////
1290 /// THIS and SIB are too full; create a NEWNODE, and balance
1291 /// the number of keys between the three of them.
1292 ///
1293 /// picture: (also see Knuth Vol 3 pg 478)
1294 /// ~~~ {.cpp}
1295 /// keyidx keyidx+1
1296 /// +--+--+--+--+--+--...
1297 /// | | | | | |
1298 /// fParent--->| | | |
1299 /// | | | |
1300 /// +*-+*-+*-+--+--+--...
1301 /// | | |
1302 /// +----+ | +-----+
1303 /// | +-----+ |
1304 /// V | V
1305 /// +----------+ | +----------+
1306 /// | | | | |
1307 /// this->| | | | |<--sib
1308 /// +----------+ | +----------+
1309 /// V
1310 /// data
1311 /// ~~~
1312 /// keyidx is the index of where the sibling is, and where the
1313 /// newly created node will be recorded (sibling will be moved to
1314 /// keyidx+1)
1315 
1317 {
1318  R__ASSERT(keyidx > 0 && keyidx <= fParent->fLast);
1319 
1320  rightsib->SetKey(0, fParent->GetKey(keyidx));
1321  Int_t nofKeys = Psize() + rightsib->Vsize();
1322  Int_t newSizeThis = nofKeys / 3;
1323  Int_t newSizeNew = (nofKeys - newSizeThis) / 2;
1324  Int_t newSizeSib = (nofKeys - newSizeThis - newSizeNew);
1325  Int_t noFromThis = Psize() - newSizeThis;
1326  Int_t noFromSib = rightsib->Vsize() - newSizeSib;
1327  // because of their smaller size, this TBtInnerNode may not have to
1328  // give up any elements to the new node. I.e., noFromThis == 0.
1329  // This will not happen for TBtLeafNodes.
1330  // We handle this by pulling an item from the rightsib.
1331  R__CHECK(noFromThis >= 0);
1332  R__CHECK(noFromSib >= 1);
1333  TBtInnerNode *newNode = new TBtInnerNode(fParent);
1334  R__CHECK(newNode != 0);
1335  if (noFromThis > 0) {
1336  newNode->Append(GetItem(fLast));
1337  fParent->AddElt(keyidx, GetKey(fLast--), newNode);
1338  if (noFromThis > 2)
1339  this->PushRight(noFromThis-1, newNode, keyidx);
1340  rightsib->PushLeft(noFromSib, newNode, keyidx+1);
1341  } else {
1342  // pull an element from the rightsib
1343  newNode->Append(rightsib->GetItem(0));
1344  fParent->AddElt(keyidx+1, rightsib->GetKey(1), rightsib);
1345  rightsib->ShiftLeft(1);
1346  fParent->SetTree(keyidx, newNode);
1347  rightsib->PushLeft(noFromSib-1, newNode, keyidx+1);
1348  }
1349  fParent->SetNofKeys(keyidx-1, this->NofKeys());
1350  fParent->SetNofKeys(keyidx, newNode->NofKeys());
1351  fParent->SetNofKeys(keyidx+1, rightsib->NofKeys());
1352  if (fParent->IsFull())
1353  fParent->InformParent();
1354 }
1355 
1356 /** \class TBtLeafNode
1357 Leaf node of a TBtree.
1358 */
1359 
1360 ////////////////////////////////////////////////////////////////////////////////
1361 /// Constructor.
1362 
1364 {
1365  fItem = new TObject *[MaxIndex()+1];
1366  memset(fItem, 0, (MaxIndex()+1)*sizeof(TObject*));
1367 
1368  R__ASSERT(fItem != 0);
1369  if (obj != 0)
1370  fItem[++fLast] = (TObject*)obj; // cast const away
1371 }
1372 
1373 ////////////////////////////////////////////////////////////////////////////////
1374 /// Destructor.
1375 
1377 {
1378  delete [] fItem;
1379 }
1380 
1381 ////////////////////////////////////////////////////////////////////////////////
1382 /// Add the object OBJ to the leaf node, inserting it at location INDEX
1383 /// in the fItem array.
1384 
1385 void TBtLeafNode::Add(const TObject *obj, Int_t index)
1386 {
1387  R__ASSERT(obj->IsSortable());
1388  R__ASSERT(0 <= index && index <= fLast+1);
1389  R__ASSERT(fLast <= MaxIndex());
1390  for (Int_t i = fLast+1; i > index ; i--)
1391  fItem[i] = fItem[i-1];
1392  fItem[index] = (TObject *)obj;
1393  fLast++;
1394 
1395  // check for overflow
1396  if (fParent == 0)
1397  fTree->IncrNofKeys();
1398  else
1399  fParent->IncrNofKeys(this);
1400 
1401  if (IsFull()) {
1402  // it's full; tell parent node
1403  if (fParent == 0) {
1404  // this occurs when this leaf is the only node in the
1405  // btree, and this->fTree->fRoot == this
1406  R__CHECK(fTree->fRoot == this);
1407  // in which case we inform the btree, which can be
1408  // considered the parent of this node
1409  fTree->RootIsFull();
1410  } else {
1411  // the parent is responsible for splitting/balancing subnodes
1412  fParent->IsFull(this);
1413  }
1414  }
1415 }
1416 
1417 ////////////////////////////////////////////////////////////////////////////////
1418 /// A convenience function, does not worry about the element in
1419 /// the parent, simply moves elements from SRC[start] to SRC[stop]
1420 /// into the current array.
1421 /// This should never create a full node.
1422 /// That is, it is not used anywhere where THIS could possibly be
1423 /// near full.
1424 /// Does NOT handle nofKeys.
1425 
1427 {
1428  if (start > stop)
1429  return;
1430  R__ASSERT(0 <= start && start <= src->fLast);
1431  R__ASSERT(0 <= stop && stop <= src->fLast);
1432  R__ASSERT(fLast + stop - start + 1 < MaxIndex()); // full-node check
1433  for (Int_t i = start; i <= stop; i++)
1434  fItem[++fLast] = src->fItem[i];
1435  R__CHECK(fLast < MaxIndex());
1436 }
1437 
1438 ////////////////////////////////////////////////////////////////////////////////
1439 /// Never called from anywhere where it might fill up THIS
1440 /// does NOT handle nofKeys.
1441 
1443 {
1444  R__ASSERT(obj->IsSortable());
1445  fItem[++fLast] = obj;
1446  R__CHECK(fLast < MaxIndex());
1447 }
1448 
1449 ////////////////////////////////////////////////////////////////////////////////
1450 /// THIS has more than LEFTSIB; move some items from THIS to LEFTSIB.
1451 
1453 {
1454  R__ASSERT(Vsize() >= leftsib->Psize());
1455  Int_t newThisSize = (Vsize() + leftsib->Psize())/2;
1456  Int_t noFromThis = Psize() - newThisSize;
1457  PushLeft(noFromThis, leftsib, pidx);
1458 }
1459 
1460 ////////////////////////////////////////////////////////////////////////////////
1461 /// THIS has more than RIGHTSIB; move some items from THIS to RIGHTSIB.
1462 
1464 {
1465  R__ASSERT(Psize() >= rightsib->Vsize());
1466  Int_t newThisSize = (Psize() + rightsib->Vsize())/2;
1467  Int_t noFromThis = Psize() - newThisSize;
1468  PushRight(noFromThis, rightsib, pidx);
1469 }
1470 
1471 ////////////////////////////////////////////////////////////////////////////////
1472 /// PITEM is the parent item whose key will change when keys are shifted
1473 /// from one LeafNode to the other.
1474 
1476 {
1477  if (Psize() < rightsib->Vsize())
1478  rightsib->BalanceWithLeft(this, pidx);
1479  else
1480  BalanceWithRight(rightsib, pidx);
1481 }
1482 
1483 ////////////////////////////////////////////////////////////////////////////////
1484 /// WHAT was not in any inner node; it is either here, or it's
1485 /// not in the tree.
1486 
1488 {
1489  for (Int_t i = 0; i <= fLast; i++) {
1490  if (fItem[i]->Compare(what) == 0)
1491  return i;
1492  if (fItem[i]->Compare(what) > 0)
1493  return -1;
1494  }
1495  return -1;
1496 }
1497 
1498 ////////////////////////////////////////////////////////////////////////////////
1499 /// Return the first node.
1500 
1502 {
1503  return this;
1504 }
1505 
1506 ////////////////////////////////////////////////////////////////////////////////
1507 /// WHAT was not in any inner node; it is either here, or it's
1508 /// not in the tree.
1509 
1510 TObject *TBtLeafNode::Found(const TObject *what, TBtNode **which, Int_t *where)
1511 {
1512  R__ASSERT(what->IsSortable());
1513  for (Int_t i = 0; i <= fLast; i++) {
1514  if (fItem[i]->Compare(what) == 0) {
1515  *which = this;
1516  *where = i;
1517  return fItem[i];
1518  }
1519  if (fItem[i]->Compare(what) > 0) {
1520  *which = this;
1521  *where = i;
1522  return 0;
1523  }
1524  }
1525  *which = this;
1526  *where = fLast+1;
1527  return 0;
1528 }
1529 
1530 ////////////////////////////////////////////////////////////////////////////////
1531 /// Returns a number in the range 0 to MaxIndex().
1532 
1534 {
1535  for (Int_t i = 0; i <= fLast; i++) {
1536  if (fItem[i] == that)
1537  return i;
1538  }
1539  R__CHECK(0);
1540  return -1;
1541 }
1542 
1543 ////////////////////////////////////////////////////////////////////////////////
1544 /// return the last node.
1545 
1547 {
1548  return this;
1549 }
1550 
1551 ////////////////////////////////////////////////////////////////////////////////
1552 /// Merge.
1553 
1555 {
1556  R__ASSERT(Psize() + rightsib->Vsize() < MaxPsize());
1557  rightsib->PushLeft(rightsib->Psize(), this, pidx);
1558  Append(fParent->GetKey(pidx));
1559  fParent->SetNofKeys(pidx-1, NofKeys());
1560  fParent->RemoveItem(pidx);
1561  delete rightsib;
1562 }
1563 
1564 ////////////////////////////////////////////////////////////////////////////////
1565 /// Return the number of keys.
1566 
1568 {
1569  return 1;
1570 }
1571 
1572 ////////////////////////////////////////////////////////////////////////////////
1573 /// Return the number of keys.
1574 
1576 {
1577  return Psize();
1578 }
1579 
1580 //______________________________________________________________________________
1581 //void TBtLeafNode::PrintOn(std::ostream& out) const
1582 //{
1583 // out << " < ";
1584 // for (Int_t i = 0; i <= fLast; i++)
1585 // out << *fItem[i] << " " ;
1586 // out << "> ";
1587 //}
1588 
1589 ////////////////////////////////////////////////////////////////////////////////
1590 /// noFromThis==1 => moves the parent item into the leftsib,
1591 /// and the first item in this's array into the parent item.
1592 
1593 void TBtLeafNode::PushLeft(Int_t noFromThis, TBtLeafNode *leftsib, Int_t pidx)
1594 {
1595  R__ASSERT(noFromThis > 0 && noFromThis <= Psize());
1596  R__ASSERT(noFromThis + leftsib->Psize() < MaxPsize());
1597  R__ASSERT(fParent->GetTree(pidx) == this);
1598  leftsib->Append(fParent->GetKey(pidx));
1599  if (noFromThis > 1)
1600  leftsib->AppendFrom(this, 0, noFromThis-2);
1601  fParent->SetKey(pidx, fItem[noFromThis-1]);
1602  ShiftLeft(noFromThis);
1603  fParent->SetNofKeys(pidx-1, leftsib->NofKeys());
1604  fParent->SetNofKeys(pidx, NofKeys());
1605 }
1606 
1607 ////////////////////////////////////////////////////////////////////////////////
1608 /// noFromThis==1 => moves the parent item into the
1609 /// rightsib, and the last item in this's array into the parent
1610 /// item.
1611 
1612 void TBtLeafNode::PushRight(Int_t noFromThis, TBtLeafNode *rightsib, Int_t pidx)
1613 {
1614  R__ASSERT(noFromThis > 0 && noFromThis <= Psize());
1615  R__ASSERT(noFromThis + rightsib->Psize() < MaxPsize());
1616  R__ASSERT(fParent->GetTree(pidx) == rightsib);
1617  // The operation is five steps:
1618  // Step I. Make room for the incoming keys in RIGHTSIB.
1619  // Step II. Move the key in the parent into RIGHTSIB.
1620  // Step III. Move the items from THIS into RIGHTSIB.
1621  // Step IV. Move the item from THIS into the parent.
1622  // Step V. Update the length of THIS.
1623  //
1624  // Step I.: make space for noFromThis items
1625  //
1626  Int_t start = fLast - noFromThis + 1;
1627  Int_t tgt, src;
1628  tgt = rightsib->fLast + noFromThis;
1629  src = rightsib->fLast;
1630  rightsib->fLast = tgt;
1631  while (src >= 0)
1632  rightsib->fItem[tgt--] = rightsib->fItem[src--];
1633 
1634  // Step II. Move the key from the parent into place
1635  rightsib->fItem[tgt--] = fParent->GetKey(pidx);
1636 
1637  // Step III.Move the items from THIS into RIGHTSIB
1638  for (Int_t i = fLast; i > start; i--)
1639  rightsib->fItem[tgt--] = fItem[i];
1640  R__CHECK(tgt == -1);
1641 
1642  // Step IV.
1643  fParent->SetKey(pidx, fItem[start]);
1644 
1645  // Step V.
1646  fLast -= noFromThis;
1647 
1648  // Step VI. update nofKeys
1649  fParent->SetNofKeys(pidx-1, NofKeys());
1650  fParent->SetNofKeys(pidx, rightsib->NofKeys());
1651 }
1652 
1653 ////////////////////////////////////////////////////////////////////////////////
1654 /// Remove an element.
1655 
1657 {
1658  R__ASSERT(index >= 0 && index <= fLast);
1659  for (Int_t to = index; to < fLast; to++)
1660  fItem[to] = fItem[to+1];
1661  fLast--;
1662  if (fParent == 0)
1663  fTree->DecrNofKeys();
1664  else
1665  fParent->DecrNofKeys(this);
1666  if (IsLow()) {
1667  if (fParent == 0) {
1668  // then this is the root; when no keys left, inform the tree
1669  if (Psize() == 0)
1670  fTree->RootIsEmpty();
1671  } else
1672  fParent->IsLow(this);
1673  }
1674 }
1675 
1676 ////////////////////////////////////////////////////////////////////////////////
1677 /// Shift.
1678 
1680 {
1681  if (cnt <= 0)
1682  return;
1683  for (Int_t i = cnt; i <= fLast; i++)
1684  fItem[i-cnt] = fItem[i];
1685  fLast -= cnt;
1686 }
1687 
1688 ////////////////////////////////////////////////////////////////////////////////
1689 /// This function is called only when THIS is the only descendent
1690 /// of the root node, and THIS needs to be split.
1691 /// Assumes that idx of THIS in Parent is 0.
1692 
1694 {
1695  TBtLeafNode *newnode = new TBtLeafNode(fParent);
1696  R__ASSERT(newnode != 0);
1697  fParent->Append(fItem[fLast--], newnode);
1700  BalanceWithRight(newnode, 1);
1701 }
1702 
1703 ////////////////////////////////////////////////////////////////////////////////
1704 /// Split.
1705 
1707 {
1708  R__ASSERT(fParent == rightsib->fParent);
1709  R__ASSERT(keyidx > 0 && keyidx <= fParent->fLast);
1710  Int_t nofKeys = Psize() + rightsib->Vsize();
1711  Int_t newSizeThis = nofKeys / 3;
1712  Int_t newSizeNew = (nofKeys - newSizeThis) / 2;
1713  Int_t newSizeSib = (nofKeys - newSizeThis - newSizeNew);
1714  Int_t noFromThis = Psize() - newSizeThis;
1715  Int_t noFromSib = rightsib->Vsize() - newSizeSib;
1716  R__CHECK(noFromThis >= 0);
1717  R__CHECK(noFromSib >= 1);
1718  TBtLeafNode *newNode = new TBtLeafNode(fParent);
1719  R__ASSERT(newNode != 0);
1720  fParent->AddElt(keyidx, fItem[fLast--], newNode);
1721  fParent->SetNofKeys(keyidx, 0);
1722  fParent->DecNofKeys(keyidx-1);
1723  this->PushRight(noFromThis-1, newNode, keyidx);
1724  rightsib->PushLeft(noFromSib, newNode, keyidx+1);
1725  if (fParent->IsFull())
1726  fParent->InformParent();
1727 }
TBtLeafNode(TBtInnerNode *p, const TObject *obj=0, TBtree *t=0)
Constructor.
Definition: TBtree.cxx:1363
void SetItem(Int_t i, TBtItem &itm)
Definition: TBtree.h:212
Int_t NofKeys(Int_t i) const
Return the number of keys.
Definition: TBtree.cxx:1567
friend class TBtInnerNode
Definition: TBtree.h:41
TObject * Before(const TObject *obj) const
May not use this method since B-tree decides order.
Definition: TBtree.cxx:237
Bool_t IsReading() const
Definition: TBuffer.h:81
void BalanceWithLeft(TBtLeafNode *l, Int_t idx)
THIS has more than LEFTSIB; move some items from THIS to LEFTSIB.
Definition: TBtree.cxx:1452
void InformParent()
Tell the parent that we are full.
Definition: TBtree.cxx:958
const TBtree * fTree
Definition: TBtree.h:340
static long int sum(long int i)
Definition: Factory.cxx:2162
Int_t IsFull() const
Definition: TBtree.h:253
Int_t fLeafMaxIndex
Definition: TBtree.h:53
TBtItem * fItem
Definition: TBtree.h:189
void ShiftLeft(Int_t cnt)
Shift.
Definition: TBtree.cxx:1679
Int_t GetNofKeys(Int_t i) const
Definition: TBtree.h:389
TObject * GetKey(Int_t i) const
Definition: TBtree.h:221
Int_t DecNofKeys(Int_t i, Int_t n=1)
Definition: TBtree.h:410
void AppendFrom(TBtInnerNode *src, Int_t start, Int_t stop)
This should never create a full node that is, it is not used anywhere where THIS could possibly be ne...
Definition: TBtree.cxx:777
Leaf node of a TBtree.
Definition: TBtree.h:270
void Fatal(const char *location, const char *msgfmt,...)
~TBtItem()
Delete a tree item.
Definition: TBtree.cxx:530
Int_t fLeafLowWaterMark
Definition: TBtree.h:51
void SetNofKeys(Int_t i, Int_t r)
Definition: TBtree.h:400
virtual TBtree * GetParentTree() const
Definition: TBtree.h:134
const char Option_t
Definition: RtypesCore.h:62
TBtInnerNode(TBtInnerNode *parent, TBtree *t=0)
Create a B-tree innernode.
Definition: TBtree.cxx:688
Int_t fInnerMaxIndex
Definition: TBtree.h:52
Int_t Rank(const TObject *obj) const
Returns the rank of the object in the tree.
Definition: TBtree.cxx:393
TObject * FindObject(const char *name) const
Find object using its name (see object&#39;s GetName()).
Definition: TBtree.cxx:275
Int_t MaxPsize() const
Definition: TBtree.h:249
Int_t NofKeys() const
Return the number of keys.
Definition: TBtree.cxx:1575
Bool_t IsArgNull(const char *where, const TObject *obj) const
Returns true if object is a null pointer.
void RemoveItem(Int_t idx)
Definition: TBtree.h:284
void Add(TObject *obj)
Add object to B-tree.
Definition: TBtree.cxx:200
Int_t Psize() const
Definition: TBtree.h:312
virtual ~TBtree()
Delete B-tree.
Definition: TBtree.cxx:189
Abstract base class (ABC) of a TBtree node.
Definition: TBtree.h:112
Buffer base class used for serializing objects.
Definition: TBuffer.h:40
TBtLeafNode * FirstLeafNode()
Return the first node.
Definition: TBtree.cxx:1501
TBtree * fTree
Definition: TBtree.h:125
#define R__ASSERT(e)
Definition: TError.h:96
void RootIsEmpty()
If root is empty clean up its space.
Definition: TBtree.cxx:441
Int_t NofKeys() const
Number of key.
Definition: TBtree.cxx:1136
virtual Int_t CheckByteCount(UInt_t startpos, UInt_t bcnt, const TClass *clss)=0
int Int_t
Definition: RtypesCore.h:41
bool Bool_t
Definition: RtypesCore.h:59
void Clear(Option_t *option="")
Remove all objects from B-tree.
Definition: TBtree.cxx:247
virtual TObject * Found(const TObject *obj, TBtNode **which, Int_t *where)=0
void DecrNofKeys()
Definition: TBtree.h:61
virtual UInt_t WriteVersion(const TClass *cl, Bool_t useBcnt=kFALSE)=0
virtual ~TBtNode()
Delete a B-tree node.
Definition: TBtree.cxx:564
TBtNode * fRoot
Definition: TBtree.h:45
void BalanceWithRight(TBtInnerNode *r, Int_t idx)
THIS has more than RIGHTSIB.
Definition: TBtree.cxx:826
Int_t IdxAdd(const TObject &obj)
Add object and return its index in the tree.
Definition: TBtree.cxx:301
TObject * operator[](Int_t i) const
return an element.
Definition: TBtree.cxx:1147
TObject * operator*() const
Return current object or nullptr.
Definition: TBtree.cxx:675
Int_t FindRankUp(const TBtNode *n) const
FindRankUp is FindRank in reverse.
Definition: TBtree.cxx:890
Iterator abstract base class.
Definition: TIterator.h:30
void AddElt(TBtItem &itm, Int_t at)
Add one element.
Definition: TBtree.cxx:735
virtual void Add(const TObject *obj, Int_t index)=0
void PushLeft(Int_t cnt, TBtInnerNode *leftsib, Int_t parentIdx)
noFromThis==1 => moves the parent item into the leftsib, and the first item in this&#39;s array into the ...
Definition: TBtree.cxx:1170
Bool_t fDirection
Definition: TBtree.h:343
TObject * Next()
Get next object from B-tree. Returns 0 when no more objects in tree.
Definition: TBtree.cxx:639
#define SafeDelete(p)
Definition: RConfig.h:499
void SetTree(Int_t i, TBtNode *node)
Definition: TBtree.h:210
Int_t IsFull() const
Definition: TBtree.h:319
Int_t fCursor
Definition: TBtree.h:342
void Remove(Int_t idx)
Remove an element.
Definition: TBtree.cxx:1656
void Class()
Definition: Class.C:29
void MergeWithRight(TBtLeafNode *r, Int_t idx)
Merge.
Definition: TBtree.cxx:1554
#define R__CHECK(e)
Definition: TError.h:100
void Reset()
Reset the B-tree iterator.
Definition: TBtree.cxx:626
TObject * Found(const TObject *obj, TBtNode **which, Int_t *where)
Recursively look for WHAT starting in the current node.
Definition: TBtree.cxx:910
Item stored in inner nodes of a TBtree.
Definition: TBtree.h:161
TBtLeafNode * LastLeafNode()
Return the last leaf node.
Definition: TBtree.cxx:1113
TIterator & operator=(const TIterator &rhs)
Overridden assignment operator.
Definition: TBtree.cxx:597
const Bool_t kIterForward
Definition: TCollection.h:37
void MayNotUse(const char *method) const
Use this method to signal that a method (defined in a base class) may not be called in a derived clas...
Definition: TObject.cxx:926
TBtNode(Int_t isleaf, TBtInnerNode *p, TBtree *t=0)
Create a B-tree node.
Definition: TBtree.cxx:541
Bool_t IsOwner() const
Definition: TCollection.h:95
void BalanceWith(TBtLeafNode *n, Int_t idx)
PITEM is the parent item whose key will change when keys are shifted from one LeafNode to the other...
Definition: TBtree.cxx:1475
Int_t FindRank(const TObject *obj) const
WHAT was not in any inner node; it is either here, or it&#39;s not in the tree.
Definition: TBtree.cxx:1487
Int_t MaxIndex() const
Definition: TBtree.h:314
TBtItem & GetItem(Int_t i) const
Definition: TBtree.h:222
void Error(const char *location, const char *msgfmt,...)
TBtNode * fTree
Definition: TBtree.h:168
TBtLeafNode * LastLeafNode()
return the last node.
Definition: TBtree.cxx:1546
Int_t fNofKeysInTree
Definition: TBtree.h:166
void MergeWithRight(TBtInnerNode *r, Int_t idx)
Merge the 2 part of the tree.
Definition: TBtree.cxx:1121
Int_t fOrder2
Definition: TBtree.h:48
Int_t fOrder
Definition: TBtree.h:47
TIterator * MakeIterator(Bool_t dir=kIterForward) const
Returns a B-tree iterator.
Definition: TBtree.cxx:385
Int_t Vsize() const
Definition: TBtree.h:430
friend class TBtLeafNode
Definition: TBtree.h:42
Int_t MaxPsize() const
Definition: TBtree.h:315
virtual TBtLeafNode * LastLeafNode()=0
void Split()
This function is called only when THIS is the only descendent of the root node, and THIS needs to be ...
Definition: TBtree.cxx:1277
TRandom2 r(17)
Int_t fCurCursor
Definition: TBtree.h:341
virtual Bool_t IsSortable() const
Definition: TObject.h:120
void PushRight(Int_t cnt, TBtLeafNode *r, Int_t parentIndex)
noFromThis==1 => moves the parent item into the rightsib, and the last item in this&#39;s array into the ...
Definition: TBtree.cxx:1612
virtual void Split()=0
void PushLeft(Int_t cnt, TBtLeafNode *l, Int_t parentIndex)
noFromThis==1 => moves the parent item into the leftsib, and the first item in this&#39;s array into the ...
Definition: TBtree.cxx:1593
Int_t fIsLeaf
Definition: TBtree.h:126
void Append(TObject *obj, TBtNode *n)
Never called from anywhere where it might fill up THIS.
Definition: TBtree.cxx:791
void AppendFrom(TBtLeafNode *src, Int_t start, Int_t stop)
A convenience function, does not worry about the element in the parent, simply moves elements from SR...
Definition: TBtree.cxx:1426
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 IsLow() const
Definition: TBtree.h:256
unsigned int UInt_t
Definition: RtypesCore.h:42
void DecrNofKeys(TBtNode *np)
THAT is a child of THIS that has just shrunk by 1.
Definition: TBtree.cxx:850
virtual void Error(const char *method, const char *msgfmt,...) const
Issue error message.
Definition: TObject.cxx:873
void RootIsFull()
The root of the tree is full.
Definition: TBtree.cxx:430
Int_t fLast
Definition: TBtree.h:119
TLine * l
Definition: textangle.C:4
Int_t fSize
Definition: TCollection.h:57
void Append(TObject *obj)
Never called from anywhere where it might fill up THIS does NOT handle nofKeys.
Definition: TBtree.cxx:1442
void IncrNofKeys(TBtNode *np)
THAT is a child of THIS that has just grown by 1.
Definition: TBtree.cxx:932
virtual void SetByteCount(UInt_t cntpos, Bool_t packInVersion=kFALSE)=0
virtual Int_t Compare(const TObject *obj) const
Compare abstract method.
Definition: TObject.cxx:166
TObject * At(Int_t idx) const
Definition: TBtree.h:372
TObject * After(const TObject *obj) const
Cannot use this method since B-tree decides order.
Definition: TBtree.cxx:228
void Init(Int_t i)
Initialize a B-tree.
Definition: TBtree.cxx:344
void Reset(Detail::TBranchProxy *x)
void Remove(Int_t idx)
Remove an element.
Definition: TBtree.cxx:1233
virtual void Remove(Int_t index)=0
Int_t Psize() const
Definition: TBtree.h:246
virtual Int_t FindRank(const TObject *obj) const =0
Int_t IsAlmostFull() const
Definition: TBtree.h:320
~TBtLeafNode()
Destructor.
Definition: TBtree.cxx:1376
~TBtInnerNode()
Constructor.
Definition: TBtree.cxx:712
static void GarbageCollect(TObject *obj)
Add to the list of things to be cleaned up.
Iterator of btree.
Definition: TBtree.h:334
Int_t IndexOf(const TBtNode *n) const
Returns a number in the range 0 to this->fLast 0 is returned if THAT == fTree[0]. ...
Definition: TBtree.cxx:946
Int_t IndexOf(const TObject *obj) const
Returns a number in the range 0 to MaxIndex().
Definition: TBtree.cxx:1533
Bool_t IsOnHeap() const
Definition: TObject.h:121
#define ClassImp(name)
Definition: Rtypes.h:336
void SplitWith(TBtLeafNode *r, Int_t idx)
Split.
Definition: TBtree.cxx:1706
TBtreeIter()
Definition: TBtree.h:345
TObject * Remove(TObject *obj)
Remove an object from the tree.
Definition: TBtree.cxx:408
Int_t IncNofKeys(Int_t i, Int_t n=1)
Definition: TBtree.h:405
Int_t IsAlmostFull() const
Definition: TBtree.h:255
void IncrNofKeys()
Definition: TBtree.h:60
void SetKey(Int_t i, TObject *obj)
Definition: TBtree.h:211
void Delete(Option_t *option="")
Remove all objects from B-tree AND delete all heap based objects.
Definition: TBtree.cxx:260
void BalanceWithLeft(TBtInnerNode *l, Int_t idx)
THIS has more than LEFTSIB.
Definition: TBtree.cxx:812
Int_t FindRank(const TObject *obj) const
Recursively look for WHAT starting in the current node.
Definition: TBtree.cxx:863
void PushRight(Int_t cnt, TBtInnerNode *rightsib, Int_t parentIdx)
The operation is three steps:
Definition: TBtree.cxx:1189
Mother of all ROOT objects.
Definition: TObject.h:37
void RemoveItem(Int_t idx)
Remove an item.
Definition: TBtree.cxx:1244
Int_t Vsize() const
Definition: TBtree.h:415
TObject * Found(const TObject *obj, TBtNode **which, Int_t *where)
WHAT was not in any inner node; it is either here, or it&#39;s not in the tree.
Definition: TBtree.cxx:1510
TBtLeafNode * FirstLeafNode()
Return the first leaf node.
Definition: TBtree.cxx:902
void ShiftLeft(Int_t cnt)
Shift to the left.
Definition: TBtree.cxx:1263
Int_t Compare(const void *item1, const void *item2)
Bool_t operator!=(const TIterator &aIter) const
This operator compares two TIterator objects.
Definition: TBtree.cxx:655
you should not use this method at all Int_t Int_t Double_t Double_t Double_t Int_t Double_t Double_t Double_t Double_t b
Definition: TRolke.cxx:630
virtual TObject * FindObject(const char *name) const
Find an object in this collection using its name.
Definition: tree.py:1
Int_t NofKeys(Int_t idx) const
Definition: TBtree.h:395
Int_t MaxIndex() const
Definition: TBtree.h:248
void SplitWith(TBtInnerNode *r, Int_t idx)
THIS and SIB are too full; create a NEWNODE, and balance the number of keys between the three of them...
Definition: TBtree.cxx:1316
virtual Int_t GetSize() const
Definition: TCollection.h:89
virtual TBtLeafNode * FirstLeafNode()=0
Inner node of a TBtree.
Definition: TBtree.h:186
void Split()
This function is called only when THIS is the only descendent of the root node, and THIS needs to be ...
Definition: TBtree.cxx:1693
virtual Int_t NofKeys() const =0
const Bool_t kTRUE
Definition: RtypesCore.h:91
TBtNode * GetTree(Int_t i) const
Definition: TBtree.h:220
TObject ** fItem
Definition: TBtree.h:275
Int_t fInnerLowWaterMark
Definition: TBtree.h:50
const Int_t n
Definition: legend1.C:16
B-tree class.
Definition: TBtree.h:38
const char * cnt
Definition: TXMLSetup.cxx:75
virtual void Warning(const char *method, const char *msgfmt,...) const
Issue warning message.
Definition: TObject.cxx:859
virtual Version_t ReadVersion(UInt_t *start=0, UInt_t *bcnt=0, const TClass *cl=0)=0
TBtInnerNode * fParent
Definition: TBtree.h:124
void Add(const TObject *obj, Int_t idx)
This is called only from TBtree::Add().
Definition: TBtree.cxx:725
Int_t IsLow() const
Definition: TBtree.h:321
void Add(const TObject *obj, Int_t idx)
Add the object OBJ to the leaf node, inserting it at location INDEX in the fItem array.
Definition: TBtree.cxx:1385
void BalanceWith(TBtInnerNode *n, int idx)
PINDX is the index of the parent item whose key will change when keys are shifted from one InnerNode ...
Definition: TBtree.cxx:839
TBtItem()
sub-tree
Definition: TBtree.cxx:496