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