Augmented btree. More...
#include <tpie/btree/base.h>
Public Types | |
typedef tree_state< T, O > | state_type |
typedef state_type::augmenter_type | augmenter_type |
typedef state_type::value_type | value_type |
Type of value stored. More... | |
typedef state_type::keyextract_type | keyextract_type |
typedef state_type::augment_type | augment_type |
typedef state_type::key_type | key_type |
The type of key used. More... | |
typedef O::C | comp_type |
typedef state_type::store_type | store_type |
typedef btree_node< state_type > | node_type |
Type of node wrapper. More... | |
typedef store_type::size_type | size_type |
Type of the size. More... | |
typedef btree_iterator < state_type > | iterator |
Iterator type. More... | |
Public Member Functions | |
iterator | begin () const |
Returns an iterator pointing to the beginning of the tree. More... | |
iterator | end () const |
Returns an iterator pointing to the end of the tree. More... | |
template<typename X = enab> | |
void | insert (value_type v, enable< X,!is_static >=enab()) |
Insert given value into the btree. More... | |
template<typename K , typename X = enab> | |
iterator | find (K v, enable< X, is_ordered >=enab()) const |
Return an iterator to the first item with the given key. More... | |
template<typename K , typename X = enab> | |
iterator | lower_bound (K v, enable< X, is_ordered >=enab()) const |
Return an interator to the first element that is "not less" than the given key. More... | |
template<typename K , typename X = enab> | |
iterator | upper_bound (K v, enable< X, is_ordered >=enab()) const |
Return an interator to the first element that is "greater" than the given key. More... | |
template<typename X = enab> | |
void | erase (const iterator &itr, enable< X,!is_static >=enab()) |
remove item at iterator More... | |
template<typename X = enab> | |
size_type | erase (key_type v, enable< X,!is_static &&is_ordered >=enab()) |
remove all items with given key More... | |
node_type | root () const |
Return the root node. More... | |
size_type | size () const throw () |
Return the number of elements in the tree. More... | |
bool | empty () const throw () |
Check if the tree is empty. More... | |
void | set_metadata (const std::string &data) |
std::string | get_metadata () |
template<typename X = enab> | |
tree (std::string path, comp_type comp=comp_type(), augmenter_type augmenter=augmenter_type(), enable< X,!is_internal >=enab()) | |
Construct a btree with the given storage. More... | |
template<typename X = enab> | |
tree (comp_type comp=comp_type(), augmenter_type augmenter=augmenter_type(), memory_bucket_ref bucket=memory_bucket_ref(), enable< X, is_internal >=enab()) | |
Construct a btree with the given storage. More... | |
const comp_type & | comp () const |
Static Public Attributes | |
static const bool | is_internal = state_type::is_internal |
static const bool | is_static = state_type::is_static |
static const bool | is_ordered = state_type::is_ordered |
Friends | |
class | bbits::builder< T, O > |
Augmented btree.
External or internal augmented btree.
The fanout and location of nodes is decided by the store type S C is the item comparator type A is the type of the augmentation computation fuctor
typedef btree_iterator<state_type> tpie::bbits::tree< T, O >::iterator |
typedef state_type::key_type tpie::bbits::tree< T, O >::key_type |
typedef btree_node<state_type> tpie::bbits::tree< T, O >::node_type |
typedef store_type::size_type tpie::bbits::tree< T, O >::size_type |
typedef state_type::value_type tpie::bbits::tree< T, O >::value_type |
|
inlineexplicit |
|
inlineexplicit |
|
inline |
Returns an iterator pointing to the beginning of the tree.
Definition at line 266 of file btree.h.
|
inline |
|
inline |
Returns an iterator pointing to the end of the tree.
Definition at line 275 of file btree.h.
Referenced by tpie::bbits::tree< T, O >::erase().
|
inline |
remove item at iterator
Definition at line 456 of file btree.h.
Referenced by tpie::bbits::tree< T, O >::erase().
|
inline |
remove all items with given key
Definition at line 545 of file btree.h.
References tpie::bbits::tree< T, O >::end(), tpie::bbits::tree< T, O >::erase(), and tpie::bbits::tree< T, O >::find().
|
inline |
Return an iterator to the first item with the given key.
Definition at line 374 of file btree.h.
Referenced by tpie::bbits::tree< T, O >::erase().
|
inline |
|
inline |
Return an interator to the first element that is "not less" than the given key.
Definition at line 405 of file btree.h.
|
inline |
Return the root node.
Definition at line 561 of file btree.h.
|
inline |
|
inline |
Return an interator to the first element that is "greater" than the given key.
Definition at line 431 of file btree.h.