Tesseract 3.02

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

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
274 void *CLIST_ITERATOR::forward() {
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
354 void *CLIST_ITERATOR::move_to_last() {
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 }