liblevenshtein::Dawg Class Reference

A Directed Acyclic Word Graph (DAWG) maps sequences of characters to form words; the collection of words is known as a dictionary. More...

#include <dawg.h>

Inheritance diagram for liblevenshtein::Dawg:

Collaboration diagram for liblevenshtein::Dawg:

Public Member Functions
	Dawg (DawgNode *root, std::size_t size)
	Constructs a new DAWG with the given root node and number of dictionary terms (size).
	Dawg ()
	Constructs an empty DAWG with a default root node (there are no outgoing edges or reachable terms from the root, not even the empty string).
virtual	~Dawg ()
	Deletes all the nodes associated with this dictionary.
virtual auto	add (const std::string &term) -> bool=0
	Adds a new term to this dictionary by adding missing sequential edges leading outward from the root node.
virtual auto	remove (const std::string &term) -> bool=0
	Removes a term from this dictionary and cleans up its path.
auto	contains (const std::string &term) const -> bool
	Determines whether the given term is contained within this dictionary.
auto	root () const -> DawgNode *
	Returns a pointer to the root node of this dictionary from which all its terms may be determined.
auto	size () const -> size_t
	Returns the number of terms in this dictionary.
auto	begin () const -> DawgIterator
	Returns an iterator pointing to the first term in this dictionary, from which all terms may be iterated over.
auto	end () const -> DawgIterator
	Returns an iterator representing the boundary following the final term in this dictionary.
auto	operator== (const Dawg &other) const -> bool
	Determines whether another DAWG is equivalent to this one.

Protected Member Functions
auto	all_nodes () const -> std::unordered_set< DawgNode * >
	Returns a set of all nodes reachable from the root, including the root.

Protected Attributes
DawgNode *	_root
	Root node of this DAWG from which all its terms may be reached.
std::size_t	_size
	Number of terms reachable from the root node.

Friends
class	std::hash< Dawg >
	Specifies the hash function for this DAWG may view its membership.
auto	operator<< (std::ostream &out, const Dawg &dawg) -> std::ostream &
	Specifies the output streaming operator for this DAWG may view its membership.

Detailed Description

A Directed Acyclic Word Graph (DAWG) maps sequences of characters to form words; the collection of words is known as a dictionary.

As its name implies, it is a directed, acyclic automaton having a single root node from which all terms in the dictionary are reachable. It is important that only those terms in the dictionary may be formed by traversing the edges of the DAWG, no terms that are not in the dictionary may be formed by joining subsequent outgoing edges from the root. Nodes denoting word boundaries are flagged as being final.

Definition at line 23 of file dawg.h.

Constructor & Destructor Documentation

Dawg() [1/2]

liblevenshtein::Dawg::Dawg	(	DawgNode *	root,
		std::size_t	size )

Constructs a new DAWG with the given root node and number of dictionary terms (size).

The number of terms reachable by combining the subsequent outgoing edges from the root must be equal to the size.

Parameters

root	Node from which all dictionary terms may be reached by subsequently traversing its outgoing edges.
size	Number of terms in the dictionary.

Definition at line 12 of file dawg.cpp.

  : _root(root),
    _size(size)
{}

Dawg() [2/2]

liblevenshtein::Dawg::Dawg

(

)

Constructs an empty DAWG with a default root node (there are no outgoing edges or reachable terms from the root, not even the empty string).

Definition at line 17 of file dawg.cpp.

  : _root(new DawgNode()),
    _size(0)
{}

~Dawg()

liblevenshtein::Dawg::~Dawg ( )

virtual

Deletes all the nodes associated with this dictionary.

Definition at line 22 of file dawg.cpp.

            {
  for (DawgNode* node : all_nodes()) {
    delete node;
  }
}

References all_nodes().

Here is the call graph for this function:

Member Function Documentation

add()

virtual auto liblevenshtein::Dawg::add ( const std::string & term ) -> bool

pure virtual

Adds a new term to this dictionary by adding missing sequential edges leading outward from the root node.

Parameters

term	The term to add to this dictionary.

Returns

Whether the term was successfully added to this dictionary.

Implemented in liblevenshtein::SortedDawg.

all_nodes()

auto liblevenshtein::Dawg::all_nodes ( ) const -> std::unordered_set<DawgNode *>

protected

Returns a set of all nodes reachable from the root, including the root.

Returns

The closure of nodes reachable from the root, including the root.

Definition at line 28 of file dawg.cpp.

                                                           {
  std::unordered_set<DawgNode *> nodes;
  std::queue<DawgNode *> pending;
  pending.push(_root);
  while (!pending.empty()) {
    DawgNode *node = pending.front();
    pending.pop();
    nodes.insert(node);
    node->for_each_edge([&](char label, DawgNode *target) {
      pending.push(target);
    });
  }
  return nodes;
}

References _root, and query().

Referenced by liblevenshtein::SortedDawg::clean_up(), and ~Dawg().

Here is the call graph for this function:

Here is the caller graph for this function:

begin()

auto liblevenshtein::Dawg::begin

(

)

const -> DawgIterator

Returns an iterator pointing to the first term in this dictionary, from which all terms may be iterated over.

Returns

An iterator pointing to the first term in this dictionary.

Definition at line 59 of file dawg.cpp.

                                       {
  return {_root};
}

References _root.

contains()

auto liblevenshtein::Dawg::contains

(

const std::string &

term

)

const -> bool

Determines whether the given term is contained within this dictionary.

Parameters

term	Query term whose membership in this dictionary must be determined.

Returns

Whether the term is contained within this dictionary.

Definition at line 43 of file dawg.cpp.

                                                       {
  DawgNode* node = _root;
  for (int i = 0; i < term.length() && node != nullptr; i += 1) {
    node = node->transition(term[i]);
  }
  return node != nullptr && node->is_final();
}

References liblevenshtein::DawgNode::is_final(), query(), and liblevenshtein::DawgNode::transition().

Referenced by liblevenshtein::from_protobuf().

Here is the call graph for this function:

Here is the caller graph for this function:

end()

auto liblevenshtein::Dawg::end

(

)

const -> DawgIterator

Returns an iterator representing the boundary following the final term in this dictionary.

The value of the iterator is not a term, but represent a boundary that must not be crossed.

Returns

An iterator pointing to the boundary following the final term in this dictionary.

Definition at line 63 of file dawg.cpp.

                                     {
  return {_size};
}

References _size.

operator==()

auto liblevenshtein::Dawg::operator==

(

const Dawg &

other

)

const -> bool

Determines whether another DAWG is equivalent to this one.

Parameters

other

Dictionary (DAWG) to compare to this one.

Returns

Whether the other dictionary is equivalent to this one.

Definition at line 72 of file dawg.cpp.

                                                     {
  return size() == other.size() && *root() == *other.root();
}

References query().

Here is the call graph for this function:

remove()

virtual auto liblevenshtein::Dawg::remove ( const std::string & term ) -> bool

pure virtual

Removes a term from this dictionary and cleans up its path.

Parameters

term	The term to remove from this dictionary.

Returns

Whether the term was removed from this dictionary.

Implemented in liblevenshtein::SortedDawg.

root()

auto liblevenshtein::Dawg::root

(

)

const -> DawgNode *

Returns a pointer to the root node of this dictionary from which all its terms may be determined.

Returns

A pointer to the root node of this dictionary.

Definition at line 51 of file dawg.cpp.

                                    {
  return _root;
}

References _root.

Referenced by query().

Here is the caller graph for this function:

size()

auto liblevenshtein::Dawg::size

(

)

const -> size_t

Returns the number of terms in this dictionary.

Returns

The size of this dictionary.

Definition at line 55 of file dawg.cpp.

                                   {
  return _size;
}

References _size.

Friends And Related Symbol Documentation

operator<<

auto operator<< ( std::ostream & out, const Dawg & dawg ) -> std::ostream &

friend

Specifies the output streaming operator for this DAWG may view its membership.

Definition at line 67 of file dawg.cpp.

                                                                   {
  out << "Dawg{size=" << dawg._size << ", root=" << dawg._root << "}";
  return out;
}

std::hash< Dawg >

friend class std::hash< Dawg >

friend

Specifies the hash function for this DAWG may view its membership.

Definition at line 113 of file dawg.h.

Member Data Documentation

_root

DawgNode* liblevenshtein::Dawg::_root

protected

Root node of this DAWG from which all its terms may be reached.

Definition at line 126 of file dawg.h.

Referenced by all_nodes(), begin(), and root().

_size

std::size_t liblevenshtein::Dawg::_size

protected

Number of terms reachable from the root node.

Definition at line 129 of file dawg.h.

Referenced by end(), and size().

---

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

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