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