/********************************************************************** * File: elst.h (Formerly elist.h) * Description: Embedded list module include file. * Author: Phil Cheatle * * (C) Copyright 1991, Hewlett-Packard Ltd. ** Licensed under the Apache License, Version 2.0 (the "License"); ** you may not use this file except in compliance with the License. ** You may obtain a copy of the License at ** http://www.apache.org/licenses/LICENSE-2.0 ** Unless required by applicable law or agreed to in writing, software ** distributed under the License is distributed on an "AS IS" BASIS, ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. ** See the License for the specific language governing permissions and ** limitations under the License. * **********************************************************************/ #ifndef ELST_H #define ELST_H #include "lsterr.h" #include "serialis.h" #include #include namespace tesseract { /********************************************************************** This module implements list classes and iterators. The following list types and iterators are provided: List type List Class Iterator Class Element Class --------- ---------- -------------- ------------- Embedded list ELIST ELIST_ITERATOR ELIST_LINK (Single linked) Embedded list ELIST2 ELIST2_ITERATOR ELIST2_LINK (Double linked) Cons List CLIST CLIST_ITERATOR CLIST_LINK (Single linked) An embedded list is where the list pointers are provided by a generic class. Data types to be listed inherit from the generic class. Data is thus linked in only ONE list at any one time. A cons list has a separate structure for a "cons cell". This contains the list pointer(s) AND a pointer to the data structure held on the list. A structure can be on many cons lists at the same time, and the structure does not need to inherit from any generic class in order to be on the list. The implementation of lists is very careful about space and speed overheads. This is why many embedded lists are provided. The same concerns mean that in-line type coercion is done, rather than use virtual functions. This is cumbersome in that each data type to be listed requires its own iterator and list class - though macros can generate these. It also prevents heterogeneous lists. **********************************************************************/ /********************************************************************** * CLASS - ELIST * * Generic list class for singly linked lists with embedded links **********************************************************************/ template class IntrusiveForwardList { public: /********************************************************************** * CLASS - ELIST_LINK * * Generic link class for singly linked lists with *embedded links * * Note: No destructor - elements are assumed to be destroyed EITHER after * they have been extracted from a list OR by the IntrusiveForwardList destructor which * walks the list. **********************************************************************/ class Link { friend class Iterator; friend class IntrusiveForwardList; T *next; public: Link() { next = nullptr; } // constructor // The special copy constructor is used by lots of classes. Link(const Link &) { next = nullptr; } // The special assignment operator is used by lots of classes. void operator=(const Link &) { next = nullptr; } }; using LINK = Link; // compat /*********************************************************************** * CLASS - ELIST_ITERATOR * * Generic iterator class for singly linked lists with *embedded links **********************************************************************/ class Iterator { friend void IntrusiveForwardList::assign_to_sublist(Iterator *, Iterator *); IntrusiveForwardList *list; // List being iterated T *prev; // prev element T *current; // current element T *next; // next element T *cycle_pt; // point we are cycling the list to. bool ex_current_was_last; // current extracted was end of list bool ex_current_was_cycle_pt; // current extracted was cycle point bool started_cycling; // Have we moved off the start? /*********************************************************************** * Iterator::extract_sublist() * * This is a private member, used only by IntrusiveForwardList::assign_to_sublist. * Given another iterator for the same list, extract the links from THIS to * OTHER inclusive, link them into a new circular list, and return a * pointer to the last element. * (Can't inline this function because it contains a loop) **********************************************************************/ T *extract_sublist( // from this current... Iterator *other_it) { // to other current #ifndef NDEBUG constexpr ERRCODE BAD_EXTRACTION_PTS("Can't extract sublist from points on different lists"); constexpr ERRCODE DONT_EXTRACT_DELETED("Can't extract a sublist marked by deleted points"); #endif constexpr ERRCODE BAD_SUBLIST("Can't find sublist end point in original list"); Iterator temp_it = *this; T *end_of_new_list; #ifndef NDEBUG if (!other_it) BAD_PARAMETER.error("ELIST_ITERATOR::extract_sublist", ABORT, "other_it nullptr"); if (!list) NO_LIST.error("ELIST_ITERATOR::extract_sublist", ABORT); if (list != other_it->list) BAD_EXTRACTION_PTS.error("ELIST_ITERATOR.extract_sublist", ABORT); if (list->empty()) EMPTY_LIST.error("ELIST_ITERATOR::extract_sublist", ABORT); if (!current || !other_it->current) DONT_EXTRACT_DELETED.error("ELIST_ITERATOR.extract_sublist", ABORT); #endif ex_current_was_last = other_it->ex_current_was_last = false; ex_current_was_cycle_pt = false; other_it->ex_current_was_cycle_pt = false; temp_it.mark_cycle_pt(); do { // walk sublist if (temp_it.cycled_list()) { // can't find end pt BAD_SUBLIST.error("Iterator.extract_sublist", ABORT); } if (temp_it.at_last()) { list->last = prev; ex_current_was_last = other_it->ex_current_was_last = true; } if (temp_it.current == cycle_pt) { ex_current_was_cycle_pt = true; } if (temp_it.current == other_it->cycle_pt) { other_it->ex_current_was_cycle_pt = true; } temp_it.forward(); } while (temp_it.prev != other_it->current); // circularise sublist other_it->current->next = current; end_of_new_list = other_it->current; // sublist = whole list if (prev == other_it->current) { list->last = nullptr; prev = current = next = nullptr; other_it->prev = other_it->current = other_it->next = nullptr; } else { prev->next = other_it->next; current = other_it->current = nullptr; next = other_it->next; other_it->prev = prev; } return end_of_new_list; } // to other current public: Iterator() { // constructor list = nullptr; } // unassigned list /*********************************************************************** * ELIST_ITERATOR::ELIST_ITERATOR * * CONSTRUCTOR - set iterator to specified list; **********************************************************************/ Iterator(IntrusiveForwardList *list_to_iterate) { set_to_list(list_to_iterate); } /*********************************************************************** * ELIST_ITERATOR::set_to_list * * (Re-)initialise the iterator to point to the start of the list_to_iterate * over. **********************************************************************/ void set_to_list( // change list IntrusiveForwardList *list_to_iterate) { #ifndef NDEBUG if (!list_to_iterate) { BAD_PARAMETER.error("ELIST_ITERATOR::set_to_list", ABORT, "list_to_iterate is nullptr"); } #endif list = list_to_iterate; prev = list->last; current = list->First(); next = current ? current->next : nullptr; cycle_pt = nullptr; // await explicit set started_cycling = false; ex_current_was_last = false; ex_current_was_cycle_pt = false; } /*********************************************************************** * ELIST_ITERATOR::add_after_then_move * * Add a new element to the list after the current element and move the * iterator to the new element. **********************************************************************/ void add_after_then_move( // add after current & T *new_element) { #ifndef NDEBUG if (!list) { NO_LIST.error("ELIST_ITERATOR::add_after_then_move", ABORT); } if (!new_element) { BAD_PARAMETER.error("ELIST_ITERATOR::add_after_then_move", ABORT, "new_element is nullptr"); } if (new_element->next) { STILL_LINKED.error("ELIST_ITERATOR::add_after_then_move", ABORT); } #endif if (list->empty()) { new_element->next = new_element; list->last = new_element; prev = next = new_element; } else { new_element->next = next; if (current) { // not extracted current->next = new_element; prev = current; if (current == list->last) { list->last = new_element; } } else { // current extracted prev->next = new_element; if (ex_current_was_last) { list->last = new_element; } if (ex_current_was_cycle_pt) { cycle_pt = new_element; } } } current = new_element; } // move to new /*********************************************************************** * ELIST_ITERATOR::add_after_stay_put * * Add a new element to the list after the current element but do not move * the iterator to the new element. **********************************************************************/ void add_after_stay_put( // add after current & T *new_element) { #ifndef NDEBUG if (!list) { NO_LIST.error("ELIST_ITERATOR::add_after_stay_put", ABORT); } if (!new_element) { BAD_PARAMETER.error("ELIST_ITERATOR::add_after_stay_put", ABORT, "new_element is nullptr"); } if (new_element->next) { STILL_LINKED.error("ELIST_ITERATOR::add_after_stay_put", ABORT); } #endif if (list->empty()) { new_element->next = new_element; list->last = new_element; prev = next = new_element; ex_current_was_last = false; current = nullptr; } else { new_element->next = next; if (current) { // not extracted current->next = new_element; if (prev == current) { prev = new_element; } if (current == list->last) { list->last = new_element; } } else { // current extracted prev->next = new_element; if (ex_current_was_last) { list->last = new_element; ex_current_was_last = false; } } next = new_element; } } // stay at current /*********************************************************************** * ELIST_ITERATOR::add_before_then_move * * Add a new element to the list before the current element and move the * iterator to the new element. **********************************************************************/ void add_before_then_move( // add before current & T *new_element) { #ifndef NDEBUG if (!list) { NO_LIST.error("ELIST_ITERATOR::add_before_then_move", ABORT); } if (!new_element) { BAD_PARAMETER.error("ELIST_ITERATOR::add_before_then_move", ABORT, "new_element is nullptr"); } if (new_element->next) { STILL_LINKED.error("ELIST_ITERATOR::add_before_then_move", ABORT); } #endif if (list->empty()) { new_element->next = new_element; list->last = new_element; prev = next = new_element; } else { prev->next = new_element; if (current) { // not extracted new_element->next = current; next = current; } else { // current extracted new_element->next = next; if (ex_current_was_last) { list->last = new_element; } if (ex_current_was_cycle_pt) { cycle_pt = new_element; } } } current = new_element; } // move to new /*********************************************************************** * ELIST_ITERATOR::add_before_stay_put * * Add a new element to the list before the current element but don't move the * iterator to the new element. **********************************************************************/ void add_before_stay_put( // add before current & T *new_element) { #ifndef NDEBUG if (!list) { NO_LIST.error("ELIST_ITERATOR::add_before_stay_put", ABORT); } if (!new_element) { BAD_PARAMETER.error("ELIST_ITERATOR::add_before_stay_put", ABORT, "new_element is nullptr"); } if (new_element->next) { STILL_LINKED.error("ELIST_ITERATOR::add_before_stay_put", ABORT); } #endif if (list->empty()) { new_element->next = new_element; list->last = new_element; prev = next = new_element; ex_current_was_last = true; current = nullptr; } else { prev->next = new_element; if (current) { // not extracted new_element->next = current; if (next == current) { next = new_element; } } else { // current extracted new_element->next = next; if (ex_current_was_last) { list->last = new_element; } } prev = new_element; } } // stay at current /*********************************************************************** * ELIST_ITERATOR::add_list_after * * Insert another list to this list after the current element but don't move *the * iterator. **********************************************************************/ void add_list_after( // add a list & IntrusiveForwardList *list_to_add) { #ifndef NDEBUG if (!list) { NO_LIST.error("ELIST_ITERATOR::add_list_after", ABORT); } if (!list_to_add) { BAD_PARAMETER.error("ELIST_ITERATOR::add_list_after", ABORT, "list_to_add is nullptr"); } #endif if (!list_to_add->empty()) { if (list->empty()) { list->last = list_to_add->last; prev = list->last; next = list->First(); ex_current_was_last = true; current = nullptr; } else { if (current) { // not extracted current->next = list_to_add->First(); if (current == list->last) { list->last = list_to_add->last; } list_to_add->last->next = next; next = current->next; } else { // current extracted prev->next = list_to_add->First(); if (ex_current_was_last) { list->last = list_to_add->last; ex_current_was_last = false; } list_to_add->last->next = next; next = prev->next; } } list_to_add->last = nullptr; } } // stay at current /*********************************************************************** * ELIST_ITERATOR::add_list_before * * Insert another list to this list before the current element. Move the * iterator to the start of the inserted elements * iterator. **********************************************************************/ void add_list_before( // add a list & IntrusiveForwardList *list_to_add) { #ifndef NDEBUG if (!list) { NO_LIST.error("ELIST_ITERATOR::add_list_before", ABORT); } if (!list_to_add) { BAD_PARAMETER.error("ELIST_ITERATOR::add_list_before", ABORT, "list_to_add is nullptr"); } #endif if (!list_to_add->empty()) { if (list->empty()) { list->last = list_to_add->last; prev = list->last; current = list->First(); next = current->next; ex_current_was_last = false; } else { prev->next = list_to_add->First(); if (current) { // not extracted list_to_add->last->next = current; } else { // current extracted list_to_add->last->next = next; if (ex_current_was_last) { list->last = list_to_add->last; } if (ex_current_was_cycle_pt) { cycle_pt = prev->next; } } current = prev->next; next = current->next; } list_to_add->last = nullptr; } } // move to it 1st item T *data() { // get current data #ifndef NDEBUG if (!list) { NO_LIST.error("ELIST_ITERATOR::data", ABORT); } if (!current) { NULL_DATA.error("ELIST_ITERATOR::data", ABORT); } #endif return current; } /*********************************************************************** * ELIST_ITERATOR::data_relative * * Return the data pointer to the element "offset" elements from current. * "offset" must not be less than -1. * (This function can't be INLINEd because it contains a loop) **********************************************************************/ T *data_relative( // get data + or - ... int8_t offset) { // offset from current T *ptr; #ifndef NDEBUG if (!list) NO_LIST.error("ELIST_ITERATOR::data_relative", ABORT); if (list->empty()) EMPTY_LIST.error("ELIST_ITERATOR::data_relative", ABORT); if (offset < -1) BAD_PARAMETER.error("ELIST_ITERATOR::data_relative", ABORT, "offset < -l"); #endif if (offset == -1) { ptr = prev; } else { for (ptr = current ? current : prev; offset-- > 0; ptr = ptr->next) { } } #ifndef NDEBUG if (!ptr) NULL_DATA.error("ELIST_ITERATOR::data_relative", ABORT); #endif return ptr; } // offset from current /*********************************************************************** * ELIST_ITERATOR::forward * * Move the iterator to the next element of the list. * REMEMBER: ALL LISTS ARE CIRCULAR. **********************************************************************/ T *forward() { #ifndef NDEBUG if (!list) NO_LIST.error("ELIST_ITERATOR::forward", ABORT); #endif if (list->empty()) { return nullptr; } if (current) { // not removed so // set previous prev = current; started_cycling = true; // In case next is deleted by another iterator, get next from current. current = current->next; } else { if (ex_current_was_cycle_pt) { cycle_pt = next; } current = next; } #ifndef NDEBUG if (!current) NULL_DATA.error("ELIST_ITERATOR::forward", ABORT); #endif next = current->next; #ifndef NDEBUG if (!next) { NULL_NEXT.error("ELIST_ITERATOR::forward", ABORT, "This is: %p Current is: %p", static_cast(this), static_cast(current)); } #endif return current; } // move to next element /*********************************************************************** * ELIST_ITERATOR::extract * * Do extraction by removing current from the list, returning it to the * caller, but NOT updating the iterator. (So that any calling loop can do * this.) The iterator's current points to nullptr. If the extracted element * is to be deleted, this is the callers responsibility. **********************************************************************/ T *extract() { T *extracted_link; #ifndef NDEBUG if (!list) { NO_LIST.error("ELIST_ITERATOR::extract", ABORT); } if (!current) { // list empty or // element extracted NULL_CURRENT.error("ELIST_ITERATOR::extract", ABORT); } #endif if (list->singleton()) { // Special case where we do need to change the iterator. prev = next = list->last = nullptr; } else { prev->next = next; // remove from list ex_current_was_last = (current == list->last); if (ex_current_was_last) { list->last = prev; } } // Always set ex_current_was_cycle_pt so an add/forward will work in a loop. ex_current_was_cycle_pt = (current == cycle_pt); extracted_link = current; extracted_link->next = nullptr; // for safety current = nullptr; return extracted_link; } // remove from list /*********************************************************************** * ELIST_ITERATOR::move_to_first() * * Move current so that it is set to the start of the list. * Return data just in case anyone wants it. **********************************************************************/ T *move_to_first() { #ifndef NDEBUG if (!list) { NO_LIST.error("ELIST_ITERATOR::move_to_first", ABORT); } #endif current = list->First(); prev = list->last; next = current ? current->next : nullptr; return current; } // go to start of list /*********************************************************************** * ELIST_ITERATOR::move_to_last() * * Move current so that it is set to the end of the list. * Return data just in case anyone wants it. * (This function can't be INLINEd because it contains a loop) **********************************************************************/ T *move_to_last() { #ifndef NDEBUG if (!list) NO_LIST.error("ELIST_ITERATOR::move_to_last", ABORT); #endif while (current != list->last) { forward(); } return current; } // go to end of list /*********************************************************************** * ELIST_ITERATOR::mark_cycle_pt() * * Remember the current location so that we can tell whether we've returned * to this point later. * * If the current point is deleted either now, or in the future, the cycle * point will be set to the next item which is set to current. This could be * by a forward, add_after_then_move or add_after_then_move. **********************************************************************/ void mark_cycle_pt() { #ifndef NDEBUG if (!list) { NO_LIST.error("ELIST_ITERATOR::mark_cycle_pt", ABORT); } #endif if (current) { cycle_pt = current; } else { ex_current_was_cycle_pt = true; } started_cycling = false; } // remember current bool empty() const { // is list empty? #ifndef NDEBUG if (!list) { NO_LIST.error("ELIST_ITERATOR::empty", ABORT); } #endif return list->empty(); } bool current_extracted() const { // current extracted? return !current; } /*********************************************************************** * ELIST_ITERATOR::at_first() * * Are we at the start of the list? * **********************************************************************/ bool at_first() const { #ifndef NDEBUG if (!list) { NO_LIST.error("ELIST_ITERATOR::at_first", ABORT); } #endif // we're at a deleted return ((list->empty()) || (current == list->First()) || ((current == nullptr) && (prev == list->last) && // NON-last pt between !ex_current_was_last)); // first and last } // Current is first? /*********************************************************************** * ELIST_ITERATOR::at_last() * * Are we at the end of the list? * **********************************************************************/ bool at_last() const { #ifndef NDEBUG if (!list) { NO_LIST.error("ELIST_ITERATOR::at_last", ABORT); } #endif // we're at a deleted return ((list->empty()) || (current == list->last) || ((current == nullptr) && (prev == list->last) && // last point between ex_current_was_last)); // first and last } // Current is last? /*********************************************************************** * ELIST_ITERATOR::cycled_list() * * Have we returned to the cycle_pt since it was set? * **********************************************************************/ bool cycled_list() const { #ifndef NDEBUG if (!list) { NO_LIST.error("ELIST_ITERATOR::cycled_list", ABORT); } #endif return ((list->empty()) || ((current == cycle_pt) && started_cycling)); } // Completed a cycle? /*********************************************************************** * ELIST_ITERATOR::add_to_end * * Add a new element to the end of the list without moving the iterator. * This is provided because a single linked list cannot move to the last as * the iterator couldn't set its prev pointer. Adding to the end is * essential for implementing queues. **********************************************************************/ void add_to_end( // add at end & T *new_element) { #ifndef NDEBUG if (!list) { NO_LIST.error("ELIST_ITERATOR::add_to_end", ABORT); } if (!new_element) { BAD_PARAMETER.error("ELIST_ITERATOR::add_to_end", ABORT, "new_element is nullptr"); } if (new_element->next) { STILL_LINKED.error("ELIST_ITERATOR::add_to_end", ABORT); } #endif if (this->at_last()) { this->add_after_stay_put(new_element); } else { if (this->at_first()) { this->add_before_stay_put(new_element); list->last = new_element; } else { // Iteratr is elsewhere new_element->next = list->last->next; list->last->next = new_element; list->last = new_element; } } } // don't move /*********************************************************************** * ELIST_ITERATOR::exchange() * * Given another iterator, whose current element is a different element on * the same list list OR an element of another list, exchange the two current * elements. On return, each iterator points to the element which was the * other iterators current on entry. * (This function hasn't been in-lined because its a bit big!) **********************************************************************/ void exchange( // positions of 2 links Iterator *other_it) { // other iterator constexpr ERRCODE DONT_EXCHANGE_DELETED("Can't exchange deleted elements of lists"); T *old_current; #ifndef NDEBUG if (!list) NO_LIST.error("ELIST_ITERATOR::exchange", ABORT); if (!other_it) BAD_PARAMETER.error("ELIST_ITERATOR::exchange", ABORT, "other_it nullptr"); if (!(other_it->list)) NO_LIST.error("ELIST_ITERATOR::exchange", ABORT, "other_it"); #endif /* Do nothing if either list is empty or if both iterators reference the same link */ if ((list->empty()) || (other_it->list->empty()) || (current == other_it->current)) { return; } /* Error if either current element is deleted */ if (!current || !other_it->current) { DONT_EXCHANGE_DELETED.error("ELIST_ITERATOR.exchange", ABORT); } /* Now handle the 4 cases: doubleton list; non-doubleton adjacent elements (other before this); non-doubleton adjacent elements (this before other); non-adjacent elements. */ // adjacent links if ((next == other_it->current) || (other_it->next == current)) { // doubleton list if ((next == other_it->current) && (other_it->next == current)) { prev = next = current; other_it->prev = other_it->next = other_it->current; } else { // non-doubleton with // adjacent links // other before this if (other_it->next == current) { other_it->prev->next = current; other_it->current->next = next; current->next = other_it->current; other_it->next = other_it->current; prev = current; } else { // this before other prev->next = other_it->current; current->next = other_it->next; other_it->current->next = current; next = current; other_it->prev = other_it->current; } } } else { // no overlap prev->next = other_it->current; current->next = other_it->next; other_it->prev->next = current; other_it->current->next = next; } /* update end of list pointer when necessary (remember that the 2 iterators may iterate over different lists!) */ if (list->last == current) { list->last = other_it->current; } if (other_it->list->last == other_it->current) { other_it->list->last = current; } if (current == cycle_pt) { cycle_pt = other_it->cycle_pt; } if (other_it->current == other_it->cycle_pt) { other_it->cycle_pt = cycle_pt; } /* The actual exchange - in all cases*/ old_current = current; current = other_it->current; other_it->current = old_current; } // other iterator //# elements in list int32_t length() const { return list->length(); } /*********************************************************************** * ELIST_ITERATOR::sort() * * Sort the elements of the list, then reposition at the start. * **********************************************************************/ void sort( // sort elements int comparator( // comparison routine const T *, const T *)) { #ifndef NDEBUG if (!list) { NO_LIST.error("ELIST_ITERATOR::sort", ABORT); } #endif list->sort(comparator); move_to_first(); } }; using ITERATOR = Iterator; // compat private: T *last = nullptr; // End of list //(Points to head) T *First() { // return first return last ? last->next : nullptr; } public: ~IntrusiveForwardList() { clear(); } /* delete elements */ void clear() { internal_clear(); } /* Become a deep copy of src_list */ template void deep_copy(const U *src_list, T *(*copier)(const T *)) { Iterator from_it(const_cast(src_list)); Iterator to_it(this); for (from_it.mark_cycle_pt(); !from_it.cycled_list(); from_it.forward()) to_it.add_after_then_move((*copier)(from_it.data())); } /*********************************************************************** * IntrusiveForwardList::internal_clear * * Used by the destructor and the "clear" member function of derived list * classes to destroy all the elements on the list. * The calling function passes a "zapper" function which can be called to * delete each element of the list, regardless of its derived type. This * technique permits a generic clear function to destroy elements of * different derived types correctly, without requiring virtual functions and * the consequential memory overhead. **********************************************************************/ // destroy all links void internal_clear() { T *ptr; T *next; if (!empty()) { ptr = last->next; // set to first last->next = nullptr; // break circle last = nullptr; // set list empty while (ptr) { next = ptr->next; delete ptr; ptr = next; } } } bool empty() const { return !last; } bool singleton() const { return last ? (last == last->next) : false; } void shallow_copy( // dangerous!! IntrusiveForwardList *from_list) { // beware destructors!! last = from_list->last; } /*********************************************************************** * IntrusiveForwardList::assign_to_sublist * * The list is set to a sublist of another list. "This" list must be empty * before this function is invoked. The two iterators passed must refer to * the same list, different from "this" one. The sublist removed is the * inclusive list from start_it's current position to end_it's current * position. If this range passes over the end of the source list then the * source list has its end set to the previous element of start_it. The * extracted sublist is unaffected by the end point of the source list, its * end point is always the end_it position. **********************************************************************/ void assign_to_sublist( // to this list Iterator *start_it, // from list start Iterator *end_it) { // from list end constexpr ERRCODE LIST_NOT_EMPTY("Destination list must be empty before extracting a sublist"); if (!empty()) { LIST_NOT_EMPTY.error("IntrusiveForwardList.assign_to_sublist", ABORT); } last = start_it->extract_sublist(end_it); } // from list end // # elements in list int32_t length() const { int32_t count = 0; if (last != nullptr) { count = 1; for (auto it = last->next; it != last; it = it->next) { count++; } } return count; } /*********************************************************************** * IntrusiveForwardList::sort * * Sort elements on list * NB If you don't like the const declarations in the comparator, coerce yours: * ( int (*)(const void *, const void *) **********************************************************************/ void sort( // sort elements int comparator( // comparison routine const T *, const T *)) { // Allocate an array of pointers, one per list element. auto count = length(); if (count > 0) { // ptr array to sort std::vector base; base.reserve(count); Iterator it(this); // Extract all elements, putting the pointers in the array. for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) { base.push_back(it.extract()); } // Sort the pointer array. std::sort(base.begin(), base.end(), // all current comparators return -1,0,1, so we handle this correctly for std::sort [&](auto &&l, auto &&r) {return comparator(l, r) < 0; }); // Rebuild the list from the sorted pointers. for (auto current : base) { it.add_to_end(current); } } } // Assuming list has been sorted already, insert new_link to // keep the list sorted according to the same comparison function. // Comparison function is the same as used by sort, i.e. uses double // indirection. Time is O(1) to add to beginning or end. // Time is linear to add pre-sorted items to an empty list. // If unique is set to true and comparator() returns 0 (an entry with the // same information as the one contained in new_link is already in the // list) - new_link is not added to the list and the function returns the // pointer to the identical entry that already exists in the list // (otherwise the function returns new_link). T *add_sorted_and_find(int comparator(const T *, const T *), bool unique, T *new_link) { // Check for adding at the end. if (last == nullptr || comparator(last, new_link) < 0) { if (last == nullptr) { new_link->next = new_link; } else { new_link->next = last->next; last->next = new_link; } last = new_link; } else { // Need to use an iterator. Iterator it(this); for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) { auto *link = it.data(); int compare = comparator(link, new_link); if (compare > 0) { break; } else if (unique && compare == 0) { return link; } } if (it.cycled_list()) { it.add_to_end(new_link); } else { it.add_before_then_move(new_link); } } return new_link; } // Same as above, but returns true if the new entry was inserted, false // if the identical entry already existed in the list. bool add_sorted(int comparator(const T *, const T *), bool unique, T *new_link) { return (add_sorted_and_find(comparator, unique, new_link) == new_link); } }; template using ELIST = IntrusiveForwardList; // add TESS_API? // move templated lists to public include dirs? #define ELISTIZEH(T) \ class T##_LIST : public IntrusiveForwardList { \ public: \ using IntrusiveForwardList::IntrusiveForwardList; \ }; \ class T##_IT : public IntrusiveForwardList::Iterator { \ public: \ using IntrusiveForwardList::Iterator::Iterator; \ }; } // namespace tesseract #endif