Coverage Report

Created: 2025-06-13 07:15

/src/tesseract/src/ccutil/clst.h
Line
Count
Source (jump to first uncovered line)
1
/**********************************************************************
2
 * File:        clst.h  (Formerly clist.h)
3
 * Description: CONS cell 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 CLST_H
20
#define CLST_H
21
22
#include "lsterr.h"
23
#include "serialis.h"
24
25
#include <algorithm>
26
#include <cstdio>
27
28
namespace tesseract {
29
30
/**********************************************************************
31
 * CLASS - CLIST
32
 *
33
 * Generic list class for singly linked CONS cell lists
34
 **********************************************************************/
35
36
template <typename T>
37
class ConsList {
38
  friend class Link;
39
40
public:
41
  /**********************************************************************
42
   *              CLASS - Link
43
   *
44
   *              Generic link class for singly linked CONS cell lists
45
   *
46
   *  Note:  No destructor - elements are assumed to be destroyed EITHER after
47
   *  they have been extracted from a list OR by the ConsList destructor which
48
   *  walks the list.
49
   **********************************************************************/
50
  struct Link {
51
    Link *next{};
52
    T *data{};
53
54
7.06M
    Link() = default;
Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Link::Link()
Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Link::Link()
Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Link::Link()
Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::Link::Link()
tesseract::ConsList<tesseract::WordWithBox>::Link::Link()
Line
Count
Source
54
3.86M
    Link() = default;
tesseract::ConsList<tesseract::EDGEPT>::Link::Link()
Line
Count
Source
54
3.20M
    Link() = default;
Unexecuted instantiation: tesseract::ConsList<tesseract::FPSEGPT_LIST>::Link::Link()
55
    Link(const Link &) = delete;
56
    void operator=(const Link &) = delete;
57
  };
58
59
  /***********************************************************************
60
   *              CLASS - Iterator
61
   *
62
   *              Generic iterator class for singly linked lists with embedded
63
   *links
64
   **********************************************************************/
65
  class Iterator {
66
    ConsList *list;                  // List being iterated
67
    Link *prev;             // prev element
68
    Link *current;          // current element
69
    Link *next;             // next element
70
    Link *cycle_pt;         // point we are cycling the list to.
71
    bool ex_current_was_last;     // current extracted was end of list
72
    bool ex_current_was_cycle_pt; // current extracted was cycle point
73
    bool started_cycling;         // Have we moved off the start?
74
75
    /***********************************************************************
76
     *              Iterator::extract_sublist()
77
     *
78
     *  This is a private member, used only by ConsList::assign_to_sublist.
79
     *  Given another iterator for the same list, extract the links from THIS to
80
     *  OTHER inclusive, link them into a new circular list, and return a
81
     *  pointer to the last element.
82
     *  (Can't inline this function because it contains a loop)
83
     **********************************************************************/
84
    Link *extract_sublist(  // from this current
85
      Iterator *other_it) {              // to other current
86
      Iterator temp_it = *this;
87
88
      constexpr ERRCODE BAD_SUBLIST("Can't find sublist end point in original list");
89
#ifndef NDEBUG
90
      constexpr ERRCODE BAD_EXTRACTION_PTS("Can't extract sublist from points on different lists");
91
      constexpr ERRCODE DONT_EXTRACT_DELETED("Can't extract a sublist marked by deleted points");
92
93
      if (list != other_it->list)
94
        BAD_EXTRACTION_PTS.error("Iterator.extract_sublist", ABORT);
95
      if (list->empty())
96
        EMPTY_LIST.error("Iterator::extract_sublist", ABORT);
97
98
      if (!current || !other_it->current)
99
        DONT_EXTRACT_DELETED.error("Iterator.extract_sublist", ABORT);
100
#endif
101
102
      ex_current_was_last = other_it->ex_current_was_last = false;
103
      ex_current_was_cycle_pt = false;
104
      other_it->ex_current_was_cycle_pt = false;
105
106
      temp_it.mark_cycle_pt();
107
      do {                         // walk sublist
108
        if (temp_it.cycled_list()) { // can't find end pt
109
          BAD_SUBLIST.error("Iterator.extract_sublist", ABORT);
110
        }
111
112
        if (temp_it.at_last()) {
113
          list->last = prev;
114
          ex_current_was_last = other_it->ex_current_was_last = true;
115
        }
116
117
        if (temp_it.current == cycle_pt) {
118
          ex_current_was_cycle_pt = true;
119
        }
120
121
        if (temp_it.current == other_it->cycle_pt) {
122
          other_it->ex_current_was_cycle_pt = true;
123
        }
124
125
        temp_it.forward();
126
      } while (temp_it.prev != other_it->current);
127
128
      // circularise sublist
129
      other_it->current->next = current;
130
      auto end_of_new_list = other_it->current;
131
132
      // sublist = whole list
133
      if (prev == other_it->current) {
134
        list->last = nullptr;
135
        prev = current = next = nullptr;
136
        other_it->prev = other_it->current = other_it->next = nullptr;
137
      } else {
138
        prev->next = other_it->next;
139
        current = other_it->current = nullptr;
140
        next = other_it->next;
141
        other_it->prev = prev;
142
      }
143
      return end_of_new_list;
144
    }
145
146
  public:
147
7.06k
    Iterator() { // constructor
148
7.06k
      list = nullptr;
149
7.06k
    } // unassigned list
Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::Iterator()
Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::Iterator()
Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::Iterator()
tesseract::ConsList<tesseract::WordWithBox>::Iterator::Iterator()
Line
Count
Source
147
7.06k
    Iterator() { // constructor
148
7.06k
      list = nullptr;
149
7.06k
    } // unassigned list
150
151
  /***********************************************************************
152
   *              Iterator::Iterator
153
   *
154
   *  CONSTRUCTOR - set iterator to specified list;
155
   **********************************************************************/
156
    Iterator( // constructor
157
12.2M
      ConsList *list_to_iterate) {
158
12.2M
      set_to_list(list_to_iterate);
159
12.2M
    }
Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::Iterator(tesseract::ConsList<tesseract::ColPartition>*)
Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::Iterator(tesseract::ConsList<tesseract::BLOBNBOX>*)
Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::Iterator(tesseract::ConsList<tesseract::ColSegment>*)
Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::Iterator::Iterator(tesseract::ConsList<tesseract::TabVector>*)
tesseract::ConsList<tesseract::WordWithBox>::Iterator::Iterator(tesseract::ConsList<tesseract::WordWithBox>*)
Line
Count
Source
157
1.85M
      ConsList *list_to_iterate) {
158
1.85M
      set_to_list(list_to_iterate);
159
1.85M
    }
tesseract::ConsList<tesseract::EDGEPT>::Iterator::Iterator(tesseract::ConsList<tesseract::EDGEPT>*)
Line
Count
Source
157
10.3M
      ConsList *list_to_iterate) {
158
10.3M
      set_to_list(list_to_iterate);
159
10.3M
    }
Unexecuted instantiation: tesseract::ConsList<tesseract::FPSEGPT_LIST>::Iterator::Iterator(tesseract::ConsList<tesseract::FPSEGPT_LIST>*)
160
161
    /***********************************************************************
162
     *              Iterator::set_to_list
163
     *
164
     *  (Re-)initialise the iterator to point to the start of the list_to_iterate
165
     *  over.
166
     **********************************************************************/
167
    void set_to_list( // change list
168
12.2M
      ConsList *list_to_iterate) {
169
12.2M
      list = list_to_iterate;
170
12.2M
      prev = list->last;
171
12.2M
      current = list->First();
172
12.2M
      next = current != nullptr ? current->next : nullptr;
173
12.2M
      cycle_pt = nullptr; // await explicit set
174
12.2M
      started_cycling = false;
175
12.2M
      ex_current_was_last = false;
176
12.2M
      ex_current_was_cycle_pt = false;
177
12.2M
    }
Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::set_to_list(tesseract::ConsList<tesseract::ColPartition>*)
Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::set_to_list(tesseract::ConsList<tesseract::BLOBNBOX>*)
Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::set_to_list(tesseract::ConsList<tesseract::ColSegment>*)
Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::Iterator::set_to_list(tesseract::ConsList<tesseract::TabVector>*)
tesseract::ConsList<tesseract::WordWithBox>::Iterator::set_to_list(tesseract::ConsList<tesseract::WordWithBox>*)
Line
Count
Source
168
1.85M
      ConsList *list_to_iterate) {
169
1.85M
      list = list_to_iterate;
170
1.85M
      prev = list->last;
171
1.85M
      current = list->First();
172
1.85M
      next = current != nullptr ? current->next : nullptr;
173
1.85M
      cycle_pt = nullptr; // await explicit set
174
1.85M
      started_cycling = false;
175
1.85M
      ex_current_was_last = false;
176
1.85M
      ex_current_was_cycle_pt = false;
177
1.85M
    }
tesseract::ConsList<tesseract::EDGEPT>::Iterator::set_to_list(tesseract::ConsList<tesseract::EDGEPT>*)
Line
Count
Source
168
10.3M
      ConsList *list_to_iterate) {
169
10.3M
      list = list_to_iterate;
170
10.3M
      prev = list->last;
171
10.3M
      current = list->First();
172
10.3M
      next = current != nullptr ? current->next : nullptr;
173
10.3M
      cycle_pt = nullptr; // await explicit set
174
10.3M
      started_cycling = false;
175
10.3M
      ex_current_was_last = false;
176
10.3M
      ex_current_was_cycle_pt = false;
177
10.3M
    }
Unexecuted instantiation: tesseract::ConsList<tesseract::FPSEGPT_LIST>::Iterator::set_to_list(tesseract::ConsList<tesseract::FPSEGPT_LIST>*)
178
179
    /***********************************************************************
180
     *              Iterator::add_after_then_move
181
     *
182
     *  Add a new element to the list after the current element and move the
183
     *  iterator to the new element.
184
     **********************************************************************/
185
    void add_after_then_move( // add after current &
186
0
      T *new_data) {
187
#ifndef NDEBUG
188
      if (!new_data) {
189
        BAD_PARAMETER.error("Iterator::add_after_then_move", ABORT, "new_data is nullptr");
190
      }
191
#endif
192
193
0
      auto new_element = new Link;
194
0
      new_element->data = new_data;
195
196
0
      if (list->empty()) {
197
0
        new_element->next = new_element;
198
0
        list->last = new_element;
199
0
        prev = next = new_element;
200
0
      } else {
201
0
        new_element->next = next;
202
203
0
        if (current) { // not extracted
204
0
          current->next = new_element;
205
0
          prev = current;
206
0
          if (current == list->last) {
207
0
            list->last = new_element;
208
0
          }
209
0
        } else { // current extracted
210
0
          prev->next = new_element;
211
0
          if (ex_current_was_last) {
212
0
            list->last = new_element;
213
0
          }
214
0
          if (ex_current_was_cycle_pt) {
215
0
            cycle_pt = new_element;
216
0
          }
217
0
        }
218
0
      }
219
0
      current = new_element;
220
0
    }      // move to new
Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::add_after_then_move(tesseract::BLOBNBOX*)
Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::add_after_then_move(tesseract::ColPartition*)
Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::add_after_then_move(tesseract::ColSegment*)
Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::Iterator::add_after_then_move(tesseract::TabVector*)
221
222
    /***********************************************************************
223
     *              Iterator::add_after_stay_put
224
     *
225
     *  Add a new element to the list after the current element but do not move
226
     *  the iterator to the new element.
227
     **********************************************************************/
228
    void add_after_stay_put( // add after current &
229
17
      T *new_data) {
230
#ifndef NDEBUG
231
      if (!new_data) {
232
        BAD_PARAMETER.error("Iterator::add_after_stay_put", ABORT, "new_data is nullptr");
233
      }
234
#endif
235
236
17
      auto new_element = new Link;
237
17
      new_element->data = new_data;
238
239
17
      if (list->empty()) {
240
0
        new_element->next = new_element;
241
0
        list->last = new_element;
242
0
        prev = next = new_element;
243
0
        ex_current_was_last = false;
244
0
        current = nullptr;
245
17
      } else {
246
17
        new_element->next = next;
247
248
17
        if (current) { // not extracted
249
17
          current->next = new_element;
250
17
          if (prev == current) {
251
17
            prev = new_element;
252
17
          }
253
17
          if (current == list->last) {
254
17
            list->last = new_element;
255
17
          }
256
17
        } else { // current extracted
257
0
          prev->next = new_element;
258
0
          if (ex_current_was_last) {
259
0
            list->last = new_element;
260
0
            ex_current_was_last = false;
261
0
          }
262
0
        }
263
17
        next = new_element;
264
17
      }
265
17
    }     // stay at current
Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::add_after_stay_put(tesseract::ColPartition*)
Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::add_after_stay_put(tesseract::BLOBNBOX*)
Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::add_after_stay_put(tesseract::ColSegment*)
tesseract::ConsList<tesseract::WordWithBox>::Iterator::add_after_stay_put(tesseract::WordWithBox*)
Line
Count
Source
229
17
      T *new_data) {
230
#ifndef NDEBUG
231
      if (!new_data) {
232
        BAD_PARAMETER.error("Iterator::add_after_stay_put", ABORT, "new_data is nullptr");
233
      }
234
#endif
235
236
17
      auto new_element = new Link;
237
17
      new_element->data = new_data;
238
239
17
      if (list->empty()) {
240
0
        new_element->next = new_element;
241
0
        list->last = new_element;
242
0
        prev = next = new_element;
243
0
        ex_current_was_last = false;
244
0
        current = nullptr;
245
17
      } else {
246
17
        new_element->next = next;
247
248
17
        if (current) { // not extracted
249
17
          current->next = new_element;
250
17
          if (prev == current) {
251
17
            prev = new_element;
252
17
          }
253
17
          if (current == list->last) {
254
17
            list->last = new_element;
255
17
          }
256
17
        } else { // current extracted
257
0
          prev->next = new_element;
258
0
          if (ex_current_was_last) {
259
0
            list->last = new_element;
260
0
            ex_current_was_last = false;
261
0
          }
262
0
        }
263
17
        next = new_element;
264
17
      }
265
17
    }     // stay at current
266
267
    /***********************************************************************
268
     *              Iterator::add_before_then_move
269
     *
270
     *  Add a new element to the list before the current element and move the
271
     *  iterator to the new element.
272
     **********************************************************************/
273
    void add_before_then_move( // add before current &
274
5.06M
      T *new_data) {
275
#ifndef NDEBUG
276
      if (!new_data) {
277
        BAD_PARAMETER.error("Iterator::add_before_then_move", ABORT, "new_data is nullptr");
278
      }
279
#endif
280
281
5.06M
      auto new_element = new Link;
282
5.06M
      new_element->data = new_data;
283
284
5.06M
      if (list->empty()) {
285
226k
        new_element->next = new_element;
286
226k
        list->last = new_element;
287
226k
        prev = next = new_element;
288
4.83M
      } else {
289
4.83M
        prev->next = new_element;
290
4.83M
        if (current) { // not extracted
291
4.83M
          new_element->next = current;
292
4.83M
          next = current;
293
4.83M
        } else { // current extracted
294
0
          new_element->next = next;
295
0
          if (ex_current_was_last) {
296
0
            list->last = new_element;
297
0
          }
298
0
          if (ex_current_was_cycle_pt) {
299
0
            cycle_pt = new_element;
300
0
          }
301
0
        }
302
4.83M
      }
303
5.06M
      current = new_element;
304
5.06M
    }       // move to new
Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::add_before_then_move(tesseract::ColPartition*)
Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::add_before_then_move(tesseract::BLOBNBOX*)
Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::add_before_then_move(tesseract::ColSegment*)
tesseract::ConsList<tesseract::WordWithBox>::Iterator::add_before_then_move(tesseract::WordWithBox*)
Line
Count
Source
274
1.85M
      T *new_data) {
275
#ifndef NDEBUG
276
      if (!new_data) {
277
        BAD_PARAMETER.error("Iterator::add_before_then_move", ABORT, "new_data is nullptr");
278
      }
279
#endif
280
281
1.85M
      auto new_element = new Link;
282
1.85M
      new_element->data = new_data;
283
284
1.85M
      if (list->empty()) {
285
0
        new_element->next = new_element;
286
0
        list->last = new_element;
287
0
        prev = next = new_element;
288
1.85M
      } else {
289
1.85M
        prev->next = new_element;
290
1.85M
        if (current) { // not extracted
291
1.85M
          new_element->next = current;
292
1.85M
          next = current;
293
1.85M
        } else { // current extracted
294
0
          new_element->next = next;
295
0
          if (ex_current_was_last) {
296
0
            list->last = new_element;
297
0
          }
298
0
          if (ex_current_was_cycle_pt) {
299
0
            cycle_pt = new_element;
300
0
          }
301
0
        }
302
1.85M
      }
303
1.85M
      current = new_element;
304
1.85M
    }       // move to new
tesseract::ConsList<tesseract::EDGEPT>::Iterator::add_before_then_move(tesseract::EDGEPT*)
Line
Count
Source
274
3.20M
      T *new_data) {
275
#ifndef NDEBUG
276
      if (!new_data) {
277
        BAD_PARAMETER.error("Iterator::add_before_then_move", ABORT, "new_data is nullptr");
278
      }
279
#endif
280
281
3.20M
      auto new_element = new Link;
282
3.20M
      new_element->data = new_data;
283
284
3.20M
      if (list->empty()) {
285
226k
        new_element->next = new_element;
286
226k
        list->last = new_element;
287
226k
        prev = next = new_element;
288
2.98M
      } else {
289
2.98M
        prev->next = new_element;
290
2.98M
        if (current) { // not extracted
291
2.98M
          new_element->next = current;
292
2.98M
          next = current;
293
2.98M
        } else { // current extracted
294
0
          new_element->next = next;
295
0
          if (ex_current_was_last) {
296
0
            list->last = new_element;
297
0
          }
298
0
          if (ex_current_was_cycle_pt) {
299
0
            cycle_pt = new_element;
300
0
          }
301
0
        }
302
2.98M
      }
303
3.20M
      current = new_element;
304
3.20M
    }       // move to new
Unexecuted instantiation: tesseract::ConsList<tesseract::FPSEGPT_LIST>::Iterator::add_before_then_move(tesseract::FPSEGPT_LIST*)
305
306
    /***********************************************************************
307
     *              Iterator::add_before_stay_put
308
     *
309
     *  Add a new element to the list before the current element but don't move the
310
     *  iterator to the new element.
311
     **********************************************************************/
312
    void add_before_stay_put( // add before current &
313
0
      T *new_data) {
314
#ifndef NDEBUG
315
      if (!new_data) {
316
        BAD_PARAMETER.error("Iterator::add_before_stay_put", ABORT, "new_data is nullptr");
317
      }
318
#endif
319
320
0
      auto new_element = new Link;
321
0
      new_element->data = new_data;
322
323
0
      if (list->empty()) {
324
0
        new_element->next = new_element;
325
0
        list->last = new_element;
326
0
        prev = next = new_element;
327
0
        ex_current_was_last = true;
328
0
        current = nullptr;
329
0
      } else {
330
0
        prev->next = new_element;
331
0
        if (current) { // not extracted
332
0
          new_element->next = current;
333
0
          if (next == current) {
334
0
            next = new_element;
335
0
          }
336
0
        } else { // current extracted
337
0
          new_element->next = next;
338
0
          if (ex_current_was_last) {
339
0
            list->last = new_element;
340
0
          }
341
0
        }
342
0
        prev = new_element;
343
0
      }
344
0
    }      // stay at current
Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::add_before_stay_put(tesseract::ColPartition*)
Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::add_before_stay_put(tesseract::BLOBNBOX*)
Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::add_before_stay_put(tesseract::ColSegment*)
Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::Iterator::add_before_stay_put(tesseract::TabVector*)
Unexecuted instantiation: tesseract::ConsList<tesseract::WordWithBox>::Iterator::add_before_stay_put(tesseract::WordWithBox*)
345
346
    /***********************************************************************
347
     *              Iterator::add_list_after
348
     *
349
     *  Insert another list to this list after the current element but don't move
350
     *the
351
     *  iterator.
352
     **********************************************************************/
353
    void add_list_after(     // add a list &
354
0
      ConsList *list_to_add) {
355
0
      if (!list_to_add->empty()) {
356
0
        if (list->empty()) {
357
0
          list->last = list_to_add->last;
358
0
          prev = list->last;
359
0
          next = list->First();
360
0
          ex_current_was_last = true;
361
0
          current = nullptr;
362
0
        } else {
363
0
          if (current) { // not extracted
364
0
            current->next = list_to_add->First();
365
0
            if (current == list->last) {
366
0
              list->last = list_to_add->last;
367
0
            }
368
0
            list_to_add->last->next = next;
369
0
            next = current->next;
370
0
          } else { // current extracted
371
0
            prev->next = list_to_add->First();
372
0
            if (ex_current_was_last) {
373
0
              list->last = list_to_add->last;
374
0
              ex_current_was_last = false;
375
0
            }
376
0
            list_to_add->last->next = next;
377
0
            next = prev->next;
378
0
          }
379
0
        }
380
0
        list_to_add->last = nullptr;
381
0
      }
382
0
    } // stay at current
Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::add_list_after(tesseract::ConsList<tesseract::BLOBNBOX>*)
Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::add_list_after(tesseract::ConsList<tesseract::ColPartition>*)
383
384
    /***********************************************************************
385
     *              Iterator::add_list_before
386
     *
387
     *  Insert another list to this list before the current element. Move the
388
     *  iterator to the start of the inserted elements
389
     *  iterator.
390
     **********************************************************************/
391
    void add_list_before(    // add a list &
392
      ConsList *list_to_add) {
393
      if (!list_to_add->empty()) {
394
        if (list->empty()) {
395
          list->last = list_to_add->last;
396
          prev = list->last;
397
          current = list->First();
398
          next = current->next;
399
          ex_current_was_last = false;
400
        } else {
401
          prev->next = list_to_add->First();
402
          if (current) { // not extracted
403
            list_to_add->last->next = current;
404
          } else { // current extracted
405
            list_to_add->last->next = next;
406
            if (ex_current_was_last) {
407
              list->last = list_to_add->last;
408
            }
409
            if (ex_current_was_cycle_pt) {
410
              cycle_pt = prev->next;
411
            }
412
          }
413
          current = prev->next;
414
          next = current->next;
415
        }
416
        list_to_add->last = nullptr;
417
      }
418
    } // move to it 1st item
419
420
9.70M
    T *data() { // get current data
421
#ifndef NDEBUG
422
      if (!list) {
423
        NO_LIST.error("Iterator::data", ABORT);
424
      }
425
#endif
426
9.70M
      return current->data;
427
9.70M
    }
Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::data()
Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::data()
Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::data()
Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::Iterator::data()
tesseract::ConsList<tesseract::WordWithBox>::Iterator::data()
Line
Count
Source
420
6.49M
    T *data() { // get current data
421
#ifndef NDEBUG
422
      if (!list) {
423
        NO_LIST.error("Iterator::data", ABORT);
424
      }
425
#endif
426
6.49M
      return current->data;
427
6.49M
    }
tesseract::ConsList<tesseract::EDGEPT>::Iterator::data()
Line
Count
Source
420
3.20M
    T *data() { // get current data
421
#ifndef NDEBUG
422
      if (!list) {
423
        NO_LIST.error("Iterator::data", ABORT);
424
      }
425
#endif
426
3.20M
      return current->data;
427
3.20M
    }
Unexecuted instantiation: tesseract::ConsList<tesseract::FPSEGPT_LIST>::Iterator::data()
428
429
    /***********************************************************************
430
     *              Iterator::data_relative
431
     *
432
     *  Return the data pointer to the element "offset" elements from current.
433
     *  "offset" must not be less than -1.
434
     *  (This function can't be INLINEd because it contains a loop)
435
     **********************************************************************/
436
    T *data_relative(  // get data + or - ...
437
0
      int8_t offset) {                 // offset from current
438
0
      Link *ptr;
439
440
#ifndef NDEBUG
441
      if (!list)
442
        NO_LIST.error("Iterator::data_relative", ABORT);
443
      if (list->empty())
444
        EMPTY_LIST.error("Iterator::data_relative", ABORT);
445
      if (offset < -1)
446
        BAD_PARAMETER.error("Iterator::data_relative", ABORT, "offset < -l");
447
#endif
448
449
0
      if (offset == -1) {
450
0
        ptr = prev;
451
0
      } else {
452
0
        for (ptr = current ? current : prev; offset-- > 0; ptr = ptr->next) {
453
0
          ;
454
0
        }
455
0
      }
456
457
0
      return ptr->data;
458
0
    }
Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::data_relative(signed char)
Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::data_relative(signed char)
Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::data_relative(signed char)
459
460
    /***********************************************************************
461
     *              Iterator::forward
462
     *
463
     *  Move the iterator to the next element of the list.
464
     *  REMEMBER: ALL LISTS ARE CIRCULAR.
465
     **********************************************************************/
466
7.84M
    T *forward() {
467
7.84M
      if (list->empty()) {
468
0
        return nullptr;
469
0
      }
470
471
7.84M
      if (current) { // not removed so
472
        // set previous
473
7.84M
        prev = current;
474
7.84M
        started_cycling = true;
475
        // In case next is deleted by another iterator, get next from current.
476
7.84M
        current = current->next;
477
7.84M
      } else {
478
0
        if (ex_current_was_cycle_pt) {
479
0
          cycle_pt = next;
480
0
        }
481
0
        current = next;
482
0
      }
483
484
7.84M
      next = current->next;
485
7.84M
      return current->data;
486
7.84M
    }
Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::forward()
Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::forward()
Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::forward()
Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::Iterator::forward()
tesseract::ConsList<tesseract::WordWithBox>::Iterator::forward()
Line
Count
Source
466
4.63M
    T *forward() {
467
4.63M
      if (list->empty()) {
468
0
        return nullptr;
469
0
      }
470
471
4.63M
      if (current) { // not removed so
472
        // set previous
473
4.63M
        prev = current;
474
4.63M
        started_cycling = true;
475
        // In case next is deleted by another iterator, get next from current.
476
4.63M
        current = current->next;
477
4.63M
      } else {
478
0
        if (ex_current_was_cycle_pt) {
479
0
          cycle_pt = next;
480
0
        }
481
0
        current = next;
482
0
      }
483
484
4.63M
      next = current->next;
485
4.63M
      return current->data;
486
4.63M
    }
tesseract::ConsList<tesseract::EDGEPT>::Iterator::forward()
Line
Count
Source
466
3.20M
    T *forward() {
467
3.20M
      if (list->empty()) {
468
0
        return nullptr;
469
0
      }
470
471
3.20M
      if (current) { // not removed so
472
        // set previous
473
3.20M
        prev = current;
474
3.20M
        started_cycling = true;
475
        // In case next is deleted by another iterator, get next from current.
476
3.20M
        current = current->next;
477
3.20M
      } else {
478
0
        if (ex_current_was_cycle_pt) {
479
0
          cycle_pt = next;
480
0
        }
481
0
        current = next;
482
0
      }
483
484
3.20M
      next = current->next;
485
3.20M
      return current->data;
486
3.20M
    }
Unexecuted instantiation: tesseract::ConsList<tesseract::FPSEGPT_LIST>::Iterator::forward()
487
488
    /***********************************************************************
489
     *              Iterator::extract
490
     *
491
     *  Do extraction by removing current from the list, deleting the cons cell
492
     *  and returning the data to the caller, but NOT updating the iterator.  (So
493
     *  that any calling loop can do this.)  The iterator's current points to
494
     *  nullptr.  If the data is to be deleted, this is the callers responsibility.
495
     **********************************************************************/
496
0
    T *extract() {
497
#ifndef NDEBUG
498
      if (!current) { // list empty or
499
        // element extracted
500
        NULL_CURRENT.error("Iterator::extract", ABORT);
501
      }
502
#endif
503
504
0
      if (list->singleton()) {
505
        // Special case where we do need to change the iterator.
506
0
        prev = next = list->last = nullptr;
507
0
      } else {
508
0
        prev->next = next; // remove from list
509
510
0
        if (current == list->last) {
511
0
          list->last = prev;
512
0
          ex_current_was_last = true;
513
0
        } else {
514
0
          ex_current_was_last = false;
515
0
        }
516
0
      }
517
      // Always set ex_current_was_cycle_pt so an add/forward will work in a loop.
518
0
      ex_current_was_cycle_pt = (current == cycle_pt);
519
0
      auto extracted_data = current->data;
520
0
      delete (current); // destroy CONS cell
521
0
      current = nullptr;
522
0
      return extracted_data;
523
0
    } // remove from list
Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::extract()
Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::extract()
Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::extract()
Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::Iterator::extract()
524
525
    /***********************************************************************
526
     *              Iterator::move_to_first()
527
     *
528
     *  Move current so that it is set to the start of the list.
529
     *  Return data just in case anyone wants it.
530
     **********************************************************************/
531
0
    T *move_to_first() {
532
0
      current = list->First();
533
0
      prev = list->last;
534
0
      next = current != nullptr ? current->next : nullptr;
535
0
      return current != nullptr ? current->data : nullptr;
536
0
    } // go to start of list
Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::move_to_first()
Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::move_to_first()
Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::move_to_first()
537
538
    /***********************************************************************
539
     *              Iterator::move_to_last()
540
     *
541
     *  Move current so that it is set to the end of the list.
542
     *  Return data just in case anyone wants it.
543
     *  (This function can't be INLINEd because it contains a loop)
544
     **********************************************************************/
545
0
    T *move_to_last() {
546
0
      while (current != list->last) {
547
0
        forward();
548
0
      }
549
550
0
      if (current == nullptr) {
551
0
        return nullptr;
552
0
      } else {
553
0
        return current->data;
554
0
      }
555
0
    }
Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::move_to_last()
Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::Iterator::move_to_last()
556
557
    /***********************************************************************
558
     *              Iterator::mark_cycle_pt()
559
     *
560
     *  Remember the current location so that we can tell whether we've returned
561
     *  to this point later.
562
     *
563
     *  If the current point is deleted either now, or in the future, the cycle
564
     *  point will be set to the next item which is set to current.  This could be
565
     *  by a forward, add_after_then_move or add_after_then_move.
566
     **********************************************************************/
567
2.43M
    void mark_cycle_pt() {
568
#ifndef NDEBUG
569
      if (!list) {
570
        NO_LIST.error("Iterator::mark_cycle_pt", ABORT);
571
      }
572
#endif
573
574
2.43M
      if (current) {
575
2.08M
        cycle_pt = current;
576
2.08M
      } else {
577
356k
        ex_current_was_cycle_pt = true;
578
356k
      }
579
2.43M
      started_cycling = false;
580
2.43M
    } // remember current
Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::mark_cycle_pt()
Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::mark_cycle_pt()
Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::mark_cycle_pt()
Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::Iterator::mark_cycle_pt()
tesseract::ConsList<tesseract::WordWithBox>::Iterator::mark_cycle_pt()
Line
Count
Source
567
1.85M
    void mark_cycle_pt() {
568
#ifndef NDEBUG
569
      if (!list) {
570
        NO_LIST.error("Iterator::mark_cycle_pt", ABORT);
571
      }
572
#endif
573
574
1.85M
      if (current) {
575
1.85M
        cycle_pt = current;
576
1.85M
      } else {
577
0
        ex_current_was_cycle_pt = true;
578
0
      }
579
1.85M
      started_cycling = false;
580
1.85M
    } // remember current
tesseract::ConsList<tesseract::EDGEPT>::Iterator::mark_cycle_pt()
Line
Count
Source
567
582k
    void mark_cycle_pt() {
568
#ifndef NDEBUG
569
      if (!list) {
570
        NO_LIST.error("Iterator::mark_cycle_pt", ABORT);
571
      }
572
#endif
573
574
582k
      if (current) {
575
226k
        cycle_pt = current;
576
356k
      } else {
577
356k
        ex_current_was_cycle_pt = true;
578
356k
      }
579
582k
      started_cycling = false;
580
582k
    } // remember current
Unexecuted instantiation: tesseract::ConsList<tesseract::FPSEGPT_LIST>::Iterator::mark_cycle_pt()
581
582
0
    bool empty() const { // is list empty?
583
0
      return list->empty();
584
0
    }
Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::empty() const
Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::empty() const
Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::empty() const
Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::Iterator::empty() const
Unexecuted instantiation: tesseract::ConsList<tesseract::WordWithBox>::Iterator::empty() const
585
586
    bool current_extracted() const { // current extracted?
587
      return !current;
588
    }
589
590
    /***********************************************************************
591
     *              Iterator::at_first()
592
     *
593
     *  Are we at the start of the list?
594
     *
595
     **********************************************************************/
596
0
    bool at_first() const {
597
      // we're at a deleted
598
0
      return ((list->empty()) || (current == list->First()) ||
599
0
        ((current == nullptr) && (prev == list->last) && // NON-last pt between
600
0
          !ex_current_was_last));                         // first and last
601
0
    } // Current is first?
Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::at_first() const
Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::at_first() const
Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::at_first() const
Unexecuted instantiation: tesseract::ConsList<tesseract::WordWithBox>::Iterator::at_first() const
602
603
    /***********************************************************************
604
     *              Iterator::at_last()
605
     *
606
     *  Are we at the end of the list?
607
     *
608
     **********************************************************************/
609
17
    bool at_last() const {
610
      // we're at a deleted
611
17
      return ((list->empty()) || (current == list->last) ||
612
17
        ((current == nullptr) && (prev == list->last) && // last point between
613
0
          ex_current_was_last));                          // first and last
614
17
    } // Current is last?
Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::at_last() const
Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::at_last() const
Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::at_last() const
Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::Iterator::at_last() const
tesseract::ConsList<tesseract::WordWithBox>::Iterator::at_last() const
Line
Count
Source
609
17
    bool at_last() const {
610
      // we're at a deleted
611
17
      return ((list->empty()) || (current == list->last) ||
612
17
        ((current == nullptr) && (prev == list->last) && // last point between
613
0
          ex_current_was_last));                          // first and last
614
17
    } // Current is last?
615
616
    /***********************************************************************
617
     *              Iterator::cycled_list()
618
     *
619
     *  Have we returned to the cycle_pt since it was set?
620
     *
621
     **********************************************************************/
622
12.1M
    bool cycled_list() const { // Completed a cycle?
623
12.1M
      return ((list->empty()) || ((current == cycle_pt) && started_cycling));
624
12.1M
    }
Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::cycled_list() const
Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::cycled_list() const
Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::cycled_list() const
Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::Iterator::cycled_list() const
tesseract::ConsList<tesseract::WordWithBox>::Iterator::cycled_list() const
Line
Count
Source
622
8.34M
    bool cycled_list() const { // Completed a cycle?
623
8.34M
      return ((list->empty()) || ((current == cycle_pt) && started_cycling));
624
8.34M
    }
tesseract::ConsList<tesseract::EDGEPT>::Iterator::cycled_list() const
Line
Count
Source
622
3.79M
    bool cycled_list() const { // Completed a cycle?
623
3.79M
      return ((list->empty()) || ((current == cycle_pt) && started_cycling));
624
3.79M
    }
Unexecuted instantiation: tesseract::ConsList<tesseract::FPSEGPT_LIST>::Iterator::cycled_list() const
625
626
    /***********************************************************************
627
     *              Iterator::add_to_end
628
     *
629
     *  Add a new element to the end of the list without moving the iterator.
630
     *  This is provided because a single linked list cannot move to the last as
631
     *  the iterator couldn't set its prev pointer.  Adding to the end is
632
     *  essential for implementing
633
                  queues.
634
    **********************************************************************/
635
    void add_to_end(  // element to add
636
17
      T *new_data) {
637
#ifndef NDEBUG
638
      if (!list) {
639
        NO_LIST.error("Iterator::add_to_end", ABORT);
640
      }
641
      if (!new_data) {
642
        BAD_PARAMETER.error("Iterator::add_to_end", ABORT, "new_data is nullptr");
643
      }
644
#endif
645
646
17
      if (this->at_last()) {
647
17
        this->add_after_stay_put(new_data);
648
17
      } else {
649
0
        if (this->at_first()) {
650
0
          this->add_before_stay_put(new_data);
651
0
          list->last = prev;
652
0
        } else { // Iteratr is elsewhere
653
0
          auto new_element = new Link;
654
0
          new_element->data = new_data;
655
656
0
          new_element->next = list->last->next;
657
0
          list->last->next = new_element;
658
0
          list->last = new_element;
659
0
        }
660
0
      }
661
17
    }
Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::Iterator::add_to_end(tesseract::ColPartition*)
Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::Iterator::add_to_end(tesseract::BLOBNBOX*)
Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::Iterator::add_to_end(tesseract::ColSegment*)
tesseract::ConsList<tesseract::WordWithBox>::Iterator::add_to_end(tesseract::WordWithBox*)
Line
Count
Source
636
17
      T *new_data) {
637
#ifndef NDEBUG
638
      if (!list) {
639
        NO_LIST.error("Iterator::add_to_end", ABORT);
640
      }
641
      if (!new_data) {
642
        BAD_PARAMETER.error("Iterator::add_to_end", ABORT, "new_data is nullptr");
643
      }
644
#endif
645
646
17
      if (this->at_last()) {
647
17
        this->add_after_stay_put(new_data);
648
17
      } else {
649
0
        if (this->at_first()) {
650
0
          this->add_before_stay_put(new_data);
651
0
          list->last = prev;
652
0
        } else { // Iteratr is elsewhere
653
0
          auto new_element = new Link;
654
0
          new_element->data = new_data;
655
656
0
          new_element->next = list->last->next;
657
0
          list->last->next = new_element;
658
0
          list->last = new_element;
659
0
        }
660
0
      }
661
17
    }
662
663
    /***********************************************************************
664
     *              Iterator::exchange()
665
     *
666
     *  Given another iterator, whose current element is a different element on
667
     *  the same list list OR an element of another list, exchange the two current
668
     *  elements.  On return, each iterator points to the element which was the
669
     *  other iterators current on entry.
670
     *  (This function hasn't been in-lined because its a bit big!)
671
     **********************************************************************/
672
    void exchange(                 // positions of 2 links
673
      Iterator *other_it) { // other iterator
674
      constexpr ERRCODE DONT_EXCHANGE_DELETED("Can't exchange deleted elements of lists");
675
676
      /* Do nothing if either list is empty or if both iterators reference the same
677
    link */
678
679
      if ((list->empty()) || (other_it->list->empty()) || (current == other_it->current)) {
680
        return;
681
      }
682
683
      /* Error if either current element is deleted */
684
685
      if (!current || !other_it->current) {
686
        DONT_EXCHANGE_DELETED.error("Iterator.exchange", ABORT);
687
      }
688
689
      /* Now handle the 4 cases: doubleton list; non-doubleton adjacent elements
690
    (other before this); non-doubleton adjacent elements (this before other);
691
    non-adjacent elements. */
692
693
    // adjacent links
694
      if ((next == other_it->current) || (other_it->next == current)) {
695
        // doubleton list
696
        if ((next == other_it->current) && (other_it->next == current)) {
697
          prev = next = current;
698
          other_it->prev = other_it->next = other_it->current;
699
        } else { // non-doubleton with
700
          // adjacent links
701
          // other before this
702
          if (other_it->next == current) {
703
            other_it->prev->next = current;
704
            other_it->current->next = next;
705
            current->next = other_it->current;
706
            other_it->next = other_it->current;
707
            prev = current;
708
          } else { // this before other
709
            prev->next = other_it->current;
710
            current->next = other_it->next;
711
            other_it->current->next = current;
712
            next = current;
713
            other_it->prev = other_it->current;
714
          }
715
        }
716
      } else { // no overlap
717
        prev->next = other_it->current;
718
        current->next = other_it->next;
719
        other_it->prev->next = current;
720
        other_it->current->next = next;
721
      }
722
723
      /* update end of list pointer when necessary (remember that the 2 iterators
724
      may iterate over different lists!) */
725
726
      if (list->last == current) {
727
        list->last = other_it->current;
728
      }
729
      if (other_it->list->last == other_it->current) {
730
        other_it->list->last = current;
731
      }
732
733
      if (current == cycle_pt) {
734
        cycle_pt = other_it->cycle_pt;
735
      }
736
      if (other_it->current == other_it->cycle_pt) {
737
        other_it->cycle_pt = cycle_pt;
738
      }
739
740
      /* The actual exchange - in all cases*/
741
742
      auto old_current = current;
743
      current = other_it->current;
744
      other_it->current = old_current;
745
    }
746
747
    /***********************************************************************
748
     *              Iterator::length()
749
     *
750
     *  Return the length of the list
751
     *
752
     **********************************************************************/
753
0
    int32_t length() const {
754
0
      return list->length();
755
0
    }
756
757
    /***********************************************************************
758
     *              Iterator::sort()
759
     *
760
     *  Sort the elements of the list, then reposition at the start.
761
     *
762
     **********************************************************************/
763
    void sort(     // sort elements
764
      int comparator(               // comparison routine
765
        const T *, const T *)) {
766
      list->sort(comparator);
767
      move_to_first();
768
    }
769
  };
770
  using ITERATOR = Iterator; // compat
771
772
private:
773
  Link *last = nullptr; // End of list
774
775
  //(Points to head)
776
12.2M
  Link *First() { // return first
777
12.2M
    return last != nullptr ? last->next : nullptr;
778
12.2M
  }
Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::First()
Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::First()
Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::First()
Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::First()
tesseract::ConsList<tesseract::WordWithBox>::First()
Line
Count
Source
776
1.85M
  Link *First() { // return first
777
1.85M
    return last != nullptr ? last->next : nullptr;
778
1.85M
  }
tesseract::ConsList<tesseract::EDGEPT>::First()
Line
Count
Source
776
10.3M
  Link *First() { // return first
777
10.3M
    return last != nullptr ? last->next : nullptr;
778
10.3M
  }
Unexecuted instantiation: tesseract::ConsList<tesseract::FPSEGPT_LIST>::First()
779
780
  const Link *First() const { // return first
781
    return last != nullptr ? last->next : nullptr;
782
  }
783
784
public:
785
7.07M
  ~ConsList() { // destructor
786
7.07M
    shallow_clear();
787
7.07M
  }
Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::~ConsList()
Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::~ConsList()
Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::~ConsList()
Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::~ConsList()
tesseract::ConsList<tesseract::WordWithBox>::~ConsList()
Line
Count
Source
785
6.48M
  ~ConsList() { // destructor
786
6.48M
    shallow_clear();
787
6.48M
  }
tesseract::ConsList<tesseract::EDGEPT>::~ConsList()
Line
Count
Source
785
582k
  ~ConsList() { // destructor
786
582k
    shallow_clear();
787
582k
  }
Unexecuted instantiation: tesseract::ConsList<tesseract::FPSEGPT_LIST>::~ConsList()
788
789
  /***********************************************************************
790
   *              ConsList::internal_deep_clear
791
   *
792
   *  Used by the "deep_clear" member function of derived list
793
   *  classes to destroy all the elements on the list.
794
   *  The calling function passes a "zapper" function which can be called to
795
   *  delete each data element of the list, regardless of its class.  This
796
   *  technique permits a generic clear function to destroy elements of
797
   *  different derived types correctly, without requiring virtual functions and
798
   *  the consequential memory overhead.
799
   **********************************************************************/
800
0
  void internal_deep_clear() {    // ptr to zapper functn
801
0
    if (!empty()) {
802
0
      auto ptr = last->next;     // set to first
803
0
      last->next = nullptr; // break circle
804
0
      last = nullptr;       // set list empty
805
0
      while (ptr) {
806
0
        auto next = ptr->next;
807
0
        delete ptr->data;
808
0
        delete (ptr);
809
0
        ptr = next;
810
0
      }
811
0
    }
812
0
  }
813
0
  void deep_clear() {
814
0
    internal_deep_clear();
815
0
  }
816
817
  /***********************************************************************
818
   *              ConsList::shallow_clear
819
   *
820
   *  Used by the destructor and the "shallow_clear" member function of derived
821
   *  list classes to destroy the list.
822
   *  The data elements are NOT destroyed.
823
   *
824
   **********************************************************************/
825
7.07M
  void shallow_clear() { // destroy all links
826
7.07M
    if (!empty()) {
827
1.20M
      auto ptr = last->next;     // set to first
828
1.20M
      last->next = nullptr; // break circle
829
1.20M
      last = nullptr;       // set list empty
830
8.27M
      while (ptr) {
831
7.06M
        auto next = ptr->next;
832
7.06M
        delete (ptr);
833
7.06M
        ptr = next;
834
7.06M
      }
835
1.20M
    }
836
7.07M
  }
Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::shallow_clear()
Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::shallow_clear()
Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::shallow_clear()
Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::shallow_clear()
tesseract::ConsList<tesseract::WordWithBox>::shallow_clear()
Line
Count
Source
825
6.48M
  void shallow_clear() { // destroy all links
826
6.48M
    if (!empty()) {
827
983k
      auto ptr = last->next;     // set to first
828
983k
      last->next = nullptr; // break circle
829
983k
      last = nullptr;       // set list empty
830
4.84M
      while (ptr) {
831
3.86M
        auto next = ptr->next;
832
3.86M
        delete (ptr);
833
3.86M
        ptr = next;
834
3.86M
      }
835
983k
    }
836
6.48M
  }
tesseract::ConsList<tesseract::EDGEPT>::shallow_clear()
Line
Count
Source
825
582k
  void shallow_clear() { // destroy all links
826
582k
    if (!empty()) {
827
226k
      auto ptr = last->next;     // set to first
828
226k
      last->next = nullptr; // break circle
829
226k
      last = nullptr;       // set list empty
830
3.43M
      while (ptr) {
831
3.20M
        auto next = ptr->next;
832
3.20M
        delete (ptr);
833
3.20M
        ptr = next;
834
3.20M
      }
835
226k
    }
836
582k
  }
Unexecuted instantiation: tesseract::ConsList<tesseract::FPSEGPT_LIST>::shallow_clear()
837
838
32.1M
  bool empty() const { // is list empty?
839
32.1M
    return !last;
840
32.1M
  }
Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::empty() const
Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::empty() const
Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::empty() const
Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::empty() const
tesseract::ConsList<tesseract::WordWithBox>::empty() const
Line
Count
Source
838
21.3M
  bool empty() const { // is list empty?
839
21.3M
    return !last;
840
21.3M
  }
tesseract::ConsList<tesseract::EDGEPT>::empty() const
Line
Count
Source
838
10.7M
  bool empty() const { // is list empty?
839
10.7M
    return !last;
840
10.7M
  }
Unexecuted instantiation: tesseract::ConsList<tesseract::FPSEGPT_LIST>::empty() const
841
842
0
  bool singleton() const {
843
0
    return last != nullptr ? (last == last->next) : false;
844
0
  }
Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::singleton() const
Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::singleton() const
Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::singleton() const
Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::singleton() const
845
846
  void shallow_copy(      // dangerous!!
847
    ConsList *from_list) { // beware destructors!!
848
    last = from_list->last;
849
  }
850
851
  /***********************************************************************
852
   *              ConsList::assign_to_sublist
853
   *
854
   *  The list is set to a sublist of another list.  "This" list must be empty
855
   *  before this function is invoked.  The two iterators passed must refer to
856
   *  the same list, different from "this" one.  The sublist removed is the
857
   *  inclusive list from start_it's current position to end_it's current
858
   *  position.  If this range passes over the end of the source list then the
859
   *  source list has its end set to the previous element of start_it.  The
860
   *  extracted sublist is unaffected by the end point of the source list, its
861
   *  end point is always the end_it position.
862
   **********************************************************************/
863
  void assign_to_sublist(  // to this list
864
    Iterator *start_it,  // from list start
865
    Iterator *end_it) {  // from list end
866
    constexpr ERRCODE LIST_NOT_EMPTY("Destination list must be empty before extracting a sublist");
867
868
    if (!empty()) {
869
      LIST_NOT_EMPTY.error("ConsList.assign_to_sublist", ABORT);
870
    }
871
872
    last = start_it->extract_sublist(end_it);
873
  }
874
875
0
  int32_t length() const { //# elements in list
876
0
    int32_t count = 0;
877
0
    if (last != nullptr) {
878
0
      count = 1;
879
0
      for (auto it = last->next; it != last; it = it->next) {
880
0
        count++;
881
0
      }
882
0
    }
883
0
    return count;
884
0
  }
Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::length() const
Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::length() const
Unexecuted instantiation: tesseract::ConsList<tesseract::TabVector>::length() const
885
886
  /***********************************************************************
887
   *              ConsList::sort
888
   *
889
   *  Sort elements on list
890
   **********************************************************************/
891
  void sort(          // sort elements
892
    int comparator( // comparison routine
893
0
      const T *, const T *)) {
894
    // Allocate an array of pointers, one per list element.
895
0
    auto count = length();
896
0
    if (count > 0) {
897
      // ptr array to sort
898
0
      std::vector<T *> base;
899
0
      base.reserve(count);
900
901
0
      Iterator it(this);
902
903
      // Extract all elements, putting the pointers in the array.
904
0
      for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
905
0
        base.push_back(it.extract());
906
0
      }
907
908
      // Sort the pointer array.
909
0
      std::sort(base.begin(), base.end(),
910
        // all current comparators return -1,0,1, so we handle this correctly for std::sort
911
0
        [&](auto &&l, auto &&r) {return comparator(l, r) < 0; });
912
913
      // Rebuild the list from the sorted pointers.
914
0
      for (auto current : base) {
915
0
        it.add_to_end(current);
916
0
      }
917
0
    }
918
0
  }
919
920
  // Assuming list has been sorted already, insert new_data to
921
  // keep the list sorted according to the same comparison function.
922
  // Comparison function is the same as used by sort, i.e. uses double
923
  // indirection. Time is O(1) to add to beginning or end.
924
  // Time is linear to add pre-sorted items to an empty list.
925
  // If unique, then don't add duplicate entries.
926
  // Returns true if the element was added to the list.
927
3.86M
  bool add_sorted(int comparator(const T *, const T *), bool unique, T *new_data) {
928
    // Check for adding at the end.
929
3.86M
    if (last == nullptr || comparator(last->data, new_data) < 0) {
930
2.00M
      auto *new_element = new Link;
931
2.00M
      new_element->data = new_data;
932
2.00M
      if (last == nullptr) {
933
983k
        new_element->next = new_element;
934
1.02M
      } else {
935
1.02M
        new_element->next = last->next;
936
1.02M
        last->next = new_element;
937
1.02M
      }
938
2.00M
      last = new_element;
939
2.00M
      return true;
940
2.00M
    } else if (!unique || last->data != new_data) {
941
      // Need to use an iterator.
942
1.85M
      Iterator it(this);
943
6.49M
      for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
944
6.49M
        auto data = it.data();
945
6.49M
        if (data == new_data && unique) {
946
0
          return false;
947
0
        }
948
6.49M
        if (comparator(data, new_data) > 0) {
949
1.85M
          break;
950
1.85M
        }
951
6.49M
      }
952
1.85M
      if (it.cycled_list()) {
953
17
        it.add_to_end(new_data);
954
1.85M
      } else {
955
1.85M
        it.add_before_then_move(new_data);
956
1.85M
      }
957
1.85M
      return true;
958
1.85M
    }
959
0
    return false;
960
3.86M
  }
Unexecuted instantiation: tesseract::ConsList<tesseract::ColPartition>::add_sorted(int (*)(tesseract::ColPartition const*, tesseract::ColPartition const*), bool, tesseract::ColPartition*)
Unexecuted instantiation: tesseract::ConsList<tesseract::BLOBNBOX>::add_sorted(int (*)(tesseract::BLOBNBOX const*, tesseract::BLOBNBOX const*), bool, tesseract::BLOBNBOX*)
Unexecuted instantiation: tesseract::ConsList<tesseract::ColSegment>::add_sorted(int (*)(tesseract::ColSegment const*, tesseract::ColSegment const*), bool, tesseract::ColSegment*)
tesseract::ConsList<tesseract::WordWithBox>::add_sorted(int (*)(tesseract::WordWithBox const*, tesseract::WordWithBox const*), bool, tesseract::WordWithBox*)
Line
Count
Source
927
3.86M
  bool add_sorted(int comparator(const T *, const T *), bool unique, T *new_data) {
928
    // Check for adding at the end.
929
3.86M
    if (last == nullptr || comparator(last->data, new_data) < 0) {
930
2.00M
      auto *new_element = new Link;
931
2.00M
      new_element->data = new_data;
932
2.00M
      if (last == nullptr) {
933
983k
        new_element->next = new_element;
934
1.02M
      } else {
935
1.02M
        new_element->next = last->next;
936
1.02M
        last->next = new_element;
937
1.02M
      }
938
2.00M
      last = new_element;
939
2.00M
      return true;
940
2.00M
    } else if (!unique || last->data != new_data) {
941
      // Need to use an iterator.
942
1.85M
      Iterator it(this);
943
6.49M
      for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
944
6.49M
        auto data = it.data();
945
6.49M
        if (data == new_data && unique) {
946
0
          return false;
947
0
        }
948
6.49M
        if (comparator(data, new_data) > 0) {
949
1.85M
          break;
950
1.85M
        }
951
6.49M
      }
952
1.85M
      if (it.cycled_list()) {
953
17
        it.add_to_end(new_data);
954
1.85M
      } else {
955
1.85M
        it.add_before_then_move(new_data);
956
1.85M
      }
957
1.85M
      return true;
958
1.85M
    }
959
0
    return false;
960
3.86M
  }
961
962
  // Assuming that the minuend and subtrahend are already sorted with
963
  // the same comparison function, shallow clears this and then copies
964
  // the set difference minuend - subtrahend to this, being the elements
965
  // of minuend that do not compare equal to anything in subtrahend.
966
  // If unique is true, any duplicates in minuend are also eliminated.
967
  void set_subtract(int comparator(const T *, const T *), bool unique, ConsList *minuend,
968
0
    ConsList *subtrahend) {
969
0
    shallow_clear();
970
0
    Iterator m_it(minuend);
971
0
    Iterator s_it(subtrahend);
972
    // Since both lists are sorted, finding the subtras that are not
973
    // minus is a case of a parallel iteration.
974
0
    for (m_it.mark_cycle_pt(); !m_it.cycled_list(); m_it.forward()) {
975
0
      auto minu = m_it.data();
976
0
      T *subtra = nullptr;
977
0
      if (!s_it.empty()) {
978
0
        subtra = s_it.data();
979
0
        while (!s_it.at_last() && comparator(subtra, minu) < 0) {
980
0
          s_it.forward();
981
0
          subtra = s_it.data();
982
0
        }
983
0
      }
984
0
      if (subtra == nullptr || comparator(subtra, minu) != 0) {
985
0
        add_sorted(comparator, unique, minu);
986
0
      }
987
0
    }
988
0
  }
989
};
990
991
#define CLISTIZEH(T)                          \
992
  class T##_CLIST : public ConsList<T> {      \
993
    using ConsList<T>::ConsList;              \
994
  };                                          \
995
  using T##_C_IT = ConsList<T>::Iterator;
996
997
} // namespace tesseract
998
999
#endif