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