liblevenshtein::DawgNode Class Reference

Represents a position within one or more terms of a DAWG dictionary. More...

#include <dawg_node.h>

Collaboration diagram for liblevenshtein::DawgNode:

Public Member Functions
	DawgNode (bool is_final=false)
	Constructs a new DAWG node with an optional parameter that determines whether it is final (i.e.
	DawgNode (std::map< char, DawgNode * > &edges, bool is_final=false)
	Constructs a new DAWG node with an initial mapping of outgoing edges and whether it represents a word boundary.
void	is_final (bool is_final)
	Specifies whether this node represents a word boundary, or immediately follows an edge having the final character of a dictionary term.
auto	is_final () const -> bool
	Declares whether this node represents a word boundary, or whether it immediately follows an edge having the final character of a dictionary term.
void	for_each_edge (const std::function< void(char, DawgNode *)> &fn) const
	Iterates over each outgoing edge of this node and invokes a callback function with each edge's character label and target node.
auto	transition (char label) const -> DawgNode *
	Returns the target node, following this one, along the edge annotated with the given label.
auto	add_edge (char label, DawgNode *target) -> DawgNode *
	Adds a new outgoing edge to this node.
auto	operator== (const DawgNode &other) const -> bool
	Determines whether this node is equivalent to another.

Private Attributes
std::map< char, DawgNode * >	_edges
	Outgoing edges from this node.
bool	_is_final = false
	Whether this node represents a word boundary.

Detailed Description

Represents a position within one or more terms of a DAWG dictionary.

The position range from before the first character to after the last one, of each term. The terms' consecutive characters are recorded as labels along the edges between the nodes. The terms may be reconstructed by traversing the outgoing edges from the root node of the dictionary and collecting the consecutive character labels along each path. Each path constructed by following the consecutive outgoing edges from the root node to final nodes forms a term in the dictionary.

Definition at line 20 of file dawg_node.h.

Constructor & Destructor Documentation

DawgNode() [1/2]

liblevenshtein::DawgNode::DawgNode

(

bool

is_final = false

)

Constructs a new DAWG node with an optional parameter that determines whether it is final (i.e.

whether it is a word boundary).

Parameters

is_final

Whether this node represents a word boundary.

Definition at line 15 of file dawg_node.cpp.

  : _is_final(is_final)
{}

DawgNode() [2/2]

liblevenshtein::DawgNode::DawgNode	(	std::map< char, DawgNode * > &	edges,
		bool	is_final = false )

Constructs a new DAWG node with an initial mapping of outgoing edges and whether it represents a word boundary.

Parameters

edges	Mapping of outgoing edges from this node.
is_final	Whether this node represents a word boundary.

Definition at line 10 of file dawg_node.cpp.

  : _edges(edges),
    _is_final(is_final)
{}

Member Function Documentation

add_edge()

auto liblevenshtein::DawgNode::add_edge	(	char	label,
		DawgNode *	target ) -> DawgNode *

Adds a new outgoing edge to this node.

Parameters

label	Annotation for the outgoing edge.
target	Destination node for the outgoing edge.

Returns

This node for chaining.

Definition at line 41 of file dawg_node.cpp.

                                                                  {
  DawgNode* existing = transition(label);
  delete existing;
  _edges[label] = target;
  return this;
}

References query().

Referenced by liblevenshtein::from_protobuf(), and liblevenshtein::SortedDawg::minimize().

Here is the call graph for this function:

Here is the caller graph for this function:

for_each_edge()

void liblevenshtein::DawgNode::for_each_edge

(

const std::function< void(char, DawgNode *)> &

fn

)

const

Iterates over each outgoing edge of this node and invokes a callback function with each edge's character label and target node.

Parameters

fn	Callback function to invoke with each edge's character label and target node.

Definition at line 27 of file dawg_node.cpp.

                                                                                {
  for (const auto &[label, target] : _edges) {
    fn(label, target);
  }
}

References _edges, and query().

Referenced by liblevenshtein::DawgIterator::advance(), liblevenshtein::LazyQuery< Result >::advance(), liblevenshtein::collect_edges(), and liblevenshtein::collect_nodes().

Here is the call graph for this function:

Here is the caller graph for this function:

is_final() [1/2]

auto liblevenshtein::DawgNode::is_final

(

)

const -> bool

Declares whether this node represents a word boundary, or whether it immediately follows an edge having the final character of a dictionary term.

Returns

Whether this node represents a word boundary.

Definition at line 23 of file dawg_node.cpp.

                                      {
  return _is_final;
}

References _is_final.

Referenced by is_final().

Here is the caller graph for this function:

is_final() [2/2]

void liblevenshtein::DawgNode::is_final

(

bool

is_final

)

Specifies whether this node represents a word boundary, or immediately follows an edge having the final character of a dictionary term.

Parameters

is_final

Whether this node represents a word boundary.

Definition at line 19 of file dawg_node.cpp.

                                     {
  _is_final = is_final;
}

References _is_final, and is_final().

Referenced by liblevenshtein::SortedDawg::add(), liblevenshtein::DawgIterator::advance(), liblevenshtein::collect_nodes(), liblevenshtein::Dawg::contains(), and liblevenshtein::LazyQuery< Result >::LazyQuery().

Here is the call graph for this function:

Here is the caller graph for this function:

operator==()

auto liblevenshtein::DawgNode::operator==

(

const DawgNode &

other

)

const -> bool

Determines whether this node is equivalent to another.

Parameters

other

Candidate node whose equivalence to this one is to be computed.

Returns

Whether this node is equivalent to the other.

Definition at line 53 of file dawg_node.cpp.

                                                             {
  if (is_final() != other.is_final()) {
    return false;
  }
 
  if (_edges.size() != other._edges.size()) {
    return false;
  }
 
  // NOLINTNEXTLINE(readability-use-anyofallof)
  for (const auto &[label, expected_target] : _edges) {
    DawgNode *actual_target = other.transition(label);
    if (actual_target == nullptr || *expected_target != *actual_target) {
      return false;
    }
  }
 
  return true;
}

References query(), and transition().

Here is the call graph for this function:

transition()

auto liblevenshtein::DawgNode::transition

(

char

label

)

const -> DawgNode *

Returns the target node, following this one, along the edge annotated with the given label.

If no such edge exists, nullptr is returned.

Parameters

label

Outgoing edge label whose target is desired.

Returns

Target node mapped-to from this node by the edge label, or nullptr if no such target exists.

Definition at line 33 of file dawg_node.cpp.

                                                        {
  auto iter = _edges.find(label);
  if (iter != _edges.end()) {
    return iter->second;
  }
  return nullptr;
}

References query().

Referenced by liblevenshtein::Dawg::contains(), and operator==().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

_edges

std::map<char, DawgNode *> liblevenshtein::DawgNode::_edges

private

Outgoing edges from this node.

Definition at line 97 of file dawg_node.h.

Referenced by for_each_edge().

_is_final

bool liblevenshtein::DawgNode::_is_final = false

private

Whether this node represents a word boundary.

Definition at line 100 of file dawg_node.h.

Referenced by is_final(), and is_final().

---

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

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