Ufe::Trie< T > Class Template Reference

Node for Universal Front End trie. More...

#include <selectionTrieFwd.h>

Public Member Functions
	Trie ()
	Trie (const Trie &)=delete
Trie &	operator= (const Trie &)=delete
	Trie (Trie &&)
Trie &	operator= (Trie &&)
TrieNode< T >::Ptr	root () const
TrieNode< T >::Ptr	add (const Path &path, const T &data)
TrieNode< T >::Ptr	remove (const Path &)
void	clear ()
TrieNode< T >::Ptr	find (const Path &path) const
bool	contains (const Path &path) const
TrieNode< T >::Ptr	node (const Path &path) const
bool	containsDescendant (const Path &path) const
bool	containsAncestor (const Path &path) const
int	closestCommonAncestor () const
std::size_t	size () const
bool	empty () const

Private Attributes
TrieNode< T >::Ptr	fRoot

Detailed Description

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

Node for Universal Front End trie.

Trie.

Each node in the trie represents a path component in the graph, except the trie root node, which is empty. Each node has a dictionary of children trie nodes.

It holds the name of a node in a run-time, a dictionary of children trie nodes, and optionally data. The run-time node is the parent of children run-time nodes, each of which have an associated trie node.

Trie nodes created to represent components that are iternal to the trie won't have data. For example, in a trivial trie, for a node with path "a|b|c|d" that has data, trie nodes for path components a, b, and c will not have data, while the trie node for d will. Data can later be added to run-time node a, b, or c.

The trie is a prefix tree data structure to allow fast hierarchical searching by path. The path can represent containment, or a 3D hierarchy.

Trie nodes can have data. A trie node without data is an internal node, and only exists to serve as parent of one or more descendant trie node(s).

Definition at line 18 of file selectionTrieFwd.h.

Constructor & Destructor Documentation

Trie() [1/3]

template<typename T >

Ufe::Trie< T >::Trie

(

)

Definition at line 190 of file trie.imp.h.

Trie() [2/3]

template<typename T >

Ufe::Trie< T >::Trie ( const Trie< T > &  )

delete

Trie() [3/3]

template<typename T >

Ufe::Trie< T >::Trie

(

Trie< T > &&

rhs

)

Definition at line 194 of file trie.imp.h.

Member Function Documentation

add()

template<typename T >

TrieNode< T >::Ptr Ufe::Trie< T >::add	(	const Path &	path,
		const T &	data
	)

Definition at line 214 of file trie.imp.h.

References Ufe::TrieNode< T >::add(), Ufe::PathString::path(), and Ufe::TrieNode< T >::setData().

Here is the call graph for this function:

clear()

template<typename T >

void Ufe::Trie< T >::clear

(

)

Definition at line 365 of file trie.imp.h.

closestCommonAncestor()

template<typename T >

int Ufe::Trie< T >::closestCommonAncestor

(

)

const

Definition at line 335 of file trie.imp.h.

contains()

template<typename T >

bool Ufe::Trie< T >::contains

(

const Path &

path

)

const

Definition at line 262 of file trie.imp.h.

References Ufe::PathString::path().

Here is the call graph for this function:

containsAncestor()

template<typename T >

bool Ufe::Trie< T >::containsAncestor

(

const Path &

path

)

const

Definition at line 299 of file trie.imp.h.

References Ufe::Path::empty(), Ufe::TrieNode< T >::hasData(), and Ufe::Path::pop().

Here is the call graph for this function:

containsDescendant()

template<typename T >

bool Ufe::Trie< T >::containsDescendant

(

const Path &

path

)

const

Definition at line 268 of file trie.imp.h.

References Ufe::TrieNode< T >::empty(), Ufe::Path::empty(), and Ufe::PathString::path().

Here is the call graph for this function:

empty()

template<typename T >

bool Ufe::Trie< T >::empty

(

)

const

Definition at line 377 of file trie.imp.h.

find()

template<typename T >

TrieNode< T >::Ptr Ufe::Trie< T >::find

(

const Path &

path

)

const

Definition at line 232 of file trie.imp.h.

References Ufe::TrieNode< T >::hasData(), and Ufe::PathString::path().

Here is the call graph for this function:

node()

template<typename T >

TrieNode< T >::Ptr Ufe::Trie< T >::node

(

const Path &

path

)

const

Definition at line 247 of file trie.imp.h.

References Ufe::PathString::path().

Here is the call graph for this function:

operator=() [1/2]

template<typename T >

Trie& Ufe::Trie< T >::operator= ( const Trie< T > &  )

delete

operator=() [2/2]

template<typename T >

Trie< T > & Ufe::Trie< T >::operator=

(

Trie< T > &&

rhs

)

Definition at line 200 of file trie.imp.h.

remove()

template<typename T >

TrieNode< T >::Ptr Ufe::Trie< T >::remove

(

const Path &

p

)

Definition at line 341 of file trie.imp.h.

References Ufe::TrieNode< T >::clearData(), Ufe::TrieNode< T >::empty(), Ufe::TrieNode< T >::hasData(), Ufe::TrieNode< T >::parent(), Ufe::TrieNode< T >::remove(), and UFE_ASSERT_MSG.

Here is the call graph for this function:

root()

template<typename T >

TrieNode< T >::Ptr Ufe::Trie< T >::root

(

)

const

Definition at line 208 of file trie.imp.h.

size()

template<typename T >

std::size_t Ufe::Trie< T >::size

(

)

const

Definition at line 371 of file trie.imp.h.

Member Data Documentation

fRoot

template<typename T >

TrieNode<T>::Ptr Ufe::Trie< T >::fRoot

private

Definition at line 172 of file trie.h.

---

The documentation for this class was generated from the following files:

• include/ufe/selectionTrieFwd.h
• include/ufe/trie.h
• include/ufe/trie.imp.h