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.imp.h
Go to the documentation of this file.
1 #line 1 "S:/jenkins/workspace/ECP/ufe/ufe-full-python3.9-windows/ufe/include/trie.imp.h"
2 #ifndef _ufeTrie_imp
3 #define _ufeTrie_imp
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 "trie.h"
15 #include "ufeAssert.h"
16 
17 #include <numeric>
18 
19 UFE_NS_DEF {
20 
21 //==============================================================================
22 // CLASS Ufe::TrieNode
23 //==============================================================================
24 
25 template<typename T>
27  : fComponent(component), fParent(), fChildren(), fHasData(false),
28  fData()
29 {}
30 
31 template<typename T>
33 {}
34 
35 template<typename T>
36 void TrieNode<T>::add(const Ptr& child)
37 {
38  // Child must not exist yet.
39  UFE_ASSERT_MSG(fChildren.find(child->component()) == fChildren.end(),
40  "Child trie node already exists.");
41 
42  fChildren[child->component()] = child;
43  // Go through this pointer to prevent "no arguments to ‘shared_from_this’
44  // that depend on a template parameter" error.
45  child->setParent(this->shared_from_this());
46 }
47 
48 template<typename T>
49 void TrieNode<T>::remove(const Ptr& child)
50 {
51  UFE_ASSERT_COMPILED(typename Children::size_type nbErased = )
52  fChildren.erase(child->component());
53  UFE_ASSERT_MSG(nbErased == 1, "Child trie node does not exist.");
54  child->setParent(Ptr());
55 }
56 
57 template<typename T>
59 {
60  fComponent = PathComponent();
61  fParent = ParentPtr();
62  fChildren.clear();
63  fHasData = false;
64 }
65 
66 template<typename T>
68 {
69  return fParent.lock();
70 }
71 
72 template<typename T>
73 bool TrieNode<T>::contains(const PathComponent& component) const
74 {
75  return fChildren.find(component) != fChildren.end();
76 }
77 
78 template<typename T>
79 typename TrieNode<T>::Ptr TrieNode<T>::operator[](const PathComponent& component) const
80 {
81  typename Children::const_iterator const found = fChildren.find(component);
82  return found == fChildren.end() ? Ptr() : found->second;
83 }
84 
85 template<typename T>
86 int TrieNode<T>::closestCommonAncestor( int depth ) const
87 {
88  std::size_t sz = size();
89 
90  // If this node has data or it's a leaf node then return
91  // before incrementing. The common ancestor is our
92  // parent.
93  //
94  // In practice both of these conditions should be the same,
95  // but we can call this function with an empty trie in which
96  // case we will have size 0 and no data in the empty root node.
97  if ( hasData() || 0 == sz) {
98  return depth;
99  }
100 
101  depth++;
102 
103  // If this node has multiple children then it is the
104  // common ancestor.
105  if (1 < sz) {
106  return depth;
107  }
108 
109  // Else we need to keep going...
110  typename Children::const_iterator const next = fChildren.begin();
111  return next->second->closestCommonAncestor(depth);
112 }
113 
114 template<typename T>
115 std::size_t TrieNode<T>::size() const
116 {
117  return fChildren.size();
118 }
119 
120 template<typename T>
121 std::size_t TrieNode<T>::treeSize() const
122 {
123  return std::accumulate(
124  fChildren.begin(), fChildren.end(), std::size_t(1),
125  [](std::size_t treeSize, const typename Children::value_type& child) {
126  return treeSize+child.second->treeSize();
127  });
128 }
129 
130 template<typename T>
131 bool TrieNode<T>::empty() const
132 {
133  return size() == 0;
134 }
135 
136 template<typename T>
138 {
139  return fComponent;
140 }
141 
142 template<typename T>
143 void TrieNode<T>::rename(const PathComponent& component)
144 {
145  UFE_ASSERT_MSG(parent()->contains(fComponent),
146  "Cannot rename child trie node, not found in parent.");
147  auto self = this->shared_from_this();
148  auto p = parent();
149  p->remove(self);
150  fComponent = component;
151  p->add(self);
152 }
153 
154 template<typename T>
155 void TrieNode<T>::move(const PathComponent& component, const Ptr& newParent)
156 {
157  auto oldParent = parent();
158  if (newParent == oldParent)
159  return;
160  UFE_ASSERT_MSG(!newParent->contains(component), "Cannot reparent child trie node, new component already exists in new parent.");
161  UFE_ASSERT_MSG(oldParent->contains(fComponent), "Cannot reparent child trie node, not found in parent.");
162  auto self = this->shared_from_this();
163  oldParent->remove(self);
164  fComponent = component;
165  newParent->add(self);
166 }
167 
168 template<typename T>
169 void TrieNode<T>::setData(const T& data)
170 {
171  fHasData = true;
172  fData = data;
173 }
174 
175 template<typename T>
177 {
178  fHasData = false;
179 }
180 
181 template<typename T>
182 const T& TrieNode<T>::data() const
183 {
184  return fData;
185 }
186 
187 template<typename T>
189 {
190  return fHasData;
191 }
192 
193 template<typename T>
195 {
196  fParent = ParentPtr(parent);
197 }
198 
199 //==============================================================================
200 // CLASS Ufe::Trie
201 //==============================================================================
202 
203 template<typename T>
204 Trie<T>::Trie() : fRoot(std::make_shared< TrieNode<T> >())
205 {}
206 
207 template<typename T>
208 Trie<T>::Trie(Trie&& rhs) : fRoot(std::move(rhs.fRoot))
209 {
210  rhs.fRoot = std::make_shared< TrieNode<T> >();
211 }
212 
213 template<typename T>
215 {
216  fRoot = std::move(rhs.fRoot);
217  rhs.fRoot = std::make_shared< TrieNode<T> >();
218  return *this;
219 }
220 
221 template<typename T>
223 {
224  return fRoot;
225 }
226 
227 template<typename T>
229 {
230  // Walk down the path inside the tree, adding trie nodes if required.
231  typename TrieNode<T>::Ptr trieNode = root();
232  for (const PathComponent& c : path) {
233  typename TrieNode<T>::Ptr child = (*trieNode)[c];
234  if (!child) {
235  child = std::make_shared< TrieNode<T> >(c);
236  trieNode->add(child);
237  }
238  trieNode = child;
239  }
240 
241  return trieNode;
242 }
243 
244 template<typename T>
245 typename TrieNode<T>::Ptr Trie<T>::add(const Path& path, const T& data)
246 {
247  typename TrieNode<T>::Ptr trieNode = createNode(path);
248 
249  // Last trie node gets the data.
250  trieNode->setData(data);
251  return trieNode;
252 }
253 
254 template<typename T>
255 typename TrieNode<T>::Ptr Trie<T>::find(const Path& path) const
256 {
257  // Walk down the path inside the tree.
258  typename TrieNode<T>::Ptr trieNode = node(path);
259  if (trieNode && trieNode->hasData())
260  return trieNode;
261  return typename TrieNode<T>::Ptr();
262 }
263 
264 template<typename T>
265 typename TrieNode<T>::Ptr Trie<T>::node(const Path& path) const
266 {
267  // Walk down the path inside the tree.
268  typename TrieNode<T>::Ptr trieNode = root();
269  for (const PathComponent& c : path) {
270  typename TrieNode<T>::Ptr child = (*trieNode)[c];
271  if (!child) {
272  return typename TrieNode<T>::Ptr();
273  }
274  trieNode = child;
275  }
276  return trieNode;
277 }
278 
279 template<typename T>
280 bool Trie<T>::contains(const Path& path) const
281 {
282  return bool(find(path));
283 }
284 
285 template<typename T>
286 template<bool INCLUDE_ANCESTOR>
287 bool Trie<T>::containsDescendantHelper(const Path& ancestorPath) const
288 {
289  // Algorithm summary: walk down the path tree to the end of the argument
290  // path. If that trie node has children, a descendant is in the trie.
291 
292  // By definition, an empty path has no descendants.
293  if (ancestorPath.empty()) {
294  return false;
295  }
296 
297  // Walk down the complete path inside the tree, if possible.
298  typename TrieNode<T>::Ptr trieNode = root();
299  for (const PathComponent& c : ancestorPath) {
300  typename TrieNode<T>::Ptr child = (*trieNode)[c];
301  // If we've reached a trie leaf node before the end of our path, there
302  // cannot be any descendants in the trie.
303  if (!child) {
304  return false;
305  }
306  trieNode = child;
307  }
308  // We reached the end of the argument path. Whether the trieNode we
309  // reached has data or not, return true if it has descendants. To
310  // implement a containsDescendantInclusive, which would include the
311  // argument path, we simply return true: at this point we've reached
312  // either an internal node, which by definition has children, or a leaf
313  // node with no descendants, which by definition has data.
314  return INCLUDE_ANCESTOR ? true : !trieNode->empty();
315 }
316 
317 template<typename T>
318 bool Trie<T>::containsDescendant(const Path& ancestorPath) const
319 {
320  return containsDescendantHelper<false>(ancestorPath);
321 }
322 
323 template<typename T>
324 bool Trie<T>::containsDescendantInclusive(const Path& ancestorPath) const
325 {
326  return containsDescendantHelper<true>(ancestorPath);
327 }
328 
329 template<typename T>
330 template<bool INCLUDE_DESCENDANT>
331 bool Trie<T>::containsAncestorHelper(const Path& descendantPath) const
332 {
333  // Algorithm summary: walk down the path tree trying to find a node
334  // with data.
335 
336  // By definition, an empty path has no ancestors.
337  if (descendantPath.empty()) {
338  return false;
339  }
340 
341  // Walk down the path inside the tree. As soon as we find a trieNode with
342  // data, return true.
343  typename TrieNode<T>::Ptr trieNode = root();
344  auto pathEndIt = descendantPath.cend();
345  // When we are not including descendentPath then finding the last PathComponent of
346  // descendentPath in the trie does not count. Set up the iterator so that we don't
347  // check the final PathComponent.
348  if (!INCLUDE_DESCENDANT) {
349  pathEndIt = std::prev(pathEndIt);
350  }
351  for (auto pathIt = descendantPath.cbegin(); pathIt != pathEndIt; ++pathIt) {
352  const PathComponent& c = *pathIt;
353  typename TrieNode<T>::Ptr child = (*trieNode)[c];
354  // If we've reached a trie leaf node before the end of our path, there
355  // is no trie node with data as ancestor of the path.
356  if (!child) {
357  return false;
358  }
359  trieNode = child;
360 
361  // Found a trieNode with data.
362  if (trieNode->hasData()) {
363  return true;
364  }
365  }
366  // We reached the end of the parent path without returning true, therefore
367  // there are no ancestors.
368  return false;
369 }
370 
371 template<typename T>
372 bool Trie<T>::containsAncestor(const Path& descendantPath) const
373 {
374  return containsAncestorHelper<false>(descendantPath);
375 }
376 
377 template<typename T>
378 bool Trie<T>::containsAncestorInclusive(const Path& descendantPath) const
379 {
380  return containsAncestorHelper<true>(descendantPath);
381 }
382 
383 template<typename T>
385 {
386  return root()->closestCommonAncestor(-1);
387 }
388 
389 template<typename T>
391 {
392  typename TrieNode<T>::Ptr found = find(p);
393  if (!found) {
394  return found;
395  }
396 
397  // First, clear the data from the trie node.
398  UFE_ASSERT_MSG(found->hasData(), "Trie node has no associated data.");
399  found->clearData();
400 
401  // Next, clean up trie if required. If trie node has no children and
402  // no data, remove it, and recurse up to its parent.
403  cleanUpNode(found);
404 
405  return found;
406 }
407 
408 template<typename T>
409 void Trie<T>::cleanUpNode(const typename TrieNode<T>::Ptr& node)
410 {
411  typename TrieNode<T>::Ptr child = node;
412  while (child->empty() && !child->hasData() && child != root()) {
413  typename TrieNode<T>::Ptr parent = child->parent();
414  parent->remove(child);
415  child = parent;
416  }
417 }
418 
419 
420 template<typename T>
421 typename TrieNode<T>::Ptr Trie<T>::move(const Path& oldPath, const Path& newPath)
422 {
423  typename TrieNode<T>::Ptr newParentNode = createNode(newPath.pop());
424  typename TrieNode<T>::Ptr trieNode = node(oldPath);
425  UFE_ASSERT_MSG(trieNode, "Trie does not contain path");
426  typename TrieNode<T>::Ptr oldParentNode = trieNode->parent();
427 
428  trieNode->move(newPath.back(), newParentNode);
429  cleanUpNode(oldParentNode);
430 
431  return trieNode;
432 }
433 
434 template<typename T>
436 {
437  root()->clear();
438 }
439 
440 template<typename T>
441 std::size_t Trie<T>::size() const
442 {
443  return root()->treeSize();
444 }
445 
446 template<typename T>
447 bool Trie<T>::empty() const
448 {
449  return size() == 0;
450 }
451 
452 }
453 
454 #endif /* _ufeTrie_imp */
void setData(const T &data)
Definition: trie.imp.h:169
TrieNode< T >::Ptr node(const Path &path) const
Definition: trie.imp.h:265
bool containsDescendantHelper(const Path &path) const
Definition: trie.imp.h:287
void clear()
Definition: trie.imp.h:58
void cleanUpNode(const typename TrieNode< T >::Ptr &node)
Definition: trie.imp.h:409
std::size_t treeSize() const
Definition: trie.imp.h:121
Components::const_iterator cbegin() const
Iteration interface on PathComponents.
bool empty() const
bool containsAncestor(const Path &path) const
Definition: trie.imp.h:372
void remove(const Ptr &child)
Definition: trie.imp.h:49
std::shared_ptr< ObservableSelection > Ptr
bool containsAncestorInclusive(const Path &path) const
Definition: trie.imp.h:378
Constant string representation with fixed space and O(1) comparison.
Definition: pathComponent.h:33
Components::const_iterator cend() const
Iteration interface on PathComponents.
Definition: path.h:197
const T & data() const
Definition: trie.imp.h:182
Trie & operator=(const Trie &)=delete
bool containsAncestorHelper(const Path &path) const
Definition: trie.imp.h:331
bool contains(const Path &path) const
Definition: trie.imp.h:280
void setParent(Ptr parent)
Definition: trie.imp.h:194
PathComponent component() const
Definition: trie.imp.h:137
Node for Universal Front End trie.
#define UFE_ASSERT_MSG(EXPR, MSG)
Definition: ufeAssert.h:34
bool containsDescendantInclusive(const Path &path) const
Definition: trie.imp.h:324
bool containsDescendant(const Path &path) const
Definition: trie.imp.h:318
void rename(const PathComponent &component)
Definition: trie.imp.h:143
void add(const Ptr &child)
Definition: trie.imp.h:36
Identify an object or 3D path in the scene.
Definition: path.h:37
int closestCommonAncestor() const
Definition: trie.imp.h:384
std::size_t size() const
Definition: trie.imp.h:115
void clearData()
Definition: trie.imp.h:176
bool contains(const PathComponent &child) const
Definition: trie.imp.h:73
PathComponent back() const
Ptr operator[](const PathComponent &child) const
Definition: trie.imp.h:79
TrieNode< T >::Ptr remove(const Path &)
Definition: trie.imp.h:390
#define UFE_NS_DEF
Definition: ufe.h:35
Ptr parent() const
Definition: trie.imp.h:67
bool hasData() const
Definition: trie.imp.h:188
TrieNode< T >::Ptr root() const
Definition: trie.imp.h:222
void move(const PathComponent &component, const Ptr &newParent)
Definition: trie.imp.h:155
bool empty() const
Definition: trie.imp.h:131
std::size_t size() const
Definition: trie.imp.h:441
TrieNode< T >::Ptr find(const Path &path) const
Definition: trie.imp.h:255
std::weak_ptr< TrieNode > ParentPtr
Definition: trie.h:98
int closestCommonAncestor(int depth) const
Definition: trie.imp.h:86
std::shared_ptr< TrieNode > Ptr
Definition: trie.h:45
void clear()
Definition: trie.imp.h:435
Path path(const std::string &pathString)
#define UFE_ASSERT_COMPILED(CODE)
Definition: ufeAssert.h:37
TrieNode< T >::Ptr move(const Path &oldPath, const Path &newPath)
Definition: trie.imp.h:421
Path pop() const
TrieNode< T >::Ptr add(const Path &path, const T &data)
Definition: trie.imp.h:245
bool empty() const
Definition: trie.imp.h:447
TrieNode< T >::Ptr createNode(const Path &path)
Definition: trie.imp.h:228