Type that is useful for navigating a btree. More...

#include <tpie/btree/base.h>

Public Types
typedef S	state_type

typedef S::key_type	key_type
	Type of the key of a value. More...

typedef S::augment_type	augment_type
	Type of the augment of a set of nodes/values. More...

typedef S::value_type	value_type
	Type of values. More...

typedef S::store_type	store_type

Public Member Functions
bool	has_parent () const
	Check if this node has a parent. More...

void	parent ()
	Move to the parent node. More...

void	child (size_t i)
	Move to the ith child. More...

btree_node	get_parent () const
	Return the parent node. More...

btree_node	get_child (size_t i) const
	Return the ith child node. More...

bool	is_leaf () const
	Return true if this is a leaf node. More...

const augment_type &	get_augmentation (size_t i) const
	Return the augmented data of the ith child. More...

key_type	min_key (size_t i) const
	Return the minimal key of the i'th child. More...

const value_type &	value (size_t i) const
	Return the i'th value. More...

size_t	count () const
	Return the number of children or values. More...

size_t	index () const
	Return the index of this node in its parent. More...

Friends
template<typename , typename >
class	bbits::tree_state

template<typename , typename >
class	bbits::tree

template<typename , typename >
class	bbits::builder

template<typename >
class	btree_iterator

Detailed Description

template<typename S>
class tpie::btree_node< S >

Type that is useful for navigating a btree.

S is the type of the store used

Definition at line 178 of file base.h.

Member Typedef Documentation

template<typename S >

typedef S::augment_type tpie::btree_node< S >::augment_type

Type of the augment of a set of nodes/values.

Definition at line 50 of file node.h.

template<typename S >

typedef S::key_type tpie::btree_node< S >::key_type

Type of the key of a value.

Definition at line 45 of file node.h.

template<typename S >

typedef S::value_type tpie::btree_node< S >::value_type

Type of values.

Definition at line 55 of file node.h.

Member Function Documentation

template<typename S >

void tpie::btree_node< S >::child ( size_t i )

inline

Move to the ith child.

Requires !is_leaf() and i < count()

Definition at line 89 of file node.h.

References tpie::btree_node< S >::count(), and tp_assert.

                          {
         tp_assert(!m_is_leaf, "Is leaf");
         tp_assert(i < count(), "Invalid i");
         if (m_path.size() + 1 == m_state->store().height()) {
             m_is_leaf = true;
             m_leaf = m_state->store().get_child_leaf(m_path.back(), i);
         } else
             m_path.push_back(m_state->store().get_child_internal(m_path.back(), i));
     }

template<typename S >

size_t tpie::btree_node< S >::count ( ) const

inline

Return the number of children or values.

Definition at line 160 of file node.h.

Referenced by tpie::btree_node< S >::child().

                          {
         if (m_is_leaf)
             return m_state->store().count(m_leaf);
         else
             return m_state->store().count(m_path.back());
     }

template<typename S >

const augment_type& tpie::btree_node< S >::get_augmentation ( size_t i ) const

inline

Return the augmented data of the ith child.

Requires !is_leaf()

Definition at line 133 of file node.h.

                                                           {
         return state_type::user_augment(m_state->store().augment(m_path.back(), i));
     }

template<typename S >

btree_node tpie::btree_node< S >::get_child ( size_t i ) const

inline

Return the ith child node.

Requires !is_leaf() and i < count()

Definition at line 115 of file node.h.

                                          {
         btree_node n=*this;
         n.child(i);
         return n;
     }

template<typename S >

btree_node tpie::btree_node< S >::get_parent ( ) const

inline

Return the parent node.

Requires hasParent()

Definition at line 104 of file node.h.

                                   {
         btree_node n=*this;
         n.parent();
         return n;
     }

template<typename S >

bool tpie::btree_node< S >::has_parent ( ) const

inline

Check if this node has a parent.

True iff this is not the root

Definition at line 65 of file node.h.

                             {
         if (m_is_leaf)
             return !m_path.empty();
         else
             return m_path.size() > 1;
     }

template<typename S >

size_t tpie::btree_node< S >::index ( ) const

inline

Return the index of this node in its parent.

Requires has_parent()

Definition at line 172 of file node.h.

                          {
         if (m_is_leaf)
             return m_state->store().index(m_leaf, m_path.back());
         return m_state->store().index(m_path.back(), m_path[m_path.size()-2]);
     }

template<typename S >

bool tpie::btree_node< S >::is_leaf ( ) const

inline

Return true if this is a leaf node.

Definition at line 124 of file node.h.

                          {
         return m_is_leaf;
     }

template<typename S >

key_type tpie::btree_node< S >::min_key ( size_t i ) const

inline

Return the minimal key of the i'th child.

Definition at line 140 of file node.h.

                                      {
         if (m_is_leaf)
             return m_state->min_key(m_leaf, i);
         else
             return m_state->min_key(m_path.back(), i);
     }

template<typename S >

void tpie::btree_node< S >::parent ( )

inline

Move to the parent node.

Requires hasParent()

Definition at line 77 of file node.h.

                   {
         if (m_is_leaf)
             m_is_leaf = false;
         else
             m_path.pop_back();
     }

template<typename S >

const value_type& tpie::btree_node< S >::value ( size_t i ) const

inline

Return the i'th value.

Requires is_leaf()

Definition at line 152 of file node.h.

References tp_assert.

                                              {
         tp_assert(m_is_leaf, "Not leaf");
         return m_state->store().get(m_leaf, i);
     }

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

btree/base.h
btree/node.h

TPIE

Public Types

Public Member Functions

Friends

Detailed Description

template<typename S> class tpie::btree_node< S >

Member Typedef Documentation

Member Function Documentation

template<typename S>
class tpie::btree_node< S >