ufe 5.5
Universal Front End is a DCC-agnostic component that will allow a DCC to browse and edit data in multiple data models
Public Member Functions | Private Member Functions | Private Attributes | List of all members
Ufe::Trie< T > Class Template Reference

Node for Universal Front End trie. More...

#include <trie.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 &)
 
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 127 of file trie.h.

Constructor & Destructor Documentation

◆ Trie() [1/3]

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

Definition at line 216 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 220 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 257 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 421 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 447 of file trie.imp.h.

◆ closestCommonAncestor()

template<typename T >
int Ufe::Trie< T >::closestCommonAncestor

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

◆ contains()

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

Definition at line 292 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 384 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 343 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 390 of file trie.imp.h.

◆ containsDescendant()

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

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

References Ufe::Path::empty(), and Ufe::TrieNode< T >::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 336 of file trie.imp.h.

◆ createNode()

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

Definition at line 240 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

Returns true when the trie is empty. Since a trie always has a root node, this method is a convenience for root()->empty().

Complexity
O(1).

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

◆ find()

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

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

References Ufe::Path::back(), Ufe::TrieNode< T >::move(), Ufe::TrieNode< T >::parent(), 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 277 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 226 of file trie.imp.h.

◆ remove()

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

Definition at line 402 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

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

◆ size()

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

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

Member Data Documentation

◆ fRoot

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

Definition at line 196 of file trie.h.

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