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

// File:        tablerecog.cpp

// Description: Helper class to help structure table areas. Given an bounding

//              box from TableFinder, the TableRecognizer should give a

//              StructuredTable (maybe a list in the future) of "good" tables

//              in that area.

// Author:      Nicholas Beato

//

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

#include <algorithm>

namespace tesseract {

// The amount of space required between the ColPartitions in 2 columns

// of a non-lined table as a multiple of the median width.

const double kHorizontalSpacing = 0.30;

// The amount of space required between the ColPartitions in 2 rows

// of a non-lined table as multiples of the median height.

const double kVerticalSpacing = -0.2;

// The number of cells that the grid lines may intersect.

// See FindCellSplitLocations for explanation.

const int kCellSplitRowThreshold = 0;

const int kCellSplitColumnThreshold = 0;

// For "lined tables", the number of required lines. Currently a guess.

const int kLinedTableMinVerticalLines = 3;

const int kLinedTableMinHorizontalLines = 3;

// Number of columns required, as a fraction of the most columns found.

// None of these are tweaked at all.

const double kRequiredColumns = 0.7;

// The tolerance for comparing margins of potential tables.

const double kMarginFactor = 1.1;

// The first and last row should be consistent cell height.

// This factor is the first and last row cell height max.

const double kMaxRowSize = 2.5;

// Number of filled columns required to form a strong table row.

// For small tables, this is an absolute number.

const double kGoodRowNumberOfColumnsSmall[] = {2, 2, 2, 2, 2, 3, 3};

// For large tables, it is a relative number

const double kGoodRowNumberOfColumnsLarge = 0.7;

// The amount of area that must be covered in a cell by ColPartitions to

// be considered "filled"

const double kMinFilledArea = 0.35;

// Indicates that a table row is weak. This means that it has

// many missing data cells or very large cell heights compared.

// to the rest of the table.

// Code is buggy right now. It is disabled in the calling function.

// It seems like sometimes the row that is passed in is not correct

// sometimes (like a phantom row is introduced). There's something going

// on in the cell_y_ data member before this is called... not certain.

static bool IsWeakTableRow(StructuredTable *table, int row) {

  if (!table->VerifyRowFilled(row)) {

    return false;

  }

  double threshold;

  if (table->column_count() < countof(kGoodRowNumberOfColumnsSmall)) {

    threshold = kGoodRowNumberOfColumnsSmall[table->column_count()];

  } else {

    threshold = table->column_count() * kGoodRowNumberOfColumnsLarge;

  }

  return table->CountFilledCellsInRow(row) < threshold;

}

////////

//////// StructuredTable Class

////////

StructuredTable::StructuredTable()

    : text_grid_(nullptr)

    , line_grid_(nullptr)

    , is_lined_(false)

    , space_above_(0)

    , space_below_(0)

    , space_left_(0)

    , space_right_(0)

    , median_cell_height_(0)

    , median_cell_width_(0)

    , max_text_height_(INT32_MAX) {}

void StructuredTable::Init() {}

void StructuredTable::set_text_grid(ColPartitionGrid *text_grid) {

  text_grid_ = text_grid;

}

void StructuredTable::set_line_grid(ColPartitionGrid *line_grid) {

  line_grid_ = line_grid;

}

void StructuredTable::set_max_text_height(int height) {

  max_text_height_ = height;

}

bool StructuredTable::is_lined() const {

  return is_lined_;

}

unsigned StructuredTable::row_count() const {

  return cell_y_.empty() ? 0 : cell_y_.size() - 1;

}

unsigned StructuredTable::column_count() const {

  return cell_x_.empty() ? 0 : cell_x_.size() - 1;

}

unsigned StructuredTable::cell_count() const {

  return row_count() * column_count();

}

void StructuredTable::set_bounding_box(const TBOX &box) {

  bounding_box_ = box;

}

const TBOX &StructuredTable::bounding_box() const {

  return bounding_box_;

}

int StructuredTable::median_cell_height() {

  return median_cell_height_;

}

int StructuredTable::median_cell_width() {

  return median_cell_width_;

}

int StructuredTable::row_height(unsigned row) const {

  ASSERT_HOST(row < row_count());

  return cell_y_[row + 1] - cell_y_[row];

}

int StructuredTable::column_width(unsigned column) const {

  ASSERT_HOST(column < column_count());

  return cell_x_[column + 1] - cell_x_[column];

}

int StructuredTable::space_above() const {

  return space_above_;

}

int StructuredTable::space_below() const {

  return space_below_;

}

// At this point, we know that the lines are contained

// by the box (by FindLinesBoundingBox).

// So try to find the cell structure and make sure it works out.

// The assumption is that all lines span the table. If this

// assumption fails, the VerifyLinedTable method will

// abort the lined table. The TableRecognizer will fall

// back on FindWhitespacedStructure.

bool StructuredTable::FindLinedStructure() {

  ClearStructure();

  // Search for all of the lines in the current box.

  // Update the cellular structure with the exact lines.

  ColPartitionGridSearch box_search(line_grid_);

  box_search.SetUniqueMode(true);

  box_search.StartRectSearch(bounding_box_);

  ColPartition *line = nullptr;

  while ((line = box_search.NextRectSearch()) != nullptr) {

    if (line->IsHorizontalLine()) {

      cell_y_.push_back(line->MidY());

    }

    if (line->IsVerticalLine()) {

      cell_x_.push_back(line->MidX());

    }

  }

  // HasSignificantLines should guarantee cells.

  // Because that code is a different class, just gracefully

  // return false. This could be an assert.

  if (cell_x_.size() < 3 || cell_y_.size() < 3) {

    return false;

  }

  // Sort and remove duplicates that may have occurred due to split lines.

  std::sort(cell_x_.begin(), cell_x_.end());

  auto last_x = std::unique(cell_x_.begin(), cell_x_.end());

  cell_x_.erase(last_x, cell_x_.end());

  std::sort(cell_y_.begin(), cell_y_.end());

  auto last_y = std::unique(cell_y_.begin(), cell_y_.end());

  cell_y_.erase(last_y, cell_y_.end());

  // The border should be the extents of line boxes, not middle.

  cell_x_[0] = bounding_box_.left();

  cell_x_[cell_x_.size() - 1] = bounding_box_.right();

  cell_y_[0] = bounding_box_.bottom();

  cell_y_[cell_y_.size() - 1] = bounding_box_.top();

  // Remove duplicates that may have occurred due to moving the borders.

  last_x = std::unique(cell_x_.begin(), cell_x_.end());

  cell_x_.erase(last_x, cell_x_.end());

  last_y = std::unique(cell_y_.begin(), cell_y_.end());

  cell_y_.erase(last_y, cell_y_.end());

  CalculateMargins();

  CalculateStats();

  is_lined_ = VerifyLinedTableCells();

  return is_lined_;

}

// Finds the cellular structure given a particular box.

bool StructuredTable::FindWhitespacedStructure() {

  ClearStructure();

  FindWhitespacedColumns();

  FindWhitespacedRows();

  if (!VerifyWhitespacedTable()) {

    return false;

  } else {

    bounding_box_.set_left(cell_x_[0]);

    bounding_box_.set_right(cell_x_[cell_x_.size() - 1]);

    bounding_box_.set_bottom(cell_y_[0]);

    bounding_box_.set_top(cell_y_[cell_y_.size() - 1]);

    AbsorbNearbyLines();

    CalculateMargins();

    CalculateStats();

    return true;

  }

}

// Tests if a partition fits inside the table structure.

// Partitions must fully span a grid line in order to intersect it.

// This means that a partition does not intersect a line

// that it "just" touches. This is mainly because the assumption

// throughout the code is that "0" distance is a very very small space.

bool StructuredTable::DoesPartitionFit(const ColPartition &part) const {

  const TBOX &box = part.bounding_box();

  for (int i : cell_x_) {

    if (box.left() < i && i < box.right()) {

      return false;

    }

  }

  for (int i : cell_y_) {

    if (box.bottom() < i && i < box.top()) {

      return false;

    }

  }

  return true;

}

// Checks if a sub-table has multiple data cells filled.

int StructuredTable::CountFilledCells() {

  return CountFilledCells(0, row_count() - 1, 0, column_count() - 1);

}

int StructuredTable::CountFilledCellsInRow(int row) {

  return CountFilledCells(row, row, 0, column_count() - 1);

}

int StructuredTable::CountFilledCellsInColumn(int column) {

  return CountFilledCells(0, row_count() - 1, column, column);

}

int StructuredTable::CountFilledCells(unsigned row_start, unsigned row_end, unsigned column_start,

                                      unsigned column_end) {

  ASSERT_HOST(row_start <= row_end && row_end < row_count());

  ASSERT_HOST(column_start <= column_end && column_end < column_count());

  int cell_count = 0;

  TBOX cell_box;

  for (unsigned row = row_start; row <= row_end; ++row) {

    cell_box.set_bottom(cell_y_[row]);

    cell_box.set_top(cell_y_[row + 1]);

    for (unsigned col = column_start; col <= column_end; ++col) {

      cell_box.set_left(cell_x_[col]);

      cell_box.set_right(cell_x_[col + 1]);

      if (CountPartitions(cell_box) > 0) {

        ++cell_count;

      }

    }

  }

  return cell_count;

}

// Makes sure that at least one cell in a row has substantial area filled.

// This can filter out large whitespace caused by growing tables too far

// and page numbers.

bool StructuredTable::VerifyRowFilled(int row) {

  for (unsigned i = 0; i < column_count(); ++i) {

    auto area_filled = CalculateCellFilledPercentage(row, i);

    if (area_filled >= kMinFilledArea) {

      return true;

    }

  }

  return false;

}

// Finds the filled area in a cell.

// Assume ColPartitions do not overlap for simplicity (even though they do).

double StructuredTable::CalculateCellFilledPercentage(unsigned row, unsigned column) {

  ASSERT_HOST(row <= row_count());

  ASSERT_HOST(column <= column_count());

  const TBOX kCellBox(cell_x_[column], cell_y_[row], cell_x_[column + 1], cell_y_[row + 1]);

  ASSERT_HOST(!kCellBox.null_box());

  ColPartitionGridSearch gsearch(text_grid_);

  gsearch.SetUniqueMode(true);

  gsearch.StartRectSearch(kCellBox);

  double area_covered = 0;

  ColPartition *text = nullptr;

  while ((text = gsearch.NextRectSearch()) != nullptr) {

    if (text->IsTextType()) {

      area_covered += text->bounding_box().intersection(kCellBox).area();

    }

  }

  const int32_t current_area = kCellBox.area();

  if (current_area == 0) {

    return 1.0;

  }

  return std::min(1.0, area_covered / current_area);

}

#ifndef GRAPHICS_DISABLED

void StructuredTable::Display(ScrollView *window, ScrollView::Color color) {

  window->Brush(ScrollView::NONE);

  window->Pen(color);

  window->Rectangle(bounding_box_.left(), bounding_box_.bottom(), bounding_box_.right(),

                    bounding_box_.top());

  for (int i : cell_x_) {

    window->Line(i, bounding_box_.bottom(), i, bounding_box_.top());

  }

  for (int i : cell_y_) {

    window->Line(bounding_box_.left(), i, bounding_box_.right(), i);

  }

  window->UpdateWindow();

}

#endif

// Clear structure information.

void StructuredTable::ClearStructure() {

  cell_x_.clear();

  cell_y_.clear();

  is_lined_ = false;

  space_above_ = 0;

  space_below_ = 0;

  space_left_ = 0;

  space_right_ = 0;

  median_cell_height_ = 0;

  median_cell_width_ = 0;

}

// When a table has lines, the lines should not intersect any partitions.

// The following function makes sure the previous assumption is met.

bool StructuredTable::VerifyLinedTableCells() {

  // Function only called when lines exist.

  ASSERT_HOST(cell_y_.size() >= 2 && cell_x_.size() >= 2);

  for (int i : cell_y_) {

    if (CountHorizontalIntersections(i) > 0) {

      return false;

    }

  }

  for (int i : cell_x_) {

    if (CountVerticalIntersections(i) > 0) {

      return false;

    }

  }

  return true;

}

// TODO(nbeato): Could be much better than this.

// Examples:

//   - Calculate the percentage of filled cells.

//   - Calculate the average number of ColPartitions per cell.

//   - Calculate the number of cells per row with partitions.

//   - Check if ColPartitions in adjacent cells are similar.

//   - Check that all columns are at least a certain width.

//   - etc.

bool StructuredTable::VerifyWhitespacedTable() {

  // criteria for a table, must be at least 2x3 or 3x2

  return row_count() >= 2 && column_count() >= 2 && cell_count() >= 6;

}

// Finds vertical splits in the ColPartitions of text_grid_ by considering

// all possible "good" guesses. A good guess is just the left/right sides of

// the partitions, since these locations will uniquely define where the

// extremal values where the splits can occur. The split happens

// in the middle of the two nearest partitions.

void StructuredTable::FindWhitespacedColumns() {

  // Set of the extents of all partitions on the page.

  std::vector<int> left_sides;

  std::vector<int> right_sides;

  // Look at each text partition. We want to find the partitions

  // that have extremal left/right sides. These will give us a basis

  // for the table columns.

  ColPartitionGridSearch gsearch(text_grid_);

  gsearch.SetUniqueMode(true);

  gsearch.StartRectSearch(bounding_box_);

  ColPartition *text = nullptr;

  while ((text = gsearch.NextRectSearch()) != nullptr) {

    if (!text->IsTextType()) {

      continue;

    }

    ASSERT_HOST(text->bounding_box().left() < text->bounding_box().right());

    int spacing = static_cast<int>(text->median_width() * kHorizontalSpacing / 2.0 + 0.5);

    left_sides.push_back(text->bounding_box().left() - spacing);

    right_sides.push_back(text->bounding_box().right() + spacing);

  }

  // It causes disaster below, so avoid it!

  if (left_sides.empty() || right_sides.empty()) {

    return;

  }

  // Since data may be inserted in grid order, we sort the left/right sides.

  std::sort(left_sides.begin(), left_sides.end());

  std::sort(right_sides.begin(), right_sides.end());

  // At this point, in the "merged list", we expect to have a left side,

  // followed by either more left sides or a right side. The last number

  // should be a right side. We find places where the splits occur by looking

  // for "valleys". If we want to force gap sizes or allow overlap, change

  // the spacing above. If you want to let lines "slice" partitions as long

  // as it is infrequent, change the following function.

  FindCellSplitLocations(left_sides, right_sides, kCellSplitColumnThreshold, &cell_x_);

}

// Finds horizontal splits in the ColPartitions of text_grid_ by considering

// all possible "good" guesses. A good guess is just the bottom/top sides of

// the partitions, since these locations will uniquely define where the

// extremal values where the splits can occur. The split happens

// in the middle of the two nearest partitions.

void StructuredTable::FindWhitespacedRows() {

  // Set of the extents of all partitions on the page.

  std::vector<int> bottom_sides;

  std::vector<int> top_sides;

  // We will be "shrinking" partitions, so keep the min/max around to

  // make sure the bottom/top lines do not intersect text.

  int min_bottom = INT32_MAX;

  int max_top = INT32_MIN;

  // Look at each text partition. We want to find the partitions

  // that have extremal bottom/top sides. These will give us a basis

  // for the table rows. Because the textlines can be skewed and close due

  // to warping, the height of the partitions is toned down a little bit.

  ColPartitionGridSearch gsearch(text_grid_);

  gsearch.SetUniqueMode(true);

  gsearch.StartRectSearch(bounding_box_);

  ColPartition *text = nullptr;

  while ((text = gsearch.NextRectSearch()) != nullptr) {

    if (!text->IsTextType()) {

      continue;

    }

    ASSERT_HOST(text->bounding_box().bottom() < text->bounding_box().top());

    min_bottom = std::min(min_bottom, static_cast<int>(text->bounding_box().bottom()));

    max_top = std::max(max_top, static_cast<int>(text->bounding_box().top()));

    // Ignore "tall" text partitions, as these are usually false positive

    // vertical text or multiple lines pulled together.

    if (text->bounding_box().height() > max_text_height_) {

      continue;

    }

    int spacing = static_cast<int>(text->bounding_box().height() * kVerticalSpacing / 2.0 + 0.5);

    int bottom = text->bounding_box().bottom() - spacing;

    int top = text->bounding_box().top() + spacing;

    // For horizontal text, the factor can be negative. This should

    // probably cause a warning or failure. I haven't actually checked if

    // it happens.

    if (bottom >= top) {

      continue;

    }

    bottom_sides.push_back(bottom);

    top_sides.push_back(top);

  }

  // It causes disaster below, so avoid it!

  if (bottom_sides.empty() || top_sides.empty()) {

    return;

  }

  // Since data may be inserted in grid order, we sort the bottom/top sides.

  std::sort(bottom_sides.begin(), bottom_sides.end());

  std::sort(top_sides.begin(), top_sides.end());

  // At this point, in the "merged list", we expect to have a bottom side,

  // followed by either more bottom sides or a top side. The last number

  // should be a top side. We find places where the splits occur by looking

  // for "valleys". If we want to force gap sizes or allow overlap, change

  // the spacing above. If you want to let lines "slice" partitions as long

  // as it is infrequent, change the following function.

  FindCellSplitLocations(bottom_sides, top_sides, kCellSplitRowThreshold, &cell_y_);

  // Recover the min/max correctly since it was shifted.

  cell_y_[0] = min_bottom;

  cell_y_[cell_y_.size() - 1] = max_top;

}

void StructuredTable::CalculateMargins() {

  space_above_ = INT32_MAX;

  space_below_ = INT32_MAX;

  space_right_ = INT32_MAX;

  space_left_ = INT32_MAX;

  UpdateMargins(text_grid_);

  UpdateMargins(line_grid_);

}

// Finds the nearest partition in grid to the table

// boundaries and updates the margin.

void StructuredTable::UpdateMargins(ColPartitionGrid *grid) {

  int below = FindVerticalMargin(grid, bounding_box_.bottom(), true);

  space_below_ = std::min(space_below_, below);

  int above = FindVerticalMargin(grid, bounding_box_.top(), false);

  space_above_ = std::min(space_above_, above);

  int left = FindHorizontalMargin(grid, bounding_box_.left(), true);

  space_left_ = std::min(space_left_, left);

  int right = FindHorizontalMargin(grid, bounding_box_.right(), false);

  space_right_ = std::min(space_right_, right);

}

int StructuredTable::FindVerticalMargin(ColPartitionGrid *grid, int border, bool decrease) const {

  ColPartitionGridSearch gsearch(grid);

  gsearch.SetUniqueMode(true);

  gsearch.StartVerticalSearch(bounding_box_.left(), bounding_box_.right(), border);

  ColPartition *part = nullptr;

  while ((part = gsearch.NextVerticalSearch(decrease)) != nullptr) {

    if (!part->IsTextType() && !part->IsHorizontalLine()) {

      continue;

    }

    int distance =

        decrease ? border - part->bounding_box().top() : part->bounding_box().bottom() - border;

    if (distance >= 0) {

      return distance;

    }

  }

  return INT32_MAX;

}

int StructuredTable::FindHorizontalMargin(ColPartitionGrid *grid, int border, bool decrease) const {

  ColPartitionGridSearch gsearch(grid);

  gsearch.SetUniqueMode(true);

  gsearch.StartSideSearch(border, bounding_box_.bottom(), bounding_box_.top());

  ColPartition *part = nullptr;

  while ((part = gsearch.NextSideSearch(decrease)) != nullptr) {

    if (!part->IsTextType() && !part->IsVerticalLine()) {

      continue;

    }

    int distance =

        decrease ? border - part->bounding_box().right() : part->bounding_box().left() - border;

    if (distance >= 0) {

      return distance;

    }

  }

  return INT32_MAX;

}

void StructuredTable::CalculateStats() {

  const int kMaxCellHeight = 1000;

  const int kMaxCellWidth = 1000;

  STATS height_stats(0, kMaxCellHeight);

  STATS width_stats(0, kMaxCellWidth);

  for (unsigned i = 0; i < row_count(); ++i) {

    height_stats.add(row_height(i), column_count());

  }

  for (unsigned i = 0; i < column_count(); ++i) {

    width_stats.add(column_width(i), row_count());

  }

  median_cell_height_ = static_cast<int>(height_stats.median() + 0.5);

  median_cell_width_ = static_cast<int>(width_stats.median() + 0.5);

}

// Looks for grid lines near the current bounding box and

// grows the bounding box to include them if no intersections

// will occur as a result. This is necessary because the margins

// are calculated relative to the closest line/text. If the

// line isn't absorbed, the margin will be the distance to the line.

void StructuredTable::AbsorbNearbyLines() {

  ColPartitionGridSearch gsearch(line_grid_);

  gsearch.SetUniqueMode(true);

  // Is the closest line above good? Loop multiple times for tables with

  // multi-line (sometimes 2) borders. Limit the number of lines by

  // making sure they stay within a table cell or so.

  ColPartition *line = nullptr;

  gsearch.StartVerticalSearch(bounding_box_.left(), bounding_box_.right(), bounding_box_.top());

  while ((line = gsearch.NextVerticalSearch(false)) != nullptr) {

    if (!line->IsHorizontalLine()) {

      break;

    }

    TBOX text_search(bounding_box_.left(), bounding_box_.top() + 1, bounding_box_.right(),

                     line->MidY());

    if (text_search.height() > median_cell_height_ * 2) {

      break;

    }

    if (CountPartitions(text_search) > 0) {

      break;

    }

    bounding_box_.set_top(line->MidY());

  }

  // As above, is the closest line below good?

  line = nullptr;

  gsearch.StartVerticalSearch(bounding_box_.left(), bounding_box_.right(), bounding_box_.bottom());

  while ((line = gsearch.NextVerticalSearch(true)) != nullptr) {

    if (!line->IsHorizontalLine()) {

      break;

    }

    TBOX text_search(bounding_box_.left(), line->MidY(), bounding_box_.right(),

                     bounding_box_.bottom() - 1);

    if (text_search.height() > median_cell_height_ * 2) {

      break;

    }

    if (CountPartitions(text_search) > 0) {

      break;

    }

    bounding_box_.set_bottom(line->MidY());

  }

  // TODO(nbeato): vertical lines

}

// This function will find all "0 valleys" (of any length) given two

// arrays. The arrays are the mins and maxes of partitions (either

// left and right or bottom and top). Since the min/max lists are generated

// with pairs of increasing integers, we can make some assumptions in

// the function about ordering of the overall list, which are shown in the

// asserts.

// The algorithm works as follows:

//   While there are numbers to process, take the smallest number.

//     If it is from the min_list, increment the "hill" counter.

//     Otherwise, decrement the "hill" counter.

//     In the process of doing this, keep track of "crossing" the

//     desired height.

// The first/last items are extremal values of the list and known.

// NOTE: This function assumes the lists are sorted!

void StructuredTable::FindCellSplitLocations(const std::vector<int> &min_list,

                                             const std::vector<int> &max_list, int max_merged,

                                             std::vector<int> *locations) {

  locations->clear();

  ASSERT_HOST(min_list.size() == max_list.size());

  if (min_list.empty()) {

    return;

  }

  ASSERT_HOST(min_list.at(0) < max_list.at(0));

  ASSERT_HOST(min_list.at(min_list.size() - 1) < max_list.at(max_list.size() - 1));

  locations->push_back(min_list.at(0));

  unsigned min_index = 0;

  unsigned max_index = 0;

  int stacked_partitions = 0;

  int last_cross_position = INT32_MAX;

  // max_index will expire after min_index.

  // However, we can't "increase" the hill size if min_index expired.

  // So finish processing when min_index expires.

  while (min_index < min_list.size()) {

    // Increase the hill count.

    if (min_list[min_index] < max_list[max_index]) {

      ++stacked_partitions;

      if (last_cross_position != INT32_MAX && stacked_partitions > max_merged) {

        int mid = (last_cross_position + min_list[min_index]) / 2;

        locations->push_back(mid);

        last_cross_position = INT32_MAX;

      }

      ++min_index;

    } else {

      // Decrease the hill count.

      --stacked_partitions;

      if (last_cross_position == INT32_MAX && stacked_partitions <= max_merged) {

        last_cross_position = max_list[max_index];

      }

      ++max_index;

    }

  }

  locations->push_back(max_list.at(max_list.size() - 1));

}

// Counts the number of partitions in the table

// box that intersection the given x value.

int StructuredTable::CountVerticalIntersections(int x) {

  int count = 0;

  // Make a small box to keep the search time down.

  const int kGridSize = text_grid_->gridsize();

  TBOX vertical_box = bounding_box_;

  vertical_box.set_left(x - kGridSize);

  vertical_box.set_right(x + kGridSize);

  ColPartitionGridSearch gsearch(text_grid_);

  gsearch.SetUniqueMode(true);

  gsearch.StartRectSearch(vertical_box);

  ColPartition *text = nullptr;

  while ((text = gsearch.NextRectSearch()) != nullptr) {

    if (!text->IsTextType()) {

      continue;

    }

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

    if (box.left() < x && x < box.right()) {

      ++count;

    }

  }

  return count;

}

// Counts the number of partitions in the table

// box that intersection the given y value.

int StructuredTable::CountHorizontalIntersections(int y) {

  int count = 0;

  // Make a small box to keep the search time down.

  const int kGridSize = text_grid_->gridsize();

  TBOX horizontal_box = bounding_box_;

  horizontal_box.set_bottom(y - kGridSize);

  horizontal_box.set_top(y + kGridSize);

  ColPartitionGridSearch gsearch(text_grid_);

  gsearch.SetUniqueMode(true);

  gsearch.StartRectSearch(horizontal_box);

  ColPartition *text = nullptr;

  while ((text = gsearch.NextRectSearch()) != nullptr) {

    if (!text->IsTextType()) {

      continue;

    }

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

    if (box.bottom() < y && y < box.top()) {

      ++count;

    }

  }

  return count;

}

// Counts how many text partitions are in this box.

// This is used to count partitions in cells, as that can indicate

// how "strong" a potential table row/column (or even full table) actually is.

int StructuredTable::CountPartitions(const TBOX &box) {

  ColPartitionGridSearch gsearch(text_grid_);

  gsearch.SetUniqueMode(true);

  gsearch.StartRectSearch(box);

  int count = 0;

  ColPartition *text = nullptr;

  while ((text = gsearch.NextRectSearch()) != nullptr) {

    if (text->IsTextType()) {

      ++count;

    }

  }

  return count;

}

////////

//////// TableRecognizer Class

////////

void TableRecognizer::Init() {}

void TableRecognizer::set_text_grid(ColPartitionGrid *text_grid) {

  text_grid_ = text_grid;

}

void TableRecognizer::set_line_grid(ColPartitionGrid *line_grid) {

  line_grid_ = line_grid;

}

void TableRecognizer::set_min_height(int height) {

  min_height_ = height;

}

void TableRecognizer::set_min_width(int width) {

  min_width_ = width;

}

void TableRecognizer::set_max_text_height(int height) {

  max_text_height_ = height;

}

StructuredTable *TableRecognizer::RecognizeTable(const TBOX &guess) {

  auto *table = new StructuredTable();

  table->Init();

  table->set_text_grid(text_grid_);

  table->set_line_grid(line_grid_);

  table->set_max_text_height(max_text_height_);

  // Try to solve this simple case, a table with *both*

  // vertical and horizontal lines.

  if (RecognizeLinedTable(guess, table)) {

    return table;

  }

  // Fallback to whitespace if that failed.

  // TODO(nbeato): Break this apart to take advantage of horizontal

  // lines or vertical lines when present.

  if (RecognizeWhitespacedTable(guess, table)) {

    return table;

  }

  // No table found...

  delete table;

  return nullptr;

}

bool TableRecognizer::RecognizeLinedTable(const TBOX &guess_box, StructuredTable *table) {

  if (!HasSignificantLines(guess_box)) {

    return false;

  }

  TBOX line_bound = guess_box;

  if (!FindLinesBoundingBox(&line_bound)) {

    return false;

  }

  table->set_bounding_box(line_bound);

  return table->FindLinedStructure();

}

// Quick implementation. Just count the number of lines in the box.

// A better implementation would counter intersections and look for connected

// components. It could even go as far as finding similar length lines.

// To account for these possible issues, the VerifyLinedTableCells function

// will reject lined tables that cause intersections with text on the page.

// TODO(nbeato): look for "better" lines

bool TableRecognizer::HasSignificantLines(const TBOX &guess) {

  ColPartitionGridSearch box_search(line_grid_);

  box_search.SetUniqueMode(true);

  box_search.StartRectSearch(guess);

  ColPartition *line = nullptr;

  int vertical_count = 0;

  int horizontal_count = 0;

  while ((line = box_search.NextRectSearch()) != nullptr) {

    if (line->IsHorizontalLine()) {

      ++horizontal_count;

    }

    if (line->IsVerticalLine()) {

      ++vertical_count;

    }

  }

  return vertical_count >= kLinedTableMinVerticalLines &&

         horizontal_count >= kLinedTableMinHorizontalLines;

}

// Given a bounding box with a bunch of horizontal / vertical lines,

// we just find the extents of all of these lines iteratively.

// The box will be at least as large as guess. This

// could possibly be a bad assumption.

// It is guaranteed to halt in at least O(n * gridarea) where n

// is the number of lines.

// The assumption is that growing the box iteratively will add lines

// several times, but eventually we'll find the extents.

//

// For tables, the approach is a bit aggressive, a single line (which could be

// noise or a column ruling) can destroy the table inside.

//

// TODO(nbeato): This is a quick first implementation.

// A better implementation would actually look for consistency

// in extents of the lines and find the extents using lines

// that clearly describe the table. This would allow the

// lines to "vote" for height/width. An approach like

// this would solve issues with page layout rulings.

// I haven't looked for these issues yet, so I can't even

// say they happen confidently.

bool TableRecognizer::FindLinesBoundingBox(TBOX *bounding_box) {

  // The first iteration will tell us if there are lines

  // present and shrink the box to a minimal iterative size.

  if (!FindLinesBoundingBoxIteration(bounding_box)) {

    return false;

  }

  // Keep growing until the area of the table stabilizes.

  // The box can only get bigger, increasing area.

  bool changed = true;

  while (changed) {

    changed = false;

    int old_area = bounding_box->area();

    bool check = FindLinesBoundingBoxIteration(bounding_box);

    // At this point, the function will return true.

    ASSERT_HOST(check);

    ASSERT_HOST(bounding_box->area() >= old_area);

    changed = (bounding_box->area() > old_area);

  }

  return true;

}

bool TableRecognizer::FindLinesBoundingBoxIteration(TBOX *bounding_box) {

  // Search for all of the lines in the current box, keeping track of extents.

  ColPartitionGridSearch box_search(line_grid_);

  box_search.SetUniqueMode(true);

  box_search.StartRectSearch(*bounding_box);

  ColPartition *line = nullptr;

  bool first_line = true;

  while ((line = box_search.NextRectSearch()) != nullptr) {

    if (line->IsLineType()) {

      if (first_line) {

        // The first iteration can shrink the box.

        *bounding_box = line->bounding_box();

        first_line = false;

      } else {

        *bounding_box += line->bounding_box();

      }

    }

  }

  return !first_line;

}

// The goal of this function is to move the table boundaries around and find

// a table that maximizes the whitespace around the table while maximizing

// the cellular structure. As a result, it gets confused by headers, footers,

// and merged columns (text that crosses columns). There is a tolerance

// that allows a few partitions to count towards potential cell merges.

// It's the max_merged parameter to FindPartitionLocations.

// It can work, but it needs some false positive remove on boundaries.

// For now, the grid structure must not intersect any partitions.

// Also, small tolerance is added to the horizontal lines for tightly packed

// tables. The tolerance is added by adjusting the bounding boxes of the

// partitions (in FindHorizontalPartitions). The current implementation

// only adjusts the vertical extents of the table.

//

// Also note. This was hacked at a lot. It could probably use some

// more hacking at to find a good set of border conditions and then a

// nice clean up.

bool TableRecognizer::RecognizeWhitespacedTable(const TBOX &guess_box, StructuredTable *table) {

  TBOX best_box = guess_box; // Best borders known.

  int best_below = 0;        // Margin size above best table.

  int best_above = 0;        // Margin size below best table.

  TBOX adjusted = guess_box; // The search box.

  // We assume that the guess box is somewhat accurate, so we don't allow

  // the adjusted border to pass half of the guessed area. This prevents

  // "negative" tables from forming.