Associates state (arbitrary data) with each node during partial, depth-first traversal of a tree. Then, during a later traversal of a potentially different subset of the same tree, the state previously associated with each node can be looked up. More...

#include <CesiumUtility/TreeTraversalState.h>

Public Member Functions
size_t	getNodeCountInPreviousTraversal () const
	Gets the total number of nodes that were visited in the previous traversal.

size_t	getNodeCountInCurrentTraversal () const
	Gets the total number of nodes that have been visited so far in the current traversal.

void	beginTraversal ()
	Begins a new traversal of the tree. The "current" and "previous" traversals are swapped, and then the new "current" traversal is cleared.

void	beginNode (const TNodePointer &pNode)
	Begins traversing a node in the tree. This node becomes the "current" node.

TNodePointer	getCurrentNode () const noexcept
	Gets the current node in the traversal.

bool	wasCurrentNodePreviouslyTraversed () const noexcept
	Determines if the current node was visited in 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 `beginNode` was most recently called.

TState &	currentState ()
	Gets the state of the current node during the current traversal. The current node is the one for which `beginNode` was most recently called.

const TState &	currentState () const
	Gets the state of the current node during the current traversal. The current node is the one for which `beginNode` was most recently called.

void	finishNode (const TNodePointer &pNode)
	Ends traversal of the given node.

template<typename Func >
void	forEachPreviousChild (Func &&callback) const
	Invokes a callback for each child of the current node that was traversed in the previous traversal.

template<typename Func >
void	forEachPreviousDescendant (Func &&callback) const
	Invokes a callback for each descendant (children, grandchildren, etc.) of the current node that was traversed in the previous traversal.

template<typename Func >
void	forEachCurrentDescendant (Func &&callback)
	Invokes a callback for each descendant (children, grandchildren, etc.) of the current node that has been traversed so far in the current traversal.

std::unordered_map< TNodePointer, TState >	slowlyGetCurrentStates () const
	Gets a mapping of nodes to states for the current traversal.

std::unordered_map< TNodePointer, TState >	slowlyGetPreviousStates () const
	Gets a mapping of nodes to states for the previous traversal.

Detailed Description

template<typename TNodePointer, typename TState>
class CesiumUtility::TreeTraversalState< TNodePointer, TState >

Associates state (arbitrary data) with each node during partial, depth-first traversal of a tree. Then, during a later traversal of a potentially different subset of the same tree, the state previously associated with each node can be looked up.

In order to operate efficiently, this class makes some assumptions. Violation of these assumptions can lead to undefined behavior.

Nodes are identified by pointer. It is not required that all nodes previously traversed remain valid in a later traversal. However, if a new node instance is created at the same memory address as a previous one, it will be considered the same node.
The entire tree is not necessarily traversed each time. However, if any children of a node are traversed, then all children of the node must be traversed.
The order of traversal of children must be the same every time.
A node that previously had no children may gain them. A node that previously had children may lose all of them. However, partial updates of the children of a node are not allowed.

Template Parameters

TNodePointer	The type of each node in the tree.
TState	The state to associate with each node.

Definition at line 35 of file TreeTraversalState.h.

Member Function Documentation

◆ beginNode()

template<typename TNodePointer , typename TState >

void CesiumUtility::TreeTraversalState< TNodePointer, TState >::beginNode ( const TNodePointer & pNode )

inline

Begins traversing a node in the tree. This node becomes the "current" node.

When beginNode is called for node A, and then for node B, without an intervening call to finishNode, that indicates that B is a child of A.

Parameters

pNode The node traversed.

Definition at line 75 of file TreeTraversalState.h.

◆ beginTraversal()

template<typename TNodePointer , typename TState >

void CesiumUtility::TreeTraversalState< TNodePointer, TState >::beginTraversal ( )

inline

Begins a new traversal of the tree. The "current" and "previous" traversals are swapped, and then the new "current" traversal is cleared.

Definition at line 57 of file TreeTraversalState.h.

◆ currentState() [1/2]

template<typename TNodePointer , typename TState >

TState & CesiumUtility::TreeTraversalState< TNodePointer, TState >::currentState ( )

inline

Gets the state of the current node during the current traversal. The current node is the one for which beginNode was most recently called.

Returns: The state object for this node on the current traversal. It may be both read and written.

Definition at line 147 of file TreeTraversalState.h.

◆ currentState() [2/2]

template<typename TNodePointer , typename TState >

const TState & CesiumUtility::TreeTraversalState< TNodePointer, TState >::currentState ( ) const

inline

Gets the state of the current node during the current traversal. The current node is the one for which beginNode was most recently called.

Returns: The state object for this node on the current traversal.

Definition at line 159 of file TreeTraversalState.h.

◆ finishNode()

template<typename TNodePointer , typename TState >

void CesiumUtility::TreeTraversalState< TNodePointer, TState >::finishNode ( const TNodePointer & pNode )

inline

Ends traversal of the given node.

This method must be called in the opposite order of calls to finishNode.

After finishNode, this node's parent node becomes the "current" node. previousState and currentState will return the states of this node's parent. A call to beginNode will delineate a new child of that same parent.

Parameters

pNode The node that is done being traversed.

Definition at line 177 of file TreeTraversalState.h.

◆ forEachCurrentDescendant()

template<typename TNodePointer , typename TState >

template<typename Func >

void CesiumUtility::TreeTraversalState< TNodePointer, TState >::forEachCurrentDescendant ( Func && callback )

inline

Invokes a callback for each descendant (children, grandchildren, etc.) of the current node that has been traversed so far in the current traversal.

If the current node's children were not traversed in the current traversal, this method returns without invoking the callback at all.

Template Parameters

Func	The type of the function to invoke.

Parameters

callback The function to invoke for each descendant of the current tile that has been traversed in the current traversal. The function is passed the TNodePointer and the TState.

Definition at line 275 of file TreeTraversalState.h.

◆ forEachPreviousChild()

template<typename TNodePointer , typename TState >

template<typename Func >

void CesiumUtility::TreeTraversalState< TNodePointer, TState >::forEachPreviousChild ( Func && callback ) const

inline

Invokes a callback for each child of the current node that was traversed in the previous traversal.

If the current node or its children were not traversed in the previous traversal, this method returns without invoking the callback at all.

Template Parameters

Func	The type of the function to invoke.

Parameters

callback The function to invoke for each previously-traversed child. The function is passed the TNodePointer and the TState.

Definition at line 210 of file TreeTraversalState.h.

◆ forEachPreviousDescendant()

template<typename TNodePointer , typename TState >

template<typename Func >

void CesiumUtility::TreeTraversalState< TNodePointer, TState >::forEachPreviousDescendant ( Func && callback ) const

inline

Invokes a callback for each descendant (children, grandchildren, etc.) of the current node that was traversed in the previous traversal.

If the current node or its children were not traversed in the previous traversal, this method returns without invoking the callback at all.

Template Parameters

Func	The type of the function to invoke.

Parameters

callback The function to invoke for each previously-traversed descendant. The function is passed the TNodePointer and the TState.

Definition at line 243 of file TreeTraversalState.h.

◆ getCurrentNode()

template<typename TNodePointer , typename TState >

TNodePointer CesiumUtility::TreeTraversalState< TNodePointer, TState >::getCurrentNode ( ) const

inlinenoexcept

Gets the current node in the traversal.

When beginNode is called, the node passed to it becomes the current one. When finishNode is called, the parent node of the one passed to it becomes the current one.

Returns: The current node, or nullptr if no traversal is in progress.

Definition at line 108 of file TreeTraversalState.h.

◆ getNodeCountInCurrentTraversal()

template<typename TNodePointer , typename TState >

size_t CesiumUtility::TreeTraversalState< TNodePointer, TState >::getNodeCountInCurrentTraversal ( ) const

inline

Gets the total number of nodes that have been visited so far in the current traversal.

Definition at line 49 of file TreeTraversalState.h.

◆ getNodeCountInPreviousTraversal()

template<typename TNodePointer , typename TState >

size_t CesiumUtility::TreeTraversalState< TNodePointer, TState >::getNodeCountInPreviousTraversal ( ) const

inline

Gets the total number of nodes that were visited in the previous traversal.

Definition at line 41 of file TreeTraversalState.h.

◆ previousState()

template<typename TNodePointer , typename TState >

const TState * CesiumUtility::TreeTraversalState< TNodePointer, TState >::previousState ( ) const

inline

Gets the state of the current node on the previous traversal. The current node is the one for which beginNode was most recently called.

Returns: The state on the previous traversal, or nullptr if the current node was not traversed during the previous traversal.

Definition at line 134 of file TreeTraversalState.h.

◆ slowlyGetCurrentStates()

template<typename TNodePointer , typename TState >

std::unordered_map< TNodePointer, TState > CesiumUtility::TreeTraversalState< TNodePointer, TState >::slowlyGetCurrentStates ( ) const

inline

Gets a mapping of nodes to states for the current traversal.

This is an inherently slow operation that should only be used in debug and test code.

Returns: The mapping of nodes to current traversal states.

Definition at line 300 of file TreeTraversalState.h.

◆ slowlyGetPreviousStates()

template<typename TNodePointer , typename TState >

std::unordered_map< TNodePointer, TState > CesiumUtility::TreeTraversalState< TNodePointer, TState >::slowlyGetPreviousStates ( ) const

inline

Gets a mapping of nodes to states for the previous traversal.

This is an inherently slow operation that should only be used in debug and test code.

Returns: The mapping of nodes to previous traversal states.

Definition at line 312 of file TreeTraversalState.h.

◆ wasCurrentNodePreviouslyTraversed()

template<typename TNodePointer , typename TState >

bool CesiumUtility::TreeTraversalState< TNodePointer, TState >::wasCurrentNodePreviouslyTraversed ( ) const

inlinenoexcept

Determines if the current node was visited in the previous traversal.

Returns: true if the current node was visited in the previous traversal; otherwise, false.

Definition at line 122 of file TreeTraversalState.h.

The documentation for this class was generated from the following file:

/home/runner/work/cesium-native/cesium-native/CesiumUtility/include/CesiumUtility/TreeTraversalState.h

Public Member Functions

Detailed Description

Member Function Documentation

◆ beginNode()

◆ beginTraversal()

◆ currentState() [1/2]

◆ currentState() [2/2]

◆ finishNode()

◆ forEachCurrentDescendant()

◆ forEachPreviousChild()

◆ forEachPreviousDescendant()

◆ getCurrentNode()

◆ getNodeCountInCurrentTraversal()

◆ getNodeCountInPreviousTraversal()

◆ previousState()

◆ slowlyGetCurrentStates()

◆ slowlyGetPreviousStates()

◆ wasCurrentNodePreviouslyTraversed()