Inner node of a TBtree.

Definition at line 190 of file TBtree.h.

Public Member Functions
	TBtInnerNode (TBtInnerNode parent, TBtree t=nullptr)
	Create a B-tree innernode.
	TBtInnerNode (TBtInnerNode parent, TBtree tree, TBtNode *oldroot)
	Called only by TBtree to initialize the TBtInnerNode that is about to become the root.
	~TBtInnerNode ()
	Constructor.
void	Add (const TObject *obj, Int_t idx) override
	This is called only from TBtree::Add().
void	Add (Int_t at, TObject obj, TBtNode n)
	Add one element.
void	Add (TBtItem &i, Int_t idx)
	Add one element.
void	AddElt (Int_t at, TObject obj, TBtNode n)
	Add one element.
void	AddElt (TBtItem &itm, Int_t at)
	Add one element.
void	Append (TBtItem &itm)
	Append itm to this tree.
void	Append (TObject obj, TBtNode n)
	Never called from anywhere where it might fill up THIS.
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.
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.
void	BalanceWithLeft (TBtInnerNode *l, Int_t idx)
	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.
void	BalanceWithRight (TBtInnerNode *r, Int_t idx)
	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.
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.
Int_t	FindRank (const TObject *obj) const override
	Recursively look for WHAT starting in the current node.
Int_t	FindRankUp (const TBtNode *n) 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.
TBtLeafNode *	FirstLeafNode () override
	Return the first leaf node.
TObject *	Found (const TObject obj, TBtNode which, Int_t where) override
	Recursively look for WHAT starting in the current node.
TBtItem &	GetItem (Int_t i) const
TObject *	GetKey (Int_t i) const
Int_t	GetNofKeys (Int_t i) const
virtual TBtree *	GetParentTree () 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.
Int_t	IndexOf (const TBtNode *n) const
	Returns a number in the range 0 to this->fLast 0 is returned if THAT == fTree[0].
void	InformParent ()
	Tell the parent that we are full.
Int_t	IsAlmostFull () const
Int_t	IsFull () const
void	IsFull (TBtNode *n)
	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:
Int_t	IsLow () const
void	IsLow (TBtNode *n)
	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:
TBtLeafNode *	LastLeafNode () override
	Return the last leaf node.
Int_t	MaxIndex () const
Int_t	MaxPsize () const
void	MergeWithRight (TBtInnerNode *r, Int_t idx)
	Merge the 2 part of the tree.
Int_t	NofKeys () const override
	Number of key.
Int_t	NofKeys (Int_t idx) const
TObject *	operator[] (Int_t i) const override
	return an element.
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.
void	PushRight (Int_t cnt, TBtInnerNode *rightsib, Int_t parentIdx)
	The operation is three steps:
void	Remove (Int_t idx) override
	Remove an element.
void	RemoveItem (Int_t idx)
	Remove an item.
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.
void	Split () override
	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.
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.
Int_t	Vsize () const

Protected Attributes
Int_t	fIsLeaf
Int_t	fLast
TBtInnerNode *	fParent
TBtree *	fTree

Private Attributes
TBtItem *	fItem

#include <TBtree.h>

Inheritance diagram for TBtInnerNode:

Constructor & Destructor Documentation

◆ TBtInnerNode() [1/2]

TBtInnerNode::TBtInnerNode	(	TBtInnerNode *	parent,
		TBtree *	t = nullptr )

Create a B-tree innernode.

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

◆ ~TBtInnerNode()

TBtInnerNode::~TBtInnerNode ( )

Constructor.

Definition at line 710 of file TBtree.cxx.

Member Function Documentation

◆ Add() [1/3]

void TBtInnerNode::Add	(	const TObject *	obj,
		Int_t	idx )

overridevirtual

This is called only from TBtree::Add().

Implements TBtNode.

Definition at line 723 of file TBtree.cxx.

◆ Add() [2/3]

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

Add one element.

Definition at line 765 of file TBtree.cxx.

◆ Add() [3/3]

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

Add one element.

Definition at line 755 of file TBtree.cxx.

◆ AddElt() [1/2]

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

Add one element.

Definition at line 746 of file TBtree.cxx.

◆ AddElt() [2/2]

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

Add one element.

Definition at line 733 of file TBtree.cxx.

◆ Append() [1/2]

void TBtInnerNode::Append ( TBtItem & itm )

Append itm to this tree.

Definition at line 799 of file TBtree.cxx.

◆ Append() [2/2]

void TBtInnerNode::Append	(	TObject *	obj,
		TBtNode *	n )

Never called from anywhere where it might fill up THIS.

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

◆ BalanceWith()

void TBtInnerNode::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.

Definition at line 837 of file TBtree.cxx.

◆ BalanceWithLeft()

void TBtInnerNode::BalanceWithLeft	(	TBtInnerNode *	l,
		Int_t	idx )

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

◆ BalanceWithRight()

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

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

◆ DecNofKeys()

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

inline

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

◆ FindRank()

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

overridevirtual

Recursively look for WHAT starting in the current node.

Implements TBtNode.

Definition at line 861 of file TBtree.cxx.

◆ FindRankUp()

Int_t TBtInnerNode::FindRankUp ( const TBtNode * n ) 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 888 of file TBtree.cxx.

◆ FirstLeafNode()

TBtLeafNode * TBtInnerNode::FirstLeafNode ( )

overridevirtual

Return the first leaf node.

Implements TBtNode.

Definition at line 900 of file TBtree.cxx.

◆ Found()

TObject * TBtInnerNode::Found	(	const TObject *	obj,
		TBtNode **	which,
		Int_t *	where )

overridevirtual

Recursively look for WHAT starting in the current node.

Implements TBtNode.

Definition at line 908 of file TBtree.cxx.

◆ GetItem()

TBtItem & TBtInnerNode::GetItem ( Int_t i ) const

inline

Definition at line 225 of file TBtree.h.

◆ GetKey()

TObject * TBtInnerNode::GetKey ( Int_t i ) const

inline

Definition at line 224 of file TBtree.h.

◆ GetNofKeys()

Int_t TBtInnerNode::GetNofKeys ( Int_t i ) const

inline

Definition at line 392 of file TBtree.h.

◆ GetParentTree()

virtual TBtree * TBtNode::GetParentTree ( ) const

inlinevirtualinherited

Definition at line 139 of file TBtree.h.

◆ GetTree()

TBtNode * TBtInnerNode::GetTree ( Int_t i ) const

inline

Definition at line 223 of file TBtree.h.

◆ IncNofKeys()

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

inline

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

◆ IndexOf()

Int_t TBtInnerNode::IndexOf ( const TBtNode * n ) const

Returns a number in the range 0 to this->fLast 0 is returned if THAT == fTree[0].

Definition at line 944 of file TBtree.cxx.

◆ InformParent()

void TBtInnerNode::InformParent ( )

Tell the parent that we are full.

Definition at line 956 of file TBtree.cxx.

◆ IsAlmostFull()

Int_t TBtInnerNode::IsAlmostFull ( ) const

inline

Definition at line 258 of file TBtree.h.

◆ IsFull() [1/2]

Int_t TBtInnerNode::IsFull ( ) const

inline

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

◆ IsLow() [1/2]

Int_t TBtInnerNode::IsLow ( ) const

inline

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

◆ LastLeafNode()

TBtLeafNode * TBtInnerNode::LastLeafNode ( )

overridevirtual

Return the last leaf node.

Implements TBtNode.

Definition at line 1111 of file TBtree.cxx.

◆ MaxIndex()

Int_t TBtInnerNode::MaxIndex ( ) const

inline

Definition at line 251 of file TBtree.h.

◆ MaxPsize()

Int_t TBtInnerNode::MaxPsize ( ) const

inline

Definition at line 252 of file TBtree.h.

◆ MergeWithRight()

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

Merge the 2 part of the tree.

Definition at line 1119 of file TBtree.cxx.

◆ NofKeys() [1/2]

Int_t TBtInnerNode::NofKeys ( ) const

overridevirtual

Number of key.

Implements TBtNode.

Definition at line 1134 of file TBtree.cxx.

◆ NofKeys() [2/2]

Int_t TBtInnerNode::NofKeys ( Int_t idx ) const

inline

Definition at line 398 of file TBtree.h.

◆ operator[]()

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

overridevirtual

return an element.

Implements TBtNode.

Definition at line 1145 of file TBtree.cxx.

◆ Psize()

Int_t TBtInnerNode::Psize ( ) const

inline

Definition at line 249 of file TBtree.h.

◆ PushLeft()

void TBtInnerNode::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.

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

◆ Remove()

void TBtInnerNode::Remove ( Int_t idx )

overridevirtual

Remove an element.

Implements TBtNode.

Definition at line 1231 of file TBtree.cxx.

◆ RemoveItem()

void TBtInnerNode::RemoveItem ( Int_t idx )

Remove an item.

Definition at line 1242 of file TBtree.cxx.

◆ SetItem() [1/2]

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

inline

Definition at line 215 of file TBtree.h.

◆ SetItem() [2/2]

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

inline

Definition at line 216 of file TBtree.h.

◆ SetKey()

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

inline

Definition at line 214 of file TBtree.h.

◆ SetNofKeys()

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

inline

Definition at line 403 of file TBtree.h.

◆ SetTree()

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

inline

Definition at line 213 of file TBtree.h.

◆ ShiftLeft()

void TBtInnerNode::ShiftLeft ( Int_t cnt )

Shift to the left.

Definition at line 1261 of file TBtree.cxx.

◆ Split()

void TBtInnerNode::Split ( )

overridevirtual

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 1275 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 1314 of file TBtree.cxx.

◆ Vsize()

Int_t TBtInnerNode::Vsize ( ) const

inline

Definition at line 418 of file TBtree.h.

Member Data Documentation

◆ fIsLeaf

Int_t TBtNode::fIsLeaf

protectedinherited

Definition at line 132 of file TBtree.h.

◆ fItem

TBtItem* TBtInnerNode::fItem

private

Definition at line 193 of file TBtree.h.

◆ fLast

Int_t TBtNode::fLast

protectedinherited

Definition at line 125 of file TBtree.h.

◆ fParent

TBtInnerNode* TBtNode::fParent

protectedinherited

Definition at line 130 of file TBtree.h.

◆ fTree

TBtree* TBtNode::fTree

protectedinherited

Definition at line 131 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

Protected Attributes

Private Attributes

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

◆ GetParentTree()

◆ 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

◆ fIsLeaf

◆ fItem

◆ fLast

◆ fParent

◆ fTree