Tesseract  3.02
 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 
85 {
86  friend class ELIST_ITERATOR;
87  friend class ELIST;
88 
89  ELIST_LINK *next;
90 
91  public:
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 
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 
189 {
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 
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 
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 
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 
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 
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 
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 };
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