Public Member Functions | |
TBtInnerNode (TBtInnerNode *parent, TBtree *t=nullptr) | |
Create a B-tree innernode. | |
TBtInnerNode (TBtInnerNode *parent, TBtree *tree, TBtNode *oldroot) | |
Called only by TBtree to initialize the TBtInnerNode that is about to become the root. | |
~TBtInnerNode () | |
Constructor. | |
void | Add (const TObject *obj, Int_t idx) override |
This is called only from TBtree::Add(). | |
void | Add (Int_t at, TObject *obj, TBtNode *n) |
Add one element. | |
void | Add (TBtItem &i, Int_t idx) |
Add one element. | |
void | AddElt (Int_t at, TObject *obj, TBtNode *n) |
Add one element. | |
void | AddElt (TBtItem &itm, Int_t at) |
Add one element. | |
void | Append (TBtItem &itm) |
Append itm to this tree. | |
void | Append (TObject *obj, TBtNode *n) |
Never called from anywhere where it might fill up THIS. | |
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 near full. | |
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 to the other. | |
void | BalanceWithLeft (TBtInnerNode *l, Int_t idx) |
THIS has more than LEFTSIB. | |
void | BalanceWithRight (TBtInnerNode *r, Int_t idx) |
THIS has more than RIGHTSIB. | |
Int_t | DecNofKeys (Int_t i, Int_t n=1) |
void | DecrNofKeys (TBtNode *np) |
THAT is a child of THIS that has just shrunk by 1. | |
Int_t | FindRank (const TObject *obj) const override |
Recursively look for WHAT starting in the current node. | |
Int_t | FindRankUp (const TBtNode *n) const |
FindRankUp is FindRank in reverse. | |
TBtLeafNode * | FirstLeafNode () override |
Return the first leaf node. | |
TObject * | Found (const TObject *obj, TBtNode **which, Int_t *where) override |
Recursively look for WHAT starting in the current node. | |
TBtItem & | GetItem (Int_t i) const |
TObject * | GetKey (Int_t i) const |
Int_t | GetNofKeys (Int_t i) const |
TBtNode * | GetTree (Int_t i) const |
Int_t | IncNofKeys (Int_t i, Int_t n=1) |
void | IncrNofKeys (TBtNode *np) |
THAT is a child of THIS that has just grown by 1. | |
Int_t | IndexOf (const TBtNode *n) const |
Returns a number in the range 0 to this->fLast 0 is returned if THAT == fTree[0]. | |
void | InformParent () |
Tell the parent that we are full. | |
Int_t | IsAlmostFull () const |
Int_t | IsFull () const |
void | IsFull (TBtNode *n) |
The child node THAT is full. | |
Int_t | IsLow () const |
void | IsLow (TBtNode *n) |
The child node THAT is <= half full. | |
TBtLeafNode * | LastLeafNode () override |
Return the last leaf node. | |
Int_t | MaxIndex () const |
Int_t | MaxPsize () const |
void | MergeWithRight (TBtInnerNode *r, Int_t idx) |
Merge the 2 part of the tree. | |
Int_t | NofKeys () const override |
Number of key. | |
Int_t | NofKeys (Int_t idx) const |
TObject * | operator[] (Int_t i) const override |
return an element. | |
Int_t | Psize () const |
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 parent item. | |
void | PushRight (Int_t cnt, TBtInnerNode *rightsib, Int_t parentIdx) |
The operation is three steps: | |
void | Remove (Int_t idx) override |
Remove an element. | |
void | RemoveItem (Int_t idx) |
Remove an item. | |
void | SetItem (Int_t i, TBtItem &itm) |
void | SetItem (Int_t i, TObject *obj, TBtNode *node) |
void | SetKey (Int_t i, TObject *obj) |
void | SetNofKeys (Int_t i, Int_t r) |
void | SetTree (Int_t i, TBtNode *node) |
void | ShiftLeft (Int_t cnt) |
Shift to the left. | |
void | Split () override |
This function is called only when THIS is the only descendent of the root node, and THIS needs to be split. | |
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. | |
Int_t | Vsize () const |
![]() | |
TBtNode (Int_t isleaf, TBtInnerNode *p, TBtree *t=nullptr) | |
Create a B-tree node. | |
virtual | ~TBtNode () |
Delete a B-tree node. | |
virtual TBtree * | GetParentTree () const |
Private Attributes | |
TBtItem * | fItem |
Additional Inherited Members | |
![]() | |
Int_t | fIsLeaf |
Int_t | fLast |
TBtInnerNode * | fParent |
TBtree * | fTree |
#include <TBtree.h>
TBtInnerNode::TBtInnerNode | ( | TBtInnerNode * | parent, |
TBtree * | t = nullptr ) |
Create a B-tree innernode.
Definition at line 686 of file TBtree.cxx.
TBtInnerNode::TBtInnerNode | ( | TBtInnerNode * | parent, |
TBtree * | tree, | ||
TBtNode * | oldroot ) |
Called only by TBtree to initialize the TBtInnerNode that is about to become the root.
Definition at line 698 of file TBtree.cxx.
TBtInnerNode::~TBtInnerNode | ( | ) |
Constructor.
Definition at line 710 of file TBtree.cxx.
This is called only from TBtree::Add().
Implements TBtNode.
Definition at line 723 of file TBtree.cxx.
Add one element.
Definition at line 765 of file TBtree.cxx.
Add one element.
Definition at line 755 of file TBtree.cxx.
Add one element.
Definition at line 746 of file TBtree.cxx.
Add one element.
Definition at line 733 of file TBtree.cxx.
void TBtInnerNode::Append | ( | TBtItem & | itm | ) |
Append itm to this tree.
Definition at line 799 of file TBtree.cxx.
Never called from anywhere where it might fill up THIS.
Definition at line 789 of file TBtree.cxx.
void TBtInnerNode::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 near full.
Definition at line 775 of file TBtree.cxx.
void TBtInnerNode::BalanceWith | ( | TBtInnerNode * | n, |
int | idx ) |
PINDX is the index of the parent item whose key will change when keys are shifted from one InnerNode to the other.
Definition at line 837 of file TBtree.cxx.
void TBtInnerNode::BalanceWithLeft | ( | TBtInnerNode * | leftsib, |
Int_t | pidx ) |
THIS has more than LEFTSIB.
Move some item from THIS to LEFTSIB. PIDX is the index of the parent item that will change when keys are moved.
Definition at line 810 of file TBtree.cxx.
void TBtInnerNode::BalanceWithRight | ( | TBtInnerNode * | rightsib, |
Int_t | pidx ) |
THIS has more than RIGHTSIB.
Move some items from THIS to RIGHTSIB. PIDX is the index of the parent item that will change when keys are moved.
Definition at line 824 of file TBtree.cxx.
void TBtInnerNode::DecrNofKeys | ( | TBtNode * | np | ) |
THAT is a child of THIS that has just shrunk by 1.
Definition at line 848 of file TBtree.cxx.
Recursively look for WHAT starting in the current node.
Implements TBtNode.
Definition at line 861 of file TBtree.cxx.
FindRankUp is FindRank in reverse.
Whereas FindRank looks for the object and computes the rank along the way while walking DOWN the tree, FindRankUp already knows where the object is and has to walk UP the tree from the object to compute the rank.
Definition at line 888 of file TBtree.cxx.
|
overridevirtual |
|
overridevirtual |
Recursively look for WHAT starting in the current node.
Implements TBtNode.
Definition at line 908 of file TBtree.cxx.
void TBtInnerNode::IncrNofKeys | ( | TBtNode * | np | ) |
THAT is a child of THIS that has just grown by 1.
Definition at line 930 of file TBtree.cxx.
Returns a number in the range 0 to this->fLast 0 is returned if THAT == fTree[0].
Definition at line 944 of file TBtree.cxx.
void TBtInnerNode::InformParent | ( | ) |
Tell the parent that we are full.
Definition at line 956 of file TBtree.cxx.
void TBtInnerNode::IsFull | ( | TBtNode * | that | ) |
The child node THAT is full.
We will either redistribute elements or create a new node and then redistribute. In an attempt to minimize the number of splits, we adopt the following strategy:
Definition at line 975 of file TBtree.cxx.
void TBtInnerNode::IsLow | ( | TBtNode * | that | ) |
The child node THAT is <= half full.
We will either redistribute elements between children, or THAT will be merged with another child. In an attempt to minimize the number of mergers, we adopt the following strategy:
Definition at line 1054 of file TBtree.cxx.
|
overridevirtual |
void TBtInnerNode::MergeWithRight | ( | TBtInnerNode * | r, |
Int_t | idx ) |
Merge the 2 part of the tree.
Definition at line 1119 of file TBtree.cxx.
|
overridevirtual |
void TBtInnerNode::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 parent item.
Definition at line 1168 of file TBtree.cxx.
void TBtInnerNode::PushRight | ( | Int_t | noFromThis, |
TBtInnerNode * | rightsib, | ||
Int_t | pidx ) |
The operation is three steps:
Definition at line 1187 of file TBtree.cxx.
|
overridevirtual |
void TBtInnerNode::RemoveItem | ( | Int_t | idx | ) |
Remove an item.
Definition at line 1242 of file TBtree.cxx.
void TBtInnerNode::ShiftLeft | ( | Int_t | cnt | ) |
Shift to the left.
Definition at line 1261 of file TBtree.cxx.
|
overridevirtual |
This function is called only when THIS is the only descendent of the root node, and THIS needs to be split.
Assumes that idx of THIS in fParent is 0.
Implements TBtNode.
Definition at line 1275 of file TBtree.cxx.
void TBtInnerNode::SplitWith | ( | TBtInnerNode * | rightsib, |
Int_t | keyidx ) |
THIS and SIB are too full; create a NEWNODE, and balance the number of keys between the three of them.
picture: (also see Knuth Vol 3 pg 478)
keyidx is the index of where the sibling is, and where the newly created node will be recorded (sibling will be moved to keyidx+1)
Definition at line 1314 of file TBtree.cxx.