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
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
210 ELIST2_LINK *ELIST2_ITERATOR::forward() {
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
252 ELIST2_LINK *ELIST2_ITERATOR::backward() {
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
293 ELIST2_LINK *ELIST2_ITERATOR::data_relative( //get data + or - ..
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 }