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)=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

Trie() [1/3]

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

~Trie()

template<typename T >

edm::Trie< T >::~Trie

(

)

Definition at line 499 of file Trie.h.

                  {
  delete _factory;
}

Trie() [2/3]

template<typename T >

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

privatedelete

avoid default constructor

Trie() [3/3]

template<typename T >

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

privatedelete

avoid copy constructor

Member Function Documentation

_addEntry()

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, str, 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;
}

clear()

template<typename T >

void edm::Trie< T >::clear

(

void

)

clear the content of trie

Definition at line 611 of file Trie.h.

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

display()

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

find() [1/2]

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(), and str.

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

find() [2/2]

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, str, 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;
}

initialNode()

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

insert() [1/2]

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(), str, and relativeConstraints::value.

Referenced by SequenceTypes.Schedule::_replaceIfHeldDirectly().

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

insert() [2/2]

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(), str, AlCaHLTBitMon_QueryRunRegistry::string, and edm::TrieNode< T >::value().

Referenced by 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);
}

node() [1/2]

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.

References str.

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

node() [2/2]

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, str, 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;
}

operator=()

template<typename T >

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

privatedelete

avoid affectation operator

setEntry() [1/2]

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 str, and relativeConstraints::value.

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

setEntry() [2/2]

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(), and str.

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

Member Data Documentation

_empty

template<typename T >

T edm::Trie< T >::_empty

private

value returned when no match is found in trie

Definition at line 210 of file Trie.h.

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

_factory

template<typename T >

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

private

factory

Definition at line 212 of file Trie.h.

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

_initialNode

template<typename T >

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

private

first node of trie

Definition at line 214 of file Trie.h.

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