---

CdbRooRoAbsBtreeR< K, FCP, ORDER > Class Template Reference

An abstract class for B-tree (balanced tree). More...

Inheritance diagram for CdbRooRoAbsBtreeR< K, FCP, ORDER >:

List of all members.

Public Member Functions
	CdbRooRoAbsBtreeR ()
	Default constructor.
virtual	~CdbRooRoAbsBtreeR ()
	Destructor.
void	dump (std::ostream &o) const
	Dump the tree.
void	insert (const K &key)
	Insert a key into the tree.
void	remove (const K &key)
	Remove a key from the tree.
bool	search (const K &key) const
	Search a key in the tree.
bool	search (const K &key, K &result) const
	Extended search for a key in the tree.
bool	fuzzySearch (const K &key, K &result) const
	Search a key in the tree using "fuzzy" search logic.
void	reset ()
	Reset the tree.
Protected Member Functions
virtual UInt_t	root () const=0
	Get a root node of the B-tree.
virtual void	set_root (UInt_t node)=0
	Set new root node of the B-tree.
virtual CdbRooRoBtreeNodeR< K, ORDER >	readNode (UInt_t node) const=0
	Get a copy of specified node.
virtual void	updateNode (UInt_t node, const CdbRooRoBtreeNodeR< K, ORDER > &value)=0
	Save back the value of specified node.
virtual UInt_t	allocate (UInt_t parent=0)=0
	Allocator.
virtual void	release (UInt_t node)=0
	Disposer.

---

Detailed Description

template<class K, class FCP = CdbRooRoBtreeDefaultFCPR<K>, UInt_t ORDER = 4>
class CdbRooRoAbsBtreeR< K, FCP, ORDER >

An abstract class for B-tree (balanced tree).

This template class implements the corresponding B-tree algorithms for embedded classes. The concrete storage for the B-tree data structures is provided by derived classes.

The template is parametrized by mean of the following parameters:

K - is a type of keys. This type has to provide the following methods:

default constructor copy constructor destructor

and operators:

= == <= > << (into std::ostream)

FCP - this is a policy class that is expected to provide the only method:

class ... { public: static bool match( const K& source, const K& target ); };

This meathod is used for one-directional comparision of two keys. This operation is meant to answer a question if specified "source" key matches the "target" one.

It's not nessesary true that if "source" matches the "target" then the "targed" would match the "source" one.

The meaning of the "match" is up to the implementation of a concrete policy and type of keys (K).

ORDER - is an order of the tree.

Definition at line 188 of file CdbRooRoAbsBtreeR.rdl.

---

Constructor & Destructor Documentation

template<class K, class FCP = CdbRooRoBtreeDefaultFCPR<K>, UInt_t ORDER = 4> CdbRooRoAbsBtreeR< K, FCP, ORDER >::CdbRooRoAbsBtreeR (    )  [inline]

Default constructor. Creates an empty tree. Definition at line 196 of file CdbRooRoAbsBtreeR.rdl.

template<class K, class FCP = CdbRooRoBtreeDefaultFCPR<K>, UInt_t ORDER = 4> virtual CdbRooRoAbsBtreeR< K, FCP, ORDER >::~CdbRooRoAbsBtreeR (    )  [inline, virtual]

Destructor. Destroys the tree. Definition at line 202 of file CdbRooRoAbsBtreeR.rdl.

---

Member Function Documentation

template<class K, class FCP = CdbRooRoBtreeDefaultFCPR<K>, UInt_t ORDER = 4> virtual UInt_t CdbRooRoAbsBtreeR< K, FCP, ORDER >::allocate (  UInt_t    parent = 0 )  [protected, pure virtual]

Allocator. To be implemented by a storage provider of a derived class. Implemented in CdbRooRoBtreeR< K, FCP, ORDER >, and CdbRooRoBtreeR< CdbRooRoInterValBteR, CdbRooRoInterValBteFCPR >. Referenced by CdbRooRoAbsBtreeR< K, FCP, ORDER >::insert().

template<class K, class FCP = CdbRooRoBtreeDefaultFCPR<K>, UInt_t ORDER = 4> void CdbRooRoAbsBtreeR< K, FCP, ORDER >::dump (  std::ostream &    o )  const [inline]

Dump the tree. The dump is done onto a stream specified through the only parameter of the method. Definition at line 209 of file CdbRooRoAbsBtreeR.rdl. Referenced by CdbRooRoAbsBtreeR< CdbRooRoInterValBteR, CdbRooRoInterValBteFCPR, ORDER >::dump().

template<class K, class FCP = CdbRooRoBtreeDefaultFCPR<K>, UInt_t ORDER = 4> bool CdbRooRoAbsBtreeR< K, FCP, ORDER >::fuzzySearch (  const K &    key, K &    result )  const [inline]

Search a key in the tree using "fuzzy" search logic. This method will use "fuzzy" logic to search for a key, which is very similar to the one specified on the input. The "similarity" is defined throught this (Btree) class template parameter. If there is such an entry then the method will return "true" and a value of the found ("similar") key. Definition at line 260 of file CdbRooRoAbsBtreeR.rdl.

template<class K, class FCP, UInt_t ORDER> void CdbRooRoAbsBtreeR< K, FCP, ORDER >::insert (  const K &    key )

Insert a key into the tree. Insert specified key into the tree. If the tree alredy has such an element then just ignore it. Definition at line 22 of file CdbRooRoAbsBtreeR.cc. References CdbRooRoAbsBtreeR< K, FCP, ORDER >::allocate(), CdbRooRoBtreeNodeR< K, ORDER >::child, CdbRooRoBtreeNodeR< K, ORDER >::isLeaf, CdbRooRoBtreeNodeR< K, ORDER >::key, CdbRooRoBtreeNodeR< K, ORDER >::n, CdbRooRoBtreeNodeR< K, ORDER >::parent, CdbRooRoAbsBtreeR< K, FCP, ORDER >::readNode(), CdbRooRoAbsBtreeR< K, FCP, ORDER >::release(), CdbRooRoAbsBtreeR< K, FCP, ORDER >::root(), CdbRooRoAbsBtreeR< K, FCP, ORDER >::search(), and CdbRooRoAbsBtreeR< K, FCP, ORDER >::updateNode().

template<class K, class FCP = CdbRooRoBtreeDefaultFCPR<K>, UInt_t ORDER = 4> virtual CdbRooRoBtreeNodeR<K,ORDER> CdbRooRoAbsBtreeR< K, FCP, ORDER >::readNode (  UInt_t    node )  const [protected, pure virtual]

Get a copy of specified node. To be implemented by a storage provider of a derived class. Implemented in CdbRooRoBtreeR< K, FCP, ORDER >, and CdbRooRoBtreeR< CdbRooRoInterValBteR, CdbRooRoInterValBteFCPR >. Referenced by CdbRooRoAbsBtreeR< K, FCP, ORDER >::insert(), CdbRooRoAbsBtreeR< K, FCP, ORDER >::remove(), and CdbRooRoAbsBtreeR< K, FCP, ORDER >::search().

template<class K, class FCP = CdbRooRoBtreeDefaultFCPR<K>, UInt_t ORDER = 4> virtual void CdbRooRoAbsBtreeR< K, FCP, ORDER >::release (  UInt_t    node )  [protected, pure virtual]

Disposer. To be implemented by a storage provider of a derived class. Implemented in CdbRooRoBtreeR< K, FCP, ORDER >, and CdbRooRoBtreeR< CdbRooRoInterValBteR, CdbRooRoInterValBteFCPR >. Referenced by CdbRooRoAbsBtreeR< K, FCP, ORDER >::insert().

template<class K, class FCP, UInt_t ORDER> void CdbRooRoAbsBtreeR< K, FCP, ORDER >::remove (  const K &    key )

Remove a key from the tree. Remove specified key from the tree. If the tree does not have such an element then just ignore it. Definition at line 147 of file CdbRooRoAbsBtreeR.cc. References CdbRooRoBtreeNodeR< K, ORDER >::child, CdbRooRoBtreeNodeR< K, ORDER >::isLeaf, CdbRooRoBtreeNodeR< K, ORDER >::key, CdbRooRoBtreeNodeR< K, ORDER >::n, CdbRooRoAbsBtreeR< K, FCP, ORDER >::readNode(), CdbRooRoAbsBtreeR< K, FCP, ORDER >::root(), and CdbRooRoAbsBtreeR< K, FCP, ORDER >::updateNode().

template<class K, class FCP = CdbRooRoBtreeDefaultFCPR<K>, UInt_t ORDER = 4> void CdbRooRoAbsBtreeR< K, FCP, ORDER >::reset (    )  [inline]

Reset the tree. This operation will remove all elements from the tree except it's root node. The root node will get 0 keys. Definition at line 273 of file CdbRooRoAbsBtreeR.rdl. Referenced by CdbRooRoAbsBtreeR< CdbRooRoInterValBteR, CdbRooRoInterValBteFCPR, ORDER >::reset().

template<class K, class FCP = CdbRooRoBtreeDefaultFCPR<K>, UInt_t ORDER = 4> virtual UInt_t CdbRooRoAbsBtreeR< K, FCP, ORDER >::root (    )  const [protected, pure virtual]

Get a root node of the B-tree. To be implemented by a storage provider of a derived class. Implemented in CdbRooRoBtreeR< K, FCP, ORDER >, and CdbRooRoBtreeR< CdbRooRoInterValBteR, CdbRooRoInterValBteFCPR >. Referenced by CdbRooRoAbsBtreeR< CdbRooRoInterValBteR, CdbRooRoInterValBteFCPR, ORDER >::dump(), CdbRooRoAbsBtreeR< CdbRooRoInterValBteR, CdbRooRoInterValBteFCPR, ORDER >::fuzzySearch(), CdbRooRoAbsBtreeR< K, FCP, ORDER >::insert(), CdbRooRoAbsBtreeR< K, FCP, ORDER >::remove(), CdbRooRoAbsBtreeR< CdbRooRoInterValBteR, CdbRooRoInterValBteFCPR, ORDER >::reset(), CdbRooRoAbsBtreeR< CdbRooRoInterValBteR, CdbRooRoInterValBteFCPR, ORDER >::search(), and CdbRooRoAbsBtreeR< K, FCP, ORDER >::search().

template<class K, class FCP, UInt_t ORDER> bool CdbRooRoAbsBtreeR< K, FCP, ORDER >::search (  const K &    key, K &    result )  const

Extended search for a key in the tree. This method will look for the presence of specified key in the tree. If there is such an entry then the method will return "true" and a value of the found ("similar") key. Definition at line 207 of file CdbRooRoAbsBtreeR.cc. References CdbRooRoBtreeNodeR< K, ORDER >::key, CdbRooRoBtreeNodeR< K, ORDER >::n, CdbRooRoAbsBtreeR< K, FCP, ORDER >::readNode(), and CdbRooRoAbsBtreeR< K, FCP, ORDER >::root().

template<class K, class FCP = CdbRooRoBtreeDefaultFCPR<K>, UInt_t ORDER = 4> bool CdbRooRoAbsBtreeR< K, FCP, ORDER >::search (  const K &    key )  const [inline]

Search a key in the tree. This method will only look for the presence of specified key in the tree. If there is such an entry it will just return "true". Definition at line 234 of file CdbRooRoAbsBtreeR.rdl. Referenced by CdbRooRoAbsBtreeR< K, FCP, ORDER >::insert().

template<class K, class FCP = CdbRooRoBtreeDefaultFCPR<K>, UInt_t ORDER = 4> virtual void CdbRooRoAbsBtreeR< K, FCP, ORDER >::set_root (  UInt_t    node )  [protected, pure virtual]

Set new root node of the B-tree. To be implemented by a storage provider of a derived class. Implemented in CdbRooRoBtreeR< K, FCP, ORDER >, and CdbRooRoBtreeR< CdbRooRoInterValBteR, CdbRooRoInterValBteFCPR >.

template<class K, class FCP = CdbRooRoBtreeDefaultFCPR<K>, UInt_t ORDER = 4> virtual void CdbRooRoAbsBtreeR< K, FCP, ORDER >::updateNode (  UInt_t    node, const CdbRooRoBtreeNodeR< K, ORDER > &    value )  [protected, pure virtual]

Save back the value of specified node. To be implemented by a storage provider of a derived class. Implemented in CdbRooRoBtreeR< K, FCP, ORDER >, and CdbRooRoBtreeR< CdbRooRoInterValBteR, CdbRooRoInterValBteFCPR >. Referenced by CdbRooRoAbsBtreeR< K, FCP, ORDER >::insert(), and CdbRooRoAbsBtreeR< K, FCP, ORDER >::remove().

---

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

• CdbRooRoAbsBtreeR.rdl
• CdbRooRoAbsBtreeR.cc

---