ufe  3.2
Universal Front End is a DCC-agnostic component that will allow a DCC to browse and edit data in multiple data models
Ufe::Trie< T > Class Template Reference

Node for Universal Front End trie. More...

#include <selectionTrieFwd.h>

Public Member Functions

 Trie ()
 
 Trie (const Trie &)=delete
 
Trieoperator= (const Trie &)=delete
 
 Trie (Trie &&)
 
Trieoperator= (Trie &&)
 
TrieNode< T >::Ptr root () const
 
TrieNode< T >::Ptr add (const Path &path, const T &data)
 
TrieNode< T >::Ptr remove (const Path &)
 
TrieNode< T >::Ptr move (const Path &oldPath, const Path &newPath)
 
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 containsDescendantInclusive (const Path &path) const
 
bool containsAncestor (const Path &path) const
 
bool containsAncestorInclusive (const Path &path) const
 
int closestCommonAncestor () const
 
std::size_t size () const
 
bool empty () const
 

Private Member Functions

TrieNode< T >::Ptr createNode (const Path &path)
 
void cleanUpNode (const typename TrieNode< T >::Ptr &node)
 
template<bool INCLUDE_DESCENDANT>
bool containsAncestorHelper (const Path &path) const
 
template<bool INCLUDE_ANCESTOR>
bool containsDescendantHelper (const Path &path) 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 runtime, a dictionary of children trie nodes, and optionally data. The runtime node is the parent of children runtime 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 runtime 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 204 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 208 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 245 of file trie.imp.h.

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

Here is the call graph for this function:

◆ cleanUpNode()

template<typename T >
void Ufe::Trie< T >::cleanUpNode ( const typename TrieNode< T >::Ptr &  node)
private

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

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

Here is the call graph for this function:

◆ clear()

template<typename T >
void Ufe::Trie< T >::clear ( )

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

◆ closestCommonAncestor()

template<typename T >
int Ufe::Trie< T >::closestCommonAncestor ( ) const

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

◆ contains()

template<typename T >
bool Ufe::Trie< T >::contains ( const Path path) const

Definition at line 280 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 372 of file trie.imp.h.

◆ containsAncestorHelper()

template<typename T >
template<bool INCLUDE_DESCENDANT>
bool Ufe::Trie< T >::containsAncestorHelper ( const Path path) const
private

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

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

Here is the call graph for this function:

◆ containsAncestorInclusive()

template<typename T >
bool Ufe::Trie< T >::containsAncestorInclusive ( const Path path) const

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

◆ containsDescendant()

template<typename T >
bool Ufe::Trie< T >::containsDescendant ( const Path path) const

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

◆ containsDescendantHelper()

template<typename T >
template<bool INCLUDE_ANCESTOR>
bool Ufe::Trie< T >::containsDescendantHelper ( const Path path) const
private

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

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

Here is the call graph for this function:

◆ containsDescendantInclusive()

template<typename T >
bool Ufe::Trie< T >::containsDescendantInclusive ( const Path path) const

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

◆ createNode()

template<typename T >
TrieNode< T >::Ptr Ufe::Trie< T >::createNode ( const Path path)
private

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

References Ufe::TrieNode< T >::add(), 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 447 of file trie.imp.h.

◆ find()

template<typename T >
TrieNode< T >::Ptr Ufe::Trie< T >::find ( const Path path) const

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

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

Here is the call graph for this function:

◆ move()

template<typename T >
TrieNode< T >::Ptr Ufe::Trie< T >::move ( const Path oldPath,
const Path newPath 
)

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

References Ufe::Path::back(), Ufe::Path::pop(), and UFE_ASSERT_MSG.

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 265 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 214 of file trie.imp.h.

◆ remove()

template<typename T >
TrieNode< T >::Ptr Ufe::Trie< T >::remove ( const Path p)

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

References Ufe::TrieNode< T >::clearData(), Ufe::TrieNode< T >::hasData(), 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 222 of file trie.imp.h.

◆ size()

template<typename T >
std::size_t Ufe::Trie< T >::size ( ) const

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

Member Data Documentation

◆ fRoot

template<typename T >
TrieNode<T>::Ptr Ufe::Trie< T >::fRoot
private

Definition at line 191 of file trie.h.


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