TPIE

11a2c2d
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 NT >
void createNewRoot (NT left, NT right)
 
template<typename X = enab>
void insert_before (value_type v, const iterator &itr, enable< X, !is_static >=enab())
 Insert given value into the btree before iterator. 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 238 of file base.h.

Member Typedef Documentation

◆ iterator

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.

◆ key_type

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.

◆ node_type

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.

◆ size_type

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.

◆ value_type

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

◆ tree() [1/2]

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 597 of file btree.h.

597  :
598  m_state(store_type(path), std::move(augmenter), keyextract_type()),
599  m_comp(comp) {}

◆ tree() [2/2]

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 605 of file btree.h.

608  :
609  m_state(store_type(bucket), std::move(augmenter), keyextract_type()),
610  m_comp(comp) {}

Member Function Documentation

◆ begin()

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 270 of file btree.h.

270  {
271  iterator i(&m_state);
272  i.goto_begin();
273  return i;
274  }

◆ empty()

template<typename T , typename O >
bool tpie::bbits::tree< T, O >::empty ( ) const
throw (
)
inline

Check if the tree is empty.

Definition at line 581 of file btree.h.

581  {
582  return m_state.store().size() == 0;
583  }

◆ end()

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 279 of file btree.h.

279  {
280  iterator i(&m_state);
281  i.goto_end();
282  return i;
283  }

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

◆ erase() [1/2]

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 461 of file btree.h.

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

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

◆ erase() [2/2]

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 550 of file btree.h.

550  {
551  size_type count = 0;
552  iterator i = find(v);
553  while(i != end()) {
554  erase(i);
555  ++count;
556  i = find(v);
557  }
558 
559  return count;
560  }

References tpie::bbits::tree< T, O >::end(), tpie::bbits::tree< T, O >::erase(), and tpie::bbits::tree< T, O >::find().

◆ find()

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 379 of file btree.h.

379  {
380  iterator itr(&m_state);
381 
382  if(m_state.store().height() == 0) {
383  itr.goto_end();
384  return itr;
385  }
386 
387  std::vector<internal_type> path;
388  leaf_type l = find_leaf<true>(path, v);
389 
390  size_t i=0;
391  size_t z = m_state.store().count(l);
392  while (true) {
393  if (i == z) {
394  itr.goto_end();
395  return itr;
396  }
397  if (!m_comp(m_state.min_key(l, i), v) &&
398  !m_comp(v, m_state.min_key(l, i))) break;
399  ++i;
400  }
401  itr.goto_item(path, l, i);
402  return itr;
403  }

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

◆ insert()

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 371 of file btree.h.

371  {
372  insert_before(v, upper_bound(m_state.m_augmenter.m_key_extract(v)));
373  }

References tpie::bbits::tree< T, O >::insert_before(), and tpie::bbits::tree< T, O >::upper_bound().

◆ insert_before()

template<typename T , typename O >
template<typename X = enab>
void tpie::bbits::tree< T, O >::insert_before ( value_type  v,
const iterator &  itr,
enable< X, !is_static >  = enab() 
)
inline

Insert given value into the btree before iterator.

Definition at line 302 of file btree.h.

302  {
303  m_state.store().set_size(m_state.store().size() + 1);
304 
305  // Handle the special case of the empty tree
306  if (m_state.store().height() == 0) {
307  leaf_type n = m_state.store().create_leaf();
308  m_state.store().set_count(n, 1);
309  m_state.store().set(n, 0, v);
310  m_state.store().set_height(1);
311  m_state.store().set_root(n);
312  return;
313  }
314 
315  const auto path = itr.m_path.data();
316  auto index = itr.index();
317  auto level = itr.m_path.size();
318 
319  //If there is room in the leaf
320  if (m_state.store().count(itr.m_leaf) != m_state.store().max_leaf_size()) {
321  insert_part(itr.m_leaf, v, index);
322  if (level != 0) {
323  augment(itr.m_leaf, path[level-1]);
324  augment_path(path, level-1);
325  }
326  return;
327  }
328 
329  // We split the leaf
330  leaf_type l2 = split_and_insert(v, itr.m_leaf, index);
331 
332  // If the leaf was a root leaf we create a new root
333  if (level == 0) {
334  createNewRoot(itr.m_leaf, l2);
335  return;
336  }
337  --level;
338  index = m_state.store().index(itr.m_leaf, path[level]) + 1;
339 
340  augment(itr.m_leaf, path[level]);
341 
342  //If there is room in the parent to insert the extra leave
343  if (m_state.store().count(path[level]) != m_state.store().max_internal_size()) {
344  insert_part(path[level], l2, index);
345  augment_path(path, level);
346  return;
347  }
348 
349  internal_type n2 = split_and_insert(l2, path[level], index);
350  while (level != 0) {
351  --level;
352  index = m_state.store().index(path[level+1], path[level]) + 1;
353  augment(path[level+1], path[level]);
354  if (m_state.store().count(path[level]) != m_state.store().max_internal_size()) {
355  insert_part(path[level], n2, index);
356  augment_path(path, level);
357  return;
358  }
359  n2 = split_and_insert(n2, path[level], index);
360  }
361 
362  //We need a new root
363  createNewRoot(path[0], n2);
364  }

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

◆ lower_bound()

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 410 of file btree.h.

410  {
411  iterator itr(&m_state);
412  if (m_state.store().height() == 0) {
413  itr.goto_end();
414  return itr;
415  }
416 
417  std::vector<internal_type> path;
418  leaf_type l = find_leaf(path, v);
419 
420  const size_t z = m_state.store().count(l);
421  for (size_t i = 0 ; i < z ; ++i) {
422  if (!m_comp(m_state.min_key(l, i), v)) {
423  itr.goto_item(path, l, i);
424  return itr;
425  }
426  }
427  itr.goto_item(path, l, z-1);
428  return ++itr;
429  }

◆ root()

template<typename T , typename O >
node_type tpie::bbits::tree< T, O >::root ( ) const
inline

Return the root node.

Precondition
!empty()

Definition at line 566 of file btree.h.

566  {
567  if (m_state.store().height() == 1) return node_type(&m_state, m_state.store().get_root_leaf());
568  return node_type(&m_state, m_state.store().get_root_internal());
569  }

◆ size()

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 574 of file btree.h.

574  {
575  return m_state.store().size();
576  }

◆ upper_bound()

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 436 of file btree.h.

436  {
437  iterator itr(&m_state);
438  if (m_state.store().height() == 0) {
439  itr.goto_end();
440  return itr;
441  }
442 
443  std::vector<internal_type> path;
444  leaf_type l = find_leaf<true>(path, v);
445 
446  const size_t z = m_state.store().count(l);
447  for (size_t i = 0 ; i < z ; ++i) {
448  if (m_comp(v, m_state.min_key(l, i))) {
449  itr.goto_item(path, l, i);
450  return itr;
451  }
452  }
453  itr.goto_item(path, l, z-1);
454  return ++itr;
455  }

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

The documentation for this class was generated from the following files:
tpie::bbits::tree::insert_before
void insert_before(value_type v, const iterator &itr, enable< X, !is_static >=enab())
Insert given value into the btree before iterator.
Definition: btree.h:302
tpie::bbits::tree::node_type
btree_node< state_type > node_type
Type of node wrapper.
Definition: btree.h:70
tpie::bbits::tree::erase
void erase(const iterator &itr, enable< X, !is_static >=enab())
remove item at iterator
Definition: btree.h:461
tpie::bbits::tree::iterator
btree_iterator< state_type > iterator
Iterator type.
Definition: btree.h:80
tpie::bbits::tree::size_type
store_type::size_type size_type
Type of the size.
Definition: btree.h:75
tpie::bbits::tree::end
iterator end() const
Returns an iterator pointing to the end of the tree.
Definition: btree.h:279
tpie::bbits::tree::upper_bound
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.
Definition: btree.h:436
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:379