20 #ifndef _TPIE_BTREE_NODE_H_
21 #define _TPIE_BTREE_NODE_H_
25 #include <tpie/btree/base.h>
26 #include <boost/iterator/iterator_facade.hpp>
58 typedef typename S::store_type store_type;
67 return !m_path.empty();
69 return m_path.size() > 1;
92 if (m_path.size() + 1 == m_state->store().height()) {
94 m_leaf = m_state->store().get_child_leaf(m_path.back(), i);
96 m_path.push_back(m_state->store().get_child_internal(m_path.back(), i));
134 return state_type::user_augment(m_state->store().augment(m_path.back(), i));
142 return m_state->min_key(m_leaf, i);
144 return m_state->min_key(m_path.back(), i);
154 return m_state->store().get(m_leaf, i);
162 return m_state->store().count(m_leaf);
164 return m_state->store().count(m_path.back());
174 return m_state->store().index(m_leaf, m_path.back());
175 return m_state->store().index(m_path.back(), m_path[m_path.size()-2]);
181 const typename state_type::combined_augment & get_combined_augmentation(
size_t i)
const {
182 return m_state->store().augment(m_path.back(), i);
186 typedef typename store_type::leaf_type leaf_type;
187 typedef typename store_type::internal_type internal_type;
189 btree_node(
const state_type * state, leaf_type root)
190 : m_state(state), m_leaf(root), m_is_leaf(true) {
193 btree_node(
const state_type * state, internal_type root)
194 : m_state(state), m_is_leaf(false) {
195 m_path.push_back(root);
198 btree_node(
const state_type * state, std::vector<internal_type> path, leaf_type leaf)
199 : m_state(state), m_path(path), m_leaf(leaf), m_is_leaf(true) {
202 const state_type * m_state;
203 std::vector<internal_type> m_path;
207 template <
typename,
typename>
208 friend class bbits::tree_state;
210 template <
typename,
typename>
211 friend class bbits::tree;
213 template <
typename,
typename>
214 friend class bbits::builder;
217 friend class btree_iterator;
220 template <
typename S>
221 class btree_iterator:
public boost::iterator_facade<
223 typename S::value_type const,
224 boost::bidirectional_traversal_tag> {
229 typedef typename S::value_type value_type;
232 typedef S state_type;
233 typedef typename S::store_type store_type;
234 typedef typename store_type::internal_type internal_type;
235 typedef typename store_type::leaf_type leaf_type;
236 typedef typename S::key_type key_type;
238 const state_type * m_state;
239 std::vector<internal_type> m_path;
243 template <
typename,
typename>
244 friend class bbits::tree;
246 btree_iterator(
const state_type * state): m_state(state) {}
248 void goto_item(
const std::vector<internal_type> & p, leaf_type l,
size_t i) {
257 if (m_state->store().height() < 2) {
258 m_leaf = m_state->store().get_root_leaf();
262 internal_type n = m_state->store().get_root_internal();
263 for (
size_t i=2;; ++i) {
265 if (i == m_state->store().height()) {
266 m_leaf = m_state->store().get_child_leaf(n, 0);
270 n = m_state->store().get_child_internal(n, 0);
277 if(m_state->store().height() == 0) {
278 m_leaf = m_state->store().get_root_leaf();
283 if (m_state->store().height() == 1) {
284 m_leaf = m_state->store().get_root_leaf();
285 m_index = m_state->store().count(m_leaf);
288 internal_type n = m_state->store().get_root_internal();
289 for (
size_t i=2;; ++i) {
291 if (i == m_state->store().height()) {
292 m_leaf = m_state->store().get_child_leaf(n, m_state->store().count(n)-1);
293 m_index = m_state->store().count(m_leaf);
296 n = m_state->store().get_child_internal(n, m_state->store().count(n)-1);
302 btree_iterator(): m_index(0), m_leaf() {}
304 const value_type & dereference()
const {
305 return m_state->store().get(m_leaf, m_index);
308 bool equal(
const btree_iterator & o)
const {
309 return m_index == o.m_index && m_leaf == o.m_leaf;
312 size_t index()
const {
return m_index;}
314 btree_node<S> get_leaf()
const {
315 return btree_node<S>(m_state, m_path, m_leaf);
324 size_t i=m_state->store().index(m_leaf, m_path.back());
327 internal_type n = m_path.back();
329 i = m_state->store().index(n, m_path.back());
335 m_path.push_back(m_state->store().get_child_internal(m_path.back(), i));
336 i = m_state->store().count(m_path.back())-1;
340 m_leaf = m_state->store().get_child_leaf(m_path.back(), i);
341 m_index = m_state->store().count(m_leaf)-1;
346 if (m_index < m_state->store().count(m_leaf))
return;
347 if (m_path.empty())
return;
349 size_t i=m_state->store().index(m_leaf, m_path.back());
351 while (i +1 == m_state->store().count(m_path.back())) {
352 internal_type n = m_path.back();
354 if (m_path.empty()) {
358 i = m_state->store().index(n, m_path.back());
363 m_path.push_back(m_state->store().get_child_internal(m_path.back(), i));
367 m_leaf = m_state->store().get_child_leaf(m_path.back(), i);
375 #endif //_TPIE_BTREE_NODE_H_
Defines the tp_assert macro.
btree_node get_child(size_t i) const
Return the ith child node.
S::augment_type augment_type
Type of the augment of a set of nodes/values.
bool has_parent() const
Check if this node has a parent.
This file contains a few deprecated definitions for legacy code.
void child(size_t i)
Move to the ith child.
key_type min_key(size_t i) const
Return the minimal key of the i'th child.
const value_type & value(size_t i) const
Return the i'th value.
size_t index() const
Return the index of this node in its parent.
const augment_type & get_augmentation(size_t i) const
Return the augmented data of the ith child.
Type that is useful for navigating a btree.
#define tp_assert(condition, message)
S::key_type key_type
Type of the key of a value.
btree_node get_parent() const
Return the parent node.
void parent()
Move to the parent node.
S::value_type value_type
Type of values.
bool is_leaf() const
Return true if this is a leaf node.
size_t count() const
Return the number of children or values.