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

 * File:        ocrblock.cpp  (Formerly block.c)

 * Description: BLOCK member functions and iterator functions.

 * Author:      Ray Smith

 *

 * (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.

 *

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

#include "ocrblock.h"

#include "stepblob.h"

#include "tprintf.h"

#include <cstdlib>

#include <memory> // std::unique_ptr

namespace tesseract {

/**

 * BLOCK::BLOCK

 *

 * Constructor for a simple rectangular block.

 */

BLOCK::BLOCK(const char *name, ///< filename

             bool prop,        ///< proportional

             int16_t kern,     ///< kerning

             int16_t space,    ///< spacing

             TDimension xmin,  ///< bottom left

             TDimension ymin,

             TDimension xmax,  ///< top right

             TDimension ymax)

    : pdblk(xmin, ymin, xmax, ymax)

    , filename(name)

    , re_rotation_(1.0f, 0.0f)

    , classify_rotation_(1.0f, 0.0f)

    , skew_(1.0f, 0.0f) {

  ICOORDELT_IT left_it = &pdblk.leftside;

  ICOORDELT_IT right_it = &pdblk.rightside;

  proportional = prop;

  kerning = kern;

  spacing = space;

  font_class = -1; // not assigned

  cell_over_xheight_ = 2.0f;

  pdblk.hand_poly = nullptr;

  left_it.set_to_list(&pdblk.leftside);

  right_it.set_to_list(&pdblk.rightside);

  // make default box

  left_it.add_to_end(new ICOORDELT(xmin, ymin));

  left_it.add_to_end(new ICOORDELT(xmin, ymax));

  right_it.add_to_end(new ICOORDELT(xmax, ymin));

  right_it.add_to_end(new ICOORDELT(xmax, ymax));

}

/**

 * decreasing_top_order

 *

 * Sort Comparator: Return <0 if row1 top < row2 top

 */

static int decreasing_top_order(const ROW *row1, const ROW *row2) {

  return row2->bounding_box().top() -

         row1->bounding_box().top();

}

/**

 * BLOCK::rotate

 *

 * Rotate the polygon by the given rotation and recompute the bounding_box.

 */

void BLOCK::rotate(const FCOORD &rotation) {

  pdblk.poly_block()->rotate(rotation);

  pdblk.box = *pdblk.poly_block()->bounding_box();

}

// Returns the bounding box including the desired combination of upper and

// lower noise/diacritic elements.

TBOX BLOCK::restricted_bounding_box(bool upper_dots, bool lower_dots) const {

  TBOX box;

  // This is a read-only iteration of the rows in the block.

  ROW_IT it(const_cast<ROW_LIST *>(&rows));

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

    box += it.data()->restricted_bounding_box(upper_dots, lower_dots);

  }

  return box;

}

/**

 * BLOCK::reflect_polygon_in_y_axis

 *

 * Reflects the polygon in the y-axis and recompute the bounding_box.

 * Does nothing to any contained rows/words/blobs etc.

 */

void BLOCK::reflect_polygon_in_y_axis() {

  pdblk.poly_block()->reflect_in_y_axis();

  pdblk.box = *pdblk.poly_block()->bounding_box();

}

/**

 * BLOCK::sort_rows

 *

 * Order rows so that they are in order of decreasing Y coordinate

 */

void BLOCK::sort_rows() { // order on "top"

  ROW_IT row_it(&rows);

  row_it.sort(decreasing_top_order);

}

/**

 * BLOCK::compress

 *

 * Delete space between the rows. (And maybe one day, compress the rows)

 * Fill space of block from top down, left aligning rows.

 */

void BLOCK::compress() { // squash it up

#define ROW_SPACING 5

  ROW_IT row_it(&rows);

  ROW *row;

  ICOORD row_spacing(0, ROW_SPACING);

  ICOORDELT_IT icoordelt_it;

  sort_rows();

  pdblk.box = TBOX(pdblk.box.topleft(), pdblk.box.topleft());

  pdblk.box.move_bottom_edge(ROW_SPACING);

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

    row = row_it.data();

    row->move(pdblk.box.botleft() - row_spacing - row->bounding_box().topleft());

    pdblk.box += row->bounding_box();

  }

  pdblk.leftside.clear();

  icoordelt_it.set_to_list(&pdblk.leftside);

  icoordelt_it.add_to_end(new ICOORDELT(pdblk.box.left(), pdblk.box.bottom()));

  icoordelt_it.add_to_end(new ICOORDELT(pdblk.box.left(), pdblk.box.top()));

  pdblk.rightside.clear();

  icoordelt_it.set_to_list(&pdblk.rightside);

  icoordelt_it.add_to_end(new ICOORDELT(pdblk.box.right(), pdblk.box.bottom()));

  icoordelt_it.add_to_end(new ICOORDELT(pdblk.box.right(), pdblk.box.top()));

}

/**

 * BLOCK::check_pitch

 *

 * Check whether the block is fixed or prop, set the flag, and set

 * the pitch if it is fixed.

 */

void BLOCK::check_pitch() { // check prop

  //      tprintf("Missing FFT fixed pitch stuff!\n");

  pitch = -1;

}

/**

 * BLOCK::compress

 *

 * Compress and move in a single operation.

 */

void BLOCK::compress( // squash it up

    const ICOORD vec  // and move

) {

  pdblk.box.move(vec);

  compress();

}

/**

 * BLOCK::print

 *

 * Print the info on a block

 */

void BLOCK::print( // print list of sides

    FILE *,        ///< file to print on

    bool dump      ///< print full detail

) {

  ICOORDELT_IT it = &pdblk.leftside; // iterator

  pdblk.box.print();

  tprintf("Proportional= %s\n", proportional ? "TRUE" : "FALSE");

  tprintf("Kerning= %d\n", kerning);

  tprintf("Spacing= %d\n", spacing);

  tprintf("Fixed_pitch=%d\n", pitch);

  tprintf("Filename= %s\n", filename.c_str());

  if (dump) {

    tprintf("Left side coords are:\n");

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

      tprintf("(%d,%d) ", it.data()->x(), it.data()->y());

    }

    tprintf("\n");

    tprintf("Right side coords are:\n");

    it.set_to_list(&pdblk.rightside);

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

      tprintf("(%d,%d) ", it.data()->x(), it.data()->y());

    }

    tprintf("\n");

  }

}

/**

 * BLOCK::operator=

 *

 * Assignment - duplicate the block structure, but with an EMPTY row list.

 */

BLOCK &BLOCK::operator=( // assignment

    const BLOCK &source  // from this

) {

  this->ELIST<BLOCK>::LINK::operator=(source);

  pdblk = source.pdblk;

  proportional = source.proportional;

  kerning = source.kerning;

  spacing = source.spacing;

  filename = source.filename; // STRINGs assign ok

  if (!rows.empty()) {

    rows.clear();

  }

  re_rotation_ = source.re_rotation_;

  classify_rotation_ = source.classify_rotation_;

  skew_ = source.skew_;

  return *this;

}

// This function is for finding the approximate (horizontal) distance from

// the x-coordinate of the left edge of a symbol to the left edge of the

// text block which contains it.  We are passed:

//   segments - output of PB_LINE_IT::get_line() which contains x-coordinate

//       intervals for the scan line going through the symbol's y-coordinate.

//       Each element of segments is of the form (x()=start_x, y()=length).

//   x - the x coordinate of the symbol we're interested in.

//   margin - return value, the distance from x,y to the left margin of the

//       block containing it.

// If all segments were to the right of x, we return false and 0.

static bool LeftMargin(ICOORDELT_LIST *segments, int x, int *margin) {

  bool found = false;

  *margin = 0;

  if (segments->empty()) {

    return found;

  }

  ICOORDELT_IT seg_it(segments);

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

    int cur_margin = x - seg_it.data()->x();

    if (cur_margin >= 0) {

      if (!found) {

        *margin = cur_margin;

      } else if (cur_margin < *margin) {

        *margin = cur_margin;

      }

      found = true;

    }

  }

  return found;

}

// This function is for finding the approximate (horizontal) distance from

// the x-coordinate of the right edge of a symbol to the right edge of the

// text block which contains it.  We are passed:

//   segments - output of PB_LINE_IT::get_line() which contains x-coordinate

//       intervals for the scan line going through the symbol's y-coordinate.

//       Each element of segments is of the form (x()=start_x, y()=length).

//   x - the x coordinate of the symbol we're interested in.

//   margin - return value, the distance from x,y to the right margin of the

//       block containing it.

// If all segments were to the left of x, we return false and 0.

static bool RightMargin(ICOORDELT_LIST *segments, int x, int *margin) {

  bool found = false;

  *margin = 0;

  if (segments->empty()) {

    return found;

  }

  ICOORDELT_IT seg_it(segments);

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

    int cur_margin = seg_it.data()->x() + seg_it.data()->y() - x;

    if (cur_margin >= 0) {

      if (!found) {

        *margin = cur_margin;

      } else if (cur_margin < *margin) {

        *margin = cur_margin;

      }

      found = true;

    }

  }

  return found;

}

// Compute the distance from the left and right ends of each row to the

// left and right edges of the block's polyblock.  Illustration:

//  ____________________________   _______________________

//  |  Howdy neighbor!         |  |rectangular blocks look|

//  |  This text is  written to|  |more like stacked pizza|

//  |illustrate how useful poly-  |boxes.                 |

//  |blobs  are   in -----------  ------   The    polyblob|

//  |dealing    with|     _________     |for a BLOCK  rec-|

//  |harder   layout|   /===========\   |ords the possibly|

//  |issues.        |    |  _    _  |   |skewed    pseudo-|

//  |  You  see this|    | |_| \|_| |   |rectangular      |

//  |text is  flowed|    |      }   |   |boundary     that|

//  |around  a  mid-|     \   ____  |   |forms the  ideal-|

//  |column portrait._____ \       /  __|ized  text margin|

//  |  Polyblobs     exist| \    /   |from which we should|

//  |to account for insets|  |   |   |measure    paragraph|

//  |which make  otherwise|  -----   |indentation.        |

//  -----------------------          ----------------------

//

// If we identify a drop-cap, we measure the left margin for the lines

// below the first line relative to one space past the drop cap.  The

// first line's margin and those past the drop cap area are measured

// relative to the enclosing polyblock.

//

// TODO(rays): Before this will work well, we'll need to adjust the

//             polyblob tighter around the text near images, as in:

//             UNLV_AUTO:mag.3G0  page 2

//             UNLV_AUTO:mag.3G4  page 16

void BLOCK::compute_row_margins() {

  if (row_list()->empty() || row_list()->singleton()) {

    return;

  }

  // If Layout analysis was not called, default to this.

  POLY_BLOCK rect_block(pdblk.bounding_box(), PT_FLOWING_TEXT);

  POLY_BLOCK *pblock = &rect_block;

  if (pdblk.poly_block() != nullptr) {

    pblock = pdblk.poly_block();

  }

  // Step One: Determine if there is a drop-cap.

  //           TODO(eger): Fix up drop cap code for RTL languages.

  ROW_IT r_it(row_list());

  ROW *first_row = r_it.data();

  ROW *second_row = r_it.data_relative(1);

  // initialize the bottom of a fictitious drop cap far above the first line.

  int drop_cap_bottom = first_row->bounding_box().top() + first_row->bounding_box().height();

  int drop_cap_right = first_row->bounding_box().left();

  int mid_second_line = second_row->bounding_box().top() - second_row->bounding_box().height() / 2;

  WERD_IT werd_it(r_it.data()->word_list()); // words of line one

  if (!werd_it.empty()) {

    C_BLOB_IT cblob_it(werd_it.data()->cblob_list());

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

      TBOX bbox = cblob_it.data()->bounding_box();

      if (bbox.bottom() <= mid_second_line) {

        // we found a real drop cap

        first_row->set_has_drop_cap(true);

        if (drop_cap_bottom > bbox.bottom()) {

          drop_cap_bottom = bbox.bottom();

        }

        if (drop_cap_right < bbox.right()) {

          drop_cap_right = bbox.right();

        }

      }

    }

  }

  // Step Two: Calculate the margin from the text of each row to the block

  //           (or drop-cap) boundaries.

  PB_LINE_IT lines(pblock);

  r_it.set_to_list(row_list());

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

    ROW *row = r_it.data();

    TBOX row_box = row->bounding_box();

    int left_y = row->base_line(row_box.left()) + row->x_height();

    int left_margin;

    const std::unique_ptr</*non-const*/ ICOORDELT_LIST> segments_left(lines.get_line(left_y));

    LeftMargin(segments_left.get(), row_box.left(), &left_margin);

    if (row_box.top() >= drop_cap_bottom) {

      int drop_cap_distance = row_box.left() - row->space() - drop_cap_right;

      if (drop_cap_distance < 0) {

        drop_cap_distance = 0;

      }

      if (drop_cap_distance < left_margin) {

        left_margin = drop_cap_distance;

      }

    }

    int right_y = row->base_line(row_box.right()) + row->x_height();

    int right_margin;

    const std::unique_ptr</*non-const*/ ICOORDELT_LIST> segments_right(lines.get_line(right_y));

    RightMargin(segments_right.get(), row_box.right(), &right_margin);

    row->set_lmargin(left_margin);

    row->set_rmargin(right_margin);

  }

}

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

 * PrintSegmentationStats

 *

 * Prints segmentation stats for the given block list.

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

void PrintSegmentationStats(BLOCK_LIST *block_list) {

  int num_blocks = 0;

  int num_rows = 0;

  int num_words = 0;

  int num_blobs = 0;

  BLOCK_IT block_it(block_list);

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

    BLOCK *block = block_it.data();

    ++num_blocks;

    ROW_IT row_it(block->row_list());

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

      ++num_rows;

      ROW *row = row_it.data();

      // Iterate over all werds in the row.

      WERD_IT werd_it(row->word_list());

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

        WERD *werd = werd_it.data();

        ++num_words;

        num_blobs += werd->cblob_list()->length();

      }

    }

  }

  tprintf("Block list stats:\nBlocks = %d\nRows = %d\nWords = %d\nBlobs = %d\n", num_blocks,

          num_rows, num_words, num_blobs);

}

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

 * ExtractBlobsFromSegmentation

 *

 * Extracts blobs from the given block list and adds them to the output list.

 * The block list must have been created by performing a page segmentation.

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

void ExtractBlobsFromSegmentation(BLOCK_LIST *blocks, C_BLOB_LIST *output_blob_list) {

  C_BLOB_IT return_list_it(output_blob_list);

  BLOCK_IT block_it(blocks);

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

    BLOCK *block = block_it.data();

    ROW_IT row_it(block->row_list());

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

      ROW *row = row_it.data();

      // Iterate over all werds in the row.

      WERD_IT werd_it(row->word_list());

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

        WERD *werd = werd_it.data();

        return_list_it.move_to_last();

        return_list_it.add_list_after(werd->cblob_list());

        return_list_it.move_to_last();

        return_list_it.add_list_after(werd->rej_cblob_list());

      }

    }

  }

}

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

 * RefreshWordBlobsFromNewBlobs()

 *

 * Refreshes the words in the block_list by using blobs in the

 * new_blobs list.

 * Block list must have word segmentation in it.

 * It consumes the blobs provided in the new_blobs list. The blobs leftover in

 * the new_blobs list after the call weren't matched to any blobs of the words

 * in block list.

 * The output not_found_blobs is a list of blobs from the original segmentation

 * in the block_list for which no corresponding new blobs were found.

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

void RefreshWordBlobsFromNewBlobs(BLOCK_LIST *block_list, C_BLOB_LIST *new_blobs,

                                  C_BLOB_LIST *not_found_blobs) {

  // Now iterate over all the blobs in the segmentation_block_list_, and just

  // replace the corresponding c-blobs inside the werds.

  BLOCK_IT block_it(block_list);

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

    BLOCK *block = block_it.data();

    if (block->pdblk.poly_block() != nullptr && !block->pdblk.poly_block()->IsText()) {

      continue; // Don't touch non-text blocks.

    }

    // Iterate over all rows in the block.

    ROW_IT row_it(block->row_list());

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

      ROW *row = row_it.data();

      // Iterate over all werds in the row.

      WERD_IT werd_it(row->word_list());

      WERD_LIST new_words;

      WERD_IT new_words_it(&new_words);

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

        WERD *werd = werd_it.extract();

        WERD *new_werd = werd->ConstructWerdWithNewBlobs(new_blobs, not_found_blobs);

        if (new_werd) {

          // Insert this new werd into the actual row's werd-list. Remove the

          // existing one.

          new_words_it.add_after_then_move(new_werd);

          delete werd;

        } else {

          // Reinsert the older word back, for lack of better options.

          // This is critical since dropping the words messes up segmentation:

          // eg. 1st word in the row might otherwise have W_FUZZY_NON turned on.

          new_words_it.add_after_then_move(werd);

        }

      }

      // Get rid of the old word list & replace it with the new one.

      row->word_list()->clear();

      werd_it.move_to_first();

      werd_it.add_list_after(&new_words);

    }

  }

}

} // namespace tesseract