liblevenshtein 4.0.0
A library for generating Finite State Transducers based on Levenshtein Automata.
Loading...
Searching...
No Matches
merge.cpp
Go to the documentation of this file.
1#include <cstddef>
2
3#include "liblevenshtein/transducer/merge.h"
4#include "liblevenshtein/transducer/state_iterator.h"
5
6namespace liblevenshtein {
7
8void insert_after(State *state, Position *curr, Position *next) {
9 if (curr == nullptr) {
10 state->head(next);
11 }
12 else {
13 state->insert_after(curr, next);
14 }
15}
16
17template <>
18void merge<Algorithm::STANDARD>(State *state,
19 const std::vector<Position *> &positions) {
20 for (Position *a : positions) {
21 std::size_t i = a->term_index();
22 std::size_t e = a->num_errors();
23
24 StateIterator iter = state->begin();
25 StateIterator iter_end = state->end();
26 Position *p = nullptr;
27
28 while (iter != iter_end) {
29 Position *b = *iter;
30 std::size_t j = b->term_index();
31 std::size_t f = b->num_errors();
32
33 if ((e < f) || (e == f) && (i < j)) {
34 p = b;
35 ++iter;
36 } else {
37 break;
38 }
39 }
40
41 if (iter != iter_end) {
42 Position *b = *iter;
43 std::size_t j = b->term_index();
44 std::size_t f = b->num_errors();
45
46 if ((j != i) || (f != e)) {
47 insert_after(state, p, a);
48 }
49 else {
50 delete a;
51 }
52 }
53 else {
54 insert_after(state, p, a);
55 }
56 }
57}
58
59template <>
60void merge<Algorithm::TRANSPOSITION>(State *state,
61 const std::vector<Position *> &positions) {
62 for (Position *a : positions) {
63 std::size_t i = a->term_index();
64 std::size_t e = a->num_errors();
65 bool s = a->is_special();
66
67 StateIterator iter = state->begin();
68 StateIterator iter_end = state->end();
69 Position *p = nullptr;
70
71 while (iter != iter_end) {
72 Position *b = *iter;
73 std::size_t j = b->term_index();
74 std::size_t f = b->num_errors();
75 bool t = b->is_special();
76
77 if (e < f || e == f && (i < j || i == j && !s && t)) {
78 p = b;
79 ++iter;
80 }
81 else {
82 break;
83 }
84 }
85
86 if (iter != iter_end) {
87 Position *b = *iter;
88 ++iter;
89
90 std::size_t j = b->term_index();
91 std::size_t f = b->num_errors();
92 bool t = b->is_special();
93
94 if (j != i || f != e || t != s) {
95 insert_after(state, p, a);
96 }
97 else {
98 delete a;
99 }
100 }
101 else {
102 insert_after(state, p, a);
103 }
104 }
105}
106
107template <>
108void merge<Algorithm::MERGE_AND_SPLIT>(
109 State *state, const std::vector<Position *> &positions) {
110 for (Position *a : positions) {
111 std::size_t i = a->term_index();
112 std::size_t e = a->num_errors();
113 bool s = a->is_special();
114
115 StateIterator iter = state->begin();
116 StateIterator iter_end = state->end();
117 Position *p = nullptr;
118
119 while (iter != iter_end) {
120 Position *b = *iter;
121 std::size_t j = b->term_index();
122 std::size_t f = b->num_errors();
123 bool t = b->is_special();
124
125 if (e < f || e == f && (i < j || i == j && !s && t)) {
126 p = b;
127 ++iter;
128 }
129 else {
130 break;
131 }
132 }
133
134 if (iter != iter_end) {
135 Position *b = *iter;
136 ++iter;
137
138 std::size_t j = b->term_index();
139 std::size_t f = b->num_errors();
140 bool t = b->is_special();
141
142 if (j != i || f != e || t != s) {
143 insert_after(state, p, a);
144 }
145 else {
146 delete a;
147 }
148 }
149 else {
150 insert_after(state, p, a);
151 }
152 }
153}
154
155} // namespace liblevenshtein
liblevenshtein::Position
Represents a location within the Levenshtein automaton.
Definition position.h:11
liblevenshtein::Position::term_index
auto term_index() const -> std::size_t
Returns the current position in the dictionary term.
Definition position.cpp:23
liblevenshtein::StateIterator
Iterates over the Position nodes in the linked-list of a Levenshtein State.
Definition state_iterator.h:14
liblevenshtein::State
Consists of a closure of Position nodes within the Levenshtein automaton.
Definition state.h:23
liblevenshtein::State::insert_after
void insert_after(Position *curr, Position *next)
Inserts a new Position into the linked-list following an existing member.
Definition state.cpp:48
liblevenshtein::State::begin
auto begin() -> StateIterator
Returns an iterator over the Positions in this State, beginning at the head and traversing to the tai...
Definition state.cpp:134
liblevenshtein::State::head
void head(Position *head)
Sets the first element in the linked-list of Position nodes.
Definition state.cpp:26
liblevenshtein::State::end
auto end() -> StateIterator
Returns an iterator representing the end of the linked-list of Positions.
Definition state.cpp:138
query
void query(ll::Dawg *dawg, const std::string &query_term, std::size_t max_distance)
Definition main.cpp:25
liblevenshtein
Various utilities regarding Levenshtein transducers.
Definition namespaces.dox:9
liblevenshtein::merge< Algorithm::STANDARD >
void merge< Algorithm::STANDARD >(State *state, const std::vector< Position * > &positions)
Definition merge.cpp:18
liblevenshtein::merge< Algorithm::MERGE_AND_SPLIT >
void merge< Algorithm::MERGE_AND_SPLIT >(State *state, const std::vector< Position * > &positions)
Definition merge.cpp:108
liblevenshtein::merge< Algorithm::TRANSPOSITION >
void merge< Algorithm::TRANSPOSITION >(State *state, const std::vector< Position * > &positions)
Definition merge.cpp:60
liblevenshtein::insert_after
void insert_after(State *state, Position *curr, Position *next)
Inserts one Position after another.
Definition merge.cpp:8
state_iterator.h