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
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).
173 ELIST_LINK *ELIST::add_sorted_and_find(
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
217 ELIST_LINK *ELIST_ITERATOR::forward() {
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
259 ELIST_LINK *ELIST_ITERATOR::data_relative( //get data + or - ...
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
297 ELIST_LINK *ELIST_ITERATOR::move_to_last() {
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 }