ufe 7.0
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 126 of file trie.h.

Constructor & Destructor Documentation

◆ Trie() [1/3]

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

Definition at line 215 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 219 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 256 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 420 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 446 of file trie.imp.h.

◆ closestCommonAncestor()

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

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

◆ contains()

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

Definition at line 291 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 383 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 342 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 389 of file trie.imp.h.

◆ containsDescendant()

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

Definition at line 329 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 298 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 335 of file trie.imp.h.

◆ createNode()

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

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

◆ find()

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

Definition at line 266 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 432 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 276 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 225 of file trie.imp.h.

◆ remove()

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

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

◆ size()

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

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

Member Data Documentation

◆ fRoot

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

Definition at line 195 of file trie.h.

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