/src/tesseract/src/ccutil/clst.h
Line | Count | Source (jump to first uncovered line) |
1 | | /********************************************************************** |
2 | | * File: clst.h (Formerly clist.h) |
3 | | * Description: CONS cell list module include file. |
4 | | * Author: Phil Cheatle |
5 | | * |
6 | | * (C) Copyright 1991, Hewlett-Packard Ltd. |
7 | | ** Licensed under the Apache License, Version 2.0 (the "License"); |
8 | | ** you may not use this file except in compliance with the License. |
9 | | ** You may obtain a copy of the License at |
10 | | ** http://www.apache.org/licenses/LICENSE-2.0 |
11 | | ** Unless required by applicable law or agreed to in writing, software |
12 | | ** distributed under the License is distributed on an "AS IS" BASIS, |
13 | | ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
14 | | ** See the License for the specific language governing permissions and |
15 | | ** limitations under the License. |
16 | | * |
17 | | **********************************************************************/ |
18 | | |
19 | | #ifndef CLST_H |
20 | | #define CLST_H |
21 | | |
22 | | #include "lsterr.h" |
23 | | #include "serialis.h" |
24 | | |
25 | | #include <algorithm> |
26 | | #include <cstdio> |
27 | | |
28 | | namespace tesseract { |
29 | | |
30 | | /********************************************************************** |
31 | | * CLASS - CLIST |
32 | | * |
33 | | * Generic list class for singly linked CONS cell lists |
34 | | **********************************************************************/ |
35 | | |
36 | | template <typename T> |
37 | | class ConsList { |
38 | | friend class Link; |
39 | | |
40 | | public: |
41 | | /********************************************************************** |
42 | | * CLASS - Link |
43 | | * |
44 | | * Generic link class for singly linked CONS cell lists |
45 | | * |
46 | | * Note: No destructor - elements are assumed to be destroyed EITHER after |
47 | | * they have been extracted from a list OR by the ConsList destructor which |
48 | | * walks the list. |
49 | | **********************************************************************/ |
50 | | struct Link { |
51 | | Link *next{}; |
52 | | T *data{}; |
53 | | |
54 | 7.06M | Link() = default; Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Link::Link() Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Link::Link() Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Link::Link() Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::Link::Link() tesseract::ConsList<tesseract::WordWithBox>::Link::Link() Line | Count | Source | 54 | 3.86M | Link() = default; |
tesseract::ConsList<tesseract::EDGEPT>::Link::Link() Line | Count | Source | 54 | 3.20M | Link() = default; |
Unexecuted instantiation: tesseract::ConsList<tesseract::FPSEGPT_LIST>::Link::Link() |
55 | | Link(const Link &) = delete; |
56 | | void operator=(const Link &) = delete; |
57 | | }; |
58 | | |
59 | | /*********************************************************************** |
60 | | * CLASS - Iterator |
61 | | * |
62 | | * Generic iterator class for singly linked lists with embedded |
63 | | *links |
64 | | **********************************************************************/ |
65 | | class Iterator { |
66 | | ConsList *list; // List being iterated |
67 | | Link *prev; // prev element |
68 | | Link *current; // current element |
69 | | Link *next; // next element |
70 | | Link *cycle_pt; // point we are cycling the list to. |
71 | | bool ex_current_was_last; // current extracted was end of list |
72 | | bool ex_current_was_cycle_pt; // current extracted was cycle point |
73 | | bool started_cycling; // Have we moved off the start? |
74 | | |
75 | | /*********************************************************************** |
76 | | * Iterator::extract_sublist() |
77 | | * |
78 | | * This is a private member, used only by ConsList::assign_to_sublist. |
79 | | * Given another iterator for the same list, extract the links from THIS to |
80 | | * OTHER inclusive, link them into a new circular list, and return a |
81 | | * pointer to the last element. |
82 | | * (Can't inline this function because it contains a loop) |
83 | | **********************************************************************/ |
84 | | Link *extract_sublist( // from this current |
85 | | Iterator *other_it) { // to other current |
86 | | Iterator temp_it = *this; |
87 | | |
88 | | constexpr ERRCODE BAD_SUBLIST("Can't find sublist end point in original list"); |
89 | | #ifndef NDEBUG |
90 | | constexpr ERRCODE BAD_EXTRACTION_PTS("Can't extract sublist from points on different lists"); |
91 | | constexpr ERRCODE DONT_EXTRACT_DELETED("Can't extract a sublist marked by deleted points"); |
92 | | |
93 | | if (list != other_it->list) |
94 | | BAD_EXTRACTION_PTS.error("Iterator.extract_sublist", ABORT); |
95 | | if (list->empty()) |
96 | | EMPTY_LIST.error("Iterator::extract_sublist", ABORT); |
97 | | |
98 | | if (!current || !other_it->current) |
99 | | DONT_EXTRACT_DELETED.error("Iterator.extract_sublist", ABORT); |
100 | | #endif |
101 | | |
102 | | ex_current_was_last = other_it->ex_current_was_last = false; |
103 | | ex_current_was_cycle_pt = false; |
104 | | other_it->ex_current_was_cycle_pt = false; |
105 | | |
106 | | temp_it.mark_cycle_pt(); |
107 | | do { // walk sublist |
108 | | if (temp_it.cycled_list()) { // can't find end pt |
109 | | BAD_SUBLIST.error("Iterator.extract_sublist", ABORT); |
110 | | } |
111 | | |
112 | | if (temp_it.at_last()) { |
113 | | list->last = prev; |
114 | | ex_current_was_last = other_it->ex_current_was_last = true; |
115 | | } |
116 | | |
117 | | if (temp_it.current == cycle_pt) { |
118 | | ex_current_was_cycle_pt = true; |
119 | | } |
120 | | |
121 | | if (temp_it.current == other_it->cycle_pt) { |
122 | | other_it->ex_current_was_cycle_pt = true; |
123 | | } |
124 | | |
125 | | temp_it.forward(); |
126 | | } while (temp_it.prev != other_it->current); |
127 | | |
128 | | // circularise sublist |
129 | | other_it->current->next = current; |
130 | | auto end_of_new_list = other_it->current; |
131 | | |
132 | | // sublist = whole list |
133 | | if (prev == other_it->current) { |
134 | | list->last = nullptr; |
135 | | prev = current = next = nullptr; |
136 | | other_it->prev = other_it->current = other_it->next = nullptr; |
137 | | } else { |
138 | | prev->next = other_it->next; |
139 | | current = other_it->current = nullptr; |
140 | | next = other_it->next; |
141 | | other_it->prev = prev; |
142 | | } |
143 | | return end_of_new_list; |
144 | | } |
145 | | |
146 | | public: |
147 | 7.06k | Iterator() { // constructor |
148 | 7.06k | list = nullptr; |
149 | 7.06k | } // unassigned list Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::Iterator() Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::Iterator() Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::Iterator() tesseract::ConsList<tesseract::WordWithBox>::Iterator::Iterator() Line | Count | Source | 147 | 7.06k | Iterator() { // constructor | 148 | 7.06k | list = nullptr; | 149 | 7.06k | } // unassigned list |
|
150 | | |
151 | | /*********************************************************************** |
152 | | * Iterator::Iterator |
153 | | * |
154 | | * CONSTRUCTOR - set iterator to specified list; |
155 | | **********************************************************************/ |
156 | | Iterator( // constructor |
157 | 12.2M | ConsList *list_to_iterate) { |
158 | 12.2M | set_to_list(list_to_iterate); |
159 | 12.2M | } Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::Iterator(tesseract::ConsList<tesseract::ColPartition>*) Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::Iterator(tesseract::ConsList<tesseract::BLOBNBOX>*) Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::Iterator(tesseract::ConsList<tesseract::ColSegment>*) Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::Iterator::Iterator(tesseract::ConsList<tesseract::TabVector>*) tesseract::ConsList<tesseract::WordWithBox>::Iterator::Iterator(tesseract::ConsList<tesseract::WordWithBox>*) Line | Count | Source | 157 | 1.85M | ConsList *list_to_iterate) { | 158 | 1.85M | set_to_list(list_to_iterate); | 159 | 1.85M | } |
tesseract::ConsList<tesseract::EDGEPT>::Iterator::Iterator(tesseract::ConsList<tesseract::EDGEPT>*) Line | Count | Source | 157 | 10.3M | ConsList *list_to_iterate) { | 158 | 10.3M | set_to_list(list_to_iterate); | 159 | 10.3M | } |
Unexecuted instantiation: tesseract::ConsList<tesseract::FPSEGPT_LIST>::Iterator::Iterator(tesseract::ConsList<tesseract::FPSEGPT_LIST>*) |
160 | | |
161 | | /*********************************************************************** |
162 | | * Iterator::set_to_list |
163 | | * |
164 | | * (Re-)initialise the iterator to point to the start of the list_to_iterate |
165 | | * over. |
166 | | **********************************************************************/ |
167 | | void set_to_list( // change list |
168 | 12.2M | ConsList *list_to_iterate) { |
169 | 12.2M | list = list_to_iterate; |
170 | 12.2M | prev = list->last; |
171 | 12.2M | current = list->First(); |
172 | 12.2M | next = current != nullptr ? current->next : nullptr; |
173 | 12.2M | cycle_pt = nullptr; // await explicit set |
174 | 12.2M | started_cycling = false; |
175 | 12.2M | ex_current_was_last = false; |
176 | 12.2M | ex_current_was_cycle_pt = false; |
177 | 12.2M | } Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::set_to_list(tesseract::ConsList<tesseract::ColPartition>*) Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::set_to_list(tesseract::ConsList<tesseract::BLOBNBOX>*) Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::set_to_list(tesseract::ConsList<tesseract::ColSegment>*) Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::Iterator::set_to_list(tesseract::ConsList<tesseract::TabVector>*) tesseract::ConsList<tesseract::WordWithBox>::Iterator::set_to_list(tesseract::ConsList<tesseract::WordWithBox>*) Line | Count | Source | 168 | 1.85M | ConsList *list_to_iterate) { | 169 | 1.85M | list = list_to_iterate; | 170 | 1.85M | prev = list->last; | 171 | 1.85M | current = list->First(); | 172 | 1.85M | next = current != nullptr ? current->next : nullptr; | 173 | 1.85M | cycle_pt = nullptr; // await explicit set | 174 | 1.85M | started_cycling = false; | 175 | 1.85M | ex_current_was_last = false; | 176 | 1.85M | ex_current_was_cycle_pt = false; | 177 | 1.85M | } |
tesseract::ConsList<tesseract::EDGEPT>::Iterator::set_to_list(tesseract::ConsList<tesseract::EDGEPT>*) Line | Count | Source | 168 | 10.3M | ConsList *list_to_iterate) { | 169 | 10.3M | list = list_to_iterate; | 170 | 10.3M | prev = list->last; | 171 | 10.3M | current = list->First(); | 172 | 10.3M | next = current != nullptr ? current->next : nullptr; | 173 | 10.3M | cycle_pt = nullptr; // await explicit set | 174 | 10.3M | started_cycling = false; | 175 | 10.3M | ex_current_was_last = false; | 176 | 10.3M | ex_current_was_cycle_pt = false; | 177 | 10.3M | } |
Unexecuted instantiation: tesseract::ConsList<tesseract::FPSEGPT_LIST>::Iterator::set_to_list(tesseract::ConsList<tesseract::FPSEGPT_LIST>*) |
178 | | |
179 | | /*********************************************************************** |
180 | | * Iterator::add_after_then_move |
181 | | * |
182 | | * Add a new element to the list after the current element and move the |
183 | | * iterator to the new element. |
184 | | **********************************************************************/ |
185 | | void add_after_then_move( // add after current & |
186 | 0 | T *new_data) { |
187 | | #ifndef NDEBUG |
188 | | if (!new_data) { |
189 | | BAD_PARAMETER.error("Iterator::add_after_then_move", ABORT, "new_data is nullptr"); |
190 | | } |
191 | | #endif |
192 | |
|
193 | 0 | auto new_element = new Link; |
194 | 0 | new_element->data = new_data; |
195 | |
|
196 | 0 | if (list->empty()) { |
197 | 0 | new_element->next = new_element; |
198 | 0 | list->last = new_element; |
199 | 0 | prev = next = new_element; |
200 | 0 | } else { |
201 | 0 | new_element->next = next; |
202 | |
|
203 | 0 | if (current) { // not extracted |
204 | 0 | current->next = new_element; |
205 | 0 | prev = current; |
206 | 0 | if (current == list->last) { |
207 | 0 | list->last = new_element; |
208 | 0 | } |
209 | 0 | } else { // current extracted |
210 | 0 | prev->next = new_element; |
211 | 0 | if (ex_current_was_last) { |
212 | 0 | list->last = new_element; |
213 | 0 | } |
214 | 0 | if (ex_current_was_cycle_pt) { |
215 | 0 | cycle_pt = new_element; |
216 | 0 | } |
217 | 0 | } |
218 | 0 | } |
219 | 0 | current = new_element; |
220 | 0 | } // move to new Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::add_after_then_move(tesseract::BLOBNBOX*) Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::add_after_then_move(tesseract::ColPartition*) Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::add_after_then_move(tesseract::ColSegment*) Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::Iterator::add_after_then_move(tesseract::TabVector*) |
221 | | |
222 | | /*********************************************************************** |
223 | | * Iterator::add_after_stay_put |
224 | | * |
225 | | * Add a new element to the list after the current element but do not move |
226 | | * the iterator to the new element. |
227 | | **********************************************************************/ |
228 | | void add_after_stay_put( // add after current & |
229 | 17 | T *new_data) { |
230 | | #ifndef NDEBUG |
231 | | if (!new_data) { |
232 | | BAD_PARAMETER.error("Iterator::add_after_stay_put", ABORT, "new_data is nullptr"); |
233 | | } |
234 | | #endif |
235 | | |
236 | 17 | auto new_element = new Link; |
237 | 17 | new_element->data = new_data; |
238 | | |
239 | 17 | if (list->empty()) { |
240 | 0 | new_element->next = new_element; |
241 | 0 | list->last = new_element; |
242 | 0 | prev = next = new_element; |
243 | 0 | ex_current_was_last = false; |
244 | 0 | current = nullptr; |
245 | 17 | } else { |
246 | 17 | new_element->next = next; |
247 | | |
248 | 17 | if (current) { // not extracted |
249 | 17 | current->next = new_element; |
250 | 17 | if (prev == current) { |
251 | 17 | prev = new_element; |
252 | 17 | } |
253 | 17 | if (current == list->last) { |
254 | 17 | list->last = new_element; |
255 | 17 | } |
256 | 17 | } else { // current extracted |
257 | 0 | prev->next = new_element; |
258 | 0 | if (ex_current_was_last) { |
259 | 0 | list->last = new_element; |
260 | 0 | ex_current_was_last = false; |
261 | 0 | } |
262 | 0 | } |
263 | 17 | next = new_element; |
264 | 17 | } |
265 | 17 | } // stay at current Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::add_after_stay_put(tesseract::ColPartition*) Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::add_after_stay_put(tesseract::BLOBNBOX*) Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::add_after_stay_put(tesseract::ColSegment*) tesseract::ConsList<tesseract::WordWithBox>::Iterator::add_after_stay_put(tesseract::WordWithBox*) Line | Count | Source | 229 | 17 | T *new_data) { | 230 | | #ifndef NDEBUG | 231 | | if (!new_data) { | 232 | | BAD_PARAMETER.error("Iterator::add_after_stay_put", ABORT, "new_data is nullptr"); | 233 | | } | 234 | | #endif | 235 | | | 236 | 17 | auto new_element = new Link; | 237 | 17 | new_element->data = new_data; | 238 | | | 239 | 17 | if (list->empty()) { | 240 | 0 | new_element->next = new_element; | 241 | 0 | list->last = new_element; | 242 | 0 | prev = next = new_element; | 243 | 0 | ex_current_was_last = false; | 244 | 0 | current = nullptr; | 245 | 17 | } else { | 246 | 17 | new_element->next = next; | 247 | | | 248 | 17 | if (current) { // not extracted | 249 | 17 | current->next = new_element; | 250 | 17 | if (prev == current) { | 251 | 17 | prev = new_element; | 252 | 17 | } | 253 | 17 | if (current == list->last) { | 254 | 17 | list->last = new_element; | 255 | 17 | } | 256 | 17 | } else { // current extracted | 257 | 0 | prev->next = new_element; | 258 | 0 | if (ex_current_was_last) { | 259 | 0 | list->last = new_element; | 260 | 0 | ex_current_was_last = false; | 261 | 0 | } | 262 | 0 | } | 263 | 17 | next = new_element; | 264 | 17 | } | 265 | 17 | } // stay at current |
|
266 | | |
267 | | /*********************************************************************** |
268 | | * Iterator::add_before_then_move |
269 | | * |
270 | | * Add a new element to the list before the current element and move the |
271 | | * iterator to the new element. |
272 | | **********************************************************************/ |
273 | | void add_before_then_move( // add before current & |
274 | 5.06M | T *new_data) { |
275 | | #ifndef NDEBUG |
276 | | if (!new_data) { |
277 | | BAD_PARAMETER.error("Iterator::add_before_then_move", ABORT, "new_data is nullptr"); |
278 | | } |
279 | | #endif |
280 | | |
281 | 5.06M | auto new_element = new Link; |
282 | 5.06M | new_element->data = new_data; |
283 | | |
284 | 5.06M | if (list->empty()) { |
285 | 226k | new_element->next = new_element; |
286 | 226k | list->last = new_element; |
287 | 226k | prev = next = new_element; |
288 | 4.83M | } else { |
289 | 4.83M | prev->next = new_element; |
290 | 4.83M | if (current) { // not extracted |
291 | 4.83M | new_element->next = current; |
292 | 4.83M | next = current; |
293 | 4.83M | } else { // current extracted |
294 | 0 | new_element->next = next; |
295 | 0 | if (ex_current_was_last) { |
296 | 0 | list->last = new_element; |
297 | 0 | } |
298 | 0 | if (ex_current_was_cycle_pt) { |
299 | 0 | cycle_pt = new_element; |
300 | 0 | } |
301 | 0 | } |
302 | 4.83M | } |
303 | 5.06M | current = new_element; |
304 | 5.06M | } // move to new Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::add_before_then_move(tesseract::ColPartition*) Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::add_before_then_move(tesseract::BLOBNBOX*) Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::add_before_then_move(tesseract::ColSegment*) tesseract::ConsList<tesseract::WordWithBox>::Iterator::add_before_then_move(tesseract::WordWithBox*) Line | Count | Source | 274 | 1.85M | T *new_data) { | 275 | | #ifndef NDEBUG | 276 | | if (!new_data) { | 277 | | BAD_PARAMETER.error("Iterator::add_before_then_move", ABORT, "new_data is nullptr"); | 278 | | } | 279 | | #endif | 280 | | | 281 | 1.85M | auto new_element = new Link; | 282 | 1.85M | new_element->data = new_data; | 283 | | | 284 | 1.85M | if (list->empty()) { | 285 | 0 | new_element->next = new_element; | 286 | 0 | list->last = new_element; | 287 | 0 | prev = next = new_element; | 288 | 1.85M | } else { | 289 | 1.85M | prev->next = new_element; | 290 | 1.85M | if (current) { // not extracted | 291 | 1.85M | new_element->next = current; | 292 | 1.85M | next = current; | 293 | 1.85M | } else { // current extracted | 294 | 0 | new_element->next = next; | 295 | 0 | if (ex_current_was_last) { | 296 | 0 | list->last = new_element; | 297 | 0 | } | 298 | 0 | if (ex_current_was_cycle_pt) { | 299 | 0 | cycle_pt = new_element; | 300 | 0 | } | 301 | 0 | } | 302 | 1.85M | } | 303 | 1.85M | current = new_element; | 304 | 1.85M | } // move to new |
tesseract::ConsList<tesseract::EDGEPT>::Iterator::add_before_then_move(tesseract::EDGEPT*) Line | Count | Source | 274 | 3.20M | T *new_data) { | 275 | | #ifndef NDEBUG | 276 | | if (!new_data) { | 277 | | BAD_PARAMETER.error("Iterator::add_before_then_move", ABORT, "new_data is nullptr"); | 278 | | } | 279 | | #endif | 280 | | | 281 | 3.20M | auto new_element = new Link; | 282 | 3.20M | new_element->data = new_data; | 283 | | | 284 | 3.20M | if (list->empty()) { | 285 | 226k | new_element->next = new_element; | 286 | 226k | list->last = new_element; | 287 | 226k | prev = next = new_element; | 288 | 2.98M | } else { | 289 | 2.98M | prev->next = new_element; | 290 | 2.98M | if (current) { // not extracted | 291 | 2.98M | new_element->next = current; | 292 | 2.98M | next = current; | 293 | 2.98M | } else { // current extracted | 294 | 0 | new_element->next = next; | 295 | 0 | if (ex_current_was_last) { | 296 | 0 | list->last = new_element; | 297 | 0 | } | 298 | 0 | if (ex_current_was_cycle_pt) { | 299 | 0 | cycle_pt = new_element; | 300 | 0 | } | 301 | 0 | } | 302 | 2.98M | } | 303 | 3.20M | current = new_element; | 304 | 3.20M | } // move to new |
Unexecuted instantiation: tesseract::ConsList<tesseract::FPSEGPT_LIST>::Iterator::add_before_then_move(tesseract::FPSEGPT_LIST*) |
305 | | |
306 | | /*********************************************************************** |
307 | | * Iterator::add_before_stay_put |
308 | | * |
309 | | * Add a new element to the list before the current element but don't move the |
310 | | * iterator to the new element. |
311 | | **********************************************************************/ |
312 | | void add_before_stay_put( // add before current & |
313 | 0 | T *new_data) { |
314 | | #ifndef NDEBUG |
315 | | if (!new_data) { |
316 | | BAD_PARAMETER.error("Iterator::add_before_stay_put", ABORT, "new_data is nullptr"); |
317 | | } |
318 | | #endif |
319 | |
|
320 | 0 | auto new_element = new Link; |
321 | 0 | new_element->data = new_data; |
322 | |
|
323 | 0 | if (list->empty()) { |
324 | 0 | new_element->next = new_element; |
325 | 0 | list->last = new_element; |
326 | 0 | prev = next = new_element; |
327 | 0 | ex_current_was_last = true; |
328 | 0 | current = nullptr; |
329 | 0 | } else { |
330 | 0 | prev->next = new_element; |
331 | 0 | if (current) { // not extracted |
332 | 0 | new_element->next = current; |
333 | 0 | if (next == current) { |
334 | 0 | next = new_element; |
335 | 0 | } |
336 | 0 | } else { // current extracted |
337 | 0 | new_element->next = next; |
338 | 0 | if (ex_current_was_last) { |
339 | 0 | list->last = new_element; |
340 | 0 | } |
341 | 0 | } |
342 | 0 | prev = new_element; |
343 | 0 | } |
344 | 0 | } // stay at current Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::add_before_stay_put(tesseract::ColPartition*) Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::add_before_stay_put(tesseract::BLOBNBOX*) Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::add_before_stay_put(tesseract::ColSegment*) Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::Iterator::add_before_stay_put(tesseract::TabVector*) Unexecuted instantiation: tesseract::ConsList<tesseract::WordWithBox>::Iterator::add_before_stay_put(tesseract::WordWithBox*) |
345 | | |
346 | | /*********************************************************************** |
347 | | * Iterator::add_list_after |
348 | | * |
349 | | * Insert another list to this list after the current element but don't move |
350 | | *the |
351 | | * iterator. |
352 | | **********************************************************************/ |
353 | | void add_list_after( // add a list & |
354 | 0 | ConsList *list_to_add) { |
355 | 0 | if (!list_to_add->empty()) { |
356 | 0 | if (list->empty()) { |
357 | 0 | list->last = list_to_add->last; |
358 | 0 | prev = list->last; |
359 | 0 | next = list->First(); |
360 | 0 | ex_current_was_last = true; |
361 | 0 | current = nullptr; |
362 | 0 | } else { |
363 | 0 | if (current) { // not extracted |
364 | 0 | current->next = list_to_add->First(); |
365 | 0 | if (current == list->last) { |
366 | 0 | list->last = list_to_add->last; |
367 | 0 | } |
368 | 0 | list_to_add->last->next = next; |
369 | 0 | next = current->next; |
370 | 0 | } else { // current extracted |
371 | 0 | prev->next = list_to_add->First(); |
372 | 0 | if (ex_current_was_last) { |
373 | 0 | list->last = list_to_add->last; |
374 | 0 | ex_current_was_last = false; |
375 | 0 | } |
376 | 0 | list_to_add->last->next = next; |
377 | 0 | next = prev->next; |
378 | 0 | } |
379 | 0 | } |
380 | 0 | list_to_add->last = nullptr; |
381 | 0 | } |
382 | 0 | } // stay at current Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::add_list_after(tesseract::ConsList<tesseract::BLOBNBOX>*) Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::add_list_after(tesseract::ConsList<tesseract::ColPartition>*) |
383 | | |
384 | | /*********************************************************************** |
385 | | * Iterator::add_list_before |
386 | | * |
387 | | * Insert another list to this list before the current element. Move the |
388 | | * iterator to the start of the inserted elements |
389 | | * iterator. |
390 | | **********************************************************************/ |
391 | | void add_list_before( // add a list & |
392 | | ConsList *list_to_add) { |
393 | | if (!list_to_add->empty()) { |
394 | | if (list->empty()) { |
395 | | list->last = list_to_add->last; |
396 | | prev = list->last; |
397 | | current = list->First(); |
398 | | next = current->next; |
399 | | ex_current_was_last = false; |
400 | | } else { |
401 | | prev->next = list_to_add->First(); |
402 | | if (current) { // not extracted |
403 | | list_to_add->last->next = current; |
404 | | } else { // current extracted |
405 | | list_to_add->last->next = next; |
406 | | if (ex_current_was_last) { |
407 | | list->last = list_to_add->last; |
408 | | } |
409 | | if (ex_current_was_cycle_pt) { |
410 | | cycle_pt = prev->next; |
411 | | } |
412 | | } |
413 | | current = prev->next; |
414 | | next = current->next; |
415 | | } |
416 | | list_to_add->last = nullptr; |
417 | | } |
418 | | } // move to it 1st item |
419 | | |
420 | 9.70M | T *data() { // get current data |
421 | | #ifndef NDEBUG |
422 | | if (!list) { |
423 | | NO_LIST.error("Iterator::data", ABORT); |
424 | | } |
425 | | #endif |
426 | 9.70M | return current->data; |
427 | 9.70M | } Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::data() Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::data() Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::data() Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::Iterator::data() tesseract::ConsList<tesseract::WordWithBox>::Iterator::data() Line | Count | Source | 420 | 6.49M | T *data() { // get current data | 421 | | #ifndef NDEBUG | 422 | | if (!list) { | 423 | | NO_LIST.error("Iterator::data", ABORT); | 424 | | } | 425 | | #endif | 426 | 6.49M | return current->data; | 427 | 6.49M | } |
tesseract::ConsList<tesseract::EDGEPT>::Iterator::data() Line | Count | Source | 420 | 3.20M | T *data() { // get current data | 421 | | #ifndef NDEBUG | 422 | | if (!list) { | 423 | | NO_LIST.error("Iterator::data", ABORT); | 424 | | } | 425 | | #endif | 426 | 3.20M | return current->data; | 427 | 3.20M | } |
Unexecuted instantiation: tesseract::ConsList<tesseract::FPSEGPT_LIST>::Iterator::data() |
428 | | |
429 | | /*********************************************************************** |
430 | | * Iterator::data_relative |
431 | | * |
432 | | * Return the data pointer to the element "offset" elements from current. |
433 | | * "offset" must not be less than -1. |
434 | | * (This function can't be INLINEd because it contains a loop) |
435 | | **********************************************************************/ |
436 | | T *data_relative( // get data + or - ... |
437 | 0 | int8_t offset) { // offset from current |
438 | 0 | Link *ptr; |
439 | |
|
440 | | #ifndef NDEBUG |
441 | | if (!list) |
442 | | NO_LIST.error("Iterator::data_relative", ABORT); |
443 | | if (list->empty()) |
444 | | EMPTY_LIST.error("Iterator::data_relative", ABORT); |
445 | | if (offset < -1) |
446 | | BAD_PARAMETER.error("Iterator::data_relative", ABORT, "offset < -l"); |
447 | | #endif |
448 | |
|
449 | 0 | if (offset == -1) { |
450 | 0 | ptr = prev; |
451 | 0 | } else { |
452 | 0 | for (ptr = current ? current : prev; offset-- > 0; ptr = ptr->next) { |
453 | 0 | ; |
454 | 0 | } |
455 | 0 | } |
456 | |
|
457 | 0 | return ptr->data; |
458 | 0 | } Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::data_relative(signed char) Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::data_relative(signed char) Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::data_relative(signed char) |
459 | | |
460 | | /*********************************************************************** |
461 | | * Iterator::forward |
462 | | * |
463 | | * Move the iterator to the next element of the list. |
464 | | * REMEMBER: ALL LISTS ARE CIRCULAR. |
465 | | **********************************************************************/ |
466 | 7.84M | T *forward() { |
467 | 7.84M | if (list->empty()) { |
468 | 0 | return nullptr; |
469 | 0 | } |
470 | | |
471 | 7.84M | if (current) { // not removed so |
472 | | // set previous |
473 | 7.84M | prev = current; |
474 | 7.84M | started_cycling = true; |
475 | | // In case next is deleted by another iterator, get next from current. |
476 | 7.84M | current = current->next; |
477 | 7.84M | } else { |
478 | 0 | if (ex_current_was_cycle_pt) { |
479 | 0 | cycle_pt = next; |
480 | 0 | } |
481 | 0 | current = next; |
482 | 0 | } |
483 | | |
484 | 7.84M | next = current->next; |
485 | 7.84M | return current->data; |
486 | 7.84M | } Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::forward() Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::forward() Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::forward() Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::Iterator::forward() tesseract::ConsList<tesseract::WordWithBox>::Iterator::forward() Line | Count | Source | 466 | 4.63M | T *forward() { | 467 | 4.63M | if (list->empty()) { | 468 | 0 | return nullptr; | 469 | 0 | } | 470 | | | 471 | 4.63M | if (current) { // not removed so | 472 | | // set previous | 473 | 4.63M | prev = current; | 474 | 4.63M | started_cycling = true; | 475 | | // In case next is deleted by another iterator, get next from current. | 476 | 4.63M | current = current->next; | 477 | 4.63M | } else { | 478 | 0 | if (ex_current_was_cycle_pt) { | 479 | 0 | cycle_pt = next; | 480 | 0 | } | 481 | 0 | current = next; | 482 | 0 | } | 483 | | | 484 | 4.63M | next = current->next; | 485 | 4.63M | return current->data; | 486 | 4.63M | } |
tesseract::ConsList<tesseract::EDGEPT>::Iterator::forward() Line | Count | Source | 466 | 3.20M | T *forward() { | 467 | 3.20M | if (list->empty()) { | 468 | 0 | return nullptr; | 469 | 0 | } | 470 | | | 471 | 3.20M | if (current) { // not removed so | 472 | | // set previous | 473 | 3.20M | prev = current; | 474 | 3.20M | started_cycling = true; | 475 | | // In case next is deleted by another iterator, get next from current. | 476 | 3.20M | current = current->next; | 477 | 3.20M | } else { | 478 | 0 | if (ex_current_was_cycle_pt) { | 479 | 0 | cycle_pt = next; | 480 | 0 | } | 481 | 0 | current = next; | 482 | 0 | } | 483 | | | 484 | 3.20M | next = current->next; | 485 | 3.20M | return current->data; | 486 | 3.20M | } |
Unexecuted instantiation: tesseract::ConsList<tesseract::FPSEGPT_LIST>::Iterator::forward() |
487 | | |
488 | | /*********************************************************************** |
489 | | * Iterator::extract |
490 | | * |
491 | | * Do extraction by removing current from the list, deleting the cons cell |
492 | | * and returning the data to the caller, but NOT updating the iterator. (So |
493 | | * that any calling loop can do this.) The iterator's current points to |
494 | | * nullptr. If the data is to be deleted, this is the callers responsibility. |
495 | | **********************************************************************/ |
496 | 0 | T *extract() { |
497 | | #ifndef NDEBUG |
498 | | if (!current) { // list empty or |
499 | | // element extracted |
500 | | NULL_CURRENT.error("Iterator::extract", ABORT); |
501 | | } |
502 | | #endif |
503 | |
|
504 | 0 | if (list->singleton()) { |
505 | | // Special case where we do need to change the iterator. |
506 | 0 | prev = next = list->last = nullptr; |
507 | 0 | } else { |
508 | 0 | prev->next = next; // remove from list |
509 | |
|
510 | 0 | if (current == list->last) { |
511 | 0 | list->last = prev; |
512 | 0 | ex_current_was_last = true; |
513 | 0 | } else { |
514 | 0 | ex_current_was_last = false; |
515 | 0 | } |
516 | 0 | } |
517 | | // Always set ex_current_was_cycle_pt so an add/forward will work in a loop. |
518 | 0 | ex_current_was_cycle_pt = (current == cycle_pt); |
519 | 0 | auto extracted_data = current->data; |
520 | 0 | delete (current); // destroy CONS cell |
521 | 0 | current = nullptr; |
522 | 0 | return extracted_data; |
523 | 0 | } // remove from list Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::extract() Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::extract() Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::extract() Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::Iterator::extract() |
524 | | |
525 | | /*********************************************************************** |
526 | | * Iterator::move_to_first() |
527 | | * |
528 | | * Move current so that it is set to the start of the list. |
529 | | * Return data just in case anyone wants it. |
530 | | **********************************************************************/ |
531 | 0 | T *move_to_first() { |
532 | 0 | current = list->First(); |
533 | 0 | prev = list->last; |
534 | 0 | next = current != nullptr ? current->next : nullptr; |
535 | 0 | return current != nullptr ? current->data : nullptr; |
536 | 0 | } // go to start of list Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::move_to_first() Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::move_to_first() Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::move_to_first() |
537 | | |
538 | | /*********************************************************************** |
539 | | * Iterator::move_to_last() |
540 | | * |
541 | | * Move current so that it is set to the end of the list. |
542 | | * Return data just in case anyone wants it. |
543 | | * (This function can't be INLINEd because it contains a loop) |
544 | | **********************************************************************/ |
545 | 0 | T *move_to_last() { |
546 | 0 | while (current != list->last) { |
547 | 0 | forward(); |
548 | 0 | } |
549 | |
|
550 | 0 | if (current == nullptr) { |
551 | 0 | return nullptr; |
552 | 0 | } else { |
553 | 0 | return current->data; |
554 | 0 | } |
555 | 0 | } Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::move_to_last() Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::Iterator::move_to_last() |
556 | | |
557 | | /*********************************************************************** |
558 | | * Iterator::mark_cycle_pt() |
559 | | * |
560 | | * Remember the current location so that we can tell whether we've returned |
561 | | * to this point later. |
562 | | * |
563 | | * If the current point is deleted either now, or in the future, the cycle |
564 | | * point will be set to the next item which is set to current. This could be |
565 | | * by a forward, add_after_then_move or add_after_then_move. |
566 | | **********************************************************************/ |
567 | 2.43M | void mark_cycle_pt() { |
568 | | #ifndef NDEBUG |
569 | | if (!list) { |
570 | | NO_LIST.error("Iterator::mark_cycle_pt", ABORT); |
571 | | } |
572 | | #endif |
573 | | |
574 | 2.43M | if (current) { |
575 | 2.08M | cycle_pt = current; |
576 | 2.08M | } else { |
577 | 356k | ex_current_was_cycle_pt = true; |
578 | 356k | } |
579 | 2.43M | started_cycling = false; |
580 | 2.43M | } // remember current Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::mark_cycle_pt() Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::mark_cycle_pt() Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::mark_cycle_pt() Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::Iterator::mark_cycle_pt() tesseract::ConsList<tesseract::WordWithBox>::Iterator::mark_cycle_pt() Line | Count | Source | 567 | 1.85M | void mark_cycle_pt() { | 568 | | #ifndef NDEBUG | 569 | | if (!list) { | 570 | | NO_LIST.error("Iterator::mark_cycle_pt", ABORT); | 571 | | } | 572 | | #endif | 573 | | | 574 | 1.85M | if (current) { | 575 | 1.85M | cycle_pt = current; | 576 | 1.85M | } else { | 577 | 0 | ex_current_was_cycle_pt = true; | 578 | 0 | } | 579 | 1.85M | started_cycling = false; | 580 | 1.85M | } // remember current |
tesseract::ConsList<tesseract::EDGEPT>::Iterator::mark_cycle_pt() Line | Count | Source | 567 | 582k | void mark_cycle_pt() { | 568 | | #ifndef NDEBUG | 569 | | if (!list) { | 570 | | NO_LIST.error("Iterator::mark_cycle_pt", ABORT); | 571 | | } | 572 | | #endif | 573 | | | 574 | 582k | if (current) { | 575 | 226k | cycle_pt = current; | 576 | 356k | } else { | 577 | 356k | ex_current_was_cycle_pt = true; | 578 | 356k | } | 579 | 582k | started_cycling = false; | 580 | 582k | } // remember current |
Unexecuted instantiation: tesseract::ConsList<tesseract::FPSEGPT_LIST>::Iterator::mark_cycle_pt() |
581 | | |
582 | 0 | bool empty() const { // is list empty? |
583 | 0 | return list->empty(); |
584 | 0 | } Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::empty() const Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::empty() const Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::empty() const Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::Iterator::empty() const Unexecuted instantiation: tesseract::ConsList<tesseract::WordWithBox>::Iterator::empty() const |
585 | | |
586 | | bool current_extracted() const { // current extracted? |
587 | | return !current; |
588 | | } |
589 | | |
590 | | /*********************************************************************** |
591 | | * Iterator::at_first() |
592 | | * |
593 | | * Are we at the start of the list? |
594 | | * |
595 | | **********************************************************************/ |
596 | 0 | bool at_first() const { |
597 | | // we're at a deleted |
598 | 0 | return ((list->empty()) || (current == list->First()) || |
599 | 0 | ((current == nullptr) && (prev == list->last) && // NON-last pt between |
600 | 0 | !ex_current_was_last)); // first and last |
601 | 0 | } // Current is first? Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::at_first() const Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::at_first() const Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::at_first() const Unexecuted instantiation: tesseract::ConsList<tesseract::WordWithBox>::Iterator::at_first() const |
602 | | |
603 | | /*********************************************************************** |
604 | | * Iterator::at_last() |
605 | | * |
606 | | * Are we at the end of the list? |
607 | | * |
608 | | **********************************************************************/ |
609 | 17 | bool at_last() const { |
610 | | // we're at a deleted |
611 | 17 | return ((list->empty()) || (current == list->last) || |
612 | 17 | ((current == nullptr) && (prev == list->last) && // last point between |
613 | 0 | ex_current_was_last)); // first and last |
614 | 17 | } // Current is last? Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::at_last() const Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::at_last() const Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::at_last() const Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::Iterator::at_last() const tesseract::ConsList<tesseract::WordWithBox>::Iterator::at_last() const Line | Count | Source | 609 | 17 | bool at_last() const { | 610 | | // we're at a deleted | 611 | 17 | return ((list->empty()) || (current == list->last) || | 612 | 17 | ((current == nullptr) && (prev == list->last) && // last point between | 613 | 0 | ex_current_was_last)); // first and last | 614 | 17 | } // Current is last? |
|
615 | | |
616 | | /*********************************************************************** |
617 | | * Iterator::cycled_list() |
618 | | * |
619 | | * Have we returned to the cycle_pt since it was set? |
620 | | * |
621 | | **********************************************************************/ |
622 | 12.1M | bool cycled_list() const { // Completed a cycle? |
623 | 12.1M | return ((list->empty()) || ((current == cycle_pt) && started_cycling)); |
624 | 12.1M | } Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::cycled_list() const Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::cycled_list() const Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::cycled_list() const Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::Iterator::cycled_list() const tesseract::ConsList<tesseract::WordWithBox>::Iterator::cycled_list() const Line | Count | Source | 622 | 8.34M | bool cycled_list() const { // Completed a cycle? | 623 | 8.34M | return ((list->empty()) || ((current == cycle_pt) && started_cycling)); | 624 | 8.34M | } |
tesseract::ConsList<tesseract::EDGEPT>::Iterator::cycled_list() const Line | Count | Source | 622 | 3.79M | bool cycled_list() const { // Completed a cycle? | 623 | 3.79M | return ((list->empty()) || ((current == cycle_pt) && started_cycling)); | 624 | 3.79M | } |
Unexecuted instantiation: tesseract::ConsList<tesseract::FPSEGPT_LIST>::Iterator::cycled_list() const |
625 | | |
626 | | /*********************************************************************** |
627 | | * Iterator::add_to_end |
628 | | * |
629 | | * Add a new element to the end of the list without moving the iterator. |
630 | | * This is provided because a single linked list cannot move to the last as |
631 | | * the iterator couldn't set its prev pointer. Adding to the end is |
632 | | * essential for implementing |
633 | | queues. |
634 | | **********************************************************************/ |
635 | | void add_to_end( // element to add |
636 | 17 | T *new_data) { |
637 | | #ifndef NDEBUG |
638 | | if (!list) { |
639 | | NO_LIST.error("Iterator::add_to_end", ABORT); |
640 | | } |
641 | | if (!new_data) { |
642 | | BAD_PARAMETER.error("Iterator::add_to_end", ABORT, "new_data is nullptr"); |
643 | | } |
644 | | #endif |
645 | | |
646 | 17 | if (this->at_last()) { |
647 | 17 | this->add_after_stay_put(new_data); |
648 | 17 | } else { |
649 | 0 | if (this->at_first()) { |
650 | 0 | this->add_before_stay_put(new_data); |
651 | 0 | list->last = prev; |
652 | 0 | } else { // Iteratr is elsewhere |
653 | 0 | auto new_element = new Link; |
654 | 0 | new_element->data = new_data; |
655 | |
|
656 | 0 | new_element->next = list->last->next; |
657 | 0 | list->last->next = new_element; |
658 | 0 | list->last = new_element; |
659 | 0 | } |
660 | 0 | } |
661 | 17 | } Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::add_to_end(tesseract::ColPartition*) Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::add_to_end(tesseract::BLOBNBOX*) Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::add_to_end(tesseract::ColSegment*) tesseract::ConsList<tesseract::WordWithBox>::Iterator::add_to_end(tesseract::WordWithBox*) Line | Count | Source | 636 | 17 | T *new_data) { | 637 | | #ifndef NDEBUG | 638 | | if (!list) { | 639 | | NO_LIST.error("Iterator::add_to_end", ABORT); | 640 | | } | 641 | | if (!new_data) { | 642 | | BAD_PARAMETER.error("Iterator::add_to_end", ABORT, "new_data is nullptr"); | 643 | | } | 644 | | #endif | 645 | | | 646 | 17 | if (this->at_last()) { | 647 | 17 | this->add_after_stay_put(new_data); | 648 | 17 | } else { | 649 | 0 | if (this->at_first()) { | 650 | 0 | this->add_before_stay_put(new_data); | 651 | 0 | list->last = prev; | 652 | 0 | } else { // Iteratr is elsewhere | 653 | 0 | auto new_element = new Link; | 654 | 0 | new_element->data = new_data; | 655 | |
| 656 | 0 | new_element->next = list->last->next; | 657 | 0 | list->last->next = new_element; | 658 | 0 | list->last = new_element; | 659 | 0 | } | 660 | 0 | } | 661 | 17 | } |
|
662 | | |
663 | | /*********************************************************************** |
664 | | * Iterator::exchange() |
665 | | * |
666 | | * Given another iterator, whose current element is a different element on |
667 | | * the same list list OR an element of another list, exchange the two current |
668 | | * elements. On return, each iterator points to the element which was the |
669 | | * other iterators current on entry. |
670 | | * (This function hasn't been in-lined because its a bit big!) |
671 | | **********************************************************************/ |
672 | | void exchange( // positions of 2 links |
673 | | Iterator *other_it) { // other iterator |
674 | | constexpr ERRCODE DONT_EXCHANGE_DELETED("Can't exchange deleted elements of lists"); |
675 | | |
676 | | /* Do nothing if either list is empty or if both iterators reference the same |
677 | | link */ |
678 | | |
679 | | if ((list->empty()) || (other_it->list->empty()) || (current == other_it->current)) { |
680 | | return; |
681 | | } |
682 | | |
683 | | /* Error if either current element is deleted */ |
684 | | |
685 | | if (!current || !other_it->current) { |
686 | | DONT_EXCHANGE_DELETED.error("Iterator.exchange", ABORT); |
687 | | } |
688 | | |
689 | | /* Now handle the 4 cases: doubleton list; non-doubleton adjacent elements |
690 | | (other before this); non-doubleton adjacent elements (this before other); |
691 | | non-adjacent elements. */ |
692 | | |
693 | | // adjacent links |
694 | | if ((next == other_it->current) || (other_it->next == current)) { |
695 | | // doubleton list |
696 | | if ((next == other_it->current) && (other_it->next == current)) { |
697 | | prev = next = current; |
698 | | other_it->prev = other_it->next = other_it->current; |
699 | | } else { // non-doubleton with |
700 | | // adjacent links |
701 | | // other before this |
702 | | if (other_it->next == current) { |
703 | | other_it->prev->next = current; |
704 | | other_it->current->next = next; |
705 | | current->next = other_it->current; |
706 | | other_it->next = other_it->current; |
707 | | prev = current; |
708 | | } else { // this before other |
709 | | prev->next = other_it->current; |
710 | | current->next = other_it->next; |
711 | | other_it->current->next = current; |
712 | | next = current; |
713 | | other_it->prev = other_it->current; |
714 | | } |
715 | | } |
716 | | } else { // no overlap |
717 | | prev->next = other_it->current; |
718 | | current->next = other_it->next; |
719 | | other_it->prev->next = current; |
720 | | other_it->current->next = next; |
721 | | } |
722 | | |
723 | | /* update end of list pointer when necessary (remember that the 2 iterators |
724 | | may iterate over different lists!) */ |
725 | | |
726 | | if (list->last == current) { |
727 | | list->last = other_it->current; |
728 | | } |
729 | | if (other_it->list->last == other_it->current) { |
730 | | other_it->list->last = current; |
731 | | } |
732 | | |
733 | | if (current == cycle_pt) { |
734 | | cycle_pt = other_it->cycle_pt; |
735 | | } |
736 | | if (other_it->current == other_it->cycle_pt) { |
737 | | other_it->cycle_pt = cycle_pt; |
738 | | } |
739 | | |
740 | | /* The actual exchange - in all cases*/ |
741 | | |
742 | | auto old_current = current; |
743 | | current = other_it->current; |
744 | | other_it->current = old_current; |
745 | | } |
746 | | |
747 | | /*********************************************************************** |
748 | | * Iterator::length() |
749 | | * |
750 | | * Return the length of the list |
751 | | * |
752 | | **********************************************************************/ |
753 | 0 | int32_t length() const { |
754 | 0 | return list->length(); |
755 | 0 | } |
756 | | |
757 | | /*********************************************************************** |
758 | | * Iterator::sort() |
759 | | * |
760 | | * Sort the elements of the list, then reposition at the start. |
761 | | * |
762 | | **********************************************************************/ |
763 | | void sort( // sort elements |
764 | | int comparator( // comparison routine |
765 | | const T *, const T *)) { |
766 | | list->sort(comparator); |
767 | | move_to_first(); |
768 | | } |
769 | | }; |
770 | | using ITERATOR = Iterator; // compat |
771 | | |
772 | | private: |
773 | | Link *last = nullptr; // End of list |
774 | | |
775 | | //(Points to head) |
776 | 12.2M | Link *First() { // return first |
777 | 12.2M | return last != nullptr ? last->next : nullptr; |
778 | 12.2M | } Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::First() Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::First() Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::First() Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::First() tesseract::ConsList<tesseract::WordWithBox>::First() Line | Count | Source | 776 | 1.85M | Link *First() { // return first | 777 | 1.85M | return last != nullptr ? last->next : nullptr; | 778 | 1.85M | } |
tesseract::ConsList<tesseract::EDGEPT>::First() Line | Count | Source | 776 | 10.3M | Link *First() { // return first | 777 | 10.3M | return last != nullptr ? last->next : nullptr; | 778 | 10.3M | } |
Unexecuted instantiation: tesseract::ConsList<tesseract::FPSEGPT_LIST>::First() |
779 | | |
780 | | const Link *First() const { // return first |
781 | | return last != nullptr ? last->next : nullptr; |
782 | | } |
783 | | |
784 | | public: |
785 | 7.07M | ~ConsList() { // destructor |
786 | 7.07M | shallow_clear(); |
787 | 7.07M | } Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::~ConsList() Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::~ConsList() Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::~ConsList() Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::~ConsList() tesseract::ConsList<tesseract::WordWithBox>::~ConsList() Line | Count | Source | 785 | 6.48M | ~ConsList() { // destructor | 786 | 6.48M | shallow_clear(); | 787 | 6.48M | } |
tesseract::ConsList<tesseract::EDGEPT>::~ConsList() Line | Count | Source | 785 | 582k | ~ConsList() { // destructor | 786 | 582k | shallow_clear(); | 787 | 582k | } |
Unexecuted instantiation: tesseract::ConsList<tesseract::FPSEGPT_LIST>::~ConsList() |
788 | | |
789 | | /*********************************************************************** |
790 | | * ConsList::internal_deep_clear |
791 | | * |
792 | | * Used by the "deep_clear" member function of derived list |
793 | | * classes to destroy all the elements on the list. |
794 | | * The calling function passes a "zapper" function which can be called to |
795 | | * delete each data element of the list, regardless of its class. This |
796 | | * technique permits a generic clear function to destroy elements of |
797 | | * different derived types correctly, without requiring virtual functions and |
798 | | * the consequential memory overhead. |
799 | | **********************************************************************/ |
800 | 0 | void internal_deep_clear() { // ptr to zapper functn |
801 | 0 | if (!empty()) { |
802 | 0 | auto ptr = last->next; // set to first |
803 | 0 | last->next = nullptr; // break circle |
804 | 0 | last = nullptr; // set list empty |
805 | 0 | while (ptr) { |
806 | 0 | auto next = ptr->next; |
807 | 0 | delete ptr->data; |
808 | 0 | delete (ptr); |
809 | 0 | ptr = next; |
810 | 0 | } |
811 | 0 | } |
812 | 0 | } |
813 | 0 | void deep_clear() { |
814 | 0 | internal_deep_clear(); |
815 | 0 | } |
816 | | |
817 | | /*********************************************************************** |
818 | | * ConsList::shallow_clear |
819 | | * |
820 | | * Used by the destructor and the "shallow_clear" member function of derived |
821 | | * list classes to destroy the list. |
822 | | * The data elements are NOT destroyed. |
823 | | * |
824 | | **********************************************************************/ |
825 | 7.07M | void shallow_clear() { // destroy all links |
826 | 7.07M | if (!empty()) { |
827 | 1.20M | auto ptr = last->next; // set to first |
828 | 1.20M | last->next = nullptr; // break circle |
829 | 1.20M | last = nullptr; // set list empty |
830 | 8.27M | while (ptr) { |
831 | 7.06M | auto next = ptr->next; |
832 | 7.06M | delete (ptr); |
833 | 7.06M | ptr = next; |
834 | 7.06M | } |
835 | 1.20M | } |
836 | 7.07M | } Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::shallow_clear() Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::shallow_clear() Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::shallow_clear() Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::shallow_clear() tesseract::ConsList<tesseract::WordWithBox>::shallow_clear() Line | Count | Source | 825 | 6.48M | void shallow_clear() { // destroy all links | 826 | 6.48M | if (!empty()) { | 827 | 983k | auto ptr = last->next; // set to first | 828 | 983k | last->next = nullptr; // break circle | 829 | 983k | last = nullptr; // set list empty | 830 | 4.84M | while (ptr) { | 831 | 3.86M | auto next = ptr->next; | 832 | 3.86M | delete (ptr); | 833 | 3.86M | ptr = next; | 834 | 3.86M | } | 835 | 983k | } | 836 | 6.48M | } |
tesseract::ConsList<tesseract::EDGEPT>::shallow_clear() Line | Count | Source | 825 | 582k | void shallow_clear() { // destroy all links | 826 | 582k | if (!empty()) { | 827 | 226k | auto ptr = last->next; // set to first | 828 | 226k | last->next = nullptr; // break circle | 829 | 226k | last = nullptr; // set list empty | 830 | 3.43M | while (ptr) { | 831 | 3.20M | auto next = ptr->next; | 832 | 3.20M | delete (ptr); | 833 | 3.20M | ptr = next; | 834 | 3.20M | } | 835 | 226k | } | 836 | 582k | } |
Unexecuted instantiation: tesseract::ConsList<tesseract::FPSEGPT_LIST>::shallow_clear() |
837 | | |
838 | 32.1M | bool empty() const { // is list empty? |
839 | 32.1M | return !last; |
840 | 32.1M | } Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::empty() const Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::empty() const Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::empty() const Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::empty() const tesseract::ConsList<tesseract::WordWithBox>::empty() const Line | Count | Source | 838 | 21.3M | bool empty() const { // is list empty? | 839 | 21.3M | return !last; | 840 | 21.3M | } |
tesseract::ConsList<tesseract::EDGEPT>::empty() const Line | Count | Source | 838 | 10.7M | bool empty() const { // is list empty? | 839 | 10.7M | return !last; | 840 | 10.7M | } |
Unexecuted instantiation: tesseract::ConsList<tesseract::FPSEGPT_LIST>::empty() const |
841 | | |
842 | 0 | bool singleton() const { |
843 | 0 | return last != nullptr ? (last == last->next) : false; |
844 | 0 | } Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::singleton() const Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::singleton() const Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::singleton() const Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::singleton() const |
845 | | |
846 | | void shallow_copy( // dangerous!! |
847 | | ConsList *from_list) { // beware destructors!! |
848 | | last = from_list->last; |
849 | | } |
850 | | |
851 | | /*********************************************************************** |
852 | | * ConsList::assign_to_sublist |
853 | | * |
854 | | * The list is set to a sublist of another list. "This" list must be empty |
855 | | * before this function is invoked. The two iterators passed must refer to |
856 | | * the same list, different from "this" one. The sublist removed is the |
857 | | * inclusive list from start_it's current position to end_it's current |
858 | | * position. If this range passes over the end of the source list then the |
859 | | * source list has its end set to the previous element of start_it. The |
860 | | * extracted sublist is unaffected by the end point of the source list, its |
861 | | * end point is always the end_it position. |
862 | | **********************************************************************/ |
863 | | void assign_to_sublist( // to this list |
864 | | Iterator *start_it, // from list start |
865 | | Iterator *end_it) { // from list end |
866 | | constexpr ERRCODE LIST_NOT_EMPTY("Destination list must be empty before extracting a sublist"); |
867 | | |
868 | | if (!empty()) { |
869 | | LIST_NOT_EMPTY.error("ConsList.assign_to_sublist", ABORT); |
870 | | } |
871 | | |
872 | | last = start_it->extract_sublist(end_it); |
873 | | } |
874 | | |
875 | 0 | int32_t length() const { //# elements in list |
876 | 0 | int32_t count = 0; |
877 | 0 | if (last != nullptr) { |
878 | 0 | count = 1; |
879 | 0 | for (auto it = last->next; it != last; it = it->next) { |
880 | 0 | count++; |
881 | 0 | } |
882 | 0 | } |
883 | 0 | return count; |
884 | 0 | } Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::length() const Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::length() const Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::length() const |
885 | | |
886 | | /*********************************************************************** |
887 | | * ConsList::sort |
888 | | * |
889 | | * Sort elements on list |
890 | | **********************************************************************/ |
891 | | void sort( // sort elements |
892 | | int comparator( // comparison routine |
893 | 0 | const T *, const T *)) { |
894 | | // Allocate an array of pointers, one per list element. |
895 | 0 | auto count = length(); |
896 | 0 | if (count > 0) { |
897 | | // ptr array to sort |
898 | 0 | std::vector<T *> base; |
899 | 0 | base.reserve(count); |
900 | |
|
901 | 0 | Iterator it(this); |
902 | | |
903 | | // Extract all elements, putting the pointers in the array. |
904 | 0 | for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) { |
905 | 0 | base.push_back(it.extract()); |
906 | 0 | } |
907 | | |
908 | | // Sort the pointer array. |
909 | 0 | std::sort(base.begin(), base.end(), |
910 | | // all current comparators return -1,0,1, so we handle this correctly for std::sort |
911 | 0 | [&](auto &&l, auto &&r) {return comparator(l, r) < 0; }); |
912 | | |
913 | | // Rebuild the list from the sorted pointers. |
914 | 0 | for (auto current : base) { |
915 | 0 | it.add_to_end(current); |
916 | 0 | } |
917 | 0 | } |
918 | 0 | } |
919 | | |
920 | | // Assuming list has been sorted already, insert new_data to |
921 | | // keep the list sorted according to the same comparison function. |
922 | | // Comparison function is the same as used by sort, i.e. uses double |
923 | | // indirection. Time is O(1) to add to beginning or end. |
924 | | // Time is linear to add pre-sorted items to an empty list. |
925 | | // If unique, then don't add duplicate entries. |
926 | | // Returns true if the element was added to the list. |
927 | 3.86M | bool add_sorted(int comparator(const T *, const T *), bool unique, T *new_data) { |
928 | | // Check for adding at the end. |
929 | 3.86M | if (last == nullptr || comparator(last->data, new_data) < 0) { |
930 | 2.00M | auto *new_element = new Link; |
931 | 2.00M | new_element->data = new_data; |
932 | 2.00M | if (last == nullptr) { |
933 | 983k | new_element->next = new_element; |
934 | 1.02M | } else { |
935 | 1.02M | new_element->next = last->next; |
936 | 1.02M | last->next = new_element; |
937 | 1.02M | } |
938 | 2.00M | last = new_element; |
939 | 2.00M | return true; |
940 | 2.00M | } else if (!unique || last->data != new_data) { |
941 | | // Need to use an iterator. |
942 | 1.85M | Iterator it(this); |
943 | 6.49M | for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) { |
944 | 6.49M | auto data = it.data(); |
945 | 6.49M | if (data == new_data && unique) { |
946 | 0 | return false; |
947 | 0 | } |
948 | 6.49M | if (comparator(data, new_data) > 0) { |
949 | 1.85M | break; |
950 | 1.85M | } |
951 | 6.49M | } |
952 | 1.85M | if (it.cycled_list()) { |
953 | 17 | it.add_to_end(new_data); |
954 | 1.85M | } else { |
955 | 1.85M | it.add_before_then_move(new_data); |
956 | 1.85M | } |
957 | 1.85M | return true; |
958 | 1.85M | } |
959 | 0 | return false; |
960 | 3.86M | } Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::add_sorted(int (*)(tesseract::ColPartition const*, tesseract::ColPartition const*), bool, tesseract::ColPartition*) Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::add_sorted(int (*)(tesseract::BLOBNBOX const*, tesseract::BLOBNBOX const*), bool, tesseract::BLOBNBOX*) Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::add_sorted(int (*)(tesseract::ColSegment const*, tesseract::ColSegment const*), bool, tesseract::ColSegment*) tesseract::ConsList<tesseract::WordWithBox>::add_sorted(int (*)(tesseract::WordWithBox const*, tesseract::WordWithBox const*), bool, tesseract::WordWithBox*) Line | Count | Source | 927 | 3.86M | bool add_sorted(int comparator(const T *, const T *), bool unique, T *new_data) { | 928 | | // Check for adding at the end. | 929 | 3.86M | if (last == nullptr || comparator(last->data, new_data) < 0) { | 930 | 2.00M | auto *new_element = new Link; | 931 | 2.00M | new_element->data = new_data; | 932 | 2.00M | if (last == nullptr) { | 933 | 983k | new_element->next = new_element; | 934 | 1.02M | } else { | 935 | 1.02M | new_element->next = last->next; | 936 | 1.02M | last->next = new_element; | 937 | 1.02M | } | 938 | 2.00M | last = new_element; | 939 | 2.00M | return true; | 940 | 2.00M | } else if (!unique || last->data != new_data) { | 941 | | // Need to use an iterator. | 942 | 1.85M | Iterator it(this); | 943 | 6.49M | for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) { | 944 | 6.49M | auto data = it.data(); | 945 | 6.49M | if (data == new_data && unique) { | 946 | 0 | return false; | 947 | 0 | } | 948 | 6.49M | if (comparator(data, new_data) > 0) { | 949 | 1.85M | break; | 950 | 1.85M | } | 951 | 6.49M | } | 952 | 1.85M | if (it.cycled_list()) { | 953 | 17 | it.add_to_end(new_data); | 954 | 1.85M | } else { | 955 | 1.85M | it.add_before_then_move(new_data); | 956 | 1.85M | } | 957 | 1.85M | return true; | 958 | 1.85M | } | 959 | 0 | return false; | 960 | 3.86M | } |
|
961 | | |
962 | | // Assuming that the minuend and subtrahend are already sorted with |
963 | | // the same comparison function, shallow clears this and then copies |
964 | | // the set difference minuend - subtrahend to this, being the elements |
965 | | // of minuend that do not compare equal to anything in subtrahend. |
966 | | // If unique is true, any duplicates in minuend are also eliminated. |
967 | | void set_subtract(int comparator(const T *, const T *), bool unique, ConsList *minuend, |
968 | 0 | ConsList *subtrahend) { |
969 | 0 | shallow_clear(); |
970 | 0 | Iterator m_it(minuend); |
971 | 0 | Iterator s_it(subtrahend); |
972 | | // Since both lists are sorted, finding the subtras that are not |
973 | | // minus is a case of a parallel iteration. |
974 | 0 | for (m_it.mark_cycle_pt(); !m_it.cycled_list(); m_it.forward()) { |
975 | 0 | auto minu = m_it.data(); |
976 | 0 | T *subtra = nullptr; |
977 | 0 | if (!s_it.empty()) { |
978 | 0 | subtra = s_it.data(); |
979 | 0 | while (!s_it.at_last() && comparator(subtra, minu) < 0) { |
980 | 0 | s_it.forward(); |
981 | 0 | subtra = s_it.data(); |
982 | 0 | } |
983 | 0 | } |
984 | 0 | if (subtra == nullptr || comparator(subtra, minu) != 0) { |
985 | 0 | add_sorted(comparator, unique, minu); |
986 | 0 | } |
987 | 0 | } |
988 | 0 | } |
989 | | }; |
990 | | |
991 | | #define CLISTIZEH(T) \ |
992 | | class T##_CLIST : public ConsList<T> { \ |
993 | | using ConsList<T>::ConsList; \ |
994 | | }; \ |
995 | | using T##_C_IT = ConsList<T>::Iterator; |
996 | | |
997 | | } // namespace tesseract |
998 | | |
999 | | #endif |