#include <Trie.h>

Public Member Functions
void	clear ()
	clear the content of trie More...

void	display (std::ostream &os)
	display content of trie in output stream More...

const T &	find (std::string const &str) const
	get an entry in the Trie More...

const T &	find (const char *str, unsigned strLen) const

const TrieNode< T > *	initialNode () const
	get initial TrieNode More...

void	insert (std::string const &str, const T &value)

void	insert (const char *str, unsigned strLen, const T &value)

const TrieNode< T > *	node (std::string const &str) const
	get node matching a string More...

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)=delete
	avoid affectation operator More...

	Trie ()=delete
	avoid default constructor More...

	Trie (const Trie &e)=delete
	avoid copy constructor More...

Private Attributes
T	_empty
	value returned when no match is found in trie More...

TrieFactory< T > *	_factory
	factory More...

TrieNode< T > *	_initialNode
	first node of trie More...

Detailed Description

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

Implement a trie in memory with the smallest structure as possible (use few RAM as possible)

Definition at line 168 of file Trie.h.

Constructor & Destructor Documentation

template<typename T >

edm::Trie< T >::Trie ( const T & empty )

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

Definition at line 492 of file Trie.h.

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

                                : _empty(empty), _factory(nullptr), _initialNode(nullptr) {
   // initialize nodes by paquets of 10000
   _factory = new TrieFactory<T>(10000);
   _initialNode = _factory->newNode(_empty);
 }

template<typename T >

edm::Trie< T >::~Trie ( )

Definition at line 499 of file Trie.h.

                   {
   delete _factory;
 }

template<typename T >

edm::Trie< T >::Trie ( )

privatedelete

avoid default constructor

template<typename T >

edm::Trie< T >::Trie ( const Trie< T > & e )

privatedelete

avoid copy constructor

Member Function Documentation

template<typename T >

edm::TrieNode< T > * edm::Trie< T >::_addEntry	(	const char *	str,
		unsigned	strLen
	)

private

Definition at line 514 of file Trie.h.

References edm::TrieNode< T >::addSubNode(), cms::cuda::assert(), newFWLiteAna::found, mps_fire::i, callgraph::previous, and edm::TrieNode< T >::subNodeByLabel().

                                                                       {
   unsigned pos = 0;
   bool found = true;
   TrieNode<T> *node = _initialNode, *previous = nullptr;
 
   // 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 != nullptr);
   return node;
 }

template<typename T >

void edm::Trie< T >::clear ( void )

clear the content of trie

Definition at line 611 of file Trie.h.

Referenced by BeautifulSoup.Tag::setString().

                        {
   _factory->clear();
   _initialNode = _factory->newNode(_empty);
 }

template<typename T >

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

display content of trie in output stream

Definition at line 617 of file Trie.h.

                                        {
   if (_initialNode)
     _initialNode->display(os, 0, 0);
 }

template<typename T >

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

get an entry in the Trie

Definition at line 560 of file Trie.h.

References spr::find().

Referenced by BeautifulSoup.Tag::__getattr__(), and BeautifulSoup.Tag::firstText().

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

template<typename T >

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

Definition at line 565 of file Trie.h.

References newFWLiteAna::found, edm::TrieNode< T >::subNodeByLabel(), and edm::TrieNode< T >::value().

Referenced by BeautifulSoup.Tag::__getattr__(), and BeautifulSoup.Tag::firstText().

                                                                 {
   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;
 }

template<typename T >

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

get initial TrieNode

Definition at line 606 of file Trie.h.

                                                     {
   return _initialNode;
 }

template<typename T >

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 545 of file Trie.h.

References edm::eventsetup::heterocontainer::insert(), and relativeConstraints::value.

Referenced by BeautifulSoup.PageElement::_invert(), and SequenceTypes.Schedule::_replaceIfHeldDirectly().

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

template<typename T >

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

Definition at line 550 of file Trie.h.

References edm::detailsTrie::errorInsert(), edm::TrieNode< T >::setValue(), AlCaHLTBitMon_QueryRunRegistry::string, and edm::TrieNode< T >::value().

Referenced by BeautifulSoup.PageElement::_invert(), and SequenceTypes.Schedule::_replaceIfHeldDirectly().

                                                                         {
   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);
 }

template<typename T >

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

get node matching a string

Definition at line 584 of file Trie.h.

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

template<typename T >

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

Definition at line 589 of file Trie.h.

References newFWLiteAna::found, and edm::TrieNode< T >::subNodeByLabel().

                                                                              {
   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;
     }
   }
   return node;
 }

template<typename T >

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

privatedelete

avoid affectation operator

template<typename T >

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

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

Definition at line 504 of file Trie.h.

References relativeConstraints::value.

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

template<typename T >

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

Definition at line 508 of file Trie.h.

References edm::TrieNode< T >::setValue().

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