Logo ROOT   6.10/09
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 186 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 688 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 700 of file TBtree.cxx.

◆ ~TBtInnerNode()

TBtInnerNode::~TBtInnerNode ( )

Constructor.

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

◆ Add() [2/3]

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

Add one element.

Definition at line 757 of file TBtree.cxx.

◆ Add() [3/3]

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

Add one element.

Definition at line 767 of file TBtree.cxx.

◆ AddElt() [1/2]

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

Add one element.

Definition at line 735 of file TBtree.cxx.

◆ AddElt() [2/2]

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

Add one element.

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

◆ Append() [2/2]

void TBtInnerNode::Append ( TBtItem itm)

Append itm to this tree.

Definition at line 801 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 777 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 839 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 812 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 826 of file TBtree.cxx.

◆ DecNofKeys()

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

Definition at line 410 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 850 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 863 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 890 of file TBtree.cxx.

◆ FirstLeafNode()

TBtLeafNode * TBtInnerNode::FirstLeafNode ( )
virtual

Return the first leaf node.

Implements TBtNode.

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

◆ GetItem()

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

Definition at line 222 of file TBtree.h.

◆ GetKey()

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

Definition at line 221 of file TBtree.h.

◆ GetNofKeys()

Int_t TBtInnerNode::GetNofKeys ( Int_t  i) const
inline

Definition at line 389 of file TBtree.h.

◆ GetTree()

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

Definition at line 220 of file TBtree.h.

◆ IncNofKeys()

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

Definition at line 405 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 932 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 946 of file TBtree.cxx.

◆ InformParent()

void TBtInnerNode::InformParent ( )

Tell the parent that we are full.

Definition at line 958 of file TBtree.cxx.

◆ IsAlmostFull()

Int_t TBtInnerNode::IsAlmostFull ( ) const
inline

Definition at line 255 of file TBtree.h.

◆ IsFull() [1/2]

Int_t TBtInnerNode::IsFull ( ) const
inline

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

◆ IsLow() [1/2]

Int_t TBtInnerNode::IsLow ( ) const
inline

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

◆ LastLeafNode()

TBtLeafNode * TBtInnerNode::LastLeafNode ( )
virtual

Return the last leaf node.

Implements TBtNode.

Definition at line 1113 of file TBtree.cxx.

◆ MaxIndex()

Int_t TBtInnerNode::MaxIndex ( ) const
inline

Definition at line 248 of file TBtree.h.

◆ MaxPsize()

Int_t TBtInnerNode::MaxPsize ( ) const
inline

Definition at line 249 of file TBtree.h.

◆ MergeWithRight()

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

Merge the 2 part of the tree.

Definition at line 1121 of file TBtree.cxx.

◆ NofKeys() [1/2]

Int_t TBtInnerNode::NofKeys ( Int_t  idx) const
inline

Definition at line 395 of file TBtree.h.

◆ NofKeys() [2/2]

Int_t TBtInnerNode::NofKeys ( ) const
virtual

Number of key.

Implements TBtNode.

Definition at line 1136 of file TBtree.cxx.

◆ operator[]()

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

return an element.

Implements TBtNode.

Definition at line 1147 of file TBtree.cxx.

◆ Psize()

Int_t TBtInnerNode::Psize ( ) const
inline

Definition at line 246 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 1170 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 1189 of file TBtree.cxx.

◆ Remove()

void TBtInnerNode::Remove ( Int_t  idx)
virtual

Remove an element.

Implements TBtNode.

Definition at line 1233 of file TBtree.cxx.

◆ RemoveItem()

void TBtInnerNode::RemoveItem ( Int_t  idx)

Remove an item.

Definition at line 1244 of file TBtree.cxx.

◆ SetItem() [1/2]

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

Definition at line 212 of file TBtree.h.

◆ SetItem() [2/2]

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

Definition at line 213 of file TBtree.h.

◆ SetKey()

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

Definition at line 211 of file TBtree.h.

◆ SetNofKeys()

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

Definition at line 400 of file TBtree.h.

◆ SetTree()

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

Definition at line 210 of file TBtree.h.

◆ ShiftLeft()

void TBtInnerNode::ShiftLeft ( Int_t  cnt)

Shift to the left.

Definition at line 1263 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 1277 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 1316 of file TBtree.cxx.

◆ Vsize()

Int_t TBtInnerNode::Vsize ( ) const
inline

Definition at line 415 of file TBtree.h.

Member Data Documentation

◆ fItem

TBtItem* TBtInnerNode::fItem
private

Definition at line 189 of file TBtree.h.


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