fpchop.cpp

Go to the documentation of this file.

/**********************************************************************
 * File:        fpchop.cpp  (Formerly fp_chop.c)
 * Description: Code to chop fixed pitch text into character cells.
 * Author:      Ray Smith
 *
 * (C) Copyright 1993, 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.
 *
 **********************************************************************/
 
// Include automatically generated configuration file if running autoconf.
#ifdef HAVE_CONFIG_H
#  include "config_auto.h"
#endif
 
#include "fpchop.h"
 
#include "blobbox.h"
#include "drawtord.h"
#include "statistc.h"
#include "topitch.h"
#include "tovars.h"
 
namespace tesseract {
 
INT_VAR(textord_fp_chop_error, 2, "Max allowed bending of chop cells");
 
static WERD *add_repeated_word(WERD_IT *rep_it, int16_t &rep_left, int16_t &prev_chop_coord,
                               uint8_t &blanks, float pitch, WERD_IT *word_it);
 
static void fixed_chop_cblob(C_BLOB *blob, int16_t chop_coord, float pitch_error,
                             C_OUTLINE_LIST *left_outlines, C_OUTLINE_LIST *right_outlines);
 
static void fixed_split_coutline(C_OUTLINE *srcline, int16_t chop_coord, float pitch_error,
                                 C_OUTLINE_IT *left_it, C_OUTLINE_IT *right_it);
 
static bool fixed_chop_coutline(C_OUTLINE *srcline, int16_t chop_coord, float pitch_error,
                                C_OUTLINE_FRAG_LIST *left_frags, C_OUTLINE_FRAG_LIST *right_frags);
 
static void save_chop_cfragment(int16_t head_index, ICOORD head_pos, int16_t tail_index,
                                ICOORD tail_pos, C_OUTLINE *srcline, C_OUTLINE_FRAG_LIST *frags);
 
static void add_frag_to_list(C_OUTLINE_FRAG *frag, C_OUTLINE_FRAG_LIST *frags);
 
static void close_chopped_cfragments(C_OUTLINE_FRAG_LIST *frags, C_OUTLINE_LIST *children,
                                     float pitch_error, C_OUTLINE_IT *dest_it);
 
static C_OUTLINE *join_chopped_fragments(C_OUTLINE_FRAG *bottom, C_OUTLINE_FRAG *top);
 
static void join_segments(C_OUTLINE_FRAG *bottom, C_OUTLINE_FRAG *top);
 
/**********************************************************************
 * fixed_pitch_words
 *
 * Make a ROW from a fixed pitch TO_ROW.
 **********************************************************************/
ROW *fixed_pitch_words( // find lines
    TO_ROW *row,        // row to do
    FCOORD rotation     // for drawing
) {
  bool bol;                // start of line
  uint8_t blanks;          // in front of word
  uint8_t new_blanks;      // blanks in empty cell
  int16_t chop_coord;      // chop boundary
  int16_t prev_chop_coord; // start of cell
  int16_t rep_left;        // left edge of rep word
  ROW *real_row;           // output row
  C_OUTLINE_LIST left_coutlines;
  C_OUTLINE_LIST right_coutlines;
  C_BLOB_LIST cblobs;
  C_BLOB_IT cblob_it = &cblobs;
  WERD_LIST words;
  WERD_IT word_it = &words; // new words
                            // repeated blobs
  WERD_IT rep_it = &row->rep_words;
  WERD *word;         // new word
  int32_t xstarts[2]; // row ends
  int32_t prev_x;     // end of prev blob
                      // iterator
  BLOBNBOX_IT box_it = row->blob_list();
  // boundaries
  ICOORDELT_IT cell_it = &row->char_cells;
 
#ifndef GRAPHICS_DISABLED
  if (textord_show_page_cuts && to_win != nullptr) {
    plot_row_cells(to_win, ScrollView::RED, row, 0, &row->char_cells);
  }
#endif
 
  prev_x = -INT16_MAX;
  bol = true;
  blanks = 0;
  if (rep_it.empty()) {
    rep_left = INT16_MAX;
  } else {
    rep_left = rep_it.data()->bounding_box().left();
  }
  if (box_it.empty()) {
    return nullptr; // empty row
  }
  xstarts[0] = box_it.data()->bounding_box().left();
  if (rep_left < xstarts[0]) {
    xstarts[0] = rep_left;
  }
  if (cell_it.empty() || row->char_cells.singleton()) {
    tprintf("Row without enough char cells!\n");
    tprintf("Leftmost blob is at (%d,%d)\n", box_it.data()->bounding_box().left(),
            box_it.data()->bounding_box().bottom());
    return nullptr;
  }
  ASSERT_HOST(!cell_it.empty() && !row->char_cells.singleton());
  prev_chop_coord = cell_it.data()->x();
  word = nullptr;
  while (rep_left < cell_it.data()->x()) {
    word =
        add_repeated_word(&rep_it, rep_left, prev_chop_coord, blanks, row->fixed_pitch, &word_it);
  }
  cell_it.mark_cycle_pt();
  if (prev_chop_coord >= cell_it.data()->x()) {
    cell_it.forward();
  }
  for (; !cell_it.cycled_list(); cell_it.forward()) {
    chop_coord = cell_it.data()->x();
    while (!box_it.empty() && box_it.data()->bounding_box().left() <= chop_coord) {
      if (box_it.data()->bounding_box().right() > prev_x) {
        prev_x = box_it.data()->bounding_box().right();
      }
      split_to_blob(box_it.extract(), chop_coord, textord_fp_chop_error + 0.5f, &left_coutlines,
                    &right_coutlines);
      box_it.forward();
      while (!box_it.empty() && box_it.data()->cblob() == nullptr) {
        delete box_it.extract();
        box_it.forward();
      }
    }
    if (!right_coutlines.empty() && left_coutlines.empty()) {
      split_to_blob(nullptr, chop_coord, textord_fp_chop_error + 0.5f, &left_coutlines,
                    &right_coutlines);
    }
    if (!left_coutlines.empty()) {
      cblob_it.add_after_then_move(new C_BLOB(&left_coutlines));
    } else {
      if (rep_left < chop_coord) {
        if (rep_left > prev_chop_coord) {
          new_blanks =
              static_cast<uint8_t>(floor((rep_left - prev_chop_coord) / row->fixed_pitch + 0.5));
        } else {
          new_blanks = 0;
        }
      } else {
        if (chop_coord > prev_chop_coord) {
          new_blanks =
              static_cast<uint8_t>(floor((chop_coord - prev_chop_coord) / row->fixed_pitch + 0.5));
        } else {
          new_blanks = 0;
        }
      }
      if (!cblob_it.empty()) {
        if (blanks < 1 && word != nullptr && !word->flag(W_REP_CHAR)) {
          blanks = 1;
        }
        word = new WERD(&cblobs, blanks, nullptr);
        cblob_it.set_to_list(&cblobs);
        word->set_flag(W_DONT_CHOP, true);
        word_it.add_after_then_move(word);
        if (bol) {
          word->set_flag(W_BOL, true);
          bol = false;
        }
        blanks = new_blanks;
      } else {
        blanks += new_blanks;
      }
      while (rep_left < chop_coord) {
        word = add_repeated_word(&rep_it, rep_left, prev_chop_coord, blanks, row->fixed_pitch,
                                 &word_it);
      }
    }
    if (prev_chop_coord < chop_coord) {
      prev_chop_coord = chop_coord;
    }
  }
  if (!cblob_it.empty()) {
    word = new WERD(&cblobs, blanks, nullptr);
    word->set_flag(W_DONT_CHOP, true);
    word_it.add_after_then_move(word);
    if (bol) {
      word->set_flag(W_BOL, true);
    }
  }
  ASSERT_HOST(word != nullptr);
  while (!rep_it.empty()) {
    add_repeated_word(&rep_it, rep_left, prev_chop_coord, blanks, row->fixed_pitch, &word_it);
  }
  // at end of line
  word_it.data()->set_flag(W_EOL, true);
  if (prev_chop_coord > prev_x) {
    prev_x = prev_chop_coord;
  }
  xstarts[1] = prev_x + 1;
  real_row =
      new ROW(row, static_cast<int16_t>(row->kern_size), static_cast<int16_t>(row->space_size));
  word_it.set_to_list(real_row->word_list());
  // put words in row
  word_it.add_list_after(&words);
  real_row->recalc_bounding_box();
  return real_row;
}
 
/**********************************************************************
 * add_repeated_word
 *
 * Add repeated word into the row at the given point.
 **********************************************************************/
 
static WERD *add_repeated_word( // move repeated word
    WERD_IT *rep_it,            // repeated words
    int16_t &rep_left,          // left edge of word
    int16_t &prev_chop_coord,   // previous word end
    uint8_t &blanks,            // no of blanks
    float pitch,                // char cell size
    WERD_IT *word_it            // list of words
) {
  WERD *word;         // word to move
  int16_t new_blanks; // extra blanks
 
  if (rep_left > prev_chop_coord) {
    new_blanks = static_cast<uint8_t>(floor((rep_left - prev_chop_coord) / pitch + 0.5));
    blanks += new_blanks;
  }
  word = rep_it->extract();
  prev_chop_coord = word->bounding_box().right();
  word_it->add_after_then_move(word);
  word->set_blanks(blanks);
  rep_it->forward();
  if (rep_it->empty()) {
    rep_left = INT16_MAX;
  } else {
    rep_left = rep_it->data()->bounding_box().left();
  }
  blanks = 0;
  return word;
}
 
/**********************************************************************
 * split_to_blob
 *
 * Split a BLOBNBOX across a vertical chop line and put the pieces
 * into a left outline list and a right outline list.
 **********************************************************************/
 
void split_to_blob(                 // split the blob
    BLOBNBOX *blob,                 // blob to split
    int16_t chop_coord,             // place to chop
    float pitch_error,              // allowed deviation
    C_OUTLINE_LIST *left_coutlines, // for cblobs
    C_OUTLINE_LIST *right_coutlines) {
  C_BLOB *real_cblob; // cblob to chop
 
  if (blob != nullptr) {
    real_cblob = blob->remove_cblob();
  } else {
    real_cblob = nullptr;
  }
  if (!right_coutlines->empty() || real_cblob != nullptr) {
    fixed_chop_cblob(real_cblob, chop_coord, pitch_error, left_coutlines, right_coutlines);
  }
 
  delete blob;
}
 
/**********************************************************************
 * fixed_chop_cblob
 *
 * Chop the given cblob (if any) and the existing right outlines to
 * produce a list of outlines left of the chop point and more to the right.
 **********************************************************************/
 
static void fixed_chop_cblob(      // split the blob
    C_BLOB *blob,                  // blob to split
    int16_t chop_coord,            // place to chop
    float pitch_error,             // allowed deviation
    C_OUTLINE_LIST *left_outlines, // left half of chop
    C_OUTLINE_LIST *right_outlines // right half of chop
) {
  C_OUTLINE *old_right;        // already there
  C_OUTLINE_LIST new_outlines; // new right ones
                               // output iterator
  C_OUTLINE_IT left_it = left_outlines;
  // in/out iterator
  C_OUTLINE_IT right_it = right_outlines;
  C_OUTLINE_IT new_it = &new_outlines;
  C_OUTLINE_IT blob_it; // outlines in blob
 
  if (!right_it.empty()) {
    while (!right_it.empty()) {
      old_right = right_it.extract();
      right_it.forward();
      fixed_split_coutline(old_right, chop_coord, pitch_error, &left_it, &new_it);
    }
    right_it.add_list_before(&new_outlines);
  }
  if (blob != nullptr) {
    blob_it.set_to_list(blob->out_list());
    for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
      fixed_split_coutline(blob_it.extract(), chop_coord, pitch_error, &left_it, &right_it);
    }
    delete blob;
  }
}
 
/**********************************************************************
 * fixed_split_outline
 *
 * Chop the given outline (if necessary) placing the fragments which
 * fall either side of the chop line into the appropriate list.
 **********************************************************************/
 
static void fixed_split_coutline( // chop the outline
    C_OUTLINE *srcline,           // source outline
    int16_t chop_coord,           // place to chop
    float pitch_error,            // allowed deviation
    C_OUTLINE_IT *left_it,        // left half of chop
    C_OUTLINE_IT *right_it        // right half of chop
) {
  C_OUTLINE *child;               // child outline
  TBOX srcbox;                    // box of outline
  C_OUTLINE_LIST left_ch;         // left children
  C_OUTLINE_LIST right_ch;        // right children
  C_OUTLINE_FRAG_LIST left_frags; // chopped fragments
  C_OUTLINE_FRAG_LIST right_frags;
  ;
  C_OUTLINE_IT left_ch_it = &left_ch;
  // for whole children
  C_OUTLINE_IT right_ch_it = &right_ch;
  // for holes
  C_OUTLINE_IT child_it = srcline->child();
 
  srcbox = srcline->bounding_box();
  if (srcbox.left() + srcbox.right() <= chop_coord * 2 &&
      srcbox.right() < chop_coord + pitch_error) {
    // Whole outline is in the left side or not far over the chop_coord,
    // so put the whole thing on the left.
    left_it->add_after_then_move(srcline);
  } else if (srcbox.left() + srcbox.right() > chop_coord * 2 &&
             srcbox.left() > chop_coord - pitch_error) {
    // Whole outline is in the right side or not far over the chop_coord,
    // so put the whole thing on the right.
    right_it->add_before_stay_put(srcline);
  } else {
    // Needs real chopping.
    if (fixed_chop_coutline(srcline, chop_coord, pitch_error, &left_frags, &right_frags)) {
      for (child_it.mark_cycle_pt(); !child_it.cycled_list(); child_it.forward()) {
        child = child_it.extract();
        srcbox = child->bounding_box();
        if (srcbox.right() < chop_coord) {
          // Whole child is on the left.
          left_ch_it.add_after_then_move(child);
        } else if (srcbox.left() > chop_coord) {
          // Whole child is on the right.
          right_ch_it.add_after_then_move(child);
        } else {
          // No pitch_error is allowed when chopping children to prevent
          // impossible outlines from being created.
          if (fixed_chop_coutline(child, chop_coord, 0.0f, &left_frags, &right_frags)) {
            delete child;
          } else {
            if (srcbox.left() + srcbox.right() <= chop_coord * 2) {
              left_ch_it.add_after_then_move(child);
            } else {
              right_ch_it.add_after_then_move(child);
            }
          }
        }
      }
      close_chopped_cfragments(&left_frags, &left_ch, pitch_error, left_it);
      close_chopped_cfragments(&right_frags, &right_ch, pitch_error, right_it);
      ASSERT_HOST(left_ch.empty() && right_ch.empty());
      // No children left.
      delete srcline; // Smashed up.
    } else {
      // Chop failed. Just use middle coord.
      if (srcbox.left() + srcbox.right() <= chop_coord * 2) {
        left_it->add_after_then_move(srcline); // Stick whole in left.
      } else {
        right_it->add_before_stay_put(srcline);
      }
    }
  }
}
 
/**********************************************************************
 * fixed_chop_coutline
 *
 * Chop the given coutline (if necessary) placing the fragments which
 * fall either side of the chop line into the appropriate list.
 * If the coutline lies too heavily to one side to chop, false is returned.
 **********************************************************************/
 
static bool fixed_chop_coutline(     // chop the outline
    C_OUTLINE *srcline,              // source outline
    int16_t chop_coord,              // place to chop
    float pitch_error,               // allowed deviation
    C_OUTLINE_FRAG_LIST *left_frags, // left half of chop
    C_OUTLINE_FRAG_LIST *right_frags // right half of chop
) {
  bool first_frag;         // fragment
  int16_t left_edge;       // of outline
  int16_t startindex;      // in first fragment
  int32_t length;          // of outline
  int16_t stepindex;       // into outline
  int16_t head_index;      // start of fragment
  ICOORD head_pos;         // start of fragment
  int16_t tail_index;      // end of fragment
  ICOORD tail_pos;         // end of fragment
  ICOORD pos;              // current point
  int16_t first_index = 0; // first tail
  ICOORD first_pos;        // first tail
 
  length = srcline->pathlength();
  pos = srcline->start_pos();
  left_edge = pos.x();
  tail_index = 0;
  tail_pos = pos;
  for (stepindex = 0; stepindex < length; stepindex++) {
    if (pos.x() < left_edge) {
      left_edge = pos.x();
      tail_index = stepindex;
      tail_pos = pos;
    }
    pos += srcline->step(stepindex);
  }
  if (left_edge >= chop_coord - pitch_error) {
    return false; // not worth it
  }
 
  startindex = tail_index;
  first_frag = true;
  head_index = tail_index;
  head_pos = tail_pos;
  do {
    do {
      tail_pos += srcline->step(tail_index);
      tail_index++;
      if (tail_index == length) {
        tail_index = 0;
      }
    } while (tail_pos.x() != chop_coord && tail_index != startindex);
    if (tail_index == startindex) {
      if (first_frag) {
        return false; // doesn't cross line
      } else {
        break;
      }
    }
    ASSERT_HOST(head_index != tail_index);
    if (!first_frag) {
      save_chop_cfragment(head_index, head_pos, tail_index, tail_pos, srcline, left_frags);
    } else {
      first_index = tail_index;
      first_pos = tail_pos;
      first_frag = false;
    }
    while (srcline->step(tail_index).x() == 0) {
      tail_pos += srcline->step(tail_index);
      tail_index++;
      if (tail_index == length) {
        tail_index = 0;
      }
    }
    head_index = tail_index;
    head_pos = tail_pos;
    while (srcline->step(tail_index).x() > 0) {
      do {
        tail_pos += srcline->step(tail_index);
        tail_index++;
        if (tail_index == length) {
          tail_index = 0;
        }
      } while (tail_pos.x() != chop_coord);
      ASSERT_HOST(head_index != tail_index);
      save_chop_cfragment(head_index, head_pos, tail_index, tail_pos, srcline, right_frags);
      while (srcline->step(tail_index).x() == 0) {
        tail_pos += srcline->step(tail_index);
        tail_index++;
        if (tail_index == length) {
          tail_index = 0;
        }
      }
      head_index = tail_index;
      head_pos = tail_pos;
    }
  } while (tail_index != startindex);
  save_chop_cfragment(head_index, head_pos, first_index, first_pos, srcline, left_frags);
  return true; // did some chopping
}
 
/**********************************************************************
 * save_chop_cfragment
 *
 * Store the given fragment in the given fragment list.
 **********************************************************************/
 
static void save_chop_cfragment( // chop the outline
    int16_t head_index,          // head of fragment
    ICOORD head_pos,             // head of fragment
    int16_t tail_index,          // tail of fragment
    ICOORD tail_pos,             // tail of fragment
    C_OUTLINE *srcline,          // source of edgesteps
    C_OUTLINE_FRAG_LIST *frags   // fragment list
) {
  int16_t jump;         // gap across end
  int16_t stepcount;    // total steps
  C_OUTLINE_FRAG *head; // head of fragment
  C_OUTLINE_FRAG *tail; // tail of fragment
  int16_t tail_y;       // ycoord of tail
 
  ASSERT_HOST(tail_pos.x() == head_pos.x());
  ASSERT_HOST(tail_index != head_index);
  stepcount = tail_index - head_index;
  if (stepcount < 0) {
    stepcount += srcline->pathlength();
  }
  jump = tail_pos.y() - head_pos.y();
  if (jump < 0) {
    jump = -jump;
  }
  if (jump == stepcount) {
    return; // its a nop
  }
  tail_y = tail_pos.y();
  head = new C_OUTLINE_FRAG(head_pos, tail_pos, srcline, head_index, tail_index);
  tail = new C_OUTLINE_FRAG(head, tail_y);
  head->other_end = tail;
  add_frag_to_list(head, frags);
  add_frag_to_list(tail, frags);
}
 
/**********************************************************************
 * C_OUTLINE_FRAG::C_OUTLINE_FRAG
 *
 * Constructors for C_OUTLINE_FRAG.
 **********************************************************************/
 
C_OUTLINE_FRAG::C_OUTLINE_FRAG( // record fragment
    ICOORD start_pt,            // start coord
    ICOORD end_pt,              // end coord
    C_OUTLINE *outline,         // source of steps
    int16_t start_index, int16_t end_index) {
  start = start_pt;
  end = end_pt;
  ycoord = start_pt.y();
  stepcount = end_index - start_index;
  if (stepcount < 0) {
    stepcount += outline->pathlength();
  }
  ASSERT_HOST(stepcount > 0);
  steps = new DIR128[stepcount];
  if (end_index > start_index) {
    for (int i = start_index; i < end_index; ++i) {
      steps[i - start_index] = outline->step_dir(i);
    }
  } else {
    int len = outline->pathlength();
    int i = start_index;
    for (; i < len; ++i) {
      steps[i - start_index] = outline->step_dir(i);
    }
    if (end_index > 0) {
      for (; i < end_index + len; ++i) {
        steps[i - start_index] = outline->step_dir(i - len);
      }
    }
  }
  other_end = nullptr;
  delete close();
}
 
C_OUTLINE_FRAG::C_OUTLINE_FRAG( // record fragment
    C_OUTLINE_FRAG *head,       // other end
    int16_t tail_y) {
  ycoord = tail_y;
  other_end = head;
  start = head->start;
  end = head->end;
  steps = nullptr;
  stepcount = 0;
}
 
/**********************************************************************
 * add_frag_to_list
 *
 * Insert the fragment in the list at the appropriate place to keep
 * them in ascending ycoord order.
 **********************************************************************/
 
static void add_frag_to_list(  // ordered add
    C_OUTLINE_FRAG *frag,      // fragment to add
    C_OUTLINE_FRAG_LIST *frags // fragment list
) {
  // output list
  C_OUTLINE_FRAG_IT frag_it = frags;
 
  if (!frags->empty()) {
    for (frag_it.mark_cycle_pt(); !frag_it.cycled_list(); frag_it.forward()) {
      if (frag_it.data()->ycoord > frag->ycoord ||
          (frag_it.data()->ycoord == frag->ycoord && frag->other_end->ycoord < frag->ycoord)) {
        frag_it.add_before_then_move(frag);
        return;
      }
    }
  }
  frag_it.add_to_end(frag);
}
 
/**********************************************************************
 * close_chopped_cfragments
 *
 * Clear the given list of fragments joining them up into outlines.
 * Each outline made soaks up any of the child outlines which it encloses.
 **********************************************************************/
 
static void close_chopped_cfragments( // chop the outline
    C_OUTLINE_FRAG_LIST *frags,       // list to clear
    C_OUTLINE_LIST *children,         // potential children
    float pitch_error,                // allowed shrinkage
    C_OUTLINE_IT *dest_it             // output list
) {
  // iterator
  C_OUTLINE_FRAG_IT frag_it = frags;
  C_OUTLINE_FRAG *bottom_frag; // bottom of cut
  C_OUTLINE_FRAG *top_frag;    // top of cut
  C_OUTLINE *outline;          // new outline
  C_OUTLINE *child;            // current child
  C_OUTLINE_IT child_it = children;
  C_OUTLINE_IT olchild_it; // children of outline
 
  while (!frag_it.empty()) {
    frag_it.move_to_first();
    // get bottom one
    bottom_frag = frag_it.extract();
    frag_it.forward();
    top_frag = frag_it.data(); // look at next
    if ((bottom_frag->steps == nullptr && top_frag->steps == nullptr) ||
        (bottom_frag->steps != nullptr && top_frag->steps != nullptr)) {
      if (frag_it.data_relative(1)->ycoord == top_frag->ycoord) {
        frag_it.forward();
      }
    }
    top_frag = frag_it.extract();
    if (top_frag->other_end != bottom_frag) {
      outline = join_chopped_fragments(bottom_frag, top_frag);
      ASSERT_HOST(outline == nullptr);
    } else {
      outline = join_chopped_fragments(bottom_frag, top_frag);
      if (outline != nullptr) {
        olchild_it.set_to_list(outline->child());
        for (child_it.mark_cycle_pt(); !child_it.cycled_list(); child_it.forward()) {
          child = child_it.data();
          if (*child < *outline) {
            olchild_it.add_to_end(child_it.extract());
          }
        }
        if (outline->bounding_box().width() > pitch_error) {
          dest_it->add_after_then_move(outline);
        } else {
          delete outline; // Make it disappear.
        }
      }
    }
  }
  while (!child_it.empty()) {
    dest_it->add_after_then_move(child_it.extract());
    child_it.forward();
  }
}
 
/**********************************************************************
 * join_chopped_fragments
 *
 * Join the two lists of POLYPTs such that neither OUTLINE_FRAG
 * operand keeps responsibility for the fragment.
 **********************************************************************/
 
static C_OUTLINE *join_chopped_fragments( // join pieces
    C_OUTLINE_FRAG *bottom,               // bottom of cut
    C_OUTLINE_FRAG *top                   // top of cut
) {
  C_OUTLINE *outline; // closed loop
 
  if (bottom->other_end == top) {
    if (bottom->steps == nullptr) {
      outline = top->close(); // turn to outline
    } else {
      outline = bottom->close();
    }
    delete top;
    delete bottom;
    return outline;
  }
  if (bottom->steps == nullptr) {
    ASSERT_HOST(top->steps != nullptr);
    join_segments(bottom->other_end, top);
  } else {
    ASSERT_HOST(top->steps == nullptr);
    join_segments(top->other_end, bottom);
  }
  top->other_end->other_end = bottom->other_end;
  bottom->other_end->other_end = top->other_end;
  delete bottom;
  delete top;
  return nullptr;
}
 
/**********************************************************************
 * join_segments
 *
 * Join the two edgestep fragments such that the second comes after
 * the first and the gap between them is closed.
 **********************************************************************/
 
static void join_segments(  // join pieces
    C_OUTLINE_FRAG *bottom, // bottom of cut
    C_OUTLINE_FRAG *top     // top of cut
) {
  DIR128 *steps;      // new steps
  int32_t stepcount;  // no of steps
  int16_t fake_count; // fake steps
  DIR128 fake_step;   // step entry
 
  ASSERT_HOST(bottom->end.x() == top->start.x());
  fake_count = top->start.y() - bottom->end.y();
  if (fake_count < 0) {
    fake_count = -fake_count;
    fake_step = 32;
  } else {
    fake_step = 96;
  }
 
  stepcount = bottom->stepcount + fake_count + top->stepcount;
  steps = new DIR128[stepcount];
  memmove(steps, bottom->steps, bottom->stepcount);
  memset(steps + bottom->stepcount, fake_step.get_dir(), fake_count);
  memmove(steps + bottom->stepcount + fake_count, top->steps, top->stepcount);
  delete[] bottom->steps;
  bottom->steps = steps;
  bottom->stepcount = stepcount;
  bottom->end = top->end;
  bottom->other_end->end = top->end;
}
 
/**********************************************************************
 * C_OUTLINE_FRAG::close
 *
 * Join the ends of this fragment and turn it into an outline.
 **********************************************************************/
 
C_OUTLINE *C_OUTLINE_FRAG::close() { // join pieces
  DIR128 *new_steps;                 // new steps
  int32_t new_stepcount;             // no of steps
  int16_t fake_count;                // fake steps
  DIR128 fake_step;                  // step entry
 
  ASSERT_HOST(start.x() == end.x());
  fake_count = start.y() - end.y();
  if (fake_count < 0) {
    fake_count = -fake_count;
    fake_step = 32;
  } else {
    fake_step = 96;
  }
 
  new_stepcount = stepcount + fake_count;
  if (new_stepcount > C_OUTLINE::kMaxOutlineLength) {
    return nullptr; // Can't join them
  }
  new_steps = new DIR128[new_stepcount];
  memmove(new_steps, steps, stepcount);
  memset(new_steps + stepcount, fake_step.get_dir(), fake_count);
  auto *result = new C_OUTLINE(start, new_steps, new_stepcount);
  delete[] new_steps;
  return result;
}
 
/**********************************************************************
 * C_OUTLINE_FRAG::operator=
 *
 * Copy this fragment.
 **********************************************************************/
 
// join pieces
C_OUTLINE_FRAG &C_OUTLINE_FRAG::operator=(const C_OUTLINE_FRAG &src // fragment to copy
) {
  delete[] steps;
 
  stepcount = src.stepcount;
  steps = new DIR128[stepcount];
  memmove(steps, src.steps, stepcount);
  start = src.start;
  end = src.end;
  ycoord = src.ycoord;
  return *this;
}
 
} // namespace tesseract