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