liblevenshtein::DawgIterator Class Reference

Iterates over all the terms in a DAWG dictionary. More...

#include <dawg_iterator.h>

Collaboration diagram for liblevenshtein::DawgIterator:

Public Member Functions
	DawgIterator (DawgNode *root)
	Constructs an iterator over the terms in a dictionary.
	DawgIterator (std::size_t term_index)
	Constructs an iterator representing the boundary following the final term in a dictionary.
	~DawgIterator ()
	Cleans up all the prefixes allocated by this iterator.
auto	operator++ () -> DawgIterator &
	Advances the iterator by one term.
auto	operator* () const -> std::string
	Returns the current dictionary term.
auto	operator== (const DawgIterator &other) const -> bool
	Compares this iterator with one representing the boundary following the final term in the dictionary.

Private Member Functions
void	advance ()
	Advances this iterator by one term.

Private Attributes
std::vector< Prefix * >	_prefixes
	Used to construct dictionary terms by collecting consecutive edge labels from the root node to their respective final nodes.
std::queue< Prefix * >	_pending
	Intermediate prefixes that have not reached all their final nodes yet.
std::string	_next_value
	Value of this iterator, i.e.
std::size_t	_term_index = 0
	Current index of the enumerated terms in the dictinary.

Detailed Description

Iterates over all the terms in a DAWG dictionary.

Definition at line 15 of file dawg_iterator.h.

Constructor & Destructor Documentation

DawgIterator() [1/2]

liblevenshtein::DawgIterator::DawgIterator

(

DawgNode *

root

)

Constructs an iterator over the terms in a dictionary.

Terms are yielded as they are reached by traversing the consecutive outgoing edges from the root node.

Parameters

root	Root node of the dictionary.

Definition at line 6 of file dawg_iterator.cpp.

                                         {
  auto *prefix = new Prefix(root);
  _prefixes.push_back(prefix);
  _pending.push(prefix);
  advance();
}

References _pending, _prefixes, advance(), and query().

Here is the call graph for this function:

DawgIterator() [2/2]

liblevenshtein::DawgIterator::DawgIterator

(

std::size_t

term_index

)

Constructs an iterator representing the boundary following the final term in a dictionary.

Parameters

term_index

Size of the dictionary. Each term is enumerated from 0, so when the term_index reaches the size of the dictionary, all terms have been traversed.

Definition at line 13 of file dawg_iterator.cpp.

  : _term_index(term_index)
{}

~DawgIterator()

liblevenshtein::DawgIterator::~DawgIterator

(

)

Cleans up all the prefixes allocated by this iterator.

Definition at line 17 of file dawg_iterator.cpp.

                            {
  for (Prefix* prefix : _prefixes) {
    delete prefix;
  }
}

References _prefixes, and query().

Here is the call graph for this function:

Member Function Documentation

advance()

void liblevenshtein::DawgIterator::advance ( )

private

Advances this iterator by one term.

Definition at line 37 of file dawg_iterator.cpp.

                           {
  if (!_pending.empty()) {
    DawgNode* node;
    std::string value;
    Prefix* prefix;
 
    do {
      prefix = _pending.front();
      _pending.pop();
 
      node = prefix->node();
      node->for_each_edge([&] (char label, DawgNode* target) {
        auto *child = new Prefix(target, prefix, label);
        _prefixes.push_back(child);
        _pending.push(child);
      });
    }
    while (!node->is_final() && !_pending.empty());
 
    if (node->is_final()) {
      _next_value = prefix->str();
    }
  }
}

References _next_value, _pending, _prefixes, liblevenshtein::DawgNode::for_each_edge(), liblevenshtein::DawgNode::is_final(), and query().

Referenced by DawgIterator().

Here is the call graph for this function:

Here is the caller graph for this function:

operator*()

auto liblevenshtein::DawgIterator::operator*

(

)

const -> std::string

Returns the current dictionary term.

Returns

The term at term_index of the dictionary.

Definition at line 29 of file dawg_iterator.cpp.

                                                {
  return _next_value;
}

References _next_value.

operator++()

auto liblevenshtein::DawgIterator::operator++

(

)

-> DawgIterator &

Advances the iterator by one term.

Returns

An iterator whose value is the next term in the dictionary.

Definition at line 23 of file dawg_iterator.cpp.

                                                {
  advance();
  _term_index += 1;
  return *this;
}

operator==()

auto liblevenshtein::DawgIterator::operator==

(

const DawgIterator &

other

)

const -> bool

Compares this iterator with one representing the boundary following the final term in the dictionary.

When this returns false, all terms in the dictionary have been iterated over. By convention, this is only used to compare iterators over the same dictionary.

Parameters

other

An iterator whose location in the dictionary must be compared with the boundary following its final term.

Returns

Whether the iterator has reached the end of the dictionary.

Definition at line 33 of file dawg_iterator.cpp.

                                                                     {
  return _term_index == other._term_index;
}

References query().

Here is the call graph for this function:

Member Data Documentation

_next_value

std::string liblevenshtein::DawgIterator::_next_value

private

Value of this iterator, i.e.

the current dictionary term.

Definition at line 78 of file dawg_iterator.h.

Referenced by advance(), and operator*().

_pending

std::queue<Prefix *> liblevenshtein::DawgIterator::_pending

private

Intermediate prefixes that have not reached all their final nodes yet.

Definition at line 75 of file dawg_iterator.h.

Referenced by advance(), and DawgIterator().

_prefixes

std::vector<Prefix *> liblevenshtein::DawgIterator::_prefixes

private

Used to construct dictionary terms by collecting consecutive edge labels from the root node to their respective final nodes.

Definition at line 72 of file dawg_iterator.h.

Referenced by advance(), DawgIterator(), and ~DawgIterator().

_term_index

std::size_t liblevenshtein::DawgIterator::_term_index = 0

private

Current index of the enumerated terms in the dictinary.

Definition at line 81 of file dawg_iterator.h.

---

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

• src/liblevenshtein/collection/dawg_iterator.h
• src/liblevenshtein/collection/dawg_iterator.cpp