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
trie.h
Go to the documentation of this file.
1 #line 1 "S:/jenkins/workspace/ECP/ufe/ufe-full-python3.9-windows/ufe/include/trie.h"
2 #ifndef _ufeTrie
3 #define _ufeTrie
4 // =======================================================================
5 // Copyright 2019 Autodesk, Inc. All rights reserved.
6 //
7 // This computer source code and related instructions and comments are the
8 // unpublished confidential and proprietary information of Autodesk, Inc.
9 // and are protected under applicable copyright and trade secret law. They
10 // may not be disclosed to, copied or used by any third party without the
11 // prior written consent of Autodesk, Inc.
12 // =======================================================================
13 
14 #include "pathComponent.h"
15 #include "path.h"
16 
17 #include <memory>
18 #include <unordered_map>
19 
20 UFE_NS_DEF {
21 
23 
38 template<typename T> class Trie;
39 
40 template<typename T>
41 class TrieNode : public std::enable_shared_from_this< TrieNode<T> >
42 {
43  friend class Trie<T>;
44 public:
45  typedef std::shared_ptr<TrieNode> Ptr;
46 
47  TrieNode(const PathComponent& component);
48 
49  // Create a trie node with a null component.
50  TrieNode();
51 
52  Ptr parent() const;
53 
54  // Child addition and removal.
55  void add(const Ptr& child);
56  void remove(const Ptr& child);
57 
58  // Child lookup.
59  bool contains(const PathComponent& child) const;
60  Ptr operator[](const PathComponent& child) const;
61 
62  // Number of children TrieNode's.
63  std::size_t size() const;
64 
65  // Number of nodes in the tree rooted at this node, including this node.
66  std::size_t treeSize() const;
67 
68  // Convenience method for size() == 0.
69  bool empty() const;
70 
71  PathComponent component() const;
72 
73  // Change the component of this node, adjusting the parent accordingly.
74  void rename(const PathComponent& component);
75 
76  // Change the component & parent of this node, adjusting the old and new parent accordingly.
77  void move(const PathComponent& component, const Ptr& newParent);
78 
79  // Copy the data into the node, and set the has data flag.
80  void setData(const T& data);
81 
82  // Access the node's data. The hasData() method must return true for data
83  // to be valid, else the return data is stale.
84  const T& data() const;
85 
86  bool hasData() const;
87 
88  // Called to find the depth of the closest common ancestor to all nodes
89  // with data. Calls itself recursively looking for either multiple children
90  // or the first node with associated data.
91  // Increments the depth parameter as it moves down the trie which can then
92  // be used to create a path that matches the specific node.
93  int closestCommonAncestor( int depth ) const;
94 
95 private:
96 
97  typedef std::unordered_map<PathComponent, Ptr> Children;
98  typedef std::weak_ptr<TrieNode> ParentPtr;
99 
100  // Clearing out of the TrieNode should be managed by the Trie only,
101  // so keeping these private.
102  void clear();
103  void clearData();
104 
105  void setParent(Ptr parent);
106 
110  bool fHasData;
111  T fData;
112 };
113 
115 
123 template<typename T>
124 class Trie
125 {
126 public:
127 
128  Trie();
129 
130  Trie(const Trie&) = delete;
131  Trie& operator=(const Trie&) = delete;
132 
133  // Move assignment and construction.
134  Trie(Trie&&);
135  Trie& operator=(Trie&&);
136 
137  typename TrieNode<T>::Ptr root() const;
138 
139  typename TrieNode<T>::Ptr add(const Path& path, const T& data);
140  typename TrieNode<T>::Ptr remove(const Path&);
141  // Move the entire hierarchy rooted at oldPath to newPath. Returns the resulting
142  // trie node if successful, else a null pointer.
143  typename TrieNode<T>::Ptr move(const Path& oldPath, const Path& newPath);
144  void clear();
145 
146  // Lookup. contains() is a convenience for bool(find(path)).
147  typename TrieNode<T>::Ptr find(const Path& path) const;
148  bool contains(const Path& path) const;
149 
150  // Return the trie node corresponding to the path, regardless of whether it
151  // has data or not. If the trie has no such node, returns a null pointer.
152  typename TrieNode<T>::Ptr node(const Path& path) const;
153 
154  // Query whether the trie contains a descendant of the argument path. Must
155  // be a strict descendant: if the trie contains only the argument
156  // itself, returns false. If the argument path is empty, returns false.
157  bool containsDescendant(const Path& path) const;
158 
159  // convenience for contains(path) ||constainsDescendant(path)
160  bool containsDescendantInclusive(const Path& path) const;
161 
162  // Query whether the trie contains an ancestor of the argument path.
163  // Must be a strict ancestor: if the trie contains only the argument
164  // itself, returns false. If the argument path is empty, returns false.
165  bool containsAncestor(const Path& path) const;
166 
167  // convenience for contains(path) || containsAncestor(path)
168  bool containsAncestorInclusive(const Path& path) const;
169 
170  // Returns the depth of the closest common ancestor of all leaf nodes.
171  // Return -1 if the trie is empty.
172  // Return 0 if the common ancestor is the root of the scene graph.
173  int closestCommonAncestor() const;
174 
175  // Number of nodes in the trie, including the root node. For testing
176  // and debugging purposes, as it traverses the trie and counts nodes.
177  std::size_t size() const;
178 
179  // Convenience method for size() == 0.
180  bool empty() const;
181 
182 private:
183 
184  typename TrieNode<T>::Ptr createNode(const Path& path);
185  void cleanUpNode(const typename TrieNode<T>::Ptr& node);
186  template<bool INCLUDE_DESCENDANT>
187  bool containsAncestorHelper(const Path& path) const;
188  template<bool INCLUDE_ANCESTOR>
189  bool containsDescendantHelper(const Path& path) const;
190 
192 };
193 
194 }
195 
196 #endif /* _ufeTrie */
bool fHasData
Definition: trie.h:110
std::unordered_map< PathComponent, Ptr > Children
Definition: trie.h:97
Constant string representation with fixed space and O(1) comparison.
Definition: pathComponent.h:33
Node for Universal Front End trie.
Identify an object or 3D path in the scene.
Definition: path.h:37
#define UFE_NS_DEF
Definition: ufe.h:35
ParentPtr fParent
Definition: trie.h:108
std::weak_ptr< TrieNode > ParentPtr
Definition: trie.h:98
std::shared_ptr< TrieNode > Ptr
Definition: trie.h:45
Path path(const std::string &pathString)
TrieNode< T >::Ptr fRoot
Definition: trie.h:191
PathComponent fComponent
Definition: trie.h:107
Children fChildren
Definition: trie.h:109