|
Fairport
v1.0.38
|
A BTree Node. More...
#include <btree.h>
Inheritance diagram for fairport::btree_node< K, V >:Public Types | |
| typedef const_btree_node_iter < K, V > | const_iterator |
Public Member Functions | |
| virtual | ~btree_node () |
| virtual const V & | lookup (const K &key) const =0 |
| Looks up the associated value for a given key. | |
| virtual const K & | get_key (uint pos) const =0 |
| Returns the key at the specified position. | |
| virtual uint | num_values () const =0 |
| Returns the number of entries in this btree_node. | |
| const_iterator | begin () const |
| Returns a STL style iterator positioned at the first entry. | |
| const_iterator | end () const |
| Returns a STL style iterator positioned at the "end" entry. | |
| int | binary_search (const K &key) const |
| Performs a binary search over the keys of this btree_node. | |
Protected Member Functions | |
| virtual void | first (btree_iter_impl< K, V > &iter) const =0 |
| Positions the iterator at the first element on this tree. | |
| virtual void | last (btree_iter_impl< K, V > &iter) const =0 |
| Positions the iterator at the "end" element. | |
| virtual void | next (btree_iter_impl< K, V > &iter) const =0 |
| Moves the iterator to the next element. | |
| virtual void | prev (btree_iter_impl< K, V > &iter) const =0 |
| Moves the iterator to the previous element. | |
Friends | |
| class | const_btree_node_iter< K, V > |
| class | btree_node_nonleaf< K, V > |
A BTree Node.
The fundamental type in the BTree system is the btree_node. It provides the generic interface which is refined by the other classes.
| K | The key type. Must be LessThan comparable. |
| V | The value type |
| typedef const_btree_node_iter<K,V> fairport::btree_node< K, V >::const_iterator |
| virtual fairport::btree_node< K, V >::~btree_node | ( | ) | [inline, virtual] |
| const_iterator fairport::btree_node< K, V >::begin | ( | ) | const [inline] |
| int fairport::btree_node< K, V >::binary_search | ( | const K & | key | ) | const |
Performs a binary search over the keys of this btree_node.
| [in] | key | The key to lookup |
| const_iterator fairport::btree_node< K, V >::end | ( | ) | const [inline] |
| virtual void fairport::btree_node< K, V >::first | ( | btree_iter_impl< K, V > & | iter | ) | const [protected, pure virtual] |
Positions the iterator at the first element on this tree.
| [in,out] | iter | Iterator state class |
Implemented in fairport::btree_node_nonleaf< K, V >, and fairport::btree_node_leaf< K, V >.
| virtual const K& fairport::btree_node< K, V >::get_key | ( | uint | pos | ) | const [pure virtual] |
Returns the key at the specified position.
This is specific to this btree_node, not the entire tree
| [in] | pos | The position to retrieve the key for |
Implemented in fairport::subnode_leaf_block, fairport::subnode_nonleaf_block, fairport::bth_leaf_node< K, V >, fairport::bth_nonleaf_node< K, V >, fairport::bt_leaf_page< K, V >, and fairport::bt_nonleaf_page< K, V >.
| virtual void fairport::btree_node< K, V >::last | ( | btree_iter_impl< K, V > & | iter | ) | const [protected, pure virtual] |
Positions the iterator at the "end" element.
| [in,out] | iter | Iterator state class |
Implemented in fairport::btree_node_nonleaf< K, V >, and fairport::btree_node_leaf< K, V >.
| virtual const V& fairport::btree_node< K, V >::lookup | ( | const K & | key | ) | const [pure virtual] |
Looks up the associated value for a given key.
This will defer to child btree_nodes as appropriate
| key_not_found<K> | if the requested key is not in this btree |
| [in] | key | The key to lookup |
Implemented in fairport::btree_node_nonleaf< K, V >, and fairport::btree_node_leaf< K, V >.
| virtual void fairport::btree_node< K, V >::next | ( | btree_iter_impl< K, V > & | iter | ) | const [protected, pure virtual] |
Moves the iterator to the next element.
| [in,out] | iter | Iterator state class |
Implemented in fairport::btree_node_nonleaf< K, V >, and fairport::btree_node_leaf< K, V >.
| virtual uint fairport::btree_node< K, V >::num_values | ( | ) | const [pure virtual] |
Returns the number of entries in this btree_node.
This is specific to this btree_node, not the entire tree
Implemented in fairport::subnode_leaf_block, fairport::subnode_nonleaf_block, fairport::bth_leaf_node< K, V >, fairport::bth_nonleaf_node< K, V >, fairport::bt_leaf_page< K, V >, and fairport::bt_nonleaf_page< K, V >.
| virtual void fairport::btree_node< K, V >::prev | ( | btree_iter_impl< K, V > & | iter | ) | const [protected, pure virtual] |
Moves the iterator to the previous element.
| [in,out] | iter | Iterator state class |
Implemented in fairport::btree_node_nonleaf< K, V >, and fairport::btree_node_leaf< K, V >.
friend class btree_node_nonleaf< K, V > [friend] |
friend class const_btree_node_iter< K, V > [friend] |