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

// File:        colpartitiongrid.cpp

// Description: Class collecting code that acts on a BBGrid of ColPartitions.

// Author:      Ray Smith

//

// (C) Copyright 2009, 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.

//

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

#ifdef HAVE_CONFIG_H

#  include "config_auto.h"

#endif

#include "colpartitiongrid.h"

#include "colpartitionset.h"

#include "imagefind.h"

#include <algorithm>

#include <utility>

namespace tesseract {

// Max pad factor used to search the neighbourhood of a partition to smooth

// partition types.

const int kMaxPadFactor = 6;

// Max multiple of size (min(height, width)) for the distance of the nearest

// neighbour for the change of type to be used.

const int kMaxNeighbourDistFactor = 4;

// Maximum number of lines in a credible figure caption.

const int kMaxCaptionLines = 7;

// Min ratio between biggest and smallest gap to bound a caption.

const double kMinCaptionGapRatio = 2.0;

// Min ratio between biggest gap and mean line height to bound a caption.

const double kMinCaptionGapHeightRatio = 0.5;

// Min fraction of ColPartition height to be overlapping for margin purposes.

const double kMarginOverlapFraction = 0.25;

// Size ratio required to consider an unmerged overlapping partition to be big.

const double kBigPartSizeRatio = 1.75;

// Fraction of gridsize to allow arbitrary overlap between partitions.

const double kTinyEnoughTextlineOverlapFraction = 0.25;

// Max vertical distance of neighbouring ColPartition as a multiple of

// partition height for it to be a partner.

// TODO(rays) fix the problem that causes a larger number to not work well.

// The value needs to be larger as sparse text blocks in a page that gets

// marked as single column will not find adjacent lines as partners, and

// will merge horizontally distant, but aligned lines. See rep.4B3 p5.

// The value needs to be small because double-spaced legal docs written

// in a single column, but justified courier have widely spaced lines

// that need to get merged before they partner-up with the lines above

// and below. See legal.3B5 p13/17. Neither of these should depend on

// the value of kMaxPartitionSpacing to be successful, and ColPartition

// merging needs attention to fix this problem.

const double kMaxPartitionSpacing = 1.75;

// Margin by which text has to beat image or vice-versa to make a firm

// decision in GridSmoothNeighbour.

const int kSmoothDecisionMargin = 4;

ColPartitionGrid::ColPartitionGrid(int gridsize, const ICOORD &bleft,

                                   const ICOORD &tright)

    : BBGrid<ColPartition, ColPartition_CLIST, ColPartition_C_IT>(

          gridsize, bleft, tright) {}

// Handles a click event in a display window.

void ColPartitionGrid::HandleClick(int x, int y) {

  BBGrid<ColPartition, ColPartition_CLIST, ColPartition_C_IT>::HandleClick(x,

                                                                           y);

  // Run a radial search for partitions that overlap.

  ColPartitionGridSearch radsearch(this);

  radsearch.SetUniqueMode(true);

  radsearch.StartRadSearch(x, y, 1);

  ColPartition *neighbour;

  FCOORD click(x, y);

  while ((neighbour = radsearch.NextRadSearch()) != nullptr) {

    const TBOX &nbox = neighbour->bounding_box();

    if (nbox.contains(click)) {

      tprintf("Block box:");

      neighbour->bounding_box().print();

      neighbour->Print();

    }

  }

}

// Merges ColPartitions in the grid that look like they belong in the same

// textline.

// For all partitions in the grid, calls the box_cb permanent callback

// to compute the search box, searches the box, and if a candidate is found,

// calls the confirm_cb to check any more rules. If the confirm_cb returns

// true, then the partitions are merged.

// Both callbacks are deleted before returning.

void ColPartitionGrid::Merges(

    const std::function<bool(ColPartition *, TBOX *)> &box_cb,

    const std::function<bool(const ColPartition *, const ColPartition *)>

        &confirm_cb) {

  // Iterate the ColPartitions in the grid.

  ColPartitionGridSearch gsearch(this);

  gsearch.StartFullSearch();

  ColPartition *part;

  while ((part = gsearch.NextFullSearch()) != nullptr) {

    if (MergePart(box_cb, confirm_cb, part)) {

      gsearch.RepositionIterator();

    }

  }

}

// For the given partition, calls the box_cb permanent callback

// to compute the search box, searches the box, and if a candidate is found,

// calls the confirm_cb to check any more rules. If the confirm_cb returns

// true, then the partitions are merged.

// Returns true if the partition is consumed by one or more merges.

bool ColPartitionGrid::MergePart(

    const std::function<bool(ColPartition *, TBOX *)> &box_cb,

    const std::function<bool(const ColPartition *, const ColPartition *)>

        &confirm_cb,

    ColPartition *part) {

  if (part->IsUnMergeableType()) {

    return false;

  }

  bool any_done = false;

  // Repeatedly merge part while we find a best merge candidate that works.

  bool merge_done = false;

  do {

    merge_done = false;

    TBOX box = part->bounding_box();

    bool debug = AlignedBlob::WithinTestRegion(2, box.left(), box.bottom());

    if (debug) {

      tprintf("Merge candidate:");

      box.print();

    }

    // Set up a rectangle search bounded by the part.

    if (!box_cb(part, &box)) {

      continue;

    }

    // Create a list of merge candidates.

    ColPartition_CLIST merge_candidates;

    FindMergeCandidates(part, box, debug, &merge_candidates);

    // Find the best merge candidate based on minimal overlap increase.

    int overlap_increase;

    ColPartition *neighbour = BestMergeCandidate(part, &merge_candidates, debug,

                                                 confirm_cb, &overlap_increase);

    if (neighbour != nullptr && overlap_increase <= 0) {

      if (debug) {

        tprintf("Merging:hoverlap=%d, voverlap=%d, OLI=%d\n",

                part->HCoreOverlap(*neighbour), part->VCoreOverlap(*neighbour),

                overlap_increase);

      }

      // Looks like a good candidate so merge it.

      RemoveBBox(neighbour);

      // We will modify the box of part, so remove it from the grid, merge

      // it and then re-insert it into the grid.

      RemoveBBox(part);

      part->Absorb(neighbour, nullptr);

      InsertBBox(true, true, part);

      merge_done = true;

      any_done = true;

    } else if (neighbour != nullptr) {

      if (debug) {

        tprintf("Overlapped when merged with increase %d: ", overlap_increase);

        neighbour->bounding_box().print();

      }

    } else if (debug) {

      tprintf("No candidate neighbour returned\n");

    }

  } while (merge_done);

  return any_done;

}

// Returns true if the given part and merge candidate might believably

// be part of a single text line according to the default rules.

// In general we only want to merge partitions that look like they

// are on the same text line, ie their median limits overlap, but we have

// to make exceptions for diacritics and stray punctuation.

static bool OKMergeCandidate(const ColPartition *part,

                             const ColPartition *candidate, bool debug) {

  const TBOX &part_box = part->bounding_box();

  if (candidate == part) {

    return false; // Ignore itself.

  }

  if (!part->TypesMatch(*candidate) || candidate->IsUnMergeableType()) {

    return false; // Don't mix inappropriate types.

  }

  const TBOX &c_box = candidate->bounding_box();

  if (debug) {

    tprintf("Examining merge candidate:");

    c_box.print();

  }

  // Candidates must be within a reasonable distance.

  if (candidate->IsVerticalType() || part->IsVerticalType()) {

    int h_dist = -part->HCoreOverlap(*candidate);

    if (h_dist >= std::max(part_box.width(), c_box.width()) / 2) {

      if (debug) {

        tprintf("Too far away: h_dist = %d\n", h_dist);

      }

      return false;

    }

  } else {

    // Coarse filter by vertical distance between partitions.

    int v_dist = -part->VCoreOverlap(*candidate);

    if (v_dist >= std::max(part_box.height(), c_box.height()) / 2) {

      if (debug) {

        tprintf("Too far away: v_dist = %d\n", v_dist);

      }

      return false;

    }

    // Candidates must either overlap in median y,

    // or part or candidate must be an acceptable diacritic.

    if (!part->VSignificantCoreOverlap(*candidate) &&

        !part->OKDiacriticMerge(*candidate, debug) &&

        !candidate->OKDiacriticMerge(*part, debug)) {

      if (debug) {

        tprintf("Candidate fails overlap and diacritic tests!\n");

      }

      return false;

    }

  }

  return true;

}

// Helper function to compute the increase in overlap of the parts list of

// Colpartitions with the combination of merge1 and merge2, compared to

// the overlap with them uncombined.

// An overlap is not counted if passes the OKMergeOverlap test with ok_overlap

// as the pixel overlap limit. merge1 and merge2 must both be non-nullptr.

static int IncreaseInOverlap(const ColPartition *merge1,

                             const ColPartition *merge2, int ok_overlap,

                             ColPartition_CLIST *parts) {

  ASSERT_HOST(merge1 != nullptr && merge2 != nullptr);

  int total_area = 0;

  ColPartition_C_IT it(parts);

  TBOX merged_box(merge1->bounding_box());

  merged_box += merge2->bounding_box();

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

    ColPartition *part = it.data();

    if (part == merge1 || part == merge2) {

      continue;

    }

    TBOX part_box = part->bounding_box();

    // Compute the overlap of the merged box with part.

    int overlap_area = part_box.intersection(merged_box).area();

    if (overlap_area > 0 &&

        !part->OKMergeOverlap(*merge1, *merge2, ok_overlap, false)) {

      total_area += overlap_area;

      // Subtract the overlap of merge1 and merge2 individually.

      overlap_area = part_box.intersection(merge1->bounding_box()).area();

      if (overlap_area > 0) {

        total_area -= overlap_area;

      }

      TBOX intersection_box = part_box.intersection(merge2->bounding_box());

      overlap_area = intersection_box.area();

      if (overlap_area > 0) {

        total_area -= overlap_area;

        // Add back the 3-way area.

        intersection_box &= merge1->bounding_box(); // In-place intersection.

        overlap_area = intersection_box.area();

        if (overlap_area > 0) {

          total_area += overlap_area;

        }

      }

    }

  }

  return total_area;

}

// Helper function to test that each partition in candidates is either a

// good diacritic merge with part or an OK merge candidate with all others

// in the candidates list.

// ASCII Art Scenario:

// We sometimes get text such as "join-this" where the - is actually a long

// dash culled from a standard set of extra characters that don't match the

// font of the text. This makes its strokewidth not match and forms a broken

// set of 3 partitions for "join", "-" and "this" and the dash may slightly

// overlap BOTH words.

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

// |     ====     |

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

// The standard merge rule: "you can merge 2 partitions as long as there is

// no increase in overlap elsewhere" fails miserably here. Merge any pair

// of partitions and the combined box overlaps more with the third than

// before. To allow the merge, we need to consider whether it is safe to

// merge everything, without merging separate text lines. For that we need

// everything to be an OKMergeCandidate (which is supposed to prevent

// separate text lines merging), but this is hard for diacritics to satisfy,

// so an alternative to being OKMergeCandidate with everything is to be an

// OKDiacriticMerge with part as the base character.

static bool TestCompatibleCandidates(const ColPartition &part, bool debug,

                                     ColPartition_CLIST *candidates) {

  ColPartition_C_IT it(candidates);

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

    ColPartition *candidate = it.data();

    if (!candidate->OKDiacriticMerge(part, false)) {

      ColPartition_C_IT it2(it);

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

        ColPartition *candidate2 = it2.data();

        if (candidate2 != candidate &&

            !OKMergeCandidate(candidate, candidate2, false)) {

          if (debug) {

            tprintf("NC overlap failed:Candidate:");

            candidate2->bounding_box().print();

            tprintf("fails to be a good merge with:");

            candidate->bounding_box().print();

          }

          return false;

        }

      }

    }

  }

  return true;

}

// Computes and returns the total overlap of all partitions in the grid.

// If overlap_grid is non-null, it is filled with a grid that holds empty

// partitions representing the union of all overlapped partitions.

int ColPartitionGrid::ComputeTotalOverlap(ColPartitionGrid **overlap_grid) {

  int total_overlap = 0;

  // Iterate the ColPartitions in the grid.

  ColPartitionGridSearch gsearch(this);

  gsearch.StartFullSearch();

  ColPartition *part;

  while ((part = gsearch.NextFullSearch()) != nullptr) {

    ColPartition_CLIST neighbors;

    const TBOX &part_box = part->bounding_box();

    FindOverlappingPartitions(part_box, part, &neighbors);

    ColPartition_C_IT n_it(&neighbors);

    bool any_part_overlap = false;

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

      const TBOX &n_box = n_it.data()->bounding_box();

      int overlap = n_box.intersection(part_box).area();

      if (overlap > 0 && overlap_grid != nullptr) {

        if (*overlap_grid == nullptr) {

          *overlap_grid = new ColPartitionGrid(gridsize(), bleft(), tright());

        }

        (*overlap_grid)->InsertBBox(true, true, n_it.data()->ShallowCopy());

        if (!any_part_overlap) {

          (*overlap_grid)->InsertBBox(true, true, part->ShallowCopy());

        }

      }

      any_part_overlap = true;

      total_overlap += overlap;

    }

  }

  return total_overlap;

}

// Finds all the ColPartitions in the grid that overlap with the given

// box and returns them SortByBoxLeft(ed) and uniqued in the given list.

// Any partition equal to not_this (may be nullptr) is excluded.

void ColPartitionGrid::FindOverlappingPartitions(const TBOX &box,

                                                 const ColPartition *not_this,

                                                 ColPartition_CLIST *parts) {

  ColPartitionGridSearch rsearch(this);

  rsearch.StartRectSearch(box);

  ColPartition *part;

  while ((part = rsearch.NextRectSearch()) != nullptr) {

    if (part != not_this) {

      parts->add_sorted(SortByBoxLeft<ColPartition>, true, part);

    }

  }

}

// Finds and returns the best candidate ColPartition to merge with part,

// selected from the candidates list, based on the minimum increase in

// pairwise overlap among all the partitions overlapped by the combined box.

// If overlap_increase is not nullptr then it returns the increase in overlap

// that would result from the merge.

// confirm_cb is a permanent callback that (if non-null) will be used to

// confirm the validity of a proposed merge candidate before selecting it.

//

// ======HOW MERGING WORKS======

// The problem:

// We want to merge all the parts of a textline together, but avoid merging

// separate textlines. Diacritics, i dots, punctuation, and broken characters

// are examples of small bits that need merging with the main textline.

// Drop-caps and descenders in one line that touch ascenders in the one below

// are examples of cases where we don't want to merge.

//

// The solution:

// Merges that increase overlap among other partitions are generally bad.

// Those that don't increase overlap (much) and minimize the total area

// seem to be good.

//

// Ascii art example:

// The text:

// groggy descenders

// minimum ascenders

// The boxes: The === represents a small box near or overlapping the lower box.

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

// |               |

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

// -===-------------

// |               |

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

// In considering what to do with the small === box, we find the 2 larger

// boxes as neighbours and possible merge candidates, but merging with the

// upper box increases overlap with the lower box, whereas merging with the

// lower box does not increase overlap.

// If the small === box didn't overlap either to start with, total area

// would be minimized by merging with the nearer (lower) box.

//

// This is a simple example. In reality, we have to allow some increase

// in overlap, or tightly spaced text would end up in bits.

ColPartition *ColPartitionGrid::BestMergeCandidate(

    const ColPartition *part, ColPartition_CLIST *candidates, bool debug,

    const std::function<bool(const ColPartition *, const ColPartition *)>

        &confirm_cb,

    int *overlap_increase) {

  if (overlap_increase != nullptr) {

    *overlap_increase = 0;

  }

  if (candidates->empty()) {

    return nullptr;

  }

  int ok_overlap =

      static_cast<int>(kTinyEnoughTextlineOverlapFraction * gridsize() + 0.5);

  // The best neighbour to merge with is the one that causes least

  // total pairwise overlap among all the neighbours.

  // If more than one offers the same total overlap, choose the one

  // with the least total area.

  const TBOX &part_box = part->bounding_box();

  ColPartition_C_IT it(candidates);

  ColPartition *best_candidate = nullptr;

  // Find the total combined box of all candidates and the original.

  TBOX full_box(part_box);

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

    ColPartition *candidate = it.data();

    full_box += candidate->bounding_box();

  }

  // Keep valid neighbours in a list.

  ColPartition_CLIST neighbours;

  // Now run a rect search of the merged box for overlapping neighbours, as

  // we need anything that might be overlapped by the merged box.

  FindOverlappingPartitions(full_box, part, &neighbours);

  if (debug) {

    tprintf("Finding best merge candidate from %d, %d neighbours for box:",

            candidates->length(), neighbours.length());

    part_box.print();

  }

  // If the best increase in overlap is positive, then we also check the

  // worst non-candidate overlap. This catches the case of multiple good

  // candidates that overlap each other when merged. If the worst

  // non-candidate overlap is better than the best overlap, then return

  // the worst non-candidate overlap instead.

  ColPartition_CLIST non_candidate_neighbours;

  non_candidate_neighbours.set_subtract(SortByBoxLeft<ColPartition>, true,

                                        &neighbours, candidates);

  int worst_nc_increase = 0;

  int best_increase = INT32_MAX;

  int best_area = 0;

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

    ColPartition *candidate = it.data();

    if (confirm_cb != nullptr && !confirm_cb(part, candidate)) {

      if (debug) {

        tprintf("Candidate not confirmed:");

        candidate->bounding_box().print();

      }

      continue;

    }

    int increase = IncreaseInOverlap(part, candidate, ok_overlap, &neighbours);

    const TBOX &cand_box = candidate->bounding_box();

    if (best_candidate == nullptr || increase < best_increase) {

      best_candidate = candidate;

      best_increase = increase;

      best_area = cand_box.bounding_union(part_box).area() - cand_box.area();

      if (debug) {

        tprintf("New best merge candidate has increase %d, area %d, over box:",

                increase, best_area);

        full_box.print();

        candidate->Print();

      }

    } else if (increase == best_increase) {

      int area = cand_box.bounding_union(part_box).area() - cand_box.area();

      if (area < best_area) {

        best_area = area;

        best_candidate = candidate;

      }

    }

    increase = IncreaseInOverlap(part, candidate, ok_overlap,

                                 &non_candidate_neighbours);

    if (increase > worst_nc_increase) {

      worst_nc_increase = increase;

    }

  }

  if (best_increase > 0) {

    // If the worst non-candidate increase is less than the best increase

    // including the candidates, then all the candidates can merge together

    // and the increase in outside overlap would be less, so use that result,

    // but only if each candidate is either a good diacritic merge with part,

    // or an ok merge candidate with all the others.

    // See TestCompatibleCandidates for more explanation and a picture.

    if (worst_nc_increase < best_increase &&

        TestCompatibleCandidates(*part, debug, candidates)) {

      best_increase = worst_nc_increase;

    }

  }

  if (overlap_increase != nullptr) {

    *overlap_increase = best_increase;

  }

  return best_candidate;

}

// Helper to remove the given box from the given partition, put it in its

// own partition, and add to the partition list.

static void RemoveBadBox(BLOBNBOX *box, ColPartition *part,

                         ColPartition_LIST *part_list) {

  part->RemoveBox(box);

  ColPartition::MakeBigPartition(box, part_list);

}

// Split partitions where it reduces overlap between their bounding boxes.

// ColPartitions are after all supposed to be a partitioning of the blobs

// AND of the space on the page!

// Blobs that cause overlaps get removed, put in individual partitions

// and added to the big_parts list. They are most likely characters on

// 2 textlines that touch, or something big like a dropcap.

void ColPartitionGrid::SplitOverlappingPartitions(

    ColPartition_LIST *big_parts) {

  int ok_overlap =

      static_cast<int>(kTinyEnoughTextlineOverlapFraction * gridsize() + 0.5);

  // Iterate the ColPartitions in the grid.

  ColPartitionGridSearch gsearch(this);

  gsearch.StartFullSearch();

  ColPartition *part;

  while ((part = gsearch.NextFullSearch()) != nullptr) {

    // Set up a rectangle search bounded by the part.

    const TBOX &box = part->bounding_box();

    ColPartitionGridSearch rsearch(this);

    rsearch.SetUniqueMode(true);

    rsearch.StartRectSearch(box);

    int unresolved_overlaps = 0;

    ColPartition *neighbour;

    while ((neighbour = rsearch.NextRectSearch()) != nullptr) {

      if (neighbour == part) {

        continue;

      }

      const TBOX &neighbour_box = neighbour->bounding_box();

      if (neighbour->OKMergeOverlap(*part, *part, ok_overlap, false) &&

          part->OKMergeOverlap(*neighbour, *neighbour, ok_overlap, false)) {

        continue; // The overlap is OK both ways.

      }

      // If removal of the biggest box from either partition eliminates the

      // overlap, and it is much bigger than the box left behind, then

      // it is either a drop-cap, an inter-line join, or some junk that

      // we don't want anyway, so put it in the big_parts list.

      if (!part->IsSingleton()) {

        BLOBNBOX *excluded = part->BiggestBox();

        TBOX shrunken = part->BoundsWithoutBox(excluded);

        if (!shrunken.overlap(neighbour_box) &&

            excluded->bounding_box().height() >

                kBigPartSizeRatio * shrunken.height()) {

          // Removing the biggest box fixes the overlap, so do it!

          gsearch.RemoveBBox();

          RemoveBadBox(excluded, part, big_parts);

          InsertBBox(true, true, part);

          gsearch.RepositionIterator();

          break;

        }

      } else if (box.contains(neighbour_box)) {

        ++unresolved_overlaps;

        continue; // No amount of splitting will fix it.

      }

      if (!neighbour->IsSingleton()) {

        BLOBNBOX *excluded = neighbour->BiggestBox();

        TBOX shrunken = neighbour->BoundsWithoutBox(excluded);

        if (!shrunken.overlap(box) &&

            excluded->bounding_box().height() >

                kBigPartSizeRatio * shrunken.height()) {

          // Removing the biggest box fixes the overlap, so do it!

          rsearch.RemoveBBox();

          RemoveBadBox(excluded, neighbour, big_parts);

          InsertBBox(true, true, neighbour);

          gsearch.RepositionIterator();

          break;

        }

      }

      int part_overlap_count = part->CountOverlappingBoxes(neighbour_box);

      int neighbour_overlap_count = neighbour->CountOverlappingBoxes(box);

      ColPartition *right_part = nullptr;

      if (neighbour_overlap_count <= part_overlap_count ||

          part->IsSingleton()) {

        // Try to split the neighbour to reduce overlap.

        BLOBNBOX *split_blob = neighbour->OverlapSplitBlob(box);

        if (split_blob != nullptr) {

          rsearch.RemoveBBox();

          right_part = neighbour->SplitAtBlob(split_blob);

          InsertBBox(true, true, neighbour);

          ASSERT_HOST(right_part != nullptr);

        }

      } else {

        // Try to split part to reduce overlap.

        BLOBNBOX *split_blob = part->OverlapSplitBlob(neighbour_box);

        if (split_blob != nullptr) {

          gsearch.RemoveBBox();

          right_part = part->SplitAtBlob(split_blob);

          InsertBBox(true, true, part);

          ASSERT_HOST(right_part != nullptr);

        }

      }

      if (right_part != nullptr) {

        InsertBBox(true, true, right_part);

        gsearch.RepositionIterator();

        rsearch.RepositionIterator();

        break;

      }

    }

    if (unresolved_overlaps > 2 && part->IsSingleton()) {

      // This part is no good so just add to big_parts.

      RemoveBBox(part);

      ColPartition_IT big_it(big_parts);

      part->set_block_owned(true);

      big_it.add_to_end(part);

      gsearch.RepositionIterator();

    }

  }

}

// Filters partitions of source_type by looking at local neighbours.

// Where a majority of neighbours have a text type, the partitions are

// changed to text, where the neighbours have image type, they are changed

// to image, and partitions that have no definite neighbourhood type are

// left unchanged.

// im_box and rerotation are used to map blob coordinates onto the

// nontext_map, which is used to prevent the spread of text neighbourhoods

// into images.

// Returns true if anything was changed.

bool ColPartitionGrid::GridSmoothNeighbours(BlobTextFlowType source_type,

                                            Image nontext_map,

                                            const TBOX &im_box,

                                            const FCOORD &rotation) {

  // Iterate the ColPartitions in the grid.

  ColPartitionGridSearch gsearch(this);

  gsearch.StartFullSearch();

  ColPartition *part;

  bool any_changed = false;

  while ((part = gsearch.NextFullSearch()) != nullptr) {

    if (part->flow() != source_type ||

        BLOBNBOX::IsLineType(part->blob_type())) {

      continue;

    }

    const TBOX &box = part->bounding_box();

    bool debug = AlignedBlob::WithinTestRegion(2, box.left(), box.bottom());

    if (SmoothRegionType(nontext_map, im_box, rotation, debug, part)) {

      any_changed = true;

    }

  }

  return any_changed;

}

// Reflects the grid and its colpartitions in the y-axis, assuming that

// all blob boxes have already been done.

void ColPartitionGrid::ReflectInYAxis() {

  ColPartition_LIST parts;

  ColPartition_IT part_it(&parts);

  // Iterate the ColPartitions in the grid to extract them.

  ColPartitionGridSearch gsearch(this);

  gsearch.StartFullSearch();

  ColPartition *part;

  while ((part = gsearch.NextFullSearch()) != nullptr) {

    part_it.add_after_then_move(part);

  }

  ICOORD bot_left(-tright().x(), bleft().y());

  ICOORD top_right(-bleft().x(), tright().y());

  // Reinitializing the grid with reflected coords also clears all the

  // pointers, so parts will now own the ColPartitions. (Briefly).

  Init(gridsize(), bot_left, top_right);

  for (part_it.move_to_first(); !part_it.empty(); part_it.forward()) {

    part = part_it.extract();

    part->ReflectInYAxis();

    InsertBBox(true, true, part);

  }

}

// Transforms the grid of partitions to the output blocks, putting each

// partition into a separate block. We don't really care about the order,

// as we just want to get as much text as possible without trying to organize

// it into proper blocks or columns.

// TODO(rays) some kind of sort function would be useful and probably better

// than the default here, which is to sort by order of the grid search.

void ColPartitionGrid::ExtractPartitionsAsBlocks(BLOCK_LIST *blocks,

                                                 TO_BLOCK_LIST *to_blocks) {

  TO_BLOCK_IT to_block_it(to_blocks);

  BLOCK_IT block_it(blocks);

  // All partitions will be put on this list and deleted on return.

  ColPartition_LIST parts;

  ColPartition_IT part_it(&parts);

  // Iterate the ColPartitions in the grid to extract them.

  ColPartitionGridSearch gsearch(this);

  gsearch.StartFullSearch();

  ColPartition *part;

  while ((part = gsearch.NextFullSearch()) != nullptr) {

    part_it.add_after_then_move(part);

    // The partition has to be at least vaguely like text.

    BlobRegionType blob_type = part->blob_type();

    if (BLOBNBOX::IsTextType(blob_type) ||

        (blob_type == BRT_UNKNOWN && part->boxes_count() > 1)) {

      PolyBlockType type =

          blob_type == BRT_VERT_TEXT ? PT_VERTICAL_TEXT : PT_FLOWING_TEXT;

      // Get metrics from the row that will be used for the block.

      TBOX box = part->bounding_box();

      int median_width = part->median_width();

      int median_height = part->median_height();

      // Turn the partition into a TO_ROW.

      TO_ROW *row = part->MakeToRow();

      if (row == nullptr) {

        // This partition is dead.

        part->DeleteBoxes();

        continue;

      }

      auto *block = new BLOCK("", true, 0, 0, box.left(), box.bottom(),

                              box.right(), box.top());

      block->pdblk.set_poly_block(new POLY_BLOCK(box, type));

      auto *to_block = new TO_BLOCK(block);

      TO_ROW_IT row_it(to_block->get_rows());

      row_it.add_after_then_move(row);

      // We haven't differentially rotated vertical and horizontal text at

      // this point, so use width or height as appropriate.

      if (blob_type == BRT_VERT_TEXT) {

        to_block->line_size = static_cast<float>(median_width);

        to_block->line_spacing = static_cast<float>(box.width());

        to_block->max_blob_size = static_cast<float>(box.width() + 1);

      } else {

        to_block->line_size = static_cast<float>(median_height);

        to_block->line_spacing = static_cast<float>(box.height());

        to_block->max_blob_size = static_cast<float>(box.height() + 1);

      }

      if (to_block->line_size == 0) {

        to_block->line_size = 1;

      }

      block_it.add_to_end(block);

      to_block_it.add_to_end(to_block);

    } else {

      // This partition is dead.

      part->DeleteBoxes();

    }

  }

  Clear();

  // Now it is safe to delete the ColPartitions as parts goes out of scope.

}

// Rotates the grid and its colpartitions by the given angle, assuming that

// all blob boxes have already been done.

void ColPartitionGrid::Deskew(const FCOORD &deskew) {

  ColPartition_LIST parts;

  ColPartition_IT part_it(&parts);

  // Iterate the ColPartitions in the grid to extract them.

  ColPartitionGridSearch gsearch(this);

  gsearch.StartFullSearch();

  ColPartition *part;

  while ((part = gsearch.NextFullSearch()) != nullptr) {

    part_it.add_after_then_move(part);

  }

  // Rebuild the grid to the new size.

  TBOX grid_box(bleft_, tright_);

  grid_box.rotate_large(deskew);

  Init(gridsize(), grid_box.botleft(), grid_box.topright());

  // Reinitializing the grid with rotated coords also clears all the

  // pointers, so parts will now own the ColPartitions. (Briefly).

  for (part_it.move_to_first(); !part_it.empty(); part_it.forward()) {

    part = part_it.extract();

    part->ComputeLimits();

    InsertBBox(true, true, part);

  }

}

// Sets the left and right tabs of the partitions in the grid.

void ColPartitionGrid::SetTabStops(TabFind *tabgrid) {

  // Iterate the ColPartitions in the grid.

  ColPartitionGridSearch gsearch(this);

  gsearch.StartFullSearch();

  ColPartition *part;

  while ((part = gsearch.NextFullSearch()) != nullptr) {

    const TBOX &part_box = part->bounding_box();

    TabVector *left_line = tabgrid->LeftTabForBox(part_box, true, false);

    // If the overlapping line is not a left tab, try for non-overlapping.

    if (left_line != nullptr && !left_line->IsLeftTab()) {

      left_line = tabgrid->LeftTabForBox(part_box, false, false);

    }

    if (left_line != nullptr && left_line->IsLeftTab()) {

      part->SetLeftTab(left_line);

    }

    TabVector *right_line = tabgrid->RightTabForBox(part_box, true, false);

    if (right_line != nullptr && !right_line->IsRightTab()) {

      right_line = tabgrid->RightTabForBox(part_box, false, false);

    }

    if (right_line != nullptr && right_line->IsRightTab()) {

      part->SetRightTab(right_line);

    }

    part->SetColumnGoodness(tabgrid->WidthCB());

  }

}

// Makes the ColPartSets and puts them in the PartSetVector ready

// for finding column bounds. Returns false if no partitions were found.

bool ColPartitionGrid::MakeColPartSets(PartSetVector *part_sets) {

  auto *part_lists = new ColPartition_LIST[gridheight()];

  part_sets->reserve(gridheight());

  // Iterate the ColPartitions in the grid to get parts onto lists for the

  // y bottom of each.

  ColPartitionGridSearch gsearch(this);

  gsearch.StartFullSearch();

  ColPartition *part;

  bool any_parts_found = false;

  while ((part = gsearch.NextFullSearch()) != nullptr) {

    BlobRegionType blob_type = part->blob_type();

    if (blob_type != BRT_NOISE &&

        (blob_type != BRT_UNKNOWN || !part->boxes()->singleton())) {

      int grid_x, grid_y;

      const TBOX &part_box = part->bounding_box();

      GridCoords(part_box.left(), part_box.bottom(), &grid_x, &grid_y);

      ColPartition_IT part_it(&part_lists[grid_y]);

      part_it.add_to_end(part);

      any_parts_found = true;

    }

  }

  if (any_parts_found) {

    for (int grid_y = 0; grid_y < gridheight(); ++grid_y) {

      ColPartitionSet *line_set = nullptr;

      if (!part_lists[grid_y].empty()) {

        line_set = new ColPartitionSet(&part_lists[grid_y]);

      }

      part_sets->push_back(line_set);

    }

  }

  delete[] part_lists;

  return any_parts_found;

}

// Makes a single ColPartitionSet consisting of a single ColPartition that

// represents the total horizontal extent of the significant content on the

// page. Used for the single column setting in place of automatic detection.

// Returns nullptr if the page is empty of significant content.

ColPartitionSet *ColPartitionGrid::MakeSingleColumnSet(WidthCallback cb) {

  ColPartition *single_column_part = nullptr;

  // Iterate the ColPartitions in the grid to get parts onto lists for the

  // y bottom of each.

  ColPartitionGridSearch gsearch(this);

  gsearch.StartFullSearch();

  ColPartition *part;

  while ((part = gsearch.NextFullSearch()) != nullptr) {

    BlobRegionType blob_type = part->blob_type();

    if (blob_type != BRT_NOISE &&

        (blob_type != BRT_UNKNOWN || !part->boxes()->singleton())) {

      // Consider for single column.

      BlobTextFlowType flow = part->flow();

      if ((blob_type == BRT_TEXT &&

           (flow == BTFT_STRONG_CHAIN || flow == BTFT_CHAIN ||

            flow == BTFT_LEADER || flow == BTFT_TEXT_ON_IMAGE)) ||

          blob_type == BRT_RECTIMAGE || blob_type == BRT_POLYIMAGE) {

        if (single_column_part == nullptr) {

          single_column_part = part->ShallowCopy();

          single_column_part->set_blob_type(BRT_TEXT);

          // Copy the tabs from itself to properly setup the margins.

          single_column_part->CopyLeftTab(*single_column_part, false);

          single_column_part->CopyRightTab(*single_column_part, false);

        } else {

          if (part->left_key() < single_column_part->left_key()) {

            single_column_part->CopyLeftTab(*part, false);

          }

          if (part->right_key() > single_column_part->right_key()) {

            single_column_part->CopyRightTab(*part, false);

          }

        }

      }

    }

  }

  if (single_column_part != nullptr) {

    // Make a ColPartitionSet out of the single_column_part as a candidate

    // for the single column case.

    single_column_part->SetColumnGoodness(cb);

    return new ColPartitionSet(single_column_part);

  }

  return nullptr;

}

// Mark the BLOBNBOXes in each partition as being owned by that partition.

void ColPartitionGrid::ClaimBoxes() {

  // Iterate the ColPartitions in the grid.

  ColPartitionGridSearch gsearch(this);

  gsearch.StartFullSearch();

  ColPartition *part;

  while ((part = gsearch.NextFullSearch()) != nullptr) {

    part->ClaimBoxes();

  }

}

// Retypes all the blobs referenced by the partitions in the grid.

// Image blobs are found and returned in the im_blobs list, as they are not

// owned by the block.

void ColPartitionGrid::ReTypeBlobs(BLOBNBOX_LIST *im_blobs) {

  BLOBNBOX_IT im_blob_it(im_blobs);