tesseract 4.1.1
Loading...
Searching...
No Matches
elst.cpp
Go to the documentation of this file.
1/**********************************************************************
2 * File: elst.cpp (Formerly elist.c)
3 * Description: Embedded list handling code which is 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 "elst.h"
21
22/***********************************************************************
23 * MEMBER FUNCTIONS OF CLASS: ELIST
24 * ================================
25 **********************************************************************/
26
27/***********************************************************************
28 * ELIST::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
40ELIST::internal_clear ( //destroy all links
41void (*zapper) (ELIST_LINK *)) {
42 //ptr to zapper functn
43 ELIST_LINK *ptr;
44 ELIST_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 * ELIST::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 ELIST::assign_to_sublist( //to this list
72 ELIST_ITERATOR *start_it, //from list start
73 ELIST_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 ("ELIST.assign_to_sublist", ABORT, nullptr);
79
80 last = start_it->extract_sublist (end_it);
81}
82
83/***********************************************************************
84 * ELIST::length
85 *
86 * Return count of elements on list
87 **********************************************************************/
88
89int32_t ELIST::length() const { // count elements
90 ELIST_ITERATOR it(const_cast<ELIST*>(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 * ELIST::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
107ELIST::sort ( //sort elements
108int comparator ( //comparison routine
109const void *, const void *)) {
110 ELIST_ITERATOR it(this);
111 int32_t count;
112 ELIST_LINK **base; //ptr array to sort
113 ELIST_LINK **current;
114 int32_t i;
115
116 /* Allocate an array of pointers, one per list element */
117 count = length ();
118 base = static_cast<ELIST_LINK **>(malloc (count * sizeof (ELIST_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.
144// If unique is set to true and comparator() returns 0 (an entry with the
145// same information as the one contained in new_link is already in the
146// list) - new_link is not added to the list and the function returns the
147// pointer to the identical entry that already exists in the list
148// (otherwise the function returns new_link).
150 int comparator(const void*, const void*),
151 bool unique, ELIST_LINK* new_link) {
152 // Check for adding at the end.
153 if (last == nullptr || comparator(&last, &new_link) < 0) {
154 if (last == nullptr) {
155 new_link->next = new_link;
156 } else {
157 new_link->next = last->next;
158 last->next = new_link;
159 }
160 last = new_link;
161 } else {
162 // Need to use an iterator.
163 ELIST_ITERATOR it(this);
164 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
165 ELIST_LINK* link = it.data();
166 int compare = comparator(&link, &new_link);
167 if (compare > 0) {
168 break;
169 } else if (unique && compare == 0) {
170 return link;
171 }
172 }
173 if (it.cycled_list())
174 it.add_to_end(new_link);
175 else
176 it.add_before_then_move(new_link);
177 }
178 return new_link;
179}
180
181/***********************************************************************
182 * MEMBER FUNCTIONS OF CLASS: ELIST_ITERATOR
183 * =========================================
184 **********************************************************************/
185
186/***********************************************************************
187 * ELIST_ITERATOR::forward
188 *
189 * Move the iterator to the next element of the list.
190 * REMEMBER: ALL LISTS ARE CIRCULAR.
191 **********************************************************************/
192
194 #ifndef NDEBUG
195 if (!list)
196 NO_LIST.error ("ELIST_ITERATOR::forward", ABORT, nullptr);
197 #endif
198 if (list->empty ())
199 return nullptr;
200
201 if (current) { //not removed so
202 //set previous
203 prev = current;
204 started_cycling = true;
205 // In case next is deleted by another iterator, get next from current.
206 current = current->next;
207 } else {
208 if (ex_current_was_cycle_pt)
209 cycle_pt = next;
210 current = next;
211 }
212#ifndef NDEBUG
213 if (!current)
214 NULL_DATA.error ("ELIST_ITERATOR::forward", ABORT, nullptr);
215#endif
216 next = current->next;
217
218 #ifndef NDEBUG
219 if (!next)
220 NULL_NEXT.error ("ELIST_ITERATOR::forward", ABORT,
221 "This is: %p Current is: %p", this, current);
222 #endif
223 return current;
224}
225
226/***********************************************************************
227 * ELIST_ITERATOR::data_relative
228 *
229 * Return the data pointer to the element "offset" elements from current.
230 * "offset" must not be less than -1.
231 * (This function can't be INLINEd because it contains a loop)
232 **********************************************************************/
233
235 int8_t offset) { //offset from current
236 ELIST_LINK *ptr;
237
238 #ifndef NDEBUG
239 if (!list)
240 NO_LIST.error ("ELIST_ITERATOR::data_relative", ABORT, nullptr);
241 if (list->empty ())
242 EMPTY_LIST.error ("ELIST_ITERATOR::data_relative", ABORT, nullptr);
243 if (offset < -1)
244 BAD_PARAMETER.error ("ELIST_ITERATOR::data_relative", ABORT,
245 "offset < -l");
246 #endif
247
248 if (offset == -1)
249 ptr = prev;
250 else
251 for (ptr = current ? current : prev; offset-- > 0; ptr = ptr->next);
252
253 #ifndef NDEBUG
254 if (!ptr)
255 NULL_DATA.error ("ELIST_ITERATOR::data_relative", ABORT, nullptr);
256 #endif
257
258 return ptr;
259}
260
261/***********************************************************************
262 * ELIST_ITERATOR::move_to_last()
263 *
264 * Move current so that it is set to the end of the list.
265 * Return data just in case anyone wants it.
266 * (This function can't be INLINEd because it contains a loop)
267 **********************************************************************/
268
270 #ifndef NDEBUG
271 if (!list)
272 NO_LIST.error ("ELIST_ITERATOR::move_to_last", ABORT, nullptr);
273 #endif
274
275 while (current != list->last)
276 forward();
277
278 return current;
279}
280
281/***********************************************************************
282 * ELIST_ITERATOR::exchange()
283 *
284 * Given another iterator, whose current element is a different element on
285 * the same list list OR an element of another list, exchange the two current
286 * elements. On return, each iterator points to the element which was the
287 * other iterators current on entry.
288 * (This function hasn't been in-lined because its a bit big!)
289 **********************************************************************/
290
291void ELIST_ITERATOR::exchange( //positions of 2 links
292 ELIST_ITERATOR *other_it) { //other iterator
293 constexpr ERRCODE DONT_EXCHANGE_DELETED(
294 "Can't exchange deleted elements of lists");
295
296 ELIST_LINK *old_current;
297
298 #ifndef NDEBUG
299 if (!list)
300 NO_LIST.error ("ELIST_ITERATOR::exchange", ABORT, nullptr);
301 if (!other_it)
302 BAD_PARAMETER.error ("ELIST_ITERATOR::exchange", ABORT, "other_it nullptr");
303 if (!(other_it->list))
304 NO_LIST.error ("ELIST_ITERATOR::exchange", ABORT, "other_it");
305 #endif
306
307 /* Do nothing if either list is empty or if both iterators reference the same
308 link */
309
310 if ((list->empty ()) ||
311 (other_it->list->empty ()) || (current == other_it->current))
312 return;
313
314 /* Error if either current element is deleted */
315
316 if (!current || !other_it->current)
317 DONT_EXCHANGE_DELETED.error ("ELIST_ITERATOR.exchange", ABORT, nullptr);
318
319 /* Now handle the 4 cases: doubleton list; non-doubleton adjacent elements
320 (other before this); non-doubleton adjacent elements (this before other);
321 non-adjacent elements. */
322
323 //adjacent links
324 if ((next == other_it->current) ||
325 (other_it->next == current)) {
326 //doubleton list
327 if ((next == other_it->current) &&
328 (other_it->next == current)) {
329 prev = next = current;
330 other_it->prev = other_it->next = other_it->current;
331 }
332 else { //non-doubleton with
333 //adjacent links
334 //other before this
335 if (other_it->next == current) {
336 other_it->prev->next = current;
337 other_it->current->next = next;
338 current->next = other_it->current;
339 other_it->next = other_it->current;
340 prev = current;
341 }
342 else { //this before other
343 prev->next = other_it->current;
344 current->next = other_it->next;
345 other_it->current->next = current;
346 next = current;
347 other_it->prev = other_it->current;
348 }
349 }
350 }
351 else { //no overlap
352 prev->next = other_it->current;
353 current->next = other_it->next;
354 other_it->prev->next = current;
355 other_it->current->next = next;
356 }
357
358 /* update end of list pointer when necessary (remember that the 2 iterators
359 may iterate over different lists!) */
360
361 if (list->last == current)
362 list->last = other_it->current;
363 if (other_it->list->last == other_it->current)
364 other_it->list->last = current;
365
366 if (current == cycle_pt)
367 cycle_pt = other_it->cycle_pt;
368 if (other_it->current == other_it->cycle_pt)
369 other_it->cycle_pt = cycle_pt;
370
371 /* The actual exchange - in all cases*/
372
373 old_current = current;
374 current = other_it->current;
375 other_it->current = old_current;
376}
377
378/***********************************************************************
379 * ELIST_ITERATOR::extract_sublist()
380 *
381 * This is a private member, used only by ELIST::assign_to_sublist.
382 * Given another iterator for the same list, extract the links from THIS to
383 * OTHER inclusive, link them into a new circular list, and return a
384 * pointer to the last element.
385 * (Can't inline this function because it contains a loop)
386 **********************************************************************/
387
388ELIST_LINK *ELIST_ITERATOR::extract_sublist( //from this current
389 ELIST_ITERATOR *other_it) { //to other current
390 #ifndef NDEBUG
391 constexpr ERRCODE BAD_EXTRACTION_PTS(
392 "Can't extract sublist from points on different lists");
393 constexpr ERRCODE DONT_EXTRACT_DELETED(
394 "Can't extract a sublist marked by deleted points");
395 #endif
396 constexpr ERRCODE BAD_SUBLIST("Can't find sublist end point in original list");
397
398 ELIST_ITERATOR temp_it = *this;
399 ELIST_LINK *end_of_new_list;
400
401 #ifndef NDEBUG
402 if (!other_it)
403 BAD_PARAMETER.error ("ELIST_ITERATOR::extract_sublist", ABORT,
404 "other_it nullptr");
405 if (!list)
406 NO_LIST.error ("ELIST_ITERATOR::extract_sublist", ABORT, nullptr);
407 if (list != other_it->list)
408 BAD_EXTRACTION_PTS.error ("ELIST_ITERATOR.extract_sublist", ABORT, nullptr);
409 if (list->empty ())
410 EMPTY_LIST.error ("ELIST_ITERATOR::extract_sublist", ABORT, nullptr);
411
412 if (!current || !other_it->current)
413 DONT_EXTRACT_DELETED.error ("ELIST_ITERATOR.extract_sublist", ABORT,
414 nullptr);
415 #endif
416
417 ex_current_was_last = other_it->ex_current_was_last = false;
418 ex_current_was_cycle_pt = false;
419 other_it->ex_current_was_cycle_pt = false;
420
421 temp_it.mark_cycle_pt ();
422 do { //walk sublist
423 if (temp_it.cycled_list()) // can't find end pt
424 BAD_SUBLIST.error ("ELIST_ITERATOR.extract_sublist", ABORT, nullptr);
425
426 if (temp_it.at_last ()) {
427 list->last = prev;
428 ex_current_was_last = other_it->ex_current_was_last = true;
429 }
430
431 if (temp_it.current == cycle_pt)
432 ex_current_was_cycle_pt = true;
433
434 if (temp_it.current == other_it->cycle_pt)
435 other_it->ex_current_was_cycle_pt = true;
436
437 temp_it.forward ();
438 }
439 while (temp_it.prev != other_it->current);
440
441 //circularise sublist
442 other_it->current->next = current;
443 end_of_new_list = other_it->current;
444
445 //sublist = whole list
446 if (prev == other_it->current) {
447 list->last = nullptr;
448 prev = current = next = nullptr;
449 other_it->prev = other_it->current = other_it->next = nullptr;
450 }
451 else {
452 prev->next = other_it->next;
453 current = other_it->current = nullptr;
454 next = other_it->next;
455 other_it->prev = prev;
456 }
457 return end_of_new_list;
458}
@ 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")
int count(LIST var_list)
Definition: oldlist.cpp:95
Definition: elst.h:107
ELIST_LINK * add_sorted_and_find(int comparator(const void *, const void *), bool unique, ELIST_LINK *new_link)
Definition: elst.cpp:149
bool empty() const
Definition: elst.h:125
void sort(int comparator(const void *, const void *))
Definition: elst.cpp:107
int32_t length() const
Definition: elst.cpp:89
void internal_clear(void(*zapper)(ELIST_LINK *))
Definition: elst.cpp:40
void assign_to_sublist(ELIST_ITERATOR *start_it, ELIST_ITERATOR *end_it)
Definition: elst.cpp:71
bool cycled_list()
Definition: elst.h:716
ELIST_LINK * forward()
Definition: elst.cpp:193
ELIST_LINK * move_to_last()
Definition: elst.cpp:269
void add_to_end(ELIST_LINK *new_link)
Definition: elst.h:775
ELIST_LINK * data()
Definition: elst.h:224
void exchange(ELIST_ITERATOR *other_it)
Definition: elst.cpp:291
void add_before_then_move(ELIST_LINK *new_link)
Definition: elst.h:416
ELIST_LINK * extract()
Definition: elst.h:594
bool at_last()
Definition: elst.h:696
void mark_cycle_pt()
Definition: elst.h:655
ELIST_LINK * data_relative(int8_t offset)
Definition: elst.cpp:234
void error(const char *caller, TessErrorLogCode action, const char *format,...) const
Definition: errcode.cpp:35