Coverage Report

Created: 2025-06-13 07:15

/src/tesseract/src/ccutil/elst2.h
Line
Count
Source (jump to first uncovered line)
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 "lsterr.h"
23
#include "serialis.h"
24
25
#include <algorithm>
26
#include <cstdio>
27
28
namespace tesseract {
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
50
 *
51
 * Generic list class for doubly linked lists with embedded links
52
 **********************************************************************/
53
54
template <typename T>
55
class IntrusiveList {
56
public:
57
  /**********************************************************************
58
   *              CLASS - Link
59
   *
60
   *              Generic link class for doubly linked lists with embedded links
61
   *
62
   *  Note:  No destructor - elements are assumed to be destroyed EITHER after
63
   *  they have been extracted from a list OR by the ELIST2 destructor which
64
   *  walks the list.
65
   **********************************************************************/
66
67
  class Link {
68
    friend class Iterator;
69
    friend class IntrusiveList;
70
71
    T *prev;
72
    T *next;
73
74
  public:
75
818k
    Link() { // constructor
76
818k
      prev = next = nullptr;
77
818k
    }
tesseract::IntrusiveList<tesseract::WERD>::Link::Link()
Line
Count
Source
75
541k
    Link() { // constructor
76
541k
      prev = next = nullptr;
77
541k
    }
tesseract::IntrusiveList<tesseract::TO_ROW>::Link::Link()
Line
Count
Source
75
277k
    Link() { // constructor
76
277k
      prev = next = nullptr;
77
277k
    }
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Link::Link()
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Link::Link()
78
79
    Link(const Link &) = delete;
80
81
    // The assignment operator is required for WERD.
82
124k
    void operator=(const Link &) {
83
124k
      prev = next = nullptr;
84
124k
    }
85
  };
86
  using LINK = Link; // compat
87
88
  /***********************************************************************
89
   *              CLASS - ELIST2_ITERATOR
90
   *
91
   *              Generic iterator class for doubly linked lists with embedded
92
   *links
93
   **********************************************************************/
94
95
  class Iterator {
96
    friend void IntrusiveList::assign_to_sublist(Iterator *, Iterator *);
97
98
    IntrusiveList *list;                 // List being iterated
99
    T *prev;            // prev element
100
    T *current;         // current element
101
    T *next;            // next element
102
    T *cycle_pt;        // point we are cycling the list to.
103
    bool ex_current_was_last;     // current extracted was end of list
104
    bool ex_current_was_cycle_pt; // current extracted was cycle point
105
    bool started_cycling;         // Have we moved off the start?
106
    /***********************************************************************
107
   *              ELIST2_ITERATOR::extract_sublist()
108
   *
109
   *  This is a private member, used only by IntrusiveList::assign_to_sublist.
110
   *  Given another iterator for the same list, extract the links from THIS to
111
   *  OTHER inclusive, link them into a new circular list, and return a
112
   *  pointer to the last element.
113
   *  (Can't inline this function because it contains a loop)
114
   **********************************************************************/
115
    T *extract_sublist(   // from this current...
116
      Iterator *other_it) {               // to other current
117
#ifndef NDEBUG
118
      constexpr ERRCODE BAD_EXTRACTION_PTS("Can't extract sublist from points on different lists");
119
      constexpr ERRCODE DONT_EXTRACT_DELETED("Can't extract a sublist marked by deleted points");
120
#endif
121
      constexpr ERRCODE BAD_SUBLIST("Can't find sublist end point in original list");
122
123
      Iterator temp_it = *this;
124
      T *end_of_new_list;
125
126
#ifndef NDEBUG
127
      if (!other_it)
128
        BAD_PARAMETER.error("ELIST2_ITERATOR::extract_sublist", ABORT, "other_it nullptr");
129
      if (!list)
130
        NO_LIST.error("ELIST2_ITERATOR::extract_sublist", ABORT);
131
      if (list != other_it->list)
132
        BAD_EXTRACTION_PTS.error("ELIST2_ITERATOR.extract_sublist", ABORT);
133
      if (list->empty())
134
        EMPTY_LIST.error("ELIST2_ITERATOR::extract_sublist", ABORT);
135
136
      if (!current || !other_it->current)
137
        DONT_EXTRACT_DELETED.error("ELIST2_ITERATOR.extract_sublist", ABORT);
138
#endif
139
140
      ex_current_was_last = other_it->ex_current_was_last = false;
141
      ex_current_was_cycle_pt = false;
142
      other_it->ex_current_was_cycle_pt = false;
143
144
      temp_it.mark_cycle_pt();
145
      do {                         // walk sublist
146
        if (temp_it.cycled_list()) { // can't find end pt
147
          BAD_SUBLIST.error("ELIST2_ITERATOR.extract_sublist", ABORT);
148
        }
149
150
        if (temp_it.at_last()) {
151
          list->last = prev;
152
          ex_current_was_last = other_it->ex_current_was_last = true;
153
        }
154
155
        if (temp_it.current == cycle_pt) {
156
          ex_current_was_cycle_pt = true;
157
        }
158
159
        if (temp_it.current == other_it->cycle_pt) {
160
          other_it->ex_current_was_cycle_pt = true;
161
        }
162
163
        temp_it.forward();
164
      }
165
      // do INCLUSIVE list
166
      while (temp_it.prev != other_it->current);
167
168
      // circularise sublist
169
      other_it->current->next = current;
170
      // circularise sublist
171
      current->prev = other_it->current;
172
      end_of_new_list = other_it->current;
173
174
      // sublist = whole list
175
      if (prev == other_it->current) {
176
        list->last = nullptr;
177
        prev = current = next = nullptr;
178
        other_it->prev = other_it->current = other_it->next = nullptr;
179
      } else {
180
        prev->next = other_it->next;
181
        other_it->next->prev = prev;
182
183
        current = other_it->current = nullptr;
184
        next = other_it->next;
185
        other_it->prev = prev;
186
      }
187
      return end_of_new_list;
188
    } // to other current
189
190
  public:
191
    /***********************************************************************
192
   *              ELIST2_ITERATOR::ELIST2_ITERATOR
193
   *
194
   *  CONSTRUCTOR - set iterator to specified list;
195
   **********************************************************************/
196
    Iterator( // constructor
197
2.33M
      IntrusiveList *list_to_iterate) {
198
2.33M
      set_to_list(list_to_iterate);
199
2.33M
    }
tesseract::IntrusiveList<tesseract::WERD>::Iterator::Iterator(tesseract::IntrusiveList<tesseract::WERD>*)
Line
Count
Source
197
1.58M
      IntrusiveList *list_to_iterate) {
198
1.58M
      set_to_list(list_to_iterate);
199
1.58M
    }
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::Iterator(tesseract::IntrusiveList<tesseract::TabVector>*)
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::Iterator(tesseract::IntrusiveList<tesseract::ColPartition>*)
tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::Iterator(tesseract::IntrusiveList<tesseract::TO_ROW>*)
Line
Count
Source
197
747k
      IntrusiveList *list_to_iterate) {
198
747k
      set_to_list(list_to_iterate);
199
747k
    }
200
201
    /***********************************************************************
202
     *              ELIST2_ITERATOR::set_to_list
203
     *
204
     *  (Re-)initialise the iterator to point to the start of the list_to_iterate
205
     *  over.
206
     **********************************************************************/
207
208
    void set_to_list( // change list
209
2.54M
      IntrusiveList *list_to_iterate) {
210
#ifndef NDEBUG
211
      if (!list_to_iterate) {
212
        BAD_PARAMETER.error("ELIST2_ITERATOR::set_to_list", ABORT, "list_to_iterate is nullptr");
213
      }
214
#endif
215
216
2.54M
      list = list_to_iterate;
217
2.54M
      prev = list->last;
218
2.54M
      current = list->First();
219
2.54M
      next = current ? current->next : nullptr;
220
2.54M
      cycle_pt = nullptr; // await explicit set
221
2.54M
      started_cycling = false;
222
2.54M
      ex_current_was_last = false;
223
2.54M
      ex_current_was_cycle_pt = false;
224
2.54M
    }
tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::set_to_list(tesseract::IntrusiveList<tesseract::TO_ROW>*)
Line
Count
Source
209
772k
      IntrusiveList *list_to_iterate) {
210
#ifndef NDEBUG
211
      if (!list_to_iterate) {
212
        BAD_PARAMETER.error("ELIST2_ITERATOR::set_to_list", ABORT, "list_to_iterate is nullptr");
213
      }
214
#endif
215
216
772k
      list = list_to_iterate;
217
772k
      prev = list->last;
218
772k
      current = list->First();
219
772k
      next = current ? current->next : nullptr;
220
772k
      cycle_pt = nullptr; // await explicit set
221
772k
      started_cycling = false;
222
772k
      ex_current_was_last = false;
223
772k
      ex_current_was_cycle_pt = false;
224
772k
    }
tesseract::IntrusiveList<tesseract::WERD>::Iterator::set_to_list(tesseract::IntrusiveList<tesseract::WERD>*)
Line
Count
Source
209
1.76M
      IntrusiveList *list_to_iterate) {
210
#ifndef NDEBUG
211
      if (!list_to_iterate) {
212
        BAD_PARAMETER.error("ELIST2_ITERATOR::set_to_list", ABORT, "list_to_iterate is nullptr");
213
      }
214
#endif
215
216
1.76M
      list = list_to_iterate;
217
1.76M
      prev = list->last;
218
1.76M
      current = list->First();
219
1.76M
      next = current ? current->next : nullptr;
220
1.76M
      cycle_pt = nullptr; // await explicit set
221
1.76M
      started_cycling = false;
222
1.76M
      ex_current_was_last = false;
223
1.76M
      ex_current_was_cycle_pt = false;
224
1.76M
    }
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::set_to_list(tesseract::IntrusiveList<tesseract::TabVector>*)
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::set_to_list(tesseract::IntrusiveList<tesseract::ColPartition>*)
225
    /***********************************************************************
226
   *              ELIST2_ITERATOR::add_after_then_move
227
   *
228
   *  Add a new element to the list after the current element and move the
229
   *  iterator to the new element.
230
   **********************************************************************/
231
    void add_after_then_move(   // add after current &
232
375k
      T *new_element) {
233
#ifndef NDEBUG
234
      if (!list) {
235
        NO_LIST.error("ELIST2_ITERATOR::add_after_then_move", ABORT);
236
      }
237
      if (!new_element) {
238
        BAD_PARAMETER.error("ELIST2_ITERATOR::add_after_then_move", ABORT, "new_element is nullptr");
239
      }
240
      if (new_element->next) {
241
        STILL_LINKED.error("ELIST2_ITERATOR::add_after_then_move", ABORT);
242
      }
243
#endif
244
245
375k
      if (list->empty()) {
246
198k
        new_element->next = new_element;
247
198k
        new_element->prev = new_element;
248
198k
        list->last = new_element;
249
198k
        prev = next = new_element;
250
198k
      } else {
251
176k
        new_element->next = next;
252
176k
        next->prev = new_element;
253
254
176k
        if (current) { // not extracted
255
176k
          new_element->prev = current;
256
176k
          current->next = new_element;
257
176k
          prev = current;
258
176k
          if (current == list->last) {
259
148k
            list->last = new_element;
260
148k
          }
261
176k
        } else { // current extracted
262
0
          new_element->prev = prev;
263
0
          prev->next = new_element;
264
0
          if (ex_current_was_last) {
265
0
            list->last = new_element;
266
0
          }
267
0
          if (ex_current_was_cycle_pt) {
268
0
            cycle_pt = new_element;
269
0
          }
270
0
        }
271
176k
      }
272
375k
      current = new_element;
273
375k
    } // move to new
tesseract::IntrusiveList<tesseract::WERD>::Iterator::add_after_then_move(tesseract::WERD*)
Line
Count
Source
232
287k
      T *new_element) {
233
#ifndef NDEBUG
234
      if (!list) {
235
        NO_LIST.error("ELIST2_ITERATOR::add_after_then_move", ABORT);
236
      }
237
      if (!new_element) {
238
        BAD_PARAMETER.error("ELIST2_ITERATOR::add_after_then_move", ABORT, "new_element is nullptr");
239
      }
240
      if (new_element->next) {
241
        STILL_LINKED.error("ELIST2_ITERATOR::add_after_then_move", ABORT);
242
      }
243
#endif
244
245
287k
      if (list->empty()) {
246
178k
        new_element->next = new_element;
247
178k
        new_element->prev = new_element;
248
178k
        list->last = new_element;
249
178k
        prev = next = new_element;
250
178k
      } else {
251
108k
        new_element->next = next;
252
108k
        next->prev = new_element;
253
254
108k
        if (current) { // not extracted
255
108k
          new_element->prev = current;
256
108k
          current->next = new_element;
257
108k
          prev = current;
258
108k
          if (current == list->last) {
259
108k
            list->last = new_element;
260
108k
          }
261
108k
        } else { // current extracted
262
0
          new_element->prev = prev;
263
0
          prev->next = new_element;
264
0
          if (ex_current_was_last) {
265
0
            list->last = new_element;
266
0
          }
267
0
          if (ex_current_was_cycle_pt) {
268
0
            cycle_pt = new_element;
269
0
          }
270
0
        }
271
108k
      }
272
287k
      current = new_element;
273
287k
    } // move to new
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::add_after_then_move(tesseract::ColPartition*)
tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::add_after_then_move(tesseract::TO_ROW*)
Line
Count
Source
232
87.5k
      T *new_element) {
233
#ifndef NDEBUG
234
      if (!list) {
235
        NO_LIST.error("ELIST2_ITERATOR::add_after_then_move", ABORT);
236
      }
237
      if (!new_element) {
238
        BAD_PARAMETER.error("ELIST2_ITERATOR::add_after_then_move", ABORT, "new_element is nullptr");
239
      }
240
      if (new_element->next) {
241
        STILL_LINKED.error("ELIST2_ITERATOR::add_after_then_move", ABORT);
242
      }
243
#endif
244
245
87.5k
      if (list->empty()) {
246
19.5k
        new_element->next = new_element;
247
19.5k
        new_element->prev = new_element;
248
19.5k
        list->last = new_element;
249
19.5k
        prev = next = new_element;
250
67.9k
      } else {
251
67.9k
        new_element->next = next;
252
67.9k
        next->prev = new_element;
253
254
67.9k
        if (current) { // not extracted
255
67.9k
          new_element->prev = current;
256
67.9k
          current->next = new_element;
257
67.9k
          prev = current;
258
67.9k
          if (current == list->last) {
259
40.1k
            list->last = new_element;
260
40.1k
          }
261
67.9k
        } else { // current extracted
262
0
          new_element->prev = prev;
263
0
          prev->next = new_element;
264
0
          if (ex_current_was_last) {
265
0
            list->last = new_element;
266
0
          }
267
0
          if (ex_current_was_cycle_pt) {
268
0
            cycle_pt = new_element;
269
0
          }
270
0
        }
271
67.9k
      }
272
87.5k
      current = new_element;
273
87.5k
    } // move to new
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::add_after_then_move(tesseract::TabVector*)
274
      /***********************************************************************
275
     *              ELIST2_ITERATOR::add_after_stay_put
276
     *
277
     *  Add a new element to the list after the current element but do not move
278
     *  the iterator to the new element.
279
     **********************************************************************/
280
    void add_after_stay_put(    // add after current &
281
25.3k
      T *new_element) {
282
#ifndef NDEBUG
283
      if (!list) {
284
        NO_LIST.error("ELIST2_ITERATOR::add_after_stay_put", ABORT);
285
      }
286
      if (!new_element) {
287
        BAD_PARAMETER.error("ELIST2_ITERATOR::add_after_stay_put", ABORT, "new_element is nullptr");
288
      }
289
      if (new_element->next) {
290
        STILL_LINKED.error("ELIST2_ITERATOR::add_after_stay_put", ABORT);
291
      }
292
#endif
293
294
25.3k
      if (list->empty()) {
295
25.3k
        new_element->next = new_element;
296
25.3k
        new_element->prev = new_element;
297
25.3k
        list->last = new_element;
298
25.3k
        prev = next = new_element;
299
25.3k
        ex_current_was_last = false;
300
25.3k
        current = nullptr;
301
25.3k
      } else {
302
0
        new_element->next = next;
303
0
        next->prev = new_element;
304
305
0
        if (current) { // not extracted
306
0
          new_element->prev = current;
307
0
          current->next = new_element;
308
0
          if (prev == current) {
309
0
            prev = new_element;
310
0
          }
311
0
          if (current == list->last) {
312
0
            list->last = new_element;
313
0
          }
314
0
        } else { // current extracted
315
0
          new_element->prev = prev;
316
0
          prev->next = new_element;
317
0
          if (ex_current_was_last) {
318
0
            list->last = new_element;
319
0
            ex_current_was_last = false;
320
0
          }
321
0
        }
322
0
        next = new_element;
323
0
      }
324
25.3k
    } // stay at current
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::WERD>::Iterator::add_after_stay_put(tesseract::WERD*)
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::add_after_stay_put(tesseract::ColPartition*)
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::add_after_stay_put(tesseract::TabVector*)
tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::add_after_stay_put(tesseract::TO_ROW*)
Line
Count
Source
281
25.3k
      T *new_element) {
282
#ifndef NDEBUG
283
      if (!list) {
284
        NO_LIST.error("ELIST2_ITERATOR::add_after_stay_put", ABORT);
285
      }
286
      if (!new_element) {
287
        BAD_PARAMETER.error("ELIST2_ITERATOR::add_after_stay_put", ABORT, "new_element is nullptr");
288
      }
289
      if (new_element->next) {
290
        STILL_LINKED.error("ELIST2_ITERATOR::add_after_stay_put", ABORT);
291
      }
292
#endif
293
294
25.3k
      if (list->empty()) {
295
25.3k
        new_element->next = new_element;
296
25.3k
        new_element->prev = new_element;
297
25.3k
        list->last = new_element;
298
25.3k
        prev = next = new_element;
299
25.3k
        ex_current_was_last = false;
300
25.3k
        current = nullptr;
301
25.3k
      } else {
302
0
        new_element->next = next;
303
0
        next->prev = new_element;
304
305
0
        if (current) { // not extracted
306
0
          new_element->prev = current;
307
0
          current->next = new_element;
308
0
          if (prev == current) {
309
0
            prev = new_element;
310
0
          }
311
0
          if (current == list->last) {
312
0
            list->last = new_element;
313
0
          }
314
0
        } else { // current extracted
315
0
          new_element->prev = prev;
316
0
          prev->next = new_element;
317
0
          if (ex_current_was_last) {
318
0
            list->last = new_element;
319
0
            ex_current_was_last = false;
320
0
          }
321
0
        }
322
0
        next = new_element;
323
0
      }
324
25.3k
    } // stay at current
325
      /***********************************************************************
326
     *              ELIST2_ITERATOR::add_before_then_move
327
     *
328
     *  Add a new element to the list before the current element and move the
329
     *  iterator to the new element.
330
     **********************************************************************/
331
    void add_before_then_move(  // add before current &
332
189k
      T *new_element) {
333
#ifndef NDEBUG
334
      if (!list) {
335
        NO_LIST.error("ELIST2_ITERATOR::add_before_then_move", ABORT);
336
      }
337
      if (!new_element) {
338
        BAD_PARAMETER.error("ELIST2_ITERATOR::add_before_then_move", ABORT, "new_element is nullptr");
339
      }
340
      if (new_element->next) {
341
        STILL_LINKED.error("ELIST2_ITERATOR::add_before_then_move", ABORT);
342
      }
343
#endif
344
345
189k
      if (list->empty()) {
346
0
        new_element->next = new_element;
347
0
        new_element->prev = new_element;
348
0
        list->last = new_element;
349
0
        prev = next = new_element;
350
189k
      } else {
351
189k
        prev->next = new_element;
352
189k
        new_element->prev = prev;
353
354
189k
        if (current) { // not extracted
355
189k
          new_element->next = current;
356
189k
          current->prev = new_element;
357
189k
          next = current;
358
189k
        } else { // current extracted
359
0
          new_element->next = next;
360
0
          next->prev = new_element;
361
0
          if (ex_current_was_last) {
362
0
            list->last = new_element;
363
0
          }
364
0
          if (ex_current_was_cycle_pt) {
365
0
            cycle_pt = new_element;
366
0
          }
367
0
        }
368
189k
      }
369
189k
      current = new_element;
370
189k
    } // move to new
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::add_before_then_move(tesseract::TabVector*)
tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::add_before_then_move(tesseract::TO_ROW*)
Line
Count
Source
332
189k
      T *new_element) {
333
#ifndef NDEBUG
334
      if (!list) {
335
        NO_LIST.error("ELIST2_ITERATOR::add_before_then_move", ABORT);
336
      }
337
      if (!new_element) {
338
        BAD_PARAMETER.error("ELIST2_ITERATOR::add_before_then_move", ABORT, "new_element is nullptr");
339
      }
340
      if (new_element->next) {
341
        STILL_LINKED.error("ELIST2_ITERATOR::add_before_then_move", ABORT);
342
      }
343
#endif
344
345
189k
      if (list->empty()) {
346
0
        new_element->next = new_element;
347
0
        new_element->prev = new_element;
348
0
        list->last = new_element;
349
0
        prev = next = new_element;
350
189k
      } else {
351
189k
        prev->next = new_element;
352
189k
        new_element->prev = prev;
353
354
189k
        if (current) { // not extracted
355
189k
          new_element->next = current;
356
189k
          current->prev = new_element;
357
189k
          next = current;
358
189k
        } else { // current extracted
359
0
          new_element->next = next;
360
0
          next->prev = new_element;
361
0
          if (ex_current_was_last) {
362
0
            list->last = new_element;
363
0
          }
364
0
          if (ex_current_was_cycle_pt) {
365
0
            cycle_pt = new_element;
366
0
          }
367
0
        }
368
189k
      }
369
189k
      current = new_element;
370
189k
    } // move to new
371
      /***********************************************************************
372
     *              ELIST2_ITERATOR::add_before_stay_put
373
     *
374
     *  Add a new element to the list before the current element but don't move the
375
     *  iterator to the new element.
376
     **********************************************************************/
377
    void add_before_stay_put(   // add before current &
378
308k
      T *new_element) {
379
#ifndef NDEBUG
380
      if (!list) {
381
        NO_LIST.error("ELIST2_ITERATOR::add_before_stay_put", ABORT);
382
      }
383
      if (!new_element) {
384
        BAD_PARAMETER.error("ELIST2_ITERATOR::add_before_stay_put", ABORT, "new_element is nullptr");
385
      }
386
      if (new_element->next) {
387
        STILL_LINKED.error("ELIST2_ITERATOR::add_before_stay_put", ABORT);
388
      }
389
#endif
390
391
308k
      if (list->empty()) {
392
0
        new_element->next = new_element;
393
0
        new_element->prev = new_element;
394
0
        list->last = new_element;
395
0
        prev = next = new_element;
396
0
        ex_current_was_last = true;
397
0
        current = nullptr;
398
308k
      } else {
399
308k
        prev->next = new_element;
400
308k
        new_element->prev = prev;
401
402
308k
        if (current) { // not extracted
403
14.4k
          new_element->next = current;
404
14.4k
          current->prev = new_element;
405
14.4k
          if (next == current) {
406
0
            next = new_element;
407
0
          }
408
294k
        } else { // current extracted
409
294k
          new_element->next = next;
410
294k
          next->prev = new_element;
411
294k
          if (ex_current_was_last) {
412
0
            list->last = new_element;
413
0
          }
414
294k
        }
415
308k
        prev = new_element;
416
308k
      }
417
308k
    } // stay at current
tesseract::IntrusiveList<tesseract::WERD>::Iterator::add_before_stay_put(tesseract::WERD*)
Line
Count
Source
378
14.4k
      T *new_element) {
379
#ifndef NDEBUG
380
      if (!list) {
381
        NO_LIST.error("ELIST2_ITERATOR::add_before_stay_put", ABORT);
382
      }
383
      if (!new_element) {
384
        BAD_PARAMETER.error("ELIST2_ITERATOR::add_before_stay_put", ABORT, "new_element is nullptr");
385
      }
386
      if (new_element->next) {
387
        STILL_LINKED.error("ELIST2_ITERATOR::add_before_stay_put", ABORT);
388
      }
389
#endif
390
391
14.4k
      if (list->empty()) {
392
0
        new_element->next = new_element;
393
0
        new_element->prev = new_element;
394
0
        list->last = new_element;
395
0
        prev = next = new_element;
396
0
        ex_current_was_last = true;
397
0
        current = nullptr;
398
14.4k
      } else {
399
14.4k
        prev->next = new_element;
400
14.4k
        new_element->prev = prev;
401
402
14.4k
        if (current) { // not extracted
403
14.4k
          new_element->next = current;
404
14.4k
          current->prev = new_element;
405
14.4k
          if (next == current) {
406
0
            next = new_element;
407
0
          }
408
14.4k
        } else { // current extracted
409
0
          new_element->next = next;
410
0
          next->prev = new_element;
411
0
          if (ex_current_was_last) {
412
0
            list->last = new_element;
413
0
          }
414
0
        }
415
14.4k
        prev = new_element;
416
14.4k
      }
417
14.4k
    } // stay at current
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::add_before_stay_put(tesseract::ColPartition*)
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::add_before_stay_put(tesseract::TabVector*)
tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::add_before_stay_put(tesseract::TO_ROW*)
Line
Count
Source
378
294k
      T *new_element) {
379
#ifndef NDEBUG
380
      if (!list) {
381
        NO_LIST.error("ELIST2_ITERATOR::add_before_stay_put", ABORT);
382
      }
383
      if (!new_element) {
384
        BAD_PARAMETER.error("ELIST2_ITERATOR::add_before_stay_put", ABORT, "new_element is nullptr");
385
      }
386
      if (new_element->next) {
387
        STILL_LINKED.error("ELIST2_ITERATOR::add_before_stay_put", ABORT);
388
      }
389
#endif
390
391
294k
      if (list->empty()) {
392
0
        new_element->next = new_element;
393
0
        new_element->prev = new_element;
394
0
        list->last = new_element;
395
0
        prev = next = new_element;
396
0
        ex_current_was_last = true;
397
0
        current = nullptr;
398
294k
      } else {
399
294k
        prev->next = new_element;
400
294k
        new_element->prev = prev;
401
402
294k
        if (current) { // not extracted
403
0
          new_element->next = current;
404
0
          current->prev = new_element;
405
0
          if (next == current) {
406
0
            next = new_element;
407
0
          }
408
294k
        } else { // current extracted
409
294k
          new_element->next = next;
410
294k
          next->prev = new_element;
411
294k
          if (ex_current_was_last) {
412
0
            list->last = new_element;
413
0
          }
414
294k
        }
415
294k
        prev = new_element;
416
294k
      }
417
294k
    } // stay at current
418
      /***********************************************************************
419
     *              ELIST2_ITERATOR::add_list_after
420
     *
421
     *  Insert another list to this list after the current element but don't move
422
     *the
423
     *  iterator.
424
     **********************************************************************/
425
    void add_list_after(      // add a list &
426
178k
      IntrusiveList *list_to_add) {
427
#ifndef NDEBUG
428
      if (!list) {
429
        NO_LIST.error("ELIST2_ITERATOR::add_list_after", ABORT);
430
      }
431
      if (!list_to_add) {
432
        BAD_PARAMETER.error("ELIST2_ITERATOR::add_list_after", ABORT, "list_to_add is nullptr");
433
      }
434
#endif
435
436
178k
      if (!list_to_add->empty()) {
437
178k
        if (list->empty()) {
438
178k
          list->last = list_to_add->last;
439
178k
          prev = list->last;
440
178k
          next = list->First();
441
178k
          ex_current_was_last = true;
442
178k
          current = nullptr;
443
178k
        } else {
444
0
          if (current) { // not extracted
445
0
            current->next = list_to_add->First();
446
0
            current->next->prev = current;
447
0
            if (current == list->last) {
448
0
              list->last = list_to_add->last;
449
0
            }
450
0
            list_to_add->last->next = next;
451
0
            next->prev = list_to_add->last;
452
0
            next = current->next;
453
0
          } else { // current extracted
454
0
            prev->next = list_to_add->First();
455
0
            prev->next->prev = prev;
456
0
            if (ex_current_was_last) {
457
0
              list->last = list_to_add->last;
458
0
              ex_current_was_last = false;
459
0
            }
460
0
            list_to_add->last->next = next;
461
0
            next->prev = list_to_add->last;
462
0
            next = prev->next;
463
0
          }
464
0
        }
465
178k
        list_to_add->last = nullptr;
466
178k
      }
467
178k
    } // stay at current
tesseract::IntrusiveList<tesseract::WERD>::Iterator::add_list_after(tesseract::IntrusiveList<tesseract::WERD>*)
Line
Count
Source
426
178k
      IntrusiveList *list_to_add) {
427
#ifndef NDEBUG
428
      if (!list) {
429
        NO_LIST.error("ELIST2_ITERATOR::add_list_after", ABORT);
430
      }
431
      if (!list_to_add) {
432
        BAD_PARAMETER.error("ELIST2_ITERATOR::add_list_after", ABORT, "list_to_add is nullptr");
433
      }
434
#endif
435
436
178k
      if (!list_to_add->empty()) {
437
178k
        if (list->empty()) {
438
178k
          list->last = list_to_add->last;
439
178k
          prev = list->last;
440
178k
          next = list->First();
441
178k
          ex_current_was_last = true;
442
178k
          current = nullptr;
443
178k
        } else {
444
0
          if (current) { // not extracted
445
0
            current->next = list_to_add->First();
446
0
            current->next->prev = current;
447
0
            if (current == list->last) {
448
0
              list->last = list_to_add->last;
449
0
            }
450
0
            list_to_add->last->next = next;
451
0
            next->prev = list_to_add->last;
452
0
            next = current->next;
453
0
          } else { // current extracted
454
0
            prev->next = list_to_add->First();
455
0
            prev->next->prev = prev;
456
0
            if (ex_current_was_last) {
457
0
              list->last = list_to_add->last;
458
0
              ex_current_was_last = false;
459
0
            }
460
0
            list_to_add->last->next = next;
461
0
            next->prev = list_to_add->last;
462
0
            next = prev->next;
463
0
          }
464
0
        }
465
178k
        list_to_add->last = nullptr;
466
178k
      }
467
178k
    } // stay at current
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::add_list_after(tesseract::IntrusiveList<tesseract::TabVector>*)
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::add_list_after(tesseract::IntrusiveList<tesseract::ColPartition>*)
468
      /***********************************************************************
469
     *              ELIST2_ITERATOR::add_list_before
470
     *
471
     *  Insert another list to this list before the current element. Move the
472
     *  iterator to the start of the inserted elements
473
     *  iterator.
474
     **********************************************************************/
475
    void add_list_before(     // add a list &
476
      IntrusiveList *list_to_add) {
477
#ifndef NDEBUG
478
      if (!list) {
479
        NO_LIST.error("ELIST2_ITERATOR::add_list_before", ABORT);
480
      }
481
      if (!list_to_add) {
482
        BAD_PARAMETER.error("ELIST2_ITERATOR::add_list_before", ABORT, "list_to_add is nullptr");
483
      }
484
#endif
485
486
      if (!list_to_add->empty()) {
487
        if (list->empty()) {
488
          list->last = list_to_add->last;
489
          prev = list->last;
490
          current = list->First();
491
          next = current->next;
492
          ex_current_was_last = false;
493
        } else {
494
          prev->next = list_to_add->First();
495
          prev->next->prev = prev;
496
497
          if (current) { // not extracted
498
            list_to_add->last->next = current;
499
            current->prev = list_to_add->last;
500
          } else { // current extracted
501
            list_to_add->last->next = next;
502
            next->prev = list_to_add->last;
503
            if (ex_current_was_last) {
504
              list->last = list_to_add->last;
505
            }
506
            if (ex_current_was_cycle_pt) {
507
              cycle_pt = prev->next;
508
            }
509
          }
510
          current = prev->next;
511
          next = current->next;
512
        }
513
        list_to_add->last = nullptr;
514
      }
515
    } // move to it 1st item
516
517
124M
    T *data() { // get current data
518
#ifndef NDEBUG
519
      if (!current) {
520
        NULL_DATA.error("ELIST2_ITERATOR::data", ABORT);
521
      }
522
      if (!list) {
523
        NO_LIST.error("ELIST2_ITERATOR::data", ABORT);
524
      }
525
#endif
526
124M
      return current;
527
124M
    }
tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::data()
Line
Count
Source
517
122M
    T *data() { // get current data
518
#ifndef NDEBUG
519
      if (!current) {
520
        NULL_DATA.error("ELIST2_ITERATOR::data", ABORT);
521
      }
522
      if (!list) {
523
        NO_LIST.error("ELIST2_ITERATOR::data", ABORT);
524
      }
525
#endif
526
122M
      return current;
527
122M
    }
tesseract::IntrusiveList<tesseract::WERD>::Iterator::data()
Line
Count
Source
517
2.36M
    T *data() { // get current data
518
#ifndef NDEBUG
519
      if (!current) {
520
        NULL_DATA.error("ELIST2_ITERATOR::data", ABORT);
521
      }
522
      if (!list) {
523
        NO_LIST.error("ELIST2_ITERATOR::data", ABORT);
524
      }
525
#endif
526
2.36M
      return current;
527
2.36M
    }
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::data()
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::data()
528
    /***********************************************************************
529
   *              ELIST2_ITERATOR::data_relative
530
   *
531
   *  Return the data pointer to the element "offset" elements from current.
532
   *  (This function can't be INLINEd because it contains a loop)
533
   **********************************************************************/
534
    T *data_relative( // get data + or - ...
535
8.65M
      int8_t offset) {                         // offset from current
536
8.65M
      T *ptr;
537
538
#ifndef NDEBUG
539
      if (!list)
540
        NO_LIST.error("ELIST2_ITERATOR::data_relative", ABORT);
541
      if (list->empty())
542
        EMPTY_LIST.error("ELIST2_ITERATOR::data_relative", ABORT);
543
#endif
544
545
8.65M
      if (offset < 0) {
546
8.86M
        for (ptr = current ? current : next; offset++ < 0; ptr = ptr->prev) {
547
4.43M
          ;
548
4.43M
        }
549
4.43M
      } else {
550
8.45M
        for (ptr = current ? current : prev; offset-- > 0; ptr = ptr->next) {
551
4.22M
          ;
552
4.22M
        }
553
4.22M
      }
554
555
#ifndef NDEBUG
556
      if (!ptr)
557
        NULL_DATA.error("ELIST2_ITERATOR::data_relative", ABORT);
558
#endif
559
560
8.65M
      return ptr;
561
8.65M
    }         // offset from current
tesseract::IntrusiveList<tesseract::WERD>::Iterator::data_relative(signed char)
Line
Count
Source
535
207k
      int8_t offset) {                         // offset from current
536
207k
      T *ptr;
537
538
#ifndef NDEBUG
539
      if (!list)
540
        NO_LIST.error("ELIST2_ITERATOR::data_relative", ABORT);
541
      if (list->empty())
542
        EMPTY_LIST.error("ELIST2_ITERATOR::data_relative", ABORT);
543
#endif
544
545
207k
      if (offset < 0) {
546
0
        for (ptr = current ? current : next; offset++ < 0; ptr = ptr->prev) {
547
0
          ;
548
0
        }
549
207k
      } else {
550
415k
        for (ptr = current ? current : prev; offset-- > 0; ptr = ptr->next) {
551
207k
          ;
552
207k
        }
553
207k
      }
554
555
#ifndef NDEBUG
556
      if (!ptr)
557
        NULL_DATA.error("ELIST2_ITERATOR::data_relative", ABORT);
558
#endif
559
560
207k
      return ptr;
561
207k
    }         // offset from current
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::data_relative(signed char)
tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::data_relative(signed char)
Line
Count
Source
535
8.45M
      int8_t offset) {                         // offset from current
536
8.45M
      T *ptr;
537
538
#ifndef NDEBUG
539
      if (!list)
540
        NO_LIST.error("ELIST2_ITERATOR::data_relative", ABORT);
541
      if (list->empty())
542
        EMPTY_LIST.error("ELIST2_ITERATOR::data_relative", ABORT);
543
#endif
544
545
8.45M
      if (offset < 0) {
546
8.86M
        for (ptr = current ? current : next; offset++ < 0; ptr = ptr->prev) {
547
4.43M
          ;
548
4.43M
        }
549
4.43M
      } else {
550
8.03M
        for (ptr = current ? current : prev; offset-- > 0; ptr = ptr->next) {
551
4.02M
          ;
552
4.02M
        }
553
4.01M
      }
554
555
#ifndef NDEBUG
556
      if (!ptr)
557
        NULL_DATA.error("ELIST2_ITERATOR::data_relative", ABORT);
558
#endif
559
560
8.45M
      return ptr;
561
8.45M
    }         // offset from current
562
      /***********************************************************************
563
     *              ELIST2_ITERATOR::forward
564
     *
565
     *  Move the iterator to the next element of the list.
566
     *  REMEMBER: ALL LISTS ARE CIRCULAR.
567
     **********************************************************************/
568
91.2M
    T *forward() {
569
#ifndef NDEBUG
570
      if (!list)
571
        NO_LIST.error("ELIST2_ITERATOR::forward", ABORT);
572
#endif
573
91.2M
      if (list->empty()) {
574
35.2k
        return nullptr;
575
35.2k
      }
576
577
91.2M
      if (current) { // not removed so
578
        // set previous
579
90.8M
        prev = current;
580
90.8M
        started_cycling = true;
581
        // In case next is deleted by another iterator, get it from the current.
582
90.8M
        current = current->next;
583
90.8M
      } else {
584
389k
        if (ex_current_was_cycle_pt) {
585
342k
          cycle_pt = next;
586
342k
        }
587
389k
        current = next;
588
389k
      }
589
590
#ifndef NDEBUG
591
      if (!current)
592
        NULL_DATA.error("ELIST2_ITERATOR::forward", ABORT);
593
#endif
594
595
91.2M
      next = current->next;
596
597
#ifndef NDEBUG
598
      if (!next) {
599
        NULL_NEXT.error("ELIST2_ITERATOR::forward", ABORT,
600
          "This is: %p  Current is: %p",
601
          static_cast<void *>(this),
602
          static_cast<void *>(current));
603
      }
604
#endif
605
606
91.2M
      return current;
607
91.2M
    } // move to next element
tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::forward()
Line
Count
Source
568
88.8M
    T *forward() {
569
#ifndef NDEBUG
570
      if (!list)
571
        NO_LIST.error("ELIST2_ITERATOR::forward", ABORT);
572
#endif
573
88.8M
      if (list->empty()) {
574
29.8k
        return nullptr;
575
29.8k
      }
576
577
88.8M
      if (current) { // not removed so
578
        // set previous
579
88.4M
        prev = current;
580
88.4M
        started_cycling = true;
581
        // In case next is deleted by another iterator, get it from the current.
582
88.4M
        current = current->next;
583
88.4M
      } else {
584
387k
        if (ex_current_was_cycle_pt) {
585
341k
          cycle_pt = next;
586
341k
        }
587
387k
        current = next;
588
387k
      }
589
590
#ifndef NDEBUG
591
      if (!current)
592
        NULL_DATA.error("ELIST2_ITERATOR::forward", ABORT);
593
#endif
594
595
88.8M
      next = current->next;
596
597
#ifndef NDEBUG
598
      if (!next) {
599
        NULL_NEXT.error("ELIST2_ITERATOR::forward", ABORT,
600
          "This is: %p  Current is: %p",
601
          static_cast<void *>(this),
602
          static_cast<void *>(current));
603
      }
604
#endif
605
606
88.8M
      return current;
607
88.8M
    } // move to next element
tesseract::IntrusiveList<tesseract::WERD>::Iterator::forward()
Line
Count
Source
568
2.41M
    T *forward() {
569
#ifndef NDEBUG
570
      if (!list)
571
        NO_LIST.error("ELIST2_ITERATOR::forward", ABORT);
572
#endif
573
2.41M
      if (list->empty()) {
574
5.42k
        return nullptr;
575
5.42k
      }
576
577
2.41M
      if (current) { // not removed so
578
        // set previous
579
2.40M
        prev = current;
580
2.40M
        started_cycling = true;
581
        // In case next is deleted by another iterator, get it from the current.
582
2.40M
        current = current->next;
583
2.40M
      } else {
584
1.55k
        if (ex_current_was_cycle_pt) {
585
603
          cycle_pt = next;
586
603
        }
587
1.55k
        current = next;
588
1.55k
      }
589
590
#ifndef NDEBUG
591
      if (!current)
592
        NULL_DATA.error("ELIST2_ITERATOR::forward", ABORT);
593
#endif
594
595
2.41M
      next = current->next;
596
597
#ifndef NDEBUG
598
      if (!next) {
599
        NULL_NEXT.error("ELIST2_ITERATOR::forward", ABORT,
600
          "This is: %p  Current is: %p",
601
          static_cast<void *>(this),
602
          static_cast<void *>(current));
603
      }
604
#endif
605
606
2.41M
      return current;
607
2.41M
    } // move to next element
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::forward()
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::forward()
608
      /***********************************************************************
609
     *              ELIST2_ITERATOR::backward
610
     *
611
     *  Move the iterator to the previous element of the list.
612
     *  REMEMBER: ALL LISTS ARE CIRCULAR.
613
     **********************************************************************/
614
7.07M
    T *backward() {
615
#ifndef NDEBUG
616
      if (!list)
617
        NO_LIST.error("ELIST2_ITERATOR::backward", ABORT);
618
#endif
619
7.07M
      if (list->empty()) {
620
0
        return nullptr;
621
0
      }
622
623
7.07M
      if (current) { // not removed so
624
        // set previous
625
7.07M
        next = current;
626
7.07M
        started_cycling = true;
627
        // In case prev is deleted by another iterator, get it from current.
628
7.07M
        current = current->prev;
629
7.07M
      } else {
630
243
        if (ex_current_was_cycle_pt) {
631
0
          cycle_pt = prev;
632
0
        }
633
243
        current = prev;
634
243
      }
635
636
#ifndef NDEBUG
637
      if (!current)
638
        NULL_DATA.error("ELIST2_ITERATOR::backward", ABORT);
639
      if (!prev) {
640
        NULL_PREV.error("ELIST2_ITERATOR::backward", ABORT,
641
          "This is: %p  Current is: %p",
642
          static_cast<void *>(this),
643
          static_cast<void *>(current));
644
      }
645
#endif
646
647
7.07M
      prev = current->prev;
648
7.07M
      return current;
649
7.07M
    } // move to prev element
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::backward()
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::backward()
tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::backward()
Line
Count
Source
614
7.07M
    T *backward() {
615
#ifndef NDEBUG
616
      if (!list)
617
        NO_LIST.error("ELIST2_ITERATOR::backward", ABORT);
618
#endif
619
7.07M
      if (list->empty()) {
620
0
        return nullptr;
621
0
      }
622
623
7.07M
      if (current) { // not removed so
624
        // set previous
625
7.07M
        next = current;
626
7.07M
        started_cycling = true;
627
        // In case prev is deleted by another iterator, get it from current.
628
7.07M
        current = current->prev;
629
7.07M
      } else {
630
243
        if (ex_current_was_cycle_pt) {
631
0
          cycle_pt = prev;
632
0
        }
633
243
        current = prev;
634
243
      }
635
636
#ifndef NDEBUG
637
      if (!current)
638
        NULL_DATA.error("ELIST2_ITERATOR::backward", ABORT);
639
      if (!prev) {
640
        NULL_PREV.error("ELIST2_ITERATOR::backward", ABORT,
641
          "This is: %p  Current is: %p",
642
          static_cast<void *>(this),
643
          static_cast<void *>(current));
644
      }
645
#endif
646
647
7.07M
      prev = current->prev;
648
7.07M
      return current;
649
7.07M
    } // move to prev element
650
      /***********************************************************************
651
     *              ELIST2_ITERATOR::extract
652
     *
653
     *  Do extraction by removing current from the list, returning it to the
654
     *  caller, but NOT updating the iterator.  (So that any calling loop can do
655
     *  this.)   The iterator's current points to nullptr.  If the extracted element
656
     *  is to be deleted, this is the callers responsibility.
657
     **********************************************************************/
658
439k
    T *extract() {
659
439k
      T *extracted_link;
660
661
#ifndef NDEBUG
662
      if (!list) {
663
        NO_LIST.error("ELIST2_ITERATOR::extract", ABORT);
664
      }
665
      if (!current) { // list empty or
666
        // element extracted
667
        NULL_CURRENT.error("ELIST2_ITERATOR::extract", ABORT);
668
      }
669
#endif
670
671
439k
      if (list->singleton()) {
672
        // Special case where we do need to change the iterator.
673
35.2k
        prev = next = list->last = nullptr;
674
404k
      } else {
675
404k
        prev->next = next; // remove from list
676
404k
        next->prev = prev;
677
678
404k
        if (current == list->last) {
679
8.42k
          list->last = prev;
680
8.42k
          ex_current_was_last = true;
681
395k
        } else {
682
395k
          ex_current_was_last = false;
683
395k
        }
684
404k
      }
685
      // Always set ex_current_was_cycle_pt so an add/forward will work in a loop.
686
439k
      ex_current_was_cycle_pt = (current == cycle_pt);
687
439k
      extracted_link = current;
688
439k
      extracted_link->next = nullptr; // for safety
689
439k
      extracted_link->prev = nullptr; // for safety
690
439k
      current = nullptr;
691
439k
      return extracted_link;
692
439k
    } // remove from list
tesseract::IntrusiveList<tesseract::WERD>::Iterator::extract()
Line
Count
Source
658
21.3k
    T *extract() {
659
21.3k
      T *extracted_link;
660
661
#ifndef NDEBUG
662
      if (!list) {
663
        NO_LIST.error("ELIST2_ITERATOR::extract", ABORT);
664
      }
665
      if (!current) { // list empty or
666
        // element extracted
667
        NULL_CURRENT.error("ELIST2_ITERATOR::extract", ABORT);
668
      }
669
#endif
670
671
21.3k
      if (list->singleton()) {
672
        // Special case where we do need to change the iterator.
673
5.42k
        prev = next = list->last = nullptr;
674
15.9k
      } else {
675
15.9k
        prev->next = next; // remove from list
676
15.9k
        next->prev = prev;
677
678
15.9k
        if (current == list->last) {
679
5.92k
          list->last = prev;
680
5.92k
          ex_current_was_last = true;
681
10.0k
        } else {
682
10.0k
          ex_current_was_last = false;
683
10.0k
        }
684
15.9k
      }
685
      // Always set ex_current_was_cycle_pt so an add/forward will work in a loop.
686
21.3k
      ex_current_was_cycle_pt = (current == cycle_pt);
687
21.3k
      extracted_link = current;
688
21.3k
      extracted_link->next = nullptr; // for safety
689
21.3k
      extracted_link->prev = nullptr; // for safety
690
21.3k
      current = nullptr;
691
21.3k
      return extracted_link;
692
21.3k
    } // remove from list
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::extract()
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::extract()
tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::extract()
Line
Count
Source
658
417k
    T *extract() {
659
417k
      T *extracted_link;
660
661
#ifndef NDEBUG
662
      if (!list) {
663
        NO_LIST.error("ELIST2_ITERATOR::extract", ABORT);
664
      }
665
      if (!current) { // list empty or
666
        // element extracted
667
        NULL_CURRENT.error("ELIST2_ITERATOR::extract", ABORT);
668
      }
669
#endif
670
671
417k
      if (list->singleton()) {
672
        // Special case where we do need to change the iterator.
673
29.8k
        prev = next = list->last = nullptr;
674
388k
      } else {
675
388k
        prev->next = next; // remove from list
676
388k
        next->prev = prev;
677
678
388k
        if (current == list->last) {
679
2.50k
          list->last = prev;
680
2.50k
          ex_current_was_last = true;
681
385k
        } else {
682
385k
          ex_current_was_last = false;
683
385k
        }
684
388k
      }
685
      // Always set ex_current_was_cycle_pt so an add/forward will work in a loop.
686
417k
      ex_current_was_cycle_pt = (current == cycle_pt);
687
417k
      extracted_link = current;
688
417k
      extracted_link->next = nullptr; // for safety
689
417k
      extracted_link->prev = nullptr; // for safety
690
417k
      current = nullptr;
691
417k
      return extracted_link;
692
417k
    } // remove from list
693
      /***********************************************************************
694
     *              ELIST2_ITERATOR::move_to_first()
695
     *
696
     *  Move current so that it is set to the start of the list.
697
     *  Return data just in case anyone wants it.
698
     **********************************************************************/
699
     // go to start of list
700
4.98M
    T *move_to_first() {
701
#ifndef NDEBUG
702
      if (!list) {
703
        NO_LIST.error("ELIST2_ITERATOR::move_to_first", ABORT);
704
      }
705
#endif
706
707
4.98M
      current = list->First();
708
4.98M
      prev = list->last;
709
4.98M
      next = current ? current->next : nullptr;
710
4.98M
      return current;
711
4.98M
    }
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::WERD>::Iterator::move_to_first()
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::move_to_first()
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::move_to_first()
tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::move_to_first()
Line
Count
Source
700
4.98M
    T *move_to_first() {
701
#ifndef NDEBUG
702
      if (!list) {
703
        NO_LIST.error("ELIST2_ITERATOR::move_to_first", ABORT);
704
      }
705
#endif
706
707
4.98M
      current = list->First();
708
4.98M
      prev = list->last;
709
4.98M
      next = current ? current->next : nullptr;
710
4.98M
      return current;
711
4.98M
    }
712
    /***********************************************************************
713
   *              ELIST2_ITERATOR::move_to_last()
714
   *
715
   *  Move current so that it is set to the end of the list.
716
   *  Return data just in case anyone wants it.
717
   **********************************************************************/
718
20.9k
    T *move_to_last() {
719
#ifndef NDEBUG
720
      if (!list) {
721
        NO_LIST.error("ELIST2_ITERATOR::move_to_last", ABORT);
722
      }
723
#endif
724
725
20.9k
      current = list->last;
726
20.9k
      prev = current ? current->prev : nullptr;
727
20.9k
      next = current ? current->next : nullptr;
728
20.9k
      return current;
729
20.9k
    } // go to end of list
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::move_to_last()
tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::move_to_last()
Line
Count
Source
718
20.9k
    T *move_to_last() {
719
#ifndef NDEBUG
720
      if (!list) {
721
        NO_LIST.error("ELIST2_ITERATOR::move_to_last", ABORT);
722
      }
723
#endif
724
725
20.9k
      current = list->last;
726
20.9k
      prev = current ? current->prev : nullptr;
727
20.9k
      next = current ? current->next : nullptr;
728
20.9k
      return current;
729
20.9k
    } // go to end of list
730
      /***********************************************************************
731
     *              ELIST2_ITERATOR::mark_cycle_pt()
732
     *
733
     *  Remember the current location so that we can tell whether we've returned
734
     *  to this point later.
735
     *
736
     *  If the current point is deleted either now, or in the future, the cycle
737
     *  point will be set to the next item which is set to current.  This could be
738
     *  by a forward, add_after_then_move or add_after_then_move.
739
     **********************************************************************/
740
2.18M
    void mark_cycle_pt() {
741
#ifndef NDEBUG
742
      if (!list) {
743
        NO_LIST.error("ELIST2_ITERATOR::mark_cycle_pt", ABORT);
744
      }
745
#endif
746
747
2.18M
      if (current) {
748
2.16M
        cycle_pt = current;
749
2.16M
      } else {
750
26.5k
        ex_current_was_cycle_pt = true;
751
26.5k
      }
752
2.18M
      started_cycling = false;
753
2.18M
    } // remember current
tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::mark_cycle_pt()
Line
Count
Source
740
786k
    void mark_cycle_pt() {
741
#ifndef NDEBUG
742
      if (!list) {
743
        NO_LIST.error("ELIST2_ITERATOR::mark_cycle_pt", ABORT);
744
      }
745
#endif
746
747
786k
      if (current) {
748
759k
        cycle_pt = current;
749
759k
      } else {
750
26.5k
        ex_current_was_cycle_pt = true;
751
26.5k
      }
752
786k
      started_cycling = false;
753
786k
    } // remember current
tesseract::IntrusiveList<tesseract::WERD>::Iterator::mark_cycle_pt()
Line
Count
Source
740
1.40M
    void mark_cycle_pt() {
741
#ifndef NDEBUG
742
      if (!list) {
743
        NO_LIST.error("ELIST2_ITERATOR::mark_cycle_pt", ABORT);
744
      }
745
#endif
746
747
1.40M
      if (current) {
748
1.40M
        cycle_pt = current;
749
1.40M
      } else {
750
0
        ex_current_was_cycle_pt = true;
751
0
      }
752
1.40M
      started_cycling = false;
753
1.40M
    } // remember current
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::mark_cycle_pt()
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::mark_cycle_pt()
754
755
5.81M
    bool empty() const { // is list empty?
756
#ifndef NDEBUG
757
      if (!list) {
758
        NO_LIST.error("ELIST2_ITERATOR::empty", ABORT);
759
      }
760
#endif
761
5.81M
      return list->empty();
762
5.81M
    }
tesseract::IntrusiveList<tesseract::WERD>::Iterator::empty() const
Line
Count
Source
755
722k
    bool empty() const { // is list empty?
756
#ifndef NDEBUG
757
      if (!list) {
758
        NO_LIST.error("ELIST2_ITERATOR::empty", ABORT);
759
      }
760
#endif
761
722k
      return list->empty();
762
722k
    }
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::empty() const
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::empty() const
tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::empty() const
Line
Count
Source
755
5.09M
    bool empty() const { // is list empty?
756
#ifndef NDEBUG
757
      if (!list) {
758
        NO_LIST.error("ELIST2_ITERATOR::empty", ABORT);
759
      }
760
#endif
761
5.09M
      return list->empty();
762
5.09M
    }
763
764
    bool current_extracted() const { // current extracted?
765
      return !current;
766
    }
767
    /***********************************************************************
768
   *              ELIST2_ITERATOR::at_first()
769
   *
770
   *  Are we at the start of the list?
771
   *
772
   **********************************************************************/
773
5.36M
    bool at_first() const {
774
#ifndef NDEBUG
775
      if (!list) {
776
        NO_LIST.error("ELIST2_ITERATOR::at_first", ABORT);
777
      }
778
#endif
779
780
      // we're at a deleted
781
5.36M
      return ((list->empty()) || (current == list->First()) ||
782
5.36M
        ((current == nullptr) && (prev == list->last) && // NON-last pt between
783
4.57M
          !ex_current_was_last));                         // first and last
784
5.36M
    } // Current is first?
tesseract::IntrusiveList<tesseract::WERD>::Iterator::at_first() const
Line
Count
Source
773
607k
    bool at_first() const {
774
#ifndef NDEBUG
775
      if (!list) {
776
        NO_LIST.error("ELIST2_ITERATOR::at_first", ABORT);
777
      }
778
#endif
779
780
      // we're at a deleted
781
607k
      return ((list->empty()) || (current == list->First()) ||
782
607k
        ((current == nullptr) && (prev == list->last) && // NON-last pt between
783
225k
          !ex_current_was_last));                         // first and last
784
607k
    } // Current is first?
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::at_first() const
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::at_first() const
tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::at_first() const
Line
Count
Source
773
4.75M
    bool at_first() const {
774
#ifndef NDEBUG
775
      if (!list) {
776
        NO_LIST.error("ELIST2_ITERATOR::at_first", ABORT);
777
      }
778
#endif
779
780
      // we're at a deleted
781
4.75M
      return ((list->empty()) || (current == list->First()) ||
782
4.75M
        ((current == nullptr) && (prev == list->last) && // NON-last pt between
783
4.34M
          !ex_current_was_last));                         // first and last
784
4.75M
    } // Current is first?
785
      /***********************************************************************
786
     *              ELIST2_ITERATOR::at_last()
787
     *
788
     *  Are we at the end of the list?
789
     *
790
     **********************************************************************/
791
98.0M
    bool at_last() const {
792
#ifndef NDEBUG
793
      if (!list) {
794
        NO_LIST.error("ELIST2_ITERATOR::at_last", ABORT);
795
      }
796
#endif
797
798
      // we're at a deleted
799
98.0M
      return ((list->empty()) || (current == list->last) ||
800
98.0M
        ((current == nullptr) && (prev == list->last) && // last point between
801
96.1M
          ex_current_was_last));                          // first and last
802
98.0M
    } // Current is last?
tesseract::IntrusiveList<tesseract::WERD>::Iterator::at_last() const
Line
Count
Source
791
294k
    bool at_last() const {
792
#ifndef NDEBUG
793
      if (!list) {
794
        NO_LIST.error("ELIST2_ITERATOR::at_last", ABORT);
795
      }
796
#endif
797
798
      // we're at a deleted
799
294k
      return ((list->empty()) || (current == list->last) ||
800
294k
        ((current == nullptr) && (prev == list->last) && // last point between
801
109k
          ex_current_was_last));                          // first and last
802
294k
    } // Current is last?
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::at_last() const
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::at_last() const
tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::at_last() const
Line
Count
Source
791
97.7M
    bool at_last() const {
792
#ifndef NDEBUG
793
      if (!list) {
794
        NO_LIST.error("ELIST2_ITERATOR::at_last", ABORT);
795
      }
796
#endif
797
798
      // we're at a deleted
799
97.7M
      return ((list->empty()) || (current == list->last) ||
800
97.7M
        ((current == nullptr) && (prev == list->last) && // last point between
801
96.0M
          ex_current_was_last));                          // first and last
802
97.7M
    } // Current is last?
803
      /***********************************************************************
804
     *              ELIST2_ITERATOR::cycled_list()
805
     *
806
     *  Have we returned to the cycle_pt since it was set?
807
     *
808
     **********************************************************************/
809
15.1M
    bool cycled_list() const {
810
#ifndef NDEBUG
811
      if (!list) {
812
        NO_LIST.error("ELIST2_ITERATOR::cycled_list", ABORT);
813
      }
814
#endif
815
816
15.1M
      return ((list->empty()) || ((current == cycle_pt) && started_cycling));
817
15.1M
    } // Completed a cycle?
tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::cycled_list() const
Line
Count
Source
809
11.6M
    bool cycled_list() const {
810
#ifndef NDEBUG
811
      if (!list) {
812
        NO_LIST.error("ELIST2_ITERATOR::cycled_list", ABORT);
813
      }
814
#endif
815
816
11.6M
      return ((list->empty()) || ((current == cycle_pt) && started_cycling));
817
11.6M
    } // Completed a cycle?
tesseract::IntrusiveList<tesseract::WERD>::Iterator::cycled_list() const
Line
Count
Source
809
3.54M
    bool cycled_list() const {
810
#ifndef NDEBUG
811
      if (!list) {
812
        NO_LIST.error("ELIST2_ITERATOR::cycled_list", ABORT);
813
      }
814
#endif
815
816
3.54M
      return ((list->empty()) || ((current == cycle_pt) && started_cycling));
817
3.54M
    } // Completed a cycle?
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::cycled_list() const
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::cycled_list() const
818
      /***********************************************************************
819
     *              ELIST2_ITERATOR::add_to_end
820
     *
821
     *  Add a new element to the end of the list without moving the iterator.
822
     *  This is provided because a single linked list cannot move to the last as
823
     *  the iterator couldn't set its prev pointer.  Adding to the end is
824
     *  essential for implementing
825
                  queues.
826
    **********************************************************************/
827
    void add_to_end(            // add at end &
828
319k
      T *new_element) {
829
#ifndef NDEBUG
830
      if (!list) {
831
        NO_LIST.error("ELIST2_ITERATOR::add_to_end", ABORT);
832
      }
833
      if (!new_element) {
834
        BAD_PARAMETER.error("ELIST2_ITERATOR::add_to_end", ABORT, "new_element is nullptr");
835
      }
836
      if (new_element->next) {
837
        STILL_LINKED.error("ELIST2_ITERATOR::add_to_end", ABORT);
838
      }
839
#endif
840
841
319k
      if (this->at_last()) {
842
25.3k
        this->add_after_stay_put(new_element);
843
294k
      } else {
844
294k
        if (this->at_first()) {
845
294k
          this->add_before_stay_put(new_element);
846
294k
          list->last = new_element;
847
294k
        } else { // Iteratr is elsewhere
848
0
          new_element->next = list->last->next;
849
0
          new_element->prev = list->last;
850
0
          list->last->next->prev = new_element;
851
0
          list->last->next = new_element;
852
0
          list->last = new_element;
853
0
        }
854
294k
      }
855
319k
    } // don't move
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::WERD>::Iterator::add_to_end(tesseract::WERD*)
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::add_to_end(tesseract::ColPartition*)
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::Iterator::add_to_end(tesseract::TabVector*)
tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::add_to_end(tesseract::TO_ROW*)
Line
Count
Source
828
319k
      T *new_element) {
829
#ifndef NDEBUG
830
      if (!list) {
831
        NO_LIST.error("ELIST2_ITERATOR::add_to_end", ABORT);
832
      }
833
      if (!new_element) {
834
        BAD_PARAMETER.error("ELIST2_ITERATOR::add_to_end", ABORT, "new_element is nullptr");
835
      }
836
      if (new_element->next) {
837
        STILL_LINKED.error("ELIST2_ITERATOR::add_to_end", ABORT);
838
      }
839
#endif
840
841
319k
      if (this->at_last()) {
842
25.3k
        this->add_after_stay_put(new_element);
843
294k
      } else {
844
294k
        if (this->at_first()) {
845
294k
          this->add_before_stay_put(new_element);
846
294k
          list->last = new_element;
847
294k
        } else { // Iteratr is elsewhere
848
0
          new_element->next = list->last->next;
849
0
          new_element->prev = list->last;
850
0
          list->last->next->prev = new_element;
851
0
          list->last->next = new_element;
852
0
          list->last = new_element;
853
0
        }
854
294k
      }
855
319k
    } // don't move
856
      /***********************************************************************
857
     *              ELIST2_ITERATOR::exchange()
858
     *
859
     *  Given another iterator, whose current element is a different element on
860
     *  the same list list OR an element of another list, exchange the two current
861
     *  elements.  On return, each iterator points to the element which was the
862
     *  other iterators current on entry.
863
     *  (This function hasn't been in-lined because its a bit big!)
864
     **********************************************************************/
865
    void exchange(                  // positions of 2 links
866
      Iterator *other_it) { // other iterator
867
      constexpr ERRCODE DONT_EXCHANGE_DELETED("Can't exchange deleted elements of lists");
868
869
      T *old_current;
870
871
#ifndef NDEBUG
872
      if (!list)
873
        NO_LIST.error("ELIST2_ITERATOR::exchange", ABORT);
874
      if (!other_it)
875
        BAD_PARAMETER.error("ELIST2_ITERATOR::exchange", ABORT, "other_it nullptr");
876
      if (!(other_it->list))
877
        NO_LIST.error("ELIST2_ITERATOR::exchange", ABORT, "other_it");
878
#endif
879
880
      /* Do nothing if either list is empty or if both iterators reference the same
881
    link */
882
883
      if ((list->empty()) || (other_it->list->empty()) || (current == other_it->current)) {
884
        return;
885
      }
886
887
      /* Error if either current element is deleted */
888
889
      if (!current || !other_it->current) {
890
        DONT_EXCHANGE_DELETED.error("ELIST2_ITERATOR.exchange", ABORT);
891
      }
892
893
      /* Now handle the 4 cases: doubleton list; non-doubleton adjacent elements
894
    (other before this); non-doubleton adjacent elements (this before other);
895
    non-adjacent elements. */
896
897
    // adjacent links
898
      if ((next == other_it->current) || (other_it->next == current)) {
899
        // doubleton list
900
        if ((next == other_it->current) && (other_it->next == current)) {
901
          prev = next = current;
902
          other_it->prev = other_it->next = other_it->current;
903
        } else { // non-doubleton with
904
          // adjacent links
905
          // other before this
906
          if (other_it->next == current) {
907
            other_it->prev->next = current;
908
            other_it->current->next = next;
909
            other_it->current->prev = current;
910
            current->next = other_it->current;
911
            current->prev = other_it->prev;
912
            next->prev = other_it->current;
913
914
            other_it->next = other_it->current;
915
            prev = current;
916
          } else { // this before other
917
            prev->next = other_it->current;
918
            current->next = other_it->next;
919
            current->prev = other_it->current;
920
            other_it->current->next = current;
921
            other_it->current->prev = prev;
922
            other_it->next->prev = current;
923
924
            next = current;
925
            other_it->prev = other_it->current;
926
          }
927
        }
928
      } else { // no overlap
929
        prev->next = other_it->current;
930
        current->next = other_it->next;
931
        current->prev = other_it->prev;
932
        next->prev = other_it->current;
933
        other_it->prev->next = current;
934
        other_it->current->next = next;
935
        other_it->current->prev = prev;
936
        other_it->next->prev = current;
937
      }
938
939
      /* update end of list pointer when necessary (remember that the 2 iterators
940
      may iterate over different lists!) */
941
942
      if (list->last == current) {
943
        list->last = other_it->current;
944
      }
945
      if (other_it->list->last == other_it->current) {
946
        other_it->list->last = current;
947
      }
948
949
      if (current == cycle_pt) {
950
        cycle_pt = other_it->cycle_pt;
951
      }
952
      if (other_it->current == other_it->cycle_pt) {
953
        other_it->cycle_pt = cycle_pt;
954
      }
955
956
      /* The actual exchange - in all cases*/
957
958
      old_current = current;
959
      current = other_it->current;
960
      other_it->current = old_current;
961
    } // other iterator
962
963
      //# elements in list
964
242k
    int32_t length() const {
965
242k
      return list->length();
966
242k
    }
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::Iterator::length() const
tesseract::IntrusiveList<tesseract::WERD>::Iterator::length() const
Line
Count
Source
964
142k
    int32_t length() const {
965
142k
      return list->length();
966
142k
    }
tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::length() const
Line
Count
Source
964
99.8k
    int32_t length() const {
965
99.8k
      return list->length();
966
99.8k
    }
967
    /***********************************************************************
968
   *              ELIST2_ITERATOR::sort()
969
   *
970
   *  Sort the elements of the list, then reposition at the start.
971
   *
972
   **********************************************************************/
973
    void sort(          // sort elements
974
      int comparator( // comparison routine
975
25.9k
        const T *, const T *)) {
976
#ifndef NDEBUG
977
      if (!list) {
978
        NO_LIST.error("ELIST2_ITERATOR::sort", ABORT);
979
      }
980
#endif
981
982
25.9k
      list->sort(comparator);
983
25.9k
      move_to_first();
984
25.9k
    }
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::WERD>::Iterator::sort(int (*)(tesseract::WERD const*, tesseract::WERD const*))
tesseract::IntrusiveList<tesseract::TO_ROW>::Iterator::sort(int (*)(tesseract::TO_ROW const*, tesseract::TO_ROW const*))
Line
Count
Source
975
25.9k
        const T *, const T *)) {
976
#ifndef NDEBUG
977
      if (!list) {
978
        NO_LIST.error("ELIST2_ITERATOR::sort", ABORT);
979
      }
980
#endif
981
982
25.9k
      list->sort(comparator);
983
25.9k
      move_to_first();
984
25.9k
    }
985
986
  private:
987
    // Don't use the following constructor.
988
    Iterator() = delete;
989
  };
990
  using ITERATOR = Iterator; // compat
991
992
private:
993
  T *last = nullptr; // End of list
994
  //(Points to head)
995
13.0M
  T *First() { // return first
996
13.0M
    return last ? last->next : nullptr;
997
13.0M
  }
tesseract::IntrusiveList<tesseract::TO_ROW>::First()
Line
Count
Source
995
10.5M
  T *First() { // return first
996
10.5M
    return last ? last->next : nullptr;
997
10.5M
  }
tesseract::IntrusiveList<tesseract::WERD>::First()
Line
Count
Source
995
2.55M
  T *First() { // return first
996
2.55M
    return last ? last->next : nullptr;
997
2.55M
  }
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::First()
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::First()
998
999
public:
1000
650k
  ~IntrusiveList() {
1001
650k
    clear();
1002
650k
  }
tesseract::IntrusiveList<tesseract::WERD>::~IntrusiveList()
Line
Count
Source
1000
635k
  ~IntrusiveList() {
1001
635k
    clear();
1002
635k
  }
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::~IntrusiveList()
tesseract::IntrusiveList<tesseract::TO_ROW>::~IntrusiveList()
Line
Count
Source
1000
15.4k
  ~IntrusiveList() {
1001
15.4k
    clear();
1002
15.4k
  }
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::~IntrusiveList()
1003
1004
  /* delete elements */
1005
650k
  void clear() {
1006
650k
    internal_clear();
1007
650k
  }
tesseract::IntrusiveList<tesseract::WERD>::clear()
Line
Count
Source
1005
635k
  void clear() {
1006
635k
    internal_clear();
1007
635k
  }
tesseract::IntrusiveList<tesseract::TO_ROW>::clear()
Line
Count
Source
1005
15.4k
  void clear() {
1006
15.4k
    internal_clear();
1007
15.4k
  }
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::clear()
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::clear()
1008
1009
  /* Become a deep copy of src_list */
1010
  template <typename U>
1011
  void deep_copy(const U *src_list, T *(*copier)(const T *)) {
1012
    Iterator from_it(const_cast<U *>(src_list));
1013
    Iterator to_it(this);
1014
1015
    for (from_it.mark_cycle_pt(); !from_it.cycled_list(); from_it.forward())
1016
      to_it.add_after_then_move((*copier)(from_it.data()));
1017
  }
1018
1019
  /***********************************************************************
1020
   *              IntrusiveList::internal_clear
1021
   *
1022
   *  Used by the destructor and the "clear" member function of derived list
1023
   *  classes to destroy all the elements on the list.
1024
   *  The calling function passes a "zapper" function which can be called to
1025
   *  delete each element of the list, regardless of its derived type.  This
1026
   *  technique permits a generic clear function to destroy elements of
1027
   *  different derived types correctly, without requiring virtual functions and
1028
   *  the consequential memory overhead.
1029
   **********************************************************************/
1030
1031
   // destroy all links
1032
650k
  void internal_clear() {
1033
    // ptr to zapper functn
1034
650k
    T *ptr;
1035
650k
    T *next;
1036
1037
650k
    if (!empty()) {
1038
188k
      ptr = last->next;     // set to first
1039
188k
      last->next = nullptr; // break circle
1040
188k
      last = nullptr;       // set list empty
1041
648k
      while (ptr) {
1042
459k
        next = ptr->next;
1043
459k
        delete ptr;
1044
459k
        ptr = next;
1045
459k
      }
1046
188k
    }
1047
650k
  }
tesseract::IntrusiveList<tesseract::WERD>::internal_clear()
Line
Count
Source
1032
635k
  void internal_clear() {
1033
    // ptr to zapper functn
1034
635k
    T *ptr;
1035
635k
    T *next;
1036
1037
635k
    if (!empty()) {
1038
173k
      ptr = last->next;     // set to first
1039
173k
      last->next = nullptr; // break circle
1040
173k
      last = nullptr;       // set list empty
1041
454k
      while (ptr) {
1042
280k
        next = ptr->next;
1043
280k
        delete ptr;
1044
280k
        ptr = next;
1045
280k
      }
1046
173k
    }
1047
635k
  }
tesseract::IntrusiveList<tesseract::TO_ROW>::internal_clear()
Line
Count
Source
1032
15.4k
  void internal_clear() {
1033
    // ptr to zapper functn
1034
15.4k
    T *ptr;
1035
15.4k
    T *next;
1036
1037
15.4k
    if (!empty()) {
1038
15.0k
      ptr = last->next;     // set to first
1039
15.0k
      last->next = nullptr; // break circle
1040
15.0k
      last = nullptr;       // set list empty
1041
194k
      while (ptr) {
1042
178k
        next = ptr->next;
1043
178k
        delete ptr;
1044
178k
        ptr = next;
1045
178k
      }
1046
15.0k
    }
1047
15.4k
  }
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::internal_clear()
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::internal_clear()
1048
1049
225M
  bool empty() const { // is list empty?
1050
225M
    return !last;
1051
225M
  }
tesseract::IntrusiveList<tesseract::WERD>::empty() const
Line
Count
Source
1049
9.20M
  bool empty() const { // is list empty?
1050
9.20M
    return !last;
1051
9.20M
  }
tesseract::IntrusiveList<tesseract::TO_ROW>::empty() const
Line
Count
Source
1049
215M
  bool empty() const { // is list empty?
1050
215M
    return !last;
1051
215M
  }
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::empty() const
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::empty() const
1052
1053
439k
  bool singleton() const {
1054
439k
    return last ? (last == last->next) : false;
1055
439k
  }
tesseract::IntrusiveList<tesseract::WERD>::singleton() const
Line
Count
Source
1053
21.3k
  bool singleton() const {
1054
21.3k
    return last ? (last == last->next) : false;
1055
21.3k
  }
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::singleton() const
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::singleton() const
tesseract::IntrusiveList<tesseract::TO_ROW>::singleton() const
Line
Count
Source
1053
417k
  bool singleton() const {
1054
417k
    return last ? (last == last->next) : false;
1055
417k
  }
1056
1057
  void shallow_copy(       // dangerous!!
1058
    IntrusiveList *from_list) { // beware destructors!!
1059
    last = from_list->last;
1060
  }
1061
1062
  /***********************************************************************
1063
 *              IntrusiveList::assign_to_sublist
1064
 *
1065
 *  The list is set to a sublist of another list.  "This" list must be empty
1066
 *  before this function is invoked.  The two iterators passed must refer to
1067
 *  the same list, different from "this" one.  The sublist removed is the
1068
 *  inclusive list from start_it's current position to end_it's current
1069
 *  position.  If this range passes over the end of the source list then the
1070
 *  source list has its end set to the previous element of start_it.  The
1071
 *  extracted sublist is unaffected by the end point of the source list, its
1072
 *  end point is always the end_it position.
1073
 **********************************************************************/
1074
  void assign_to_sublist(        // to this list
1075
    Iterator *start_it, // from list start
1076
    Iterator *end_it);  // from list end
1077
1078
  // # elements in list
1079
283k
  int32_t length() const {
1080
283k
    int32_t count = 0;
1081
283k
    if (last != nullptr) {
1082
256k
      count = 1;
1083
1.59M
      for (auto it = last->next; it != last; it = it->next) {
1084
1.33M
        count++;
1085
1.33M
      }
1086
256k
    }
1087
283k
    return count;
1088
283k
  }
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::length() const
tesseract::IntrusiveList<tesseract::WERD>::length() const
Line
Count
Source
1079
142k
  int32_t length() const {
1080
142k
    int32_t count = 0;
1081
142k
    if (last != nullptr) {
1082
142k
      count = 1;
1083
206k
      for (auto it = last->next; it != last; it = it->next) {
1084
64.2k
        count++;
1085
64.2k
      }
1086
142k
    }
1087
142k
    return count;
1088
142k
  }
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::length() const
tesseract::IntrusiveList<tesseract::TO_ROW>::length() const
Line
Count
Source
1079
141k
  int32_t length() const {
1080
141k
    int32_t count = 0;
1081
141k
    if (last != nullptr) {
1082
113k
      count = 1;
1083
1.38M
      for (auto it = last->next; it != last; it = it->next) {
1084
1.26M
        count++;
1085
1.26M
      }
1086
113k
    }
1087
141k
    return count;
1088
141k
  }
1089
  /***********************************************************************
1090
 *              IntrusiveList::sort
1091
 *
1092
 *  Sort elements on list
1093
 *  NB If you don't like the const declarations in the comparator, coerce yours:
1094
 *   (int (*)(const void *, const void *)
1095
 **********************************************************************/
1096
  void sort(          // sort elements
1097
    int comparator( // comparison routine
1098
25.9k
      const T *, const T *)) {
1099
    // Allocate an array of pointers, one per list element.
1100
25.9k
    auto count = length();
1101
25.9k
    if (count > 0) {
1102
      // ptr array to sort
1103
25.3k
      std::vector<T *> base;
1104
25.3k
      base.reserve(count);
1105
1106
25.3k
      Iterator it(this);
1107
1108
      // Extract all elements, putting the pointers in the array.
1109
344k
      for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
1110
319k
        base.push_back(it.extract());
1111
319k
      }
1112
1113
      // Sort the pointer array.
1114
25.3k
      std::sort(base.begin(), base.end(),
1115
        // all current comparators return -1,0,1, so we handle this correctly for std::sort
1116
445k
        [&](auto &&l, auto &&r) {return comparator(l, r) < 0; });
Unexecuted instantiation: auto tesseract::IntrusiveList<tesseract::WERD>::sort(int (*)(tesseract::WERD const*, tesseract::WERD const*))::{lambda(auto:1&&, auto:2&&)#1}::operator()<tesseract::WERD*&, tesseract::WERD*>(tesseract::WERD*&, tesseract::WERD*&&) const
Unexecuted instantiation: auto tesseract::IntrusiveList<tesseract::ColPartition>::sort(int (*)(tesseract::ColPartition const*, tesseract::ColPartition const*))::{lambda(auto:1&&, auto:2&&)#1}::operator()<tesseract::ColPartition*&, tesseract::ColPartition*>(tesseract::ColPartition*&, tesseract::ColPartition*&&) const
Unexecuted instantiation: auto tesseract::IntrusiveList<tesseract::TabVector>::sort(int (*)(tesseract::TabVector const*, tesseract::TabVector const*))::{lambda(auto:1&&, auto:2&&)#1}::operator()<tesseract::TabVector*&, tesseract::TabVector*>(tesseract::TabVector*&, tesseract::TabVector*&&) const
auto tesseract::IntrusiveList<tesseract::TO_ROW>::sort(int (*)(tesseract::TO_ROW const*, tesseract::TO_ROW const*))::{lambda(auto:1&&, auto:2&&)#1}::operator()<tesseract::TO_ROW*&, tesseract::TO_ROW*>(tesseract::TO_ROW*&, tesseract::TO_ROW*&&) const
Line
Count
Source
1116
445k
        [&](auto &&l, auto &&r) {return comparator(l, r) < 0; });
1117
1118
      // Rebuild the list from the sorted pointers.
1119
319k
      for (auto current : base) {
1120
319k
        it.add_to_end(current);
1121
319k
      }
1122
25.3k
    }
1123
25.9k
  }
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::WERD>::sort(int (*)(tesseract::WERD const*, tesseract::WERD const*))
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::ColPartition>::sort(int (*)(tesseract::ColPartition const*, tesseract::ColPartition const*))
Unexecuted instantiation: tesseract::IntrusiveList<tesseract::TabVector>::sort(int (*)(tesseract::TabVector const*, tesseract::TabVector const*))
tesseract::IntrusiveList<tesseract::TO_ROW>::sort(int (*)(tesseract::TO_ROW const*, tesseract::TO_ROW const*))
Line
Count
Source
1098
25.9k
      const T *, const T *)) {
1099
    // Allocate an array of pointers, one per list element.
1100
25.9k
    auto count = length();
1101
25.9k
    if (count > 0) {
1102
      // ptr array to sort
1103
25.3k
      std::vector<T *> base;
1104
25.3k
      base.reserve(count);
1105
1106
25.3k
      Iterator it(this);
1107
1108
      // Extract all elements, putting the pointers in the array.
1109
344k
      for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
1110
319k
        base.push_back(it.extract());
1111
319k
      }
1112
1113
      // Sort the pointer array.
1114
25.3k
      std::sort(base.begin(), base.end(),
1115
        // all current comparators return -1,0,1, so we handle this correctly for std::sort
1116
25.3k
        [&](auto &&l, auto &&r) {return comparator(l, r) < 0; });
1117
1118
      // Rebuild the list from the sorted pointers.
1119
319k
      for (auto current : base) {
1120
319k
        it.add_to_end(current);
1121
319k
      }
1122
25.3k
    }
1123
25.9k
  }
1124
1125
  // Assuming list has been sorted already, insert new_link to
1126
  // keep the list sorted according to the same comparison function.
1127
  // Comparison function is the same as used by sort, i.e. uses double
1128
  // indirection. Time is O(1) to add to beginning or end.
1129
  // Time is linear to add pre-sorted items to an empty list.
1130
0
  void add_sorted(int comparator(const T *, const T *), T *new_link) {
1131
    // Check for adding at the end.
1132
0
    if (last == nullptr || comparator(last, new_link) < 0) {
1133
0
      if (last == nullptr) {
1134
0
        new_link->next = new_link;
1135
0
        new_link->prev = new_link;
1136
0
      } else {
1137
0
        new_link->next = last->next;
1138
0
        new_link->prev = last;
1139
0
        last->next = new_link;
1140
0
        new_link->next->prev = new_link;
1141
0
      }
1142
0
      last = new_link;
1143
0
    } else {
1144
      // Need to use an iterator.
1145
0
      Iterator it(this);
1146
0
      for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
1147
0
        auto link = it.data();
1148
0
        if (comparator(link, new_link) > 0) {
1149
0
          break;
1150
0
        }
1151
0
      }
1152
0
      if (it.cycled_list()) {
1153
0
        it.add_to_end(new_link);
1154
0
      } else {
1155
0
        it.add_before_then_move(new_link);
1156
0
      }
1157
0
    }
1158
0
  }
1159
};
1160
1161
template <typename CLASSNAME>
1162
using ELIST2 = IntrusiveList<CLASSNAME>;
1163
1164
// add TESS_API?
1165
// move templated lists to public include dirs?
1166
#define ELIST2IZEH(T)                           \
1167
  class T##_LIST : public IntrusiveList<T> {   \
1168
  public:                                               \
1169
    using IntrusiveList<T>::IntrusiveList;                    \
1170
  };                                                    \
1171
  class T##_IT : public IntrusiveList<T>::Iterator { \
1172
  public:                                               \
1173
    using base = IntrusiveList<T>::Iterator;           \
1174
    using base::base;                                   \
1175
  };
1176
1177
} // namespace tesseract
1178
1179
#endif