edm::TrieNode< T > Class Template Reference

this class represent the node of a trie, it contains a link to a sub node and a link to a brother (node which have the same father) More...

#include <Trie.h>

List of all members.

Public Types
typedef TrieNodeIter< T >	const_iterator
Public Member Functions
void	addSubNode (unsigned char chr, TrieNode< T > *node)
TrieNodeIter< T >	begin () const
	initialize subnode iterator (std conforming)
const TrieNode< T > *	brother () const
	get brother (return 0x0 this node has no brother)
TrieNode< T > *	brother ()
unsigned char	brotherLabel () const
	get brother label
void	clear ()
	clear content of TrieNode
void	display (std::ostream &os, unsigned offset, unsigned char label) const
	display content of node in output stream
TrieNodeIter< T >	end () const
	mark end of iteration (std conforming)
void	setValue (const T &val)
	set value associed to node
const TrieNode< T > *	subNode () const
TrieNode< T > *	subNode ()
TrieNode< T > *	subNodeByLabel (unsigned char chr)
const TrieNode< T > *	subNodeByLabel (unsigned char chr) const
unsigned char	subNodeLabel () const
	TrieNode ()
const T &	value () const
	get value associed to node
	~TrieNode ()
Private Member Functions
void	_addBrother (unsigned char chr, TrieNode< T > *brother)
	add a new brother
TrieNode< T > *	_getBrother (unsigned char chr)
const TrieNode< T > *	_getBrother (unsigned char chr) const
template<typename Node >
Node	_sequentialSearch (Node first, unsigned char label, unsigned char val) const
void	_setBrother (TrieNode< T > *brother, unsigned char brotherLabel)
	set brother (used by sort)
TrieNode &	operator= (const TrieNode &e)
	avoid affectation operator
	TrieNode (const TrieNode &e)
	avoid copy constructor
Private Attributes
TrieNode< T > *	_brother
	pointer to brother (node with same father as this one)
unsigned char	_brotherLabel
	character to go to brother (node with same father as this one)
TrieNode< T > *	_firstSubNode
	pointer to first sub node
unsigned char	_firstSubNodeLabel
	character to go to first subnode
T	_value
	value associed to this node

---

Detailed Description

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

this class represent the node of a trie, it contains a link to a sub node and a link to a brother (node which have the same father)

Definition at line 80 of file Trie.h.

---

Member Typedef Documentation

template<typename T>

typedef TrieNodeIter<T> edm::TrieNode< T >::const_iterator

Definition at line 84 of file Trie.h.

---

Constructor & Destructor Documentation

template<typename T >

edm::TrieNode< T >::TrieNode

(

)

we can not set _value here because type is unknown. assert that the value is set later with setValue()

Definition at line 366 of file Trie.h.

                         :
  _brother(0), _brotherLabel(0), _firstSubNode(0), _firstSubNodeLabel(0),_value()
{
}

template<typename T >

edm::TrieNode< T >::~TrieNode

(

)

Definition at line 374 of file Trie.h.

{
  // do not delete _brother and _firstSubNode because they are
  // allocated by factory (TrieFactory) and factory will delete them
}

template<typename T>

edm::TrieNode< T >::TrieNode

(

const TrieNode< T > &

e

)

[private]

avoid copy constructor

---

Member Function Documentation

template<typename T >

void edm::TrieNode< T >::_addBrother	(	unsigned char	chr,
		TrieNode< T > *	brother
	)		[private]

add a new brother

Definition at line 430 of file Trie.h.

References edm::TrieNode< T >::_addBrother(), and edm::TrieNode< T >::_setBrother().

Referenced by edm::TrieNode< T >::_addBrother().

{
  if (!_brother || _brotherLabel > chr)
    {
      brother->_setBrother(_brother, _brotherLabel);
      _brother = brother;
      _brotherLabel = chr;
    }
  else
    _brother->_addBrother(chr, brother);
}

template<typename T >

const edm::TrieNode< T > * edm::TrieNode< T >::_getBrother

(

unsigned char

chr

)

const [private]

@ brief get brother that has the label chr (return 0x0 if brother is not found)

Definition at line 417 of file Trie.h.

{
  const TrieNode<T> *brother = _brother;
  return _sequentialSearch(brother, _brotherLabel, chr);
}

template<typename T >

edm::TrieNode< T > * edm::TrieNode< T >::_getBrother

(

unsigned char

chr

)

[private]

@ brief get brother that has the label chr (return 0x0 if brother is not found)

Definition at line 424 of file Trie.h.

{
  return _sequentialSearch(_brother, _brotherLabel, chr);
}

template<typename T >

template<typename Node >

Node edm::TrieNode< T >::_sequentialSearch	(	Node	first,
		unsigned char	label,
		unsigned char	val
	)		const [inline, private]

Definition at line 494 of file Trie.h.

References edm::first().

{
  if (first && label <= val)
    {
      if (label == val)
        return first;
      return first->_getBrother(val);
    }
  return 0x0;
}

template<typename T >

void edm::TrieNode< T >::_setBrother	(	TrieNode< T > *	brother,
		unsigned char	brotherLabel
	)		[private]

set brother (used by sort)

Definition at line 506 of file Trie.h.

Referenced by edm::TrieNode< T >::_addBrother(), and edm::TrieNode< T >::addSubNode().

{
  _brother = brother;
  _brotherLabel = brotherLabel;
}

template<typename T >

void edm::TrieNode< T >::addSubNode	(	unsigned char	chr,
		TrieNode< T > *	node
	)

Definition at line 480 of file Trie.h.

References edm::TrieNode< T >::_setBrother(), and python::Node::node.

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

{
  if (!_firstSubNode || _firstSubNodeLabel > chr)
    {
      node->_setBrother(_firstSubNode, _firstSubNodeLabel);
      _firstSubNode = node;
      _firstSubNodeLabel = chr;
    }
  else
    _firstSubNode->_addBrother(chr, node);
}

template<typename T >

edm::TrieNodeIter< T > edm::TrieNode< T >::begin

(

void

)

const

initialize subnode iterator (std conforming)

Definition at line 383 of file Trie.h.

                            {
  return const_iterator(this);
}

template<typename T >

edm::TrieNode< T > * edm::TrieNode< T >::brother

(

)

Definition at line 411 of file Trie.h.

{
  return _brother;
}

template<typename T >

const edm::TrieNode< T > * edm::TrieNode< T >::brother

(

)

const

get brother (return 0x0 this node has no brother)

Definition at line 405 of file Trie.h.

Referenced by edm::TrieNodeIter< T >::increment().

{
  return _brother;
}

template<typename T >

unsigned char edm::TrieNode< T >::brotherLabel

(

)

const

get brother label

Definition at line 443 of file Trie.h.

Referenced by edm::TrieNodeIter< T >::increment().

{
  return _brotherLabel;
}

template<typename T >

void edm::TrieNode< T >::clear

(

void

)

clear content of TrieNode

Definition at line 528 of file Trie.h.

Referenced by edm::TrieFactory< T >::newNode().

{
  _brother = 0x0;
  _brotherLabel = 0;
  _firstSubNode = 0x0;
  _firstSubNodeLabel = 0;
}

template<typename T >

void edm::TrieNode< T >::display	(	std::ostream &	os,
		unsigned	offset,
		unsigned char	label
	)		const

display content of node in output stream

Definition at line 513 of file Trie.h.

References i, and evf::evtn::offset().

{
  unsigned int i;
  for (i = 0; i < offset; ++i)
    os << " ";
  if (label)
    os << "label[" << label << "] ";
  os << "value[" << _value << "]" << std::endl;
  if (_firstSubNode)
    _firstSubNode->display(os, offset + 2, _firstSubNodeLabel);
  if (_brother)
    _brother->display(os, offset, _brotherLabel);
}

template<typename T >

edm::TrieNodeIter< T > edm::TrieNode< T >::end

(

void

)

const

mark end of iteration (std conforming)

Definition at line 388 of file Trie.h.

                          {
  return const_iterator(0);
}

template<typename T>

TrieNode& edm::TrieNode< T >::operator=

(

const TrieNode< T > &

e

)

[private]

avoid affectation operator

template<typename T >

void edm::TrieNode< T >::setValue

(

const T &

val

)

set value associed to node

Definition at line 393 of file Trie.h.

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

{
  _value = val;
}

template<typename T >

const edm::TrieNode< T > * edm::TrieNode< T >::subNode

(

)

const

Definition at line 449 of file Trie.h.

{
  return _firstSubNode;
}

template<typename T >

edm::TrieNode< T > * edm::TrieNode< T >::subNode

(

)

Definition at line 455 of file Trie.h.

{
  return _firstSubNode;
}

template<typename T >

edm::TrieNode< T > * edm::TrieNode< T >::subNodeByLabel

(

unsigned char

chr

)

Definition at line 474 of file Trie.h.

{
  return _sequentialSearch(_firstSubNode, _firstSubNodeLabel, chr);
}

template<typename T >

const edm::TrieNode< T > * edm::TrieNode< T >::subNodeByLabel

(

unsigned char

chr

)

const

Definition at line 467 of file Trie.h.

References edm::first().

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

{
  const TrieNode<T> *first = _firstSubNode;
  return _sequentialSearch(first, _firstSubNodeLabel, chr);
}

template<typename T >

unsigned char edm::TrieNode< T >::subNodeLabel

(

)

const

Definition at line 461 of file Trie.h.

{
  return _firstSubNodeLabel;
}

template<typename T >

const T & edm::TrieNode< T >::value

(

)

const

get value associed to node

Definition at line 399 of file Trie.h.

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

{
  return _value;
}

---

Member Data Documentation

template<typename T>

TrieNode<T>* edm::TrieNode< T >::_brother [private]

pointer to brother (node with same father as this one)

Definition at line 152 of file Trie.h.

template<typename T>

unsigned char edm::TrieNode< T >::_brotherLabel [private]

character to go to brother (node with same father as this one)

Definition at line 154 of file Trie.h.

template<typename T>

TrieNode<T>* edm::TrieNode< T >::_firstSubNode [private]

pointer to first sub node

Definition at line 156 of file Trie.h.

template<typename T>

unsigned char edm::TrieNode< T >::_firstSubNodeLabel [private]

character to go to first subnode

Definition at line 158 of file Trie.h.

template<typename T>

T edm::TrieNode< T >::_value [private]

value associed to this node

Definition at line 160 of file Trie.h.