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