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