Loading...
Searching...
No Matches
gtsam::DSF< KEY > Class Template Reference
Detailed Description
template<class KEY>
class gtsam::DSF< KEY >
class gtsam::DSF< KEY >
Disjoint Set Forest class.
Quoting from CLR: A disjoint-set data structure maintains a collection S = {S_1,S_2,...} of disjoint dynamic sets. Each set is identified by a representative, which is some member of the set.
Inheritance diagram for gtsam::DSF< KEY >:
Public Types | |
| typedef DSF< KEY > | Self |
| typedef std::set< KEY > | Set |
| typedef BTree< KEY, KEY > | Tree |
| typedef std::pair< KEY, KEY > | KeyLabel |
Protected Member Functions | |
| KEY | findSet_ (const KEY &key) |
| same as findSet except with path compression: After we have traversed the path to the root, each parent pointer is made to directly point to it | |
| Protected Member Functions inherited from gtsam::BTree< KEY, KEY > | |
| BTree () | |
| default constructor creates an empty tree | |
| BTree (const BTree &other) | |
| copy constructor | |
| BTree (const value_type &keyValue) | |
| create leaf from key-value pair | |
| BTree (const BTree &l, const value_type &keyValue, const BTree &r) | |
| create from key-value pair and left, right subtrees | |
| BTree & | operator= (const BTree &other) |
| assignment operator | |
| bool | empty () const |
| Check whether tree is empty. | |
| BTree | add (const value_type &xd) const |
| add a key-value pair | |
| BTree | add (const KEY &x, const KEY &d) const |
| add a key-value pair | |
| bool | mem (const KEY &x) const |
| member predicate | |
| bool | same (const BTree &other) const |
| Check whether trees are exactly the same (occupy same memory). | |
| bool | operator== (const BTree &other) const |
| Check whether trees are structurally the same, i.e., contain the same values in same tree-structure. | |
| bool | operator!= (const BTree &other) const |
| const value_type & | min () const |
| minimum key binding | |
| BTree | remove_min () const |
| remove minimum key binding | |
| BTree | remove (const KEY &x) const |
| remove a key-value pair | |
| size_t | height () const |
| Return height of the tree, 0 if empty. | |
| size_t | size () const |
| return size of the tree | |
| const KEY & | find (const KEY &k) const |
| find a value given a key, throws exception when not found Optimized non-recursive version as [find] is crucial for speed | |
| void | print (const std::string &s="") const |
| print in-order | |
| void | iter (std::function< void(const KEY &, const KEY &)> f) const |
| iterate over tree | |
| BTree< KEY, TO > | map (std::function< TO(const KEY &, const KEY &)> f) const |
| map key-values in tree over function f that computes a new value | |
| ACC | fold (std::function< ACC(const KEY &, const KEY &, const ACC &)> f, const ACC &a) const |
| 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. | |
| const_iterator | begin () const |
| return iterator | |
| const_iterator | end () const |
| return iterator | |
Additional Inherited Members | |
| Protected Types inherited from gtsam::BTree< KEY, KEY > | |
| typedef std::pair< KEY, KEY > | value_type |
| typedef const_iterator | iterator |
| Static Protected Member Functions inherited from gtsam::BTree< KEY, KEY > | |
| static BTree | merge (const BTree &t1, const BTree &t2) |
| merge two trees | |
The documentation for this class was generated from the following file:
- /tmp/gtsam-4.2-docs.H5EUbA/src/gtsam_unstable/base/DSF.h
