tesseract  5.0.0-alpha-619-ge9db
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 
39 void
40 CLIST::internal_deep_clear ( //destroy all links
41 void (*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 
67 void 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 
96 void 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 
114 int32_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 
129 void
130 CLIST::sort ( //sort elements
131 int comparator ( //comparison routine
132 const 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.
169 bool 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.
207 void CLIST::set_subtract(int comparator(const void*, const void*),
208  bool unique,
209  CLIST* minuend, CLIST* subtrahend) {
210  shallow_clear();
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 
244 void *CLIST_ITERATOR::forward() {
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 
284 void *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 
344 void 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 
441 CLIST_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 }
BAD_PARAMETER
constexpr ERRCODE BAD_PARAMETER("List parameter error")
CLIST::sort
void sort(int comparator(const void *, const void *))
Definition: clst.cpp:124
CLIST_ITERATOR::data
void * data()
Definition: clst.h:190
ERRCODE
Definition: errcode.h:67
CLIST::set_subtract
void set_subtract(int comparator(const void *, const void *), bool unique, CLIST *minuend, CLIST *subtrahend)
Definition: clst.cpp:201
CLIST
Definition: clst.h:67
NULL_NEXT
constexpr ERRCODE NULL_NEXT("Next element on the list is nullptr")
CLIST_LINK
Definition: clst.h:38
CLIST::assign_to_sublist
void assign_to_sublist(CLIST_ITERATOR *start_it, CLIST_ITERATOR *end_it)
Definition: clst.cpp:92
CLIST::empty
bool empty() const
Definition: clst.h:95
CLIST_ITERATOR::mark_cycle_pt
void mark_cycle_pt()
Definition: clst.h:614
CLIST_ITERATOR::extract
void * extract()
Definition: clst.h:553
CLIST_ITERATOR::cycled_list
bool cycled_list()
Definition: clst.h:669
ERRCODE::error
void error(const char *caller, TessErrorLogCode action, const char *format,...) const
Definition: errcode.cpp:33
CLIST::add_sorted
bool add_sorted(int comparator(const void *, const void *), bool unique, void *new_data)
Definition: clst.cpp:163
NULL_DATA
constexpr ERRCODE NULL_DATA("List would have returned a nullptr data pointer")
CLIST::length
int32_t length() const
Definition: clst.cpp:109
CLIST_ITERATOR::add_before_then_move
void add_before_then_move(void *new_data)
Definition: clst.h:375
CLIST_ITERATOR::at_last
bool at_last()
Definition: clst.h:651
CLIST_ITERATOR::move_to_last
void * move_to_last()
Definition: clst.cpp:309
CLIST_ITERATOR::data_relative
void * data_relative(int8_t offset)
Definition: clst.cpp:275
EMPTY_LIST
constexpr ERRCODE EMPTY_LIST("List is empty")
CLIST_ITERATOR::exchange
void exchange(CLIST_ITERATOR *other_it)
Definition: clst.cpp:333
count
int count(LIST var_list)
Definition: oldlist.cpp:79
CLIST::internal_deep_clear
void internal_deep_clear(void(*zapper)(void *))
Definition: clst.cpp:38
CLIST::shallow_clear
void shallow_clear()
Definition: clst.cpp:64
CLIST_ITERATOR::add_to_end
void add_to_end(void *new_data)
Definition: clst.h:722
CLIST_ITERATOR::empty
bool empty()
Definition: clst.h:213
ABORT
Definition: errcode.h:43
CLIST_ITERATOR::forward
void * forward()
Definition: clst.cpp:236
CLIST_ITERATOR
Definition: clst.h:141
NO_LIST
constexpr ERRCODE NO_LIST("Iterator not set to a list")
clst.h