ROOT  6.07/01
Reference Guide
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Groups Pages
List of all members | Public Member Functions | Private Attributes | List of all members
TBtInnerNode Class Reference

Inner node of a TBtree.

Definition at line 190 of file TBtree.h.

Public Member Functions

 TBtInnerNode (TBtInnerNode *parent, TBtree *t=0)
 Create a B-tree innernode. More...
 
 TBtInnerNode (TBtInnerNode *parent, TBtree *tree, TBtNode *oldroot)
 Called only by TBtree to initialize the TBtInnerNode that is about to become the root. More...
 
 ~TBtInnerNode ()
 Constructor. More...
 
void Add (const TObject *obj, Int_t idx)
 This is called only from TBtree::Add(). More...
 
void Add (TBtItem &i, Int_t idx)
 Add one element. More...
 
void Add (Int_t at, TObject *obj, TBtNode *n)
 Add one element. More...
 
void AddElt (TBtItem &itm, Int_t at)
 Add one element. More...
 
void AddElt (Int_t at, TObject *obj, TBtNode *n)
 Add one element. More...
 
void Remove (Int_t idx)
 Remove an element. More...
 
void RemoveItem (Int_t idx)
 Remove an item. More...
 
TObjectoperator[] (Int_t i) const
 return an element. More...
 
TObjectFound (const TObject *obj, TBtNode **which, Int_t *where)
 Recursively look for WHAT starting in the current node. More...
 
Int_t NofKeys (Int_t idx) const
 
Int_t NofKeys () const
 Number of key. More...
 
void SetTree (Int_t i, TBtNode *node)
 
void SetKey (Int_t i, TObject *obj)
 
void SetItem (Int_t i, TBtItem &itm)
 
void SetItem (Int_t i, TObject *obj, TBtNode *node)
 
Int_t GetNofKeys (Int_t i) const
 
void SetNofKeys (Int_t i, Int_t r)
 
Int_t IncNofKeys (Int_t i, Int_t n=1)
 
Int_t DecNofKeys (Int_t i, Int_t n=1)
 
Int_t FindRank (const TObject *obj) const
 Recursively look for WHAT starting in the current node. More...
 
Int_t FindRankUp (const TBtNode *n) const
 FindRankUp is FindRank in reverse. More...
 
TBtNodeGetTree (Int_t i) const
 
TObjectGetKey (Int_t i) const
 
TBtItemGetItem (Int_t i) const
 
Int_t IndexOf (const TBtNode *n) const
 Returns a number in the range 0 to this->fLast 0 is returned if THAT == fTree[0]. More...
 
void IncrNofKeys (TBtNode *np)
 THAT is a child of THIS that has just grown by 1. More...
 
void DecrNofKeys (TBtNode *np)
 THAT is a child of THIS that has just shrunk by 1. More...
 
TBtLeafNodeFirstLeafNode ()
 Return the first leaf node. More...
 
TBtLeafNodeLastLeafNode ()
 Return the last leaf node. More...
 
void InformParent ()
 Tell the parent that we are full. More...
 
void Split ()
 This function is called only when THIS is the only descendent of the root node, and THIS needs to be split. More...
 
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. More...
 
void MergeWithRight (TBtInnerNode *r, Int_t idx)
 Merge the 2 part of the tree. More...
 
void BalanceWithLeft (TBtInnerNode *l, Int_t idx)
 THIS has more than LEFTSIB. More...
 
void BalanceWithRight (TBtInnerNode *r, Int_t idx)
 THIS has more than RIGHTSIB. More...
 
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. More...
 
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. More...
 
void PushRight (Int_t cnt, TBtInnerNode *rightsib, Int_t parentIdx)
 The operation is three steps: More...
 
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. More...
 
void Append (TObject *obj, TBtNode *n)
 Never called from anywhere where it might fill up THIS. More...
 
void Append (TBtItem &itm)
 Append itm to this tree. More...
 
void ShiftLeft (Int_t cnt)
 Shift to the left. More...
 
Int_t Psize () const
 
Int_t Vsize () const
 
Int_t MaxIndex () const
 
Int_t MaxPsize () const
 
Int_t IsFull () const
 
void IsFull (TBtNode *n)
 The child node THAT is full. More...
 
Int_t IsAlmostFull () const
 
Int_t IsLow () const
 
void IsLow (TBtNode *n)
 The child node THAT is <= half full. More...
 
- Public Member Functions inherited from TBtNode
 TBtNode (Int_t isleaf, TBtInnerNode *p, TBtree *t=0)
 Create a B-tree node. More...
 
virtual ~TBtNode ()
 Delete a B-tree node. More...
 
virtual TBtreeGetParentTree () const
 

Private Attributes

TBtItemfItem
 

Additional Inherited Members

- Protected Attributes inherited from TBtNode
Int_t fLast
 
TBtInnerNodefParent
 
TBtreefTree
 
Int_t fIsLeaf
 

#include <TBtree.h>

Inheritance diagram for TBtInnerNode:
[legend]

Constructor & Destructor Documentation

TBtInnerNode::TBtInnerNode ( TBtInnerNode parent,
TBtree t = 0 
)

Create a B-tree innernode.

Definition at line 687 of file TBtree.cxx.

Referenced by Split(), and SplitWith().

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 699 of file TBtree.cxx.

TBtInnerNode::~TBtInnerNode ( )

Constructor.

Definition at line 711 of file TBtree.cxx.

Member Function Documentation

void TBtInnerNode::Add ( const TObject obj,
Int_t  idx 
)
virtual

This is called only from TBtree::Add().

Implements TBtNode.

Definition at line 724 of file TBtree.cxx.

Referenced by Add().

void TBtInnerNode::Add ( TBtItem i,
Int_t  idx 
)

Add one element.

Definition at line 756 of file TBtree.cxx.

void TBtInnerNode::Add ( Int_t  at,
TObject obj,
TBtNode n 
)

Add one element.

Definition at line 766 of file TBtree.cxx.

void TBtInnerNode::AddElt ( TBtItem itm,
Int_t  at 
)

Add one element.

Definition at line 734 of file TBtree.cxx.

Referenced by Add(), AddElt(), SplitWith(), and TBtLeafNode::SplitWith().

void TBtInnerNode::AddElt ( Int_t  at,
TObject obj,
TBtNode n 
)

Add one element.

Definition at line 747 of file TBtree.cxx.

void TBtInnerNode::Append ( TObject obj,
TBtNode n 
)

Never called from anywhere where it might fill up THIS.

Definition at line 790 of file TBtree.cxx.

Referenced by Split(), TBtLeafNode::Split(), SplitWith(), and TBtInnerNode().

void TBtInnerNode::Append ( TBtItem itm)

Append itm to this tree.

Definition at line 800 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 776 of file TBtree.cxx.

Referenced by MergeWithRight(), PushLeft(), and Split().

void TBtInnerNode::BalanceWith ( TBtInnerNode rightsib,
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 838 of file TBtree.cxx.

Referenced by IsLow().

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 811 of file TBtree.cxx.

Referenced by BalanceWith(), and IsFull().

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 825 of file TBtree.cxx.

Referenced by BalanceWith(), IsFull(), and Split().

Int_t TBtInnerNode::DecNofKeys ( Int_t  i,
Int_t  n = 1 
)
inline

Definition at line 414 of file TBtree.h.

Referenced by PushRight(), Split(), and TBtLeafNode::SplitWith().

void TBtInnerNode::DecrNofKeys ( TBtNode np)

THAT is a child of THIS that has just shrunk by 1.

Definition at line 849 of file TBtree.cxx.

Referenced by DecrNofKeys(), and TBtLeafNode::Remove().

Int_t TBtInnerNode::FindRank ( const TObject obj) const
virtual

Recursively look for WHAT starting in the current node.

Implements TBtNode.

Definition at line 862 of file TBtree.cxx.

Int_t TBtInnerNode::FindRankUp ( const TBtNode that) const

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 889 of file TBtree.cxx.

Referenced by FindRankUp(), and TBtree::IdxAdd().

TBtLeafNode * TBtInnerNode::FirstLeafNode ( )
virtual

Return the first leaf node.

Implements TBtNode.

Definition at line 901 of file TBtree.cxx.

TObject * TBtInnerNode::Found ( const TObject obj,
TBtNode **  which,
Int_t where 
)
virtual

Recursively look for WHAT starting in the current node.

Implements TBtNode.

Definition at line 909 of file TBtree.cxx.

TBtItem& TBtInnerNode::GetItem ( Int_t  i) const
inline

Definition at line 226 of file TBtree.h.

Referenced by AddElt(), AppendFrom(), PushRight(), ShiftLeft(), and SplitWith().

TObject* TBtInnerNode::GetKey ( Int_t  i) const
inline
Int_t TBtInnerNode::GetNofKeys ( Int_t  i) const
inline

Definition at line 393 of file TBtree.h.

Referenced by FindRank(), FindRankUp(), MergeWithRight(), NofKeys(), operator[](), and Split().

TBtNode* TBtInnerNode::GetTree ( Int_t  i) const
inline
Int_t TBtInnerNode::IncNofKeys ( Int_t  i,
Int_t  n = 1 
)
inline

Definition at line 409 of file TBtree.h.

Referenced by MergeWithRight(), PushRight(), and Split().

void TBtInnerNode::IncrNofKeys ( TBtNode np)

THAT is a child of THIS that has just grown by 1.

Definition at line 931 of file TBtree.cxx.

Referenced by TBtLeafNode::Add(), and IncrNofKeys().

Int_t TBtInnerNode::IndexOf ( const TBtNode that) const

Returns a number in the range 0 to this->fLast 0 is returned if THAT == fTree[0].

Definition at line 945 of file TBtree.cxx.

Referenced by DecrNofKeys(), FindRankUp(), IncrNofKeys(), IsFull(), and IsLow().

void TBtInnerNode::InformParent ( )

Tell the parent that we are full.

Definition at line 957 of file TBtree.cxx.

Referenced by Add(), SplitWith(), and TBtLeafNode::SplitWith().

Int_t TBtInnerNode::IsAlmostFull ( ) const
inline

Definition at line 259 of file TBtree.h.

Referenced by IsFull().

Int_t TBtInnerNode::IsFull ( ) const
inline

Definition at line 257 of file TBtree.h.

Referenced by Add(), TBtLeafNode::Add(), InformParent(), SplitWith(), and TBtLeafNode::SplitWith().

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:

  • redistribute if possible
  • if not possible, then split with a sibling

Definition at line 976 of file TBtree.cxx.

Int_t TBtInnerNode::IsLow ( ) const
inline

Definition at line 260 of file TBtree.h.

Referenced by TBtLeafNode::Remove(), and RemoveItem().

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:

  • redistribute if possible
  • if not possible, then merge with a sibling

Definition at line 1055 of file TBtree.cxx.

TBtLeafNode * TBtInnerNode::LastLeafNode ( )
virtual

Return the last leaf node.

Implements TBtNode.

Definition at line 1112 of file TBtree.cxx.

Int_t TBtInnerNode::MaxIndex ( ) const
inline

Definition at line 252 of file TBtree.h.

Referenced by AddElt(), Append(), AppendFrom(), IsAlmostFull(), IsFull(), MergeWithRight(), and TBtInnerNode().

Int_t TBtInnerNode::MaxPsize ( ) const
inline

Definition at line 253 of file TBtree.h.

Referenced by IsLow(), PushLeft(), and PushRight().

void TBtInnerNode::MergeWithRight ( TBtInnerNode r,
Int_t  idx 
)

Merge the 2 part of the tree.

Definition at line 1120 of file TBtree.cxx.

Referenced by IsLow().

Int_t TBtInnerNode::NofKeys ( Int_t  idx) const
inline

Definition at line 399 of file TBtree.h.

Referenced by PushLeft(), PushRight(), and SplitWith().

Int_t TBtInnerNode::NofKeys ( ) const
virtual

Number of key.

Implements TBtNode.

Definition at line 1135 of file TBtree.cxx.

Referenced by PushLeft(), PushRight(), and SplitWith().

TObject * TBtInnerNode::operator[] ( Int_t  i) const
virtual

return an element.

Implements TBtNode.

Definition at line 1146 of file TBtree.cxx.

Int_t TBtInnerNode::Psize ( ) const
inline
void TBtInnerNode::PushLeft ( Int_t  noFromThis,
TBtInnerNode leftsib,
Int_t  pidx 
)

noFromThis==1 => moves the parent item into the leftsib, and the first item in this's array into the parent item.

Definition at line 1169 of file TBtree.cxx.

Referenced by BalanceWithLeft(), MergeWithRight(), and SplitWith().

void TBtInnerNode::PushRight ( Int_t  noFromThis,
TBtInnerNode rightsib,
Int_t  pidx 
)

The operation is three steps:

  • Step I. Make room for the incoming keys in RIGHTSIB.
  • Step II. Move the items from THIS into RIGHTSIB.
  • Step III. Update the length of THIS.

Definition at line 1188 of file TBtree.cxx.

Referenced by BalanceWithRight(), and SplitWith().

void TBtInnerNode::Remove ( Int_t  idx)
virtual

Remove an element.

Implements TBtNode.

Definition at line 1232 of file TBtree.cxx.

void TBtInnerNode::RemoveItem ( Int_t  idx)

Remove an item.

Definition at line 1243 of file TBtree.cxx.

Referenced by MergeWithRight(), and TBtLeafNode::MergeWithRight().

void TBtInnerNode::SetItem ( Int_t  i,
TBtItem itm 
)
inline

Definition at line 216 of file TBtree.h.

Referenced by AddElt(), Append(), AppendFrom(), and PushRight().

void TBtInnerNode::SetItem ( Int_t  i,
TObject obj,
TBtNode node 
)
inline

Definition at line 217 of file TBtree.h.

void TBtInnerNode::SetKey ( Int_t  i,
TObject obj 
)
inline
void TBtInnerNode::SetNofKeys ( Int_t  i,
Int_t  r 
)
inline
void TBtInnerNode::SetTree ( Int_t  i,
TBtNode node 
)
inline

Definition at line 214 of file TBtree.h.

Referenced by SetItem(), and SplitWith().

void TBtInnerNode::ShiftLeft ( Int_t  cnt)

Shift to the left.

Definition at line 1262 of file TBtree.cxx.

Referenced by PushLeft(), and SplitWith().

void TBtInnerNode::Split ( )
virtual

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 1276 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 keyidx+1
+--+--+--+--+--+--...
| | | | | |
fParent--->| | | |
| | | |
+*-+*-+*-+--+--+--...
| | |
+----+ | +-----+
| +-----+ |
V | V
+----------+ | +----------+
| | | | |
this->| | | | |<--sib
+----------+ | +----------+
V
data

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 1315 of file TBtree.cxx.

Referenced by IsFull().

Int_t TBtInnerNode::Vsize ( ) const
inline

Member Data Documentation

TBtItem* TBtInnerNode::fItem
private
Collaboration diagram for TBtInnerNode:
[legend]

The documentation for this class was generated from the following files: