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_type &	min () const

bool	operator!= (const BTree &other) const

BTree &	operator= (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 Node >	sharedNode

Private Member Functions
const KEY &	key () const

const value_type &	keyValue () const

const BTree &	left () const

const BTree &	right () 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:

BTree.h

Classes

Public Types

Public Member Functions

Static Public Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

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

Member Typedef Documentation

◆ iterator

◆ sharedNode

◆ value_type

Constructor & Destructor Documentation

◆ BTree() [1/4]

◆ BTree() [2/4]

◆ BTree() [3/4]

◆ BTree() [4/4]

Member Function Documentation

◆ add() [1/2]

◆ add() [2/2]

◆ balance()

◆ begin()

◆ empty()

◆ end()

◆ find()

◆ fold()

◆ height()

◆ iter()

◆ key()

◆ keyValue()

◆ left()

◆ map()

◆ mem()

◆ merge()

◆ min()

◆ operator!=()

◆ operator=()

◆ operator==()

◆ print()

◆ remove()

◆ remove_min()

◆ right()

◆ same()

◆ size()

◆ value()

Member Data Documentation

◆ root_

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