llvm::ImutAVLTreeInOrderIterator< ImutInfo > Class Template Reference

Bidirectional in-order iterator over the nodes of an ImutAVLTree. More...

#include "llvm/ADT/ImmutableSet.h"

Public Types
using	iterator_category = std::bidirectional_iterator_tag
using	value_type = ImutAVLTree<ImutInfo>
using	difference_type = std::ptrdiff_t
using	pointer = value_type *
using	reference = value_type &
using	TreeTy = ImutAVLTree<ImutInfo>

Public Member Functions
	ImutAVLTreeInOrderIterator ()=default
	ImutAVLTreeInOrderIterator (const TreeTy *Root)
bool	operator== (const ImutAVLTreeInOrderIterator &x) const
bool	operator!= (const ImutAVLTreeInOrderIterator &x) const
TreeTy &	operator* () const
TreeTy *	operator-> () const
ImutAVLTreeInOrderIterator &	operator++ ()
ImutAVLTreeInOrderIterator &	operator-- ()
void	skipSubTree ()
	Move to the in-order successor of the entire subtree rooted at the current node, i.e.

Detailed Description

template<typename ImutInfo>
class llvm::ImutAVLTreeInOrderIterator< ImutInfo >

Bidirectional in-order iterator over the nodes of an ImutAVLTree.

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.

Definition at line 670 of file ImmutableSet.h.

Member Typedef Documentation

difference_type

template<typename ImutInfo>

using llvm::ImutAVLTreeInOrderIterator< ImutInfo >::difference_type = std::ptrdiff_t

Definition at line 674 of file ImmutableSet.h.

iterator_category

template<typename ImutInfo>

using llvm::ImutAVLTreeInOrderIterator< ImutInfo >::iterator_category = std::bidirectional_iterator_tag

Definition at line 672 of file ImmutableSet.h.

pointer

template<typename ImutInfo>

using llvm::ImutAVLTreeInOrderIterator< ImutInfo >::pointer = value_type *

Definition at line 675 of file ImmutableSet.h.

reference

template<typename ImutInfo>

using llvm::ImutAVLTreeInOrderIterator< ImutInfo >::reference = value_type &

Definition at line 676 of file ImmutableSet.h.

TreeTy

template<typename ImutInfo>

using llvm::ImutAVLTreeInOrderIterator< ImutInfo >::TreeTy = ImutAVLTree<ImutInfo>

Definition at line 678 of file ImmutableSet.h.

value_type

template<typename ImutInfo>

using llvm::ImutAVLTreeInOrderIterator< ImutInfo >::value_type = ImutAVLTree<ImutInfo>

Definition at line 673 of file ImmutableSet.h.

Constructor & Destructor Documentation

ImutAVLTreeInOrderIterator() [1/2]

template<typename ImutInfo>

llvm::ImutAVLTreeInOrderIterator< ImutInfo >::ImutAVLTreeInOrderIterator ( )

default

Referenced by operator!=(), operator++(), operator--(), and operator==().

ImutAVLTreeInOrderIterator() [2/2]

template<typename ImutInfo>

llvm::ImutAVLTreeInOrderIterator< ImutInfo >::ImutAVLTreeInOrderIterator ( const TreeTy * Root )

inline

Definition at line 721 of file ImmutableSet.h.

Member Function Documentation

operator!=()

template<typename ImutInfo>

bool llvm::ImutAVLTreeInOrderIterator< ImutInfo >::operator!= ( const ImutAVLTreeInOrderIterator< ImutInfo > & x ) const

inline

Definition at line 735 of file ImmutableSet.h.

References ImutAVLTreeInOrderIterator().

operator*()

template<typename ImutInfo>

TreeTy & llvm::ImutAVLTreeInOrderIterator< ImutInfo >::operator* ( ) const

inline

Definition at line 739 of file ImmutableSet.h.

operator++()

template<typename ImutInfo>

ImutAVLTreeInOrderIterator & llvm::ImutAVLTreeInOrderIterator< ImutInfo >::operator++ ( )

inline

Definition at line 742 of file ImmutableSet.h.

References assert(), and ImutAVLTreeInOrderIterator().

operator--()

template<typename ImutInfo>

ImutAVLTreeInOrderIterator & llvm::ImutAVLTreeInOrderIterator< ImutInfo >::operator-- ( )

inline

Definition at line 754 of file ImmutableSet.h.

References assert(), and ImutAVLTreeInOrderIterator().

operator->()

template<typename ImutInfo>

TreeTy * llvm::ImutAVLTreeInOrderIterator< ImutInfo >::operator-> ( ) const

inline

Definition at line 740 of file ImmutableSet.h.

operator==()

template<typename ImutInfo>

bool llvm::ImutAVLTreeInOrderIterator< ImutInfo >::operator== ( const ImutAVLTreeInOrderIterator< ImutInfo > & x ) const

inline

Definition at line 730 of file ImmutableSet.h.

References ImutAVLTreeInOrderIterator().

skipSubTree()

template<typename ImutInfo>

void llvm::ImutAVLTreeInOrderIterator< ImutInfo >::skipSubTree ( )

inline

Move to the in-order successor of the entire subtree rooted at the current node, i.e.

skip the current node together with its right subtree. This is exactly the ascent half of operator++.

Definition at line 768 of file ImmutableSet.h.

References assert().

Referenced by llvm::ImutAVLTree< ValInfo >::isEqual().

---

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

• include/llvm/ADT/ImmutableSet.h