Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/tesseract/src/ccutil/clst.h @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
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 "list.h"
23 #include "lsterr.h"
24 #include "serialis.h"
25
26 #include <cstdio>
27
28 namespace tesseract {
29
30 class CLIST_ITERATOR;
31
32 /**********************************************************************
33 * CLASS - CLIST_LINK
34 *
35 * Generic link class for singly linked CONS cell lists
36 *
37 * Note: No destructor - elements are assumed to be destroyed EITHER after
38 * they have been extracted from a list OR by the CLIST destructor which
39 * walks the list.
40 **********************************************************************/
41
42 class CLIST_LINK {
43 friend class CLIST_ITERATOR;
44 friend class CLIST;
45
46 CLIST_LINK *next;
47 void *data;
48
49 public:
50 CLIST_LINK() { // constructor
51 data = next = nullptr;
52 }
53
54 CLIST_LINK(const CLIST_LINK &) = delete;
55 void operator=(const CLIST_LINK &) = delete;
56 };
57
58 /**********************************************************************
59 * CLASS - CLIST
60 *
61 * Generic list class for singly linked CONS cell lists
62 **********************************************************************/
63
64 class TESS_API CLIST {
65 friend class CLIST_ITERATOR;
66
67 CLIST_LINK *last = nullptr; // End of list
68
69 //(Points to head)
70 CLIST_LINK *First() { // return first
71 return last != nullptr ? last->next : nullptr;
72 }
73
74 const CLIST_LINK *First() const { // return first
75 return last != nullptr ? last->next : nullptr;
76 }
77
78 public:
79 ~CLIST() { // destructor
80 shallow_clear();
81 }
82
83 void internal_deep_clear( // destroy all links
84 void (*zapper)(void *)); // ptr to zapper functn
85
86 void shallow_clear(); // clear list but don't
87 // delete data elements
88
89 bool empty() const { // is list empty?
90 return !last;
91 }
92
93 bool singleton() const {
94 return last != nullptr ? (last == last->next) : false;
95 }
96
97 void shallow_copy( // dangerous!!
98 CLIST *from_list) { // beware destructors!!
99 last = from_list->last;
100 }
101
102 void assign_to_sublist( // to this list
103 CLIST_ITERATOR *start_it, // from list start
104 CLIST_ITERATOR *end_it); // from list end
105
106 int32_t length() const { //# elements in list
107 int32_t count = 0;
108 if (last != nullptr) {
109 count = 1;
110 for (auto it = last->next; it != last; it = it->next) {
111 count++;
112 }
113 }
114 return count;
115 }
116
117 void sort( // sort elements
118 int comparator( // comparison routine
119 const void *, const void *));
120
121 // Assuming list has been sorted already, insert new_data to
122 // keep the list sorted according to the same comparison function.
123 // Comparison function is the same as used by sort, i.e. uses double
124 // indirection. Time is O(1) to add to beginning or end.
125 // Time is linear to add pre-sorted items to an empty list.
126 // If unique, then don't add duplicate entries.
127 // Returns true if the element was added to the list.
128 bool add_sorted(int comparator(const void *, const void *), bool unique, void *new_data);
129
130 // Assuming that the minuend and subtrahend are already sorted with
131 // the same comparison function, shallow clears this and then copies
132 // the set difference minuend - subtrahend to this, being the elements
133 // of minuend that do not compare equal to anything in subtrahend.
134 // If unique is true, any duplicates in minuend are also eliminated.
135 void set_subtract(int comparator(const void *, const void *), bool unique, CLIST *minuend,
136 CLIST *subtrahend);
137 };
138
139 /***********************************************************************
140 * CLASS - CLIST_ITERATOR
141 *
142 * Generic iterator class for singly linked lists with embedded
143 *links
144 **********************************************************************/
145
146 class TESS_API CLIST_ITERATOR {
147 friend void CLIST::assign_to_sublist(CLIST_ITERATOR *, CLIST_ITERATOR *);
148
149 CLIST *list; // List being iterated
150 CLIST_LINK *prev; // prev element
151 CLIST_LINK *current; // current element
152 CLIST_LINK *next; // next element
153 CLIST_LINK *cycle_pt; // point we are cycling the list to.
154 bool ex_current_was_last; // current extracted was end of list
155 bool ex_current_was_cycle_pt; // current extracted was cycle point
156 bool started_cycling; // Have we moved off the start?
157
158 CLIST_LINK *extract_sublist( // from this current...
159 CLIST_ITERATOR *other_it); // to other current
160
161 public:
162 CLIST_ITERATOR() { // constructor
163 list = nullptr;
164 } // unassigned list
165
166 CLIST_ITERATOR( // constructor
167 CLIST *list_to_iterate);
168
169 void set_to_list( // change list
170 CLIST *list_to_iterate);
171
172 void add_after_then_move( // add after current &
173 void *new_data); // move to new
174
175 void add_after_stay_put( // add after current &
176 void *new_data); // stay at current
177
178 void add_before_then_move( // add before current &
179 void *new_data); // move to new
180
181 void add_before_stay_put( // add before current &
182 void *new_data); // stay at current
183
184 void add_list_after( // add a list &
185 CLIST *list_to_add); // stay at current
186
187 void add_list_before( // add a list &
188 CLIST *list_to_add); // move to it 1st item
189
190 void *data() { // get current data
191 #ifndef NDEBUG
192 if (!list) {
193 NO_LIST.error("CLIST_ITERATOR::data", ABORT);
194 }
195 #endif
196 return current->data;
197 }
198
199 void *data_relative( // get data + or - ...
200 int8_t offset); // offset from current
201
202 void *forward(); // move to next element
203
204 void *extract(); // remove from list
205
206 void *move_to_first(); // go to start of list
207
208 void *move_to_last(); // go to end of list
209
210 void mark_cycle_pt(); // remember current
211
212 bool empty() const { // is list empty?
213 return list->empty();
214 }
215
216 bool current_extracted() const { // current extracted?
217 return !current;
218 }
219
220 bool at_first() const; // Current is first?
221
222 bool at_last() const; // Current is last?
223
224 bool cycled_list() const; // Completed a cycle?
225
226 void add_to_end( // add at end &
227 void *new_data); // don't move
228
229 void exchange( // positions of 2 links
230 CLIST_ITERATOR *other_it); // other iterator
231
232 int32_t length() const; //# elements in list
233
234 void sort( // sort elements
235 int comparator( // comparison routine
236 const void *, const void *));
237 };
238
239 /***********************************************************************
240 * CLIST_ITERATOR::set_to_list
241 *
242 * (Re-)initialise the iterator to point to the start of the list_to_iterate
243 * over.
244 **********************************************************************/
245
246 inline void CLIST_ITERATOR::set_to_list( // change list
247 CLIST *list_to_iterate) {
248 list = list_to_iterate;
249 prev = list->last;
250 current = list->First();
251 next = current != nullptr ? current->next : nullptr;
252 cycle_pt = nullptr; // await explicit set
253 started_cycling = false;
254 ex_current_was_last = false;
255 ex_current_was_cycle_pt = false;
256 }
257
258 /***********************************************************************
259 * CLIST_ITERATOR::CLIST_ITERATOR
260 *
261 * CONSTRUCTOR - set iterator to specified list;
262 **********************************************************************/
263
264 inline CLIST_ITERATOR::CLIST_ITERATOR(CLIST *list_to_iterate) {
265 set_to_list(list_to_iterate);
266 }
267
268 /***********************************************************************
269 * CLIST_ITERATOR::add_after_then_move
270 *
271 * Add a new element to the list after the current element and move the
272 * iterator to the new element.
273 **********************************************************************/
274
275 inline void CLIST_ITERATOR::add_after_then_move( // element to add
276 void *new_data) {
277 #ifndef NDEBUG
278 if (!new_data) {
279 BAD_PARAMETER.error("CLIST_ITERATOR::add_after_then_move", ABORT, "new_data is nullptr");
280 }
281 #endif
282
283 auto new_element = new CLIST_LINK;
284 new_element->data = new_data;
285
286 if (list->empty()) {
287 new_element->next = new_element;
288 list->last = new_element;
289 prev = next = new_element;
290 } else {
291 new_element->next = next;
292
293 if (current) { // not extracted
294 current->next = new_element;
295 prev = current;
296 if (current == list->last) {
297 list->last = new_element;
298 }
299 } else { // current extracted
300 prev->next = new_element;
301 if (ex_current_was_last) {
302 list->last = new_element;
303 }
304 if (ex_current_was_cycle_pt) {
305 cycle_pt = new_element;
306 }
307 }
308 }
309 current = new_element;
310 }
311
312 /***********************************************************************
313 * CLIST_ITERATOR::add_after_stay_put
314 *
315 * Add a new element to the list after the current element but do not move
316 * the iterator to the new element.
317 **********************************************************************/
318
319 inline void CLIST_ITERATOR::add_after_stay_put( // element to add
320 void *new_data) {
321 #ifndef NDEBUG
322 if (!new_data) {
323 BAD_PARAMETER.error("CLIST_ITERATOR::add_after_stay_put", ABORT, "new_data is nullptr");
324 }
325 #endif
326
327 auto new_element = new CLIST_LINK;
328 new_element->data = new_data;
329
330 if (list->empty()) {
331 new_element->next = new_element;
332 list->last = new_element;
333 prev = next = new_element;
334 ex_current_was_last = false;
335 current = nullptr;
336 } else {
337 new_element->next = next;
338
339 if (current) { // not extracted
340 current->next = new_element;
341 if (prev == current) {
342 prev = new_element;
343 }
344 if (current == list->last) {
345 list->last = new_element;
346 }
347 } else { // current extracted
348 prev->next = new_element;
349 if (ex_current_was_last) {
350 list->last = new_element;
351 ex_current_was_last = false;
352 }
353 }
354 next = new_element;
355 }
356 }
357
358 /***********************************************************************
359 * CLIST_ITERATOR::add_before_then_move
360 *
361 * Add a new element to the list before the current element and move the
362 * iterator to the new element.
363 **********************************************************************/
364
365 inline void CLIST_ITERATOR::add_before_then_move( // element to add
366 void *new_data) {
367 #ifndef NDEBUG
368 if (!new_data) {
369 BAD_PARAMETER.error("CLIST_ITERATOR::add_before_then_move", ABORT, "new_data is nullptr");
370 }
371 #endif
372
373 auto new_element = new CLIST_LINK;
374 new_element->data = new_data;
375
376 if (list->empty()) {
377 new_element->next = new_element;
378 list->last = new_element;
379 prev = next = new_element;
380 } else {
381 prev->next = new_element;
382 if (current) { // not extracted
383 new_element->next = current;
384 next = current;
385 } else { // current extracted
386 new_element->next = next;
387 if (ex_current_was_last) {
388 list->last = new_element;
389 }
390 if (ex_current_was_cycle_pt) {
391 cycle_pt = new_element;
392 }
393 }
394 }
395 current = new_element;
396 }
397
398 /***********************************************************************
399 * CLIST_ITERATOR::add_before_stay_put
400 *
401 * Add a new element to the list before the current element but don't move the
402 * iterator to the new element.
403 **********************************************************************/
404
405 inline void CLIST_ITERATOR::add_before_stay_put( // element to add
406 void *new_data) {
407 #ifndef NDEBUG
408 if (!new_data) {
409 BAD_PARAMETER.error("CLIST_ITERATOR::add_before_stay_put", ABORT, "new_data is nullptr");
410 }
411 #endif
412
413 auto new_element = new CLIST_LINK;
414 new_element->data = new_data;
415
416 if (list->empty()) {
417 new_element->next = new_element;
418 list->last = new_element;
419 prev = next = new_element;
420 ex_current_was_last = true;
421 current = nullptr;
422 } else {
423 prev->next = new_element;
424 if (current) { // not extracted
425 new_element->next = current;
426 if (next == current) {
427 next = new_element;
428 }
429 } else { // current extracted
430 new_element->next = next;
431 if (ex_current_was_last) {
432 list->last = new_element;
433 }
434 }
435 prev = new_element;
436 }
437 }
438
439 /***********************************************************************
440 * CLIST_ITERATOR::add_list_after
441 *
442 * Insert another list to this list after the current element but don't move
443 *the
444 * iterator.
445 **********************************************************************/
446
447 inline void CLIST_ITERATOR::add_list_after(CLIST *list_to_add) {
448 if (!list_to_add->empty()) {
449 if (list->empty()) {
450 list->last = list_to_add->last;
451 prev = list->last;
452 next = list->First();
453 ex_current_was_last = true;
454 current = nullptr;
455 } else {
456 if (current) { // not extracted
457 current->next = list_to_add->First();
458 if (current == list->last) {
459 list->last = list_to_add->last;
460 }
461 list_to_add->last->next = next;
462 next = current->next;
463 } else { // current extracted
464 prev->next = list_to_add->First();
465 if (ex_current_was_last) {
466 list->last = list_to_add->last;
467 ex_current_was_last = false;
468 }
469 list_to_add->last->next = next;
470 next = prev->next;
471 }
472 }
473 list_to_add->last = nullptr;
474 }
475 }
476
477 /***********************************************************************
478 * CLIST_ITERATOR::add_list_before
479 *
480 * Insert another list to this list before the current element. Move the
481 * iterator to the start of the inserted elements
482 * iterator.
483 **********************************************************************/
484
485 inline void CLIST_ITERATOR::add_list_before(CLIST *list_to_add) {
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 if (current) { // not extracted
496 list_to_add->last->next = current;
497 } else { // current extracted
498 list_to_add->last->next = next;
499 if (ex_current_was_last) {
500 list->last = list_to_add->last;
501 }
502 if (ex_current_was_cycle_pt) {
503 cycle_pt = prev->next;
504 }
505 }
506 current = prev->next;
507 next = current->next;
508 }
509 list_to_add->last = nullptr;
510 }
511 }
512
513 /***********************************************************************
514 * CLIST_ITERATOR::extract
515 *
516 * Do extraction by removing current from the list, deleting the cons cell
517 * and returning the data to the caller, but NOT updating the iterator. (So
518 * that any calling loop can do this.) The iterator's current points to
519 * nullptr. If the data is to be deleted, this is the callers responsibility.
520 **********************************************************************/
521
522 inline void *CLIST_ITERATOR::extract() {
523 #ifndef NDEBUG
524 if (!current) { // list empty or
525 // element extracted
526 NULL_CURRENT.error("CLIST_ITERATOR::extract", ABORT);
527 }
528 #endif
529
530 if (list->singleton()) {
531 // Special case where we do need to change the iterator.
532 prev = next = list->last = nullptr;
533 } else {
534 prev->next = next; // remove from list
535
536 if (current == list->last) {
537 list->last = prev;
538 ex_current_was_last = true;
539 } else {
540 ex_current_was_last = false;
541 }
542 }
543 // Always set ex_current_was_cycle_pt so an add/forward will work in a loop.
544 ex_current_was_cycle_pt = (current == cycle_pt);
545 auto extracted_data = current->data;
546 delete (current); // destroy CONS cell
547 current = nullptr;
548 return extracted_data;
549 }
550
551 /***********************************************************************
552 * CLIST_ITERATOR::move_to_first()
553 *
554 * Move current so that it is set to the start of the list.
555 * Return data just in case anyone wants it.
556 **********************************************************************/
557
558 inline void *CLIST_ITERATOR::move_to_first() {
559 current = list->First();
560 prev = list->last;
561 next = current != nullptr ? current->next : nullptr;
562 return current != nullptr ? current->data : nullptr;
563 }
564
565 /***********************************************************************
566 * CLIST_ITERATOR::mark_cycle_pt()
567 *
568 * Remember the current location so that we can tell whether we've returned
569 * to this point later.
570 *
571 * If the current point is deleted either now, or in the future, the cycle
572 * point will be set to the next item which is set to current. This could be
573 * by a forward, add_after_then_move or add_after_then_move.
574 **********************************************************************/
575
576 inline void CLIST_ITERATOR::mark_cycle_pt() {
577 #ifndef NDEBUG
578 if (!list) {
579 NO_LIST.error("CLIST_ITERATOR::mark_cycle_pt", ABORT);
580 }
581 #endif
582
583 if (current) {
584 cycle_pt = current;
585 } else {
586 ex_current_was_cycle_pt = true;
587 }
588 started_cycling = false;
589 }
590
591 /***********************************************************************
592 * CLIST_ITERATOR::at_first()
593 *
594 * Are we at the start of the list?
595 *
596 **********************************************************************/
597
598 inline bool CLIST_ITERATOR::at_first() const {
599 // we're at a deleted
600 return ((list->empty()) || (current == list->First()) ||
601 ((current == nullptr) && (prev == list->last) && // NON-last pt between
602 !ex_current_was_last)); // first and last
603 }
604
605 /***********************************************************************
606 * CLIST_ITERATOR::at_last()
607 *
608 * Are we at the end of the list?
609 *
610 **********************************************************************/
611
612 inline bool CLIST_ITERATOR::at_last() const {
613 // we're at a deleted
614 return ((list->empty()) || (current == list->last) ||
615 ((current == nullptr) && (prev == list->last) && // last point between
616 ex_current_was_last)); // first and last
617 }
618
619 /***********************************************************************
620 * CLIST_ITERATOR::cycled_list()
621 *
622 * Have we returned to the cycle_pt since it was set?
623 *
624 **********************************************************************/
625
626 inline bool CLIST_ITERATOR::cycled_list() const {
627 return ((list->empty()) || ((current == cycle_pt) && started_cycling));
628 }
629
630 /***********************************************************************
631 * CLIST_ITERATOR::length()
632 *
633 * Return the length of the list
634 *
635 **********************************************************************/
636
637 inline int32_t CLIST_ITERATOR::length() const {
638 return list->length();
639 }
640
641 /***********************************************************************
642 * CLIST_ITERATOR::sort()
643 *
644 * Sort the elements of the list, then reposition at the start.
645 *
646 **********************************************************************/
647
648 inline void CLIST_ITERATOR::sort( // sort elements
649 int comparator( // comparison routine
650 const void *, const void *)) {
651 list->sort(comparator);
652 move_to_first();
653 }
654
655 /***********************************************************************
656 * CLIST_ITERATOR::add_to_end
657 *
658 * Add a new element to the end of the list without moving the iterator.
659 * This is provided because a single linked list cannot move to the last as
660 * the iterator couldn't set its prev pointer. Adding to the end is
661 * essential for implementing
662 queues.
663 **********************************************************************/
664
665 inline void CLIST_ITERATOR::add_to_end( // element to add
666 void *new_data) {
667 #ifndef NDEBUG
668 if (!list) {
669 NO_LIST.error("CLIST_ITERATOR::add_to_end", ABORT);
670 }
671 if (!new_data) {
672 BAD_PARAMETER.error("CLIST_ITERATOR::add_to_end", ABORT, "new_data is nullptr");
673 }
674 #endif
675
676 if (this->at_last()) {
677 this->add_after_stay_put(new_data);
678 } else {
679 if (this->at_first()) {
680 this->add_before_stay_put(new_data);
681 list->last = prev;
682 } else { // Iteratr is elsewhere
683 auto new_element = new CLIST_LINK;
684 new_element->data = new_data;
685
686 new_element->next = list->last->next;
687 list->last->next = new_element;
688 list->last = new_element;
689 }
690 }
691 }
692
693 template <typename CLASSNAME>
694 class X_CLIST : public CLIST {
695 public:
696 X_CLIST() = default;
697 X_CLIST(const X_CLIST &) = delete;
698 X_CLIST &operator=(const X_CLIST &) = delete;
699
700 void deep_clear() {
701 internal_deep_clear([](void *link) {delete static_cast<CLASSNAME *>(link);});
702 }
703 };
704
705 #define CLISTIZEH(CLASSNAME) \
706 class CLASSNAME##_CLIST : public X_CLIST<CLASSNAME> { \
707 using X_CLIST<CLASSNAME>::X_CLIST; \
708 }; \
709 struct CLASSNAME##_C_IT : X_ITER<CLIST_ITERATOR, CLASSNAME> { \
710 using X_ITER<CLIST_ITERATOR, CLASSNAME>::X_ITER; \
711 };
712
713 } // namespace tesseract
714
715 #endif