tesseract 4.1.1
Loading...
Searching...
No Matches
elst2.cpp
Go to the documentation of this file.
1/**********************************************************************
2 * File: elst2.cpp (Formerly elist2.c)
3 * Description: Doubly linked embedded list code not in the 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#include <cstdlib>
20#include "elst2.h"
21
22/***********************************************************************
23 * MEMBER FUNCTIONS OF CLASS: ELIST2
24 * =================================
25 **********************************************************************/
26
27/***********************************************************************
28 * ELIST2::internal_clear
29 *
30 * Used by the destructor and the "clear" member function of derived list
31 * classes to destroy all the elements on the list.
32 * The calling function passes a "zapper" function which can be called to
33 * delete each element of the list, regardless of its derived type. This
34 * technique permits a generic clear function to destroy elements of
35 * different derived types correctly, without requiring virtual functions and
36 * the consequential memory overhead.
37 **********************************************************************/
38
39void
40ELIST2::internal_clear ( //destroy all links
41void (*zapper) (ELIST2_LINK *)) {
42 //ptr to zapper functn
43 ELIST2_LINK *ptr;
44 ELIST2_LINK *next;
45
46 if (!empty ()) {
47 ptr = last->next; //set to first
48 last->next = nullptr; //break circle
49 last = nullptr; //set list empty
50 while (ptr) {
51 next = ptr->next;
52 zapper(ptr);
53 ptr = next;
54 }
55 }
56}
57
58/***********************************************************************
59 * ELIST2::assign_to_sublist
60 *
61 * The list is set to a sublist of another list. "This" list must be empty
62 * before this function is invoked. The two iterators passed must refer to
63 * the same list, different from "this" one. The sublist removed is the
64 * inclusive list from start_it's current position to end_it's current
65 * position. If this range passes over the end of the source list then the
66 * source list has its end set to the previous element of start_it. The
67 * extracted sublist is unaffected by the end point of the source list, its
68 * end point is always the end_it position.
69 **********************************************************************/
70
71void ELIST2::assign_to_sublist( //to this list
72 ELIST2_ITERATOR *start_it, //from list start
73 ELIST2_ITERATOR *end_it) { //from list end
74 constexpr ERRCODE LIST_NOT_EMPTY(
75 "Destination list must be empty before extracting a sublist");
76
77 if (!empty ())
78 LIST_NOT_EMPTY.error ("ELIST2.assign_to_sublist", ABORT, nullptr);
79
80 last = start_it->extract_sublist (end_it);
81}
82
83/***********************************************************************
84 * ELIST2::length
85 *
86 * Return count of elements on list
87 **********************************************************************/
88
89int32_t ELIST2::length() const { // count elements
90 ELIST2_ITERATOR it(const_cast<ELIST2*>(this));
91 int32_t count = 0;
92
93 for (it.mark_cycle_pt (); !it.cycled_list (); it.forward ())
94 count++;
95 return count;
96}
97
98/***********************************************************************
99 * ELIST2::sort
100 *
101 * Sort elements on list
102 * NB If you don't like the const declarations in the comparator, coerce yours:
103 * (int (*)(const void *, const void *)
104 **********************************************************************/
105
106void
107ELIST2::sort ( //sort elements
108int comparator ( //comparison routine
109const void *, const void *)) {
110 ELIST2_ITERATOR it(this);
111 int32_t count;
112 ELIST2_LINK **base; //ptr array to sort
113 ELIST2_LINK **current;
114 int32_t i;
115
116 /* Allocate an array of pointers, one per list element */
117 count = length ();
118 base = static_cast<ELIST2_LINK **>(malloc (count * sizeof (ELIST2_LINK *)));
119
120 /* Extract all elements, putting the pointers in the array */
121 current = base;
122 for (it.mark_cycle_pt (); !it.cycled_list (); it.forward ()) {
123 *current = it.extract ();
124 current++;
125 }
126
127 /* Sort the pointer array */
128 qsort(base, count, sizeof(*base), comparator);
129
130 /* Rebuild the list from the sorted pointers */
131 current = base;
132 for (i = 0; i < count; i++) {
133 it.add_to_end (*current);
134 current++;
135 }
136 free(base);
137}
138
139// Assuming list has been sorted already, insert new_link to
140// keep the list sorted according to the same comparison function.
141// Comparison function is the same as used by sort, i.e. uses double
142// indirection. Time is O(1) to add to beginning or end.
143// Time is linear to add pre-sorted items to an empty list.
144void ELIST2::add_sorted(int comparator(const void*, const void*),
145 ELIST2_LINK* new_link) {
146 // Check for adding at the end.
147 if (last == nullptr || comparator(&last, &new_link) < 0) {
148 if (last == nullptr) {
149 new_link->next = new_link;
150 new_link->prev = new_link;
151 } else {
152 new_link->next = last->next;
153 new_link->prev = last;
154 last->next = new_link;
155 new_link->next->prev = new_link;
156 }
157 last = new_link;
158 } else {
159 // Need to use an iterator.
160 ELIST2_ITERATOR it(this);
161 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
162 ELIST2_LINK* link = it.data();
163 if (comparator(&link, &new_link) > 0)
164 break;
165 }
166 if (it.cycled_list())
167 it.add_to_end(new_link);
168 else
169 it.add_before_then_move(new_link);
170 }
171}
172
173/***********************************************************************
174 * MEMBER FUNCTIONS OF CLASS: ELIST2_ITERATOR
175 * ==========================================
176 **********************************************************************/
177
178/***********************************************************************
179 * ELIST2_ITERATOR::forward
180 *
181 * Move the iterator to the next element of the list.
182 * REMEMBER: ALL LISTS ARE CIRCULAR.
183 **********************************************************************/
184
186 #ifndef NDEBUG
187 if (!list)
188 NO_LIST.error ("ELIST2_ITERATOR::forward", ABORT, nullptr);
189 #endif
190 if (list->empty ())
191 return nullptr;
192
193 if (current) { //not removed so
194 //set previous
195 prev = current;
196 started_cycling = true;
197 // In case next is deleted by another iterator, get it from the current.
198 current = current->next;
199 }
200 else {
201 if (ex_current_was_cycle_pt)
202 cycle_pt = next;
203 current = next;
204 }
205
206#ifndef NDEBUG
207 if (!current)
208 NULL_DATA.error ("ELIST2_ITERATOR::forward", ABORT, nullptr);
209#endif
210
211 next = current->next;
212
213#ifndef NDEBUG
214 if (!next)
215 NULL_NEXT.error ("ELIST2_ITERATOR::forward", ABORT,
216 "This is: %p Current is: %p", this, current);
217#endif
218
219 return current;
220}
221
222/***********************************************************************
223 * ELIST2_ITERATOR::backward
224 *
225 * Move the iterator to the previous element of the list.
226 * REMEMBER: ALL LISTS ARE CIRCULAR.
227 **********************************************************************/
228
230 #ifndef NDEBUG
231 if (!list)
232 NO_LIST.error ("ELIST2_ITERATOR::backward", ABORT, nullptr);
233 #endif
234 if (list->empty ())
235 return nullptr;
236
237 if (current) { //not removed so
238 //set previous
239 next = current;
240 started_cycling = true;
241 // In case prev is deleted by another iterator, get it from current.
242 current = current->prev;
243 } else {
244 if (ex_current_was_cycle_pt)
245 cycle_pt = prev;
246 current = prev;
247 }
248
249 #ifndef NDEBUG
250 if (!current)
251 NULL_DATA.error ("ELIST2_ITERATOR::backward", ABORT, nullptr);
252 if (!prev)
253 NULL_PREV.error ("ELIST2_ITERATOR::backward", ABORT,
254 "This is: %p Current is: %p", this, current);
255 #endif
256
257 prev = current->prev;
258 return current;
259}
260
261/***********************************************************************
262 * ELIST2_ITERATOR::data_relative
263 *
264 * Return the data pointer to the element "offset" elements from current.
265 * (This function can't be INLINEd because it contains a loop)
266 **********************************************************************/
267
269 int8_t offset) { //offset from current
270 ELIST2_LINK *ptr;
271
272 #ifndef NDEBUG
273 if (!list)
274 NO_LIST.error ("ELIST2_ITERATOR::data_relative", ABORT, nullptr);
275 if (list->empty ())
276 EMPTY_LIST.error ("ELIST2_ITERATOR::data_relative", ABORT, nullptr);
277 #endif
278
279 if (offset < 0)
280 for (ptr = current ? current : next; offset++ < 0; ptr = ptr->prev);
281 else
282 for (ptr = current ? current : prev; offset-- > 0; ptr = ptr->next);
283
284 #ifndef NDEBUG
285 if (!ptr)
286 NULL_DATA.error ("ELIST2_ITERATOR::data_relative", ABORT, nullptr);
287 #endif
288
289 return ptr;
290}
291
292/***********************************************************************
293 * ELIST2_ITERATOR::exchange()
294 *
295 * Given another iterator, whose current element is a different element on
296 * the same list list OR an element of another list, exchange the two current
297 * elements. On return, each iterator points to the element which was the
298 * other iterators current on entry.
299 * (This function hasn't been in-lined because its a bit big!)
300 **********************************************************************/
301
302void ELIST2_ITERATOR::exchange( //positions of 2 links
303 ELIST2_ITERATOR *other_it) { //other iterator
304 constexpr ERRCODE DONT_EXCHANGE_DELETED(
305 "Can't exchange deleted elements of lists");
306
307 ELIST2_LINK *old_current;
308
309 #ifndef NDEBUG
310 if (!list)
311 NO_LIST.error ("ELIST2_ITERATOR::exchange", ABORT, nullptr);
312 if (!other_it)
313 BAD_PARAMETER.error ("ELIST2_ITERATOR::exchange", ABORT, "other_it nullptr");
314 if (!(other_it->list))
315 NO_LIST.error ("ELIST2_ITERATOR::exchange", ABORT, "other_it");
316 #endif
317
318 /* Do nothing if either list is empty or if both iterators reference the same
319 link */
320
321 if ((list->empty ()) ||
322 (other_it->list->empty ()) || (current == other_it->current))
323 return;
324
325 /* Error if either current element is deleted */
326
327 if (!current || !other_it->current)
328 DONT_EXCHANGE_DELETED.error ("ELIST2_ITERATOR.exchange", ABORT, nullptr);
329
330 /* Now handle the 4 cases: doubleton list; non-doubleton adjacent elements
331 (other before this); non-doubleton adjacent elements (this before other);
332 non-adjacent elements. */
333
334 //adjacent links
335 if ((next == other_it->current) ||
336 (other_it->next == current)) {
337 //doubleton list
338 if ((next == other_it->current) &&
339 (other_it->next == current)) {
340 prev = next = current;
341 other_it->prev = other_it->next = other_it->current;
342 }
343 else { //non-doubleton with
344 //adjacent links
345 //other before this
346 if (other_it->next == current) {
347 other_it->prev->next = current;
348 other_it->current->next = next;
349 other_it->current->prev = current;
350 current->next = other_it->current;
351 current->prev = other_it->prev;
352 next->prev = other_it->current;
353
354 other_it->next = other_it->current;
355 prev = current;
356 }
357 else { //this before other
358 prev->next = other_it->current;
359 current->next = other_it->next;
360 current->prev = other_it->current;
361 other_it->current->next = current;
362 other_it->current->prev = prev;
363 other_it->next->prev = current;
364
365 next = current;
366 other_it->prev = other_it->current;
367 }
368 }
369 }
370 else { //no overlap
371 prev->next = other_it->current;
372 current->next = other_it->next;
373 current->prev = other_it->prev;
374 next->prev = other_it->current;
375 other_it->prev->next = current;
376 other_it->current->next = next;
377 other_it->current->prev = prev;
378 other_it->next->prev = current;
379 }
380
381 /* update end of list pointer when necessary (remember that the 2 iterators
382 may iterate over different lists!) */
383
384 if (list->last == current)
385 list->last = other_it->current;
386 if (other_it->list->last == other_it->current)
387 other_it->list->last = current;
388
389 if (current == cycle_pt)
390 cycle_pt = other_it->cycle_pt;
391 if (other_it->current == other_it->cycle_pt)
392 other_it->cycle_pt = cycle_pt;
393
394 /* The actual exchange - in all cases*/
395
396 old_current = current;
397 current = other_it->current;
398 other_it->current = old_current;
399}
400
401/***********************************************************************
402 * ELIST2_ITERATOR::extract_sublist()
403 *
404 * This is a private member, used only by ELIST2::assign_to_sublist.
405 * Given another iterator for the same list, extract the links from THIS to
406 * OTHER inclusive, link them into a new circular list, and return a
407 * pointer to the last element.
408 * (Can't inline this function because it contains a loop)
409 **********************************************************************/
410
411ELIST2_LINK *ELIST2_ITERATOR::extract_sublist( //from this current
412 ELIST2_ITERATOR *other_it) { //to other current
413 #ifndef NDEBUG
414 constexpr ERRCODE BAD_EXTRACTION_PTS(
415 "Can't extract sublist from points on different lists");
416 constexpr ERRCODE DONT_EXTRACT_DELETED(
417 "Can't extract a sublist marked by deleted points");
418 #endif
419 constexpr ERRCODE BAD_SUBLIST("Can't find sublist end point in original list");
420
421 ELIST2_ITERATOR temp_it = *this;
422 ELIST2_LINK *end_of_new_list;
423
424 #ifndef NDEBUG
425 if (!other_it)
426 BAD_PARAMETER.error ("ELIST2_ITERATOR::extract_sublist", ABORT,
427 "other_it nullptr");
428 if (!list)
429 NO_LIST.error ("ELIST2_ITERATOR::extract_sublist", ABORT, nullptr);
430 if (list != other_it->list)
431 BAD_EXTRACTION_PTS.error ("ELIST2_ITERATOR.extract_sublist", ABORT, nullptr);
432 if (list->empty ())
433 EMPTY_LIST.error ("ELIST2_ITERATOR::extract_sublist", ABORT, nullptr);
434
435 if (!current || !other_it->current)
436 DONT_EXTRACT_DELETED.error ("ELIST2_ITERATOR.extract_sublist", ABORT,
437 nullptr);
438 #endif
439
440 ex_current_was_last = other_it->ex_current_was_last = false;
441 ex_current_was_cycle_pt = false;
442 other_it->ex_current_was_cycle_pt = false;
443
444 temp_it.mark_cycle_pt ();
445 do { //walk sublist
446 if (temp_it.cycled_list()) // can't find end pt
447 BAD_SUBLIST.error ("ELIST2_ITERATOR.extract_sublist", ABORT, nullptr);
448
449 if (temp_it.at_last ()) {
450 list->last = prev;
451 ex_current_was_last = other_it->ex_current_was_last = true;
452 }
453
454 if (temp_it.current == cycle_pt)
455 ex_current_was_cycle_pt = true;
456
457 if (temp_it.current == other_it->cycle_pt)
458 other_it->ex_current_was_cycle_pt = true;
459
460 temp_it.forward ();
461 }
462 //do INCLUSIVE list
463 while (temp_it.prev != other_it->current);
464
465 //circularise sublist
466 other_it->current->next = current;
467 //circularise sublist
468 current->prev = other_it->current;
469 end_of_new_list = other_it->current;
470
471 //sublist = whole list
472 if (prev == other_it->current) {
473 list->last = nullptr;
474 prev = current = next = nullptr;
475 other_it->prev = other_it->current = other_it->next = nullptr;
476 }
477 else {
478 prev->next = other_it->next;
479 other_it->next->prev = prev;
480
481 current = other_it->current = nullptr;
482 next = other_it->next;
483 other_it->prev = prev;
484 }
485 return end_of_new_list;
486}
@ ABORT
Definition: errcode.h:29
constexpr ERRCODE NULL_DATA("List would have returned a nullptr data pointer")
constexpr ERRCODE BAD_PARAMETER("List parameter error")
constexpr ERRCODE NULL_NEXT("Next element on the list is nullptr")
constexpr ERRCODE NO_LIST("Iterator not set to a list")
constexpr ERRCODE EMPTY_LIST("List is empty")
constexpr ERRCODE NULL_PREV("Previous element on the list is nullptr")
int count(LIST var_list)
Definition: oldlist.cpp:95
Definition: elst2.h:87
void internal_clear(void(*zapper)(ELIST2_LINK *))
Definition: elst2.cpp:40
bool empty() const
Definition: elst2.h:105
int32_t length() const
Definition: elst2.cpp:89
void add_sorted(int comparator(const void *, const void *), ELIST2_LINK *new_link)
Definition: elst2.cpp:144
void sort(int comparator(const void *, const void *))
Definition: elst2.cpp:107
void assign_to_sublist(ELIST2_ITERATOR *start_it, ELIST2_ITERATOR *end_it)
Definition: elst2.cpp:71
bool at_last()
Definition: elst2.h:709
void exchange(ELIST2_ITERATOR *other_it)
Definition: elst2.cpp:302
ELIST2_LINK * extract()
Definition: elst2.h:586
void add_before_then_move(ELIST2_LINK *new_link)
Definition: elst2.h:392
ELIST2_LINK * forward()
Definition: elst2.cpp:185
ELIST2_LINK * backward()
Definition: elst2.cpp:229
ELIST2_LINK * data()
Definition: elst2.h:190
void mark_cycle_pt()
Definition: elst2.h:670
ELIST2_LINK * data_relative(int8_t offset)
Definition: elst2.cpp:268
bool cycled_list()
Definition: elst2.h:728
void add_to_end(ELIST2_LINK *new_link)
Definition: elst2.h:784
void error(const char *caller, TessErrorLogCode action, const char *format,...) const
Definition: errcode.cpp:35