|
|
|
#include <Trie.h>
Public Member Functions | |
| void | clear () |
| clear the content of trie | |
| void | display (std::ostream &os) |
| display content of trie in output stream | |
| const T & | find (const char *str, unsigned strLen) const |
| const T & | find (std::string const &str) const |
| get an entry in the Trie | |
| const TrieNode< T > * | initialNode () const |
| get initial TrieNode | |
| void | insert (const char *str, unsigned strLen, const T &value) |
| void | insert (std::string const &str, const T &value) |
| const TrieNode< T > * | node (std::string const &str) const |
| get node matching a string | |
| const TrieNode< T > * | node (const char *str, unsigned strLen) const |
| void | setEntry (std::string const &str, const T &value) |
| void | setEntry (const char *str, unsigned strLen, const T &value) |
| Trie (const T &empty) | |
| ~Trie () | |
Private Member Functions | |
| TrieNode< T > * | _addEntry (const char *str, unsigned strLen) |
| Trie & | operator= (const Trie &e) |
| avoid affectation operator | |
| Trie () | |
| avoid default constructor | |
| Trie (const Trie &e) | |
| avoid copy constructor | |
Private Attributes | |
| T | _empty |
| value returned when no match is found in trie | |
| TrieFactory< T > * | _factory |
| factory | |
| TrieNode< T > * | _initialNode |
| first node of trie | |
Implement a trie in memory with the smallest structure as possible (use few RAM as possible)
constuctor, empty is the value returned when no match in found in trie
Definition at line 557 of file Trie.h.
References edm::Trie< T >::_empty, edm::Trie< T >::_factory, and edm::Trie< T >::_initialNode.
: _empty(empty), _factory(0x0), _initialNode(0x0) { // initialize nodes by paquets of 10000 _factory = new TrieFactory<T>(10000); _initialNode = _factory->newNode(_empty); }
| edm::TrieNode< T > * edm::Trie< T >::_addEntry | ( | const char * | str, |
| unsigned | strLen | ||
| ) | [private] |
Definition at line 584 of file Trie.h.
References edm::TrieNode< T >::addSubNode(), newFWLiteAna::found, i, python::Node::node, pos, and edm::TrieNode< T >::subNodeByLabel().
{
unsigned pos = 0;
bool found = true;
TrieNode<T> *node = _initialNode, *previous = 0x0;
// Look for the part of the word which is in Trie
while (found && pos < strLen)
{
found = false;
previous = node;
node = node->subNodeByLabel(str[pos]);
if (node)
{
found = true;
++pos;
}
}
// Add part of the word which is not in Trie
if (!node || pos != strLen)
{
node = previous;
for (unsigned i = pos; i < strLen; ++i)
{
TrieNode<T> *newNode = _factory->newNode(_empty);
node->addSubNode(str[pos], newNode);
node = newNode;
++pos;
}
}
assert(node != 0x0);
return node;
}
| void edm::Trie< T >::clear | ( | void | ) |
clear the content of trie
Definition at line 698 of file Trie.h.
References edm::Trie< T >::clear().
Referenced by edm::Trie< T >::clear().
{
_factory->clear();
_initialNode = _factory->newNode(_empty);
}
| void edm::Trie< T >::display | ( | std::ostream & | os | ) |
display content of trie in output stream
Definition at line 705 of file Trie.h.
References edm::Trie< T >::display().
Referenced by edm::Trie< T >::display().
{
if (_initialNode)
_initialNode->display(os, 0, 0);
}
| const T & edm::Trie< T >::find | ( | std::string const & | str | ) | const |
get an entry in the Trie
Definition at line 638 of file Trie.h.
References spr::find().
{
return find(str.c_str(),str.size());
}
| const T & edm::Trie< T >::find | ( | const char * | str, |
| unsigned | strLen | ||
| ) | const |
Definition at line 643 of file Trie.h.
References newFWLiteAna::found, python::Node::node, pos, edm::TrieNode< T >::subNodeByLabel(), and edm::TrieNode< T >::value().
{
unsigned pos = 0;
bool found = true;
const TrieNode<T> *node = _initialNode;
while (found && pos < strLen)
{
found = false;
node = node->subNodeByLabel(str[pos]);
if (node)
{
found = true;
++pos;
}
}
if (node && pos == strLen) // The word is complet in the automaton
return node->value();
return _empty;
}
| const edm::TrieNode< T > * edm::Trie< T >::initialNode | ( | ) | const |
| void edm::Trie< T >::insert | ( | const char * | str, |
| unsigned | strLen, | ||
| const T & | value | ||
| ) |
Definition at line 627 of file Trie.h.
References edm::detailsTrie::errorInsert(), python::Node::node, edm::TrieNode< T >::setValue(), and edm::TrieNode< T >::value().
{
TrieNode<T> *node = _addEntry(str, strLen);
// Set the value on the last node
if (node && node->value() != _empty)
detailsTrie::errorInsert(std::string(str,strLen));
node->setValue(value);
}
| void edm::Trie< T >::insert | ( | std::string const & | str, |
| const T & | value | ||
| ) |
add an entry in the Trie, if entry already exist an exception is throw
Definition at line 621 of file Trie.h.
References edm::eventsetup::heterocontainer::insert(), and relativeConstraints::value.
Referenced by GeometricSearchTrackerBuilder::build().
| edm::TrieNode< T > const * edm::Trie< T >::node | ( | const char * | str, |
| unsigned | strLen | ||
| ) | const |
Definition at line 672 of file Trie.h.
References newFWLiteAna::found, python::Node::node, pos, and edm::TrieNode< T >::subNodeByLabel().
| edm::TrieNode< T > const * edm::Trie< T >::node | ( | std::string const & | str | ) | const |
get node matching a string
Definition at line 666 of file Trie.h.
References python::Node::node.
Referenced by GeometricSearchTrackerBuilder::build().
{
return node(str.c_str(),str.size());
}
avoid affectation operator
| void edm::Trie< T >::setEntry | ( | std::string const & | str, |
| const T & | value | ||
| ) |
| void edm::Trie< T >::setEntry | ( | const char * | str, |
| unsigned | strLen, | ||
| const T & | value | ||
| ) |
Definition at line 577 of file Trie.h.
References python::Node::node, and edm::TrieNode< T >::setValue().
value returned when no match is found in trie
Definition at line 222 of file Trie.h.
Referenced by edm::Trie< T >::Trie().
TrieFactory<T>* edm::Trie< T >::_factory [private] |
TrieNode<T>* edm::Trie< T >::_initialNode [private] |
1.7.3