cesium-native 0.48.0
Loading...
Searching...
No Matches
TreeTraversalState.h
1#pragma once
2
3#include <CesiumUtility/Assert.h>
4
5#include <cstddef>
6#include <unordered_map>
7#include <vector>
8
9namespace CesiumUtility {
10
35template <typename TNodePointer, typename TState> class TreeTraversalState {
36public:
42 return this->_previousTraversal.size();
43 }
44
50 return this->_currentTraversal.size();
51 }
52
58 // If this assertion fails, it indicates a traversal is already in progress.
59 CESIUM_ASSERT(this->_parentIndices.empty());
60
61 this->_previousTraversal.swap(this->_currentTraversal);
62 this->_currentTraversal.clear();
63 this->_previousTraversalNextNodeIndex = 0;
64 }
65
75 void beginNode(const TNodePointer& pNode) {
76 int64_t currentTraversalIndex = int64_t(this->_currentTraversal.size());
77 int64_t previousTraversalIndex = this->_previousTraversalNextNodeIndex;
78
79 if (previousTraversalIndex >= 0 &&
80 size_t(previousTraversalIndex) < this->_previousTraversal.size()) {
81 const TraversalData& previousData =
82 this->_previousTraversal[size_t(previousTraversalIndex)];
83 if (previousData.pNode == pNode) {
84 ++this->_previousTraversalNextNodeIndex;
85 } else {
86 previousTraversalIndex = -1;
87 }
88 } else {
89 previousTraversalIndex = -1;
90 }
91
92 this->_parentIndices.emplace_back(TraversalIndices{
93 .previous = previousTraversalIndex,
94 .current = currentTraversalIndex});
95
96 this->_currentTraversal.emplace_back(TraversalData{pNode, -1, TState()});
97 }
98
108 TNodePointer getCurrentNode() const noexcept {
109 if (this->_parentIndices.empty())
110 return nullptr;
111
112 return this->currentData().pNode;
113 }
114
122 bool wasCurrentNodePreviouslyTraversed() const noexcept {
123 return this->previousState() != nullptr;
124 }
125
134 const TState* previousState() const {
135 const TraversalData* pData = this->previousData();
136 return pData ? &pData->state : nullptr;
137 }
138
147 TState& currentState() {
148 TraversalData& data = this->currentData();
149 return data.state;
150 }
151
159 const TState& currentState() const {
160 const TraversalData& data = this->currentData();
161 return data.state;
162 }
163
177 void finishNode([[maybe_unused]] const TNodePointer& pNode) {
178 // An assertion failure here indicates mismatched calls to beginNode /
179 // finishNode.
180 CESIUM_ASSERT(!this->_currentTraversal.empty());
181 CESIUM_ASSERT(!this->_parentIndices.empty());
182 CESIUM_ASSERT(this->currentData().pNode == pNode);
183
184 this->currentData().nextSiblingIndex =
185 int64_t(this->_currentTraversal.size());
186
187 // Now that this node is done, skip its subtree, if any, in the previous
188 // traversal. If this finished node doesn't exist in the previous traversal,
189 // look for the next node in the previous traversal at the current position.
190 const TraversalData* pPreviousData = this->previousData();
191 if (pPreviousData) {
192 CESIUM_ASSERT(pPreviousData->nextSiblingIndex >= 0);
193 this->_previousTraversalNextNodeIndex = pPreviousData->nextSiblingIndex;
194 }
195
196 this->_parentIndices.pop_back();
197 }
198
210 template <typename Func> void forEachPreviousChild(Func&& callback) const {
211 int64_t parentPreviousIndex = this->previousDataIndex();
212 if (parentPreviousIndex < 0) {
213 // Current node was not previously traversed.
214 return;
215 }
216
217 const TraversalData& parentPreviousData =
218 this->_previousTraversal[size_t(parentPreviousIndex)];
219
220 for (size_t i = size_t(parentPreviousIndex + 1);
221 i < size_t(parentPreviousData.nextSiblingIndex);) {
222 CESIUM_ASSERT(i < this->_previousTraversal.size());
223 const TraversalData& data = this->_previousTraversal[i];
224 callback(data.pNode, data.state);
225 CESIUM_ASSERT(
226 data.nextSiblingIndex >= 0 && size_t(data.nextSiblingIndex) > i);
227 i = size_t(data.nextSiblingIndex);
228 }
229 }
230
242 template <typename Func>
243 void forEachPreviousDescendant(Func&& callback) const {
244 int64_t parentPreviousIndex = this->previousDataIndex();
245 if (parentPreviousIndex < 0) {
246 // Current node was not previously traversed.
247 return;
248 }
249
250 const TraversalData& parentPreviousData =
251 this->_previousTraversal[size_t(parentPreviousIndex)];
252
253 for (size_t i = size_t(parentPreviousIndex + 1);
254 i < size_t(parentPreviousData.nextSiblingIndex);
255 ++i) {
256 CESIUM_ASSERT(i < this->_previousTraversal.size());
257 const TraversalData& data = this->_previousTraversal[i];
258 callback(data.pNode, data.state);
259 }
260 }
261
275 template <typename Func> void forEachCurrentDescendant(Func&& callback) {
276 int64_t parentCurrentIndex = this->currentDataIndex();
277 CESIUM_ASSERT(parentCurrentIndex >= 0);
278
279 const TraversalData& parentCurrentData =
280 this->_currentTraversal[size_t(parentCurrentIndex)];
281
282 size_t endIndex = parentCurrentData.nextSiblingIndex >= 0
283 ? size_t(parentCurrentData.nextSiblingIndex)
284 : this->_currentTraversal.size();
285
286 for (size_t i = size_t(parentCurrentIndex + 1); i < endIndex; ++i) {
287 TraversalData& data = this->_currentTraversal[i];
288 callback(data.pNode, data.state);
289 }
290 }
291
300 std::unordered_map<TNodePointer, TState> slowlyGetCurrentStates() const {
301 return this->slowlyGetStates(this->_currentTraversal);
302 }
303
312 std::unordered_map<TNodePointer, TState> slowlyGetPreviousStates() const {
313 return this->slowlyGetStates(this->_previousTraversal);
314 }
315
316private:
317 struct TraversalData {
318 TNodePointer pNode;
319 int64_t nextSiblingIndex;
320 TState state;
321 };
322
323 struct TraversalIndices {
324 int64_t previous;
325 int64_t current;
326 };
327
328 int64_t previousDataIndex() const {
329 CESIUM_ASSERT(!this->_parentIndices.empty());
330
331 int64_t result = this->_parentIndices.back().previous;
332
333 CESIUM_ASSERT(
334 result == -1 ||
335 (result >= 0 && size_t(result) < this->_previousTraversal.size()));
336
337 return result;
338 }
339
340 int64_t currentDataIndex() const {
341 CESIUM_ASSERT(!this->_parentIndices.empty());
342
343 // An assertion failure here may indicate beginTraversal wasn't called.
344 CESIUM_ASSERT(
345 this->_parentIndices.back().current >= 0 &&
346 this->_parentIndices.back().current <
347 static_cast<int64_t>(this->_currentTraversal.size()));
348
349 return this->_parentIndices.back().current;
350 }
351
352 const TraversalData* previousData() const {
353 int64_t previousIndex = this->previousDataIndex();
354 if (previousIndex < 0)
355 return nullptr;
356
357 const TraversalData& previousData =
358 this->_previousTraversal[size_t(previousIndex)];
359
360 CESIUM_ASSERT(previousData.pNode == this->currentData().pNode);
361
362 return &previousData;
363 }
364
365 TraversalData& currentData() {
366 int64_t currentIndex = this->currentDataIndex();
367 CESIUM_ASSERT(currentIndex >= 0);
368 return this->_currentTraversal[size_t(currentIndex)];
369 }
370
371 const TraversalData& currentData() const {
372 int64_t currentIndex = this->currentDataIndex();
373 CESIUM_ASSERT(currentIndex >= 0);
374 return this->_currentTraversal[size_t(currentIndex)];
375 }
376
377 std::unordered_map<TNodePointer, TState>
378 slowlyGetStates(const std::vector<TraversalData>& traversalData) const {
379 std::unordered_map<TNodePointer, TState> result;
380
381 for (const TraversalData& data : traversalData) {
382 result[data.pNode] = data.state;
383 }
384
385 return result;
386 }
387
388 std::vector<TraversalData> _previousTraversal;
389 std::vector<TraversalData> _currentTraversal;
390
391 // A stack of indices into the previous and current traversals. When
392 // `beginNode` is called, the index of that node within each traversal is
393 // pushed onto the end of this vector. This is always the index of the _last_
394 // node in the `_currentTraversal`, because `beginNode` always adds a new
395 // entry to the end of the `currentTraversal`. The previous traversal index
396 // may be -1 if the current node was not visited at all in the previous
397 // traversal. `finishNode` pops the last entry off the end of this array.
398 std::vector<TraversalIndices> _parentIndices;
399
400 // The index of the next node in the previous traversal. In `beginNode`, this
401 // new node is added to the end of `_currentTraversal`. In
402 // `_previousTraversal`, if it exists at all, it will be found at this index.
403 int64_t _previousTraversalNextNodeIndex = 0;
404};
405
406} // namespace CesiumUtility
Associates state (arbitrary data) with each node during partial, depth-first traversal of a tree....
size_t getNodeCountInCurrentTraversal() const
Gets the total number of nodes that have been visited so far in the current traversal.
void forEachCurrentDescendant(Func &&callback)
Invokes a callback for each descendant (children, grandchildren, etc.) of the current node that has b...
void beginNode(const TNodePointer &pNode)
Begins traversing a node in the tree. This node becomes the "current" node.
void finishNode(const TNodePointer &pNode)
Ends traversal of the given node.
std::unordered_map< TNodePointer, TState > slowlyGetPreviousStates() const
Gets a mapping of nodes to states for the previous traversal.
const TState * previousState() const
Gets the state of the current node on the previous traversal. The current node is the one for which b...
bool wasCurrentNodePreviouslyTraversed() const noexcept
Determines if the current node was visited in the previous traversal.
TNodePointer getCurrentNode() const noexcept
Gets the current node in the traversal.
void beginTraversal()
Begins a new traversal of the tree. The "current" and "previous" traversals are swapped,...
void forEachPreviousDescendant(Func &&callback) const
Invokes a callback for each descendant (children, grandchildren, etc.) of the current node that was t...
TState & currentState()
Gets the state of the current node during the current traversal. The current node is the one for whic...
std::unordered_map< TNodePointer, TState > slowlyGetCurrentStates() const
Gets a mapping of nodes to states for the current traversal.
void forEachPreviousChild(Func &&callback) const
Invokes a callback for each child of the current node that was traversed in the previous traversal.
const TState & currentState() const
Gets the state of the current node during the current traversal. The current node is the one for whic...
size_t getNodeCountInPreviousTraversal() const
Gets the total number of nodes that were visited in the previous traversal.
Utility classes for Cesium.