Logo ROOT   6.08/07
Reference Guide
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 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 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 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 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...
 
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. More...
 
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...
 
TBtLeafNodeFirstLeafNode ()
 Return the first leaf node. More...
 
TObjectFound (const TObject *obj, TBtNode **which, Int_t *where)
 Recursively look for WHAT starting in the current node. More...
 
TBtItemGetItem (Int_t i) const
 
TObjectGetKey (Int_t i) const
 
Int_t GetNofKeys (Int_t i) const
 
TBtNodeGetTree (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. More...
 
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 InformParent ()
 Tell the parent that we are full. More...
 
Int_t IsAlmostFull () const
 
Int_t IsFull () const
 
void IsFull (TBtNode *n)
 The child node THAT is full. More...
 
Int_t IsLow () const
 
void IsLow (TBtNode *n)
 The child node THAT is <= half full. More...
 
TBtLeafNodeLastLeafNode ()
 Return the last leaf node. More...
 
Int_t MaxIndex () const
 
Int_t MaxPsize () const
 
void MergeWithRight (TBtInnerNode *r, Int_t idx)
 Merge the 2 part of the tree. More...
 
Int_t NofKeys (Int_t idx) const
 
Int_t NofKeys () const
 Number of key. More...
 
TObjectoperator[] (Int_t i) const
 return an element. More...
 
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. More...
 
void PushRight (Int_t cnt, TBtInnerNode *rightsib, Int_t parentIdx)
 The operation is three steps: More...
 
void Remove (Int_t idx)
 Remove an element. More...
 
void RemoveItem (Int_t idx)
 Remove an item. More...
 
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. 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...
 
Int_t Vsize () const
 
- 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 fIsLeaf
 
Int_t fLast
 
TBtInnerNodefParent
 
TBtreefTree
 

#include <TBtree.h>

Inheritance diagram for TBtInnerNode:
[legend]

Constructor & Destructor Documentation

◆ TBtInnerNode() [1/2]

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

Create a B-tree innernode.

Definition at line 687 of file TBtree.cxx.

◆ TBtInnerNode() [2/2]

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::~TBtInnerNode ( )

Constructor.

Definition at line 711 of file TBtree.cxx.

Member Function Documentation

◆ Add() [1/3]

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.

◆ Add() [2/3]

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

Add one element.

Definition at line 756 of file TBtree.cxx.

◆ Add() [3/3]

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

Add one element.

Definition at line 766 of file TBtree.cxx.

◆ AddElt() [1/2]

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

Add one element.

Definition at line 734 of file TBtree.cxx.

◆ AddElt() [2/2]

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

Add one element.

Definition at line 747 of file TBtree.cxx.

◆ Append() [1/2]

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.

◆ Append() [2/2]

void TBtInnerNode::Append ( TBtItem itm)

Append itm to this tree.

Definition at line 800 of file TBtree.cxx.

◆ AppendFrom()

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.

◆ BalanceWith()

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.

◆ BalanceWithLeft()

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.

◆ BalanceWithRight()

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.

◆ DecNofKeys()

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

Definition at line 414 of file TBtree.h.

◆ DecrNofKeys()

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.

◆ FindRank()

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.

◆ FindRankUp()

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.

◆ FirstLeafNode()

TBtLeafNode * TBtInnerNode::FirstLeafNode ( )
virtual

Return the first leaf node.

Implements TBtNode.

Definition at line 901 of file TBtree.cxx.

◆ Found()

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.

◆ GetItem()

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

Definition at line 226 of file TBtree.h.

◆ GetKey()

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

Definition at line 225 of file TBtree.h.

◆ GetNofKeys()

Int_t TBtInnerNode::GetNofKeys ( Int_t  i) const
inline

Definition at line 393 of file TBtree.h.

◆ GetTree()

TBtNode* TBtInnerNode::GetTree ( Int_t  i) const
inline

Definition at line 224 of file TBtree.h.

◆ IncNofKeys()

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

Definition at line 409 of file TBtree.h.

◆ IncrNofKeys()

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.

◆ IndexOf()

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.

◆ InformParent()

void TBtInnerNode::InformParent ( )

Tell the parent that we are full.

Definition at line 957 of file TBtree.cxx.

◆ IsAlmostFull()

Int_t TBtInnerNode::IsAlmostFull ( ) const
inline

Definition at line 259 of file TBtree.h.

◆ IsFull() [1/2]

Int_t TBtInnerNode::IsFull ( ) const
inline

Definition at line 257 of file TBtree.h.

◆ IsFull() [2/2]

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.

◆ IsLow() [1/2]

Int_t TBtInnerNode::IsLow ( ) const
inline

Definition at line 260 of file TBtree.h.

◆ IsLow() [2/2]

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.

◆ LastLeafNode()

TBtLeafNode * TBtInnerNode::LastLeafNode ( )
virtual

Return the last leaf node.

Implements TBtNode.

Definition at line 1112 of file TBtree.cxx.

◆ MaxIndex()

Int_t TBtInnerNode::MaxIndex ( ) const
inline

Definition at line 252 of file TBtree.h.

◆ MaxPsize()

Int_t TBtInnerNode::MaxPsize ( ) const
inline

Definition at line 253 of file TBtree.h.

◆ MergeWithRight()

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

Merge the 2 part of the tree.

Definition at line 1120 of file TBtree.cxx.

◆ NofKeys() [1/2]

Int_t TBtInnerNode::NofKeys ( Int_t  idx) const
inline

Definition at line 399 of file TBtree.h.

◆ NofKeys() [2/2]

Int_t TBtInnerNode::NofKeys ( ) const
virtual

Number of key.

Implements TBtNode.

Definition at line 1135 of file TBtree.cxx.

◆ operator[]()

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

return an element.

Implements TBtNode.

Definition at line 1146 of file TBtree.cxx.

◆ Psize()

Int_t TBtInnerNode::Psize ( ) const
inline

Definition at line 250 of file TBtree.h.

◆ PushLeft()

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.

◆ PushRight()

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.

◆ Remove()

void TBtInnerNode::Remove ( Int_t  idx)
virtual

Remove an element.

Implements TBtNode.

Definition at line 1232 of file TBtree.cxx.

◆ RemoveItem()

void TBtInnerNode::RemoveItem ( Int_t  idx)

Remove an item.

Definition at line 1243 of file TBtree.cxx.

◆ SetItem() [1/2]

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

Definition at line 216 of file TBtree.h.

◆ SetItem() [2/2]

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

Definition at line 217 of file TBtree.h.

◆ SetKey()

void TBtInnerNode::SetKey ( Int_t  i,
TObject obj 
)
inline

Definition at line 215 of file TBtree.h.

◆ SetNofKeys()

void TBtInnerNode::SetNofKeys ( Int_t  i,
Int_t  r 
)
inline

Definition at line 404 of file TBtree.h.

◆ SetTree()

void TBtInnerNode::SetTree ( Int_t  i,
TBtNode node 
)
inline

Definition at line 214 of file TBtree.h.

◆ ShiftLeft()

void TBtInnerNode::ShiftLeft ( Int_t  cnt)

Shift to the left.

Definition at line 1262 of file TBtree.cxx.

◆ Split()

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.

◆ SplitWith()

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

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.

◆ Vsize()

Int_t TBtInnerNode::Vsize ( ) const
inline

Definition at line 419 of file TBtree.h.

Member Data Documentation

◆ fItem

TBtItem* TBtInnerNode::fItem
private

Definition at line 193 of file TBtree.h.


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