tesseract  3.04.01
 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 &) { //don't copy link
73  prev = next = NULL;
74  }
75 
76  void operator= ( //don't 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  // Comparison 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); //don't 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 (!list_to_iterate)
268  BAD_PARAMETER.error ("ELIST2_ITERATOR::set_to_list", ABORT,
269  "list_to_iterate is NULL");
270  #endif
271 
272  list = list_to_iterate;
273  prev = list->last;
274  current = list->First ();
275  next = current ? current->next : NULL;
276  cycle_pt = NULL; //await explicit set
277  started_cycling = FALSE;
278  ex_current_was_last = FALSE;
279  ex_current_was_cycle_pt = FALSE;
280 }
281 
282 
283 /***********************************************************************
284  * ELIST2_ITERATOR::ELIST2_ITERATOR
285  *
286  * CONSTRUCTOR - set iterator to specified list;
287  **********************************************************************/
288 
289 inline ELIST2_ITERATOR::ELIST2_ITERATOR(ELIST2 *list_to_iterate) {
290  set_to_list(list_to_iterate);
291 }
292 
293 
294 /***********************************************************************
295  * ELIST2_ITERATOR::add_after_then_move
296  *
297  * Add a new element to the list after the current element and move the
298  * iterator to the new element.
299  **********************************************************************/
300 
301 inline void ELIST2_ITERATOR::add_after_then_move( // element to add
302  ELIST2_LINK *new_element) {
303  #ifndef NDEBUG
304  if (!list)
305  NO_LIST.error ("ELIST2_ITERATOR::add_after_then_move", ABORT, NULL);
306  if (!new_element)
307  BAD_PARAMETER.error ("ELIST2_ITERATOR::add_after_then_move", ABORT,
308  "new_element is NULL");
309  if (new_element->next)
310  STILL_LINKED.error ("ELIST2_ITERATOR::add_after_then_move", ABORT, NULL);
311  #endif
312 
313  if (list->empty ()) {
314  new_element->next = new_element;
315  new_element->prev = new_element;
316  list->last = new_element;
317  prev = next = new_element;
318  }
319  else {
320  new_element->next = next;
321  next->prev = new_element;
322 
323  if (current) { //not extracted
324  new_element->prev = current;
325  current->next = new_element;
326  prev = current;
327  if (current == list->last)
328  list->last = new_element;
329  }
330  else { //current extracted
331  new_element->prev = prev;
332  prev->next = new_element;
333  if (ex_current_was_last)
334  list->last = new_element;
335  if (ex_current_was_cycle_pt)
336  cycle_pt = new_element;
337  }
338  }
339  current = new_element;
340 }
341 
342 
343 /***********************************************************************
344  * ELIST2_ITERATOR::add_after_stay_put
345  *
346  * Add a new element to the list after the current element but do not move
347  * the iterator to the new element.
348  **********************************************************************/
349 
350 inline void ELIST2_ITERATOR::add_after_stay_put( // element to add
351  ELIST2_LINK *new_element) {
352  #ifndef NDEBUG
353  if (!list)
354  NO_LIST.error ("ELIST2_ITERATOR::add_after_stay_put", ABORT, NULL);
355  if (!new_element)
356  BAD_PARAMETER.error ("ELIST2_ITERATOR::add_after_stay_put", ABORT,
357  "new_element is NULL");
358  if (new_element->next)
359  STILL_LINKED.error ("ELIST2_ITERATOR::add_after_stay_put", ABORT, NULL);
360  #endif
361 
362  if (list->empty ()) {
363  new_element->next = new_element;
364  new_element->prev = new_element;
365  list->last = new_element;
366  prev = next = new_element;
367  ex_current_was_last = FALSE;
368  current = NULL;
369  }
370  else {
371  new_element->next = next;
372  next->prev = new_element;
373 
374  if (current) { //not extracted
375  new_element->prev = current;
376  current->next = new_element;
377  if (prev == current)
378  prev = new_element;
379  if (current == list->last)
380  list->last = new_element;
381  }
382  else { //current extracted
383  new_element->prev = prev;
384  prev->next = new_element;
385  if (ex_current_was_last) {
386  list->last = new_element;
387  ex_current_was_last = FALSE;
388  }
389  }
390  next = new_element;
391  }
392 }
393 
394 
395 /***********************************************************************
396  * ELIST2_ITERATOR::add_before_then_move
397  *
398  * Add a new element to the list before the current element and move the
399  * iterator to the new element.
400  **********************************************************************/
401 
402 inline void ELIST2_ITERATOR::add_before_then_move( // element to add
403  ELIST2_LINK *new_element) {
404  #ifndef NDEBUG
405  if (!list)
406  NO_LIST.error ("ELIST2_ITERATOR::add_before_then_move", ABORT, NULL);
407  if (!new_element)
408  BAD_PARAMETER.error ("ELIST2_ITERATOR::add_before_then_move", ABORT,
409  "new_element is NULL");
410  if (new_element->next)
411  STILL_LINKED.error ("ELIST2_ITERATOR::add_before_then_move", ABORT, NULL);
412  #endif
413 
414  if (list->empty ()) {
415  new_element->next = new_element;
416  new_element->prev = new_element;
417  list->last = new_element;
418  prev = next = new_element;
419  }
420  else {
421  prev->next = new_element;
422  new_element->prev = prev;
423 
424  if (current) { //not extracted
425  new_element->next = current;
426  current->prev = new_element;
427  next = current;
428  }
429  else { //current extracted
430  new_element->next = next;
431  next->prev = new_element;
432  if (ex_current_was_last)
433  list->last = new_element;
434  if (ex_current_was_cycle_pt)
435  cycle_pt = new_element;
436  }
437  }
438  current = new_element;
439 }
440 
441 
442 /***********************************************************************
443  * ELIST2_ITERATOR::add_before_stay_put
444  *
445  * Add a new element to the list before the current element but don't move the
446  * iterator to the new element.
447  **********************************************************************/
448 
449 inline void ELIST2_ITERATOR::add_before_stay_put( // element to add
450  ELIST2_LINK *new_element) {
451  #ifndef NDEBUG
452  if (!list)
453  NO_LIST.error ("ELIST2_ITERATOR::add_before_stay_put", ABORT, NULL);
454  if (!new_element)
455  BAD_PARAMETER.error ("ELIST2_ITERATOR::add_before_stay_put", ABORT,
456  "new_element is NULL");
457  if (new_element->next)
458  STILL_LINKED.error ("ELIST2_ITERATOR::add_before_stay_put", ABORT, NULL);
459  #endif
460 
461  if (list->empty ()) {
462  new_element->next = new_element;
463  new_element->prev = new_element;
464  list->last = new_element;
465  prev = next = new_element;
466  ex_current_was_last = TRUE;
467  current = NULL;
468  }
469  else {
470  prev->next = new_element;
471  new_element->prev = prev;
472 
473  if (current) { //not extracted
474  new_element->next = current;
475  current->prev = new_element;
476  if (next == current)
477  next = new_element;
478  }
479  else { //current extracted
480  new_element->next = next;
481  next->prev = new_element;
482  if (ex_current_was_last)
483  list->last = new_element;
484  }
485  prev = new_element;
486  }
487 }
488 
489 
490 /***********************************************************************
491  * ELIST2_ITERATOR::add_list_after
492  *
493  * Insert another list to this list after the current element but don't move the
494  * iterator.
495  **********************************************************************/
496 
497 inline void ELIST2_ITERATOR::add_list_after(ELIST2 *list_to_add) {
498  #ifndef NDEBUG
499  if (!list)
500  NO_LIST.error ("ELIST2_ITERATOR::add_list_after", ABORT, NULL);
501  if (!list_to_add)
502  BAD_PARAMETER.error ("ELIST2_ITERATOR::add_list_after", ABORT,
503  "list_to_add is NULL");
504  #endif
505 
506  if (!list_to_add->empty ()) {
507  if (list->empty ()) {
508  list->last = list_to_add->last;
509  prev = list->last;
510  next = list->First ();
511  ex_current_was_last = TRUE;
512  current = NULL;
513  }
514  else {
515  if (current) { //not extracted
516  current->next = list_to_add->First ();
517  current->next->prev = current;
518  if (current == list->last)
519  list->last = list_to_add->last;
520  list_to_add->last->next = next;
521  next->prev = list_to_add->last;
522  next = current->next;
523  }
524  else { //current extracted
525  prev->next = list_to_add->First ();
526  prev->next->prev = prev;
527  if (ex_current_was_last) {
528  list->last = list_to_add->last;
529  ex_current_was_last = FALSE;
530  }
531  list_to_add->last->next = next;
532  next->prev = list_to_add->last;
533  next = prev->next;
534  }
535  }
536  list_to_add->last = NULL;
537  }
538 }
539 
540 
541 /***********************************************************************
542  * ELIST2_ITERATOR::add_list_before
543  *
544  * Insert another list to this list before the current element. Move the
545  * iterator to the start of the inserted elements
546  * iterator.
547  **********************************************************************/
548 
549 inline void ELIST2_ITERATOR::add_list_before(ELIST2 *list_to_add) {
550  #ifndef NDEBUG
551  if (!list)
552  NO_LIST.error ("ELIST2_ITERATOR::add_list_before", ABORT, NULL);
553  if (!list_to_add)
554  BAD_PARAMETER.error ("ELIST2_ITERATOR::add_list_before", ABORT,
555  "list_to_add is NULL");
556  #endif
557 
558  if (!list_to_add->empty ()) {
559  if (list->empty ()) {
560  list->last = list_to_add->last;
561  prev = list->last;
562  current = list->First ();
563  next = current->next;
564  ex_current_was_last = FALSE;
565  }
566  else {
567  prev->next = list_to_add->First ();
568  prev->next->prev = prev;
569 
570  if (current) { //not extracted
571  list_to_add->last->next = current;
572  current->prev = list_to_add->last;
573  }
574  else { //current extracted
575  list_to_add->last->next = next;
576  next->prev = list_to_add->last;
577  if (ex_current_was_last)
578  list->last = list_to_add->last;
579  if (ex_current_was_cycle_pt)
580  cycle_pt = prev->next;
581  }
582  current = prev->next;
583  next = current->next;
584  }
585  list_to_add->last = NULL;
586  }
587 }
588 
589 
590 /***********************************************************************
591  * ELIST2_ITERATOR::extract
592  *
593  * Do extraction by removing current from the list, returning it to the
594  * caller, but NOT updating the iterator. (So that any calling loop can do
595  * this.) The iterator's current points to NULL. If the extracted element
596  * is to be deleted, this is the callers responsibility.
597  **********************************************************************/
598 
599 inline ELIST2_LINK *ELIST2_ITERATOR::extract() {
600  ELIST2_LINK *extracted_link;
601 
602  #ifndef NDEBUG
603  if (!list)
604  NO_LIST.error ("ELIST2_ITERATOR::extract", ABORT, NULL);
605  if (!current) //list empty or
606  //element extracted
607  NULL_CURRENT.error ("ELIST2_ITERATOR::extract",
608  ABORT, NULL);
609  #endif
610 
611  if (list->singleton()) {
612  // Special case where we do need to change the iterator.
613  prev = next = list->last = NULL;
614  } else {
615  prev->next = next; //remove from list
616  next->prev = prev;
617 
618  if (current == list->last) {
619  list->last = prev;
620  ex_current_was_last = TRUE;
621  } else {
622  ex_current_was_last = FALSE;
623  }
624  }
625  // Always set ex_current_was_cycle_pt so an add/forward will work in a loop.
626  ex_current_was_cycle_pt = (current == cycle_pt) ? TRUE : FALSE;
627  extracted_link = current;
628  extracted_link->next = NULL; //for safety
629  extracted_link->prev = NULL; //for safety
630  current = NULL;
631  return extracted_link;
632 }
633 
634 
635 /***********************************************************************
636  * ELIST2_ITERATOR::move_to_first()
637  *
638  * Move current so that it is set to the start of the list.
639  * Return data just in case anyone wants it.
640  **********************************************************************/
641 
642 inline ELIST2_LINK *ELIST2_ITERATOR::move_to_first() {
643  #ifndef NDEBUG
644  if (!list)
645  NO_LIST.error ("ELIST2_ITERATOR::move_to_first", ABORT, NULL);
646  #endif
647 
648  current = list->First ();
649  prev = list->last;
650  next = current ? current->next : NULL;
651  return current;
652 }
653 
654 
655 /***********************************************************************
656  * ELIST2_ITERATOR::move_to_last()
657  *
658  * Move current so that it is set to the end of the list.
659  * Return data just in case anyone wants it.
660  **********************************************************************/
661 
662 inline ELIST2_LINK *ELIST2_ITERATOR::move_to_last() {
663  #ifndef NDEBUG
664  if (!list)
665  NO_LIST.error ("ELIST2_ITERATOR::move_to_last", ABORT, NULL);
666  #endif
667 
668  current = list->last;
669  prev = current ? current->prev : NULL;
670  next = current ? current->next : NULL;
671  return current;
672 }
673 
674 
675 /***********************************************************************
676  * ELIST2_ITERATOR::mark_cycle_pt()
677  *
678  * Remember the current location so that we can tell whether we've returned
679  * to this point later.
680  *
681  * If the current point is deleted either now, or in the future, the cycle
682  * point will be set to the next item which is set to current. This could be
683  * by a forward, add_after_then_move or add_after_then_move.
684  **********************************************************************/
685 
686 inline void ELIST2_ITERATOR::mark_cycle_pt() {
687  #ifndef NDEBUG
688  if (!list)
689  NO_LIST.error ("ELIST2_ITERATOR::mark_cycle_pt", ABORT, NULL);
690  #endif
691 
692  if (current)
693  cycle_pt = current;
694  else
695  ex_current_was_cycle_pt = TRUE;
696  started_cycling = FALSE;
697 }
698 
699 
700 /***********************************************************************
701  * ELIST2_ITERATOR::at_first()
702  *
703  * Are we at the start of the list?
704  *
705  **********************************************************************/
706 
707 inline BOOL8 ELIST2_ITERATOR::at_first() {
708  #ifndef NDEBUG
709  if (!list)
710  NO_LIST.error ("ELIST2_ITERATOR::at_first", ABORT, NULL);
711  #endif
712 
713  //we're at a deleted
714  return ((list->empty ()) || (current == list->First ()) || ((current == NULL) &&
715  (prev == list->last) && //NON-last pt between
716  !ex_current_was_last)); //first and last
717 }
718 
719 
720 /***********************************************************************
721  * ELIST2_ITERATOR::at_last()
722  *
723  * Are we at the end of the list?
724  *
725  **********************************************************************/
726 
727 inline BOOL8 ELIST2_ITERATOR::at_last() {
728  #ifndef NDEBUG
729  if (!list)
730  NO_LIST.error ("ELIST2_ITERATOR::at_last", ABORT, NULL);
731  #endif
732 
733  //we're at a deleted
734  return ((list->empty ()) || (current == list->last) || ((current == NULL) &&
735  (prev == list->last) && //last point between
736  ex_current_was_last)); //first and last
737 }
738 
739 
740 /***********************************************************************
741  * ELIST2_ITERATOR::cycled_list()
742  *
743  * Have we returned to the cycle_pt since it was set?
744  *
745  **********************************************************************/
746 
747 inline BOOL8 ELIST2_ITERATOR::cycled_list() {
748  #ifndef NDEBUG
749  if (!list)
750  NO_LIST.error ("ELIST2_ITERATOR::cycled_list", ABORT, NULL);
751  #endif
752 
753  return ((list->empty ()) || ((current == cycle_pt) && started_cycling));
754 
755 }
756 
757 
758 /***********************************************************************
759  * ELIST2_ITERATOR::length()
760  *
761  * Return the length of the list
762  *
763  **********************************************************************/
764 
765 inline inT32 ELIST2_ITERATOR::length() {
766  #ifndef NDEBUG
767  if (!list)
768  NO_LIST.error ("ELIST2_ITERATOR::length", ABORT, NULL);
769  #endif
770 
771  return list->length ();
772 }
773 
774 
775 /***********************************************************************
776  * ELIST2_ITERATOR::sort()
777  *
778  * Sort the elements of the list, then reposition at the start.
779  *
780  **********************************************************************/
781 
782 inline void
783 ELIST2_ITERATOR::sort ( //sort elements
784 int comparator ( //comparison routine
785 const void *, const void *)) {
786  #ifndef NDEBUG
787  if (!list)
788  NO_LIST.error ("ELIST2_ITERATOR::sort", ABORT, NULL);
789  #endif
790 
791  list->sort (comparator);
792  move_to_first();
793 }
794 
795 
796 /***********************************************************************
797  * ELIST2_ITERATOR::add_to_end
798  *
799  * Add a new element to the end of the list without moving the iterator.
800  * This is provided because a single linked list cannot move to the last as
801  * the iterator couldn't set its prev pointer. Adding to the end is
802  * essential for implementing
803  queues.
804 **********************************************************************/
805 
806 inline void ELIST2_ITERATOR::add_to_end( // element to add
807  ELIST2_LINK *new_element) {
808  #ifndef NDEBUG
809  if (!list)
810  NO_LIST.error ("ELIST2_ITERATOR::add_to_end", ABORT, NULL);
811  if (!new_element)
812  BAD_PARAMETER.error ("ELIST2_ITERATOR::add_to_end", ABORT,
813  "new_element is NULL");
814  if (new_element->next)
815  STILL_LINKED.error ("ELIST2_ITERATOR::add_to_end", ABORT, NULL);
816  #endif
817 
818  if (this->at_last ()) {
819  this->add_after_stay_put (new_element);
820  }
821  else {
822  if (this->at_first ()) {
823  this->add_before_stay_put (new_element);
824  list->last = new_element;
825  }
826  else { //Iteratr is elsewhere
827  new_element->next = list->last->next;
828  new_element->prev = list->last;
829  list->last->next->prev = new_element;
830  list->last->next = new_element;
831  list->last = new_element;
832  }
833  }
834 }
835 
836 
837 /***********************************************************************
838  QUOTE_IT MACRO DEFINITION
839  ===========================
840 Replace <parm> with "<parm>". <parm> may be an arbitrary number of tokens
841 ***********************************************************************/
842 
843 #define QUOTE_IT( parm ) #parm
844 
845 /***********************************************************************
846  ELIST2IZE( CLASSNAME ) MACRO DEFINITION
847  ======================================
848 
849 CLASSNAME is assumed to be the name of a class which has a baseclass of
850 ELIST2_LINK.
851 
852 NOTE: Because we don't use virtual functions in the list code, the list code
853 will NOT work correctly for classes derived from this.
854 
855 The macro generates:
856  - An element deletion function: CLASSNAME##_zapper
857  - An E_LIST2 subclass: CLASSNAME##_LIST
858  - An E_LIST2_ITERATOR subclass:
859  CLASSNAME##_IT
860 
861 NOTE: Generated names are DELIBERATELY designed to clash with those for
862 ELISTIZE but NOT with those for CLISTIZE and CLIST2IZE
863 
864 Two macros are provided: ELIST2IZE and ELIST2IZEH
865 The ...IZEH macros just define the class names for use in .h files
866 The ...IZE macros define the code use in .c files
867 ***********************************************************************/
868 
869 /***********************************************************************
870  ELIST2IZEH( CLASSNAME ) MACRO
871 
872 ELIST2IZEH is a concatenation of 3 fragments ELIST2IZEH_A, ELIST2IZEH_B and
873 ELIST2IZEH_C.
874 ***********************************************************************/
875 
876 #define ELIST2IZEH_A( CLASSNAME ) \
877  \
878 extern DLLSYM void CLASSNAME##_zapper( /*delete a link*/ \
879 ELIST2_LINK* link); /*link to delete*/
880 
881 #define ELIST2IZEH_B( CLASSNAME ) \
882  \
883 /*********************************************************************** \
884 * CLASS - CLASSNAME##_LIST \
885 * \
886 * List class for class CLASSNAME \
887 * \
888 **********************************************************************/ \
889  \
890 class DLLSYM CLASSNAME##_LIST : public ELIST2 \
891 { \
892 public: \
893  CLASSNAME##_LIST():ELIST2() {} \
894  /* constructor */ \
895  \
896  CLASSNAME##_LIST( /* don't construct */ \
897  const CLASSNAME##_LIST&) /*by initial assign*/\
898  { DONT_CONSTRUCT_LIST_BY_COPY.error( QUOTE_IT( CLASSNAME##_LIST ), \
899  ABORT, NULL ); } \
900  \
901 void clear() /* delete elements */\
902  { ELIST2::internal_clear( &CLASSNAME##_zapper ); } \
903  \
904  ~CLASSNAME##_LIST() /* destructor */ \
905  { clear(); } \
906 \
907 /* Become a deep copy of src_list*/ \
908 void deep_copy(const CLASSNAME##_LIST* src_list, \
909  CLASSNAME* (*copier)(const CLASSNAME*)); \
910 \
911 void operator=( /* prevent assign */ \
912  const CLASSNAME##_LIST&) \
913  { DONT_ASSIGN_LISTS.error( QUOTE_IT( CLASSNAME##_LIST ), \
914  ABORT, NULL ); }
915 
916 #define ELIST2IZEH_C( CLASSNAME ) \
917 }; \
918  \
919  \
920  \
921 /*********************************************************************** \
922 * CLASS - CLASSNAME##_IT \
923 * \
924 * Iterator class for class CLASSNAME##_LIST \
925 * \
926 * Note: We don't need to coerce pointers to member functions input \
927 * parameters as these are automatically converted to the type of the base \
928 * type. ("A ptr to a class may be converted to a pointer to a public base \
929 * class of that class") \
930 **********************************************************************/ \
931  \
932 class DLLSYM CLASSNAME##_IT : public ELIST2_ITERATOR \
933 { \
934 public: \
935  CLASSNAME##_IT():ELIST2_ITERATOR(){} \
936  \
937  CLASSNAME##_IT( \
938 CLASSNAME##_LIST* list):ELIST2_ITERATOR(list){} \
939  \
940  CLASSNAME* data() \
941  { return (CLASSNAME*) ELIST2_ITERATOR::data(); } \
942  \
943  CLASSNAME* data_relative( \
944  inT8 offset) \
945  { return (CLASSNAME*) ELIST2_ITERATOR::data_relative( offset ); } \
946  \
947  CLASSNAME* forward() \
948  { return (CLASSNAME*) ELIST2_ITERATOR::forward(); } \
949  \
950  CLASSNAME* backward() \
951  { return (CLASSNAME*) ELIST2_ITERATOR::backward(); } \
952  \
953  CLASSNAME* extract() \
954  { return (CLASSNAME*) ELIST2_ITERATOR::extract(); } \
955  \
956  CLASSNAME* move_to_first() \
957  { return (CLASSNAME*) ELIST2_ITERATOR::move_to_first(); } \
958  \
959  CLASSNAME* move_to_last() \
960  { return (CLASSNAME*) ELIST2_ITERATOR::move_to_last(); } \
961 };
962 
963 #define ELIST2IZEH( CLASSNAME ) \
964  \
965 ELIST2IZEH_A( CLASSNAME ) \
966  \
967 ELIST2IZEH_B( CLASSNAME ) \
968  \
969 ELIST2IZEH_C( CLASSNAME )
970 
971 
972 /***********************************************************************
973  ELIST2IZE( CLASSNAME ) MACRO
974 ***********************************************************************/
975 
976 #define ELIST2IZE( CLASSNAME ) \
977  \
978 /*********************************************************************** \
979 * CLASSNAME##_zapper \
980 * \
981 * A function which can delete a CLASSNAME element. This is passed to the \
982 * generic clear list member function so that when a list is cleared the \
983 * elements on the list are properly destroyed from the base class, even \
984 * though we don't use a virtual destructor function. \
985 **********************************************************************/ \
986  \
987 DLLSYM void CLASSNAME##_zapper( /*delete a link*/ \
988 ELIST2_LINK* link) /*link to delete*/ \
989 { \
990 delete (CLASSNAME *) link; \
991 } \
992 \
993 /* Become a deep copy of src_list*/ \
994 void CLASSNAME##_LIST::deep_copy(const CLASSNAME##_LIST* src_list, \
995  CLASSNAME* (*copier)(const CLASSNAME*)) { \
996 \
997  CLASSNAME##_IT from_it(const_cast<CLASSNAME##_LIST*>(src_list)); \
998  CLASSNAME##_IT to_it(this); \
999 \
1000  for (from_it.mark_cycle_pt(); !from_it.cycled_list(); from_it.forward()) \
1001  to_it.add_after_then_move((*copier)(from_it.data())); \
1002 }
1003 
1004 #endif
inT32
int inT32
Definition: host.h:102
ELIST2_ITERATOR::empty
BOOL8 empty()
Definition: elst2.h:225
ELIST2_ITERATOR::extract
ELIST2_LINK * extract()
Definition: elst2.h:599
ELIST2::empty
bool empty() const
Definition: elst2.h:107
inT8
SIGNED char inT8
Definition: host.h:98
ELIST2_ITERATOR::sort
void sort(int comparator(const void *, const void *))
Definition: elst2.h:783
ELIST2::singleton
bool singleton() const
Definition: elst2.h:111
ELIST2_ITERATOR::add_list_before
void add_list_before(ELIST2 *list_to_add)
Definition: elst2.h:549
FALSE
#define FALSE
Definition: capi.h:29
ELIST2_ITERATOR::mark_cycle_pt
void mark_cycle_pt()
Definition: elst2.h:686
ELIST2::ELIST2
ELIST2()
Definition: elst2.h:99
ELIST2::sort
void sort(int comparator(const void *, const void *))
Definition: elst2.cpp:111
ELIST2_ITERATOR::add_before_then_move
void add_before_then_move(ELIST2_LINK *new_link)
Definition: elst2.h:402
ELIST2_ITERATOR::ELIST2_ITERATOR
ELIST2_ITERATOR()
Definition: elst2.h:171
ELIST2
Definition: elst2.h:88
ELIST2_ITERATOR::add_list_after
void add_list_after(ELIST2 *list_to_add)
Definition: elst2.h:497
BAD_PARAMETER
const ERRCODE BAD_PARAMETER
Definition: lsterr.h:39
ELIST2_ITERATOR::length
inT32 length()
Definition: elst2.h:765
NO_LIST
const ERRCODE NO_LIST
Definition: lsterr.h:32
STILL_LINKED
const ERRCODE STILL_LINKED
Definition: lsterr.h:40
ELIST2_ITERATOR::add_after_then_move
void add_after_then_move(ELIST2_LINK *new_link)
Definition: elst2.h:301
ELIST2::assign_to_sublist
void assign_to_sublist(ELIST2_ITERATOR *start_it, ELIST2_ITERATOR *end_it)
Definition: elst2.cpp:73
ELIST2_LINK::ELIST2_LINK
ELIST2_LINK()
Definition: elst2.h:67
ELIST2_ITERATOR::add_before_stay_put
void add_before_stay_put(ELIST2_LINK *new_link)
Definition: elst2.h:449
ELIST2::shallow_copy
void shallow_copy(ELIST2 *from_list)
Definition: elst2.h:115
ELIST2_ITERATOR::at_last
BOOL8 at_last()
Definition: elst2.h:727
ELIST2_ITERATOR::current_extracted
BOOL8 current_extracted()
Definition: elst2.h:233
ERRCODE::error
void error(const char *caller, TessErrorLogCode action, const char *format,...) const
Definition: errcode.cpp:40
ELIST2_ITERATOR::data
ELIST2_LINK * data()
Definition: elst2.h:199
list_rec::next
struct list_rec * next
Definition: oldlist.h:130
ELIST2_ITERATOR::move_to_last
ELIST2_LINK * move_to_last()
Definition: elst2.h:662
NULL_DATA
const ERRCODE NULL_DATA
Definition: lsterr.h:34
ELIST2_ITERATOR::set_to_list
void set_to_list(ELIST2 *list_to_iterate)
Definition: elst2.h:264
ABORT
Definition: errcode.h:30
ELIST2_LINK::ELIST2_LINK
ELIST2_LINK(const ELIST2_LINK &)
Definition: elst2.h:71
BOOL8
unsigned char BOOL8
Definition: host.h:113
TRUE
#define TRUE
Definition: capi.h:28
DLLSYM
#define DLLSYM
Definition: platform.h:25
ELIST2::length
inT32 length() const
Definition: elst2.cpp:92
ELIST2_ITERATOR::cycled_list
BOOL8 cycled_list()
Definition: elst2.h:747
ELIST2_ITERATOR::at_first
BOOL8 at_first()
Definition: elst2.h:707
NULL_CURRENT
const ERRCODE NULL_CURRENT
Definition: lsterr.h:35
last
LIST last(LIST var_list)
Definition: oldlist.cpp:277
ELIST2_ITERATOR::move_to_first
ELIST2_LINK * move_to_first()
Definition: elst2.h:642
ELIST2_ITERATOR::add_to_end
void add_to_end(ELIST2_LINK *new_link)
Definition: elst2.h:806
ELIST2_ITERATOR::add_after_stay_put
void add_after_stay_put(ELIST2_LINK *new_link)
Definition: elst2.h:350