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

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

TObject *	Found (const TObject obj, TBtNode which, Int_t where)
	Recursively look for WHAT starting in the current node. More...

TBtItem &	GetItem (Int_t i) const

TObject *	GetKey (Int_t i) const

Int_t	GetNofKeys (Int_t i) const

TBtNode *	GetTree (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...

TBtLeafNode *	LastLeafNode ()
	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...

TObject *	operator[] (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 TBtree *	GetParentTree () const

Private Attributes
TBtItem *	fItem

Additional Inherited Members
Protected Attributes inherited from TBtNode
Int_t	fIsLeaf

Int_t	fLast

TBtInnerNode *	fParent

TBtree *	fTree

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

◆ 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:

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