"Fossies" - the Fresh Open Source Software Archive

Member "tesseract-ocr/doc/html/clst_8cpp_source.html" (26 Oct 2012, 105292 Bytes) of package /linux/misc/old/tesseract-ocr-3.02.02-doc-html.tar.gz:


Caution: In this restricted "Fossies" environment the current HTML page may not be correctly presentated and may have some non-functional links. You can here alternatively try to browse the pure source code or just view or download the uninterpreted raw source code. If the rendering is insufficient you may try to find and view the page on the tesseract-ocr-3.02.02-doc-html.tar.gz project site itself.

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 }