A key/value dictionary for string keys. More...
#include <RadixTree.h>
Inheritance diagram for RadixTree< T >:
Collaboration diagram for RadixTree< T >:
Classes | |
| class | Node |
Public Types | |
| typedef ::Iterator< T, Node > | Iterator |
| typedef Iterator::Const | ConstIterator |
| typedef Result< T, bool > | LookupType |
Public Member Functions | |
| RadixTree () | |
| RadixTree (const RadixTree< T > &x) | |
| RadixTree (bool bCaseSensitive) | |
| ~RadixTree () | |
| RadixTree & | operator= (const RadixTree &x) |
| size_t | count () const |
| void | insert (const String &key, const T &value) |
| Result< T, bool > | lookup (const String &key) const |
| void | remove (const String &key) |
| void | clear () |
| Iterator | erase (Iterator iter) |
| Iterator | begin () |
| ConstIterator | begin () const |
| Iterator | end () |
| ConstIterator | end () const |
| void | dump (void(*emit_line)(const char *s)) const |
Private Member Functions | |
| Node * | cloneNode (Node *node, Node *parent) |
| Node * | getNewNode () |
| void | returnNode (Node *p) |
Private Attributes | |
| size_t | m_nItems |
| Node * | m_pRoot |
| const bool | m_bCaseSensitive |
| ObjectPool< Node > | m_NodePool |
Detailed Description
template<class T>
class RadixTree< T >
A key/value dictionary for string keys.
Dictionary class, aka Map for string keys. This is implemented as a Radix Tree - also known as a Patricia Trie.
Definition at line 45 of file RadixTree.h.
Member Typedef Documentation
| typedef Iterator::Const RadixTree< T >::ConstIterator |
Type of the constant bidirectional iterator
Definition at line 187 of file RadixTree.h.
Type of the bidirectional iterator
Definition at line 185 of file RadixTree.h.
Member Function Documentation
Get an iterator pointing to the beginning of the List
- Returns
- iterator pointing to the beginning of the List
Definition at line 233 of file RadixTree.h.
|
inline |
Get a constant iterator pointing to the beginning of the List
- Returns
- constant iterator pointing to the beginning of the List
Definition at line 242 of file RadixTree.h.
Get an iterator pointing to the end of the List + 1
- Returns
- iterator pointing to the end of the List + 1
Definition at line 251 of file RadixTree.h.
|
inline |
Get a constant iterator pointing to the end of the List + 1
- Returns
- constant iterator pointing to the end of the List + 1
Definition at line 257 of file RadixTree.h.
Erase one Element
Definition at line 222 of file RadixTree.h.
Obtain a new Node with the same case-sensitive flag.
Definition at line 269 of file RadixTree.h.
Referenced by RadixTree< T >::clear(), RadixTree< T >::cloneNode(), RadixTree< T >::insert(), and RadixTree< T >::remove().
Here is the caller graph for this function:
Return a Node so it can be allocated again.
Definition at line 276 of file RadixTree.h.
Referenced by RadixTree< T >::clear(), RadixTree< T >::dump(), RadixTree< T >::operator=(), RadixTree< T >::RadixTree(), RadixTree< T >::remove(), and RadixTree< T >::~RadixTree().
Here is the caller graph for this function:
Member Data Documentation
|
private |
Whether matches are case-sensitive or not.
Definition at line 293 of file RadixTree.h.
Referenced by RadixTree< T >::Node::matchKey().
|
private |
Number of items in the tree.
Definition at line 289 of file RadixTree.h.
Referenced by RadixTree< T >::clear(), RadixTree< T >::count(), RadixTree< T >::insert(), RadixTree< T >::operator=(), RadixTree< T >::RadixTree(), and RadixTree< T >::remove().
|
private |
Pool of node objects (to reduce impact of lots of node allocs/deallocs).
Definition at line 296 of file RadixTree.h.
The tree's root.
Definition at line 291 of file RadixTree.h.
Referenced by RadixTree< T >::clear(), RadixTree< T >::dump(), RamFs::initialise(), RadixTree< T >::insert(), RadixTree< T >::lookup(), RadixTree< T >::operator=(), RadixTree< T >::RadixTree(), RadixTree< T >::remove(), RamFile::unpinBlock(), and RadixTree< T >::~RadixTree().
The documentation for this class was generated from the following file:
