Classes | Public Types | Public Member Functions | Static Public Member Functions | Private Types | Private Member Functions | Static Private Member Functions | Private Attributes | List of all members
gtsam::BTree< KEY, VALUE > Class Template Reference

#include <BTree.h>

Classes

class  const_iterator
 Const iterator Not trivial: iterator keeps a stack to indicate current path from root_. More...
 
struct  Node
 

Public Types

typedef const_iterator iterator
 
typedef std::pair< KEY, VALUE > value_type
 

Public Member Functions

BTree add (const value_type &xd) const
 
BTree add (const KEY &x, const VALUE &d) const
 
const_iterator begin () const
 
 BTree ()
 
 BTree (const BTree &other)
 
 BTree (const value_type &keyValue)
 
 BTree (const BTree &l, const value_type &keyValue, const BTree &r)
 
bool empty () const
 
const_iterator end () const
 
const VALUE & find (const KEY &k) const
 
template<class ACC >
ACC fold (boost::function< ACC(const KEY &, const VALUE &, const ACC &)> f, const ACC &a) const
 
size_t height () const
 
void iter (boost::function< void(const KEY &, const VALUE &)> f) const
 
template<class TO >
BTree< KEY, TO > map (boost::function< TO(const KEY &, const VALUE &)> f) const
 
bool mem (const KEY &x) const
 
const value_typemin () const
 
bool operator!= (const BTree &other) const
 
BTreeoperator= (const BTree &other)
 
bool operator== (const BTree &other) const
 
void print (const std::string &s="") const
 
BTree remove (const KEY &x) const
 
BTree remove_min () const
 
bool same (const BTree &other) const
 
size_t size () const
 

Static Public Member Functions

static BTree merge (const BTree &t1, const BTree &t2)
 

Private Types

typedef boost::shared_ptr< const NodesharedNode
 

Private Member Functions

const KEY & key () const
 
const value_typekeyValue () const
 
const BTreeleft () const
 
const BTreeright () const
 
const VALUE & value () const
 

Static Private Member Functions

static BTree balance (const BTree &l, const value_type &xd, const BTree &r)
 

Private Attributes

sharedNode root_
 

Detailed Description

template<class KEY, class VALUE>
class gtsam::BTree< KEY, VALUE >

Definition at line 32 of file BTree.h.

Member Typedef Documentation

template<class KEY, class VALUE>
typedef const_iterator gtsam::BTree< KEY, VALUE >::iterator

Definition at line 400 of file BTree.h.

template<class KEY, class VALUE>
typedef boost::shared_ptr<const Node> gtsam::BTree< KEY, VALUE >::sharedNode
private

Definition at line 76 of file BTree.h.

template<class KEY, class VALUE>
typedef std::pair<KEY, VALUE> gtsam::BTree< KEY, VALUE >::value_type

Definition at line 36 of file BTree.h.

Constructor & Destructor Documentation

template<class KEY, class VALUE>
gtsam::BTree< KEY, VALUE >::BTree ( )
inline

default constructor creates an empty tree

Definition at line 113 of file BTree.h.

template<class KEY, class VALUE>
gtsam::BTree< KEY, VALUE >::BTree ( const BTree< KEY, VALUE > &  other)
inline

copy constructor

Definition at line 117 of file BTree.h.

template<class KEY, class VALUE>
gtsam::BTree< KEY, VALUE >::BTree ( const value_type keyValue)
inline

create leaf from key-value pair

Definition at line 122 of file BTree.h.

template<class KEY, class VALUE>
gtsam::BTree< KEY, VALUE >::BTree ( const BTree< KEY, VALUE > &  l,
const value_type keyValue,
const BTree< KEY, VALUE > &  r 
)
inline

create from key-value pair and left, right subtrees

Definition at line 127 of file BTree.h.

Member Function Documentation

template<class KEY, class VALUE>
BTree gtsam::BTree< KEY, VALUE >::add ( const value_type xd) const
inline

add a key-value pair

Definition at line 143 of file BTree.h.

template<class KEY, class VALUE>
BTree gtsam::BTree< KEY, VALUE >::add ( const KEY &  x,
const VALUE &  d 
) const
inline

add a key-value pair

Definition at line 155 of file BTree.h.

template<class KEY, class VALUE>
static BTree gtsam::BTree< KEY, VALUE >::balance ( const BTree< KEY, VALUE > &  l,
const value_type xd,
const BTree< KEY, VALUE > &  r 
)
inlinestaticprivate

create a new balanced tree out of two trees and a key-value pair

Definition at line 86 of file BTree.h.

template<class KEY, class VALUE>
const_iterator gtsam::BTree< KEY, VALUE >::begin ( ) const
inline

return iterator

Definition at line 403 of file BTree.h.

template<class KEY, class VALUE>
bool gtsam::BTree< KEY, VALUE >::empty ( ) const
inline

Check whether tree is empty

Definition at line 138 of file BTree.h.

template<class KEY, class VALUE>
const_iterator gtsam::BTree< KEY, VALUE >::end ( ) const
inline

return iterator

Definition at line 408 of file BTree.h.

template<class KEY, class VALUE>
const VALUE& gtsam::BTree< KEY, VALUE >::find ( const KEY &  k) const
inline

find a value given a key, throws exception when not found Optimized non-recursive version as [find] is crucial for speed

Definition at line 239 of file BTree.h.

template<class KEY, class VALUE>
template<class ACC >
ACC gtsam::BTree< KEY, VALUE >::fold ( boost::function< ACC(const KEY &, const VALUE &, const ACC &)>  f,
const ACC &  a 
) const
inline

t.fold(f,a) computes [(f kN dN ... (f k1 d1 a)...)], where [k1 ... kN] are the keys of all bindings in [m], and [d1 ... dN] are the associated data. The associated values are passed to [f] in reverse sort order

Definition at line 285 of file BTree.h.

template<class KEY, class VALUE>
size_t gtsam::BTree< KEY, VALUE >::height ( ) const
inline

Return height of the tree, 0 if empty

Definition at line 225 of file BTree.h.

template<class KEY, class VALUE>
void gtsam::BTree< KEY, VALUE >::iter ( boost::function< void(const KEY &, const VALUE &)>  f) const
inline

iterate over tree

Definition at line 263 of file BTree.h.

template<class KEY, class VALUE>
const KEY& gtsam::BTree< KEY, VALUE >::key ( ) const
inlineprivate

Definition at line 80 of file BTree.h.

template<class KEY, class VALUE>
const value_type& gtsam::BTree< KEY, VALUE >::keyValue ( ) const
inlineprivate

Definition at line 79 of file BTree.h.

template<class KEY, class VALUE>
const BTree& gtsam::BTree< KEY, VALUE >::left ( ) const
inlineprivate

Definition at line 82 of file BTree.h.

template<class KEY, class VALUE>
template<class TO >
BTree<KEY, TO> gtsam::BTree< KEY, VALUE >::map ( boost::function< TO(const KEY &, const VALUE &)>  f) const
inline

map key-values in tree over function f that computes a new value

Definition at line 272 of file BTree.h.

template<class KEY, class VALUE>
bool gtsam::BTree< KEY, VALUE >::mem ( const KEY &  x) const
inline

member predicate

Definition at line 160 of file BTree.h.

template<class KEY, class VALUE>
static BTree gtsam::BTree< KEY, VALUE >::merge ( const BTree< KEY, VALUE > &  t1,
const BTree< KEY, VALUE > &  t2 
)
inlinestatic

merge two trees

Definition at line 206 of file BTree.h.

template<class KEY, class VALUE>
const value_type& gtsam::BTree< KEY, VALUE >::min ( ) const
inline

minimum key binding

Definition at line 192 of file BTree.h.

template<class KEY, class VALUE>
bool gtsam::BTree< KEY, VALUE >::operator!= ( const BTree< KEY, VALUE > &  other) const
inline

Definition at line 187 of file BTree.h.

template<class KEY, class VALUE>
BTree& gtsam::BTree< KEY, VALUE >::operator= ( const BTree< KEY, VALUE > &  other)
inline

assignment operator

Definition at line 132 of file BTree.h.

template<class KEY, class VALUE>
bool gtsam::BTree< KEY, VALUE >::operator== ( const BTree< KEY, VALUE > &  other) const
inline

Check whether trees are structurally the same, i.e., contain the same values in same tree-structure.

Definition at line 178 of file BTree.h.

template<class KEY, class VALUE>
void gtsam::BTree< KEY, VALUE >::print ( const std::string &  s = "") const
inline

print in-order

Definition at line 252 of file BTree.h.

template<class KEY, class VALUE>
BTree gtsam::BTree< KEY, VALUE >::remove ( const KEY &  x) const
inline

remove a key-value pair

Definition at line 214 of file BTree.h.

template<class KEY, class VALUE>
BTree gtsam::BTree< KEY, VALUE >::remove_min ( ) const
inline

remove minimum key binding

Definition at line 199 of file BTree.h.

template<class KEY, class VALUE>
const BTree& gtsam::BTree< KEY, VALUE >::right ( void  ) const
inlineprivate

Definition at line 83 of file BTree.h.

template<class KEY, class VALUE>
bool gtsam::BTree< KEY, VALUE >::same ( const BTree< KEY, VALUE > &  other) const
inline

Check whether trees are exactly the same (occupy same memory)

Definition at line 170 of file BTree.h.

template<class KEY, class VALUE>
size_t gtsam::BTree< KEY, VALUE >::size ( ) const
inline

return size of the tree

Definition at line 230 of file BTree.h.

template<class KEY, class VALUE>
const VALUE& gtsam::BTree< KEY, VALUE >::value ( ) const
inlineprivate

Definition at line 81 of file BTree.h.

Member Data Documentation

template<class KEY, class VALUE>
sharedNode gtsam::BTree< KEY, VALUE >::root_
private

Definition at line 77 of file BTree.h.


The documentation for this class was generated from the following file:


gtsam
Author(s):
autogenerated on Sat May 8 2021 02:58:04