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