HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Traversal.h
Go to the documentation of this file.
1 //
2 // TM & (c) 2017 Lucasfilm Entertainment Company Ltd. and Lucasfilm Ltd.
3 // All rights reserved. See LICENSE.txt for license.
4 //
5 
6 #ifndef MATERIALX_TRAVERSAL_H
7 #define MATERIALX_TRAVERSAL_H
8 
9 /// @file
10 /// Graph traversal classes
11 
13 
15 
16 class Element;
17 
18 using ElementPtr = shared_ptr<Element>;
19 using ConstElementPtr = shared_ptr<const Element>;
20 
21 /// @class Edge
22 /// An edge between two connected Elements, returned during graph traversal.
23 ///
24 /// A valid Edge consists of a downstream element, an upstream element, and
25 /// optionally a connecting element that binds them. As an example, the edge
26 /// between two Node elements will contain a connecting element for the Input
27 /// of the downstream Node.
28 /// @sa Element::traverseGraph
30 {
31  public:
32  Edge(ElementPtr elemDown, ElementPtr elemConnect, ElementPtr elemUp) :
33  _elemDown(elemDown),
34  _elemConnect(elemConnect),
35  _elemUp(elemUp)
36  {
37  }
38  ~Edge() { }
39 
40  bool operator==(const Edge& rhs) const
41  {
42  return _elemDown == rhs._elemDown &&
43  _elemConnect == rhs._elemConnect &&
44  _elemUp == rhs._elemUp;
45  }
46  bool operator!=(const Edge& rhs) const
47  {
48  return !(*this == rhs);
49  }
50  bool operator<(const Edge& rhs) const
51  {
52  return std::tie(_elemDown, _elemConnect, _elemUp) < std::tie(rhs._elemDown, rhs._elemConnect, rhs._elemUp);
53  }
54 
55  operator bool() const;
56 
57  /// Return the downstream element of the edge.
59  {
60  return _elemDown;
61  }
62 
63  /// Return the connecting element of the edge, if any.
65  {
66  return _elemConnect;
67  }
68 
69  /// Return the upstream element of the edge.
71  {
72  return _elemUp;
73  }
74 
75  /// Return the name of this edge, if any.
76  string getName() const;
77 
78  private:
79  ElementPtr _elemDown;
80  ElementPtr _elemConnect;
81  ElementPtr _elemUp;
82 };
83 
84 /// @class TreeIterator
85 /// An iterator object representing the state of a tree traversal.
86 ///
87 /// @sa Element::traverseTree
89 {
90  public:
91  explicit TreeIterator(ElementPtr elem) :
92  _elem(elem),
93  _prune(false),
94  _holdCount(0)
95  {
96  }
98 
99  private:
100  using StackFrame = std::pair<ElementPtr, size_t>;
101 
102  public:
103  bool operator==(const TreeIterator& rhs) const
104  {
105  return _elem == rhs._elem &&
106  _stack == rhs._stack &&
107  _prune == rhs._prune;
108  }
109  bool operator!=(const TreeIterator& rhs) const
110  {
111  return !(*this == rhs);
112  }
113 
114  /// Dereference this iterator, returning the current element in the
115  /// traversal.
117  {
118  return _elem;
119  }
120 
121  /// Iterate to the next element in the traversal.
122  TreeIterator& operator++();
123 
124  /// @name Elements
125  /// @{
126 
127  /// Return the current element in the traversal.
129  {
130  return _elem;
131  }
132 
133  /// @}
134  /// @name Depth
135  /// @{
136 
137  /// Return the element depth of the current traversal, where the starting
138  /// element represents a depth of zero.
139  size_t getElementDepth() const
140  {
141  return _stack.size();
142  }
143 
144  /// @}
145  /// @name Pruning
146  /// @{
147 
148  /// Set the prune subtree flag, which controls whether the current subtree
149  /// is pruned from traversal.
150  /// @param prune If set to true, then the current subtree will be pruned.
152  {
153  _prune = prune;
154  }
155 
156  /// Return the prune subtree flag, which controls whether the current
157  /// subtree is pruned from traversal.
158  bool getPruneSubtree() const
159  {
160  return _prune;
161  }
162 
163  /// @}
164  /// @name Range Methods
165  /// @{
166 
167  /// Interpret this object as an iteration range, and return its begin
168  /// iterator.
169  TreeIterator& begin(size_t holdCount = 0)
170  {
171  _holdCount = holdCount;
172  return *this;
173  }
174 
175  /// Return the sentinel end iterator for this class.
176  static const TreeIterator& end();
177 
178  /// @}
179 
180  private:
181  ElementPtr _elem;
182  vector<StackFrame> _stack;
183  bool _prune;
184  size_t _holdCount;
185 };
186 
187 /// @class GraphIterator
188 /// An iterator object representing the state of an upstream graph traversal.
189 ///
190 /// @sa Element::traverseGraph
192 {
193  public:
194  explicit GraphIterator(ElementPtr elem) :
195  _upstreamElem(elem),
196  _prune(false),
197  _holdCount(0)
198  {
199  _pathElems.insert(elem);
200  }
202 
203  private:
204  using ElementSet = std::set<ElementPtr>;
205  using StackFrame = std::pair<ElementPtr, size_t>;
206 
207  public:
208  bool operator==(const GraphIterator& rhs) const
209  {
210  return _upstreamElem == rhs._upstreamElem &&
211  _stack == rhs._stack &&
212  _prune == rhs._prune;
213  }
214  bool operator!=(const GraphIterator& rhs) const
215  {
216  return !(*this == rhs);
217  }
218 
219  /// Dereference this iterator, returning the current edge in the traversal.
220  Edge operator*() const
221  {
222  return Edge(getDownstreamElement(),
223  getConnectingElement(),
224  getUpstreamElement());
225  }
226 
227  /// Iterate to the next edge in the traversal.
228  /// @throws ExceptionFoundCycle if a cycle is encountered.
229  GraphIterator& operator++();
230 
231  /// @name Elements
232  /// @{
233 
234  /// Return the downstream element of the current edge.
236  {
237  return !_stack.empty() ? _stack.back().first : ElementPtr();
238  }
239 
240  /// Return the connecting element, if any, of the current edge.
242  {
243  return _connectingElem;
244  }
245 
246  /// Return the upstream element of the current edge.
248  {
249  return _upstreamElem;
250  }
251 
252  /// Return the index of the current edge within the range of upstream edges
253  /// available to the downstream element.
254  size_t getUpstreamIndex() const
255  {
256  return !_stack.empty() ? _stack.back().second : 0;
257  }
258 
259  /// @}
260  /// @name Depth
261  /// @{
262 
263  /// Return the element depth of the current traversal, where a single edge
264  /// between two elements represents a depth of one.
265  size_t getElementDepth() const
266  {
267  return _stack.size();
268  }
269 
270  /// Return the node depth of the current traversal, where a single edge
271  /// between two nodes represents a depth of one.
272  size_t getNodeDepth() const;
273 
274  /// @}
275  /// @name Pruning
276  /// @{
277 
278  /// Set the prune subgraph flag, which controls whether the current subgraph
279  /// is pruned from traversal.
280  /// @param prune If set to true, then the current subgraph will be pruned.
282  {
283  _prune = prune;
284  }
285 
286  /// Return the prune subgraph flag, which controls whether the current
287  /// subgraph is pruned from traversal.
288  bool getPruneSubgraph() const
289  {
290  return _prune;
291  }
292 
293  /// @}
294  /// @name Range Methods
295  /// @{
296 
297  /// Interpret this object as an iteration range, and return its begin
298  /// iterator.
299  GraphIterator& begin(size_t holdCount = 0)
300  {
301  // Increment once to generate a valid edge.
302  if (_stack.empty())
303  {
304  operator++();
305  }
306 
307  _holdCount = holdCount;
308  return *this;
309  }
310 
311  /// Return the sentinel end iterator for this class.
312  static const GraphIterator& end();
313 
314  /// @}
315 
316  private:
317  void extendPathUpstream(ElementPtr upstreamElem, ElementPtr connectingElem);
318  void returnPathDownstream(ElementPtr upstreamElem);
319 
320  private:
321  ElementPtr _upstreamElem;
322  ElementPtr _connectingElem;
323  ElementSet _pathElems;
324  vector<StackFrame> _stack;
325  bool _prune;
326  size_t _holdCount;
327 };
328 
329 /// @class InheritanceIterator
330 /// An iterator object representing the current state of an inheritance traversal.
331 ///
332 /// @sa Element::traverseInheritance
334 {
335  public:
337  _elem(elem),
338  _holdCount(0)
339  {
340  _pathElems.insert(elem);
341  }
343 
344  private:
345  using ConstElementSet = std::set<ConstElementPtr>;
346 
347  public:
348  bool operator==(const InheritanceIterator& rhs) const
349  {
350  return _elem == rhs._elem;
351  }
352  bool operator!=(const InheritanceIterator& rhs) const
353  {
354  return !(*this == rhs);
355  }
356 
357  /// Dereference this iterator, returning the current element in the
358  /// traversal.
360  {
361  return _elem;
362  }
363 
364  /// Iterate to the next element in the traversal.
365  /// @throws ExceptionFoundCycle if a cycle is encountered.
366  InheritanceIterator& operator++();
367 
368  /// Interpret this object as an iteration range, and return its begin
369  /// iterator.
370  InheritanceIterator& begin(size_t holdCount = 0)
371  {
372  _holdCount = holdCount;
373  return *this;
374  }
375 
376  /// Return the sentinel end iterator for this class.
377  static const InheritanceIterator& end();
378 
379  private:
380  ConstElementPtr _elem;
381  ConstElementSet _pathElems;
382  size_t _holdCount;
383 };
384 
385 /// @class ExceptionFoundCycle
386 /// An exception that is thrown when a traversal call encounters a cycle.
388 {
389  public:
390  using Exception::Exception;
391 };
392 
393 extern MX_CORE_API const Edge NULL_EDGE;
394 
398 
400 
401 #endif
shared_ptr< const Element > ConstElementPtr
A shared pointer to a const Element.
Definition: Element.h:32
ElementPtr getElement() const
Return the current element in the traversal.
Definition: Traversal.h:128
bool getPruneSubtree() const
Definition: Traversal.h:158
bool operator!=(const InheritanceIterator &rhs) const
Definition: Traversal.h:352
#define MATERIALX_NAMESPACE_BEGIN
Definition: Generated.h:23
bool operator!=(const Edge &rhs) const
Definition: Traversal.h:46
GraphIterator & begin(size_t holdCount=0)
Definition: Traversal.h:299
TreeIterator(ElementPtr elem)
Definition: Traversal.h:91
Edge(ElementPtr elemDown, ElementPtr elemConnect, ElementPtr elemUp)
Definition: Traversal.h:32
Edge operator*() const
Dereference this iterator, returning the current edge in the traversal.
Definition: Traversal.h:220
bool operator==(const TreeIterator &rhs) const
Definition: Traversal.h:103
ElementPtr getConnectingElement() const
Return the connecting element of the edge, if any.
Definition: Traversal.h:64
#define MX_CORE_API
Definition: Export.h:18
void setPruneSubgraph(bool prune)
Definition: Traversal.h:281
bool operator!=(const TreeIterator &rhs) const
Definition: Traversal.h:109
Definition: Traversal.h:29
ElementPtr getUpstreamElement() const
Return the upstream element of the edge.
Definition: Traversal.h:70
ElementPtr getUpstreamElement() const
Return the upstream element of the current edge.
Definition: Traversal.h:247
MX_CORE_API const TreeIterator NULL_TREE_ITERATOR
GLuint GLuint end
Definition: glcorearb.h:475
bool operator!=(const GraphIterator &rhs) const
Definition: Traversal.h:214
bool operator==(const Edge &rhs) const
Definition: Traversal.h:40
TreeIterator & begin(size_t holdCount=0)
Definition: Traversal.h:169
ElementPtr getConnectingElement() const
Return the connecting element, if any, of the current edge.
Definition: Traversal.h:241
MX_CORE_API const InheritanceIterator NULL_INHERITANCE_ITERATOR
size_t getUpstreamIndex() const
Definition: Traversal.h:254
MX_CORE_API const Edge NULL_EDGE
GraphIterator(ElementPtr elem)
Definition: Traversal.h:194
Exception(const string &msg)
Definition: Exception.h:24
shared_ptr< Element > ElementPtr
Definition: Traversal.h:18
ElementPtr getDownstreamElement() const
Return the downstream element of the current edge.
Definition: Traversal.h:235
size_t getElementDepth() const
Definition: Traversal.h:139
InheritanceIterator(ConstElementPtr elem)
Definition: Traversal.h:336
~Edge()
Definition: Traversal.h:38
ConstElementPtr operator*() const
Definition: Traversal.h:359
bool getPruneSubgraph() const
Definition: Traversal.h:288
MX_CORE_API const GraphIterator NULL_GRAPH_ITERATOR
bool operator==(const InheritanceIterator &rhs) const
Definition: Traversal.h:348
shared_ptr< Element > ElementPtr
A shared pointer to an Element.
Definition: Element.h:30
InheritanceIterator & begin(size_t holdCount=0)
Definition: Traversal.h:370
#define MATERIALX_NAMESPACE_END
Definition: Generated.h:24
void prune(TreeT &tree, typename TreeT::ValueType tolerance=zeroVal< typename TreeT::ValueType >(), bool threaded=true, size_t grainSize=1)
Reduce the memory footprint of a tree by replacing with tiles any nodes whose values are all the same...
Definition: Prune.h:335
size_t getElementDepth() const
Definition: Traversal.h:265
void setPruneSubtree(bool prune)
Definition: Traversal.h:151
bool operator==(const GraphIterator &rhs) const
Definition: Traversal.h:208
bool operator<(const Edge &rhs) const
Definition: Traversal.h:50
ElementPtr getDownstreamElement() const
Return the downstream element of the edge.
Definition: Traversal.h:58
ElementPtr operator*() const
Definition: Traversal.h:116