TPIE

2362a60
Public Types | Public Member Functions | Static Public Attributes | Friends | List of all members
tpie::bbits::tree< T, O > Class Template Reference

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 >
 

Detailed Description

template<typename T, typename O>
class tpie::bbits::tree< 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

Definition at line 195 of file base.h.

Member Typedef Documentation

template<typename T , typename O >
typedef btree_iterator<state_type> tpie::bbits::tree< T, O >::iterator

Iterator type.

Definition at line 80 of file btree.h.

template<typename T , typename O >
typedef state_type::key_type tpie::bbits::tree< T, O >::key_type

The type of key used.

Definition at line 60 of file btree.h.

template<typename T , typename O >
typedef btree_node<state_type> tpie::bbits::tree< T, O >::node_type

Type of node wrapper.

Definition at line 70 of file btree.h.

template<typename T , typename O >
typedef store_type::size_type tpie::bbits::tree< T, O >::size_type

Type of the size.

Definition at line 75 of file btree.h.

template<typename T , typename O >
typedef state_type::value_type tpie::bbits::tree< T, O >::value_type

Type of value stored.

Definition at line 51 of file btree.h.

Constructor & Destructor Documentation

template<typename T , typename O >
template<typename X = enab>
tpie::bbits::tree< T, O >::tree ( std::string  path,
comp_type  comp = comp_type(),
augmenter_type  augmenter = augmenter_type(),
enable< X,!is_internal >  = enab() 
)
inlineexplicit

Construct a btree with the given storage.

Definition at line 592 of file btree.h.

592  :
593  m_state(store_type(path), std::move(augmenter), keyextract_type()),
594  m_comp(comp) {}
template<typename T , typename O >
template<typename X = enab>
tpie::bbits::tree< T, O >::tree ( comp_type  comp = comp_type(),
augmenter_type  augmenter = augmenter_type(),
memory_bucket_ref  bucket = memory_bucket_ref(),
enable< X, is_internal >  = enab() 
)
inlineexplicit

Construct a btree with the given storage.

Definition at line 600 of file btree.h.

603  :
604  m_state(store_type(bucket), std::move(augmenter), keyextract_type()),
605  m_comp(comp) {}

Member Function Documentation

template<typename T , typename O >
iterator tpie::bbits::tree< T, O >::begin ( ) const
inline

Returns an iterator pointing to the beginning of the tree.

Definition at line 266 of file btree.h.

266  {
267  iterator i(&m_state);
268  i.goto_begin();
269  return i;
270  }
tpie::bbits::tree::iterator
btree_iterator< state_type > iterator
Iterator type.
Definition: btree.h:80
template<typename T , typename O >
bool tpie::bbits::tree< T, O >::empty ( ) const
throw (
)
inline

Check if the tree is empty.

Definition at line 576 of file btree.h.

576  {
577  return m_state.store().size() == 0;
578  }
template<typename T , typename O >
iterator tpie::bbits::tree< T, O >::end ( ) const
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().

275  {
276  iterator i(&m_state);
277  i.goto_end();
278  return i;
279  }
tpie::bbits::tree::iterator
btree_iterator< state_type > iterator
Iterator type.
Definition: btree.h:80
template<typename T , typename O >
template<typename X = enab>
void tpie::bbits::tree< T, O >::erase ( const iterator &  itr,
enable< X,!is_static >  = enab() 
)
inline

remove item at iterator

Definition at line 456 of file btree.h.

Referenced by tpie::bbits::tree< T, O >::erase().

456  {
457  std::vector<internal_type> path=itr.m_path;
458  leaf_type l = itr.m_leaf;
459 
460  size_t z = m_state.store().count(l);
461  size_t i = itr.m_index;
462 
463  m_state.store().set_size(m_state.store().size()-1);
464  --z;
465  for (; i != z; ++i)
466  m_state.store().move(l, i+1, l, i);
467  m_state.store().set_count(l, z);
468 
469  // If we still have a large enough size
470  if (z >= m_state.store().min_leaf_size()) {
471  // We are the lone root
472  if (path.empty()) {
473  augment_path(l);
474  return;
475  }
476  augment(l, path.back());
477  augment_path(path);
478  return;
479  }
480 
481  // We are too small but the root
482  if (path.empty()) {
483  // We are now the empty tree
484  if (z == 0) {
485  m_state.store().destroy(l);
486  m_state.store().set_height(0);
487  return;
488  }
489  augment_path(l);
490  return;
491  }
492 
493  // Steal or merge
494  if (remove_fixup_round(l, path.back())) {
495  augment_path(path);
496  return;
497  }
498 
499  // If l is now the only child of the root, make l the root
500  if (path.size() == 1) {
501  if (m_state.store().count(path.back()) == 1) {
502  l = m_state.store().get_child_leaf(path.back(), 0);
503  m_state.store().set_count(path.back(), 0);
504  m_state.store().destroy(path.back());
505  m_state.store().set_height(1);
506  m_state.store().set_root(l);
507  augment_path(l);
508  return;
509  }
510  augment_path(path);
511  return;
512  }
513 
514  while (true) {
515  // We need to handle the parent
516  internal_type p = path.back();
517  path.pop_back();
518  if (remove_fixup_round(p, path.back())) {
519  augment_path(path);
520  return;
521  }
522 
523  if (path.size() == 1) {
524  if (m_state.store().count(path.back()) == 1) {
525  p = m_state.store().get_child_internal(path.back(), 0);
526  m_state.store().set_count(path.back(), 0);
527  m_state.store().destroy(path.back());
528  m_state.store().set_height(m_state.store().height()-1);
529  m_state.store().set_root(p);
530  path.clear();
531  path.push_back(p);
532  augment_path(path);
533  return;
534  }
535  augment_path(path);
536  return;
537  }
538  }
539  }
template<typename T , typename O >
template<typename X = enab>
size_type tpie::bbits::tree< T, O >::erase ( key_type  v,
enable< X,!is_static &&is_ordered >  = enab() 
)
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().

545  {
546  size_type count = 0;
547  iterator i = find(v);
548  while(i != end()) {
549  erase(i);
550  ++count;
551  i = find(v);
552  }
553 
554  return count;
555  }
tpie::bbits::tree::find
iterator find(K v, enable< X, is_ordered >=enab()) const
Return an iterator to the first item with the given key.
Definition: btree.h:374
tpie::bbits::tree::erase
void erase(const iterator &itr, enable< X,!is_static >=enab())
remove item at iterator
Definition: btree.h:456
tpie::bbits::tree::size_type
store_type::size_type size_type
Type of the size.
Definition: btree.h:75
tpie::bbits::tree::iterator
btree_iterator< state_type > iterator
Iterator type.
Definition: btree.h:80
tpie::bbits::tree::end
iterator end() const
Returns an iterator pointing to the end of the tree.
Definition: btree.h:275
template<typename T , typename O >
template<typename K , typename X = enab>
iterator tpie::bbits::tree< T, O >::find ( K  v,
enable< X, is_ordered >  = enab() 
) const
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().

374  {
375  iterator itr(&m_state);
376 
377  if(m_state.store().height() == 0) {
378  itr.goto_end();
379  return itr;
380  }
381 
382  std::vector<internal_type> path;
383  leaf_type l = find_leaf<true>(path, v);
384 
385  size_t i=0;
386  size_t z = m_state.store().count(l);
387  while (true) {
388  if (i == z) {
389  itr.goto_end();
390  return itr;
391  }
392  if (!m_comp(m_state.min_key(l, i), v) &&
393  !m_comp(v, m_state.min_key(l, i))) break;
394  ++i;
395  }
396  itr.goto_item(path, l, i);
397  return itr;
398  }
tpie::bbits::tree::iterator
btree_iterator< state_type > iterator
Iterator type.
Definition: btree.h:80
template<typename T , typename O >
template<typename X = enab>
void tpie::bbits::tree< T, O >::insert ( value_type  v,
enable< X,!is_static >  = enab() 
)
inline

Insert given value into the btree.

Definition at line 285 of file btree.h.

285  {
286  m_state.store().set_size(m_state.store().size() + 1);
287 
288  // Handle the special case of the empty tree
289  if (m_state.store().height() == 0) {
290  leaf_type n = m_state.store().create_leaf();
291  m_state.store().set_count(n, 1);
292  m_state.store().set(n, 0, v);
293  m_state.store().set_height(1);
294  m_state.store().set_root(n);
295  augment_path(n);
296  return;
297  }
298 
299  std::vector<internal_type> path;
300 
301  // Find the leaf contaning the value
302  leaf_type l = find_leaf(path, m_state.min_key(v));
303  //If there is room in the leaf
304  if (m_state.store().count(l) != m_state.store().max_leaf_size()) {
305  insert_part(l, v);
306  if (!path.empty()) augment(l, path.back());
307  augment_path(path);
308  return;
309  }
310 
311  // We split the leaf
312  leaf_type l2 = split_and_insert(v, l);
313 
314  // If the leaf was a root leef we create a new root
315  if (path.empty()) {
316  internal_type i=m_state.store().create_internal();
317  m_state.store().set_count(i, 2);
318  m_state.store().set(i, 0, l);
319  m_state.store().set(i, 1, l2);
320  m_state.store().set_root(i);
321  m_state.store().set_height(m_state.store().height()+1);
322  augment(l, i);
323  augment(l2, i);
324  path.push_back(i);
325  augment_path(path);
326  return;
327  }
328 
329  internal_type p = path.back();
330  augment(l, p);
331 
332  //If there is room in the parent to insert the extra leave
333  if (m_state.store().count(p) != m_state.store().max_internal_size()) {
334  insert_part(p, l2);
335  augment_path(path);
336  return;
337  }
338 
339  path.pop_back();
340  internal_type n2 = split_and_insert(l2, p);
341  internal_type n1 = p;
342 
343  while (!path.empty()) {
344  internal_type p = path.back();
345  augment(n1, p);
346  if (m_state.store().count(p) != m_state.store().max_internal_size()) {
347  insert_part(p, n2);
348  augment_path(path);
349  return;
350  }
351  path.pop_back();
352  n2 = split_and_insert(n2, p);
353  n1 = p;
354 
355  }
356 
357  //We need a new root
358  internal_type i=m_state.store().create_internal();
359  m_state.store().set_count(i, 2);
360  m_state.store().set(i, 0, n1);
361  m_state.store().set(i, 1, n2);
362  m_state.store().set_root(i);
363  m_state.store().set_height(m_state.store().height()+1);
364  augment(n1, i);
365  augment(n2, i);
366  path.push_back(i);
367  augment_path(path);
368  }
template<typename T , typename O >
template<typename K , typename X = enab>
iterator tpie::bbits::tree< T, O >::lower_bound ( K  v,
enable< X, is_ordered >  = enab() 
) const
inline

Return an interator to the first element that is "not less" than the given key.

Definition at line 405 of file btree.h.

405  {
406  iterator itr(&m_state);
407  if (m_state.store().height() == 0) {
408  itr.goto_end();
409  return itr;
410  }
411 
412  std::vector<internal_type> path;
413  leaf_type l = find_leaf(path, v);
414 
415  const size_t z = m_state.store().count(l);
416  for (size_t i = 0 ; i < z ; ++i) {
417  if (!m_comp(m_state.min_key(l, i), v)) {
418  itr.goto_item(path, l, i);
419  return itr;
420  }
421  }
422  itr.goto_item(path, l, z-1);
423  return ++itr;
424  }
tpie::bbits::tree::iterator
btree_iterator< state_type > iterator
Iterator type.
Definition: btree.h:80
template<typename T , typename O >
node_type tpie::bbits::tree< T, O >::root ( ) const
inline

Return the root node.

Precondition
!empty()

Definition at line 561 of file btree.h.

561  {
562  if (m_state.store().height() == 1) return node_type(&m_state, m_state.store().get_root_leaf());
563  return node_type(&m_state, m_state.store().get_root_internal());
564  }
tpie::bbits::tree::node_type
btree_node< state_type > node_type
Type of node wrapper.
Definition: btree.h:70
template<typename T , typename O >
size_type tpie::bbits::tree< T, O >::size ( ) const
throw (
)
inline

Return the number of elements in the tree.

Definition at line 569 of file btree.h.

569  {
570  return m_state.store().size();
571  }
template<typename T , typename O >
template<typename K , typename X = enab>
iterator tpie::bbits::tree< T, O >::upper_bound ( K  v,
enable< X, is_ordered >  = enab() 
) const
inline

Return an interator to the first element that is "greater" than the given key.

Definition at line 431 of file btree.h.

431  {
432  iterator itr(&m_state);
433  if (m_state.store().height() == 0) {
434  itr.goto_end();
435  return itr;
436  }
437 
438  std::vector<internal_type> path;
439  leaf_type l = find_leaf<true>(path, v);
440 
441  const size_t z = m_state.store().count(l);
442  for (size_t i = 0 ; i < z ; ++i) {
443  if (m_comp(v, m_state.min_key(l, i))) {
444  itr.goto_item(path, l, i);
445  return itr;
446  }
447  }
448  itr.goto_item(path, l, z-1);
449  return ++itr;
450  }
tpie::bbits::tree::iterator
btree_iterator< state_type > iterator
Iterator type.
Definition: btree.h:80
The documentation for this class was generated from the following files: