203 Error(
"Add",
"object must be sortable");
285 Error(
"FindObject",
"object must be sortable");
304 Error(
"IdxAdd",
"object must be sortable");
346 Warning(
"Init",
"order must be at least 3");
395 Error(
"Rank",
"object must be sortable");
410 Error(
"Remove",
"object must be sortable");
470 TSeqCollection::Streamer(b);
480 TSeqCollection::Streamer(b);
509 fNofKeysInTree = n->
NofKeys()+1;
521 fNofKeysInTree = n->
NofKeys()+1;
577 : fTree(t), fCurCursor(0), fCursor(0), fDirection(dir)
642 if (fCursor < fTree->GetSize())
657 const TBtreeIter &iter(dynamic_cast<const TBtreeIter &>(aIter));
676 return (((
fCurCursor >= 0) && (fCurCursor < fTree->GetSize())) ?
692 ::Fatal(
"TBtInnerNode::TBtInnerNode",
"no more memory");
704 ::Fatal(
"TBtInnerNode::TBtInnerNode",
"no more memory");
728 ln->
Add(obj, ln->fLast+1);
781 R__ASSERT(0 <= stop && stop <= src->fLast );
783 for (
Int_t i = start; i <= stop; i++)
817 PushLeft(noFromThis, leftsib, pidx);
893 for (
Int_t i = 0; i <
l; i++)
986 Int_t hasLeftSib = (leafidx > 0) &&
994 }
else if (hasLeftSib) {
1001 }
else if (hasRightSib) {
1004 }
else if (leftSibFull) {
1007 }
else if (hasLeftSib) {
1022 Int_t hasLeftSib = (inneridx > 0) &&
1029 }
else if (hasLeftSib) {
1035 }
else if (hasRightSib) {
1037 }
else if (leftSibFull) {
1039 }
else if (hasLeftSib) {
1065 Int_t hasLeftSib = (leafidx > 0) &&
1075 }
else if (hasLeftSib) {
1078 }
else if (hasRightSib) {
1091 Int_t hasLeftSib = (inneridx > 0) &&
1099 }
else if (hasLeftSib) {
1101 }
else if (hasRightSib) {
1123 if (rightsib->
Psize() > 0)
1140 return sum +
Psize();
1154 ::Error(
"TBtInnerNode::operator[]",
"should not happen, 0 returned");
1161 ::Error(
"TBtInnerNode::operator[]",
"should not happen, 0 returned");
1199 tgt = rightsib->
fLast + noFromThis;
1200 src = rightsib->
fLast;
1201 rightsib->
fLast = tgt;
1222 fLast -= noFromThis;
1321 Int_t newSizeThis = nofKeys / 3;
1322 Int_t newSizeNew = (nofKeys - newSizeThis) / 2;
1323 Int_t newSizeSib = (nofKeys - newSizeThis - newSizeNew);
1325 Int_t noFromSib = rightsib->
Vsize() - newSizeSib;
1334 if (noFromThis > 0) {
1338 this->
PushRight(noFromThis-1, newNode, keyidx);
1339 rightsib->
PushLeft(noFromSib, newNode, keyidx+1);
1346 rightsib->
PushLeft(noFromSib-1, newNode, keyidx+1);
1430 R__ASSERT(0 <= stop && stop <= src->fLast);
1432 for (
Int_t i = start; i <= stop; i++)
1456 PushLeft(noFromThis, leftsib, pidx);
1535 if (
fItem[i] == that)
1627 tgt = rightsib->
fLast + noFromThis;
1628 src = rightsib->
fLast;
1629 rightsib->
fLast = tgt;
1631 rightsib->
fItem[tgt--] = rightsib->
fItem[src--];
1645 fLast -= noFromThis;
1710 Int_t newSizeThis = nofKeys / 3;
1711 Int_t newSizeNew = (nofKeys - newSizeThis) / 2;
1712 Int_t newSizeSib = (nofKeys - newSizeThis - newSizeNew);
1714 Int_t noFromSib = rightsib->
Vsize() - newSizeSib;
1722 this->
PushRight(noFromThis-1, newNode, keyidx);
1723 rightsib->
PushLeft(noFromSib, newNode, keyidx+1);
TBtLeafNode(TBtInnerNode *p, const TObject *obj=0, TBtree *t=0)
Constructor.
Int_t NofKeys(Int_t idx) const
void SetItem(Int_t i, TBtItem &itm)
Int_t NofKeys(Int_t i) const
Return the number of keys.
TObject * At(Int_t idx) const
friend class TBtInnerNode
void BalanceWithLeft(TBtLeafNode *l, Int_t idx)
THIS has more than LEFTSIB; move some items from THIS to LEFTSIB.
void InformParent()
Tell the parent that we are full.
static long int sum(long int i)
Int_t FindRankUp(const TBtNode *n) const
FindRankUp is FindRank in reverse.
void ShiftLeft(Int_t cnt)
Shift.
virtual Int_t FindRank(const TObject *obj) const =0
Int_t DecNofKeys(Int_t i, Int_t n=1)
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...
virtual TObject * FindObject(const char *name) const
Find an object in this collection using its name.
void Fatal(const char *location, const char *msgfmt,...)
~TBtItem()
Delete a tree item.
TIterator * MakeIterator(Bool_t dir=kIterForward) const
Returns a B-tree iterator.
void SetNofKeys(Int_t i, Int_t r)
TBtInnerNode(TBtInnerNode *parent, TBtree *t=0)
Create a B-tree innernode.
Int_t IsAlmostFull() const
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...
void RemoveItem(Int_t idx)
void Add(TObject *obj)
Add object to B-tree.
virtual ~TBtree()
Delete B-tree.
Abstract base class (ABC) of a TBtree node.
Buffer base class used for serializing objects.
TBtLeafNode * FirstLeafNode()
Return the first node.
void RootIsEmpty()
If root is empty clean up its space.
virtual Int_t CheckByteCount(UInt_t startpos, UInt_t bcnt, const TClass *clss)=0
void Clear(Option_t *option="")
Remove all objects from B-tree.
virtual TObject * Found(const TObject *obj, TBtNode **which, Int_t *where)=0
virtual UInt_t WriteVersion(const TClass *cl, Bool_t useBcnt=kFALSE)=0
virtual ~TBtNode()
Delete a B-tree node.
TObject * After(const TObject *obj) const
Cannot use this method since B-tree decides order.
void BalanceWithRight(TBtInnerNode *r, Int_t idx)
THIS has more than RIGHTSIB.
Int_t IdxAdd(const TObject &obj)
Add object and return its index in the tree.
Iterator abstract base class.
void AddElt(TBtItem &itm, Int_t at)
Add one element.
Int_t NofKeys() const
Return the number of keys.
virtual void Add(const TObject *obj, Int_t index)=0
void PushLeft(Int_t cnt, TBtInnerNode *leftsib, Int_t parentIdx)
noFromThis==1 => moves the parent item into the leftsib, and the first item in this's array into the ...
Bool_t IsArgNull(const char *where, const TObject *obj) const
Returns true if object is a null pointer.
Int_t FindRank(const TObject *obj) const
Recursively look for WHAT starting in the current node.
TObject * Next()
Get next object from B-tree. Returns 0 when no more objects in tree.
virtual Int_t NofKeys() const =0
void SetTree(Int_t i, TBtNode *node)
void Remove(Int_t idx)
Remove an element.
void MergeWithRight(TBtLeafNode *r, Int_t idx)
Merge.
void Init(TClassEdit::TInterpreterLookupHelper *helper)
void Reset()
Reset the B-tree iterator.
TObject * Found(const TObject *obj, TBtNode **which, Int_t *where)
Recursively look for WHAT starting in the current node.
Item stored in inner nodes of a TBtree.
TBtLeafNode * LastLeafNode()
Return the last leaf node.
TIterator & operator=(const TIterator &rhs)
Overridden assignment operator.
const Bool_t kIterForward
TBtNode(Int_t isleaf, TBtInnerNode *p, TBtree *t=0)
Create a B-tree node.
virtual void Error(const char *method, const char *msgfmt,...) const
Issue error message.
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...
void Error(const char *location, const char *msgfmt,...)
TBtLeafNode * LastLeafNode()
return the last node.
TBtItem & GetItem(Int_t i) const
virtual Bool_t IsSortable() const
void MergeWithRight(TBtInnerNode *r, Int_t idx)
Merge the 2 part of the tree.
virtual TBtLeafNode * LastLeafNode()=0
void Split()
This function is called only when THIS is the only descendent of the root node, and THIS needs to be ...
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.
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 ...
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 ...
TBtNode * GetTree(Int_t i) const
void Append(TObject *obj, TBtNode *n)
Never called from anywhere where it might fill up THIS.
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...
void BalanceWithRight(TBtLeafNode *r, Int_t idx)
THIS has more than RIGHTSIB; move some items from THIS to RIGHTSIB.
TObject * operator*() const
Return current object or nullptr.
Int_t NofKeys() const
Number of key.
void DecrNofKeys(TBtNode *np)
THAT is a child of THIS that has just shrunk by 1.
void RootIsFull()
The root of the tree is full.
void Append(TObject *obj)
Never called from anywhere where it might fill up THIS does NOT handle nofKeys.
void IncrNofKeys(TBtNode *np)
THAT is a child of THIS that has just grown by 1.
virtual void SetByteCount(UInt_t cntpos, Bool_t packInVersion=kFALSE)=0
void Init(Int_t i)
Initialize a B-tree.
void Reset(Detail::TBranchProxy *x)
void Remove(Int_t idx)
Remove an element.
virtual void Remove(Int_t index)=0
virtual TBtree * GetParentTree() const
Int_t IsAlmostFull() const
TObject * operator[](Int_t i) const
return an element.
TObject * Before(const TObject *obj) const
May not use this method since B-tree decides order.
~TBtLeafNode()
Destructor.
~TBtInnerNode()
Constructor.
static void GarbageCollect(TObject *obj)
Add to the list of things to be cleaned up.
TObject * GetKey(Int_t i) const
Int_t Rank(const TObject *obj) const
Returns the rank of the object in the tree.
virtual Int_t GetSize() const
void SplitWith(TBtLeafNode *r, Int_t idx)
Split.
TObject * Remove(TObject *obj)
Remove an object from the tree.
Int_t IncNofKeys(Int_t i, Int_t n=1)
void SetKey(Int_t i, TObject *obj)
void Delete(Option_t *option="")
Remove all objects from B-tree AND delete all heap based objects.
void BalanceWithLeft(TBtInnerNode *l, Int_t idx)
THIS has more than LEFTSIB.
void PushRight(Int_t cnt, TBtInnerNode *rightsib, Int_t parentIdx)
The operation is three steps:
Bool_t operator!=(const TIterator &aIter) const
This operator compares two TIterator objects.
Mother of all ROOT objects.
void RemoveItem(Int_t idx)
Remove an item.
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.
Int_t IndexOf(const TObject *obj) const
Returns a number in the range 0 to MaxIndex().
TBtLeafNode * FirstLeafNode()
Return the first leaf node.
void ShiftLeft(Int_t cnt)
Shift to the left.
Int_t Compare(const void *item1, const void *item2)
Int_t IndexOf(const TBtNode *n) const
Returns a number in the range 0 to this->fLast 0 is returned if THAT == fTree[0]. ...
you should not use this method at all Int_t Int_t Double_t Double_t Double_t Int_t Double_t Double_t Double_t Double_t b
virtual Int_t Compare(const TObject *obj) const
Compare abstract method.
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...
TObject * FindObject(const char *name) const
Find object using its name (see object's GetName()).
Int_t GetNofKeys(Int_t i) const
virtual TBtLeafNode * FirstLeafNode()=0
void Split()
This function is called only when THIS is the only descendent of the root node, and THIS needs to be ...
virtual Version_t ReadVersion(UInt_t *start=0, UInt_t *bcnt=0, const TClass *cl=0)=0
void Add(const TObject *obj, Int_t idx)
This is called only from TBtree::Add().
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.
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 ...
virtual void Warning(const char *method, const char *msgfmt,...) const
Issue warning message.