Logo ROOT  
Reference Guide
 
Loading...
Searching...
No Matches
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(nullptr, obj, this);
209 R__CHECK(fRoot != nullptr);
210 IncrNofKeys();
211 } else {
212 TBtNode *loc;
213 Int_t idx;
214 if (fRoot->Found(obj, &loc, &idx)) {
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 nullptr;
232}
233
234////////////////////////////////////////////////////////////////////////////////
235/// May not use this method since B-tree decides order.
236
238{
239 MayNotUse("Before");
240 return nullptr;
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 nullptr;
288 }
289 if (!fRoot)
290 return nullptr;
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(nullptr, &obj, this);
310 R__ASSERT(fRoot != nullptr);
311 IncrNofKeys();
312 r = 0;
313 } else {
314 TBtNode *loc;
315 int idx;
316 if (fRoot->Found(&obj, &loc, &idx)) {
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)
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 = nullptr;
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 nullptr;
413 }
414 if (!fRoot)
415 return nullptr;
416
417 TBtNode *loc;
418 Int_t idx;
419 TObject *ob = fRoot->Found(obj, &loc, &idx);
420 if (!ob)
421 return nullptr;
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(nullptr, this, oldroot);
434 R__ASSERT(fRoot != nullptr);
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 = nullptr;
448 } else {
450 R__CHECK(iroot->Psize() == 0);
451 fRoot = iroot->GetTree(0);
452 fRoot->fParent = nullptr;
453 delete iroot;
454 }
455}
456
457////////////////////////////////////////////////////////////////////////////////
458/// Stream all objects in the btree to or from the I/O buffer.
459
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;
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;
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 = nullptr;
500 fKey = nullptr;
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) {
547 R__CHECK(t != nullptr);
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 nullptr;
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)
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)
705 ::Fatal("TBtInnerNode::TBtInnerNode", "no more memory");
706 Append(nullptr, 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
726{
727 R__ASSERT(index >= 1 && obj->IsSortable());
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)
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 : 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)
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) {
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 = nullptr;
982 TBtLeafNode *right= nullptr;
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)) != nullptr);
987 Int_t hasLeftSib = (leafidx > 0) &&
988 ((left = (TBtLeafNode*)GetTree(leafidx-1)) != nullptr);
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 = nullptr;
1020 TBtInnerNode *right = nullptr;
1021 Int_t hasRightSib = (inneridx < fLast) &&
1022 ((right = (TBtInnerNode*)GetTree(inneridx+1)) != nullptr);
1023 Int_t hasLeftSib = (inneridx > 0) &&
1024 ((left=(TBtInnerNode*)GetTree(inneridx-1)) != nullptr);
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 = nullptr;
1061 TBtLeafNode *right = nullptr;
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)) != nullptr);
1066 Int_t hasLeftSib = (leafidx > 0) &&
1067 ((left = (TBtLeafNode*)GetTree(leafidx-1)) != nullptr);
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 = nullptr;
1089 TBtInnerNode *right = nullptr;
1090 Int_t hasRightSib = (inneridx < fLast) &&
1091 ((right = (TBtInnerNode*)GetTree(inneridx+1)) != nullptr);
1092 Int_t hasLeftSib = (inneridx > 0) &&
1093 ((left = (TBtInnerNode*)GetTree(inneridx-1)) != nullptr);
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 nullptr;
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 nullptr;
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);
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) {
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 != nullptr);
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 != nullptr);
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 != nullptr);
1369 if (obj)
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
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)
1397 fTree->IncrNofKeys();
1398 else
1399 fParent->IncrNofKeys(this);
1400
1401 if (IsFull()) {
1402 // it's full; tell parent node
1403 if (!fParent) {
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 nullptr;
1523 }
1524 }
1525 *which = this;
1526 *where = fLast+1;
1527 return nullptr;
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)
1663 fTree->DecrNofKeys();
1664 else
1665 fParent->DecrNofKeys(this);
1666 if (IsLow()) {
1667 if (!fParent) {
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 != nullptr);
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 != nullptr);
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}
#define SafeDelete(p)
Definition RConfig.hxx:540
#define d(i)
Definition RSha256.hxx:102
#define b(i)
Definition RSha256.hxx:100
constexpr Bool_t kTRUE
Definition RtypesCore.h:100
const char Option_t
Definition RtypesCore.h:66
#define ClassImp(name)
Definition Rtypes.h:377
const Bool_t kIterForward
Definition TCollection.h:42
#define R__ASSERT(e)
Definition TError.h:117
void Error(const char *location, const char *msgfmt,...)
Use this function in case an error occurred.
Definition TError.cxx:197
void Fatal(const char *location, const char *msgfmt,...)
Use this function in case of a fatal error. It will abort the program.
Definition TError.cxx:256
#define R__CHECK(e)
Definition TError.h:121
Int_t Compare(const void *item1, const void *item2)
winID h TVirtualViewer3D TVirtualGLPainter p
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void char Point_t Rectangle_t WindowAttributes_t Float_t r
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void char Point_t Rectangle_t WindowAttributes_t index
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void char Point_t Rectangle_t src
char name[80]
Definition TGX11.cxx:110
Inner node of a TBtree.
Definition TBtree.h:186
Int_t DecNofKeys(Int_t i, Int_t n=1)
Definition TBtree.h:413
void InformParent()
Tell the parent that we are full.
Definition TBtree.cxx:958
void ShiftLeft(Int_t cnt)
Shift to the left.
Definition TBtree.cxx:1263
Int_t NofKeys() const override
Number of key.
Definition TBtree.cxx:1136
void BalanceWithLeft(TBtInnerNode *l, Int_t idx)
THIS has more than LEFTSIB.
Definition TBtree.cxx:812
Int_t IncNofKeys(Int_t i, Int_t n=1)
Definition TBtree.h:408
void BalanceWithRight(TBtInnerNode *r, Int_t idx)
THIS has more than RIGHTSIB.
Definition TBtree.cxx:826
Int_t FindRankUp(const TBtNode *n) const
FindRankUp is FindRank in reverse.
Definition TBtree.cxx:890
void AppendFrom(TBtInnerNode *src, Int_t start, Int_t stop)
This should never create a full node that is, it is not used anywhere where THIS could possibly be ne...
Definition TBtree.cxx:777
void Append(TObject *obj, TBtNode *n)
Never called from anywhere where it might fill up THIS.
Definition TBtree.cxx:791
Int_t IsFull() const
Definition TBtree.h:253
TBtItem & GetItem(Int_t i) const
Definition TBtree.h:222
void SetKey(Int_t i, TObject *obj)
Definition TBtree.h:211
Int_t GetNofKeys(Int_t i) const
Definition TBtree.h:392
void AddElt(TBtItem &itm, Int_t at)
Add one element.
Definition TBtree.cxx:735
Int_t MaxIndex() const
Definition TBtree.h:248
Int_t Vsize() const
Definition TBtree.h:418
Int_t IndexOf(const TBtNode *n) const
Returns a number in the range 0 to this->fLast 0 is returned if THAT == fTree[0].
Definition TBtree.cxx:946
Int_t FindRank(const TObject *obj) const override
Recursively look for WHAT starting in the current node.
Definition TBtree.cxx:863
void Add(const TObject *obj, Int_t idx) override
This is called only from TBtree::Add().
Definition TBtree.cxx:725
void MergeWithRight(TBtInnerNode *r, Int_t idx)
Merge the 2 part of the tree.
Definition TBtree.cxx:1121
Int_t IsAlmostFull() const
Definition TBtree.h:255
void SetItem(Int_t i, TBtItem &itm)
Definition TBtree.h:212
void SetNofKeys(Int_t i, Int_t r)
Definition TBtree.h:403
Int_t MaxPsize() const
Definition TBtree.h:249
void SetTree(Int_t i, TBtNode *node)
Definition TBtree.h:210
void PushLeft(Int_t cnt, TBtInnerNode *leftsib, Int_t parentIdx)
noFromThis==1 => moves the parent item into the leftsib, and the first item in this's array into the ...
Definition TBtree.cxx:1170
void IncrNofKeys(TBtNode *np)
THAT is a child of THIS that has just grown by 1.
Definition TBtree.cxx:932
TObject * GetKey(Int_t i) const
Definition TBtree.h:221
void DecrNofKeys(TBtNode *np)
THAT is a child of THIS that has just shrunk by 1.
Definition TBtree.cxx:850
void Remove(Int_t idx) override
Remove an element.
Definition TBtree.cxx:1233
~TBtInnerNode()
Constructor.
Definition TBtree.cxx:712
void BalanceWith(TBtInnerNode *n, int idx)
PINDX is the index of the parent item whose key will change when keys are shifted from one InnerNode ...
Definition TBtree.cxx:839
void Split() override
This function is called only when THIS is the only descendent of the root node, and THIS needs to be ...
Definition TBtree.cxx:1277
void PushRight(Int_t cnt, TBtInnerNode *rightsib, Int_t parentIdx)
The operation is three steps:
Definition TBtree.cxx:1189
TObject * operator[](Int_t i) const override
return an element.
Definition TBtree.cxx:1147
TBtNode * GetTree(Int_t i) const
Definition TBtree.h:220
void SplitWith(TBtInnerNode *r, Int_t idx)
THIS and SIB are too full; create a NEWNODE, and balance the number of keys between the three of them...
Definition TBtree.cxx:1316
void RemoveItem(Int_t idx)
Remove an item.
Definition TBtree.cxx:1244
TBtItem * fItem
Definition TBtree.h:189
TBtLeafNode * FirstLeafNode() override
Return the first leaf node.
Definition TBtree.cxx:902
Int_t NofKeys(Int_t idx) const
Definition TBtree.h:398
TObject * Found(const TObject *obj, TBtNode **which, Int_t *where) override
Recursively look for WHAT starting in the current node.
Definition TBtree.cxx:910
Int_t IsLow() const
Definition TBtree.h:256
TBtLeafNode * LastLeafNode() override
Return the last leaf node.
Definition TBtree.cxx:1113
Int_t Psize() const
Definition TBtree.h:246
Item stored in inner nodes of a TBtree.
Definition TBtree.h:161
TBtItem()
sub-tree
Definition TBtree.cxx:496
~TBtItem()
Delete a tree item.
Definition TBtree.cxx:530
TObject * fKey
Definition TBtree.h:167
Int_t fNofKeysInTree
Definition TBtree.h:166
TBtNode * fTree
Definition TBtree.h:168
Leaf node of a TBtree.
Definition TBtree.h:270
void BalanceWith(TBtLeafNode *n, Int_t idx)
PITEM is the parent item whose key will change when keys are shifted from one LeafNode to the other.
Definition TBtree.cxx:1475
void BalanceWithRight(TBtLeafNode *r, Int_t idx)
THIS has more than RIGHTSIB; move some items from THIS to RIGHTSIB.
Definition TBtree.cxx:1463
Int_t Vsize() const
Definition TBtree.h:433
void Split() override
This function is called only when THIS is the only descendent of the root node, and THIS needs to be ...
Definition TBtree.cxx:1693
Int_t IsAlmostFull() const
Definition TBtree.h:320
void RemoveItem(Int_t idx)
Definition TBtree.h:284
Int_t Psize() const
Definition TBtree.h:312
TObject ** fItem
Definition TBtree.h:275
void ShiftLeft(Int_t cnt)
Shift.
Definition TBtree.cxx:1679
void PushRight(Int_t cnt, TBtLeafNode *r, Int_t parentIndex)
noFromThis==1 => moves the parent item into the rightsib, and the last item in this's array into the ...
Definition TBtree.cxx:1612
Int_t MaxPsize() const
Definition TBtree.h:315
void SplitWith(TBtLeafNode *r, Int_t idx)
Split.
Definition TBtree.cxx:1706
TObject * Found(const TObject *obj, TBtNode **which, Int_t *where) override
WHAT was not in any inner node; it is either here, or it's not in the tree.
Definition TBtree.cxx:1510
TBtLeafNode * FirstLeafNode() override
Return the first node.
Definition TBtree.cxx:1501
void Remove(Int_t idx) override
Remove an element.
Definition TBtree.cxx:1656
void BalanceWithLeft(TBtLeafNode *l, Int_t idx)
THIS has more than LEFTSIB; move some items from THIS to LEFTSIB.
Definition TBtree.cxx:1452
void PushLeft(Int_t cnt, TBtLeafNode *l, Int_t parentIndex)
noFromThis==1 => moves the parent item into the leftsib, and the first item in this's array into the ...
Definition TBtree.cxx:1593
void Add(const TObject *obj, Int_t idx) override
Add the object OBJ to the leaf node, inserting it at location INDEX in the fItem array.
Definition TBtree.cxx:1385
void MergeWithRight(TBtLeafNode *r, Int_t idx)
Merge.
Definition TBtree.cxx:1554
~TBtLeafNode()
Destructor.
Definition TBtree.cxx:1376
Int_t NofKeys() const override
Return the number of keys.
Definition TBtree.cxx:1575
Int_t MaxIndex() const
Definition TBtree.h:314
Int_t NofKeys(Int_t i) const
Return the number of keys.
Definition TBtree.cxx:1567
TBtLeafNode * LastLeafNode() override
return the last node.
Definition TBtree.cxx:1546
Int_t IsLow() const
Definition TBtree.h:321
void Append(TObject *obj)
Never called from anywhere where it might fill up THIS does NOT handle nofKeys.
Definition TBtree.cxx:1442
Int_t IsFull() const
Definition TBtree.h:319
Int_t FindRank(const TObject *obj) const override
WHAT was not in any inner node; it is either here, or it's not in the tree.
Definition TBtree.cxx:1487
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
TBtNode(Int_t isleaf, TBtInnerNode *p, TBtree *t=nullptr)
Create a B-tree node.
Definition TBtree.cxx:541
TBtInnerNode * fParent
Definition TBtree.h:124
friend class TBtInnerNode
Definition TBtree.h:115
virtual void Split()=0
TBtree * fTree
Definition TBtree.h:125
Int_t fIsLeaf
Definition TBtree.h:126
Int_t fLast
Definition TBtree.h:119
virtual void Remove(Int_t index)=0
virtual TBtLeafNode * FirstLeafNode()=0
virtual TObject * Found(const TObject *obj, TBtNode **which, Int_t *where)=0
Iterator of btree.
Definition TBtree.h:334
const TBtree * fTree
Definition TBtree.h:337
TBtreeIter()
Definition TBtree.h:342
Int_t fCurCursor
Definition TBtree.h:338
Bool_t operator!=(const TIterator &aIter) const override
This operator compares two TIterator objects.
Definition TBtree.cxx:655
static TClass * Class()
TIterator & operator=(const TIterator &rhs) override
Overridden assignment operator.
Definition TBtree.cxx:597
Bool_t fDirection
Definition TBtree.h:340
TObject * Next() override
Get next object from B-tree. Returns 0 when no more objects in tree.
Definition TBtree.cxx:639
void Reset() override
Reset the B-tree iterator.
Definition TBtree.cxx:626
Int_t fCursor
Definition TBtree.h:339
TObject * operator*() const override
Return current object or nullptr.
Definition TBtree.cxx:675
B-tree class.
Definition TBtree.h:38
Int_t fOrder
Definition TBtree.h:47
Int_t fInnerMaxIndex
Definition TBtree.h:52
Int_t IdxAdd(const TObject &obj)
Add object and return its index in the tree.
Definition TBtree.cxx:301
Int_t Rank(const TObject *obj) const
Returns the rank of the object in the tree.
Definition TBtree.cxx:393
TClass * IsA() const override
Definition TBtree.h:100
void Delete(Option_t *option="") override
Remove all objects from B-tree AND delete all heap based objects.
Definition TBtree.cxx:260
virtual ~TBtree()
Delete B-tree.
Definition TBtree.cxx:189
void Init(Int_t i)
Initialize a B-tree.
Definition TBtree.cxx:344
void DecrNofKeys()
Definition TBtree.h:61
friend class TBtLeafNode
Definition TBtree.h:42
TBtNode * fRoot
Definition TBtree.h:45
Int_t fLeafLowWaterMark
Definition TBtree.h:51
Int_t fLeafMaxIndex
Definition TBtree.h:53
TObject * Before(const TObject *obj) const override
May not use this method since B-tree decides order.
Definition TBtree.cxx:237
friend class TBtInnerNode
Definition TBtree.h:41
TObject * Remove(TObject *obj) override
Remove an object from the tree.
Definition TBtree.cxx:408
void RootIsFull()
The root of the tree is full.
Definition TBtree.cxx:430
TBtree(Int_t ordern=3)
Create a B-tree of certain order (by default 3).
Definition TBtree.cxx:180
void Add(TObject *obj) override
Add object to B-tree.
Definition TBtree.cxx:200
void Clear(Option_t *option="") override
Remove all objects from B-tree.
Definition TBtree.cxx:247
void Streamer(TBuffer &) override
Stream all objects in the btree to or from the I/O buffer.
Definition TBtree.cxx:460
TObject * After(const TObject *obj) const override
Cannot use this method since B-tree decides order.
Definition TBtree.cxx:228
Int_t fOrder2
Definition TBtree.h:48
TIterator * MakeIterator(Bool_t dir=kIterForward) const override
Returns a B-tree iterator.
Definition TBtree.cxx:385
void RootIsEmpty()
If root is empty clean up its space.
Definition TBtree.cxx:441
Int_t fInnerLowWaterMark
Definition TBtree.h:50
TObject * At(Int_t idx) const override
Definition TBtree.h:375
TObject * FindObject(const char *name) const override
Find object using its name (see object's GetName()).
Definition TBtree.cxx:275
void IncrNofKeys()
Definition TBtree.h:60
Buffer base class used for serializing objects.
Definition TBuffer.h:43
Bool_t IsArgNull(const char *where, const TObject *obj) const
Returns true if object is a null pointer.
Bool_t IsOwner() const
TObject * FindObject(const char *name) const override
Find an object in this collection using its name.
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.
Iterator abstract base class.
Definition TIterator.h:30
virtual TClass * IsA() const
Definition TIterator.h:48
Mother of all ROOT objects.
Definition TObject.h:41
virtual Bool_t IsSortable() const
Definition TObject.h:150
R__ALWAYS_INLINE Bool_t IsOnHeap() const
Definition TObject.h:152
virtual void Warning(const char *method, const char *msgfmt,...) const
Issue warning message.
Definition TObject.cxx:956
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:1023
virtual void Error(const char *method, const char *msgfmt,...) const
Issue error message.
Definition TObject.cxx:970
void Streamer(TBuffer &) override
Stream all objects in the collection to or from the I/O buffer.
const Int_t n
Definition legend1.C:16
Definition tree.py:1
static const char * what
Definition stlLoader.cc:6
TLine l
Definition textangle.C:4
static uint64_t sum(uint64_t i)
Definition Factory.cxx:2345