liblevenshtein::State Class Reference

Consists of a closure of Position nodes within the Levenshtein automaton. More...

#include <state.h>

Collaboration diagram for liblevenshtein::State:

Public Member Functions
	State ()=default
	Constructs an empty state, which is most commonly used to represent the intersection of the root nodes of the Levenshtein and dictionary automata.
	State (std::initializer_list< Position * > positions)
	Constructs a new State with an initial list of Positions.
	State (std::vector< Position * > &positions)
	Constructs a new State with an initial list of Positions.
	~State ()
	Frees any owned allocations.
void	head (Position *head)
	Sets the first element in the linked-list of Position nodes.
auto	head () const -> Position *
	Returns the first Position in the linked-list of Position nodes.
void	add (Position *next)
	Adds a new Position to the tail of the linked-list.
void	insert_after (Position *curr, Position *next)
	Inserts a new Position into the linked-list following an existing member.
void	remove (Position *prev, Position *curr)
	Removes a Position from the linked-list.
void	sort (const Comparator &compare)
	Merge-sorts the linked-list of Positions.
auto	begin () -> StateIterator
	Returns an iterator over the Positions in this State, beginning at the head and traversing to the tail.
auto	end () -> StateIterator
	Returns an iterator representing the end of the linked-list of Positions.

Private Member Functions
auto	merge_sort (const Comparator &compare, Position *lower) -> Position *
	Sorts the linked-list of Positions within the Levenshtein automaton.

Static Private Member Functions
static auto	merge (const Comparator &compare, Position *lower, Position *upper) -> Position *
	Merge-sorts the nodes in the range between lower and upper.
static auto	find_middle (Position *lower) -> Position *
	Finds the middle node between lower and the tail.

Private Attributes
Position *	_head = nullptr
	First Position in the linked-list.

Detailed Description

Consists of a closure of Position nodes within the Levenshtein automaton.

Each State consists of all possible locations that are reachable within the intersection of the Levenshtein and dictionary automata, guided by the query term, at the current index within the dictionary.

Definition at line 23 of file state.h.

Constructor & Destructor Documentation

State() [1/3]

liblevenshtein::State::State ( )

default

Constructs an empty state, which is most commonly used to represent the intersection of the root nodes of the Levenshtein and dictionary automata.

State() [2/3]

liblevenshtein::State::State

(

std::initializer_list< Position * >

positions

)

Constructs a new State with an initial list of Positions.

Parameters

positions

Initial list of Positions at the current index within the dictionary automaton.

Definition at line 6 of file state.cpp.

                                                      {
  Position *curr = nullptr;
  for (Position *next : positions) {
    insert_after(curr, next);
    curr = next;
  }
}

References insert_after(), and query().

Here is the call graph for this function:

State() [3/3]

liblevenshtein::State::State

(

std::vector< Position * > &

positions

)

Constructs a new State with an initial list of Positions.

Parameters

positions

Initial list of Positions at the current index within the dictionary automaton.

Definition at line 14 of file state.cpp.

                                             {
  Position *curr = nullptr;
  for (Position *next : positions) {
    insert_after(curr, next);
    curr = next;
  }
}

References insert_after(), and query().

Here is the call graph for this function:

~State()

liblevenshtein::State::~State

(

)

Frees any owned allocations.

Definition at line 22 of file state.cpp.

              {
  delete _head;
}

References _head.

Member Function Documentation

add()

void liblevenshtein::State::add

(

Position *

next

)

Adds a new Position to the tail of the linked-list.

Parameters

next	The Position to insert at the tail of the linked-list.

Definition at line 35 of file state.cpp.

                              {
  if (_head == nullptr) {
    _head = next;
  }
  else {
    Position* curr = _head;
    while (curr->next() != nullptr) {
      curr = curr->next();
    }
    curr->next(next);
  }
}

References _head, liblevenshtein::Position::next(), and query().

Referenced by insert_after().

Here is the call graph for this function:

Here is the caller graph for this function:

begin()

auto liblevenshtein::State::begin

(

)

-> StateIterator

Returns an iterator over the Positions in this State, beginning at the head and traversing to the tail.

Returns

An iterator over Positions in this State.

Definition at line 134 of file state.cpp.

                                   {
  return {this, _head};
}

Referenced by liblevenshtein::merge< Algorithm::MERGE_AND_SPLIT >(), liblevenshtein::merge< Algorithm::STANDARD >(), liblevenshtein::merge< Algorithm::TRANSPOSITION >(), and liblevenshtein::UnsubsumeFn::operator()().

Here is the caller graph for this function:

end()

auto liblevenshtein::State::end

(

)

-> StateIterator

Returns an iterator representing the end of the linked-list of Positions.

Returns

An iterator pointing to the end of the linked-list.

Definition at line 138 of file state.cpp.

                                 {
  return {this, nullptr};
}

Referenced by liblevenshtein::merge< Algorithm::MERGE_AND_SPLIT >(), liblevenshtein::merge< Algorithm::STANDARD >(), liblevenshtein::merge< Algorithm::TRANSPOSITION >(), and liblevenshtein::UnsubsumeFn::operator()().

Here is the caller graph for this function:

find_middle()

auto liblevenshtein::State::find_middle ( Position * lower ) -> Position *

staticprivate

Finds the middle node between lower and the tail.

Parameters

lower

Lower bound for the search for the mid-point.

Returns

A pointer to the mid-point between lower and the tail.

Definition at line 118 of file state.cpp.

                                                     {
  Position* slow = lower;
  Position* fast = lower;
 
  while (fast->next() != nullptr && fast->next()->next() != nullptr) {
    slow = slow->next();
    fast = fast->next()->next();
  }
 
  return slow;
}

References liblevenshtein::Position::next(), and query().

Here is the call graph for this function:

head() [1/2]

auto liblevenshtein::State::head

(

)

const -> Position *

Returns the first Position in the linked-list of Position nodes.

Returns

The first Position in the linked-list of Position nodes.

Definition at line 31 of file state.cpp.

                                     {
  return _head;
}

References _head.

Referenced by head().

Here is the caller graph for this function:

head() [2/2]

void liblevenshtein::State::head

(

Position *

head

)

Sets the first element in the linked-list of Position nodes.

The linked-list is used with a modified version of merge-sort to merge new Positions that will not be redundant.

Parameters

head	First Position in the linked-list of Positions.

Definition at line 26 of file state.cpp.

                               {
  head->next(_head);
  _head = head;
}

References _head, head(), and liblevenshtein::Position::next().

Referenced by liblevenshtein::LazyQuery< Result >::advance(), liblevenshtein::StateIterator::insert(), liblevenshtein::insert_after(), and liblevenshtein::StateTransition::operator()().

Here is the call graph for this function:

Here is the caller graph for this function:

insert_after()

void liblevenshtein::State::insert_after	(	Position *	curr,
		Position *	next )

Inserts a new Position into the linked-list following an existing member.

Parameters

curr	Existing member of the linked-list whose follow node should be set to next.
next	New Position to insert into the linked-list following curr.

Definition at line 48 of file state.cpp.

                                                       {
  if (curr != nullptr) {
    next->next(curr->next());
    curr->next(next);
  }
  else {
    add(next);
  }
}

References add(), liblevenshtein::Position::next(), and query().

Referenced by liblevenshtein::StateIterator::insert(), liblevenshtein::insert_after(), State(), and State().

Here is the call graph for this function:

Here is the caller graph for this function:

merge()

auto liblevenshtein::State::merge ( const Comparator & compare, Position * lower, Position * upper ) -> Position *

staticprivate

Merge-sorts the nodes in the range between lower and upper.

Parameters

compare	Comparator used to lexicographically sort the Position nodes.
lower	Lower bound of sortation.
upper	Upper bound of sortation.

Returns

A pointer to the head of the sorted sub-list.

Definition at line 88 of file state.cpp.

                  {
  Position temp(-1, -1);
  Position* next = &temp;
  Position* curr = next;
 
  while (lower != nullptr && upper != nullptr) {
    if (compare(lower, upper) < 1) {
      curr->next(lower);
      lower = lower->next();
    }
    else {
      curr->next(upper);
      upper = upper->next();
    }
    curr = curr->next();
  }
 
  if (upper != nullptr) {
    curr->next(upper);
  }
  else if (lower != nullptr) {
    curr->next(lower);
  }
 
  curr = next->next();
  temp.next(nullptr);
  return curr;
}

References liblevenshtein::compare(), liblevenshtein::Position::next(), and query().

Here is the call graph for this function:

merge_sort()

auto liblevenshtein::State::merge_sort ( const Comparator & compare, Position * lower ) -> Position *

private

Sorts the linked-list of Positions within the Levenshtein automaton.

Parameters

compare	Algorithm-specific comparator for sorting the linked-list of Position nodes.
lower	Lower bound of linked-list nodes for the current branch of sortation.

Returns

A pointer to the head of the sorted sub-list.

Definition at line 73 of file state.cpp.

                  {
  if (lower == nullptr || lower->next() == nullptr) {
    return lower;
  }
 
  Position* middle = find_middle(lower);
  Position* upper = middle->next();
  middle->next(nullptr);
 
  return merge(compare,
         merge_sort(compare, lower),
         merge_sort(compare, upper));
}

References liblevenshtein::compare(), liblevenshtein::merge(), liblevenshtein::Position::next(), and query().

Referenced by sort().

Here is the call graph for this function:

Here is the caller graph for this function:

remove()

void liblevenshtein::State::remove	(	Position *	prev,
		Position *	curr )

Removes a Position from the linked-list.

By convention, prev must be the immediately preceding Position in the linked-list to curr.

Parameters

prev	Position in the linked-list preceding the one to remove.
curr	Position in the linked-lsit to remove.

Definition at line 58 of file state.cpp.

                                                 {
  // ASSUMPTION: prev->next() == curr
  Position* temp;
  if (prev != nullptr) {
    temp = prev->next();
    prev->next(curr->next());
  }
  else {
    temp = _head;
    _head = _head->next();
  }
  temp->next(nullptr);
  delete temp;
}

References _head, liblevenshtein::Position::next(), and query().

Referenced by liblevenshtein::StateIterator::remove().

Here is the call graph for this function:

Here is the caller graph for this function:

sort()

void liblevenshtein::State::sort

(

const Comparator &

compare

)

Merge-sorts the linked-list of Positions.

Parameters

compare

Comparator to use during sortation.

Definition at line 130 of file state.cpp.

                                          {
  _head = merge_sort(compare, _head);
}

References _head, liblevenshtein::compare(), and merge_sort().

Here is the call graph for this function:

Member Data Documentation

_head

Position* liblevenshtein::State::_head = nullptr

private

First Position in the linked-list.

This will be the lexicographically least Position in the linked-list. Each successive Position is lexicographically greater than the previous ones.

Definition at line 121 of file state.h.

Referenced by add(), head(), head(), remove(), sort(), and ~State().

---

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

• src/liblevenshtein/transducer/state.h
• src/liblevenshtein/transducer/state.cpp