///////////////////////////////////////////////////////////////////////

// File:        colfind.cpp

// Description: Class to hold BLOBNBOXs in a grid for fast access

//              to neighbours.

// Author:      Ray Smith

//

// (C) Copyright 2007, Google Inc.

// 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 "colfind.h"

#include "ccnontextdetect.h"

#include "colpartition.h"

#include "colpartitionset.h"

#ifndef DISABLED_LEGACY_ENGINE

#  include "equationdetectbase.h"

#endif

#include "blobbox.h"

#include "linefind.h"

#include "normalis.h"

#include "params.h"

#include "scrollview.h"

#include "strokewidth.h"

#include "tablefind.h"

#include "workingpartset.h"

#include <algorithm>

namespace tesseract {

// When assigning columns, the max number of misfit grid rows/ColPartitionSets

// that can be ignored.

const int kMaxIncompatibleColumnCount = 2;

// Max fraction of mean_column_gap_ for the gap between two partitions within a

// column to allow them to merge.

const double kHorizontalGapMergeFraction = 0.5;

// Minimum gutter width as a fraction of gridsize

const double kMinGutterWidthGrid = 0.5;

// Max multiple of a partition's median size as a distance threshold for

// adding noise blobs.

const double kMaxDistToPartSizeRatio = 1.5;

#ifndef GRAPHICS_DISABLED

static BOOL_VAR(textord_tabfind_show_initial_partitions, false, "Show partition bounds");

static BOOL_VAR(textord_tabfind_show_reject_blobs, false, "Show blobs rejected as noise");

static INT_VAR(textord_tabfind_show_partitions, 0,

               "Show partition bounds, waiting if >1 (ScrollView)");

static BOOL_VAR(textord_tabfind_show_columns, false, "Show column bounds (ScrollView)");

static BOOL_VAR(textord_tabfind_show_blocks, false, "Show final block bounds (ScrollView)");

#endif

static BOOL_VAR(textord_tabfind_find_tables, true, "run table detection");

#ifndef GRAPHICS_DISABLED

ScrollView *ColumnFinder::blocks_win_ = nullptr;

#endif

// Gridsize is an estimate of the text size in the image. A suitable value

// is in TO_BLOCK::line_size after find_components has been used to make

// the blobs.

// bleft and tright are the bounds of the image (or rectangle) being processed.

// vlines is a (possibly empty) list of TabVector and vertical_x and y are

// the sum logical vertical vector produced by LineFinder::FindVerticalLines.

ColumnFinder::ColumnFinder(int gridsize, const ICOORD &bleft, const ICOORD &tright, int resolution,

                           bool cjk_script, double aligned_gap_fraction, TabVector_LIST *vlines,

                           TabVector_LIST *hlines, int vertical_x, int vertical_y)

    : TabFind(gridsize, bleft, tright, vlines, vertical_x, vertical_y, resolution)

    , cjk_script_(cjk_script)

    , min_gutter_width_(static_cast<int>(kMinGutterWidthGrid * gridsize))

    , mean_column_gap_(tright.x() - bleft.x())

    , tabfind_aligned_gap_fraction_(aligned_gap_fraction)

    , deskew_(0.0f, 0.0f)

    , reskew_(1.0f, 0.0f)

    , rotation_(1.0f, 0.0f)

    , rerotate_(1.0f, 0.0f)

    , text_rotation_(0.0f, 0.0f)

    , best_columns_(nullptr)

    , stroke_width_(nullptr)

    , part_grid_(gridsize, bleft, tright)

    , nontext_map_(nullptr)

    , projection_(resolution)

    , denorm_(nullptr)

    , equation_detect_(nullptr) {

  TabVector_IT h_it(&horizontal_lines_);

  h_it.add_list_after(hlines);

}

ColumnFinder::~ColumnFinder() {

  for (auto set : column_sets_) {

    delete set;

  }

  delete[] best_columns_;

  delete stroke_width_;

#ifndef GRAPHICS_DISABLED

  delete input_blobs_win_;

#endif

  nontext_map_.destroy();

  while (denorm_ != nullptr) {

    DENORM *dead_denorm = denorm_;

    denorm_ = const_cast<DENORM *>(denorm_->predecessor());

    delete dead_denorm;

  }

  // The ColPartitions are destroyed automatically, but any boxes in

  // the noise_parts_ list are owned and need to be deleted explicitly.

  ColPartition_IT part_it(&noise_parts_);

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

    ColPartition *part = part_it.data();

    part->DeleteBoxes();

  }

  // Likewise any boxes in the good_parts_ list need to be deleted.

  // These are just the image parts. Text parts have already given their

  // boxes on to the TO_BLOCK, and have empty lists.

  part_it.set_to_list(&good_parts_);

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

    ColPartition *part = part_it.data();

    part->DeleteBoxes();

  }

  // Also, any blobs on the image_bblobs_ list need to have their cblobs

  // deleted. This only happens if there has been an early return from

  // FindColumns, as in a normal return, the blobs go into the grid and

  // end up in noise_parts_, good_parts_ or the output blocks.

  BLOBNBOX_IT bb_it(&image_bblobs_);

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

    BLOBNBOX *bblob = bb_it.data();

    delete bblob->cblob();

  }

}

// Performs initial processing on the blobs in the input_block:

// Setup the part_grid_, stroke_width_, nontext_map.

// Obvious noise blobs are filtered out and used to mark the nontext_map_.

// Initial stroke-width analysis is used to get local text alignment

// direction, so the textline projection_ map can be setup.

// On return, IsVerticallyAlignedText may be called (now optionally) to

// determine the gross textline alignment of the page.

void ColumnFinder::SetupAndFilterNoise(PageSegMode pageseg_mode, Image photo_mask_pix,

                                       TO_BLOCK *input_block) {

  part_grid_.Init(gridsize(), bleft(), tright());

  delete stroke_width_;

  stroke_width_ = new StrokeWidth(gridsize(), bleft(), tright());

  min_gutter_width_ = static_cast<int>(kMinGutterWidthGrid * gridsize());

  input_block->ReSetAndReFilterBlobs();

#ifndef GRAPHICS_DISABLED

  if (textord_tabfind_show_blocks) {

    input_blobs_win_ = MakeWindow(0, 0, "Filtered Input Blobs");

    input_block->plot_graded_blobs(input_blobs_win_);

  }

#endif // !GRAPHICS_DISABLED

  SetBlockRuleEdges(input_block);

  nontext_map_.destroy();

  // Run a preliminary strokewidth neighbour detection on the medium blobs.

  stroke_width_->SetNeighboursOnMediumBlobs(input_block);

  CCNonTextDetect nontext_detect(gridsize(), bleft(), tright());

  // Remove obvious noise and make the initial non-text map.

  nontext_map_ =

      nontext_detect.ComputeNonTextMask(textord_debug_tabfind, photo_mask_pix, input_block);

  stroke_width_->FindTextlineDirectionAndFixBrokenCJK(pageseg_mode, cjk_script_, input_block);

  // Clear the strokewidth grid ready for rotation or leader finding.

  stroke_width_->Clear();

}

// Tests for vertical alignment of text (returning true if so), and generates

// a list of blobs of moderate aspect ratio, in the most frequent writing

// direction (in osd_blobs) for orientation and script detection to test

// the character orientation.

// block is the single block for the whole page or rectangle to be OCRed.

// Note that the vertical alignment may be due to text whose writing direction

// is vertical, like say Japanese, or due to text whose writing direction is

// horizontal but whose text appears vertically aligned because the image is

// not the right way up.

bool ColumnFinder::IsVerticallyAlignedText(double find_vertical_text_ratio, TO_BLOCK *block,

                                           BLOBNBOX_CLIST *osd_blobs) {

  return stroke_width_->TestVerticalTextDirection(find_vertical_text_ratio, block, osd_blobs);

}

// Rotates the blobs and the TabVectors so that the gross writing direction

// (text lines) are horizontal and lines are read down the page.

// Applied rotation stored in rotation_.

// A second rotation is calculated for application during recognition to

// make the rotated blobs upright for recognition.

// Subsequent rotation stored in text_rotation_.

//

// Arguments:

//   vertical_text_lines true if the text lines are vertical.

//   recognition_rotation [0..3] is the number of anti-clockwise 90 degree

//   rotations from osd required for the text to be upright and readable.

void ColumnFinder::CorrectOrientation(TO_BLOCK *block, bool vertical_text_lines,

                                      int recognition_rotation) {

  const FCOORD anticlockwise90(0.0f, 1.0f);

  const FCOORD clockwise90(0.0f, -1.0f);

  const FCOORD rotation180(-1.0f, 0.0f);

  const FCOORD norotation(1.0f, 0.0f);

  text_rotation_ = norotation;

  // Rotate the page to make the text upright, as implied by

  // recognition_rotation.

  rotation_ = norotation;

  if (recognition_rotation == 1) {

    rotation_ = anticlockwise90;

  } else if (recognition_rotation == 2) {

    rotation_ = rotation180;

  } else if (recognition_rotation == 3) {

    rotation_ = clockwise90;

  }

  // We infer text writing direction to be vertical if there are several

  // vertical text lines detected, and horizontal if not. But if the page

  // orientation was determined to be 90 or 270 degrees, the true writing

  // direction is the opposite of what we inferred.

  if (recognition_rotation & 1) {

    vertical_text_lines = !vertical_text_lines;

  }

  // If we still believe the writing direction is vertical, we use the

  // convention of rotating the page ccw 90 degrees to make the text lines

  // horizontal, and mark the blobs for rotation cw 90 degrees for

  // classification so that the text order is correct after recognition.

  if (vertical_text_lines) {

    rotation_.rotate(anticlockwise90);

    text_rotation_.rotate(clockwise90);

  }

  // Set rerotate_ to the inverse of rotation_.

  rerotate_ = FCOORD(rotation_.x(), -rotation_.y());

  if (rotation_.x() != 1.0f || rotation_.y() != 0.0f) {

    // Rotate all the blobs and tab vectors.

    RotateBlobList(rotation_, &block->large_blobs);

    RotateBlobList(rotation_, &block->blobs);

    RotateBlobList(rotation_, &block->small_blobs);

    RotateBlobList(rotation_, &block->noise_blobs);

    TabFind::ResetForVerticalText(rotation_, rerotate_, &horizontal_lines_, &min_gutter_width_);

    part_grid_.Init(gridsize(), bleft(), tright());

    // Reset all blobs to initial state and filter by size.

    // Since they have rotated, the list they belong on could have changed.

    block->ReSetAndReFilterBlobs();

    SetBlockRuleEdges(block);

    stroke_width_->CorrectForRotation(rerotate_, &part_grid_);

  }

  if (textord_debug_tabfind) {

    tprintf("Vertical=%d, orientation=%d, final rotation=(%f, %f)+(%f,%f)\n", vertical_text_lines,

            recognition_rotation, rotation_.x(), rotation_.y(), text_rotation_.x(),

            text_rotation_.y());

  }

  // Setup the denormalization.

  ASSERT_HOST(denorm_ == nullptr);

  denorm_ = new DENORM;

  denorm_->SetupNormalization(nullptr, &rotation_, nullptr, 0.0f, 0.0f, 1.0f, 1.0f, 0.0f, 0.0f);

}

// Finds blocks of text, image, rule line, table etc, returning them in the

// blocks and to_blocks

// (Each TO_BLOCK points to the basic BLOCK and adds more information.)

// Image blocks are generated by a combination of photo_mask_pix (which may

// NOT be nullptr) and the rejected text found during preliminary textline

// finding.

// The input_block is the result of a call to find_components, and contains

// the blobs found in the image or rectangle to be OCRed. These blobs will be

// removed and placed in the output blocks, while unused ones will be deleted.

// If single_column is true, the input is treated as single column, but

// it is still divided into blocks of equal line spacing/text size.

// scaled_color is scaled down by scaled_factor from the input color image,

// and may be nullptr if the input was not color.

// grey_pix is optional, but if present must match the photo_mask_pix in size,

// and must be a *real* grey image instead of binary_pix * 255.

// thresholds_pix is expected to be present iff grey_pix is present and

// can be an integer factor reduction of the grey_pix. It represents the

// thresholds that were used to create the binary_pix from the grey_pix.

// If diacritic_blobs is non-null, then diacritics/noise blobs, that would

// confuse layout analysis by causing textline overlap, are placed there,

// with the expectation that they will be reassigned to words later and

// noise/diacriticness determined via classification.

// Returns -1 if the user hits the 'd' key in the blocks window while running

// in debug mode, which requests a retry with more debug info.

int ColumnFinder::FindBlocks(PageSegMode pageseg_mode, Image scaled_color, int scaled_factor,

                             TO_BLOCK *input_block, Image photo_mask_pix, Image thresholds_pix,

                             Image grey_pix, DebugPixa *pixa_debug, BLOCK_LIST *blocks,

                             BLOBNBOX_LIST *diacritic_blobs, TO_BLOCK_LIST *to_blocks) {

  photo_mask_pix |= nontext_map_;

  stroke_width_->FindLeaderPartitions(input_block, &part_grid_);

  stroke_width_->RemoveLineResidue(&big_parts_);

  FindInitialTabVectors(nullptr, min_gutter_width_, tabfind_aligned_gap_fraction_, input_block);

  SetBlockRuleEdges(input_block);

  stroke_width_->GradeBlobsIntoPartitions(pageseg_mode, rerotate_, input_block, nontext_map_,

                                          denorm_, cjk_script_, &projection_, diacritic_blobs,

                                          &part_grid_, &big_parts_);

  if (!PSM_SPARSE(pageseg_mode)) {

    ImageFind::FindImagePartitions(photo_mask_pix, rotation_, rerotate_, input_block, this,

                                   pixa_debug, &part_grid_, &big_parts_);

    ImageFind::TransferImagePartsToImageMask(rerotate_, &part_grid_, photo_mask_pix);

    ImageFind::FindImagePartitions(photo_mask_pix, rotation_, rerotate_, input_block, this,

                                   pixa_debug, &part_grid_, &big_parts_);

  }

  part_grid_.ReTypeBlobs(&image_bblobs_);

  TidyBlobs(input_block);

  Reset();

  // TODO(rays) need to properly handle big_parts_.

  ColPartition_IT p_it(&big_parts_);

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

    p_it.data()->DisownBoxesNoAssert();

  }

  big_parts_.clear();

  delete stroke_width_;

  stroke_width_ = nullptr;

  // Compute the edge offsets whether or not there is a grey_pix. It is done

  // here as the c_blobs haven't been touched by rotation or anything yet,

  // so no denorm is required, yet the text has been separated from image, so

  // no time is wasted running it on image blobs.

  input_block->ComputeEdgeOffsets(thresholds_pix, grey_pix);

  // A note about handling right-to-left scripts (Hebrew/Arabic):

  // The columns must be reversed and come out in right-to-left instead of

  // the normal left-to-right order. Because the left-to-right ordering

  // is implicit in many data structures, it is simpler to fool the algorithms

  // into thinking they are dealing with left-to-right text.

  // To do this, we reflect the needed data in the y-axis and then reflect

  // the blocks back after they have been created. This is a temporary

  // arrangement that is confined to this function only, so the reflection

  // is completely invisible in the output blocks.

  // The only objects reflected are:

  // The vertical separator lines that have already been found;

  // The bounding boxes of all BLOBNBOXES on all lists on the input_block

  // plus the image_bblobs. The outlines are not touched, since they are

  // not looked at.

  bool input_is_rtl = input_block->block->right_to_left();

  if (input_is_rtl) {

    // Reflect the vertical separator lines (member of TabFind).

    ReflectInYAxis();

    // Reflect the blob boxes.

    ReflectForRtl(input_block, &image_bblobs_);

    part_grid_.ReflectInYAxis();

  }

  if (!PSM_SPARSE(pageseg_mode)) {

    if (!PSM_COL_FIND_ENABLED(pageseg_mode)) {

      // No tab stops needed. Just the grid that FindTabVectors makes.

      DontFindTabVectors(&image_bblobs_, input_block, &deskew_, &reskew_);

    } else {

      SetBlockRuleEdges(input_block);

      // Find the tab stops, estimate skew, and deskew the tabs, blobs and

      // part_grid_.

      FindTabVectors(&horizontal_lines_, &image_bblobs_, input_block, min_gutter_width_,

                     tabfind_aligned_gap_fraction_, &part_grid_, &deskew_, &reskew_);

      // Add the deskew to the denorm_.

      auto *new_denorm = new DENORM;

      new_denorm->SetupNormalization(nullptr, &deskew_, denorm_, 0.0f, 0.0f, 1.0f, 1.0f, 0.0f,

                                     0.0f);

      denorm_ = new_denorm;

    }

    SetBlockRuleEdges(input_block);

    part_grid_.SetTabStops(this);

    // Make the column_sets_.

    if (!MakeColumns(false)) {

      tprintf("Empty page!!\n");

      part_grid_.DeleteParts();

      return 0; // This is an empty page.

    }

    // Refill the grid using rectangular spreading, and get the benefit

    // of the completed tab vectors marking the rule edges of each blob.

    Clear();

#ifndef GRAPHICS_DISABLED

    if (textord_tabfind_show_reject_blobs) {

      ScrollView *rej_win = MakeWindow(500, 300, "Rejected blobs");

      input_block->plot_graded_blobs(rej_win);

    }

#endif // !GRAPHICS_DISABLED

    InsertBlobsToGrid(false, false, &image_bblobs_, this);

    InsertBlobsToGrid(true, true, &input_block->blobs, this);

    part_grid_.GridFindMargins(best_columns_);

    // Split and merge the partitions by looking at local neighbours.

    GridSplitPartitions();

    // Resolve unknown partitions by adding to an existing partition, fixing

    // the type, or declaring them noise.

    part_grid_.GridFindMargins(best_columns_);

    GridMergePartitions();

    // Insert any unused noise blobs that are close enough to an appropriate

    // partition.

    InsertRemainingNoise(input_block);

    // Add horizontal line separators as partitions.

    GridInsertHLinePartitions();

    GridInsertVLinePartitions();

    // Recompute margins based on a local neighbourhood search.

    part_grid_.GridFindMargins(best_columns_);

    SetPartitionTypes();

  }

#ifndef GRAPHICS_DISABLED

  if (textord_tabfind_show_initial_partitions) {

    ScrollView *part_win = MakeWindow(100, 300, "InitialPartitions");

    part_grid_.DisplayBoxes(part_win);

    DisplayTabVectors(part_win);

  }

#endif

  if (!PSM_SPARSE(pageseg_mode)) {

#ifndef DISABLED_LEGACY_ENGINE

    if (equation_detect_) {

      equation_detect_->FindEquationParts(&part_grid_, best_columns_);

    }

#endif

    if (textord_tabfind_find_tables) {

      TableFinder table_finder;

      table_finder.Init(gridsize(), bleft(), tright());

      table_finder.set_resolution(resolution_);

      table_finder.set_left_to_right_language(!input_block->block->right_to_left());

      // Copy cleaned partitions from part_grid_ to clean_part_grid_ and

      // insert dot-like noise into period_grid_

      table_finder.InsertCleanPartitions(&part_grid_, input_block);

      // Get Table Regions

      table_finder.LocateTables(&part_grid_, best_columns_, WidthCB(), reskew_);

    }

    GridRemoveUnderlinePartitions();

    part_grid_.DeleteUnknownParts(input_block);

    // Build the partitions into chains that belong in the same block and

    // refine into one-to-one links, then smooth the types within each chain.

    part_grid_.FindPartitionPartners();

    part_grid_.FindFigureCaptions();

    part_grid_.RefinePartitionPartners(true);

    SmoothPartnerRuns();

#ifndef GRAPHICS_DISABLED

    if (textord_tabfind_show_partitions) {

      ScrollView *window = MakeWindow(400, 300, "Partitions");

      if (window != nullptr) {

        part_grid_.DisplayBoxes(window);

        if (!textord_debug_printable) {

          DisplayTabVectors(window);

        }

        if (window != nullptr && textord_tabfind_show_partitions > 1) {

          window->AwaitEvent(SVET_DESTROY);

        }

      }

    }

#endif // !GRAPHICS_DISABLED

    part_grid_.AssertNoDuplicates();

  }

  // Ownership of the ColPartitions moves from part_sets_ to part_grid_ here,

  // and ownership of the BLOBNBOXes moves to the ColPartitions.

  // (They were previously owned by the block or the image_bblobs list.)

  ReleaseBlobsAndCleanupUnused(input_block);

  // Ownership of the ColPartitions moves from part_grid_ to good_parts_ and

  // noise_parts_ here. In text blocks, ownership of the BLOBNBOXes moves

  // from the ColPartitions to the output TO_BLOCK. In non-text, the

  // BLOBNBOXes stay with the ColPartitions and get deleted in the destructor.

  if (PSM_SPARSE(pageseg_mode)) {

    part_grid_.ExtractPartitionsAsBlocks(blocks, to_blocks);

  } else {

    TransformToBlocks(blocks, to_blocks);

  }

  if (textord_debug_tabfind) {

    tprintf("Found %d blocks, %d to_blocks\n", blocks->length(), to_blocks->length());

  }

#ifndef GRAPHICS_DISABLED

  if (textord_tabfind_show_blocks) {

    DisplayBlocks(blocks);

  }

#endif

  RotateAndReskewBlocks(input_is_rtl, to_blocks);

  int result = 0;

#ifndef GRAPHICS_DISABLED

  if (blocks_win_ != nullptr) {

    bool waiting = false;

    do {

      waiting = false;

      auto event = blocks_win_->AwaitEvent(SVET_ANY);

      if (event->type == SVET_INPUT && event->parameter != nullptr) {

        if (*event->parameter == 'd') {

          result = -1;

        } else {

          blocks->clear();

        }

      } else if (event->type == SVET_DESTROY) {

        blocks_win_ = nullptr;

      } else {

        waiting = true;

      }

    } while (waiting);

  }

#endif // !GRAPHICS_DISABLED

  return result;

}

// Get the rotation required to deskew, and its inverse rotation.

void ColumnFinder::GetDeskewVectors(FCOORD *deskew, FCOORD *reskew) {

  *reskew = reskew_;

  *deskew = reskew_;

  deskew->set_y(-deskew->y());

}

#ifndef DISABLED_LEGACY_ENGINE

void ColumnFinder::SetEquationDetect(EquationDetectBase *detect) {

  equation_detect_ = detect;

}

#endif

//////////////// PRIVATE CODE /////////////////////////

#ifndef GRAPHICS_DISABLED

// Displays the blob and block bounding boxes in a window called Blocks.

void ColumnFinder::DisplayBlocks(BLOCK_LIST *blocks) {

  if (blocks_win_ == nullptr) {

    blocks_win_ = MakeWindow(700, 300, "Blocks");

  } else {

    blocks_win_->Clear();

  }

  DisplayBoxes(blocks_win_);

  BLOCK_IT block_it(blocks);

  int serial = 1;

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

    BLOCK *block = block_it.data();

    block->pdblk.plot(blocks_win_, serial++,

                      textord_debug_printable ? ScrollView::BLUE : ScrollView::GREEN);

  }

  blocks_win_->Update();

}

// Displays the column edges at each grid y coordinate defined by

// best_columns_.

void ColumnFinder::DisplayColumnBounds(PartSetVector *sets) {

  ScrollView *col_win = MakeWindow(50, 300, "Columns");

  DisplayBoxes(col_win);

  col_win->Pen(textord_debug_printable ? ScrollView::BLUE : ScrollView::GREEN);

  for (int i = 0; i < gridheight_; ++i) {

    ColPartitionSet *columns = best_columns_[i];

    if (columns != nullptr) {

      columns->DisplayColumnEdges(i * gridsize_, (i + 1) * gridsize_, col_win);

    }

  }

}

#endif // !GRAPHICS_DISABLED

// Sets up column_sets_ (the determined column layout at each horizontal

// slice). Returns false if the page is empty.

bool ColumnFinder::MakeColumns(bool single_column) {

  // The part_sets_ are a temporary structure used during column creation,

  // and is a vector of ColPartitionSets, representing ColPartitions found

  // at horizontal slices through the page.

  PartSetVector part_sets;

  if (!single_column) {

    if (!part_grid_.MakeColPartSets(&part_sets)) {

      return false; // Empty page.

    }

    ASSERT_HOST(part_grid_.gridheight() == gridheight_);

    // Try using only the good parts first.

    bool good_only = true;

    do {

      for (int i = 0; i < gridheight_; ++i) {

        ColPartitionSet *line_set = part_sets.at(i);

        if (line_set != nullptr && line_set->LegalColumnCandidate()) {

          ColPartitionSet *column_candidate = line_set->Copy(good_only);

          if (column_candidate != nullptr) {

            column_candidate->AddToColumnSetsIfUnique(&column_sets_, WidthCB());

          }

        }

      }

      good_only = !good_only;

    } while (column_sets_.empty() && !good_only);

    if (textord_debug_tabfind) {

      PrintColumnCandidates("Column candidates");

    }

    // Improve the column candidates against themselves.

    ImproveColumnCandidates(&column_sets_, &column_sets_);

    if (textord_debug_tabfind) {

      PrintColumnCandidates("Improved columns");

    }

    // Improve the column candidates using the part_sets_.

    ImproveColumnCandidates(&part_sets, &column_sets_);

  }

  ColPartitionSet *single_column_set = part_grid_.MakeSingleColumnSet(WidthCB());

  if (single_column_set != nullptr) {

    // Always add the single column set as a backup even if not in

    // single column mode.

    single_column_set->AddToColumnSetsIfUnique(&column_sets_, WidthCB());

  }

  if (textord_debug_tabfind) {

    PrintColumnCandidates("Final Columns");

  }

  bool has_columns = !column_sets_.empty();

  if (has_columns) {

    // Divide the page into sections of uniform column layout.

    bool any_multi_column = AssignColumns(part_sets);

#ifndef GRAPHICS_DISABLED

    if (textord_tabfind_show_columns) {

      DisplayColumnBounds(&part_sets);

    }

#endif

    ComputeMeanColumnGap(any_multi_column);

  }

  for (auto line_set : part_sets) {

    if (line_set != nullptr) {

      line_set->RelinquishParts();

      delete line_set;

    }

  }

  return has_columns;

}

// Attempt to improve the column_candidates by expanding the columns

// and adding new partitions from the partition sets in src_sets.

// Src_sets may be equal to column_candidates, in which case it will

// use them as a source to improve themselves.

void ColumnFinder::ImproveColumnCandidates(PartSetVector *src_sets, PartSetVector *column_sets) {

  // TODO: optimize.

  PartSetVector temp_cols = *column_sets;

  column_sets->clear();

  if (src_sets == column_sets) {

    src_sets = &temp_cols;

  }

  int set_size = temp_cols.size();

  // Try using only the good parts first.

  bool good_only = true;

  do {

    for (int i = 0; i < set_size; ++i) {

      ColPartitionSet *column_candidate = temp_cols.at(i);

      ASSERT_HOST(column_candidate != nullptr);

      ColPartitionSet *improved = column_candidate->Copy(good_only);

      if (improved != nullptr) {

        improved->ImproveColumnCandidate(WidthCB(), src_sets);

        improved->AddToColumnSetsIfUnique(column_sets, WidthCB());

      }

    }

    good_only = !good_only;

  } while (column_sets->empty() && !good_only);

  if (column_sets->empty()) {

    // TODO: optimize.

    *column_sets = temp_cols;

    temp_cols.clear();

  } else {

    for (auto data : temp_cols) {

      delete data;

    }

  }

}

// Prints debug information on the column candidates.

void ColumnFinder::PrintColumnCandidates(const char *title) {

  int set_size = column_sets_.size();

  tprintf("Found %d %s:\n", set_size, title);

  if (textord_debug_tabfind >= 3) {

    for (int i = 0; i < set_size; ++i) {

      ColPartitionSet *column_set = column_sets_.at(i);

      column_set->Print();

    }

  }

}

// Finds the optimal set of columns that cover the entire image with as

// few changes in column partition as possible.

// NOTE: this could be thought of as an optimization problem, but a simple

// greedy algorithm is used instead. The algorithm repeatedly finds the modal

// compatible column in an unassigned region and uses that with the extra

// tweak of extending the modal region over small breaks in compatibility.

// Where modal regions overlap, the boundary is chosen so as to minimize

// the cost in terms of ColPartitions not fitting an approved column.

// Returns true if any part of the page is multi-column.

bool ColumnFinder::AssignColumns(const PartSetVector &part_sets) {

  int set_count = part_sets.size();

  ASSERT_HOST(set_count == gridheight());

  // Allocate and init the best_columns_.

  best_columns_ = new ColPartitionSet *[set_count];

  for (int y = 0; y < set_count; ++y) {

    best_columns_[y] = nullptr;

  }

  int column_count = column_sets_.size();

  // column_set_costs[part_sets_ index][column_sets_ index] is

  // < INT32_MAX if the partition set is compatible with the column set,

  // in which case its value is the cost for that set used in deciding

  // which competing set to assign.

  // any_columns_possible[part_sets_ index] is true if any of

  // possible_column_sets[part_sets_ index][*] is < INT32_MAX.

  // assigned_costs[part_sets_ index] is set to the column_set_costs

  // of the assigned column_sets_ index or INT32_MAX if none is set.

  // On return the best_columns_ member is set.

  bool *any_columns_possible = new bool[set_count];

  int *assigned_costs = new int[set_count];

  int **column_set_costs = new int *[set_count];

  // Set possible column_sets to indicate whether each set is compatible

  // with each column.

  for (int part_i = 0; part_i < set_count; ++part_i) {

    ColPartitionSet *line_set = part_sets.at(part_i);

    bool debug = line_set != nullptr && WithinTestRegion(2, line_set->bounding_box().left(),

                                                         line_set->bounding_box().bottom());

    column_set_costs[part_i] = new int[column_count];

    any_columns_possible[part_i] = false;

    assigned_costs[part_i] = INT32_MAX;

    for (int col_i = 0; col_i < column_count; ++col_i) {

      if (line_set != nullptr &&

          column_sets_.at(col_i)->CompatibleColumns(debug, line_set, WidthCB())) {

        column_set_costs[part_i][col_i] = column_sets_.at(col_i)->UnmatchedWidth(line_set);

        any_columns_possible[part_i] = true;

      } else {

        column_set_costs[part_i][col_i] = INT32_MAX;

        if (debug) {

          tprintf("Set id %d did not match at y=%d, lineset =%p\n",

                  col_i, part_i, static_cast<void *>(line_set));

        }

      }

    }

  }

  bool any_multi_column = false;

  // Assign a column set to each vertical grid position.

  // While there is an unassigned range, find its mode.

  int start, end;

  while (BiggestUnassignedRange(set_count, any_columns_possible, &start, &end)) {

    if (textord_debug_tabfind >= 2) {

      tprintf("Biggest unassigned range = %d- %d\n", start, end);

    }

    // Find the modal column_set_id in the range.

    int column_set_id = RangeModalColumnSet(column_set_costs, assigned_costs, start, end);

    if (textord_debug_tabfind >= 2) {

      tprintf("Range modal column id = %d\n", column_set_id);

      column_sets_.at(column_set_id)->Print();

    }

    // Now find the longest run of the column_set_id in the range.

    ShrinkRangeToLongestRun(column_set_costs, assigned_costs, any_columns_possible, column_set_id,

                            &start, &end);

    if (textord_debug_tabfind >= 2) {

      tprintf("Shrunk range = %d- %d\n", start, end);

    }

    // Extend the start and end past the longest run, while there are

    // only small gaps in compatibility that can be overcome by larger

    // regions of compatibility beyond.

    ExtendRangePastSmallGaps(column_set_costs, assigned_costs, any_columns_possible, column_set_id,

                             -1, -1, &start);

    --end;

    ExtendRangePastSmallGaps(column_set_costs, assigned_costs, any_columns_possible, column_set_id,

                             1, set_count, &end);

    ++end;

    if (textord_debug_tabfind) {

      tprintf("Column id %d applies to range = %d - %d\n", column_set_id, start, end);

    }

    // Assign the column to the range, which now may overlap with other ranges.

    AssignColumnToRange(column_set_id, start, end, column_set_costs, assigned_costs);

    if (column_sets_.at(column_set_id)->GoodColumnCount() > 1) {

      any_multi_column = true;

    }

  }

  // If anything remains unassigned, the whole lot is unassigned, so

  // arbitrarily assign id 0.

  if (best_columns_[0] == nullptr) {

    AssignColumnToRange(0, 0, gridheight_, column_set_costs, assigned_costs);

  }

  // Free memory.

  for (int i = 0; i < set_count; ++i) {

    delete[] column_set_costs[i];

  }

  delete[] assigned_costs;

  delete[] any_columns_possible;

  delete[] column_set_costs;

  return any_multi_column;

}

// Finds the biggest range in part_sets_ that has no assigned column, but

// column assignment is possible.

bool ColumnFinder::BiggestUnassignedRange(int set_count, const bool *any_columns_possible,

                                          int *best_start, int *best_end) {

  int best_range_size = 0;

  *best_start = set_count;

  *best_end = set_count;

  int end = set_count;

  for (int start = 0; start < gridheight_; start = end) {

    // Find the first unassigned index in start.

    while (start < set_count) {

      if (best_columns_[start] == nullptr && any_columns_possible[start]) {

        break;

      }

      ++start;

    }

    // Find the first past the end and count the good ones in between.

    int range_size = 1; // Number of non-null, but unassigned line sets.

    end = start + 1;

    while (end < set_count) {

      if (best_columns_[end] != nullptr) {

        break;

      }

      if (any_columns_possible[end]) {

        ++range_size;

      }

      ++end;

    }

    if (start < set_count && range_size > best_range_size) {

      best_range_size = range_size;

      *best_start = start;

      *best_end = end;

    }

  }

  return *best_start < *best_end;

}

// Finds the modal compatible column_set_ index within the given range.

int ColumnFinder::RangeModalColumnSet(int **column_set_costs, const int *assigned_costs, int start,

                                      int end) {

  int column_count = column_sets_.size();

  STATS column_stats(0, column_count - 1);

  for (int part_i = start; part_i < end; ++part_i) {

    for (int col_j = 0; col_j < column_count; ++col_j) {

      if (column_set_costs[part_i][col_j] < assigned_costs[part_i]) {

        column_stats.add(col_j, 1);

      }

    }

  }

  ASSERT_HOST(column_stats.get_total() > 0);

  return column_stats.mode();

}

// Given that there are many column_set_id compatible columns in the range,

// shrinks the range to the longest contiguous run of compatibility, allowing

// gaps where no columns are possible, but not where competing columns are

// possible.

void ColumnFinder::ShrinkRangeToLongestRun(int **column_set_costs, const int *assigned_costs,

                                           const bool *any_columns_possible, int column_set_id,

                                           int *best_start, int *best_end) {

  // orig_start and orig_end are the maximum range we will look at.

  int orig_start = *best_start;

  int orig_end = *best_end;

  int best_range_size = 0;

  *best_start = orig_end;

  *best_end = orig_end;

  int end = orig_end;

  for (int start = orig_start; start < orig_end; start = end) {

    // Find the first possible

    while (start < orig_end) {

      if (column_set_costs[start][column_set_id] < assigned_costs[start] ||

          !any_columns_possible[start]) {

        break;

      }

      ++start;

    }

    // Find the first past the end.

    end = start + 1;

    while (end < orig_end) {

      if (column_set_costs[end][column_set_id] >= assigned_costs[start] &&

          any_columns_possible[end]) {

        break;

      }

      ++end;

    }

    if (start < orig_end && end - start > best_range_size) {

      best_range_size = end - start;

      *best_start = start;

      *best_end = end;

    }

  }

}

// Moves start in the direction of step, up to, but not including end while

// the only incompatible regions are no more than kMaxIncompatibleColumnCount

// in size, and the compatible regions beyond are bigger.

void ColumnFinder::ExtendRangePastSmallGaps(int **column_set_costs, const int *assigned_costs,

                                            const bool *any_columns_possible, int column_set_id,

                                            int step, int end, int *start) {

  if (textord_debug_tabfind > 2) {

    tprintf("Starting expansion at %d, step=%d, limit=%d\n", *start, step, end);

  }

  if (*start == end) {

    return; // Cannot be expanded.

  }

  int barrier_size = 0;

  int good_size = 0;

  do {

    // Find the size of the incompatible barrier.

    barrier_size = 0;

    int i;

    for (i = *start + step; i != end; i += step) {

      if (column_set_costs[i][column_set_id] < assigned_costs[i]) {

        break; // We are back on.

      }

      // Locations where none are possible don't count.

      if (any_columns_possible[i]) {

        ++barrier_size;

      }

    }

    if (textord_debug_tabfind > 2) {

      tprintf("At %d, Barrier size=%d\n", i, barrier_size);

    }

    if (barrier_size > kMaxIncompatibleColumnCount) {

      return; // Barrier too big.

    }

    if (i == end) {

      // We can't go any further, but the barrier was small, so go to the end.

      *start = i - step;

      return;

    }

    // Now find the size of the good region on the other side.

    good_size = 1;

    for (i += step; i != end; i += step) {

      if (column_set_costs[i][column_set_id] < assigned_costs[i]) {

        ++good_size;

      } else if (any_columns_possible[i]) {

        break;

      }

    }

    if (textord_debug_tabfind > 2) {

      tprintf("At %d, good size = %d\n", i, good_size);

    }

    // If we had enough good ones we can extend the start and keep looking.

    if (good_size >= barrier_size) {

      *start = i - step;

    }

  } while (good_size >= barrier_size);

}

// Assigns the given column_set_id to the given range.

void ColumnFinder::AssignColumnToRange(int column_set_id, int start, int end,

                                       int **column_set_costs, int *assigned_costs) {

  ColPartitionSet *column_set = column_sets_.at(column_set_id);

  for (int i = start; i < end; ++i) {

    assigned_costs[i] = column_set_costs[i][column_set_id];

    best_columns_[i] = column_set;

  }

}