Method add_sorted

deps/tesseract/ccutil/elst2.cpp:146–173

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.

// indirection. Time is O(1) to add to beginning or end.
// Time is linear to add pre-sorted items to an empty list.
void ELIST2::add_sorted(int comparator(const void*, const void*),
                        ELIST2_LINK* new_link) {
  // Check for adding at the end.
  if (last == NULL || comparator(&last, &new_link) < 0) {
    if (last == NULL) {
      new_link->next = new_link;
      new_link->prev = new_link;
    } else {
      new_link->next = last->next;
      new_link->prev = last;
      last->next = new_link;
      new_link->next->prev = new_link;
    }
    last = new_link;
  } else {
    // Need to use an iterator.
    ELIST2_ITERATOR it(this);
    for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
      ELIST2_LINK* link = it.data();
      if (comparator(&link, &new_link) > 0)
        break;
    }
    if (it.cycled_list())
      it.add_to_end(new_link);
    else
      it.add_before_then_move(new_link);
  }
}

/***********************************************************************
 *  MEMBER FUNCTIONS OF CLASS: ELIST2_ITERATOR