Bidirectional in-order iterator over the nodes of an ImutAVLTree.
Declared in <llvm/ADT/ImmutableSet.h>
template<
typename ImutInfo,
bool Canonicalize = true>
class ImutAVLTreeInOrderIterator;The iterator keeps the chain of ancestors from the root down to the current node on an explicit stack of plain node pointers, and decides which way to move next by inspecting whether it is ascending from a node's left or right child. This avoids storing any per-node visit-state: there is no need to remember "have I already visited this node's left/right subtree", because that is recovered by comparing the child we just left against the parent's left and right pointers.
A node's parent cannot be cached in the node itself, because these trees are persistent and structurally shared: a single node may appear as the child of different parents across different tree versions. The ancestor stack is therefore the per-traversal parent chain.
| Name | Description |
|---|---|
TreeTy | Concrete AVL tree type visited by this iterator. |
difference_type | Signed distance between iterator positions. |
iterator_category | Identifies this as a bidirectional iterator. |
pointer | Pointer to the current tree node. |
reference | Reference to the current tree node in the in-order traversal. |
value_type | The tree node type visited by this iterator. |
| Name | Description |
|---|---|
ImutAVLTreeInOrderIterator [constructor] | Constructors |
operator* | Returns a reference to the current tree node. |
operator++ | Advances to the in-order successor of the current node. |
operator-- | Move to the in-order predecessor of the current node. |
operator-> | Returns a pointer to the current tree node. |
skipSubTree | Skips the current node and its right subtree. |
operator== | Returns true if this iterator and x refer to the same node, or if both are end(). Comparing iterators from different trees is not meaningful. |
operator!= | Returns true if this iterator and x refer to different nodes (or one is end() and the other is not). |