/**********************************************************************

 * File:        wordseg.cpp  (Formerly wspace.c)

 * Description: Code to segment the blobs into words.

 * Author:      Ray Smith

 *

 * (C) Copyright 1992, 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 "wordseg.h"

#include <cmath>

#include "blobbox.h"

#include "cjkpitch.h"

#include "drawtord.h"

#include "fpchop.h"

#include "makerow.h"

#include "pitsync1.h"

#include "statistc.h"

#include "textord.h"

#include "topitch.h"

#include "tovars.h"

namespace tesseract {

BOOL_VAR(textord_force_make_prop_words, false, "Force proportional word segmentation on all rows");

BOOL_VAR(textord_chopper_test, false, "Chopper is being tested.");

#define BLOCK_STATS_CLUSTERS 10

/**

 * @name make_single_word

 *

 * For each row, arrange the blobs into one word. There is no fixed

 * pitch detection.

 */

void make_single_word(bool one_blob, TO_ROW_LIST *rows, ROW_LIST *real_rows) {

  TO_ROW_IT to_row_it(rows);

  ROW_IT row_it(real_rows);

  for (to_row_it.mark_cycle_pt(); !to_row_it.cycled_list(); to_row_it.forward()) {

    TO_ROW *row = to_row_it.data();

    // The blobs have to come out of the BLOBNBOX into the C_BLOB_LIST ready

    // to create the word.

    C_BLOB_LIST cblobs;

    C_BLOB_IT cblob_it(&cblobs);

    BLOBNBOX_IT box_it(row->blob_list());

    for (; !box_it.empty(); box_it.forward()) {

      BLOBNBOX *bblob = box_it.extract();

      if (bblob->joined_to_prev() || (one_blob && !cblob_it.empty())) {

        auto cblob = bblob->remove_cblob();

        if (cblob != nullptr) {

          C_OUTLINE_IT cout_it(cblob_it.data()->out_list());

          cout_it.move_to_last();

          cout_it.add_list_after(cblob->out_list());

          delete cblob;

        }

      } else {

        auto cblob = bblob->remove_cblob();

        if (cblob != nullptr) {

          cblob_it.add_after_then_move(cblob);

        }

      }

      delete bblob;

    }

    // Convert the TO_ROW to a ROW.

    ROW *real_row =

        new ROW(row, static_cast<int16_t>(row->kern_size), static_cast<int16_t>(row->space_size));

    WERD_IT word_it(real_row->word_list());

    WERD *word = new WERD(&cblobs, 0, nullptr);

    word->set_flag(W_BOL, true);

    word->set_flag(W_EOL, true);

    word->set_flag(W_DONT_CHOP, one_blob);

    word_it.add_after_then_move(word);

    real_row->recalc_bounding_box();

    row_it.add_after_then_move(real_row);

  }

}

/**

 * make_words

 *

 * Arrange the blobs into words.

 */

void make_words(tesseract::Textord *textord,

                ICOORD page_tr,               // top right

                float gradient,               // page skew

                BLOCK_LIST *blocks,           // block list

                TO_BLOCK_LIST *port_blocks) { // output list

  TO_BLOCK_IT block_it;                       // iterator

  TO_BLOCK *block;                            // current block

  if (textord->use_cjk_fp_model()) {

    compute_fixed_pitch_cjk(page_tr, port_blocks);

  } else {

    compute_fixed_pitch(page_tr, port_blocks, gradient, FCOORD(0.0f, -1.0f),

                        !bool(textord_test_landscape));

  }

  textord->to_spacing(page_tr, port_blocks);

  block_it.set_to_list(port_blocks);

  for (block_it.mark_cycle_pt(); !block_it.cycled_list(); block_it.forward()) {

    block = block_it.data();

    make_real_words(textord, block, FCOORD(1.0f, 0.0f));

  }

}

/**

 * @name set_row_spaces

 *

 * Set the min_space and max_nonspace members of the row so that

 * the blobs can be arranged into words.

 */

void set_row_spaces( // find space sizes

    TO_BLOCK *block, // block to do

    FCOORD rotation, // for drawing

    bool testing_on  // correct orientation

) {

  TO_ROW *row; // current row

  TO_ROW_IT row_it = block->get_rows();

  if (row_it.empty()) {

    return; // empty block

  }

  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {

    row = row_it.data();

    if (row->fixed_pitch == 0) {

      row->min_space = static_cast<int32_t>(

          ceil(row->pr_space - (row->pr_space - row->pr_nonsp) * textord_words_definite_spread));

      row->max_nonspace = static_cast<int32_t>(

          floor(row->pr_nonsp + (row->pr_space - row->pr_nonsp) * textord_words_definite_spread));

      if (testing_on && textord_show_initial_words) {

        tprintf("Assigning defaults %d non, %d space to row at %g\n", row->max_nonspace,

                row->min_space, row->intercept());

      }

      row->space_threshold = (row->max_nonspace + row->min_space) / 2;

      row->space_size = row->pr_space;

      row->kern_size = row->pr_nonsp;

    }

#ifndef GRAPHICS_DISABLED

    if (textord_show_initial_words && testing_on) {

      plot_word_decisions(to_win, static_cast<int16_t>(row->fixed_pitch), row);

    }

#endif

  }

}

/**

 * @name row_words

 *

 * Compute the max nonspace and min space for the row.

 */

int32_t row_words(    // compute space size

    TO_BLOCK *block,  // block it came from

    TO_ROW *row,      // row to operate on

    int32_t maxwidth, // max expected space size

    FCOORD rotation,  // for drawing

    bool testing_on   // for debug

) {

  bool testing_row;      // contains testpt

  bool prev_valid;       // if decent size

  int32_t prev_x;        // end of prev blob

  int32_t cluster_count; // no of clusters

  int32_t gap_index;     // which cluster

  int32_t smooth_factor; // for smoothing stats

  BLOBNBOX *blob;        // current blob

  float lower, upper;    // clustering parameters

  float gaps[3];         // gap clusers

  ICOORD testpt;

  TBOX blob_box; // bounding box

                 // iterator

  BLOBNBOX_IT blob_it = row->blob_list();

  STATS gap_stats(0, maxwidth - 1);

  STATS cluster_stats[4]; // clusters

  testpt = ICOORD(textord_test_x, textord_test_y);

  smooth_factor = static_cast<int32_t>(block->xheight * textord_wordstats_smooth_factor + 1.5);

  //      if (testing_on)

  //              tprintf("Row smooth factor=%d\n",smooth_factor);

  prev_valid = false;

  prev_x = -INT32_MAX;

  testing_row = false;

  for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {

    blob = blob_it.data();

    blob_box = blob->bounding_box();

    if (blob_box.contains(testpt)) {

      testing_row = true;

    }

    gap_stats.add(blob_box.width(), 1);

  }

  gap_stats.clear();

  for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {

    blob = blob_it.data();

    if (!blob->joined_to_prev()) {

      blob_box = blob->bounding_box();

      if (prev_valid && blob_box.left() - prev_x < maxwidth) {

        gap_stats.add(blob_box.left() - prev_x, 1);

      }

      prev_valid = true;

      prev_x = blob_box.right();

    }

  }

  if (gap_stats.get_total() == 0) {

    row->min_space = 0; // no evidence

    row->max_nonspace = 0;

    return 0;

  }

  gap_stats.smooth(smooth_factor);

  lower = row->xheight * textord_words_initial_lower;

  upper = row->xheight * textord_words_initial_upper;

  cluster_count = gap_stats.cluster(lower, upper, textord_spacesize_ratioprop, 3, cluster_stats);

  while (cluster_count < 2 && std::ceil(lower) < std::floor(upper)) {

    // shrink gap

    upper = (upper * 3 + lower) / 4;

    lower = (lower * 3 + upper) / 4;

    cluster_count = gap_stats.cluster(lower, upper, textord_spacesize_ratioprop, 3, cluster_stats);

  }

  if (cluster_count < 2) {

    row->min_space = 0; // no evidence

    row->max_nonspace = 0;

    return 0;

  }

  for (gap_index = 0; gap_index < cluster_count; gap_index++) {

    gaps[gap_index] = cluster_stats[gap_index + 1].ile(0.5);

  }

  // get medians

  if (cluster_count > 2) {

    if (testing_on && textord_show_initial_words) {

      tprintf("Row at %g has 3 sizes of gap:%g,%g,%g\n", row->intercept(),

              cluster_stats[1].ile(0.5), cluster_stats[2].ile(0.5), cluster_stats[3].ile(0.5));

    }

    lower = gaps[0];

    if (gaps[1] > lower) {

      upper = gaps[1]; // prefer most frequent

      if (upper < block->xheight * textord_words_min_minspace && gaps[2] > gaps[1]) {

        upper = gaps[2];

      }

    } else if (gaps[2] > lower && gaps[2] >= block->xheight * textord_words_min_minspace) {

      upper = gaps[2];

    } else if (lower >= block->xheight * textord_words_min_minspace) {

      upper = lower; // not nice

      lower = gaps[1];

      if (testing_on && textord_show_initial_words) {

        tprintf("Had to switch most common from lower to upper!!\n");

        gap_stats.print();

      }

    } else {

      row->min_space = 0; // no evidence

      row->max_nonspace = 0;

      return 0;

    }

  } else {

    if (gaps[1] < gaps[0]) {

      if (testing_on && textord_show_initial_words) {

        tprintf("Had to switch most common from lower to upper!!\n");

        gap_stats.print();

      }

      lower = gaps[1];

      upper = gaps[0];

    } else {

      upper = gaps[1];

      lower = gaps[0];

    }

  }

  if (upper < block->xheight * textord_words_min_minspace) {

    row->min_space = 0; // no evidence

    row->max_nonspace = 0;

    return 0;

  }

  if (upper * 3 < block->min_space * 2 + block->max_nonspace ||

      lower * 3 > block->min_space * 2 + block->max_nonspace) {

    if (testing_on && textord_show_initial_words) {

      tprintf("Disagreement between block and row at %g!!\n", row->intercept());

      tprintf("Lower=%g, upper=%g, Stats:\n", lower, upper);

      gap_stats.print();

    }

  }

  row->min_space =

      static_cast<int32_t>(ceil(upper - (upper - lower) * textord_words_definite_spread));

  row->max_nonspace =

      static_cast<int32_t>(floor(lower + (upper - lower) * textord_words_definite_spread));

  row->space_threshold = (row->max_nonspace + row->min_space) / 2;

  row->space_size = upper;

  row->kern_size = lower;

  if (testing_on && textord_show_initial_words) {

    if (testing_row) {

      tprintf("GAP STATS\n");

      gap_stats.print();

      tprintf("SPACE stats\n");

      cluster_stats[2].print_summary();

      tprintf("NONSPACE stats\n");

      cluster_stats[1].print_summary();

    }

    tprintf("Row at %g has minspace=%d(%g), max_non=%d(%g)\n", row->intercept(), row->min_space,

            upper, row->max_nonspace, lower);

  }

  return cluster_stats[2].get_total();

}

/**

 * @name row_words2

 *

 * Compute the max nonspace and min space for the row.

 */

int32_t row_words2(   // compute space size

    TO_BLOCK *block,  // block it came from

    TO_ROW *row,      // row to operate on

    int32_t maxwidth, // max expected space size

    FCOORD rotation,  // for drawing

    bool testing_on   // for debug

) {

  bool prev_valid;       // if decent size

  bool this_valid;       // current blob big enough

  int32_t prev_x;        // end of prev blob

  int32_t min_width;     // min interesting width

  int32_t valid_count;   // good gaps

  int32_t total_count;   // total gaps

  int32_t cluster_count; // no of clusters

  int32_t prev_count;    // previous cluster_count

  int32_t gap_index;     // which cluster

  int32_t smooth_factor; // for smoothing stats

  BLOBNBOX *blob;        // current blob

  float lower, upper;    // clustering parameters

  ICOORD testpt;

  TBOX blob_box; // bounding box

                 // iterator

  BLOBNBOX_IT blob_it = row->blob_list();

  STATS gap_stats(0, maxwidth - 1);

  // gap sizes

  float gaps[BLOCK_STATS_CLUSTERS];

  STATS cluster_stats[BLOCK_STATS_CLUSTERS + 1];

  // clusters

  testpt = ICOORD(textord_test_x, textord_test_y);

  smooth_factor = static_cast<int32_t>(block->xheight * textord_wordstats_smooth_factor + 1.5);

  //      if (testing_on)

  //              tprintf("Row smooth factor=%d\n",smooth_factor);

  prev_valid = false;

  prev_x = -INT16_MAX;

  const bool testing_row = false;

  // min blob size

  min_width = static_cast<int32_t>(block->pr_space);

  total_count = 0;

  for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {

    blob = blob_it.data();

    if (!blob->joined_to_prev()) {

      blob_box = blob->bounding_box();

      this_valid = blob_box.width() >= min_width;

      if (this_valid && prev_valid && blob_box.left() - prev_x < maxwidth) {

        gap_stats.add(blob_box.left() - prev_x, 1);

      }

      total_count++; // count possibles

      prev_x = blob_box.right();

      prev_valid = this_valid;

    }

  }

  valid_count = gap_stats.get_total();

  if (valid_count < total_count * textord_words_minlarge) {

    gap_stats.clear();

    prev_x = -INT16_MAX;

    for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {

      blob = blob_it.data();

      if (!blob->joined_to_prev()) {

        blob_box = blob->bounding_box();

        if (blob_box.left() - prev_x < maxwidth) {

          gap_stats.add(blob_box.left() - prev_x, 1);

        }

        prev_x = blob_box.right();

      }

    }

  }

  if (gap_stats.get_total() == 0) {

    row->min_space = 0; // no evidence

    row->max_nonspace = 0;

    return 0;

  }

  cluster_count = 0;

  lower = block->xheight * words_initial_lower;

  upper = block->xheight * words_initial_upper;

  gap_stats.smooth(smooth_factor);

  do {

    prev_count = cluster_count;

    cluster_count = gap_stats.cluster(lower, upper, textord_spacesize_ratioprop,

                                      BLOCK_STATS_CLUSTERS, cluster_stats);

  } while (cluster_count > prev_count && cluster_count < BLOCK_STATS_CLUSTERS);

  if (cluster_count < 1) {

    row->min_space = 0;

    row->max_nonspace = 0;

    return 0;

  }

  for (gap_index = 0; gap_index < cluster_count; gap_index++) {

    gaps[gap_index] = cluster_stats[gap_index + 1].ile(0.5);

  }

  // get medians

  if (testing_on) {

    tprintf("cluster_count=%d:", cluster_count);

    for (gap_index = 0; gap_index < cluster_count; gap_index++) {

      tprintf(" %g(%d)", gaps[gap_index], cluster_stats[gap_index + 1].get_total());

    }

    tprintf("\n");

  }

  // Try to find proportional non-space and space for row.

  for (gap_index = 0; gap_index < cluster_count && gaps[gap_index] > block->max_nonspace;

       gap_index++) {

    ;

  }

  if (gap_index < cluster_count) {

    lower = gaps[gap_index]; // most frequent below

  } else {

    if (testing_on) {

      tprintf("No cluster below block threshold!, using default=%g\n", block->pr_nonsp);

    }

    lower = block->pr_nonsp;

  }

  for (gap_index = 0; gap_index < cluster_count && gaps[gap_index] <= block->max_nonspace;

       gap_index++) {

    ;

  }

  if (gap_index < cluster_count) {

    upper = gaps[gap_index]; // most frequent above

  } else {

    if (testing_on) {

      tprintf("No cluster above block threshold!, using default=%g\n", block->pr_space);

    }

    upper = block->pr_space;

  }

  row->min_space =

      static_cast<int32_t>(ceil(upper - (upper - lower) * textord_words_definite_spread));

  row->max_nonspace =

      static_cast<int32_t>(floor(lower + (upper - lower) * textord_words_definite_spread));

  row->space_threshold = (row->max_nonspace + row->min_space) / 2;

  row->space_size = upper;

  row->kern_size = lower;

  if (testing_on) {

    if (testing_row) {

      tprintf("GAP STATS\n");

      gap_stats.print();

      tprintf("SPACE stats\n");

      cluster_stats[2].print_summary();

      tprintf("NONSPACE stats\n");

      cluster_stats[1].print_summary();

    }

    tprintf("Row at %g has minspace=%d(%g), max_non=%d(%g)\n", row->intercept(), row->min_space,

            upper, row->max_nonspace, lower);

  }

  return 1;

}

/**

 * @name make_real_words

 *

 * Convert a TO_BLOCK to a BLOCK.

 */

void make_real_words(tesseract::Textord *textord,

                     TO_BLOCK *block, // block to do

                     FCOORD rotation  // for drawing

) {

  TO_ROW *row; // current row

  TO_ROW_IT row_it = block->get_rows();

  ROW *real_row = nullptr; // output row

  ROW_IT real_row_it = block->block->row_list();

  if (row_it.empty()) {

    return; // empty block

  }

  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {

    row = row_it.data();

    if (row->blob_list()->empty() && !row->rep_words.empty()) {

      real_row = make_rep_words(row, block);

    } else if (!row->blob_list()->empty()) {

      // In a fixed pitch document, some lines may be detected as fixed pitch

      // while others don't, and will go through different path.

      // For non-space delimited language like CJK, fixed pitch chop always

      // leave the entire line as one word.  We can force consistent chopping

      // with force_make_prop_words flag.

      POLY_BLOCK *pb = block->block->pdblk.poly_block();

      if (textord_chopper_test) {

        real_row = textord->make_blob_words(row, rotation);

      } else if (textord_force_make_prop_words || (pb != nullptr && !pb->IsText()) ||

                 row->pitch_decision == PITCH_DEF_PROP || row->pitch_decision == PITCH_CORR_PROP) {

        real_row = textord->make_prop_words(row, rotation);

      } else if (row->pitch_decision == PITCH_DEF_FIXED ||

                 row->pitch_decision == PITCH_CORR_FIXED) {

        real_row = fixed_pitch_words(row, rotation);

      } else {

        ASSERT_HOST(false);

      }

    }

    if (real_row != nullptr) {

      // put row in block

      real_row_it.add_after_then_move(real_row);

    }

  }

  block->block->set_stats(block->fixed_pitch == 0, static_cast<int16_t>(block->kern_size),

                          static_cast<int16_t>(block->space_size),

                          static_cast<int16_t>(block->fixed_pitch));

  block->block->check_pitch();

}

/**

 * @name make_rep_words

 *

 * Fabricate a real row from only the repeated blob words.

 * Get the xheight from the block as it may be more meaningful.

 */

ROW *make_rep_words( // make a row

    TO_ROW *row,     // row to convert

    TO_BLOCK *block  // block it lives in

) {

  ROW *real_row; // output row

  TBOX word_box; // bounding box

                 // iterator

  WERD_IT word_it = &row->rep_words;

  if (word_it.empty()) {

    return nullptr;

  }

  word_box = word_it.data()->bounding_box();

  for (word_it.mark_cycle_pt(); !word_it.cycled_list(); word_it.forward()) {

    word_box += word_it.data()->bounding_box();

  }

  row->xheight = block->xheight;

  real_row =

      new ROW(row, static_cast<int16_t>(block->kern_size), static_cast<int16_t>(block->space_size));

  word_it.set_to_list(real_row->word_list());

  // put words in row

  word_it.add_list_after(&row->rep_words);

  real_row->recalc_bounding_box();

  return real_row;

}

/**

 * @name make_real_word

 *

 * Construct a WERD from a given number of adjacent entries in a

 * list of BLOBNBOXs.

 */

WERD *make_real_word(BLOBNBOX_IT *box_it, // iterator

                     int32_t blobcount,   // no of blobs to use

                     bool bol,            // start of line

                     uint8_t blanks       // no of blanks

) {

  C_OUTLINE_IT cout_it;

  C_BLOB_LIST cblobs;

  C_BLOB_IT cblob_it = &cblobs;

  for (int blobindex = 0; blobindex < blobcount; blobindex++) {

    auto bblob = box_it->extract();

    if (bblob->joined_to_prev()) {

      auto cblob = bblob->remove_cblob();

      if (cblob != nullptr) {

        cout_it.set_to_list(cblob_it.data()->out_list());

        cout_it.move_to_last();

        cout_it.add_list_after(cblob->out_list());

        delete cblob;

      }

    } else {

      auto cblob = bblob->remove_cblob();

      if (cblob != nullptr) {

        cblob_it.add_after_then_move(cblob);

      }

    }

    delete bblob;

    box_it->forward(); // next one

  }

  if (blanks < 1) {

    blanks = 1;

  }

  auto word = new WERD(&cblobs, blanks, nullptr);

  if (bol) {

    word->set_flag(W_BOL, true);

  }

  if (box_it->at_first()) {

    word->set_flag(W_EOL, true); // at end of line

  }

  return word;

}

} // namespace tesseract