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.h
Go to the documentation of this file.
1 /**********************************************************************
2 * File: elst2.h (Formerly elist2.h)
3 * Description: Double linked embedded list module 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 #ifndef ELST2_H
21 #define ELST2_H
22
23 #include <stdio.h>
24 #include "host.h"
25 #include "serialis.h"
26 #include "lsterr.h"
27
28 class ELIST2_ITERATOR;
29
30 /**********************************************************************
31 DESIGN NOTE
32 ===========
33
34 It would probably be possible to implement the ELIST2 classes as derived
35 classes from ELIST. I haven't done this because:
36
37 a) I think it would be harder to understand the code
38 (Though the problem with not inheriting is that changes to ELIST must be
39 reflected in ELIST2 and vice versa)
40
41 b) Most of the code is inline so:
42 i) The duplication in source does not affect the run time code size - the
43 code is copied inline anyway!
44
45 ii) The compiler should have a bit less work to do!
46 **********************************************************************/
47
48 /**********************************************************************
49 * CLASS - ELIST2_LINK
50 *
51 * Generic link class for doubly linked lists with embedded links
52 *
53 * Note: No destructor - elements are assumed to be destroyed EITHER after
54 * they have been extracted from a list OR by the ELIST2 destructor which
55 * walks the list.
56 **********************************************************************/
57
58 class DLLSYM ELIST2_LINK
59 {
60 friend class ELIST2_ITERATOR;
61 friend class ELIST2;
62
63 ELIST2_LINK *prev;
64 ELIST2_LINK *next;
65
66 public:
67 ELIST2_LINK() { //constructor
68 prev = next = NULL;
69 }
70
71 ELIST2_LINK( //copy constructor
72 const ELIST2_LINK &) { //dont copy link
73 prev = next = NULL;
74 }
75
76 void operator= ( //dont copy links
77 const ELIST2_LINK &) {
78 prev = next = NULL;
79 }
80 };
81
82 /**********************************************************************
83 * CLASS - ELIST2
84 *
85 * Generic list class for doubly linked lists with embedded links
86 **********************************************************************/
87
88 class DLLSYM ELIST2
89 {
90 friend class ELIST2_ITERATOR;
91
92 ELIST2_LINK *last; //End of list
93 //(Points to head)
94 ELIST2_LINK *First() { // return first
95 return last ? last->next : NULL;
96 }
97
98 public:
99 ELIST2() { //constructor
100 last = NULL;
101 }
102
103 void internal_clear ( //destroy all links
104 void (*zapper) (ELIST2_LINK *));
105 //ptr to zapper functn
106
107 bool empty() const { //is list empty?
108 return !last;
109 }
110
111 bool singleton() const {
112 return last ? (last == last->next) : false;
113 }
114
115 void shallow_copy( //dangerous!!
116 ELIST2 *from_list) { //beware destructors!!
117 last = from_list->last;
118 }
119
120 //ptr to copier functn
121 void internal_deep_copy (ELIST2_LINK * (*copier) (ELIST2_LINK *),
122 const ELIST2 * list); //list being copied
123
124 void assign_to_sublist( //to this list
125 ELIST2_ITERATOR *start_it, //from list start
126 ELIST2_ITERATOR *end_it); //from list end
127
128 inT32 length() const; // # elements in list
129
130 void sort ( //sort elements
131 int comparator ( //comparison routine
132 const void *, const void *));
133
134 // Assuming list has been sorted already, insert new_link to
135 // keep the list sorted according to the same comparison function.
136 // Comparision function is the same as used by sort, i.e. uses double
137 // indirection. Time is O(1) to add to beginning or end.
138 // Time is linear to add pre-sorted items to an empty list.
139 void add_sorted(int comparator(const void*, const void*),
140 ELIST2_LINK* new_link);
141
142 };
143
144 /***********************************************************************
145 * CLASS - ELIST2_ITERATOR
146 *
147 * Generic iterator class for doubly linked lists with embedded links
148 **********************************************************************/
149
150 class DLLSYM ELIST2_ITERATOR
151 {
152 friend void ELIST2::assign_to_sublist(ELIST2_ITERATOR *, ELIST2_ITERATOR *);
153
154 ELIST2 *list; //List being iterated
155 ELIST2_LINK *prev; //prev element
156 ELIST2_LINK *current; //current element
157 ELIST2_LINK *next; //next element
158 BOOL8 ex_current_was_last; //current extracted
159 //was end of list
160 BOOL8 ex_current_was_cycle_pt; //current extracted
161 //was cycle point
162 ELIST2_LINK *cycle_pt; //point we are cycling
163 //the list to.
164 BOOL8 started_cycling; //Have we moved off
165 //the start?
166
167 ELIST2_LINK *extract_sublist( //from this current...
168 ELIST2_ITERATOR *other_it); //to other current
169
170 public:
171 ELIST2_ITERATOR() { //constructor
172 list = NULL;
173 } //unassigned list
174
175 ELIST2_ITERATOR( //constructor
176 ELIST2 *list_to_iterate);
177
178 void set_to_list( //change list
179 ELIST2 *list_to_iterate);
180
181 void add_after_then_move( //add after current &
182 ELIST2_LINK *new_link); //move to new
183
184 void add_after_stay_put( //add after current &
185 ELIST2_LINK *new_link); //stay at current
186
187 void add_before_then_move( //add before current &
188 ELIST2_LINK *new_link); //move to new
189
190 void add_before_stay_put( //add before current &
191 ELIST2_LINK *new_link); //stay at current
192
193 void add_list_after( //add a list &
194 ELIST2 *list_to_add); //stay at current
195
196 void add_list_before( //add a list &
197 ELIST2 *list_to_add); //move to it 1st item
198
199 ELIST2_LINK *data() { //get current data
200 #ifndef NDEBUG
201 if (!current)
202 NULL_DATA.error ("ELIST2_ITERATOR::data", ABORT, NULL);
203 if (!list)
204 NO_LIST.error ("ELIST2_ITERATOR::data", ABORT, NULL);
205 #endif
206 return current;
207 }
208
209 ELIST2_LINK *data_relative( //get data + or - ...
210 inT8 offset); //offset from current
211
212 ELIST2_LINK *forward(); //move to next element
213
214 ELIST2_LINK *backward(); //move to prev element
215
216 ELIST2_LINK *extract(); //remove from list
217
218 //go to start of list
219 ELIST2_LINK *move_to_first();
220
221 ELIST2_LINK *move_to_last(); //go to end of list
222
223 void mark_cycle_pt(); //remember current
224
225 BOOL8 empty() { //is list empty?
226 #ifndef NDEBUG
227 if (!list)
228 NO_LIST.error ("ELIST2_ITERATOR::empty", ABORT, NULL);
229 #endif
230 return list->empty ();
231 }
232
233 BOOL8 current_extracted() { //current extracted?
234 return !current;
235 }
236
237 BOOL8 at_first(); //Current is first?
238
239 BOOL8 at_last(); //Current is last?
240
241 BOOL8 cycled_list(); //Completed a cycle?
242
243 void add_to_end( //add at end &
244 ELIST2_LINK *new_link); //dont move
245
246 void exchange( //positions of 2 links
247 ELIST2_ITERATOR *other_it); //other iterator
248
249 inT32 length(); //# elements in list
250
251 void sort ( //sort elements
252 int comparator ( //comparison routine
253 const void *, const void *));
254
255 };
256
257 /***********************************************************************
258 * ELIST2_ITERATOR::set_to_list
259 *
260 * (Re-)initialise the iterator to point to the start of the list_to_iterate
261 * over.
262 **********************************************************************/
263
264 inline void ELIST2_ITERATOR::set_to_list( //change list
265 ELIST2 *list_to_iterate) {
266 #ifndef NDEBUG
267 if (!this)
268 NULL_OBJECT.error ("ELIST2_ITERATOR::set_to_list", ABORT, NULL);
269 if (!list_to_iterate)
270 BAD_PARAMETER.error ("ELIST2_ITERATOR::set_to_list", ABORT,
271 "list_to_iterate is NULL");
272 #endif
273
274 list = list_to_iterate;
275 prev = list->last;
276 current = list->First ();
277 next = current ? current->next : NULL;
278 cycle_pt = NULL; //await explicit set
279 started_cycling = FALSE;
280 ex_current_was_last = FALSE;
281 ex_current_was_cycle_pt = FALSE;
282 }
283
284
285 /***********************************************************************
286 * ELIST2_ITERATOR::ELIST2_ITERATOR
287 *
288 * CONSTRUCTOR - set iterator to specified list;
289 **********************************************************************/
290
291 inline ELIST2_ITERATOR::ELIST2_ITERATOR(ELIST2 *list_to_iterate) {
292 set_to_list(list_to_iterate);
293 }
294
295
296 /***********************************************************************
297 * ELIST2_ITERATOR::add_after_then_move
298 *
299 * Add a new element to the list after the current element and move the
300 * iterator to the new element.
301 **********************************************************************/
302
303 inline void ELIST2_ITERATOR::add_after_then_move( // element to add
304 ELIST2_LINK *new_element) {
305 #ifndef NDEBUG
306 if (!this)
307 NULL_OBJECT.error ("ELIST2_ITERATOR::add_after_then_move", ABORT, NULL);
308 if (!list)
309 NO_LIST.error ("ELIST2_ITERATOR::add_after_then_move", ABORT, NULL);
310 if (!new_element)
311 BAD_PARAMETER.error ("ELIST2_ITERATOR::add_after_then_move", ABORT,
312 "new_element is NULL");
313 if (new_element->next)
314 STILL_LINKED.error ("ELIST2_ITERATOR::add_after_then_move", ABORT, NULL);
315 #endif
316
317 if (list->empty ()) {
318 new_element->next = new_element;
319 new_element->prev = new_element;
320 list->last = new_element;
321 prev = next = new_element;
322 }
323 else {
324 new_element->next = next;
325 next->prev = new_element;
326
327 if (current) { //not extracted
328 new_element->prev = current;
329 current->next = new_element;
330 prev = current;
331 if (current == list->last)
332 list->last = new_element;
333 }
334 else { //current extracted
335 new_element->prev = prev;
336 prev->next = new_element;
337 if (ex_current_was_last)
338 list->last = new_element;
339 if (ex_current_was_cycle_pt)
340 cycle_pt = new_element;
341 }
342 }
343 current = new_element;
344 }
345
346
347 /***********************************************************************
348 * ELIST2_ITERATOR::add_after_stay_put
349 *
350 * Add a new element to the list after the current element but do not move
351 * the iterator to the new element.
352 **********************************************************************/
353
354 inline void ELIST2_ITERATOR::add_after_stay_put( // element to add
355 ELIST2_LINK *new_element) {
356 #ifndef NDEBUG
357 if (!this)
358 NULL_OBJECT.error ("ELIST2_ITERATOR::add_after_stay_put", ABORT, NULL);
359 if (!list)
360 NO_LIST.error ("ELIST2_ITERATOR::add_after_stay_put", ABORT, NULL);
361 if (!new_element)
362 BAD_PARAMETER.error ("ELIST2_ITERATOR::add_after_stay_put", ABORT,
363 "new_element is NULL");
364 if (new_element->next)
365 STILL_LINKED.error ("ELIST2_ITERATOR::add_after_stay_put", ABORT, NULL);
366 #endif
367
368 if (list->empty ()) {
369 new_element->next = new_element;
370 new_element->prev = new_element;
371 list->last = new_element;
372 prev = next = new_element;
373 ex_current_was_last = FALSE;
374 current = NULL;
375 }
376 else {
377 new_element->next = next;
378 next->prev = new_element;
379
380 if (current) { //not extracted
381 new_element->prev = current;
382 current->next = new_element;
383 if (prev == current)
384 prev = new_element;
385 if (current == list->last)
386 list->last = new_element;
387 }
388 else { //current extracted
389 new_element->prev = prev;
390 prev->next = new_element;
391 if (ex_current_was_last) {
392 list->last = new_element;
393 ex_current_was_last = FALSE;
394 }
395 }
396 next = new_element;
397 }
398 }
399
400
401 /***********************************************************************
402 * ELIST2_ITERATOR::add_before_then_move
403 *
404 * Add a new element to the list before the current element and move the
405 * iterator to the new element.
406 **********************************************************************/
407
408 inline void ELIST2_ITERATOR::add_before_then_move( // element to add
409 ELIST2_LINK *new_element) {
410 #ifndef NDEBUG
411 if (!this)
412 NULL_OBJECT.error ("ELIST2_ITERATOR::add_before_then_move", ABORT, NULL);
413 if (!list)
414 NO_LIST.error ("ELIST2_ITERATOR::add_before_then_move", ABORT, NULL);
415 if (!new_element)
416 BAD_PARAMETER.error ("ELIST2_ITERATOR::add_before_then_move", ABORT,
417 "new_element is NULL");
418 if (new_element->next)
419 STILL_LINKED.error ("ELIST2_ITERATOR::add_before_then_move", ABORT, NULL);
420 #endif
421
422 if (list->empty ()) {
423 new_element->next = new_element;
424 new_element->prev = new_element;
425 list->last = new_element;
426 prev = next = new_element;
427 }
428 else {
429 prev->next = new_element;
430 new_element->prev = prev;
431
432 if (current) { //not extracted
433 new_element->next = current;
434 current->prev = new_element;
435 next = current;
436 }
437 else { //current extracted
438 new_element->next = next;
439 next->prev = new_element;
440 if (ex_current_was_last)
441 list->last = new_element;
442 if (ex_current_was_cycle_pt)
443 cycle_pt = new_element;
444 }
445 }
446 current = new_element;
447 }
448
449
450 /***********************************************************************
451 * ELIST2_ITERATOR::add_before_stay_put
452 *
453 * Add a new element to the list before the current element but dont move the
454 * iterator to the new element.
455 **********************************************************************/
456
457 inline void ELIST2_ITERATOR::add_before_stay_put( // element to add
458 ELIST2_LINK *new_element) {
459 #ifndef NDEBUG
460 if (!this)
461 NULL_OBJECT.error ("ELIST2_ITERATOR::add_before_stay_put", ABORT, NULL);
462 if (!list)
463 NO_LIST.error ("ELIST2_ITERATOR::add_before_stay_put", ABORT, NULL);
464 if (!new_element)
465 BAD_PARAMETER.error ("ELIST2_ITERATOR::add_before_stay_put", ABORT,
466 "new_element is NULL");
467 if (new_element->next)
468 STILL_LINKED.error ("ELIST2_ITERATOR::add_before_stay_put", ABORT, NULL);
469 #endif
470
471 if (list->empty ()) {
472 new_element->next = new_element;
473 new_element->prev = new_element;
474 list->last = new_element;
475 prev = next = new_element;
476 ex_current_was_last = TRUE;
477 current = NULL;
478 }
479 else {
480 prev->next = new_element;
481 new_element->prev = prev;
482
483 if (current) { //not extracted
484 new_element->next = current;
485 current->prev = new_element;
486 if (next == current)
487 next = new_element;
488 }
489 else { //current extracted
490 new_element->next = next;
491 next->prev = new_element;
492 if (ex_current_was_last)
493 list->last = new_element;
494 }
495 prev = new_element;
496 }
497 }
498
499
500 /***********************************************************************
501 * ELIST2_ITERATOR::add_list_after
502 *
503 * Insert another list to this list after the current element but dont move the
504 * iterator.
505 **********************************************************************/
506
507 inline void ELIST2_ITERATOR::add_list_after(ELIST2 *list_to_add) {
508 #ifndef NDEBUG
509 if (!this)
510 NULL_OBJECT.error ("ELIST2_ITERATOR::add_list_after", ABORT, NULL);
511 if (!list)
512 NO_LIST.error ("ELIST2_ITERATOR::add_list_after", ABORT, NULL);
513 if (!list_to_add)
514 BAD_PARAMETER.error ("ELIST2_ITERATOR::add_list_after", ABORT,
515 "list_to_add is NULL");
516 #endif
517
518 if (!list_to_add->empty ()) {
519 if (list->empty ()) {
520 list->last = list_to_add->last;
521 prev = list->last;
522 next = list->First ();
523 ex_current_was_last = TRUE;
524 current = NULL;
525 }
526 else {
527 if (current) { //not extracted
528 current->next = list_to_add->First ();
529 current->next->prev = current;
530 if (current == list->last)
531 list->last = list_to_add->last;
532 list_to_add->last->next = next;
533 next->prev = list_to_add->last;
534 next = current->next;
535 }
536 else { //current extracted
537 prev->next = list_to_add->First ();
538 prev->next->prev = prev;
539 if (ex_current_was_last) {
540 list->last = list_to_add->last;
541 ex_current_was_last = FALSE;
542 }
543 list_to_add->last->next = next;
544 next->prev = list_to_add->last;
545 next = prev->next;
546 }
547 }
548 list_to_add->last = NULL;
549 }
550 }
551
552
553 /***********************************************************************
554 * ELIST2_ITERATOR::add_list_before
555 *
556 * Insert another list to this list before the current element. Move the
557 * iterator to the start of the inserted elements
558 * iterator.
559 **********************************************************************/
560
561 inline void ELIST2_ITERATOR::add_list_before(ELIST2 *list_to_add) {
562 #ifndef NDEBUG
563 if (!this)
564 NULL_OBJECT.error ("ELIST2_ITERATOR::add_list_before", ABORT, NULL);
565 if (!list)
566 NO_LIST.error ("ELIST2_ITERATOR::add_list_before", ABORT, NULL);
567 if (!list_to_add)
568 BAD_PARAMETER.error ("ELIST2_ITERATOR::add_list_before", ABORT,
569 "list_to_add is NULL");
570 #endif
571
572 if (!list_to_add->empty ()) {
573 if (list->empty ()) {
574 list->last = list_to_add->last;
575 prev = list->last;
576 current = list->First ();
577 next = current->next;
578 ex_current_was_last = FALSE;
579 }
580 else {
581 prev->next = list_to_add->First ();
582 prev->next->prev = prev;
583
584 if (current) { //not extracted
585 list_to_add->last->next = current;
586 current->prev = list_to_add->last;
587 }
588 else { //current extracted
589 list_to_add->last->next = next;
590 next->prev = list_to_add->last;
591 if (ex_current_was_last)
592 list->last = list_to_add->last;
593 if (ex_current_was_cycle_pt)
594 cycle_pt = prev->next;
595 }
596 current = prev->next;
597 next = current->next;
598 }
599 list_to_add->last = NULL;
600 }
601 }
602
603
604 /***********************************************************************
605 * ELIST2_ITERATOR::extract
606 *
607 * Do extraction by removing current from the list, returning it to the
608 * caller, but NOT updating the iterator. (So that any calling loop can do
609 * this.) The iterator's current points to NULL. If the extracted element
610 * is to be deleted, this is the callers responsibility.
611 **********************************************************************/
612
613 inline ELIST2_LINK *ELIST2_ITERATOR::extract() {
614 ELIST2_LINK *extracted_link;
615
616 #ifndef NDEBUG
617 if (!this)
618 NULL_OBJECT.error ("ELIST2_ITERATOR::extract", ABORT, NULL);
619 if (!list)
620 NO_LIST.error ("ELIST2_ITERATOR::extract", ABORT, NULL);
621 if (!current) //list empty or
622 //element extracted
623 NULL_CURRENT.error ("ELIST2_ITERATOR::extract",
624 ABORT, NULL);
625 #endif
626
627 if (list->singleton()) {
628 // Special case where we do need to change the iterator.
629 prev = next = list->last = NULL;
630 } else {
631 prev->next = next; //remove from list
632 next->prev = prev;
633
634 if (current == list->last) {
635 list->last = prev;
636 ex_current_was_last = TRUE;
637 } else {
638 ex_current_was_last = FALSE;
639 }
640 }
641 // Always set ex_current_was_cycle_pt so an add/forward will work in a loop.
642 ex_current_was_cycle_pt = (current == cycle_pt) ? TRUE : FALSE;
643 extracted_link = current;
644 extracted_link->next = NULL; //for safety
645 extracted_link->prev = NULL; //for safety
646 current = NULL;
647 return extracted_link;
648 }
649
650
651 /***********************************************************************
652 * ELIST2_ITERATOR::move_to_first()
653 *
654 * Move current so that it is set to the start of the list.
655 * Return data just in case anyone wants it.
656 **********************************************************************/
657
658 inline ELIST2_LINK *ELIST2_ITERATOR::move_to_first() {
659 #ifndef NDEBUG
660 if (!this)
661 NULL_OBJECT.error ("ELIST2_ITERATOR::move_to_first", ABORT, NULL);
662 if (!list)
663 NO_LIST.error ("ELIST2_ITERATOR::move_to_first", ABORT, NULL);
664 #endif
665
666 current = list->First ();
667 prev = list->last;
668 next = current ? current->next : NULL;
669 return current;
670 }
671
672
673 /***********************************************************************
674 * ELIST2_ITERATOR::move_to_last()
675 *
676 * Move current so that it is set to the end of the list.
677 * Return data just in case anyone wants it.
678 **********************************************************************/
679
680 inline ELIST2_LINK *ELIST2_ITERATOR::move_to_last() {
681 #ifndef NDEBUG
682 if (!this)
683 NULL_OBJECT.error ("ELIST2_ITERATOR::move_to_last", ABORT, NULL);
684 if (!list)
685 NO_LIST.error ("ELIST2_ITERATOR::move_to_last", ABORT, NULL);
686 #endif
687
688 current = list->last;
689 prev = current ? current->prev : NULL;
690 next = current ? current->next : NULL;
691 return current;
692 }
693
694
695 /***********************************************************************
696 * ELIST2_ITERATOR::mark_cycle_pt()
697 *
698 * Remember the current location so that we can tell whether we've returned
699 * to this point later.
700 *
701 * If the current point is deleted either now, or in the future, the cycle
702 * point will be set to the next item which is set to current. This could be
703 * by a forward, add_after_then_move or add_after_then_move.
704 **********************************************************************/
705
706 inline void ELIST2_ITERATOR::mark_cycle_pt() {
707 #ifndef NDEBUG
708 if (!this)
709 NULL_OBJECT.error ("ELIST2_ITERATOR::mark_cycle_pt", ABORT, NULL);
710 if (!list)
711 NO_LIST.error ("ELIST2_ITERATOR::mark_cycle_pt", ABORT, NULL);
712 #endif
713
714 if (current)
715 cycle_pt = current;
716 else
717 ex_current_was_cycle_pt = TRUE;
718 started_cycling = FALSE;
719 }
720
721
722 /***********************************************************************
723 * ELIST2_ITERATOR::at_first()
724 *
725 * Are we at the start of the list?
726 *
727 **********************************************************************/
728
729 inline BOOL8 ELIST2_ITERATOR::at_first() {
730 #ifndef NDEBUG
731 if (!this)
732 NULL_OBJECT.error ("ELIST2_ITERATOR::at_first", ABORT, NULL);
733 if (!list)
734 NO_LIST.error ("ELIST2_ITERATOR::at_first", ABORT, NULL);
735 #endif
736
737 //we're at a deleted
738 return ((list->empty ()) || (current == list->First ()) || ((current == NULL) &&
739 (prev == list->last) && //NON-last pt between
740 !ex_current_was_last)); //first and last
741 }
742
743
744 /***********************************************************************
745 * ELIST2_ITERATOR::at_last()
746 *
747 * Are we at the end of the list?
748 *
749 **********************************************************************/
750
751 inline BOOL8 ELIST2_ITERATOR::at_last() {
752 #ifndef NDEBUG
753 if (!this)
754 NULL_OBJECT.error ("ELIST2_ITERATOR::at_last", ABORT, NULL);
755 if (!list)
756 NO_LIST.error ("ELIST2_ITERATOR::at_last", ABORT, NULL);
757 #endif
758
759 //we're at a deleted
760 return ((list->empty ()) || (current == list->last) || ((current == NULL) &&
761 (prev == list->last) && //last point between
762 ex_current_was_last)); //first and last
763 }
764
765
766 /***********************************************************************
767 * ELIST2_ITERATOR::cycled_list()
768 *
769 * Have we returned to the cycle_pt since it was set?
770 *
771 **********************************************************************/
772
773 inline BOOL8 ELIST2_ITERATOR::cycled_list() {
774 #ifndef NDEBUG
775 if (!this)
776 NULL_OBJECT.error ("ELIST2_ITERATOR::cycled_list", ABORT, NULL);
777 if (!list)
778 NO_LIST.error ("ELIST2_ITERATOR::cycled_list", ABORT, NULL);
779 #endif
780
781 return ((list->empty ()) || ((current == cycle_pt) && started_cycling));
782
783 }
784
785
786 /***********************************************************************
787 * ELIST2_ITERATOR::length()
788 *
789 * Return the length of the list
790 *
791 **********************************************************************/
792
793 inline inT32 ELIST2_ITERATOR::length() {
794 #ifndef NDEBUG
795 if (!this)
796 NULL_OBJECT.error ("ELIST2_ITERATOR::length", ABORT, NULL);
797 if (!list)
798 NO_LIST.error ("ELIST2_ITERATOR::length", ABORT, NULL);
799 #endif
800
801 return list->length ();
802 }
803
804
805 /***********************************************************************
806 * ELIST2_ITERATOR::sort()
807 *
808 * Sort the elements of the list, then reposition at the start.
809 *
810 **********************************************************************/
811
812 inline void
813 ELIST2_ITERATOR::sort ( //sort elements
814 int comparator ( //comparison routine
815 const void *, const void *)) {
816 #ifndef NDEBUG
817 if (!this)
818 NULL_OBJECT.error ("ELIST2_ITERATOR::sort", ABORT, NULL);
819 if (!list)
820 NO_LIST.error ("ELIST2_ITERATOR::sort", ABORT, NULL);
821 #endif
822
823 list->sort (comparator);
824 move_to_first();
825 }
826
827
828 /***********************************************************************
829 * ELIST2_ITERATOR::add_to_end
830 *
831 * Add a new element to the end of the list without moving the iterator.
832 * This is provided because a single linked list cannot move to the last as
833 * the iterator couldn't set its prev pointer. Adding to the end is
834 * essential for implementing
835 queues.
836 **********************************************************************/
837
838 inline void ELIST2_ITERATOR::add_to_end( // element to add
839 ELIST2_LINK *new_element) {
840 #ifndef NDEBUG
841 if (!this)
842 NULL_OBJECT.error ("ELIST2_ITERATOR::add_to_end", ABORT, NULL);
843 if (!list)
844 NO_LIST.error ("ELIST2_ITERATOR::add_to_end", ABORT, NULL);
845 if (!new_element)
846 BAD_PARAMETER.error ("ELIST2_ITERATOR::add_to_end", ABORT,
847 "new_element is NULL");
848 if (new_element->next)
849 STILL_LINKED.error ("ELIST2_ITERATOR::add_to_end", ABORT, NULL);
850 #endif
851
852 if (this->at_last ()) {
853 this->add_after_stay_put (new_element);
854 }
855 else {
856 if (this->at_first ()) {
857 this->add_before_stay_put (new_element);
858 list->last = new_element;
859 }
860 else { //Iteratr is elsewhere
861 new_element->next = list->last->next;
862 new_element->prev = list->last;
863 list->last->next->prev = new_element;
864 list->last->next = new_element;
865 list->last = new_element;
866 }
867 }
868 }
869
870
871 /***********************************************************************
872 QUOTE_IT MACRO DEFINITION
873 ===========================
874 Replace <parm> with "<parm>". <parm> may be an arbitrary number of tokens
875 ***********************************************************************/
876
877 #define QUOTE_IT( parm ) #parm
878
879 /***********************************************************************
880 ELIST2IZE( CLASSNAME ) MACRO DEFINITION
881 ======================================
882
883 CLASSNAME is assumed to be the name of a class which has a baseclass of
884 ELIST2_LINK.
885
886 NOTE: Because we dont use virtual functions in the list code, the list code
887 will NOT work correctly for classes derived from this.
888
889 The macro generates:
890 - An element deletion function: CLASSNAME##_zapper
891 - An E_LIST2 subclass: CLASSNAME##_LIST
892 - An E_LIST2_ITERATOR subclass:
893 CLASSNAME##_IT
894
895 NOTE: Generated names are DELIBERATELY designed to clash with those for
896 ELISTIZE but NOT with those for CLISTIZE and CLIST2IZE
897
898 Two macros are provided: ELIST2IZE and ELIST2IZEH
899 The ...IZEH macros just define the class names for use in .h files
900 The ...IZE macros define the code use in .c files
901 ***********************************************************************/
902
903 /***********************************************************************
904 ELIST2IZEH( CLASSNAME ) MACRO
905
906 ELIST2IZEH is a concatenation of 3 fragments ELIST2IZEH_A, ELIST2IZEH_B and
907 ELIST2IZEH_C.
908 ***********************************************************************/
909
910 #define ELIST2IZEH_A( CLASSNAME ) \
911 \
912 extern DLLSYM void CLASSNAME##_zapper( /*delete a link*/ \
913 ELIST2_LINK* link); /*link to delete*/
914
915 #define ELIST2IZEH_B( CLASSNAME ) \
916 \
917 /*********************************************************************** \
918 * CLASS - CLASSNAME##_LIST \
919 * \
920 * List class for class CLASSNAME \
921 * \
922 **********************************************************************/ \
923 \
924 class DLLSYM CLASSNAME##_LIST : public ELIST2 \
925 { \
926 public: \
927 CLASSNAME##_LIST():ELIST2() {} \
928 /* constructor */ \
929 \
930 CLASSNAME##_LIST( /* dont construct */ \
931 const CLASSNAME##_LIST&) /*by initial assign*/\
932 { DONT_CONSTRUCT_LIST_BY_COPY.error( QUOTE_IT( CLASSNAME##_LIST ), \
933 ABORT, NULL ); } \
934 \
935 void clear() /* delete elements */\
936 { ELIST2::internal_clear( &CLASSNAME##_zapper ); } \
937 \
938 ~CLASSNAME##_LIST() /* destructor */ \
939 { clear(); } \
940 \
941 /* Become a deep copy of src_list*/ \
942 void deep_copy(const CLASSNAME##_LIST* src_list, \
943 CLASSNAME* (*copier)(const CLASSNAME*)); \
944 \
945 void operator=( /* prevent assign */ \
946 const CLASSNAME##_LIST&) \
947 { DONT_ASSIGN_LISTS.error( QUOTE_IT( CLASSNAME##_LIST ), \
948 ABORT, NULL ); }
949
950 #define ELIST2IZEH_C( CLASSNAME ) \
951 }; \
952 \
953 \
954 \
955 /*********************************************************************** \
956 * CLASS - CLASSNAME##_IT \
957 * \
958 * Iterator class for class CLASSNAME##_LIST \
959 * \
960 * Note: We don't need to coerce pointers to member functions input \
961 * parameters as these are automatically converted to the type of the base \
962 * type. ("A ptr to a class may be converted to a pointer to a public base \
963 * class of that class") \
964 **********************************************************************/ \
965 \
966 class DLLSYM CLASSNAME##_IT : public ELIST2_ITERATOR \
967 { \
968 public: \
969 CLASSNAME##_IT():ELIST2_ITERATOR(){} \
970 \
971 CLASSNAME##_IT( \
972 CLASSNAME##_LIST* list):ELIST2_ITERATOR(list){} \
973 \
974 CLASSNAME* data() \
975 { return (CLASSNAME*) ELIST2_ITERATOR::data(); } \
976 \
977 CLASSNAME* data_relative( \
978 inT8 offset) \
979 { return (CLASSNAME*) ELIST2_ITERATOR::data_relative( offset ); } \
980 \
981 CLASSNAME* forward() \
982 { return (CLASSNAME*) ELIST2_ITERATOR::forward(); } \
983 \
984 CLASSNAME* backward() \
985 { return (CLASSNAME*) ELIST2_ITERATOR::backward(); } \
986 \
987 CLASSNAME* extract() \
988 { return (CLASSNAME*) ELIST2_ITERATOR::extract(); } \
989 \
990 CLASSNAME* move_to_first() \
991 { return (CLASSNAME*) ELIST2_ITERATOR::move_to_first(); } \
992 \
993 CLASSNAME* move_to_last() \
994 { return (CLASSNAME*) ELIST2_ITERATOR::move_to_last(); } \
995 };
996
997 #define ELIST2IZEH( CLASSNAME ) \
998 \
999 ELIST2IZEH_A( CLASSNAME ) \
1000 \
1001 ELIST2IZEH_B( CLASSNAME ) \
1002 \
1003 ELIST2IZEH_C( CLASSNAME )
1004
1005
1006 /***********************************************************************
1007 ELIST2IZE( CLASSNAME ) MACRO
1008 ***********************************************************************/
1009
1010 #define ELIST2IZE( CLASSNAME ) \
1011 \
1012 /*********************************************************************** \
1013 * CLASSNAME##_zapper \
1014 * \
1015 * A function which can delete a CLASSNAME element. This is passed to the \
1016 * generic clear list member function so that when a list is cleared the \
1017 * elements on the list are properly destroyed from the base class, even \
1018 * though we dont use a virtual destructor function. \
1019 **********************************************************************/ \
1020 \
1021 DLLSYM void CLASSNAME##_zapper( /*delete a link*/ \
1022 ELIST2_LINK* link) /*link to delete*/ \
1023 { \
1024 delete (CLASSNAME *) link; \
1025 } \
1026 \
1027 /* Become a deep copy of src_list*/ \
1028 void CLASSNAME##_LIST::deep_copy(const CLASSNAME##_LIST* src_list, \
1029 CLASSNAME* (*copier)(const CLASSNAME*)) { \
1030 \
1031 CLASSNAME##_IT from_it(const_cast<CLASSNAME##_LIST*>(src_list)); \
1032 CLASSNAME##_IT to_it(this); \
1033 \
1034 for (from_it.mark_cycle_pt(); !from_it.cycled_list(); from_it.forward()) \
1035 to_it.add_after_then_move((*copier)(from_it.data())); \
1036 }
1037
1038 #endif