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:

Collaboration diagram for TBtInnerNode:

Constructor & Destructor Documentation

§ TBtInnerNode() [1/2]

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

Create a B-tree innernode.

Definition at line 684 of file TBtree.cxx.

Referenced by Split(), and SplitWith().

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

§ ~TBtInnerNode()

TBtInnerNode::~TBtInnerNode ( )

Constructor.

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

Referenced by Add().

§ Add() [2/3]

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

Add one element.

Definition at line 753 of file TBtree.cxx.

§ Add() [3/3]

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

Add one element.

Definition at line 763 of file TBtree.cxx.

§ AddElt() [1/2]

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

Add one element.

Definition at line 731 of file TBtree.cxx.

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

§ AddElt() [2/2]

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

Add one element.

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

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

§ Append() [2/2]

void TBtInnerNode::Append ( TBtItem & itm )

Append itm to this tree.

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

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

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

Referenced by IsLow(), and TBtLeafNode::SetKey().

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

Referenced by BalanceWith(), IsFull(), and TBtLeafNode::SetKey().

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

Referenced by BalanceWith(), IsFull(), TBtLeafNode::SetKey(), and Split().

§ DecNofKeys()

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

§ DecrNofKeys()

void TBtInnerNode::DecrNofKeys ( TBtNode * np )

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

Definition at line 846 of file TBtree.cxx.

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

§ FindRank()

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

virtual

Recursively look for WHAT starting in the current node.

Implements TBtNode.

Definition at line 859 of file TBtree.cxx.

Referenced by TBtLeafNode::RemoveItem().

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

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

§ FirstLeafNode()

TBtLeafNode * TBtInnerNode::FirstLeafNode ( )

virtual

Return the first leaf node.

Implements TBtNode.

Definition at line 898 of file TBtree.cxx.

Referenced by TBtLeafNode::SetKey().

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

Referenced by TBtLeafNode::RemoveItem().

§ GetItem()

TBtItem& TBtInnerNode::GetItem ( Int_t i ) const

inline

Definition at line 226 of file TBtree.h.

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

§ GetKey()

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

§ GetNofKeys()

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

§ GetTree()

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(), and TBtLeafNode::Split().

§ IncNofKeys()

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

§ IncrNofKeys()

void TBtInnerNode::IncrNofKeys ( TBtNode * np )

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

Definition at line 928 of file TBtree.cxx.

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

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

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

§ InformParent()

void TBtInnerNode::InformParent ( )

Tell the parent that we are full.

Definition at line 954 of file TBtree.cxx.

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

§ IsAlmostFull()

Int_t TBtInnerNode::IsAlmostFull ( ) const

inline

Definition at line 259 of file TBtree.h.

Referenced by IsFull().

§ IsFull() [1/2]

Int_t TBtInnerNode::IsFull ( ) const

inline

Definition at line 257 of file TBtree.h.

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

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

§ IsLow() [1/2]

Int_t TBtInnerNode::IsLow ( ) const

inline

Definition at line 260 of file TBtree.h.

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

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

§ LastLeafNode()

TBtLeafNode * TBtInnerNode::LastLeafNode ( )

virtual

Return the last leaf node.

Implements TBtNode.

Definition at line 1109 of file TBtree.cxx.

Referenced by TBtLeafNode::SetKey().

§ MaxIndex()

Int_t TBtInnerNode::MaxIndex ( ) const

inline

Definition at line 252 of file TBtree.h.

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

§ MaxPsize()

Int_t TBtInnerNode::MaxPsize ( ) const

inline

Definition at line 253 of file TBtree.h.

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

§ MergeWithRight()

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

Merge the 2 part of the tree.

Definition at line 1117 of file TBtree.cxx.

Referenced by IsLow(), and TBtLeafNode::SetKey().

§ NofKeys() [1/2]

Int_t TBtInnerNode::NofKeys ( Int_t idx ) const

inline

Definition at line 399 of file TBtree.h.

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

§ NofKeys() [2/2]

Int_t TBtInnerNode::NofKeys ( ) const

virtual

Number of key.

Implements TBtNode.

Definition at line 1132 of file TBtree.cxx.

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

§ operator[]()

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

virtual

return an element.

Implements TBtNode.

Definition at line 1143 of file TBtree.cxx.

§ Psize()

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(), and SplitWith().

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

Referenced by BalanceWithLeft(), MergeWithRight(), TBtLeafNode::SetKey(), and SplitWith().

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

Referenced by BalanceWithRight(), TBtLeafNode::SetKey(), and SplitWith().

§ Remove()

void TBtInnerNode::Remove ( Int_t idx )

virtual

Remove an element.

Implements TBtNode.

Definition at line 1229 of file TBtree.cxx.

§ RemoveItem()

void TBtInnerNode::RemoveItem ( Int_t idx )

Remove an item.

Definition at line 1240 of file TBtree.cxx.

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

§ SetItem() [1/2]

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

inline

Definition at line 216 of file TBtree.h.

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

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

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

§ SetNofKeys()

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

§ SetTree()

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

inline

Definition at line 214 of file TBtree.h.

Referenced by SplitWith().

§ ShiftLeft()

void TBtInnerNode::ShiftLeft ( Int_t cnt )

Shift to the left.

Definition at line 1259 of file TBtree.cxx.

Referenced by PushLeft(), TBtLeafNode::SetKey(), and SplitWith().

§ 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 1273 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
                   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 1312 of file TBtree.cxx.

Referenced by IsFull(), and TBtLeafNode::SetKey().

§ Vsize()

Int_t TBtInnerNode::Vsize ( ) const

inline

Definition at line 419 of file TBtree.h.

Referenced by BalanceWith(), BalanceWithLeft(), BalanceWithRight(), IsLow(), MergeWithRight(), TBtLeafNode::Psize(), and SplitWith().

Member Data Documentation

§ fItem

TBtItem* TBtInnerNode::fItem

private

Definition at line 193 of file TBtree.h.

Referenced by DecrNofKeys(), IncrNofKeys(), RemoveItem(), TBtInnerNode(), and ~TBtInnerNode().

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

core/cont/inc/TBtree.h
core/cont/src/TBtree.cxx

Public Member Functions

Private Attributes

Additional Inherited Members

Constructor & Destructor Documentation

§ TBtInnerNode() [1/2]

§ TBtInnerNode() [2/2]

§ ~TBtInnerNode()

Member Function Documentation

§ Add() [1/3]

§ Add() [2/3]

§ Add() [3/3]

§ AddElt() [1/2]

§ AddElt() [2/2]

§ Append() [1/2]

§ Append() [2/2]

§ AppendFrom()

§ BalanceWith()

§ BalanceWithLeft()

§ BalanceWithRight()

§ DecNofKeys()

§ DecrNofKeys()

§ FindRank()

§ FindRankUp()

§ FirstLeafNode()

§ Found()

§ GetItem()

§ GetKey()

§ GetNofKeys()

§ GetTree()

§ IncNofKeys()

§ IncrNofKeys()

§ IndexOf()

§ InformParent()

§ IsAlmostFull()

§ IsFull() [1/2]

§ IsFull() [2/2]

§ IsLow() [1/2]

§ IsLow() [2/2]

§ LastLeafNode()

§ MaxIndex()

§ MaxPsize()

§ MergeWithRight()

§ NofKeys() [1/2]

§ NofKeys() [2/2]

§ operator[]()

§ Psize()

§ PushLeft()

§ PushRight()

§ Remove()

§ RemoveItem()

§ SetItem() [1/2]

§ SetItem() [2/2]

§ SetKey()

§ SetNofKeys()

§ SetTree()

§ ShiftLeft()

§ Split()

§ SplitWith()

§ Vsize()

Member Data Documentation

§ fItem