SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
sdsl::cst_dfs_const_forward_iterator< Cst, cache_size > Class Template Reference

An forward iterator for (compressed) suffix trees. More...

#include <cst_iterators.hpp>

Public Types

using iterator_category = std::forward_iterator_tag
 
using value_type = typename Cst::node_type
 
using difference_type = std::ptrdiff_t
 
using pointer = value_type *
 
using reference = value_type &
 
typedef const value_type const_reference
 
typedef Cst::size_type size_type
 
typedef cst_dfs_const_forward_iterator< Cst > iterator
 
typedef Cst::node_type node_type
 

Public Member Functions

 cst_dfs_const_forward_iterator (Cst const *cst, const value_type node, bool visited=false, bool valid=true)
 Constructor.
 
 ~cst_dfs_const_forward_iterator ()
 Copy Constructor.
 
uint8_t visit () const
 Returns how often the current node was already visited.
 
void skip_subtree ()
 
const_reference operator* () const
 Method for dereferencing the iterator.
 
iteratoroperator++ ()
 Prefix increment of the iterator.
 
void operator++ (int)
 Postfix increment of the iterator.
 
bool operator== (iterator const &it) const
 Equality operator.
 
bool operator!= (iterator const &it) const
 Inequality operator.
 

Detailed Description

template<class Cst, uint32_t cache_size = 128>
class sdsl::cst_dfs_const_forward_iterator< Cst, cache_size >

An forward iterator for (compressed) suffix trees.

The cst_dfs_const_forward_iterator iterates through the nodes of a (compressed) suffix tree in depth first search (dfs) order. Note, that

  • each inner node is visited twice, and
  • each leaf node is visited only once.

If the current node is a inner node, the method visit() returns 1 for the first visit and 2 for the second one.

Time complexity
$\Order{1}$ for all methods
Space complexity
$\Order{1} $

This iterator is the standard iterator for the classes

Definition at line 38 of file cst_iterators.hpp.

Member Typedef Documentation

◆ const_reference

template<class Cst , uint32_t cache_size = 128>
typedef const value_type sdsl::cst_dfs_const_forward_iterator< Cst, cache_size >::const_reference

Definition at line 47 of file cst_iterators.hpp.

◆ difference_type

template<class Cst , uint32_t cache_size = 128>
using sdsl::cst_dfs_const_forward_iterator< Cst, cache_size >::difference_type = std::ptrdiff_t

Definition at line 43 of file cst_iterators.hpp.

◆ iterator

template<class Cst , uint32_t cache_size = 128>
typedef cst_dfs_const_forward_iterator<Cst> sdsl::cst_dfs_const_forward_iterator< Cst, cache_size >::iterator

Definition at line 49 of file cst_iterators.hpp.

◆ iterator_category

template<class Cst , uint32_t cache_size = 128>
using sdsl::cst_dfs_const_forward_iterator< Cst, cache_size >::iterator_category = std::forward_iterator_tag

Definition at line 41 of file cst_iterators.hpp.

◆ node_type

template<class Cst , uint32_t cache_size = 128>
typedef Cst::node_type sdsl::cst_dfs_const_forward_iterator< Cst, cache_size >::node_type

Definition at line 50 of file cst_iterators.hpp.

◆ pointer

template<class Cst , uint32_t cache_size = 128>
using sdsl::cst_dfs_const_forward_iterator< Cst, cache_size >::pointer = value_type *

Definition at line 44 of file cst_iterators.hpp.

◆ reference

template<class Cst , uint32_t cache_size = 128>
using sdsl::cst_dfs_const_forward_iterator< Cst, cache_size >::reference = value_type &

Definition at line 45 of file cst_iterators.hpp.

◆ size_type

template<class Cst , uint32_t cache_size = 128>
typedef Cst::size_type sdsl::cst_dfs_const_forward_iterator< Cst, cache_size >::size_type

Definition at line 48 of file cst_iterators.hpp.

◆ value_type

template<class Cst , uint32_t cache_size = 128>
using sdsl::cst_dfs_const_forward_iterator< Cst, cache_size >::value_type = typename Cst::node_type

Definition at line 42 of file cst_iterators.hpp.

Constructor & Destructor Documentation

◆ cst_dfs_const_forward_iterator()

template<class Cst , uint32_t cache_size = 128>
sdsl::cst_dfs_const_forward_iterator< Cst, cache_size >::cst_dfs_const_forward_iterator ( Cst const * cst,
const value_type node,
bool visited = false,
bool valid = true )
inline

Constructor.

Definition at line 85 of file cst_iterators.hpp.

◆ ~cst_dfs_const_forward_iterator()

template<class Cst , uint32_t cache_size = 128>
sdsl::cst_dfs_const_forward_iterator< Cst, cache_size >::~cst_dfs_const_forward_iterator ( )
inline

Copy Constructor.

Definition at line 109 of file cst_iterators.hpp.

Member Function Documentation

◆ operator!=()

template<class Cst , uint32_t cache_size = 128>
bool sdsl::cst_dfs_const_forward_iterator< Cst, cache_size >::operator!= ( iterator const & it) const
inline

Inequality operator.

Definition at line 201 of file cst_iterators.hpp.

◆ operator*()

template<class Cst , uint32_t cache_size = 128>
const_reference sdsl::cst_dfs_const_forward_iterator< Cst, cache_size >::operator* ( ) const
inline

Method for dereferencing the iterator.

Definition at line 136 of file cst_iterators.hpp.

◆ operator++() [1/2]

template<class Cst , uint32_t cache_size = 128>
iterator & sdsl::cst_dfs_const_forward_iterator< Cst, cache_size >::operator++ ( )
inline

Prefix increment of the iterator.

Definition at line 142 of file cst_iterators.hpp.

◆ operator++() [2/2]

template<class Cst , uint32_t cache_size = 128>
void sdsl::cst_dfs_const_forward_iterator< Cst, cache_size >::operator++ ( int )
inline

Postfix increment of the iterator.

Definition at line 186 of file cst_iterators.hpp.

◆ operator==()

template<class Cst , uint32_t cache_size = 128>
bool sdsl::cst_dfs_const_forward_iterator< Cst, cache_size >::operator== ( iterator const & it) const
inline

Equality operator.

Definition at line 192 of file cst_iterators.hpp.

◆ skip_subtree()

template<class Cst , uint32_t cache_size = 128>
void sdsl::cst_dfs_const_forward_iterator< Cst, cache_size >::skip_subtree ( )
inline

Definition at line 124 of file cst_iterators.hpp.

◆ visit()

template<class Cst , uint32_t cache_size = 128>
uint8_t sdsl::cst_dfs_const_forward_iterator< Cst, cache_size >::visit ( ) const
inline

Returns how often the current node was already visited.

Definition at line 119 of file cst_iterators.hpp.


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