Logo ROOT  
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
14B-tree class. TBtree inherits from the TSeqCollection ABC.
15
16## B-tree Implementation notes
17
18This implements B-trees with several refinements. Most of them can be found
19in Knuth Vol 3, but some were developed to adapt to restrictions imposed
20by C++. First, a restatement of Knuth's properties that a B-tree must
21satisfy, assuming we make the enhancement he suggests in the paragraph
22at the bottom of page 476. Instead of storing null pointers to non-existent
23nodes (which Knuth calls the leaves) we utilize the space to store keys.
24Therefore, what Knuth calls level (l-1) is the bottom of our tree, and
25we call the nodes at this level LeafNodes. Other nodes are called InnerNodes.
26The other enhancement we have adopted is in the paragraph at the bottom of
27page 477: overflow control.
28
29The 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
45The values of InnerLowWaterMark and LeafLowWaterMark may actually be set
46by the user when the tree is initialized, but currently they are set
47automatically to:
48~~~ {.cpp}
49 InnerLowWaterMark = ceiling(Order/2)
50 LeafLowWaterMark = Order - 1
51~~~
52If the tree is only filled, then all the nodes will be at least 2/3 full.
53They will almost all be exactly 2/3 full if the elements are added to the
54tree in order (either increasing or decreasing). [Knuth says McCreight's
55experiments showed almost 100% memory utilization. I don't see how that
56can be given the algorithms that Knuth gives. McCreight must have used
57a different scheme for balancing. [No, he used a different scheme for
58splitting: he did a two-way split instead of the three way split as we do
59here. Which means that McCreight does better on insertion of ordered data,
60but we should do better on insertion of random data.]]
61
62It must also be noted that B-trees were designed for DISK access algorithms,
63not necessarily in-memory sorting, as we intend it to be used here. However,
64if the order is kept small (< 6?) any inefficiency is negligible for
65in-memory sorting. Knuth points out that balanced trees are actually
66preferable for memory sorting. I'm not sure that I believe this, but
67it's interesting. Also, deleting elements from balanced binary trees, being
68beyond the scope of Knuth's book (p. 465), is beyond my scope. B-trees
69are good enough.
70
71A B-tree is declared to be of a certain ORDER (3 by default). This number
72determines the number of keys contained in any interior node of the tree.
73Each interior node will contain ORDER keys, and therefore ORDER+1 pointers
74to sub-trees. The keys are numbered and indexed 1 to ORDER while the
75pointers are numbered and indexed 0 to ORDER. The 0th ptr points to the
76sub-tree of all elements that are less than key[1]. Ptr[1] points to the
77sub-tree that contains all the elements greater than key[1] and less than
78key[2]. etc. The array of pointers and keys is allocated as ORDER+1
79pairs of keys and nodes, meaning that one key field (key[0]) is not used
80and therefore wasted. Given that the number of interior nodes is
81small, that this waste allows fewer cases of special code, and that it
82is useful in certain of the methods, it was felt to be a worthwhile waste.
83
84The size of the exterior nodes (leaf nodes) does not need to be related to
85the size of the interior nodes at all. Since leaf nodes contain only
86keys, they may be as large or small as we like independent of the size
87of the interior nodes. For no particular reason other than it seems like
88a good idea, we will allocate 2*(ORDER+1) keys in each leaf node, and they
89will be numbered and indexed from 0 to 2*ORDER+1. It does have the advantage
90of keeping the size of the leaf and interior arrays the same, so that if we
91find allocation and de-allocation of these arrays expensive, we can modify
92their allocation to use a garbage ring, or something.
93
94Both 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"
96is the order of the tree, and the inclusive upper limit on the indices of
97the keys in the interior nodes. The variable "order2" is the inclusive
98upper 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~~~
107Currently, 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~~~
127It is conceptually VERY convenient to think of the data as being the
128very first element of the sib node. Any primitive that tells sib to
129perform some action on n nodes should include this 'hidden' element.
130For InnerNodes, the hidden element has (physical) index 0 in the array,
131and in LeafNodes, the hidden element has (virtual) index -1 in the array.
132Therefore, there are two 'size' primitives for nodes:
133~~~ {.cpp}
134Psize - the physical size: how many elements are contained in the
135 array in the node.
136Vsize - 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~~~
141Parent nodes are always InnerNodes.
142
143These are the primitive operations on Nodes:
144~~~ {.cpp}
145Append(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.
148Split() - divide a node in two, and create two new nodes.
149SplitWith(sib) - create a third node between this node and the sib node,
150 divvying up the elements of their arrays.
151PushLeft(n) - move n elements into the left sibling
152PushRight(n) - move n elements into the right sibling
153BalanceWithRight() - even up the number of elements in the two nodes.
154BalanceWithLeft() - ditto
155~~~
156To allow this implementation of btrees to also be an implementation of
157sorted arrays/lists, the overhead is included to allow O(log n) access
158of elements by their rank (`give me the 5th largest element').
159Therefore, each Item keeps track of the number of keys in and below it
160in the tree (remember, each item's tree is all keys to the RIGHT of the
161item'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
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();
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 {
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 }
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
275TObject *TBtree::FindObject(const char *name) const
276{
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
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
393Int_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 {
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
460void 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;
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;
479 b << fInnerMaxIndex;
480 b << fLeafMaxIndex;
481 TSeqCollection::Streamer(b);
482 b.SetByteCount(R__c, kTRUE);
483 }
484}
485
486
487/** \class TBtItem
488Item 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
535Abstract 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;
619 }
620 return *this;
621}
622
623////////////////////////////////////////////////////////////////////////////////
624/// Reset the B-tree iterator.
625
627{
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
725void 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);
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{
794 if (d) R__ASSERT(d->IsSortable());
795 SetItem(++fLast, d, n);
796}
797
798////////////////////////////////////////////////////////////////////////////////
799/// Append itm to this tree.
800
802{
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);
854 if (fParent != 0)
855 fParent->DecrNofKeys(this);
856 else
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
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);
936 if (fParent != 0)
937 fParent->IncrNofKeys(this);
938 else
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
1170void 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
1189void 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())
1354}
1355
1356/** \class TBtLeafNode
1357Leaf 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
1385void 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
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
1593void 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
1612void 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())
1727}
void Class()
Definition: Class.C:29
ROOT::R::TRInterface & r
Definition: Object.C:4
#define SafeDelete(p)
Definition: RConfig.hxx:543
#define d(i)
Definition: RSha256.hxx:102
#define b(i)
Definition: RSha256.hxx:100
unsigned int UInt_t
Definition: RtypesCore.h:44
const Bool_t kTRUE
Definition: RtypesCore.h:89
const char Option_t
Definition: RtypesCore.h:64
#define ClassImp(name)
Definition: Rtypes.h:361
const Bool_t kIterForward
Definition: TCollection.h:40
#define R__ASSERT(e)
Definition: TError.h:96
void Error(const char *location, const char *msgfmt,...)
void Fatal(const char *location, const char *msgfmt,...)
#define R__CHECK(e)
Definition: TError.h:100
Int_t Compare(const void *item1, const void *item2)
char name[80]
Definition: TGX11.cxx:109
Inner node of a TBtree.
Definition: TBtree.h:186
Int_t DecNofKeys(Int_t i, Int_t n=1)
Definition: TBtree.h:410
void InformParent()
Tell the parent that we are full.
Definition: TBtree.cxx:958
void ShiftLeft(Int_t cnt)
Shift to the left.
Definition: TBtree.cxx:1263
TBtLeafNode * LastLeafNode()
Return the last leaf node.
Definition: TBtree.cxx:1113
void BalanceWithLeft(TBtInnerNode *l, Int_t idx)
THIS has more than LEFTSIB.
Definition: TBtree.cxx:812
Int_t IncNofKeys(Int_t i, Int_t n=1)
Definition: TBtree.h:405
void BalanceWithRight(TBtInnerNode *r, Int_t idx)
THIS has more than RIGHTSIB.
Definition: TBtree.cxx:826
Int_t FindRankUp(const TBtNode *n) const
FindRankUp is FindRank in reverse.
Definition: TBtree.cxx:890
void AppendFrom(TBtInnerNode *src, Int_t start, Int_t stop)
This should never create a full node that is, it is not used anywhere where THIS could possibly be ne...
Definition: TBtree.cxx:777
void Append(TObject *obj, TBtNode *n)
Never called from anywhere where it might fill up THIS.
Definition: TBtree.cxx:791
void Add(const TObject *obj, Int_t idx)
This is called only from TBtree::Add().
Definition: TBtree.cxx:725
Int_t IsFull() const
Definition: TBtree.h:253
TBtItem & GetItem(Int_t i) const
Definition: TBtree.h:222
void SetKey(Int_t i, TObject *obj)
Definition: TBtree.h:211
Int_t GetNofKeys(Int_t i) const
Definition: TBtree.h:389
void AddElt(TBtItem &itm, Int_t at)
Add one element.
Definition: TBtree.cxx:735
Int_t MaxIndex() const
Definition: TBtree.h:248
Int_t Vsize() const
Definition: TBtree.h:415
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
void MergeWithRight(TBtInnerNode *r, Int_t idx)
Merge the 2 part of the tree.
Definition: TBtree.cxx:1121
TBtLeafNode * FirstLeafNode()
Return the first leaf node.
Definition: TBtree.cxx:902
Int_t IsAlmostFull() const
Definition: TBtree.h:255
void SetItem(Int_t i, TBtItem &itm)
Definition: TBtree.h:212
void SetNofKeys(Int_t i, Int_t r)
Definition: TBtree.h:400
TObject * operator[](Int_t i) const
return an element.
Definition: TBtree.cxx:1147
Int_t MaxPsize() const
Definition: TBtree.h:249
void SetTree(Int_t i, TBtNode *node)
Definition: TBtree.h:210
Int_t FindRank(const TObject *obj) const
Recursively look for WHAT starting in the current node.
Definition: TBtree.cxx:863
void Remove(Int_t idx)
Remove an element.
Definition: TBtree.cxx:1233
Int_t NofKeys() const
Number of key.
Definition: TBtree.cxx:1136
void PushLeft(Int_t cnt, TBtInnerNode *leftsib, Int_t parentIdx)
noFromThis==1 => moves the parent item into the leftsib, and the first item in this's array into the ...
Definition: TBtree.cxx:1170
void IncrNofKeys(TBtNode *np)
THAT is a child of THIS that has just grown by 1.
Definition: TBtree.cxx:932
TObject * GetKey(Int_t i) const
Definition: TBtree.h:221
void DecrNofKeys(TBtNode *np)
THAT is a child of THIS that has just shrunk by 1.
Definition: TBtree.cxx:850
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
~TBtInnerNode()
Constructor.
Definition: TBtree.cxx:712
void BalanceWith(TBtInnerNode *n, int idx)
PINDX is the index of the parent item whose key will change when keys are shifted from one InnerNode ...
Definition: TBtree.cxx:839
void PushRight(Int_t cnt, TBtInnerNode *rightsib, Int_t parentIdx)
The operation is three steps:
Definition: TBtree.cxx:1189
TBtNode * GetTree(Int_t i) const
Definition: TBtree.h:220
void SplitWith(TBtInnerNode *r, Int_t idx)
THIS and SIB are too full; create a NEWNODE, and balance the number of keys between the three of them...
Definition: TBtree.cxx:1316
TObject * Found(const TObject *obj, TBtNode **which, Int_t *where)
Recursively look for WHAT starting in the current node.
Definition: TBtree.cxx:910
void RemoveItem(Int_t idx)
Remove an item.
Definition: TBtree.cxx:1244
TBtItem * fItem
Definition: TBtree.h:189
Int_t NofKeys(Int_t idx) const
Definition: TBtree.h:395
Int_t IsLow() const
Definition: TBtree.h:256
Int_t Psize() const
Definition: TBtree.h:246
Item stored in inner nodes of a TBtree.
Definition: TBtree.h:161
TBtItem()
sub-tree
Definition: TBtree.cxx:496
~TBtItem()
Delete a tree item.
Definition: TBtree.cxx:530
TObject * fKey
Definition: TBtree.h:167
Int_t fNofKeysInTree
Definition: TBtree.h:166
TBtNode * fTree
Definition: TBtree.h:168
Leaf node of a TBtree.
Definition: TBtree.h:270
void BalanceWith(TBtLeafNode *n, Int_t idx)
PITEM is the parent item whose key will change when keys are shifted from one LeafNode to the other.
Definition: TBtree.cxx:1475
void BalanceWithRight(TBtLeafNode *r, Int_t idx)
THIS has more than RIGHTSIB; move some items from THIS to RIGHTSIB.
Definition: TBtree.cxx:1463
Int_t Vsize() const
Definition: TBtree.h:430
Int_t IsAlmostFull() const
Definition: TBtree.h:320
void RemoveItem(Int_t idx)
Definition: TBtree.h:284
Int_t Psize() const
Definition: TBtree.h:312
Int_t NofKeys() const
Return the number of keys.
Definition: TBtree.cxx:1575
TObject ** fItem
Definition: TBtree.h:275
void ShiftLeft(Int_t cnt)
Shift.
Definition: TBtree.cxx:1679
void PushRight(Int_t cnt, TBtLeafNode *r, Int_t parentIndex)
noFromThis==1 => moves the parent item into the rightsib, and the last item in this's array into the ...
Definition: TBtree.cxx:1612
Int_t MaxPsize() const
Definition: TBtree.h:315
void SplitWith(TBtLeafNode *r, Int_t idx)
Split.
Definition: TBtree.cxx:1706
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 BalanceWithLeft(TBtLeafNode *l, Int_t idx)
THIS has more than LEFTSIB; move some items from THIS to LEFTSIB.
Definition: TBtree.cxx:1452
void PushLeft(Int_t cnt, TBtLeafNode *l, Int_t parentIndex)
noFromThis==1 => moves the parent item into the leftsib, and the first item in this's array into the ...
Definition: TBtree.cxx:1593
Int_t FindRank(const TObject *obj) const
WHAT was not in any inner node; it is either here, or it's not in the tree.
Definition: TBtree.cxx:1487
TBtLeafNode * LastLeafNode()
return the last node.
Definition: TBtree.cxx:1546
void MergeWithRight(TBtLeafNode *r, Int_t idx)
Merge.
Definition: TBtree.cxx:1554
~TBtLeafNode()
Destructor.
Definition: TBtree.cxx:1376
TObject * Found(const TObject *obj, TBtNode **which, Int_t *where)
WHAT was not in any inner node; it is either here, or it's not in the tree.
Definition: TBtree.cxx:1510
Int_t MaxIndex() const
Definition: TBtree.h:314
TBtLeafNode * FirstLeafNode()
Return the first node.
Definition: TBtree.cxx:1501
Int_t NofKeys(Int_t i) const
Return the number of keys.
Definition: TBtree.cxx:1567
void Remove(Int_t idx)
Remove an element.
Definition: TBtree.cxx:1656
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
Int_t IsLow() const
Definition: TBtree.h:321
void Append(TObject *obj)
Never called from anywhere where it might fill up THIS does NOT handle nofKeys.
Definition: TBtree.cxx:1442
Int_t IsFull() const
Definition: TBtree.h:319
Int_t IndexOf(const TObject *obj) const
Returns a number in the range 0 to MaxIndex().
Definition: TBtree.cxx:1533
void AppendFrom(TBtLeafNode *src, Int_t start, Int_t stop)
A convenience function, does not worry about the element in the parent, simply moves elements from SR...
Definition: TBtree.cxx:1426
Abstract base class (ABC) of a TBtree node.
Definition: TBtree.h:112
virtual void Add(const TObject *obj, Int_t index)=0
virtual TBtLeafNode * LastLeafNode()=0
virtual Int_t FindRank(const TObject *obj) const =0
virtual ~TBtNode()
Delete a B-tree node.
Definition: TBtree.cxx:564
virtual Int_t NofKeys() const =0
friend class TBtLeafNode
Definition: TBtree.h:116
TBtInnerNode * fParent
Definition: TBtree.h:124
friend class TBtInnerNode
Definition: TBtree.h:115
TBtNode(Int_t isleaf, TBtInnerNode *p, TBtree *t=0)
Create a B-tree node.
Definition: TBtree.cxx:541
virtual void Split()=0
TBtree * fTree
Definition: TBtree.h:125
Int_t fIsLeaf
Definition: TBtree.h:126
Int_t fLast
Definition: TBtree.h:119
virtual TBtree * GetParentTree() const
Definition: TBtree.h:134
virtual void Remove(Int_t index)=0
virtual TBtLeafNode * FirstLeafNode()=0
virtual TObject * Found(const TObject *obj, TBtNode **which, Int_t *where)=0
Iterator of btree.
Definition: TBtree.h:337
const TBtree * fTree
Definition: TBtree.h:340
TBtreeIter()
Definition: TBtree.h:345
void Reset()
Reset the B-tree iterator.
Definition: TBtree.cxx:626
Int_t fCurCursor
Definition: TBtree.h:341
Bool_t operator!=(const TIterator &aIter) const
This operator compares two TIterator objects.
Definition: TBtree.cxx:655
TObject * operator*() const
Return current object or nullptr.
Definition: TBtree.cxx:675
TObject * Next()
Get next object from B-tree. Returns 0 when no more objects in tree.
Definition: TBtree.cxx:639
Bool_t fDirection
Definition: TBtree.h:343
TIterator & operator=(const TIterator &rhs)
Overridden assignment operator.
Definition: TBtree.cxx:597
Int_t fCursor
Definition: TBtree.h:342
B-tree class.
Definition: TBtree.h:38
Int_t fOrder
Definition: TBtree.h:47
void Add(TObject *obj)
Add object to B-tree.
Definition: TBtree.cxx:200
Int_t fInnerMaxIndex
Definition: TBtree.h:52
Int_t IdxAdd(const TObject &obj)
Add object and return its index in the tree.
Definition: TBtree.cxx:301
Int_t Rank(const TObject *obj) const
Returns the rank of the object in the tree.
Definition: TBtree.cxx:393
void Delete(Option_t *option="")
Remove all objects from B-tree AND delete all heap based objects.
Definition: TBtree.cxx:260
virtual ~TBtree()
Delete B-tree.
Definition: TBtree.cxx:189
void Init(Int_t i)
Initialize a B-tree.
Definition: TBtree.cxx:344
void DecrNofKeys()
Definition: TBtree.h:61
friend class TBtLeafNode
Definition: TBtree.h:42
TBtNode * fRoot
Definition: TBtree.h:45
Int_t fLeafLowWaterMark
Definition: TBtree.h:51
TObject * Before(const TObject *obj) const
May not use this method since B-tree decides order.
Definition: TBtree.cxx:237
void Clear(Option_t *option="")
Remove all objects from B-tree.
Definition: TBtree.cxx:247
TIterator * MakeIterator(Bool_t dir=kIterForward) const
Returns a B-tree iterator.
Definition: TBtree.cxx:385
Int_t fLeafMaxIndex
Definition: TBtree.h:53
friend class TBtInnerNode
Definition: TBtree.h:41
void RootIsFull()
The root of the tree is full.
Definition: TBtree.cxx:430
TBtree(Int_t ordern=3)
Create a B-tree of certain order (by default 3).
Definition: TBtree.cxx:180
TObject * Remove(TObject *obj)
Remove an object from the tree.
Definition: TBtree.cxx:408
TObject * After(const TObject *obj) const
Cannot use this method since B-tree decides order.
Definition: TBtree.cxx:228
Int_t fOrder2
Definition: TBtree.h:48
TObject * At(Int_t idx) const
Definition: TBtree.h:372
TObject * FindObject(const char *name) const
Find object using its name (see object's GetName()).
Definition: TBtree.cxx:275
void RootIsEmpty()
If root is empty clean up its space.
Definition: TBtree.cxx:441
Int_t fInnerLowWaterMark
Definition: TBtree.h:50
void IncrNofKeys()
Definition: TBtree.h:60
Buffer base class used for serializing objects.
Definition: TBuffer.h:42
virtual TObject * FindObject(const char *name) const
Find an object in this collection using its name.
Bool_t IsArgNull(const char *where, const TObject *obj) const
Returns true if object is a null pointer.
Bool_t IsOwner() const
Definition: TCollection.h:188
static void GarbageCollect(TObject *obj)
Add to the list of things to be cleaned up.
virtual Int_t GetSize() const
Return the capacity of the collection, i.e.
Definition: TCollection.h:182
Iterator abstract base class.
Definition: TIterator.h:30
Mother of all ROOT objects.
Definition: TObject.h:37
virtual Bool_t IsSortable() const
Definition: TObject.h:146
R__ALWAYS_INLINE Bool_t IsOnHeap() const
Definition: TObject.h:148
virtual void Warning(const char *method, const char *msgfmt,...) const
Issue warning message.
Definition: TObject.cxx:877
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:944
virtual void Error(const char *method, const char *msgfmt,...) const
Issue error message.
Definition: TObject.cxx:891
const Int_t n
Definition: legend1.C:16
Definition: tree.py:1
const char * cnt
Definition: TXMLSetup.cxx:74
static const char * what
Definition: stlLoader.cc:6
auto * l
Definition: textangle.C:4
static long int sum(long int i)
Definition: Factory.cxx:2275