/src/tesseract/src/ccutil/elst2.h
Line | Count | Source (jump to first uncovered line) |
1 | | /********************************************************************** |
2 | | * File: elst2.h (Formerly elist2.h) |
3 | | * Description: Double linked embedded 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 ELST2_H |
20 | | #define ELST2_H |
21 | | |
22 | | #include "lsterr.h" |
23 | | #include "serialis.h" |
24 | | |
25 | | #include <algorithm> |
26 | | #include <cstdio> |
27 | | |
28 | | namespace tesseract { |
29 | | |
30 | | /********************************************************************** |
31 | | DESIGN NOTE |
32 | | =========== |
33 | | |
34 | | It would probably be possible to implement the ELIST2 classes as derived |
35 | | classes from ELIST. I haven't done this because: |
36 | | |
37 | | a) I think it would be harder to understand the code |
38 | | (Though the problem with not inheriting is that changes to ELIST must be |
39 | | reflected in ELIST2 and vice versa) |
40 | | |
41 | | b) Most of the code is inline so: |
42 | | i) The duplication in source does not affect the run time code size - the |
43 | | code is copied inline anyway! |
44 | | |
45 | | ii) The compiler should have a bit less work to do! |
46 | | **********************************************************************/ |
47 | | |
48 | | /********************************************************************** |
49 | | * CLASS - ELIST2 |
50 | | * |
51 | | * Generic list class for doubly linked lists with embedded links |
52 | | **********************************************************************/ |
53 | | |
54 | | template <typename T> |
55 | | class IntrusiveList { |
56 | | public: |
57 | | /********************************************************************** |
58 | | * CLASS - Link |
59 | | * |
60 | | * Generic link class for doubly linked lists with embedded links |
61 | | * |
62 | | * Note: No destructor - elements are assumed to be destroyed EITHER after |
63 | | * they have been extracted from a list OR by the ELIST2 destructor which |
64 | | * walks the list. |
65 | | **********************************************************************/ |
66 | | |
67 | | class Link { |
68 | | friend class Iterator; |
69 | | friend class IntrusiveList; |
70 | | |
71 | | T *prev; |
72 | | T *next; |
73 | | |
74 | | public: |
75 | 818k | Link() { // constructor |
76 | 818k | prev = next = nullptr; |
77 | 818k | } tesseract::IntrusiveList<tesseract::WERD>::Link::Link() Line | Count | Source | 75 | 541k | Link() { // constructor | 76 | 541k | prev = next = nullptr; | 77 | 541k | } |
tesseract::IntrusiveList<tesseract::TO_ROW>::Link::Link() Line | Count | Source | 75 | 277k | Link() { // constructor | 76 | 277k | prev = next = nullptr; | 77 | 277k | } |
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Link::Link() Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Link::Link() |
78 | | |
79 | | Link(const Link &) = delete; |
80 | | |
81 | | // The assignment operator is required for WERD. |
82 | 124k | void operator=(const Link &) { |
83 | 124k | prev = next = nullptr; |
84 | 124k | } |
85 | | }; |
86 | | using LINK = Link; // compat |
87 | | |
88 | | /*********************************************************************** |
89 | | * CLASS - ELIST2_ITERATOR |
90 | | * |
91 | | * Generic iterator class for doubly linked lists with embedded |
92 | | *links |
93 | | **********************************************************************/ |
94 | | |
95 | | class Iterator { |
96 | | friend void IntrusiveList::assign_to_sublist(Iterator *, Iterator *); |
97 | | |
98 | | IntrusiveList *list; // List being iterated |
99 | | T *prev; // prev element |
100 | | T *current; // current element |
101 | | T *next; // next element |
102 | | T *cycle_pt; // point we are cycling the list to. |
103 | | bool ex_current_was_last; // current extracted was end of list |
104 | | bool ex_current_was_cycle_pt; // current extracted was cycle point |
105 | | bool started_cycling; // Have we moved off the start? |
106 | | /*********************************************************************** |
107 | | * ELIST2_ITERATOR::extract_sublist() |
108 | | * |
109 | | * This is a private member, used only by IntrusiveList::assign_to_sublist. |
110 | | * Given another iterator for the same list, extract the links from THIS to |
111 | | * OTHER inclusive, link them into a new circular list, and return a |
112 | | * pointer to the last element. |
113 | | * (Can't inline this function because it contains a loop) |
114 | | **********************************************************************/ |
115 | | T *extract_sublist( // from this current... |
116 | | Iterator *other_it) { // to other current |
117 | | #ifndef NDEBUG |
118 | | constexpr ERRCODE BAD_EXTRACTION_PTS("Can't extract sublist from points on different lists"); |
119 | | constexpr ERRCODE DONT_EXTRACT_DELETED("Can't extract a sublist marked by deleted points"); |
120 | | #endif |
121 | | constexpr ERRCODE BAD_SUBLIST("Can't find sublist end point in original list"); |
122 | | |
123 | | Iterator temp_it = *this; |
124 | | T *end_of_new_list; |
125 | | |
126 | | #ifndef NDEBUG |
127 | | if (!other_it) |
128 | | BAD_PARAMETER.error("ELIST2_ITERATOR::extract_sublist", ABORT, "other_it nullptr"); |
129 | | if (!list) |
130 | | NO_LIST.error("ELIST2_ITERATOR::extract_sublist", ABORT); |
131 | | if (list != other_it->list) |
132 | | BAD_EXTRACTION_PTS.error("ELIST2_ITERATOR.extract_sublist", ABORT); |
133 | | if (list->empty()) |
134 | | EMPTY_LIST.error("ELIST2_ITERATOR::extract_sublist", ABORT); |
135 | | |
136 | | if (!current || !other_it->current) |
137 | | DONT_EXTRACT_DELETED.error("ELIST2_ITERATOR.extract_sublist", ABORT); |
138 | | #endif |
139 | | |
140 | | ex_current_was_last = other_it->ex_current_was_last = false; |
141 | | ex_current_was_cycle_pt = false; |
142 | | other_it->ex_current_was_cycle_pt = false; |
143 | | |
144 | | temp_it.mark_cycle_pt(); |
145 | | do { // walk sublist |
146 | | if (temp_it.cycled_list()) { // can't find end pt |
147 | | BAD_SUBLIST.error("ELIST2_ITERATOR.extract_sublist", ABORT); |
148 | | } |
149 | | |
150 | | if (temp_it.at_last()) { |
151 | | list->last = prev; |
152 | | ex_current_was_last = other_it->ex_current_was_last = true; |
153 | | } |
154 | | |
155 | | if (temp_it.current == cycle_pt) { |
156 | | ex_current_was_cycle_pt = true; |
157 | | } |
158 | | |
159 | | if (temp_it.current == other_it->cycle_pt) { |
160 | | other_it->ex_current_was_cycle_pt = true; |
161 | | } |
162 | | |
163 | | temp_it.forward(); |
164 | | } |
165 | | // do INCLUSIVE list |
166 | | while (temp_it.prev != other_it->current); |
167 | | |
168 | | // circularise sublist |
169 | | other_it->current->next = current; |
170 | | // circularise sublist |
171 | | current->prev = other_it->current; |
172 | | end_of_new_list = other_it->current; |
173 | | |
174 | | // sublist = whole list |
175 | | if (prev == other_it->current) { |
176 | | list->last = nullptr; |
177 | | prev = current = next = nullptr; |
178 | | other_it->prev = other_it->current = other_it->next = nullptr; |
179 | | } else { |
180 | | prev->next = other_it->next; |
181 | | other_it->next->prev = prev; |
182 | | |
183 | | current = other_it->current = nullptr; |
184 | | next = other_it->next; |
185 | | other_it->prev = prev; |
186 | | } |
187 | | return end_of_new_list; |
188 | | } // to other current |
189 | | |
190 | | public: |
191 | | /*********************************************************************** |
192 | | * ELIST2_ITERATOR::ELIST2_ITERATOR |
193 | | * |
194 | | * CONSTRUCTOR - set iterator to specified list; |
195 | | **********************************************************************/ |
196 | | Iterator( // constructor |
197 | 2.33M | IntrusiveList *list_to_iterate) { |
198 | 2.33M | set_to_list(list_to_iterate); |
199 | 2.33M | } tesseract::IntrusiveList<tesseract::WERD>::Iterator::Iterator(tesseract::IntrusiveList<tesseract::WERD>*) Line | Count | Source | 197 | 1.58M | IntrusiveList *list_to_iterate) { | 198 | 1.58M | set_to_list(list_to_iterate); | 199 | 1.58M | } |
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::Iterator(tesseract::IntrusiveList<tesseract::TabVector>*) Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::Iterator(tesseract::IntrusiveList<tesseract::ColPartition>*) tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::Iterator(tesseract::IntrusiveList<tesseract::TO_ROW>*) Line | Count | Source | 197 | 747k | IntrusiveList *list_to_iterate) { | 198 | 747k | set_to_list(list_to_iterate); | 199 | 747k | } |
|
200 | | |
201 | | /*********************************************************************** |
202 | | * ELIST2_ITERATOR::set_to_list |
203 | | * |
204 | | * (Re-)initialise the iterator to point to the start of the list_to_iterate |
205 | | * over. |
206 | | **********************************************************************/ |
207 | | |
208 | | void set_to_list( // change list |
209 | 2.54M | IntrusiveList *list_to_iterate) { |
210 | | #ifndef NDEBUG |
211 | | if (!list_to_iterate) { |
212 | | BAD_PARAMETER.error("ELIST2_ITERATOR::set_to_list", ABORT, "list_to_iterate is nullptr"); |
213 | | } |
214 | | #endif |
215 | | |
216 | 2.54M | list = list_to_iterate; |
217 | 2.54M | prev = list->last; |
218 | 2.54M | current = list->First(); |
219 | 2.54M | next = current ? current->next : nullptr; |
220 | 2.54M | cycle_pt = nullptr; // await explicit set |
221 | 2.54M | started_cycling = false; |
222 | 2.54M | ex_current_was_last = false; |
223 | 2.54M | ex_current_was_cycle_pt = false; |
224 | 2.54M | } tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::set_to_list(tesseract::IntrusiveList<tesseract::TO_ROW>*) Line | Count | Source | 209 | 772k | IntrusiveList *list_to_iterate) { | 210 | | #ifndef NDEBUG | 211 | | if (!list_to_iterate) { | 212 | | BAD_PARAMETER.error("ELIST2_ITERATOR::set_to_list", ABORT, "list_to_iterate is nullptr"); | 213 | | } | 214 | | #endif | 215 | | | 216 | 772k | list = list_to_iterate; | 217 | 772k | prev = list->last; | 218 | 772k | current = list->First(); | 219 | 772k | next = current ? current->next : nullptr; | 220 | 772k | cycle_pt = nullptr; // await explicit set | 221 | 772k | started_cycling = false; | 222 | 772k | ex_current_was_last = false; | 223 | 772k | ex_current_was_cycle_pt = false; | 224 | 772k | } |
tesseract::IntrusiveList<tesseract::WERD>::Iterator::set_to_list(tesseract::IntrusiveList<tesseract::WERD>*) Line | Count | Source | 209 | 1.76M | IntrusiveList *list_to_iterate) { | 210 | | #ifndef NDEBUG | 211 | | if (!list_to_iterate) { | 212 | | BAD_PARAMETER.error("ELIST2_ITERATOR::set_to_list", ABORT, "list_to_iterate is nullptr"); | 213 | | } | 214 | | #endif | 215 | | | 216 | 1.76M | list = list_to_iterate; | 217 | 1.76M | prev = list->last; | 218 | 1.76M | current = list->First(); | 219 | 1.76M | next = current ? current->next : nullptr; | 220 | 1.76M | cycle_pt = nullptr; // await explicit set | 221 | 1.76M | started_cycling = false; | 222 | 1.76M | ex_current_was_last = false; | 223 | 1.76M | ex_current_was_cycle_pt = false; | 224 | 1.76M | } |
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::set_to_list(tesseract::IntrusiveList<tesseract::TabVector>*) Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::set_to_list(tesseract::IntrusiveList<tesseract::ColPartition>*) |
225 | | /*********************************************************************** |
226 | | * ELIST2_ITERATOR::add_after_then_move |
227 | | * |
228 | | * Add a new element to the list after the current element and move the |
229 | | * iterator to the new element. |
230 | | **********************************************************************/ |
231 | | void add_after_then_move( // add after current & |
232 | 375k | T *new_element) { |
233 | | #ifndef NDEBUG |
234 | | if (!list) { |
235 | | NO_LIST.error("ELIST2_ITERATOR::add_after_then_move", ABORT); |
236 | | } |
237 | | if (!new_element) { |
238 | | BAD_PARAMETER.error("ELIST2_ITERATOR::add_after_then_move", ABORT, "new_element is nullptr"); |
239 | | } |
240 | | if (new_element->next) { |
241 | | STILL_LINKED.error("ELIST2_ITERATOR::add_after_then_move", ABORT); |
242 | | } |
243 | | #endif |
244 | | |
245 | 375k | if (list->empty()) { |
246 | 198k | new_element->next = new_element; |
247 | 198k | new_element->prev = new_element; |
248 | 198k | list->last = new_element; |
249 | 198k | prev = next = new_element; |
250 | 198k | } else { |
251 | 176k | new_element->next = next; |
252 | 176k | next->prev = new_element; |
253 | | |
254 | 176k | if (current) { // not extracted |
255 | 176k | new_element->prev = current; |
256 | 176k | current->next = new_element; |
257 | 176k | prev = current; |
258 | 176k | if (current == list->last) { |
259 | 148k | list->last = new_element; |
260 | 148k | } |
261 | 176k | } else { // current extracted |
262 | 0 | new_element->prev = prev; |
263 | 0 | prev->next = new_element; |
264 | 0 | if (ex_current_was_last) { |
265 | 0 | list->last = new_element; |
266 | 0 | } |
267 | 0 | if (ex_current_was_cycle_pt) { |
268 | 0 | cycle_pt = new_element; |
269 | 0 | } |
270 | 0 | } |
271 | 176k | } |
272 | 375k | current = new_element; |
273 | 375k | } // move to new tesseract::IntrusiveList<tesseract::WERD>::Iterator::add_after_then_move(tesseract::WERD*) Line | Count | Source | 232 | 287k | T *new_element) { | 233 | | #ifndef NDEBUG | 234 | | if (!list) { | 235 | | NO_LIST.error("ELIST2_ITERATOR::add_after_then_move", ABORT); | 236 | | } | 237 | | if (!new_element) { | 238 | | BAD_PARAMETER.error("ELIST2_ITERATOR::add_after_then_move", ABORT, "new_element is nullptr"); | 239 | | } | 240 | | if (new_element->next) { | 241 | | STILL_LINKED.error("ELIST2_ITERATOR::add_after_then_move", ABORT); | 242 | | } | 243 | | #endif | 244 | | | 245 | 287k | if (list->empty()) { | 246 | 178k | new_element->next = new_element; | 247 | 178k | new_element->prev = new_element; | 248 | 178k | list->last = new_element; | 249 | 178k | prev = next = new_element; | 250 | 178k | } else { | 251 | 108k | new_element->next = next; | 252 | 108k | next->prev = new_element; | 253 | | | 254 | 108k | if (current) { // not extracted | 255 | 108k | new_element->prev = current; | 256 | 108k | current->next = new_element; | 257 | 108k | prev = current; | 258 | 108k | if (current == list->last) { | 259 | 108k | list->last = new_element; | 260 | 108k | } | 261 | 108k | } else { // current extracted | 262 | 0 | new_element->prev = prev; | 263 | 0 | prev->next = new_element; | 264 | 0 | if (ex_current_was_last) { | 265 | 0 | list->last = new_element; | 266 | 0 | } | 267 | 0 | if (ex_current_was_cycle_pt) { | 268 | 0 | cycle_pt = new_element; | 269 | 0 | } | 270 | 0 | } | 271 | 108k | } | 272 | 287k | current = new_element; | 273 | 287k | } // move to new |
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::add_after_then_move(tesseract::ColPartition*) tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::add_after_then_move(tesseract::TO_ROW*) Line | Count | Source | 232 | 87.5k | T *new_element) { | 233 | | #ifndef NDEBUG | 234 | | if (!list) { | 235 | | NO_LIST.error("ELIST2_ITERATOR::add_after_then_move", ABORT); | 236 | | } | 237 | | if (!new_element) { | 238 | | BAD_PARAMETER.error("ELIST2_ITERATOR::add_after_then_move", ABORT, "new_element is nullptr"); | 239 | | } | 240 | | if (new_element->next) { | 241 | | STILL_LINKED.error("ELIST2_ITERATOR::add_after_then_move", ABORT); | 242 | | } | 243 | | #endif | 244 | | | 245 | 87.5k | if (list->empty()) { | 246 | 19.5k | new_element->next = new_element; | 247 | 19.5k | new_element->prev = new_element; | 248 | 19.5k | list->last = new_element; | 249 | 19.5k | prev = next = new_element; | 250 | 67.9k | } else { | 251 | 67.9k | new_element->next = next; | 252 | 67.9k | next->prev = new_element; | 253 | | | 254 | 67.9k | if (current) { // not extracted | 255 | 67.9k | new_element->prev = current; | 256 | 67.9k | current->next = new_element; | 257 | 67.9k | prev = current; | 258 | 67.9k | if (current == list->last) { | 259 | 40.1k | list->last = new_element; | 260 | 40.1k | } | 261 | 67.9k | } else { // current extracted | 262 | 0 | new_element->prev = prev; | 263 | 0 | prev->next = new_element; | 264 | 0 | if (ex_current_was_last) { | 265 | 0 | list->last = new_element; | 266 | 0 | } | 267 | 0 | if (ex_current_was_cycle_pt) { | 268 | 0 | cycle_pt = new_element; | 269 | 0 | } | 270 | 0 | } | 271 | 67.9k | } | 272 | 87.5k | current = new_element; | 273 | 87.5k | } // move to new |
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::add_after_then_move(tesseract::TabVector*) |
274 | | /*********************************************************************** |
275 | | * ELIST2_ITERATOR::add_after_stay_put |
276 | | * |
277 | | * Add a new element to the list after the current element but do not move |
278 | | * the iterator to the new element. |
279 | | **********************************************************************/ |
280 | | void add_after_stay_put( // add after current & |
281 | 25.3k | T *new_element) { |
282 | | #ifndef NDEBUG |
283 | | if (!list) { |
284 | | NO_LIST.error("ELIST2_ITERATOR::add_after_stay_put", ABORT); |
285 | | } |
286 | | if (!new_element) { |
287 | | BAD_PARAMETER.error("ELIST2_ITERATOR::add_after_stay_put", ABORT, "new_element is nullptr"); |
288 | | } |
289 | | if (new_element->next) { |
290 | | STILL_LINKED.error("ELIST2_ITERATOR::add_after_stay_put", ABORT); |
291 | | } |
292 | | #endif |
293 | | |
294 | 25.3k | if (list->empty()) { |
295 | 25.3k | new_element->next = new_element; |
296 | 25.3k | new_element->prev = new_element; |
297 | 25.3k | list->last = new_element; |
298 | 25.3k | prev = next = new_element; |
299 | 25.3k | ex_current_was_last = false; |
300 | 25.3k | current = nullptr; |
301 | 25.3k | } else { |
302 | 0 | new_element->next = next; |
303 | 0 | next->prev = new_element; |
304 | |
|
305 | 0 | if (current) { // not extracted |
306 | 0 | new_element->prev = current; |
307 | 0 | current->next = new_element; |
308 | 0 | if (prev == current) { |
309 | 0 | prev = new_element; |
310 | 0 | } |
311 | 0 | if (current == list->last) { |
312 | 0 | list->last = new_element; |
313 | 0 | } |
314 | 0 | } else { // current extracted |
315 | 0 | new_element->prev = prev; |
316 | 0 | prev->next = new_element; |
317 | 0 | if (ex_current_was_last) { |
318 | 0 | list->last = new_element; |
319 | 0 | ex_current_was_last = false; |
320 | 0 | } |
321 | 0 | } |
322 | 0 | next = new_element; |
323 | 0 | } |
324 | 25.3k | } // stay at current Unexecuted instantiation: tesseract::IntrusiveList<tesseract::WERD>::Iterator::add_after_stay_put(tesseract::WERD*) Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::add_after_stay_put(tesseract::ColPartition*) Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::add_after_stay_put(tesseract::TabVector*) tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::add_after_stay_put(tesseract::TO_ROW*) Line | Count | Source | 281 | 25.3k | T *new_element) { | 282 | | #ifndef NDEBUG | 283 | | if (!list) { | 284 | | NO_LIST.error("ELIST2_ITERATOR::add_after_stay_put", ABORT); | 285 | | } | 286 | | if (!new_element) { | 287 | | BAD_PARAMETER.error("ELIST2_ITERATOR::add_after_stay_put", ABORT, "new_element is nullptr"); | 288 | | } | 289 | | if (new_element->next) { | 290 | | STILL_LINKED.error("ELIST2_ITERATOR::add_after_stay_put", ABORT); | 291 | | } | 292 | | #endif | 293 | | | 294 | 25.3k | if (list->empty()) { | 295 | 25.3k | new_element->next = new_element; | 296 | 25.3k | new_element->prev = new_element; | 297 | 25.3k | list->last = new_element; | 298 | 25.3k | prev = next = new_element; | 299 | 25.3k | ex_current_was_last = false; | 300 | 25.3k | current = nullptr; | 301 | 25.3k | } else { | 302 | 0 | new_element->next = next; | 303 | 0 | next->prev = new_element; | 304 | |
| 305 | 0 | if (current) { // not extracted | 306 | 0 | new_element->prev = current; | 307 | 0 | current->next = new_element; | 308 | 0 | if (prev == current) { | 309 | 0 | prev = new_element; | 310 | 0 | } | 311 | 0 | if (current == list->last) { | 312 | 0 | list->last = new_element; | 313 | 0 | } | 314 | 0 | } else { // current extracted | 315 | 0 | new_element->prev = prev; | 316 | 0 | prev->next = new_element; | 317 | 0 | if (ex_current_was_last) { | 318 | 0 | list->last = new_element; | 319 | 0 | ex_current_was_last = false; | 320 | 0 | } | 321 | 0 | } | 322 | 0 | next = new_element; | 323 | 0 | } | 324 | 25.3k | } // stay at current |
|
325 | | /*********************************************************************** |
326 | | * ELIST2_ITERATOR::add_before_then_move |
327 | | * |
328 | | * Add a new element to the list before the current element and move the |
329 | | * iterator to the new element. |
330 | | **********************************************************************/ |
331 | | void add_before_then_move( // add before current & |
332 | 189k | T *new_element) { |
333 | | #ifndef NDEBUG |
334 | | if (!list) { |
335 | | NO_LIST.error("ELIST2_ITERATOR::add_before_then_move", ABORT); |
336 | | } |
337 | | if (!new_element) { |
338 | | BAD_PARAMETER.error("ELIST2_ITERATOR::add_before_then_move", ABORT, "new_element is nullptr"); |
339 | | } |
340 | | if (new_element->next) { |
341 | | STILL_LINKED.error("ELIST2_ITERATOR::add_before_then_move", ABORT); |
342 | | } |
343 | | #endif |
344 | | |
345 | 189k | if (list->empty()) { |
346 | 0 | new_element->next = new_element; |
347 | 0 | new_element->prev = new_element; |
348 | 0 | list->last = new_element; |
349 | 0 | prev = next = new_element; |
350 | 189k | } else { |
351 | 189k | prev->next = new_element; |
352 | 189k | new_element->prev = prev; |
353 | | |
354 | 189k | if (current) { // not extracted |
355 | 189k | new_element->next = current; |
356 | 189k | current->prev = new_element; |
357 | 189k | next = current; |
358 | 189k | } else { // current extracted |
359 | 0 | new_element->next = next; |
360 | 0 | next->prev = new_element; |
361 | 0 | if (ex_current_was_last) { |
362 | 0 | list->last = new_element; |
363 | 0 | } |
364 | 0 | if (ex_current_was_cycle_pt) { |
365 | 0 | cycle_pt = new_element; |
366 | 0 | } |
367 | 0 | } |
368 | 189k | } |
369 | 189k | current = new_element; |
370 | 189k | } // move to new Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::add_before_then_move(tesseract::TabVector*) tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::add_before_then_move(tesseract::TO_ROW*) Line | Count | Source | 332 | 189k | T *new_element) { | 333 | | #ifndef NDEBUG | 334 | | if (!list) { | 335 | | NO_LIST.error("ELIST2_ITERATOR::add_before_then_move", ABORT); | 336 | | } | 337 | | if (!new_element) { | 338 | | BAD_PARAMETER.error("ELIST2_ITERATOR::add_before_then_move", ABORT, "new_element is nullptr"); | 339 | | } | 340 | | if (new_element->next) { | 341 | | STILL_LINKED.error("ELIST2_ITERATOR::add_before_then_move", ABORT); | 342 | | } | 343 | | #endif | 344 | | | 345 | 189k | if (list->empty()) { | 346 | 0 | new_element->next = new_element; | 347 | 0 | new_element->prev = new_element; | 348 | 0 | list->last = new_element; | 349 | 0 | prev = next = new_element; | 350 | 189k | } else { | 351 | 189k | prev->next = new_element; | 352 | 189k | new_element->prev = prev; | 353 | | | 354 | 189k | if (current) { // not extracted | 355 | 189k | new_element->next = current; | 356 | 189k | current->prev = new_element; | 357 | 189k | next = current; | 358 | 189k | } else { // current extracted | 359 | 0 | new_element->next = next; | 360 | 0 | next->prev = new_element; | 361 | 0 | if (ex_current_was_last) { | 362 | 0 | list->last = new_element; | 363 | 0 | } | 364 | 0 | if (ex_current_was_cycle_pt) { | 365 | 0 | cycle_pt = new_element; | 366 | 0 | } | 367 | 0 | } | 368 | 189k | } | 369 | 189k | current = new_element; | 370 | 189k | } // move to new |
|
371 | | /*********************************************************************** |
372 | | * ELIST2_ITERATOR::add_before_stay_put |
373 | | * |
374 | | * Add a new element to the list before the current element but don't move the |
375 | | * iterator to the new element. |
376 | | **********************************************************************/ |
377 | | void add_before_stay_put( // add before current & |
378 | 308k | T *new_element) { |
379 | | #ifndef NDEBUG |
380 | | if (!list) { |
381 | | NO_LIST.error("ELIST2_ITERATOR::add_before_stay_put", ABORT); |
382 | | } |
383 | | if (!new_element) { |
384 | | BAD_PARAMETER.error("ELIST2_ITERATOR::add_before_stay_put", ABORT, "new_element is nullptr"); |
385 | | } |
386 | | if (new_element->next) { |
387 | | STILL_LINKED.error("ELIST2_ITERATOR::add_before_stay_put", ABORT); |
388 | | } |
389 | | #endif |
390 | | |
391 | 308k | if (list->empty()) { |
392 | 0 | new_element->next = new_element; |
393 | 0 | new_element->prev = new_element; |
394 | 0 | list->last = new_element; |
395 | 0 | prev = next = new_element; |
396 | 0 | ex_current_was_last = true; |
397 | 0 | current = nullptr; |
398 | 308k | } else { |
399 | 308k | prev->next = new_element; |
400 | 308k | new_element->prev = prev; |
401 | | |
402 | 308k | if (current) { // not extracted |
403 | 14.4k | new_element->next = current; |
404 | 14.4k | current->prev = new_element; |
405 | 14.4k | if (next == current) { |
406 | 0 | next = new_element; |
407 | 0 | } |
408 | 294k | } else { // current extracted |
409 | 294k | new_element->next = next; |
410 | 294k | next->prev = new_element; |
411 | 294k | if (ex_current_was_last) { |
412 | 0 | list->last = new_element; |
413 | 0 | } |
414 | 294k | } |
415 | 308k | prev = new_element; |
416 | 308k | } |
417 | 308k | } // stay at current tesseract::IntrusiveList<tesseract::WERD>::Iterator::add_before_stay_put(tesseract::WERD*) Line | Count | Source | 378 | 14.4k | T *new_element) { | 379 | | #ifndef NDEBUG | 380 | | if (!list) { | 381 | | NO_LIST.error("ELIST2_ITERATOR::add_before_stay_put", ABORT); | 382 | | } | 383 | | if (!new_element) { | 384 | | BAD_PARAMETER.error("ELIST2_ITERATOR::add_before_stay_put", ABORT, "new_element is nullptr"); | 385 | | } | 386 | | if (new_element->next) { | 387 | | STILL_LINKED.error("ELIST2_ITERATOR::add_before_stay_put", ABORT); | 388 | | } | 389 | | #endif | 390 | | | 391 | 14.4k | if (list->empty()) { | 392 | 0 | new_element->next = new_element; | 393 | 0 | new_element->prev = new_element; | 394 | 0 | list->last = new_element; | 395 | 0 | prev = next = new_element; | 396 | 0 | ex_current_was_last = true; | 397 | 0 | current = nullptr; | 398 | 14.4k | } else { | 399 | 14.4k | prev->next = new_element; | 400 | 14.4k | new_element->prev = prev; | 401 | | | 402 | 14.4k | if (current) { // not extracted | 403 | 14.4k | new_element->next = current; | 404 | 14.4k | current->prev = new_element; | 405 | 14.4k | if (next == current) { | 406 | 0 | next = new_element; | 407 | 0 | } | 408 | 14.4k | } else { // current extracted | 409 | 0 | new_element->next = next; | 410 | 0 | next->prev = new_element; | 411 | 0 | if (ex_current_was_last) { | 412 | 0 | list->last = new_element; | 413 | 0 | } | 414 | 0 | } | 415 | 14.4k | prev = new_element; | 416 | 14.4k | } | 417 | 14.4k | } // stay at current |
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::add_before_stay_put(tesseract::ColPartition*) Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::add_before_stay_put(tesseract::TabVector*) tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::add_before_stay_put(tesseract::TO_ROW*) Line | Count | Source | 378 | 294k | T *new_element) { | 379 | | #ifndef NDEBUG | 380 | | if (!list) { | 381 | | NO_LIST.error("ELIST2_ITERATOR::add_before_stay_put", ABORT); | 382 | | } | 383 | | if (!new_element) { | 384 | | BAD_PARAMETER.error("ELIST2_ITERATOR::add_before_stay_put", ABORT, "new_element is nullptr"); | 385 | | } | 386 | | if (new_element->next) { | 387 | | STILL_LINKED.error("ELIST2_ITERATOR::add_before_stay_put", ABORT); | 388 | | } | 389 | | #endif | 390 | | | 391 | 294k | if (list->empty()) { | 392 | 0 | new_element->next = new_element; | 393 | 0 | new_element->prev = new_element; | 394 | 0 | list->last = new_element; | 395 | 0 | prev = next = new_element; | 396 | 0 | ex_current_was_last = true; | 397 | 0 | current = nullptr; | 398 | 294k | } else { | 399 | 294k | prev->next = new_element; | 400 | 294k | new_element->prev = prev; | 401 | | | 402 | 294k | if (current) { // not extracted | 403 | 0 | new_element->next = current; | 404 | 0 | current->prev = new_element; | 405 | 0 | if (next == current) { | 406 | 0 | next = new_element; | 407 | 0 | } | 408 | 294k | } else { // current extracted | 409 | 294k | new_element->next = next; | 410 | 294k | next->prev = new_element; | 411 | 294k | if (ex_current_was_last) { | 412 | 0 | list->last = new_element; | 413 | 0 | } | 414 | 294k | } | 415 | 294k | prev = new_element; | 416 | 294k | } | 417 | 294k | } // stay at current |
|
418 | | /*********************************************************************** |
419 | | * ELIST2_ITERATOR::add_list_after |
420 | | * |
421 | | * Insert another list to this list after the current element but don't move |
422 | | *the |
423 | | * iterator. |
424 | | **********************************************************************/ |
425 | | void add_list_after( // add a list & |
426 | 178k | IntrusiveList *list_to_add) { |
427 | | #ifndef NDEBUG |
428 | | if (!list) { |
429 | | NO_LIST.error("ELIST2_ITERATOR::add_list_after", ABORT); |
430 | | } |
431 | | if (!list_to_add) { |
432 | | BAD_PARAMETER.error("ELIST2_ITERATOR::add_list_after", ABORT, "list_to_add is nullptr"); |
433 | | } |
434 | | #endif |
435 | | |
436 | 178k | if (!list_to_add->empty()) { |
437 | 178k | if (list->empty()) { |
438 | 178k | list->last = list_to_add->last; |
439 | 178k | prev = list->last; |
440 | 178k | next = list->First(); |
441 | 178k | ex_current_was_last = true; |
442 | 178k | current = nullptr; |
443 | 178k | } else { |
444 | 0 | if (current) { // not extracted |
445 | 0 | current->next = list_to_add->First(); |
446 | 0 | current->next->prev = current; |
447 | 0 | if (current == list->last) { |
448 | 0 | list->last = list_to_add->last; |
449 | 0 | } |
450 | 0 | list_to_add->last->next = next; |
451 | 0 | next->prev = list_to_add->last; |
452 | 0 | next = current->next; |
453 | 0 | } else { // current extracted |
454 | 0 | prev->next = list_to_add->First(); |
455 | 0 | prev->next->prev = prev; |
456 | 0 | if (ex_current_was_last) { |
457 | 0 | list->last = list_to_add->last; |
458 | 0 | ex_current_was_last = false; |
459 | 0 | } |
460 | 0 | list_to_add->last->next = next; |
461 | 0 | next->prev = list_to_add->last; |
462 | 0 | next = prev->next; |
463 | 0 | } |
464 | 0 | } |
465 | 178k | list_to_add->last = nullptr; |
466 | 178k | } |
467 | 178k | } // stay at current tesseract::IntrusiveList<tesseract::WERD>::Iterator::add_list_after(tesseract::IntrusiveList<tesseract::WERD>*) Line | Count | Source | 426 | 178k | IntrusiveList *list_to_add) { | 427 | | #ifndef NDEBUG | 428 | | if (!list) { | 429 | | NO_LIST.error("ELIST2_ITERATOR::add_list_after", ABORT); | 430 | | } | 431 | | if (!list_to_add) { | 432 | | BAD_PARAMETER.error("ELIST2_ITERATOR::add_list_after", ABORT, "list_to_add is nullptr"); | 433 | | } | 434 | | #endif | 435 | | | 436 | 178k | if (!list_to_add->empty()) { | 437 | 178k | if (list->empty()) { | 438 | 178k | list->last = list_to_add->last; | 439 | 178k | prev = list->last; | 440 | 178k | next = list->First(); | 441 | 178k | ex_current_was_last = true; | 442 | 178k | current = nullptr; | 443 | 178k | } else { | 444 | 0 | if (current) { // not extracted | 445 | 0 | current->next = list_to_add->First(); | 446 | 0 | current->next->prev = current; | 447 | 0 | if (current == list->last) { | 448 | 0 | list->last = list_to_add->last; | 449 | 0 | } | 450 | 0 | list_to_add->last->next = next; | 451 | 0 | next->prev = list_to_add->last; | 452 | 0 | next = current->next; | 453 | 0 | } else { // current extracted | 454 | 0 | prev->next = list_to_add->First(); | 455 | 0 | prev->next->prev = prev; | 456 | 0 | if (ex_current_was_last) { | 457 | 0 | list->last = list_to_add->last; | 458 | 0 | ex_current_was_last = false; | 459 | 0 | } | 460 | 0 | list_to_add->last->next = next; | 461 | 0 | next->prev = list_to_add->last; | 462 | 0 | next = prev->next; | 463 | 0 | } | 464 | 0 | } | 465 | 178k | list_to_add->last = nullptr; | 466 | 178k | } | 467 | 178k | } // stay at current |
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::add_list_after(tesseract::IntrusiveList<tesseract::TabVector>*) Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::add_list_after(tesseract::IntrusiveList<tesseract::ColPartition>*) |
468 | | /*********************************************************************** |
469 | | * ELIST2_ITERATOR::add_list_before |
470 | | * |
471 | | * Insert another list to this list before the current element. Move the |
472 | | * iterator to the start of the inserted elements |
473 | | * iterator. |
474 | | **********************************************************************/ |
475 | | void add_list_before( // add a list & |
476 | | IntrusiveList *list_to_add) { |
477 | | #ifndef NDEBUG |
478 | | if (!list) { |
479 | | NO_LIST.error("ELIST2_ITERATOR::add_list_before", ABORT); |
480 | | } |
481 | | if (!list_to_add) { |
482 | | BAD_PARAMETER.error("ELIST2_ITERATOR::add_list_before", ABORT, "list_to_add is nullptr"); |
483 | | } |
484 | | #endif |
485 | | |
486 | | if (!list_to_add->empty()) { |
487 | | if (list->empty()) { |
488 | | list->last = list_to_add->last; |
489 | | prev = list->last; |
490 | | current = list->First(); |
491 | | next = current->next; |
492 | | ex_current_was_last = false; |
493 | | } else { |
494 | | prev->next = list_to_add->First(); |
495 | | prev->next->prev = prev; |
496 | | |
497 | | if (current) { // not extracted |
498 | | list_to_add->last->next = current; |
499 | | current->prev = list_to_add->last; |
500 | | } else { // current extracted |
501 | | list_to_add->last->next = next; |
502 | | next->prev = list_to_add->last; |
503 | | if (ex_current_was_last) { |
504 | | list->last = list_to_add->last; |
505 | | } |
506 | | if (ex_current_was_cycle_pt) { |
507 | | cycle_pt = prev->next; |
508 | | } |
509 | | } |
510 | | current = prev->next; |
511 | | next = current->next; |
512 | | } |
513 | | list_to_add->last = nullptr; |
514 | | } |
515 | | } // move to it 1st item |
516 | | |
517 | 124M | T *data() { // get current data |
518 | | #ifndef NDEBUG |
519 | | if (!current) { |
520 | | NULL_DATA.error("ELIST2_ITERATOR::data", ABORT); |
521 | | } |
522 | | if (!list) { |
523 | | NO_LIST.error("ELIST2_ITERATOR::data", ABORT); |
524 | | } |
525 | | #endif |
526 | 124M | return current; |
527 | 124M | } tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::data() Line | Count | Source | 517 | 122M | T *data() { // get current data | 518 | | #ifndef NDEBUG | 519 | | if (!current) { | 520 | | NULL_DATA.error("ELIST2_ITERATOR::data", ABORT); | 521 | | } | 522 | | if (!list) { | 523 | | NO_LIST.error("ELIST2_ITERATOR::data", ABORT); | 524 | | } | 525 | | #endif | 526 | 122M | return current; | 527 | 122M | } |
tesseract::IntrusiveList<tesseract::WERD>::Iterator::data() Line | Count | Source | 517 | 2.36M | T *data() { // get current data | 518 | | #ifndef NDEBUG | 519 | | if (!current) { | 520 | | NULL_DATA.error("ELIST2_ITERATOR::data", ABORT); | 521 | | } | 522 | | if (!list) { | 523 | | NO_LIST.error("ELIST2_ITERATOR::data", ABORT); | 524 | | } | 525 | | #endif | 526 | 2.36M | return current; | 527 | 2.36M | } |
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::data() Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::data() |
528 | | /*********************************************************************** |
529 | | * ELIST2_ITERATOR::data_relative |
530 | | * |
531 | | * Return the data pointer to the element "offset" elements from current. |
532 | | * (This function can't be INLINEd because it contains a loop) |
533 | | **********************************************************************/ |
534 | | T *data_relative( // get data + or - ... |
535 | 8.65M | int8_t offset) { // offset from current |
536 | 8.65M | T *ptr; |
537 | | |
538 | | #ifndef NDEBUG |
539 | | if (!list) |
540 | | NO_LIST.error("ELIST2_ITERATOR::data_relative", ABORT); |
541 | | if (list->empty()) |
542 | | EMPTY_LIST.error("ELIST2_ITERATOR::data_relative", ABORT); |
543 | | #endif |
544 | | |
545 | 8.65M | if (offset < 0) { |
546 | 8.86M | for (ptr = current ? current : next; offset++ < 0; ptr = ptr->prev) { |
547 | 4.43M | ; |
548 | 4.43M | } |
549 | 4.43M | } else { |
550 | 8.45M | for (ptr = current ? current : prev; offset-- > 0; ptr = ptr->next) { |
551 | 4.22M | ; |
552 | 4.22M | } |
553 | 4.22M | } |
554 | | |
555 | | #ifndef NDEBUG |
556 | | if (!ptr) |
557 | | NULL_DATA.error("ELIST2_ITERATOR::data_relative", ABORT); |
558 | | #endif |
559 | | |
560 | 8.65M | return ptr; |
561 | 8.65M | } // offset from current tesseract::IntrusiveList<tesseract::WERD>::Iterator::data_relative(signed char) Line | Count | Source | 535 | 207k | int8_t offset) { // offset from current | 536 | 207k | T *ptr; | 537 | | | 538 | | #ifndef NDEBUG | 539 | | if (!list) | 540 | | NO_LIST.error("ELIST2_ITERATOR::data_relative", ABORT); | 541 | | if (list->empty()) | 542 | | EMPTY_LIST.error("ELIST2_ITERATOR::data_relative", ABORT); | 543 | | #endif | 544 | | | 545 | 207k | if (offset < 0) { | 546 | 0 | for (ptr = current ? current : next; offset++ < 0; ptr = ptr->prev) { | 547 | 0 | ; | 548 | 0 | } | 549 | 207k | } else { | 550 | 415k | for (ptr = current ? current : prev; offset-- > 0; ptr = ptr->next) { | 551 | 207k | ; | 552 | 207k | } | 553 | 207k | } | 554 | | | 555 | | #ifndef NDEBUG | 556 | | if (!ptr) | 557 | | NULL_DATA.error("ELIST2_ITERATOR::data_relative", ABORT); | 558 | | #endif | 559 | | | 560 | 207k | return ptr; | 561 | 207k | } // offset from current |
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::data_relative(signed char) tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::data_relative(signed char) Line | Count | Source | 535 | 8.45M | int8_t offset) { // offset from current | 536 | 8.45M | T *ptr; | 537 | | | 538 | | #ifndef NDEBUG | 539 | | if (!list) | 540 | | NO_LIST.error("ELIST2_ITERATOR::data_relative", ABORT); | 541 | | if (list->empty()) | 542 | | EMPTY_LIST.error("ELIST2_ITERATOR::data_relative", ABORT); | 543 | | #endif | 544 | | | 545 | 8.45M | if (offset < 0) { | 546 | 8.86M | for (ptr = current ? current : next; offset++ < 0; ptr = ptr->prev) { | 547 | 4.43M | ; | 548 | 4.43M | } | 549 | 4.43M | } else { | 550 | 8.03M | for (ptr = current ? current : prev; offset-- > 0; ptr = ptr->next) { | 551 | 4.02M | ; | 552 | 4.02M | } | 553 | 4.01M | } | 554 | | | 555 | | #ifndef NDEBUG | 556 | | if (!ptr) | 557 | | NULL_DATA.error("ELIST2_ITERATOR::data_relative", ABORT); | 558 | | #endif | 559 | | | 560 | 8.45M | return ptr; | 561 | 8.45M | } // offset from current |
|
562 | | /*********************************************************************** |
563 | | * ELIST2_ITERATOR::forward |
564 | | * |
565 | | * Move the iterator to the next element of the list. |
566 | | * REMEMBER: ALL LISTS ARE CIRCULAR. |
567 | | **********************************************************************/ |
568 | 91.2M | T *forward() { |
569 | | #ifndef NDEBUG |
570 | | if (!list) |
571 | | NO_LIST.error("ELIST2_ITERATOR::forward", ABORT); |
572 | | #endif |
573 | 91.2M | if (list->empty()) { |
574 | 35.2k | return nullptr; |
575 | 35.2k | } |
576 | | |
577 | 91.2M | if (current) { // not removed so |
578 | | // set previous |
579 | 90.8M | prev = current; |
580 | 90.8M | started_cycling = true; |
581 | | // In case next is deleted by another iterator, get it from the current. |
582 | 90.8M | current = current->next; |
583 | 90.8M | } else { |
584 | 389k | if (ex_current_was_cycle_pt) { |
585 | 342k | cycle_pt = next; |
586 | 342k | } |
587 | 389k | current = next; |
588 | 389k | } |
589 | | |
590 | | #ifndef NDEBUG |
591 | | if (!current) |
592 | | NULL_DATA.error("ELIST2_ITERATOR::forward", ABORT); |
593 | | #endif |
594 | | |
595 | 91.2M | next = current->next; |
596 | | |
597 | | #ifndef NDEBUG |
598 | | if (!next) { |
599 | | NULL_NEXT.error("ELIST2_ITERATOR::forward", ABORT, |
600 | | "This is: %p Current is: %p", |
601 | | static_cast<void *>(this), |
602 | | static_cast<void *>(current)); |
603 | | } |
604 | | #endif |
605 | | |
606 | 91.2M | return current; |
607 | 91.2M | } // move to next element tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::forward() Line | Count | Source | 568 | 88.8M | T *forward() { | 569 | | #ifndef NDEBUG | 570 | | if (!list) | 571 | | NO_LIST.error("ELIST2_ITERATOR::forward", ABORT); | 572 | | #endif | 573 | 88.8M | if (list->empty()) { | 574 | 29.8k | return nullptr; | 575 | 29.8k | } | 576 | | | 577 | 88.8M | if (current) { // not removed so | 578 | | // set previous | 579 | 88.4M | prev = current; | 580 | 88.4M | started_cycling = true; | 581 | | // In case next is deleted by another iterator, get it from the current. | 582 | 88.4M | current = current->next; | 583 | 88.4M | } else { | 584 | 387k | if (ex_current_was_cycle_pt) { | 585 | 341k | cycle_pt = next; | 586 | 341k | } | 587 | 387k | current = next; | 588 | 387k | } | 589 | | | 590 | | #ifndef NDEBUG | 591 | | if (!current) | 592 | | NULL_DATA.error("ELIST2_ITERATOR::forward", ABORT); | 593 | | #endif | 594 | | | 595 | 88.8M | next = current->next; | 596 | | | 597 | | #ifndef NDEBUG | 598 | | if (!next) { | 599 | | NULL_NEXT.error("ELIST2_ITERATOR::forward", ABORT, | 600 | | "This is: %p Current is: %p", | 601 | | static_cast<void *>(this), | 602 | | static_cast<void *>(current)); | 603 | | } | 604 | | #endif | 605 | | | 606 | 88.8M | return current; | 607 | 88.8M | } // move to next element |
tesseract::IntrusiveList<tesseract::WERD>::Iterator::forward() Line | Count | Source | 568 | 2.41M | T *forward() { | 569 | | #ifndef NDEBUG | 570 | | if (!list) | 571 | | NO_LIST.error("ELIST2_ITERATOR::forward", ABORT); | 572 | | #endif | 573 | 2.41M | if (list->empty()) { | 574 | 5.42k | return nullptr; | 575 | 5.42k | } | 576 | | | 577 | 2.41M | if (current) { // not removed so | 578 | | // set previous | 579 | 2.40M | prev = current; | 580 | 2.40M | started_cycling = true; | 581 | | // In case next is deleted by another iterator, get it from the current. | 582 | 2.40M | current = current->next; | 583 | 2.40M | } else { | 584 | 1.55k | if (ex_current_was_cycle_pt) { | 585 | 603 | cycle_pt = next; | 586 | 603 | } | 587 | 1.55k | current = next; | 588 | 1.55k | } | 589 | | | 590 | | #ifndef NDEBUG | 591 | | if (!current) | 592 | | NULL_DATA.error("ELIST2_ITERATOR::forward", ABORT); | 593 | | #endif | 594 | | | 595 | 2.41M | next = current->next; | 596 | | | 597 | | #ifndef NDEBUG | 598 | | if (!next) { | 599 | | NULL_NEXT.error("ELIST2_ITERATOR::forward", ABORT, | 600 | | "This is: %p Current is: %p", | 601 | | static_cast<void *>(this), | 602 | | static_cast<void *>(current)); | 603 | | } | 604 | | #endif | 605 | | | 606 | 2.41M | return current; | 607 | 2.41M | } // move to next element |
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::forward() Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::forward() |
608 | | /*********************************************************************** |
609 | | * ELIST2_ITERATOR::backward |
610 | | * |
611 | | * Move the iterator to the previous element of the list. |
612 | | * REMEMBER: ALL LISTS ARE CIRCULAR. |
613 | | **********************************************************************/ |
614 | 7.07M | T *backward() { |
615 | | #ifndef NDEBUG |
616 | | if (!list) |
617 | | NO_LIST.error("ELIST2_ITERATOR::backward", ABORT); |
618 | | #endif |
619 | 7.07M | if (list->empty()) { |
620 | 0 | return nullptr; |
621 | 0 | } |
622 | | |
623 | 7.07M | if (current) { // not removed so |
624 | | // set previous |
625 | 7.07M | next = current; |
626 | 7.07M | started_cycling = true; |
627 | | // In case prev is deleted by another iterator, get it from current. |
628 | 7.07M | current = current->prev; |
629 | 7.07M | } else { |
630 | 243 | if (ex_current_was_cycle_pt) { |
631 | 0 | cycle_pt = prev; |
632 | 0 | } |
633 | 243 | current = prev; |
634 | 243 | } |
635 | | |
636 | | #ifndef NDEBUG |
637 | | if (!current) |
638 | | NULL_DATA.error("ELIST2_ITERATOR::backward", ABORT); |
639 | | if (!prev) { |
640 | | NULL_PREV.error("ELIST2_ITERATOR::backward", ABORT, |
641 | | "This is: %p Current is: %p", |
642 | | static_cast<void *>(this), |
643 | | static_cast<void *>(current)); |
644 | | } |
645 | | #endif |
646 | | |
647 | 7.07M | prev = current->prev; |
648 | 7.07M | return current; |
649 | 7.07M | } // move to prev element Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::backward() Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::backward() tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::backward() Line | Count | Source | 614 | 7.07M | T *backward() { | 615 | | #ifndef NDEBUG | 616 | | if (!list) | 617 | | NO_LIST.error("ELIST2_ITERATOR::backward", ABORT); | 618 | | #endif | 619 | 7.07M | if (list->empty()) { | 620 | 0 | return nullptr; | 621 | 0 | } | 622 | | | 623 | 7.07M | if (current) { // not removed so | 624 | | // set previous | 625 | 7.07M | next = current; | 626 | 7.07M | started_cycling = true; | 627 | | // In case prev is deleted by another iterator, get it from current. | 628 | 7.07M | current = current->prev; | 629 | 7.07M | } else { | 630 | 243 | if (ex_current_was_cycle_pt) { | 631 | 0 | cycle_pt = prev; | 632 | 0 | } | 633 | 243 | current = prev; | 634 | 243 | } | 635 | | | 636 | | #ifndef NDEBUG | 637 | | if (!current) | 638 | | NULL_DATA.error("ELIST2_ITERATOR::backward", ABORT); | 639 | | if (!prev) { | 640 | | NULL_PREV.error("ELIST2_ITERATOR::backward", ABORT, | 641 | | "This is: %p Current is: %p", | 642 | | static_cast<void *>(this), | 643 | | static_cast<void *>(current)); | 644 | | } | 645 | | #endif | 646 | | | 647 | 7.07M | prev = current->prev; | 648 | 7.07M | return current; | 649 | 7.07M | } // move to prev element |
|
650 | | /*********************************************************************** |
651 | | * ELIST2_ITERATOR::extract |
652 | | * |
653 | | * Do extraction by removing current from the list, returning it to the |
654 | | * caller, but NOT updating the iterator. (So that any calling loop can do |
655 | | * this.) The iterator's current points to nullptr. If the extracted element |
656 | | * is to be deleted, this is the callers responsibility. |
657 | | **********************************************************************/ |
658 | 439k | T *extract() { |
659 | 439k | T *extracted_link; |
660 | | |
661 | | #ifndef NDEBUG |
662 | | if (!list) { |
663 | | NO_LIST.error("ELIST2_ITERATOR::extract", ABORT); |
664 | | } |
665 | | if (!current) { // list empty or |
666 | | // element extracted |
667 | | NULL_CURRENT.error("ELIST2_ITERATOR::extract", ABORT); |
668 | | } |
669 | | #endif |
670 | | |
671 | 439k | if (list->singleton()) { |
672 | | // Special case where we do need to change the iterator. |
673 | 35.2k | prev = next = list->last = nullptr; |
674 | 404k | } else { |
675 | 404k | prev->next = next; // remove from list |
676 | 404k | next->prev = prev; |
677 | | |
678 | 404k | if (current == list->last) { |
679 | 8.42k | list->last = prev; |
680 | 8.42k | ex_current_was_last = true; |
681 | 395k | } else { |
682 | 395k | ex_current_was_last = false; |
683 | 395k | } |
684 | 404k | } |
685 | | // Always set ex_current_was_cycle_pt so an add/forward will work in a loop. |
686 | 439k | ex_current_was_cycle_pt = (current == cycle_pt); |
687 | 439k | extracted_link = current; |
688 | 439k | extracted_link->next = nullptr; // for safety |
689 | 439k | extracted_link->prev = nullptr; // for safety |
690 | 439k | current = nullptr; |
691 | 439k | return extracted_link; |
692 | 439k | } // remove from list tesseract::IntrusiveList<tesseract::WERD>::Iterator::extract() Line | Count | Source | 658 | 21.3k | T *extract() { | 659 | 21.3k | T *extracted_link; | 660 | | | 661 | | #ifndef NDEBUG | 662 | | if (!list) { | 663 | | NO_LIST.error("ELIST2_ITERATOR::extract", ABORT); | 664 | | } | 665 | | if (!current) { // list empty or | 666 | | // element extracted | 667 | | NULL_CURRENT.error("ELIST2_ITERATOR::extract", ABORT); | 668 | | } | 669 | | #endif | 670 | | | 671 | 21.3k | if (list->singleton()) { | 672 | | // Special case where we do need to change the iterator. | 673 | 5.42k | prev = next = list->last = nullptr; | 674 | 15.9k | } else { | 675 | 15.9k | prev->next = next; // remove from list | 676 | 15.9k | next->prev = prev; | 677 | | | 678 | 15.9k | if (current == list->last) { | 679 | 5.92k | list->last = prev; | 680 | 5.92k | ex_current_was_last = true; | 681 | 10.0k | } else { | 682 | 10.0k | ex_current_was_last = false; | 683 | 10.0k | } | 684 | 15.9k | } | 685 | | // Always set ex_current_was_cycle_pt so an add/forward will work in a loop. | 686 | 21.3k | ex_current_was_cycle_pt = (current == cycle_pt); | 687 | 21.3k | extracted_link = current; | 688 | 21.3k | extracted_link->next = nullptr; // for safety | 689 | 21.3k | extracted_link->prev = nullptr; // for safety | 690 | 21.3k | current = nullptr; | 691 | 21.3k | return extracted_link; | 692 | 21.3k | } // remove from list |
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::extract() Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::extract() tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::extract() Line | Count | Source | 658 | 417k | T *extract() { | 659 | 417k | T *extracted_link; | 660 | | | 661 | | #ifndef NDEBUG | 662 | | if (!list) { | 663 | | NO_LIST.error("ELIST2_ITERATOR::extract", ABORT); | 664 | | } | 665 | | if (!current) { // list empty or | 666 | | // element extracted | 667 | | NULL_CURRENT.error("ELIST2_ITERATOR::extract", ABORT); | 668 | | } | 669 | | #endif | 670 | | | 671 | 417k | if (list->singleton()) { | 672 | | // Special case where we do need to change the iterator. | 673 | 29.8k | prev = next = list->last = nullptr; | 674 | 388k | } else { | 675 | 388k | prev->next = next; // remove from list | 676 | 388k | next->prev = prev; | 677 | | | 678 | 388k | if (current == list->last) { | 679 | 2.50k | list->last = prev; | 680 | 2.50k | ex_current_was_last = true; | 681 | 385k | } else { | 682 | 385k | ex_current_was_last = false; | 683 | 385k | } | 684 | 388k | } | 685 | | // Always set ex_current_was_cycle_pt so an add/forward will work in a loop. | 686 | 417k | ex_current_was_cycle_pt = (current == cycle_pt); | 687 | 417k | extracted_link = current; | 688 | 417k | extracted_link->next = nullptr; // for safety | 689 | 417k | extracted_link->prev = nullptr; // for safety | 690 | 417k | current = nullptr; | 691 | 417k | return extracted_link; | 692 | 417k | } // remove from list |
|
693 | | /*********************************************************************** |
694 | | * ELIST2_ITERATOR::move_to_first() |
695 | | * |
696 | | * Move current so that it is set to the start of the list. |
697 | | * Return data just in case anyone wants it. |
698 | | **********************************************************************/ |
699 | | // go to start of list |
700 | 4.98M | T *move_to_first() { |
701 | | #ifndef NDEBUG |
702 | | if (!list) { |
703 | | NO_LIST.error("ELIST2_ITERATOR::move_to_first", ABORT); |
704 | | } |
705 | | #endif |
706 | | |
707 | 4.98M | current = list->First(); |
708 | 4.98M | prev = list->last; |
709 | 4.98M | next = current ? current->next : nullptr; |
710 | 4.98M | return current; |
711 | 4.98M | } Unexecuted instantiation: tesseract::IntrusiveList<tesseract::WERD>::Iterator::move_to_first() Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::move_to_first() Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::move_to_first() tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::move_to_first() Line | Count | Source | 700 | 4.98M | T *move_to_first() { | 701 | | #ifndef NDEBUG | 702 | | if (!list) { | 703 | | NO_LIST.error("ELIST2_ITERATOR::move_to_first", ABORT); | 704 | | } | 705 | | #endif | 706 | | | 707 | 4.98M | current = list->First(); | 708 | 4.98M | prev = list->last; | 709 | 4.98M | next = current ? current->next : nullptr; | 710 | 4.98M | return current; | 711 | 4.98M | } |
|
712 | | /*********************************************************************** |
713 | | * ELIST2_ITERATOR::move_to_last() |
714 | | * |
715 | | * Move current so that it is set to the end of the list. |
716 | | * Return data just in case anyone wants it. |
717 | | **********************************************************************/ |
718 | 20.9k | T *move_to_last() { |
719 | | #ifndef NDEBUG |
720 | | if (!list) { |
721 | | NO_LIST.error("ELIST2_ITERATOR::move_to_last", ABORT); |
722 | | } |
723 | | #endif |
724 | | |
725 | 20.9k | current = list->last; |
726 | 20.9k | prev = current ? current->prev : nullptr; |
727 | 20.9k | next = current ? current->next : nullptr; |
728 | 20.9k | return current; |
729 | 20.9k | } // go to end of list Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::move_to_last() tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::move_to_last() Line | Count | Source | 718 | 20.9k | T *move_to_last() { | 719 | | #ifndef NDEBUG | 720 | | if (!list) { | 721 | | NO_LIST.error("ELIST2_ITERATOR::move_to_last", ABORT); | 722 | | } | 723 | | #endif | 724 | | | 725 | 20.9k | current = list->last; | 726 | 20.9k | prev = current ? current->prev : nullptr; | 727 | 20.9k | next = current ? current->next : nullptr; | 728 | 20.9k | return current; | 729 | 20.9k | } // go to end of list |
|
730 | | /*********************************************************************** |
731 | | * ELIST2_ITERATOR::mark_cycle_pt() |
732 | | * |
733 | | * Remember the current location so that we can tell whether we've returned |
734 | | * to this point later. |
735 | | * |
736 | | * If the current point is deleted either now, or in the future, the cycle |
737 | | * point will be set to the next item which is set to current. This could be |
738 | | * by a forward, add_after_then_move or add_after_then_move. |
739 | | **********************************************************************/ |
740 | 2.18M | void mark_cycle_pt() { |
741 | | #ifndef NDEBUG |
742 | | if (!list) { |
743 | | NO_LIST.error("ELIST2_ITERATOR::mark_cycle_pt", ABORT); |
744 | | } |
745 | | #endif |
746 | | |
747 | 2.18M | if (current) { |
748 | 2.16M | cycle_pt = current; |
749 | 2.16M | } else { |
750 | 26.5k | ex_current_was_cycle_pt = true; |
751 | 26.5k | } |
752 | 2.18M | started_cycling = false; |
753 | 2.18M | } // remember current tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::mark_cycle_pt() Line | Count | Source | 740 | 786k | void mark_cycle_pt() { | 741 | | #ifndef NDEBUG | 742 | | if (!list) { | 743 | | NO_LIST.error("ELIST2_ITERATOR::mark_cycle_pt", ABORT); | 744 | | } | 745 | | #endif | 746 | | | 747 | 786k | if (current) { | 748 | 759k | cycle_pt = current; | 749 | 759k | } else { | 750 | 26.5k | ex_current_was_cycle_pt = true; | 751 | 26.5k | } | 752 | 786k | started_cycling = false; | 753 | 786k | } // remember current |
tesseract::IntrusiveList<tesseract::WERD>::Iterator::mark_cycle_pt() Line | Count | Source | 740 | 1.40M | void mark_cycle_pt() { | 741 | | #ifndef NDEBUG | 742 | | if (!list) { | 743 | | NO_LIST.error("ELIST2_ITERATOR::mark_cycle_pt", ABORT); | 744 | | } | 745 | | #endif | 746 | | | 747 | 1.40M | if (current) { | 748 | 1.40M | cycle_pt = current; | 749 | 1.40M | } else { | 750 | 0 | ex_current_was_cycle_pt = true; | 751 | 0 | } | 752 | 1.40M | started_cycling = false; | 753 | 1.40M | } // remember current |
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::mark_cycle_pt() Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::mark_cycle_pt() |
754 | | |
755 | 5.81M | bool empty() const { // is list empty? |
756 | | #ifndef NDEBUG |
757 | | if (!list) { |
758 | | NO_LIST.error("ELIST2_ITERATOR::empty", ABORT); |
759 | | } |
760 | | #endif |
761 | 5.81M | return list->empty(); |
762 | 5.81M | } tesseract::IntrusiveList<tesseract::WERD>::Iterator::empty() const Line | Count | Source | 755 | 722k | bool empty() const { // is list empty? | 756 | | #ifndef NDEBUG | 757 | | if (!list) { | 758 | | NO_LIST.error("ELIST2_ITERATOR::empty", ABORT); | 759 | | } | 760 | | #endif | 761 | 722k | return list->empty(); | 762 | 722k | } |
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::empty() const Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::empty() const tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::empty() const Line | Count | Source | 755 | 5.09M | bool empty() const { // is list empty? | 756 | | #ifndef NDEBUG | 757 | | if (!list) { | 758 | | NO_LIST.error("ELIST2_ITERATOR::empty", ABORT); | 759 | | } | 760 | | #endif | 761 | 5.09M | return list->empty(); | 762 | 5.09M | } |
|
763 | | |
764 | | bool current_extracted() const { // current extracted? |
765 | | return !current; |
766 | | } |
767 | | /*********************************************************************** |
768 | | * ELIST2_ITERATOR::at_first() |
769 | | * |
770 | | * Are we at the start of the list? |
771 | | * |
772 | | **********************************************************************/ |
773 | 5.36M | bool at_first() const { |
774 | | #ifndef NDEBUG |
775 | | if (!list) { |
776 | | NO_LIST.error("ELIST2_ITERATOR::at_first", ABORT); |
777 | | } |
778 | | #endif |
779 | | |
780 | | // we're at a deleted |
781 | 5.36M | return ((list->empty()) || (current == list->First()) || |
782 | 5.36M | ((current == nullptr) && (prev == list->last) && // NON-last pt between |
783 | 4.57M | !ex_current_was_last)); // first and last |
784 | 5.36M | } // Current is first? tesseract::IntrusiveList<tesseract::WERD>::Iterator::at_first() const Line | Count | Source | 773 | 607k | bool at_first() const { | 774 | | #ifndef NDEBUG | 775 | | if (!list) { | 776 | | NO_LIST.error("ELIST2_ITERATOR::at_first", ABORT); | 777 | | } | 778 | | #endif | 779 | | | 780 | | // we're at a deleted | 781 | 607k | return ((list->empty()) || (current == list->First()) || | 782 | 607k | ((current == nullptr) && (prev == list->last) && // NON-last pt between | 783 | 225k | !ex_current_was_last)); // first and last | 784 | 607k | } // Current is first? |
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::at_first() const Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::at_first() const tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::at_first() const Line | Count | Source | 773 | 4.75M | bool at_first() const { | 774 | | #ifndef NDEBUG | 775 | | if (!list) { | 776 | | NO_LIST.error("ELIST2_ITERATOR::at_first", ABORT); | 777 | | } | 778 | | #endif | 779 | | | 780 | | // we're at a deleted | 781 | 4.75M | return ((list->empty()) || (current == list->First()) || | 782 | 4.75M | ((current == nullptr) && (prev == list->last) && // NON-last pt between | 783 | 4.34M | !ex_current_was_last)); // first and last | 784 | 4.75M | } // Current is first? |
|
785 | | /*********************************************************************** |
786 | | * ELIST2_ITERATOR::at_last() |
787 | | * |
788 | | * Are we at the end of the list? |
789 | | * |
790 | | **********************************************************************/ |
791 | 98.0M | bool at_last() const { |
792 | | #ifndef NDEBUG |
793 | | if (!list) { |
794 | | NO_LIST.error("ELIST2_ITERATOR::at_last", ABORT); |
795 | | } |
796 | | #endif |
797 | | |
798 | | // we're at a deleted |
799 | 98.0M | return ((list->empty()) || (current == list->last) || |
800 | 98.0M | ((current == nullptr) && (prev == list->last) && // last point between |
801 | 96.1M | ex_current_was_last)); // first and last |
802 | 98.0M | } // Current is last? tesseract::IntrusiveList<tesseract::WERD>::Iterator::at_last() const Line | Count | Source | 791 | 294k | bool at_last() const { | 792 | | #ifndef NDEBUG | 793 | | if (!list) { | 794 | | NO_LIST.error("ELIST2_ITERATOR::at_last", ABORT); | 795 | | } | 796 | | #endif | 797 | | | 798 | | // we're at a deleted | 799 | 294k | return ((list->empty()) || (current == list->last) || | 800 | 294k | ((current == nullptr) && (prev == list->last) && // last point between | 801 | 109k | ex_current_was_last)); // first and last | 802 | 294k | } // Current is last? |
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::at_last() const Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::at_last() const tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::at_last() const Line | Count | Source | 791 | 97.7M | bool at_last() const { | 792 | | #ifndef NDEBUG | 793 | | if (!list) { | 794 | | NO_LIST.error("ELIST2_ITERATOR::at_last", ABORT); | 795 | | } | 796 | | #endif | 797 | | | 798 | | // we're at a deleted | 799 | 97.7M | return ((list->empty()) || (current == list->last) || | 800 | 97.7M | ((current == nullptr) && (prev == list->last) && // last point between | 801 | 96.0M | ex_current_was_last)); // first and last | 802 | 97.7M | } // Current is last? |
|
803 | | /*********************************************************************** |
804 | | * ELIST2_ITERATOR::cycled_list() |
805 | | * |
806 | | * Have we returned to the cycle_pt since it was set? |
807 | | * |
808 | | **********************************************************************/ |
809 | 15.1M | bool cycled_list() const { |
810 | | #ifndef NDEBUG |
811 | | if (!list) { |
812 | | NO_LIST.error("ELIST2_ITERATOR::cycled_list", ABORT); |
813 | | } |
814 | | #endif |
815 | | |
816 | 15.1M | return ((list->empty()) || ((current == cycle_pt) && started_cycling)); |
817 | 15.1M | } // Completed a cycle? tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::cycled_list() const Line | Count | Source | 809 | 11.6M | bool cycled_list() const { | 810 | | #ifndef NDEBUG | 811 | | if (!list) { | 812 | | NO_LIST.error("ELIST2_ITERATOR::cycled_list", ABORT); | 813 | | } | 814 | | #endif | 815 | | | 816 | 11.6M | return ((list->empty()) || ((current == cycle_pt) && started_cycling)); | 817 | 11.6M | } // Completed a cycle? |
tesseract::IntrusiveList<tesseract::WERD>::Iterator::cycled_list() const Line | Count | Source | 809 | 3.54M | bool cycled_list() const { | 810 | | #ifndef NDEBUG | 811 | | if (!list) { | 812 | | NO_LIST.error("ELIST2_ITERATOR::cycled_list", ABORT); | 813 | | } | 814 | | #endif | 815 | | | 816 | 3.54M | return ((list->empty()) || ((current == cycle_pt) && started_cycling)); | 817 | 3.54M | } // Completed a cycle? |
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::cycled_list() const Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::cycled_list() const |
818 | | /*********************************************************************** |
819 | | * ELIST2_ITERATOR::add_to_end |
820 | | * |
821 | | * Add a new element to the end of the list without moving the iterator. |
822 | | * This is provided because a single linked list cannot move to the last as |
823 | | * the iterator couldn't set its prev pointer. Adding to the end is |
824 | | * essential for implementing |
825 | | queues. |
826 | | **********************************************************************/ |
827 | | void add_to_end( // add at end & |
828 | 319k | T *new_element) { |
829 | | #ifndef NDEBUG |
830 | | if (!list) { |
831 | | NO_LIST.error("ELIST2_ITERATOR::add_to_end", ABORT); |
832 | | } |
833 | | if (!new_element) { |
834 | | BAD_PARAMETER.error("ELIST2_ITERATOR::add_to_end", ABORT, "new_element is nullptr"); |
835 | | } |
836 | | if (new_element->next) { |
837 | | STILL_LINKED.error("ELIST2_ITERATOR::add_to_end", ABORT); |
838 | | } |
839 | | #endif |
840 | | |
841 | 319k | if (this->at_last()) { |
842 | 25.3k | this->add_after_stay_put(new_element); |
843 | 294k | } else { |
844 | 294k | if (this->at_first()) { |
845 | 294k | this->add_before_stay_put(new_element); |
846 | 294k | list->last = new_element; |
847 | 294k | } else { // Iteratr is elsewhere |
848 | 0 | new_element->next = list->last->next; |
849 | 0 | new_element->prev = list->last; |
850 | 0 | list->last->next->prev = new_element; |
851 | 0 | list->last->next = new_element; |
852 | 0 | list->last = new_element; |
853 | 0 | } |
854 | 294k | } |
855 | 319k | } // don't move Unexecuted instantiation: tesseract::IntrusiveList<tesseract::WERD>::Iterator::add_to_end(tesseract::WERD*) Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::add_to_end(tesseract::ColPartition*) Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::add_to_end(tesseract::TabVector*) tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::add_to_end(tesseract::TO_ROW*) Line | Count | Source | 828 | 319k | T *new_element) { | 829 | | #ifndef NDEBUG | 830 | | if (!list) { | 831 | | NO_LIST.error("ELIST2_ITERATOR::add_to_end", ABORT); | 832 | | } | 833 | | if (!new_element) { | 834 | | BAD_PARAMETER.error("ELIST2_ITERATOR::add_to_end", ABORT, "new_element is nullptr"); | 835 | | } | 836 | | if (new_element->next) { | 837 | | STILL_LINKED.error("ELIST2_ITERATOR::add_to_end", ABORT); | 838 | | } | 839 | | #endif | 840 | | | 841 | 319k | if (this->at_last()) { | 842 | 25.3k | this->add_after_stay_put(new_element); | 843 | 294k | } else { | 844 | 294k | if (this->at_first()) { | 845 | 294k | this->add_before_stay_put(new_element); | 846 | 294k | list->last = new_element; | 847 | 294k | } else { // Iteratr is elsewhere | 848 | 0 | new_element->next = list->last->next; | 849 | 0 | new_element->prev = list->last; | 850 | 0 | list->last->next->prev = new_element; | 851 | 0 | list->last->next = new_element; | 852 | 0 | list->last = new_element; | 853 | 0 | } | 854 | 294k | } | 855 | 319k | } // don't move |
|
856 | | /*********************************************************************** |
857 | | * ELIST2_ITERATOR::exchange() |
858 | | * |
859 | | * Given another iterator, whose current element is a different element on |
860 | | * the same list list OR an element of another list, exchange the two current |
861 | | * elements. On return, each iterator points to the element which was the |
862 | | * other iterators current on entry. |
863 | | * (This function hasn't been in-lined because its a bit big!) |
864 | | **********************************************************************/ |
865 | | void exchange( // positions of 2 links |
866 | | Iterator *other_it) { // other iterator |
867 | | constexpr ERRCODE DONT_EXCHANGE_DELETED("Can't exchange deleted elements of lists"); |
868 | | |
869 | | T *old_current; |
870 | | |
871 | | #ifndef NDEBUG |
872 | | if (!list) |
873 | | NO_LIST.error("ELIST2_ITERATOR::exchange", ABORT); |
874 | | if (!other_it) |
875 | | BAD_PARAMETER.error("ELIST2_ITERATOR::exchange", ABORT, "other_it nullptr"); |
876 | | if (!(other_it->list)) |
877 | | NO_LIST.error("ELIST2_ITERATOR::exchange", ABORT, "other_it"); |
878 | | #endif |
879 | | |
880 | | /* Do nothing if either list is empty or if both iterators reference the same |
881 | | link */ |
882 | | |
883 | | if ((list->empty()) || (other_it->list->empty()) || (current == other_it->current)) { |
884 | | return; |
885 | | } |
886 | | |
887 | | /* Error if either current element is deleted */ |
888 | | |
889 | | if (!current || !other_it->current) { |
890 | | DONT_EXCHANGE_DELETED.error("ELIST2_ITERATOR.exchange", ABORT); |
891 | | } |
892 | | |
893 | | /* Now handle the 4 cases: doubleton list; non-doubleton adjacent elements |
894 | | (other before this); non-doubleton adjacent elements (this before other); |
895 | | non-adjacent elements. */ |
896 | | |
897 | | // adjacent links |
898 | | if ((next == other_it->current) || (other_it->next == current)) { |
899 | | // doubleton list |
900 | | if ((next == other_it->current) && (other_it->next == current)) { |
901 | | prev = next = current; |
902 | | other_it->prev = other_it->next = other_it->current; |
903 | | } else { // non-doubleton with |
904 | | // adjacent links |
905 | | // other before this |
906 | | if (other_it->next == current) { |
907 | | other_it->prev->next = current; |
908 | | other_it->current->next = next; |
909 | | other_it->current->prev = current; |
910 | | current->next = other_it->current; |
911 | | current->prev = other_it->prev; |
912 | | next->prev = other_it->current; |
913 | | |
914 | | other_it->next = other_it->current; |
915 | | prev = current; |
916 | | } else { // this before other |
917 | | prev->next = other_it->current; |
918 | | current->next = other_it->next; |
919 | | current->prev = other_it->current; |
920 | | other_it->current->next = current; |
921 | | other_it->current->prev = prev; |
922 | | other_it->next->prev = current; |
923 | | |
924 | | next = current; |
925 | | other_it->prev = other_it->current; |
926 | | } |
927 | | } |
928 | | } else { // no overlap |
929 | | prev->next = other_it->current; |
930 | | current->next = other_it->next; |
931 | | current->prev = other_it->prev; |
932 | | next->prev = other_it->current; |
933 | | other_it->prev->next = current; |
934 | | other_it->current->next = next; |
935 | | other_it->current->prev = prev; |
936 | | other_it->next->prev = current; |
937 | | } |
938 | | |
939 | | /* update end of list pointer when necessary (remember that the 2 iterators |
940 | | may iterate over different lists!) */ |
941 | | |
942 | | if (list->last == current) { |
943 | | list->last = other_it->current; |
944 | | } |
945 | | if (other_it->list->last == other_it->current) { |
946 | | other_it->list->last = current; |
947 | | } |
948 | | |
949 | | if (current == cycle_pt) { |
950 | | cycle_pt = other_it->cycle_pt; |
951 | | } |
952 | | if (other_it->current == other_it->cycle_pt) { |
953 | | other_it->cycle_pt = cycle_pt; |
954 | | } |
955 | | |
956 | | /* The actual exchange - in all cases*/ |
957 | | |
958 | | old_current = current; |
959 | | current = other_it->current; |
960 | | other_it->current = old_current; |
961 | | } // other iterator |
962 | | |
963 | | //# elements in list |
964 | 242k | int32_t length() const { |
965 | 242k | return list->length(); |
966 | 242k | } Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::length() const tesseract::IntrusiveList<tesseract::WERD>::Iterator::length() const Line | Count | Source | 964 | 142k | int32_t length() const { | 965 | 142k | return list->length(); | 966 | 142k | } |
tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::length() const Line | Count | Source | 964 | 99.8k | int32_t length() const { | 965 | 99.8k | return list->length(); | 966 | 99.8k | } |
|
967 | | /*********************************************************************** |
968 | | * ELIST2_ITERATOR::sort() |
969 | | * |
970 | | * Sort the elements of the list, then reposition at the start. |
971 | | * |
972 | | **********************************************************************/ |
973 | | void sort( // sort elements |
974 | | int comparator( // comparison routine |
975 | 25.9k | const T *, const T *)) { |
976 | | #ifndef NDEBUG |
977 | | if (!list) { |
978 | | NO_LIST.error("ELIST2_ITERATOR::sort", ABORT); |
979 | | } |
980 | | #endif |
981 | | |
982 | 25.9k | list->sort(comparator); |
983 | 25.9k | move_to_first(); |
984 | 25.9k | } Unexecuted instantiation: tesseract::IntrusiveList<tesseract::WERD>::Iterator::sort(int (*)(tesseract::WERD const*, tesseract::WERD const*)) tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::sort(int (*)(tesseract::TO_ROW const*, tesseract::TO_ROW const*)) Line | Count | Source | 975 | 25.9k | const T *, const T *)) { | 976 | | #ifndef NDEBUG | 977 | | if (!list) { | 978 | | NO_LIST.error("ELIST2_ITERATOR::sort", ABORT); | 979 | | } | 980 | | #endif | 981 | | | 982 | 25.9k | list->sort(comparator); | 983 | 25.9k | move_to_first(); | 984 | 25.9k | } |
|
985 | | |
986 | | private: |
987 | | // Don't use the following constructor. |
988 | | Iterator() = delete; |
989 | | }; |
990 | | using ITERATOR = Iterator; // compat |
991 | | |
992 | | private: |
993 | | T *last = nullptr; // End of list |
994 | | //(Points to head) |
995 | 13.0M | T *First() { // return first |
996 | 13.0M | return last ? last->next : nullptr; |
997 | 13.0M | } tesseract::IntrusiveList<tesseract::TO_ROW>::First() Line | Count | Source | 995 | 10.5M | T *First() { // return first | 996 | 10.5M | return last ? last->next : nullptr; | 997 | 10.5M | } |
tesseract::IntrusiveList<tesseract::WERD>::First() Line | Count | Source | 995 | 2.55M | T *First() { // return first | 996 | 2.55M | return last ? last->next : nullptr; | 997 | 2.55M | } |
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::First() Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::First() |
998 | | |
999 | | public: |
1000 | 650k | ~IntrusiveList() { |
1001 | 650k | clear(); |
1002 | 650k | } tesseract::IntrusiveList<tesseract::WERD>::~IntrusiveList() Line | Count | Source | 1000 | 635k | ~IntrusiveList() { | 1001 | 635k | clear(); | 1002 | 635k | } |
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::~IntrusiveList() tesseract::IntrusiveList<tesseract::TO_ROW>::~IntrusiveList() Line | Count | Source | 1000 | 15.4k | ~IntrusiveList() { | 1001 | 15.4k | clear(); | 1002 | 15.4k | } |
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::~IntrusiveList() |
1003 | | |
1004 | | /* delete elements */ |
1005 | 650k | void clear() { |
1006 | 650k | internal_clear(); |
1007 | 650k | } tesseract::IntrusiveList<tesseract::WERD>::clear() Line | Count | Source | 1005 | 635k | void clear() { | 1006 | 635k | internal_clear(); | 1007 | 635k | } |
tesseract::IntrusiveList<tesseract::TO_ROW>::clear() Line | Count | Source | 1005 | 15.4k | void clear() { | 1006 | 15.4k | internal_clear(); | 1007 | 15.4k | } |
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::clear() Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::clear() |
1008 | | |
1009 | | /* Become a deep copy of src_list */ |
1010 | | template <typename U> |
1011 | | void deep_copy(const U *src_list, T *(*copier)(const T *)) { |
1012 | | Iterator from_it(const_cast<U *>(src_list)); |
1013 | | Iterator to_it(this); |
1014 | | |
1015 | | for (from_it.mark_cycle_pt(); !from_it.cycled_list(); from_it.forward()) |
1016 | | to_it.add_after_then_move((*copier)(from_it.data())); |
1017 | | } |
1018 | | |
1019 | | /*********************************************************************** |
1020 | | * IntrusiveList::internal_clear |
1021 | | * |
1022 | | * Used by the destructor and the "clear" member function of derived list |
1023 | | * classes to destroy all the elements on the list. |
1024 | | * The calling function passes a "zapper" function which can be called to |
1025 | | * delete each element of the list, regardless of its derived type. This |
1026 | | * technique permits a generic clear function to destroy elements of |
1027 | | * different derived types correctly, without requiring virtual functions and |
1028 | | * the consequential memory overhead. |
1029 | | **********************************************************************/ |
1030 | | |
1031 | | // destroy all links |
1032 | 650k | void internal_clear() { |
1033 | | // ptr to zapper functn |
1034 | 650k | T *ptr; |
1035 | 650k | T *next; |
1036 | | |
1037 | 650k | if (!empty()) { |
1038 | 188k | ptr = last->next; // set to first |
1039 | 188k | last->next = nullptr; // break circle |
1040 | 188k | last = nullptr; // set list empty |
1041 | 648k | while (ptr) { |
1042 | 459k | next = ptr->next; |
1043 | 459k | delete ptr; |
1044 | 459k | ptr = next; |
1045 | 459k | } |
1046 | 188k | } |
1047 | 650k | } tesseract::IntrusiveList<tesseract::WERD>::internal_clear() Line | Count | Source | 1032 | 635k | void internal_clear() { | 1033 | | // ptr to zapper functn | 1034 | 635k | T *ptr; | 1035 | 635k | T *next; | 1036 | | | 1037 | 635k | if (!empty()) { | 1038 | 173k | ptr = last->next; // set to first | 1039 | 173k | last->next = nullptr; // break circle | 1040 | 173k | last = nullptr; // set list empty | 1041 | 454k | while (ptr) { | 1042 | 280k | next = ptr->next; | 1043 | 280k | delete ptr; | 1044 | 280k | ptr = next; | 1045 | 280k | } | 1046 | 173k | } | 1047 | 635k | } |
tesseract::IntrusiveList<tesseract::TO_ROW>::internal_clear() Line | Count | Source | 1032 | 15.4k | void internal_clear() { | 1033 | | // ptr to zapper functn | 1034 | 15.4k | T *ptr; | 1035 | 15.4k | T *next; | 1036 | | | 1037 | 15.4k | if (!empty()) { | 1038 | 15.0k | ptr = last->next; // set to first | 1039 | 15.0k | last->next = nullptr; // break circle | 1040 | 15.0k | last = nullptr; // set list empty | 1041 | 194k | while (ptr) { | 1042 | 178k | next = ptr->next; | 1043 | 178k | delete ptr; | 1044 | 178k | ptr = next; | 1045 | 178k | } | 1046 | 15.0k | } | 1047 | 15.4k | } |
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::internal_clear() Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::internal_clear() |
1048 | | |
1049 | 225M | bool empty() const { // is list empty? |
1050 | 225M | return !last; |
1051 | 225M | } tesseract::IntrusiveList<tesseract::WERD>::empty() const Line | Count | Source | 1049 | 9.20M | bool empty() const { // is list empty? | 1050 | 9.20M | return !last; | 1051 | 9.20M | } |
tesseract::IntrusiveList<tesseract::TO_ROW>::empty() const Line | Count | Source | 1049 | 215M | bool empty() const { // is list empty? | 1050 | 215M | return !last; | 1051 | 215M | } |
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::empty() const Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::empty() const |
1052 | | |
1053 | 439k | bool singleton() const { |
1054 | 439k | return last ? (last == last->next) : false; |
1055 | 439k | } tesseract::IntrusiveList<tesseract::WERD>::singleton() const Line | Count | Source | 1053 | 21.3k | bool singleton() const { | 1054 | 21.3k | return last ? (last == last->next) : false; | 1055 | 21.3k | } |
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::singleton() const Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::singleton() const tesseract::IntrusiveList<tesseract::TO_ROW>::singleton() const Line | Count | Source | 1053 | 417k | bool singleton() const { | 1054 | 417k | return last ? (last == last->next) : false; | 1055 | 417k | } |
|
1056 | | |
1057 | | void shallow_copy( // dangerous!! |
1058 | | IntrusiveList *from_list) { // beware destructors!! |
1059 | | last = from_list->last; |
1060 | | } |
1061 | | |
1062 | | /*********************************************************************** |
1063 | | * IntrusiveList::assign_to_sublist |
1064 | | * |
1065 | | * The list is set to a sublist of another list. "This" list must be empty |
1066 | | * before this function is invoked. The two iterators passed must refer to |
1067 | | * the same list, different from "this" one. The sublist removed is the |
1068 | | * inclusive list from start_it's current position to end_it's current |
1069 | | * position. If this range passes over the end of the source list then the |
1070 | | * source list has its end set to the previous element of start_it. The |
1071 | | * extracted sublist is unaffected by the end point of the source list, its |
1072 | | * end point is always the end_it position. |
1073 | | **********************************************************************/ |
1074 | | void assign_to_sublist( // to this list |
1075 | | Iterator *start_it, // from list start |
1076 | | Iterator *end_it); // from list end |
1077 | | |
1078 | | // # elements in list |
1079 | 283k | int32_t length() const { |
1080 | 283k | int32_t count = 0; |
1081 | 283k | if (last != nullptr) { |
1082 | 256k | count = 1; |
1083 | 1.59M | for (auto it = last->next; it != last; it = it->next) { |
1084 | 1.33M | count++; |
1085 | 1.33M | } |
1086 | 256k | } |
1087 | 283k | return count; |
1088 | 283k | } Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::length() const tesseract::IntrusiveList<tesseract::WERD>::length() const Line | Count | Source | 1079 | 142k | int32_t length() const { | 1080 | 142k | int32_t count = 0; | 1081 | 142k | if (last != nullptr) { | 1082 | 142k | count = 1; | 1083 | 206k | for (auto it = last->next; it != last; it = it->next) { | 1084 | 64.2k | count++; | 1085 | 64.2k | } | 1086 | 142k | } | 1087 | 142k | return count; | 1088 | 142k | } |
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::length() const tesseract::IntrusiveList<tesseract::TO_ROW>::length() const Line | Count | Source | 1079 | 141k | int32_t length() const { | 1080 | 141k | int32_t count = 0; | 1081 | 141k | if (last != nullptr) { | 1082 | 113k | count = 1; | 1083 | 1.38M | for (auto it = last->next; it != last; it = it->next) { | 1084 | 1.26M | count++; | 1085 | 1.26M | } | 1086 | 113k | } | 1087 | 141k | return count; | 1088 | 141k | } |
|
1089 | | /*********************************************************************** |
1090 | | * IntrusiveList::sort |
1091 | | * |
1092 | | * Sort elements on list |
1093 | | * NB If you don't like the const declarations in the comparator, coerce yours: |
1094 | | * (int (*)(const void *, const void *) |
1095 | | **********************************************************************/ |
1096 | | void sort( // sort elements |
1097 | | int comparator( // comparison routine |
1098 | 25.9k | const T *, const T *)) { |
1099 | | // Allocate an array of pointers, one per list element. |
1100 | 25.9k | auto count = length(); |
1101 | 25.9k | if (count > 0) { |
1102 | | // ptr array to sort |
1103 | 25.3k | std::vector<T *> base; |
1104 | 25.3k | base.reserve(count); |
1105 | | |
1106 | 25.3k | Iterator it(this); |
1107 | | |
1108 | | // Extract all elements, putting the pointers in the array. |
1109 | 344k | for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) { |
1110 | 319k | base.push_back(it.extract()); |
1111 | 319k | } |
1112 | | |
1113 | | // Sort the pointer array. |
1114 | 25.3k | std::sort(base.begin(), base.end(), |
1115 | | // all current comparators return -1,0,1, so we handle this correctly for std::sort |
1116 | 445k | [&](auto &&l, auto &&r) {return comparator(l, r) < 0; }); Unexecuted instantiation: auto tesseract::IntrusiveList<tesseract::WERD>::sort(int (*)(tesseract::WERD const*, tesseract::WERD const*))::{lambda(auto:1&&, auto:2&&)#1}::operator()<tesseract::WERD*&, tesseract::WERD*>(tesseract::WERD*&, tesseract::WERD*&&) const Unexecuted instantiation: auto tesseract::IntrusiveList<tesseract::ColPartition>::sort(int (*)(tesseract::ColPartition const*, tesseract::ColPartition const*))::{lambda(auto:1&&, auto:2&&)#1}::operator()<tesseract::ColPartition*&, tesseract::ColPartition*>(tesseract::ColPartition*&, tesseract::ColPartition*&&) const Unexecuted instantiation: auto tesseract::IntrusiveList<tesseract::TabVector>::sort(int (*)(tesseract::TabVector const*, tesseract::TabVector const*))::{lambda(auto:1&&, auto:2&&)#1}::operator()<tesseract::TabVector*&, tesseract::TabVector*>(tesseract::TabVector*&, tesseract::TabVector*&&) const auto tesseract::IntrusiveList<tesseract::TO_ROW>::sort(int (*)(tesseract::TO_ROW const*, tesseract::TO_ROW const*))::{lambda(auto:1&&, auto:2&&)#1}::operator()<tesseract::TO_ROW*&, tesseract::TO_ROW*>(tesseract::TO_ROW*&, tesseract::TO_ROW*&&) const Line | Count | Source | 1116 | 445k | [&](auto &&l, auto &&r) {return comparator(l, r) < 0; }); |
|
1117 | | |
1118 | | // Rebuild the list from the sorted pointers. |
1119 | 319k | for (auto current : base) { |
1120 | 319k | it.add_to_end(current); |
1121 | 319k | } |
1122 | 25.3k | } |
1123 | 25.9k | } Unexecuted instantiation: tesseract::IntrusiveList<tesseract::WERD>::sort(int (*)(tesseract::WERD const*, tesseract::WERD const*)) Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::sort(int (*)(tesseract::ColPartition const*, tesseract::ColPartition const*)) Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::sort(int (*)(tesseract::TabVector const*, tesseract::TabVector const*)) tesseract::IntrusiveList<tesseract::TO_ROW>::sort(int (*)(tesseract::TO_ROW const*, tesseract::TO_ROW const*)) Line | Count | Source | 1098 | 25.9k | const T *, const T *)) { | 1099 | | // Allocate an array of pointers, one per list element. | 1100 | 25.9k | auto count = length(); | 1101 | 25.9k | if (count > 0) { | 1102 | | // ptr array to sort | 1103 | 25.3k | std::vector<T *> base; | 1104 | 25.3k | base.reserve(count); | 1105 | | | 1106 | 25.3k | Iterator it(this); | 1107 | | | 1108 | | // Extract all elements, putting the pointers in the array. | 1109 | 344k | for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) { | 1110 | 319k | base.push_back(it.extract()); | 1111 | 319k | } | 1112 | | | 1113 | | // Sort the pointer array. | 1114 | 25.3k | std::sort(base.begin(), base.end(), | 1115 | | // all current comparators return -1,0,1, so we handle this correctly for std::sort | 1116 | 25.3k | [&](auto &&l, auto &&r) {return comparator(l, r) < 0; }); | 1117 | | | 1118 | | // Rebuild the list from the sorted pointers. | 1119 | 319k | for (auto current : base) { | 1120 | 319k | it.add_to_end(current); | 1121 | 319k | } | 1122 | 25.3k | } | 1123 | 25.9k | } |
|
1124 | | |
1125 | | // Assuming list has been sorted already, insert new_link to |
1126 | | // keep the list sorted according to the same comparison function. |
1127 | | // Comparison function is the same as used by sort, i.e. uses double |
1128 | | // indirection. Time is O(1) to add to beginning or end. |
1129 | | // Time is linear to add pre-sorted items to an empty list. |
1130 | 0 | void add_sorted(int comparator(const T *, const T *), T *new_link) { |
1131 | | // Check for adding at the end. |
1132 | 0 | if (last == nullptr || comparator(last, new_link) < 0) { |
1133 | 0 | if (last == nullptr) { |
1134 | 0 | new_link->next = new_link; |
1135 | 0 | new_link->prev = new_link; |
1136 | 0 | } else { |
1137 | 0 | new_link->next = last->next; |
1138 | 0 | new_link->prev = last; |
1139 | 0 | last->next = new_link; |
1140 | 0 | new_link->next->prev = new_link; |
1141 | 0 | } |
1142 | 0 | last = new_link; |
1143 | 0 | } else { |
1144 | | // Need to use an iterator. |
1145 | 0 | Iterator it(this); |
1146 | 0 | for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) { |
1147 | 0 | auto link = it.data(); |
1148 | 0 | if (comparator(link, new_link) > 0) { |
1149 | 0 | break; |
1150 | 0 | } |
1151 | 0 | } |
1152 | 0 | if (it.cycled_list()) { |
1153 | 0 | it.add_to_end(new_link); |
1154 | 0 | } else { |
1155 | 0 | it.add_before_then_move(new_link); |
1156 | 0 | } |
1157 | 0 | } |
1158 | 0 | } |
1159 | | }; |
1160 | | |
1161 | | template <typename CLASSNAME> |
1162 | | using ELIST2 = IntrusiveList<CLASSNAME>; |
1163 | | |
1164 | | // add TESS_API? |
1165 | | // move templated lists to public include dirs? |
1166 | | #define ELIST2IZEH(T) \ |
1167 | | class T##_LIST : public IntrusiveList<T> { \ |
1168 | | public: \ |
1169 | | using IntrusiveList<T>::IntrusiveList; \ |
1170 | | }; \ |
1171 | | class T##_IT : public IntrusiveList<T>::Iterator { \ |
1172 | | public: \ |
1173 | | using base = IntrusiveList<T>::Iterator; \ |
1174 | | using base::base; \ |
1175 | | }; |
1176 | | |
1177 | | } // namespace tesseract |
1178 | | |
1179 | | #endif |