edm::Trie< T > Class Template Reference

#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)
	avoid affectation operator More...
	Trie ()
	avoid default constructor More...
	Trie (const Trie &e)
	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 179 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 555 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);
}

template<typename T >

edm::Trie< T >::~Trie

(

)

Definition at line 564 of file Trie.h.

{
  delete _factory;
}

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  )

private

Definition at line 582 of file Trie.h.

References edm::TrieNode< T >::addSubNode(), assert(), newFWLiteAna::found, i, 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;
}

template<typename T >

void edm::Trie< T >::clear

(

void

)

clear the content of trie

Definition at line 696 of file Trie.h.

Referenced by Vispa.Views.WidgetView.WidgetView::closeEvent(), Vispa.Views.BoxDecayView.BoxDecayView::closeEvent(), Vispa.Share.FindAlgorithm.FindAlgorithm::findUsingFindDialog(), Vispa.Views.LineDecayView.LineDecayView::setDataObjects(), Vispa.Views.WidgetView.WidgetView::setDataObjects(), BeautifulSoup.Tag::setString(), Vispa.Views.TreeView.TreeView::updateContent(), Vispa.Views.TableView.TableView::updateContent(), Vispa.Views.BoxDecayView.BoxDecayView::updateContent(), and Vispa.Views.PropertyView.PropertyView::updateContent().

{
  _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 703 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 636 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 641 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 690 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 619 of file Trie.h.

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

Referenced by BeautifulSoup.PageElement::_invert(), and GeometricSearchTrackerBuilder::build().

{
  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 625 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().

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

Referenced by GeometricSearchTrackerBuilder::build().

                                            {
    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 670 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 )

private

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

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

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

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 >::Trie().

template<typename T >

TrieFactory<T>* edm::Trie< T >::_factory

private

factory

Definition at line 224 of file Trie.h.

Referenced by edm::Trie< T >::Trie().

template<typename T >

TrieNode<T>* edm::Trie< T >::_initialNode

private

first node of trie

Definition at line 226 of file Trie.h.

Referenced by edm::Trie< T >::Trie().