tesseract  5.0.0-alpha-619-ge9db
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 
39 void
40 ELIST2::internal_clear ( //destroy all links
41 void (*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 
71 void 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 
89 int32_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 
106 void
107 ELIST2::sort ( //sort elements
108 int comparator ( //comparison routine
109 const 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.
144 void 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 
268 ELIST2_LINK *ELIST2_ITERATOR::data_relative( //get data + or - ..
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 
302 void 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 
411 ELIST2_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 }
BAD_PARAMETER
constexpr ERRCODE BAD_PARAMETER("List parameter error")
ERRCODE
Definition: errcode.h:67
ELIST2_ITERATOR::data_relative
ELIST2_LINK * data_relative(int8_t offset)
Definition: elst2.cpp:259
ELIST2::sort
void sort(int comparator(const void *, const void *))
Definition: elst2.cpp:102
ELIST2::empty
bool empty() const
Definition: elst2.h:104
NULL_NEXT
constexpr ERRCODE NULL_NEXT("Next element on the list is nullptr")
elst2.h
ELIST2::length
int32_t length() const
Definition: elst2.cpp:85
ELIST2_ITERATOR::exchange
void exchange(ELIST2_ITERATOR *other_it)
Definition: elst2.cpp:292
ELIST2_ITERATOR::add_before_then_move
void add_before_then_move(ELIST2_LINK *new_link)
Definition: elst2.h:382
ELIST2::assign_to_sublist
void assign_to_sublist(ELIST2_ITERATOR *start_it, ELIST2_ITERATOR *end_it)
Definition: elst2.cpp:68
ELIST2_ITERATOR::cycled_list
bool cycled_list()
Definition: elst2.h:708
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")
ELIST2_ITERATOR::backward
ELIST2_LINK * backward()
Definition: elst2.cpp:221
ELIST2_ITERATOR::forward
ELIST2_LINK * forward()
Definition: elst2.cpp:178
ELIST2_ITERATOR::mark_cycle_pt
void mark_cycle_pt()
Definition: elst2.h:653
EMPTY_LIST
constexpr ERRCODE EMPTY_LIST("List is empty")
ELIST2_ITERATOR::at_last
bool at_last()
Definition: elst2.h:690
count
int count(LIST var_list)
Definition: oldlist.cpp:79
ELIST2_ITERATOR
Definition: elst2.h:144
ELIST2_LINK
Definition: elst2.h:53
ELIST2::internal_clear
void internal_clear(void(*zapper)(ELIST2_LINK *))
Definition: elst2.cpp:38
ELIST2_ITERATOR::extract
ELIST2_LINK * extract()
Definition: elst2.h:572
ABORT
Definition: errcode.h:43
NO_LIST
constexpr ERRCODE NO_LIST("Iterator not set to a list")
ELIST2_ITERATOR::add_to_end
void add_to_end(ELIST2_LINK *new_link)
Definition: elst2.h:761
ELIST2::add_sorted
void add_sorted(int comparator(const void *, const void *), ELIST2_LINK *new_link)
Definition: elst2.cpp:139
NULL_PREV
constexpr ERRCODE NULL_PREV("Previous element on the list is nullptr")
ELIST2_ITERATOR::data
ELIST2_LINK * data()
Definition: elst2.h:189