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