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