42 return this->_previousTraversal.size();
50 return this->_currentTraversal.size();
59 CESIUM_ASSERT(this->_parentIndices.empty());
61 this->_previousTraversal.swap(this->_currentTraversal);
62 this->_currentTraversal.clear();
63 this->_previousTraversalNextNodeIndex = 0;
76 int64_t currentTraversalIndex = int64_t(this->_currentTraversal.size());
77 int64_t previousTraversalIndex = this->_previousTraversalNextNodeIndex;
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;
86 previousTraversalIndex = -1;
89 previousTraversalIndex = -1;
92 this->_parentIndices.emplace_back(TraversalIndices{
93 .previous = previousTraversalIndex,
94 .current = currentTraversalIndex});
96 this->_currentTraversal.emplace_back(TraversalData{pNode, -1, TState()});
109 if (this->_parentIndices.empty())
112 return this->currentData().pNode;
135 const TraversalData* pData = this->previousData();
136 return pData ? &pData->state :
nullptr;
148 TraversalData& data = this->currentData();
160 const TraversalData& data = this->currentData();
177 void finishNode([[maybe_unused]]
const TNodePointer& pNode) {
180 CESIUM_ASSERT(!this->_currentTraversal.empty());
181 CESIUM_ASSERT(!this->_parentIndices.empty());
182 CESIUM_ASSERT(this->currentData().pNode == pNode);
184 this->currentData().nextSiblingIndex =
185 int64_t(this->_currentTraversal.size());
190 const TraversalData* pPreviousData = this->previousData();
192 CESIUM_ASSERT(pPreviousData->nextSiblingIndex >= 0);
193 this->_previousTraversalNextNodeIndex = pPreviousData->nextSiblingIndex;
196 this->_parentIndices.pop_back();
211 int64_t parentPreviousIndex = this->previousDataIndex();
212 if (parentPreviousIndex < 0) {
217 const TraversalData& parentPreviousData =
218 this->_previousTraversal[size_t(parentPreviousIndex)];
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);
226 data.nextSiblingIndex >= 0 &&
size_t(data.nextSiblingIndex) > i);
227 i = size_t(data.nextSiblingIndex);
242 template <
typename Func>
244 int64_t parentPreviousIndex = this->previousDataIndex();
245 if (parentPreviousIndex < 0) {
250 const TraversalData& parentPreviousData =
251 this->_previousTraversal[size_t(parentPreviousIndex)];
253 for (
size_t i =
size_t(parentPreviousIndex + 1);
254 i < size_t(parentPreviousData.nextSiblingIndex);
256 CESIUM_ASSERT(i < this->_previousTraversal.size());
257 const TraversalData& data = this->_previousTraversal[i];
258 callback(data.pNode, data.state);
276 int64_t parentCurrentIndex = this->currentDataIndex();
277 CESIUM_ASSERT(parentCurrentIndex >= 0);
279 const TraversalData& parentCurrentData =
280 this->_currentTraversal[size_t(parentCurrentIndex)];
282 size_t endIndex = parentCurrentData.nextSiblingIndex >= 0
283 ? size_t(parentCurrentData.nextSiblingIndex)
284 : this->_currentTraversal.size();
286 for (
size_t i =
size_t(parentCurrentIndex + 1); i < endIndex; ++i) {
287 TraversalData& data = this->_currentTraversal[i];
288 callback(data.pNode, data.state);
301 return this->slowlyGetStates(this->_currentTraversal);
313 return this->slowlyGetStates(this->_previousTraversal);
317 struct TraversalData {
319 int64_t nextSiblingIndex;
323 struct TraversalIndices {
328 int64_t previousDataIndex()
const {
329 CESIUM_ASSERT(!this->_parentIndices.empty());
331 int64_t result = this->_parentIndices.back().previous;
335 (result >= 0 &&
size_t(result) < this->_previousTraversal.size()));
340 int64_t currentDataIndex()
const {
341 CESIUM_ASSERT(!this->_parentIndices.empty());
345 this->_parentIndices.back().current >= 0 &&
346 this->_parentIndices.back().current <
347 static_cast<int64_t
>(this->_currentTraversal.size()));
349 return this->_parentIndices.back().current;
352 const TraversalData* previousData()
const {
353 int64_t previousIndex = this->previousDataIndex();
354 if (previousIndex < 0)
357 const TraversalData& previousData =
358 this->_previousTraversal[size_t(previousIndex)];
360 CESIUM_ASSERT(previousData.pNode == this->currentData().pNode);
362 return &previousData;
365 TraversalData& currentData() {
366 int64_t currentIndex = this->currentDataIndex();
367 CESIUM_ASSERT(currentIndex >= 0);
368 return this->_currentTraversal[size_t(currentIndex)];
371 const TraversalData& currentData()
const {
372 int64_t currentIndex = this->currentDataIndex();
373 CESIUM_ASSERT(currentIndex >= 0);
374 return this->_currentTraversal[size_t(currentIndex)];
377 std::unordered_map<TNodePointer, TState>
378 slowlyGetStates(
const std::vector<TraversalData>& traversalData)
const {
379 std::unordered_map<TNodePointer, TState> result;
381 for (
const TraversalData& data : traversalData) {
382 result[data.pNode] = data.state;
388 std::vector<TraversalData> _previousTraversal;
389 std::vector<TraversalData> _currentTraversal;
398 std::vector<TraversalIndices> _parentIndices;
403 int64_t _previousTraversalNextNodeIndex = 0;