tesseract  5.0.0-alpha-619-ge9db
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 
39 void
40 ELIST::internal_clear ( //destroy all links
41 void (*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 
71 void 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 
89 int32_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 
106 void
107 ELIST::sort ( //sort elements
108 int comparator ( //comparison routine
109 const 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 
234 ELIST_LINK *ELIST_ITERATOR::data_relative( //get data + or - ...
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 
291 void 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 
388 ELIST_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 }
BAD_PARAMETER
constexpr ERRCODE BAD_PARAMETER("List parameter error")
elst.h
ELIST_ITERATOR
Definition: elst.h:175
ERRCODE
Definition: errcode.h:67
ELIST::length
int32_t length() const
Definition: elst.cpp:84
NULL_NEXT
constexpr ERRCODE NULL_NEXT("Next element on the list is nullptr")
ELIST_ITERATOR::exchange
void exchange(ELIST_ITERATOR *other_it)
Definition: elst.cpp:280
ELIST_ITERATOR::data
ELIST_LINK * data()
Definition: elst.h:222
ELIST_ITERATOR::extract
ELIST_LINK * extract()
Definition: elst.h:580
ELIST_ITERATOR::at_last
bool at_last()
Definition: elst.h:678
ELIST::sort
void sort(int comparator(const void *, const void *))
Definition: elst.cpp:101
ERRCODE::error
void error(const char *caller, TessErrorLogCode action, const char *format,...) const
Definition: errcode.cpp:33
NULL_DATA
constexpr ERRCODE NULL_DATA("List would have returned a nullptr data pointer")
ELIST_ITERATOR::mark_cycle_pt
void mark_cycle_pt()
Definition: elst.h:639
ELIST_ITERATOR::move_to_last
ELIST_LINK * move_to_last()
Definition: elst.cpp:259
ELIST::internal_clear
void internal_clear(void(*zapper)(ELIST_LINK *))
Definition: elst.cpp:37
ELIST_ITERATOR::cycled_list
bool cycled_list()
Definition: elst.h:697
EMPTY_LIST
constexpr ERRCODE EMPTY_LIST("List is empty")
ELIST::add_sorted_and_find
ELIST_LINK * add_sorted_and_find(int comparator(const void *, const void *), bool unique, ELIST_LINK *new_link)
Definition: elst.cpp:143
count
int count(LIST var_list)
Definition: oldlist.cpp:79
ELIST_ITERATOR::add_before_then_move
void add_before_then_move(ELIST_LINK *new_link)
Definition: elst.h:406
ELIST_ITERATOR::data_relative
ELIST_LINK * data_relative(int8_t offset)
Definition: elst.cpp:225
ELIST_ITERATOR::forward
ELIST_LINK * forward()
Definition: elst.cpp:185
ELIST_ITERATOR::add_to_end
void add_to_end(ELIST_LINK *new_link)
Definition: elst.h:753
ELIST_LINK
Definition: elst.h:74
ABORT
Definition: errcode.h:43
ELIST::assign_to_sublist
void assign_to_sublist(ELIST_ITERATOR *start_it, ELIST_ITERATOR *end_it)
Definition: elst.cpp:67
NO_LIST
constexpr ERRCODE NO_LIST("Iterator not set to a list")
ELIST::empty
bool empty() const
Definition: elst.h:124