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...

TObject *	operator[] (Int_t i) const
	return an element. More...

TObject *	Found (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...

TBtNode *	GetTree (Int_t i) const

TObject *	GetKey (Int_t i) const

TBtItem &	GetItem (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...

TBtLeafNode *	FirstLeafNode ()
	Return the first leaf node. More...

TBtLeafNode *	LastLeafNode ()
	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 TBtree *	GetParentTree () const

Private Attributes
TBtItem *	fItem

Additional Inherited Members
Protected Attributes inherited from TBtNode
Int_t	fLast

TBtInnerNode *	fParent

TBtree *	fTree

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

Definition at line 225 of file TBtree.h.

Referenced by FindRank(), Found(), MergeWithRight(), TBtLeafNode::MergeWithRight(), operator[](), PushLeft(), TBtLeafNode::PushLeft(), PushRight(), TBtLeafNode::PushRight(), Split(), and SplitWith().

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

Definition at line 224 of file TBtree.h.

Referenced by Add(), BalanceWithLeft(), BalanceWithRight(), FindRank(), FirstLeafNode(), Found(), TBtree::IdxAdd(), IndexOf(), IsFull(), IsLow(), LastLeafNode(), operator[](), PushLeft(), TBtLeafNode::PushLeft(), PushRight(), TBtLeafNode::PushRight(), Remove(), TBtree::RootIsEmpty(), TBtLeafNode::Split(), Vsize(), and TBtLeafNode::Vsize().

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

Definition at line 250 of file TBtree.h.

Referenced by BalanceWith(), BalanceWithLeft(), BalanceWithRight(), IsLow(), MergeWithRight(), NofKeys(), PushLeft(), PushRight(), RemoveItem(), TBtree::RootIsEmpty(), SplitWith(), and Vsize().

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

Definition at line 215 of file TBtree.h.

Referenced by MergeWithRight(), PushLeft(), TBtLeafNode::PushLeft(), PushRight(), TBtLeafNode::PushRight(), Remove(), SetItem(), and SplitWith().

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

inline

Definition at line 404 of file TBtree.h.

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

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