CMSSW Reference Manual

List of all members.


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)
	add an entry in the Trie, if entry already exist an exception is throw
const TrieNode< T > *	node (const char *str, unsigned strLen) const
const TrieNode< T > *	node (std::string const &str) const
	get node matching a string
void	setEntry (const char *str, unsigned strLen, const T &value)
void	setEntry (std::string const &str, const T &value)
	associates a value to a string, if string is already in Trie, value is overwriten
	Trie (const T &empty)
	constuctor, empty is the value returned when no match in found in trie
	~Trie ()
Private Member Functions
TrieNode< T > *	_addEntry (const char *str, unsigned strLen)
Trie &	operator= (const Trie &e)
	avoid affectation operator
	Trie (const Trie &e)
	avoid copy constructor
	Trie ()
	avoid default 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

Detailed Description

template<typename T>
class edm::Trie< T >

Constructor & Destructor Documentation

template<typename T>

edm::Trie< T >::Trie ( const T & empty ) [inline]

constuctor, empty is the value returned when no match in found in trie

Definition at line 556 of file Trie.h.

References edm::Trie< T >::_empty, edm::Trie< T >::_factory, and edm::Trie< T >::_initialNode.

00556                                :
00557   _empty(empty), _factory(0x0), _initialNode(0x0)
00558 {
00559   // initialize nodes by paquets of 10000
00560   _factory = new TrieFactory<T>(10000);
00561   _initialNode = _factory->newNode(_empty);
00562 }

template<typename T>

edm::Trie< T >::~Trie ( ) [inline]

Definition at line 565 of file Trie.h.

References edm::Trie< T >::_factory.

00566 {
00567   delete _factory;
00568 }

template<typename T>

edm::Trie< T >::Trie ( ) [private]

avoid default constructor

template<typename T>

edm::Trie< T >::Trie ( const Trie< T > & e ) [private]

avoid copy constructor

Member Function Documentation

template<typename T>

edm::TrieNode< T > * edm::Trie< T >::_addEntry	(	const char *	str,
		unsigned	strLen
	)			`[inline, private]`

Definition at line 583 of file Trie.h.

References edm::Trie< T >::_empty, edm::Trie< T >::_factory, edm::Trie< T >::_initialNode, edm::TrieNode< T >::addSubNode(), i, edm::Trie< T >::node(), and edm::TrieNode< T >::subNodeByLabel().

Referenced by edm::Trie< T >::insert(), and edm::Trie< T >::setEntry().

00584 {
00585   unsigned      pos = 0;
00586   bool          found = true;
00587   TrieNode<T>   *node = _initialNode, *previous = 0x0;
00588 
00589   // Look for the part of the word which is in Trie
00590   while (found && pos < strLen)
00591     {
00592       found = false;
00593       previous = node;
00594       node = node->subNodeByLabel(str[pos]);
00595       if (node)
00596         {
00597           found = true;
00598           ++pos;
00599         }
00600     }
00601 
00602   // Add part of the word which is not in Trie
00603   if (!node || pos != strLen)
00604     {
00605       node = previous;
00606       for (unsigned i = pos; i < strLen; ++i)
00607         {
00608           TrieNode<T> *newNode = _factory->newNode(_empty);
00609           node->addSubNode(str[pos], newNode);
00610           node = newNode;
00611           ++pos;
00612         }
00613     }
00614   assert(node != 0x0);
00615   return node;
00616 }

template<typename T>

void edm::Trie< T >::clear ( void ) [inline]

clear the content of trie

Definition at line 697 of file Trie.h.

References edm::Trie< T >::_empty, edm::Trie< T >::_factory, and edm::Trie< T >::_initialNode.

00698 {
00699   _factory->clear();
00700   _initialNode = _factory->newNode(_empty);
00701 }

template<typename T>

void edm::Trie< T >::display ( std::ostream & os ) [inline]

display content of trie in output stream

Definition at line 704 of file Trie.h.

References edm::Trie< T >::_initialNode.

00705 {
00706   if (_initialNode)
00707     _initialNode->display(os, 0, 0);
00708 }

template<typename T>

const T & edm::Trie< T >::find	(	const char *	str,
		unsigned	strLen
	)			const `[inline]`

Definition at line 642 of file Trie.h.

References edm::Trie< T >::_empty, edm::Trie< T >::_initialNode, edm::Trie< T >::node(), edm::TrieNode< T >::subNodeByLabel(), and edm::TrieNode< T >::value().

00643 {
00644   unsigned              pos = 0;
00645   bool                  found = true;
00646   const TrieNode<T>     *node = _initialNode;
00647   
00648   while (found && pos < strLen)
00649     {
00650       found = false;
00651       node = node->subNodeByLabel(str[pos]);
00652       if (node)
00653         {
00654           found = true;
00655           ++pos;
00656         }
00657     }
00658   if (node && pos == strLen) // The word is complet in the automaton
00659     return node->value();
00660   return _empty;
00661 }

template<typename T>

const T & edm::Trie< T >::find ( std::string const & str ) const [inline]

get an entry in the Trie

Definition at line 637 of file Trie.h.

00637                                                      {
00638   return find(str.c_str(),str.size());
00639 }

template<typename T>

const edm::TrieNode< T > * edm::Trie< T >::initialNode ( ) const [inline]

get initial TrieNode

Definition at line 691 of file Trie.h.

References edm::Trie< T >::_initialNode.

00692 {
00693   return _initialNode;
00694 }

template<typename T>

void edm::Trie< T >::insert	(	const char *	str,
		unsigned	strLen,
		const T &	value
	)			`[inline]`

Definition at line 626 of file Trie.h.

References edm::Trie< T >::_addEntry(), edm::Trie< T >::_empty, edm::detailsTrie::errorInsert(), edm::Trie< T >::node(), edm::TrieNode< T >::setValue(), and edm::TrieNode< T >::value().

00627 {
00628   TrieNode<T>   *node = _addEntry(str, strLen);
00629   
00630   // Set the value on the last node
00631   if (node && node->value() != _empty)
00632     detailsTrie::errorInsert(std::string(str,strLen));
00633   node->setValue(value);
00634 }

template<typename T>

void edm::Trie< T >::insert	(	std::string const &	str,
		const T &	value
	)			`[inline]`

add an entry in the Trie, if entry already exist an exception is throw

Definition at line 620 of file Trie.h.

00621 {
00622   insert(str.c_str(),str.size(),value);
00623 }

template<typename T>

edm::TrieNode< T > const * edm::Trie< T >::node	(	const char *	str,
		unsigned	strLen
	)			const `[inline]`

Definition at line 671 of file Trie.h.

References edm::Trie< T >::_initialNode, edm::Trie< T >::node(), and edm::TrieNode< T >::subNodeByLabel().

00671                                                        {
00672   unsigned              pos = 0;
00673   bool                  found = true;
00674   const TrieNode<T>     *node = _initialNode;
00675         
00676   while (found && pos < strLen)
00677     {
00678       found = false;
00679       node = node->subNodeByLabel(str[pos]);
00680       if (node)
00681         {
00682           found = true;
00683           ++pos;
00684         }
00685     }
00686   return node;
00687 }

template<typename T>

edm::TrieNode< T > const * edm::Trie< T >::node ( std::string const & str ) const [inline]

get node matching a string

Definition at line 665 of file Trie.h.

Referenced by edm::Trie< T >::_addEntry(), edm::Trie< T >::find(), edm::Trie< T >::insert(), edm::Trie< T >::node(), and edm::Trie< T >::setEntry().

00665                                             {
00666     return node(str.c_str(),str.size());
00667   }

template<typename T>

Trie& edm::Trie< T >::operator= ( const Trie< T > & e ) [private]

avoid affectation operator

template<typename T>

void edm::Trie< T >::setEntry	(	const char *	str,
		unsigned	strLen,
		const T &	value
	)			`[inline]`

Definition at line 576 of file Trie.h.

References edm::Trie< T >::_addEntry(), edm::Trie< T >::node(), and edm::TrieNode< T >::setValue().

00577 {
00578   TrieNode<T>   *node = _addEntry(str, strLen);
00579   node->setValue(value);
00580 }

template<typename T>

void edm::Trie< T >::setEntry	(	std::string const &	str,
		const T &	value
	)			`[inline]`

associates a value to a string, if string is already in Trie, value is overwriten

Definition at line 571 of file Trie.h.

00572 {
00573   setEntry(str.c_str(),str.size(),value);
00574 }

Member Data Documentation

template<typename T>

T edm::Trie< T >::_empty [private]

value returned when no match is found in trie

Definition at line 222 of file Trie.h.

Referenced by edm::Trie< T >::_addEntry(), edm::Trie< T >::clear(), edm::Trie< T >::find(), edm::Trie< T >::insert(), and edm::Trie< T >::Trie().

edm::Trie< T > Class Template Reference

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

template<typename T> class edm::Trie< T >

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<typename T>
class edm::Trie< T >