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

Binary tree. More...

#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 (std::function< ACC(const KEY &, const VALUE &, const ACC &)> f, const ACC &a) const
 
size_t height () const
 
void iter (std::function< void(const KEY &, const VALUE &)> f) const
 
template<class TO >
BTree< KEY, TO > map (std::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 std::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 >

Binary tree.

Definition at line 34 of file BTree.h.

Member Typedef Documentation

◆ iterator

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

Definition at line 402 of file BTree.h.

◆ sharedNode

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

Definition at line 78 of file BTree.h.

◆ value_type

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

Definition at line 38 of file BTree.h.

Constructor & Destructor Documentation

◆ BTree() [1/4]

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

default constructor creates an empty tree

Definition at line 115 of file BTree.h.

◆ BTree() [2/4]

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

copy constructor

Definition at line 119 of file BTree.h.

◆ BTree() [3/4]

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

create leaf from key-value pair

Definition at line 124 of file BTree.h.

◆ BTree() [4/4]

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 129 of file BTree.h.

Member Function Documentation

◆ add() [1/2]

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 145 of file BTree.h.

◆ add() [2/2]

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 157 of file BTree.h.

◆ balance()

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 88 of file BTree.h.

◆ begin()

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

return iterator

Definition at line 405 of file BTree.h.

◆ empty()

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

Check whether tree is empty

Definition at line 140 of file BTree.h.

◆ end()

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

return iterator

Definition at line 410 of file BTree.h.

◆ find()

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 241 of file BTree.h.

◆ fold()

template<class KEY, class VALUE>
template<class ACC >
ACC gtsam::BTree< KEY, VALUE >::fold ( std::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 287 of file BTree.h.

◆ height()

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 227 of file BTree.h.

◆ iter()

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

iterate over tree

Definition at line 265 of file BTree.h.

◆ key()

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

Definition at line 82 of file BTree.h.

◆ keyValue()

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

Definition at line 81 of file BTree.h.

◆ left()

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

Definition at line 84 of file BTree.h.

◆ map()

template<class KEY, class VALUE>
template<class TO >
BTree<KEY, TO> gtsam::BTree< KEY, VALUE >::map ( std::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 274 of file BTree.h.

◆ mem()

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

member predicate

Definition at line 162 of file BTree.h.

◆ merge()

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 208 of file BTree.h.

◆ min()

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

minimum key binding

Definition at line 194 of file BTree.h.

◆ operator!=()

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

Definition at line 189 of file BTree.h.

◆ operator=()

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

assignment operator

Definition at line 134 of file BTree.h.

◆ operator==()

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 180 of file BTree.h.

◆ print()

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

print in-order

Definition at line 254 of file BTree.h.

◆ remove()

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

remove a key-value pair

Definition at line 216 of file BTree.h.

◆ remove_min()

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

remove minimum key binding

Definition at line 201 of file BTree.h.

◆ right()

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

Definition at line 85 of file BTree.h.

◆ same()

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 172 of file BTree.h.

◆ size()

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

return size of the tree

Definition at line 232 of file BTree.h.

◆ value()

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

Definition at line 83 of file BTree.h.

Member Data Documentation

◆ root_

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

Definition at line 79 of file BTree.h.


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


gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:46:15