Inner node of a TBtree.

Definition at line 186 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.

void	BalanceWithRight (TBtInnerNode *r, Int_t idx)
	THIS has more than RIGHTSIB.

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.

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

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.

Int_t	IsLow () const

void	IsLow (TBtNode *n)
	The child node THAT is <= half full.

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.

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

Public Member Functions inherited from TBtNode
	TBtNode (Int_t isleaf, TBtInnerNode p, TBtree t=nullptr)
	Create a B-tree node.

virtual	~TBtNode ()
	Delete a B-tree node.

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 = `nullptr`
	)

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
	)

overridevirtual

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

Implements TBtNode.

Definition at line 725 of file TBtree.cxx.

◆ Add() [2/3]

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

Add one element.

Definition at line 767 of file TBtree.cxx.

◆ Add() [3/3]

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

Add one element.

Definition at line 757 of file TBtree.cxx.

◆ AddElt() [1/2]

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

Add one element.

Definition at line 748 of file TBtree.cxx.

◆ AddElt() [2/2]

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

Add one element.

Definition at line 735 of file TBtree.cxx.

◆ Append() [1/2]

void TBtInnerNode::Append ( TBtItem & itm )

Append itm to this tree.

Definition at line 801 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 791 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 *	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 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 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 850 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 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 ( )

overridevirtual

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
	)

overridevirtual

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

overridevirtual

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

overridevirtual

Number of key.

Implements TBtNode.

Definition at line 1136 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 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	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 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 )

overridevirtual

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

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

◆ Vsize()

Int_t TBtInnerNode::Vsize ( ) const

inline

Definition at line 418 of file TBtree.h.

Member Data Documentation

◆ fItem

TBtItem* TBtInnerNode::fItem

private

Definition at line 189 of file TBtree.h.

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