// Copyright (c) 2012 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "ui/views/layout/grid_layout.h"

#include <algorithm>
#include <cmath>
#include <numeric>
#include <utility>

#include "base/memory/ptr_util.h"
#include "base/stl_util.h"
#include "ui/views/border.h"
#include "ui/views/layout/layout_provider.h"
#include "ui/views/view.h"
#include "ui/views/window/dialog_delegate.h"

namespace views {
namespace {

// Used when calculating the minimum size to build up how much each column is
// shrunk.
struct ColumnMinResizeData {
  // The column being resized.
  Column* column;

  // The remaining amount of space available (the difference between the
  // preferred and minimum).
  int available = 0;

  // How much to shrink the preferred by.
  int delta = 0;
};

}  // namespace

// LayoutElement ------------------------------------------------------

// A LayoutElement has a size and location along one axis. It contains
// methods that are used along both axis.
class LayoutElement {
 public:
  // Invokes ResetSize on all the layout elements.
  template <class T>
  static void ResetSizes(std::vector<std::unique_ptr<T>>* elements) {
    // Reset the layout width of each column.
    for (const auto& element : *elements)
      element->ResetSize();
  }

  // Sets the location of each element to be the sum of the sizes of the
  // preceding elements.
  template <class T>
  static void CalculateLocationsFromSize(
      std::vector<std::unique_ptr<T>>* elements) {
    // Reset the layout width of each column.
    int location = 0;
    for (const auto& element : *elements) {
      element->SetLocation(location);
      location += element->Size();
    }
  }

  // Distributes delta among the resizable elements.
  // Each resizable element is given ResizePercent / total_percent * delta
  // pixels extra of space.
  template <class T>
  static void DistributeDelta(int delta,
                              std::vector<std::unique_ptr<T>>* elements) {
    if (delta == 0)
      return;

    float total_percent = 0;
    int resize_count = 0;
    for (const auto& element : *elements) {
      total_percent += element->ResizePercent();
      if (element->ResizePercent() > 0)
        resize_count++;
    }
    if (total_percent == 0) {
      // None of the elements are resizable, return.
      return;
    }
    int remaining = delta;
    int resized = resize_count;
    for (const auto& element : *elements) {
      if (element->ResizePercent() > 0) {
        int to_give;
        if (--resized == 0) {
          to_give = remaining;
        } else {
          to_give = static_cast<int>(
              delta * (element->resize_percent_ / total_percent));
          remaining -= to_give;
        }
        element->SetSize(element->Size() + to_give);
      }
    }
  }

  // Returns the sum of the size of the elements from start to start + length.
  template <class T>
  static int TotalSize(int start,
                       int length,
                       std::vector<std::unique_ptr<T>>* elements) {
    DCHECK_GE(start, 0);
    DCHECK_GT(length, 0);
    DCHECK_LE(size_t{start + length}, elements->size());
    return std::accumulate(
        elements->cbegin() + start, elements->cbegin() + start + length, 0,
        [](int size, const auto& elem) { return size + elem->Size(); });
  }

  explicit LayoutElement(float resize_percent)
      : resize_percent_(resize_percent) {
    DCHECK_GE(resize_percent, 0);
  }

  virtual ~LayoutElement() = default;

  void SetLocation(int location) { location_ = location; }

  int Location() { return location_; }

  // Adjusts the size of this LayoutElement to be the max of the current size
  // and the specified size.
  virtual void AdjustSize(int size) { size_ = std::max(size_, size); }

  // Resets the size to the initial size. This sets the size to 0, but
  // subclasses that have a different initial size should override.
  virtual void ResetSize() { SetSize(0); }

  void SetSize(int size) { size_ = size; }

  int Size() { return size_; }

  void SetResizePercent(float percent) { resize_percent_ = percent; }

  float ResizePercent() { return resize_percent_; }

  bool IsResizable() { return resize_percent_ > 0; }

 private:
  float resize_percent_;
  int location_;
  int size_;

  DISALLOW_COPY_AND_ASSIGN(LayoutElement);
};

// Column -------------------------------------------------------------

// As the name implies, this represents a Column. Column contains default
// values for views originating in this column.
class Column : public LayoutElement {
 public:
  Column(GridLayout::Alignment h_align,
         GridLayout::Alignment v_align,
         float resize_percent,
         GridLayout::ColumnSize size_type,
         int fixed_width,
         int min_width,
         bool is_padding)
      : LayoutElement(resize_percent),
        h_align_(h_align),
        v_align_(v_align),
        size_type_(size_type),
        same_size_column_(-1),
        fixed_width_(fixed_width),
        min_width_(min_width),
        is_padding_(is_padding),
        master_column_(nullptr) {}

  ~Column() override = default;

  GridLayout::Alignment h_align() { return h_align_; }
  GridLayout::Alignment v_align() { return v_align_; }

  // LayoutElement:
  void ResetSize() override;

 private:
  friend class ColumnSet;
  friend class GridLayout;

  Column* GetLastMasterColumn();

  // Determines the max size of all linked columns, and sets each column
  // to that size. This should only be used for the master column.
  void UnifyLinkedColumnSizes(int size_limit);

  void AdjustSize(int size) override;

  const GridLayout::Alignment h_align_;
  const GridLayout::Alignment v_align_;
  const GridLayout::ColumnSize size_type_;
  int same_size_column_;
  const int fixed_width_;
  const int min_width_;

  const bool is_padding_;

  // If multiple columns have their sizes linked, one is the
  // master column. The master column is identified by the
  // master_column field being equal to itself. The master columns
  // same_size_columns field contains the set of Columns with the
  // the same size. Columns who are linked to other columns, but
  // are not the master column have their master_column pointing to
  // one of the other linked columns. Use the method GetLastMasterColumn
  // to resolve the true master column.
  std::vector<Column*> same_size_columns_;
  Column* master_column_;

  DISALLOW_COPY_AND_ASSIGN(Column);
};

void Column::ResetSize() {
  if (size_type_ == GridLayout::ColumnSize::kFixed) {
    SetSize(fixed_width_);
  } else {
    SetSize(min_width_);
  }
}

Column* Column::GetLastMasterColumn() {
  if (master_column_ == nullptr) {
    return nullptr;
  }
  if (master_column_ == this) {
    return this;
  }
  return master_column_->GetLastMasterColumn();
}

void Column::UnifyLinkedColumnSizes(int size_limit) {
  DCHECK(master_column_ == this);

  // Accumulate the size first.
  int size = 0;
  for (auto* column : same_size_columns_) {
    if (column->Size() <= size_limit)
      size = std::max(size, column->Size());
  }

  // Then apply it.
  for (auto* column : same_size_columns_)
    column->SetSize(std::max(size, column->Size()));
}

void Column::AdjustSize(int size) {
  if (size_type_ == GridLayout::ColumnSize::kUsePreferred)
    LayoutElement::AdjustSize(size);
}

// Row -------------------------------------------------------------

class Row : public LayoutElement {
 public:
  Row(int height, float resize_percent, ColumnSet* column_set)
      : LayoutElement(resize_percent),
        height_(height),
        column_set_(column_set),
        max_ascent_(0),
        max_descent_(0) {}

  ~Row() override = default;

  void ResetSize() override {
    max_ascent_ = max_descent_ = 0;
    SetSize(height_);
  }

  ColumnSet* column_set() { return column_set_; }

  // Adjusts the size to accommodate the specified ascent/descent.
  void AdjustSizeForBaseline(int ascent, int descent) {
    max_ascent_ = std::max(ascent, max_ascent_);
    max_descent_ = std::max(descent, max_descent_);
    AdjustSize(max_ascent_ + max_descent_);
  }

  int max_ascent() const { return max_ascent_; }

  int max_descent() const { return max_descent_; }

 private:
  const int height_;
  // The column set used for this row; null for padding rows.
  ColumnSet* column_set_;

  int max_ascent_;
  int max_descent_;

  DISALLOW_COPY_AND_ASSIGN(Row);
};

// ViewState -------------------------------------------------------------

// Identifies the location in the grid of a particular view, along with
// placement information and size information.
struct ViewState {
  ViewState(ColumnSet* column_set,
            View* view,
            int start_col,
            int start_row,
            int col_span,
            int row_span,
            GridLayout::Alignment h_align,
            GridLayout::Alignment v_align,
            int pref_width,
            int pref_height)
      : column_set(column_set),
        view(view),
        start_col(start_col),
        start_row(start_row),
        col_span(col_span),
        row_span(row_span),
        h_align(h_align),
        v_align(v_align),
        pref_width_fixed(pref_width > 0),
        pref_height_fixed(pref_height > 0),
        width(pref_width),
        height(pref_height) {
    DCHECK(view && start_col >= 0 && start_row >= 0 && col_span > 0 &&
           row_span > 0 && start_col < column_set->num_columns() &&
           (start_col + col_span) <= column_set->num_columns());
  }

  ColumnSet* const column_set;
  View* const view;
  const int start_col;
  const int start_row;
  const int col_span;
  const int row_span;
  const GridLayout::Alignment h_align;
  const GridLayout::Alignment v_align;

  // If true, the height/width were explicitly set and the view's preferred and
  // minimum size is ignored.
  const bool pref_width_fixed;
  const bool pref_height_fixed;

  // The preferred size, only set during the preferred size pass
  // (SizeCalculationType::kPreferred).
  gfx::Size pref_size;

  // The width/height. This is one of possible three values:
  // . an explicitly set value (if pref_X_fixed is true). If an explicitly set
  //   value was provided, then this value never changes.
  // . the preferred width.
  // . the minimum width.
  // If the value wasn't explicitly set, then whether the value is the preferred
  // or minimum depends upon the pass.
  int width;
  int height;

  // Used during layout. Gives how much width/height has not yet been
  // distributed to the columns/rows the view is in.
  int remaining_width = 0;
  int remaining_height = 0;

  // The baseline. Only used if the view is vertically aligned along the
  // baseline.
  int baseline = -1;
};

static bool CompareByColumnSpan(const ViewState* v1, const ViewState* v2) {
  return v1->col_span < v2->col_span;
}

static bool CompareByRowSpan(const std::unique_ptr<ViewState>& v1,
                             const ViewState* v2) {
  return v1->row_span < v2->row_span;
}

// ColumnSet -------------------------------------------------------------

ColumnSet::ColumnSet(int id) : id_(id), linked_column_size_limit_(INT_MAX) {}

ColumnSet::~ColumnSet() = default;

void ColumnSet::AddPaddingColumn(float resize_percent, int width) {
  AddColumn(GridLayout::FILL, GridLayout::FILL, resize_percent,
            GridLayout::ColumnSize::kFixed, width, width, true);
}

void ColumnSet::AddColumn(GridLayout::Alignment h_align,
                          GridLayout::Alignment v_align,
                          float resize_percent,
                          GridLayout::ColumnSize size_type,
                          int fixed_width,
                          int min_width) {
  AddColumn(h_align, v_align, resize_percent, size_type, fixed_width, min_width,
            false);
}

void ColumnSet::LinkColumnSizes(const std::vector<int>& columns) {
  if (columns.size() <= 1)
    return;
  int last = columns[0];
  for (size_t i = 1; i < columns.size(); ++i) {
    int next = columns[i];
    DCHECK_GE(next, 0);
    DCHECK_LT(next, num_columns());
    columns_[last]->same_size_column_ = next;
    last = next;
  }
}

void ColumnSet::AddColumn(GridLayout::Alignment h_align,
                          GridLayout::Alignment v_align,
                          float resize_percent,
                          GridLayout::ColumnSize size_type,
                          int fixed_width,
                          int min_width,
                          bool is_padding) {
  columns_.push_back(std::make_unique<Column>(h_align, v_align, resize_percent,
                                              size_type, fixed_width, min_width,
                                              is_padding));
}

void ColumnSet::AddViewState(ViewState* view_state) {
  // view_states are ordered by column_span (in ascending order).
  auto i = std::lower_bound(view_states_.begin(), view_states_.end(),
                            view_state, CompareByColumnSpan);
  view_states_.insert(i, view_state);
}

void ColumnSet::CalculateMasterColumns() {
  for (const auto& column : columns_) {
    int same_size_column_index = column->same_size_column_;
    if (same_size_column_index != -1) {
      DCHECK(same_size_column_index >= 0 &&
             same_size_column_index < static_cast<int>(columns_.size()));
      Column* master_column = column->master_column_;
      Column* same_size_column = columns_[same_size_column_index].get();
      Column* same_size_column_master = same_size_column->master_column_;
      if (master_column == nullptr) {
        // Current column is not linked to any other column.
        if (same_size_column_master == nullptr) {
          // Both columns are not linked.
          column->master_column_ = column.get();
          same_size_column->master_column_ = column.get();
          column->same_size_columns_.push_back(same_size_column);
          column->same_size_columns_.push_back(column.get());
        } else {
          // Column to link to is linked with other columns.
          // Add current column to list of linked columns in other columns
          // master column.
          same_size_column->GetLastMasterColumn()->same_size_columns_.push_back(
              column.get());
          // And update the master column for the current column to that
          // of the same sized column.
          column->master_column_ = same_size_column;
        }
      } else {
        // Current column is already linked with another column.
        if (same_size_column_master == nullptr) {
          // Column to link with is not linked to any other columns.
          // Update it's master_column.
          same_size_column->master_column_ = column.get();
          // Add linked column to list of linked column.
          column->GetLastMasterColumn()->same_size_columns_.push_back(
              same_size_column);
        } else if (column->GetLastMasterColumn() !=
                   same_size_column->GetLastMasterColumn()) {
          // The two columns are already linked with other columns.
          std::vector<Column*>* same_size_columns =
              &(column->GetLastMasterColumn()->same_size_columns_);
          std::vector<Column*>* other_same_size_columns =
              &(same_size_column->GetLastMasterColumn()->same_size_columns_);
          // Add all the columns from the others master to current columns
          // master.
          same_size_columns->insert(same_size_columns->end(),
                                    other_same_size_columns->begin(),
                                    other_same_size_columns->end());
          // The other master is no longer a master, clear its vector of
          // linked columns, and reset its master_column.
          other_same_size_columns->clear();
          same_size_column->GetLastMasterColumn()->master_column_ =
              column.get();
        }
      }
    }
  }
  AccumulateMasterColumns();
}

void ColumnSet::AccumulateMasterColumns() {
  DCHECK(master_columns_.empty());
  for (const auto& column : columns_) {
    Column* master_column = column->GetLastMasterColumn();
    if (master_column && !base::Contains(master_columns_, master_column)) {
      master_columns_.push_back(master_column);
    }
    // At this point, GetLastMasterColumn may not == master_column
    // (may have to go through a few Columns)_. Reset master_column to
    // avoid hops.
    column->master_column_ = master_column;
  }
}

void ColumnSet::UnifyLinkedColumnSizes() {
  for (auto* column : master_columns_)
    column->UnifyLinkedColumnSizes(linked_column_size_limit_);
}

void ColumnSet::UpdateRemainingWidth(ViewState* view_state) {
  view_state->remaining_width -= LayoutElement::TotalSize(
      view_state->start_col, view_state->col_span, &columns_);
}

void ColumnSet::DistributeRemainingWidth(ViewState* view_state) {
  // This is nearly the same as that for rows, but differs in so far as how
  // Rows and Columns are treated. Rows have two states, resizable or not.
  // Columns have three, resizable, USE_PREF or not resizable. This results
  // in slightly different handling for distributing unaccounted size.
  int width = view_state->remaining_width;
  if (width <= 0) {
    // The columns this view is in are big enough to accommodate it.
    return;
  }

  // Determine which columns are resizable, and which have a size type
  // of USE_PREF.
  int resizable_columns = 0;
  int pref_size_columns = 0;
  int start_col = view_state->start_col;
  int max_col = view_state->start_col + view_state->col_span;
  float total_resize = 0;
  for (int i = start_col; i < max_col; ++i) {
    if (columns_[i]->IsResizable()) {
      total_resize += columns_[i]->ResizePercent();
      resizable_columns++;
    } else if (columns_[i]->size_type_ ==
               GridLayout::ColumnSize::kUsePreferred) {
      pref_size_columns++;
    }
  }

  if (resizable_columns > 0) {
    // There are resizable columns, give them the remaining width. The extra
    // width is distributed using the resize values of each column.
    int remaining_width = width;
    for (int i = start_col, resize_i = 0; i < max_col; ++i) {
      if (columns_[i]->IsResizable()) {
        resize_i++;
        int delta =
            (resize_i == resizable_columns)
                ? remaining_width
                : static_cast<int>(width * columns_[i]->ResizePercent() /
                                   total_resize);
        remaining_width -= delta;
        columns_[i]->SetSize(columns_[i]->Size() + delta);
      }
    }
  } else if (pref_size_columns > 0) {
    // None of the columns are resizable, distribute the width among those
    // that use the preferred size.
    int to_distribute = width / pref_size_columns;
    for (int i = start_col; i < max_col; ++i) {
      if (columns_[i]->size_type_ == GridLayout::ColumnSize::kUsePreferred) {
        width -= to_distribute;
        if (width < to_distribute)
          to_distribute += width;
        columns_[i]->SetSize(columns_[i]->Size() + to_distribute);
      }
    }
  }
}

int ColumnSet::LayoutWidth() {
  int width = 0;
  for (const auto& column : columns_)
    width += column->Size();

  return width;
}

int ColumnSet::GetColumnWidth(int start_col, int col_span) {
  return LayoutElement::TotalSize(start_col, col_span, &columns_);
}

void ColumnSet::ResetColumnXCoordinates() {
  LayoutElement::CalculateLocationsFromSize(&columns_);
}

void ColumnSet::CalculateSize(SizeCalculationType type) {
#if DCHECK_IS_ON()
  // SizeCalculationType::kMinimum must be preceded by a request for
  // SizeCalculationType::kPreferred.
  DCHECK(type == SizeCalculationType::kPreferred ||
         last_calculation_type_ == SizeCalculationType::kPreferred);
  last_calculation_type_ = type;
#endif
  // Reset the size and remaining sizes.
  for (auto* view_state : view_states_) {
    if (!view_state->pref_width_fixed || !view_state->pref_height_fixed) {
      gfx::Size size;
      if (type == SizeCalculationType::kMinimum && CanUseMinimum(*view_state)) {
        // If the min size is bigger than the preferred, use the preferred.
        // This relies on MINIMUM being calculated immediately after PREFERRED,
        // which the rest of this code relies on as well.
        size = view_state->view->GetMinimumSize();
        if (size.width() > view_state->width)
          size.set_width(view_state->width);
        if (size.height() > view_state->height)
          size.set_height(view_state->height);
      } else {
        size = view_state->view->GetPreferredSize();
        view_state->pref_size = size;
      }
      if (!view_state->pref_width_fixed)
        view_state->width = size.width();
      if (!view_state->pref_height_fixed)
        view_state->height = size.height();
    }
    view_state->remaining_width = view_state->width;
    view_state->remaining_height = view_state->height;
  }

  LayoutElement::ResetSizes(&columns_);

  // Distribute the size of each view with a col span == 1.
  auto view_state_iterator = view_states_.begin();
  for (; view_state_iterator != view_states_.end() &&
         (*view_state_iterator)->col_span == 1;
       ++view_state_iterator) {
    ViewState* view_state = *view_state_iterator;
    Column* column = columns_[view_state->start_col].get();
    column->AdjustSize(view_state->width);
    view_state->remaining_width -= column->Size();
  }

  // Make sure all linked columns have the same size.
  UnifyLinkedColumnSizes();

  // Distribute the size of each view with a column span > 1.
  for (; view_state_iterator != view_states_.end(); ++view_state_iterator) {
    ViewState* view_state = *view_state_iterator;

    // Update the remaining_width from columns this view_state touches.
    UpdateRemainingWidth(view_state);

    // Distribute the remaining width.
    DistributeRemainingWidth(view_state);

    // Update the size of linked columns.
    // This may need to be combined with previous step.
    UnifyLinkedColumnSizes();
  }
}

void ColumnSet::Resize(int delta, bool honors_min_width) {
  if (delta < 0 && honors_min_width) {
    // DistributeDelta() assumes resizable columns can equally be shrunk. That
    // isn't desired when given a size smaller than the prefered. Instead the
    // columns need to be resized but bounded by the minimum. ResizeUsingMin()
    // does this.
    ResizeUsingMin(delta);
    return;
  }

  LayoutElement::DistributeDelta(delta, &columns_);
}

void ColumnSet::ResizeUsingMin(int total_delta) {
  DCHECK_LE(total_delta, 0);

  // |total_delta| is negative, but easier to do operations when positive.
  total_delta = std::abs(total_delta);

  std::vector<int> preferred_column_sizes(columns_.size());
  for (size_t i = 0; i < columns_.size(); ++i)
    preferred_column_sizes[i] = columns_[i]->Size();

  // Recalculate the sizes using the min.
  CalculateSize(ColumnSet::SizeCalculationType::kMinimum);

  // Build up the set of columns that can be shrunk in |resize_data|, this
  // iteration also resets the size of the column back to the preferred size.
  std::vector<ColumnMinResizeData> resize_data;
  float total_percent = 0;
  for (size_t i = 0; i < columns_.size(); ++i) {
    Column* column = columns_[i].get();
    const int available =
        std::max(0, preferred_column_sizes[i] -
                        std::max(column->min_width_, column->Size()));
    DCHECK_GE(available, 0);
    // Set the size back to preferred. We'll reset the size if necessary later.
    column->SetSize(preferred_column_sizes[i]);
    if (column->ResizePercent() <= 0 || available == 0)
      continue;
    resize_data.push_back({column, available, 0});
    total_percent += column->ResizePercent();
  }
  if (resize_data.empty())
    return;

  // Loop through the columns updating the amount available and the amount to
  // resize. This may take multiple iterations if the column min is hit.
  // Generally there are not that many columns in a GridLayout, so this code is
  // not optimized. Any time the column hits the min it is removed from
  // |resize_data|.
  while (!resize_data.empty() && total_delta > 0) {
    float next_iteration_total_percent = total_percent;
    int next_iteration_delta = total_delta;
#if DCHECK_IS_ON()
    const int initial_delta = total_delta;
#endif
    for (size_t i = resize_data.size(); i > 0; --i) {
      ColumnMinResizeData& data = resize_data[i - 1];
      int delta =
          std::min(data.available,
                   static_cast<int>(total_delta * data.column->ResizePercent() /
                                    total_percent));
      // Make sure at least one column in resized (rounding errors may prevent
      // that).
      if (i == 1 && delta == 0 && next_iteration_delta == total_delta)
        delta = 1;
      next_iteration_delta -= delta;
      data.delta += delta;
      data.available -= delta;
      if (data.available == 0) {
        data.column->SetSize(data.column->Size() - data.delta);
        next_iteration_total_percent -= data.column->ResizePercent();
        resize_data.erase(resize_data.begin() + (i - 1));
      }
    }
#if DCHECK_IS_ON()
    DCHECK(next_iteration_delta < initial_delta);
#endif
    total_delta = next_iteration_delta;
    total_percent = next_iteration_total_percent;
  }

  for (const ColumnMinResizeData& data : resize_data)
    data.column->SetSize(data.column->Size() - data.delta);
}

bool ColumnSet::CanUseMinimum(const ViewState& view_state) const {
  const auto resizable = [](const auto& col) {
    return col->ResizePercent() > 0 &&
           col->size_type_ != GridLayout::ColumnSize::kFixed;
  };
  return std::all_of(
      columns_.cbegin() + view_state.start_col,
      columns_.cbegin() + view_state.start_col + view_state.col_span,
      resizable);
}

// GridLayout -------------------------------------------------------------

GridLayout::GridLayout() = default;

GridLayout::~GridLayout() = default;

ColumnSet* GridLayout::AddColumnSet(int id) {
  DCHECK(GetColumnSet(id) == nullptr);
  column_sets_.push_back(base::WrapUnique(new ColumnSet(id)));
  return column_sets_.back().get();
}

ColumnSet* GridLayout::GetColumnSet(int id) {
  const auto i = std::find_if(
      column_sets_.cbegin(), column_sets_.cend(),
      [id](const auto& column_set) { return column_set->id_ == id; });
  return (i == column_sets_.cend()) ? nullptr : i->get();
}

void GridLayout::StartRowWithPadding(float vertical_resize,
                                     int column_set_id,
                                     float padding_resize,
                                     int padding) {
  AddPaddingRow(padding_resize, padding);
  StartRow(vertical_resize, column_set_id);
}

void GridLayout::StartRow(float vertical_resize,
                          int column_set_id,
                          int height) {
  DCHECK_GE(height, 0);
  ColumnSet* column_set = GetColumnSet(column_set_id);
  DCHECK(column_set);
  AddRow(std::make_unique<Row>(height, vertical_resize, column_set));
}

void GridLayout::AddPaddingRow(float vertical_resize, int pixel_count) {
  AddRow(std::make_unique<Row>(pixel_count, vertical_resize, nullptr));
}

void GridLayout::SkipColumns(int col_count) {
  DCHECK_GT(col_count, 0);
  next_column_ += col_count;
  DCHECK(current_row_col_set_ &&
         next_column_ <= current_row_col_set_->num_columns());
  SkipPaddingColumns();
}

void GridLayout::AddExistingView(View* view, int col_span, int row_span) {
  DCHECK(view->parent() && view->parent() == host_)
      << "Use AddView() to add a new View that isn't already parented to "
         "|host_|.";
  DCHECK(current_row_col_set_ &&
         next_column_ < current_row_col_set_->num_columns());
  Column* column = current_row_col_set_->columns_[next_column_].get();
  AddExistingView(view, col_span, row_span, column->h_align(),
                  column->v_align());
}

void GridLayout::AddViewImpl(std::unique_ptr<View> view,
                             int col_span,
                             int row_span) {
  DCHECK(current_row_col_set_ &&
         next_column_ < current_row_col_set_->num_columns());
  Column* column = current_row_col_set_->columns_[next_column_].get();
  AddViewImpl(std::move(view), col_span, row_span, column->h_align(),
              column->v_align(), 0, 0);
}

void GridLayout::AddExistingView(View* view,
                                 int col_span,
                                 int row_span,
                                 Alignment h_align,
                                 Alignment v_align,
                                 int pref_width,
                                 int pref_height) {
  DCHECK(view->parent() && view->parent() == host_)
      << "Use AddView() to add a new View that isn't already parented to "
         "|host_|.";
  DCHECK(current_row_col_set_ && col_span > 0 && row_span > 0 &&
         (next_column_ + col_span) <= current_row_col_set_->num_columns());
  // We don't support baseline alignment of views spanning rows. Please add if
  // you need it.
  DCHECK(v_align != BASELINE || row_span == 1);
  AddViewState(std::make_unique<ViewState>(
      current_row_col_set_, view, next_column_, current_row_, col_span,
      row_span, h_align, v_align, pref_width, pref_height));
}

void GridLayout::AddViewImpl(std::unique_ptr<View> view,
                             int col_span,
                             int row_span,
                             Alignment h_align,
                             Alignment v_align,
                             int pref_width,
                             int pref_height) {
  DCHECK(current_row_col_set_ && col_span > 0 && row_span > 0 &&
         (next_column_ + col_span) <= current_row_col_set_->num_columns());
  // We don't support baseline alignment of views spanning rows. Please add if
  // you need it.
  DCHECK(v_align != BASELINE || row_span == 1);
  adding_view_ = true;
  View* view_ptr = host_->AddChildView(std::move(view));
  adding_view_ = false;
  AddViewState(std::make_unique<ViewState>(
      current_row_col_set_, view_ptr, next_column_, current_row_, col_span,
      row_span, h_align, v_align, pref_width, pref_height));
}

static void CalculateSize(int pref_size,
                          GridLayout::Alignment alignment,
                          int* location,
                          int* size) {
  if (alignment != GridLayout::FILL) {
    int available_size = *size;
    *size = std::min(*size, pref_size);
    switch (alignment) {
      case GridLayout::LEADING:
        // Nothing to do, location already points to start.
        break;
      case GridLayout::BASELINE:  // If we were asked to align on baseline, but
                                  // the view doesn't have a baseline, fall back
                                  // to center.
      case GridLayout::CENTER:
        *location += (available_size - *size) / 2;
        break;
      case GridLayout::TRAILING:
        *location = *location + available_size - *size;
        break;
      default:
        NOTREACHED();
    }
  }
}

void GridLayout::Installed(View* host) {
  host_ = host;
}

void GridLayout::ViewAdded(View* host, View* view) {
  DCHECK(host_ == host && adding_view_);
}

void GridLayout::ViewRemoved(View* host, View* view) {
  DCHECK(host_ == host);
}

void GridLayout::Layout(View* host) {
  DCHECK(host_ == host);
  // SizeRowsAndColumns sets the size and location of each row/column, but
  // not of the views.
  gfx::Size pref;
  SizeRowsAndColumns(true, host_->width(), host_->height(), &pref);

  // Size each view.
  for (const auto& view_state : view_states_) {
    ColumnSet* column_set = view_state->column_set;
    View* view = view_state->view;
    DCHECK(view);
    const gfx::Insets& insets = host_->GetInsets();
    int x =
        column_set->columns_[view_state->start_col]->Location() + insets.left();
    int width =
        column_set->GetColumnWidth(view_state->start_col, view_state->col_span);
    CalculateSize(view_state->width, view_state->h_align, &x, &width);
    int y = rows_[view_state->start_row]->Location() + insets.top();
    int height = LayoutElement::TotalSize(view_state->start_row,
                                          view_state->row_span, &rows_);
    if (view_state->v_align == BASELINE && view_state->baseline != -1) {
      y += rows_[view_state->start_row]->max_ascent() - view_state->baseline;
      height = view_state->height;
    } else {
      CalculateSize(view_state->height, view_state->v_align, &y, &height);
    }
    view->SetBounds(x, y, width, height);
  }
}

gfx::Size GridLayout::GetPreferredSize(const View* host) const {
  DCHECK(host_ == host);
  gfx::Size out;
  SizeRowsAndColumns(false, 0, 0, &out);
  out.SetSize(std::max(out.width(), minimum_size_.width()),
              std::max(out.height(), minimum_size_.height()));
  return out;
}

int GridLayout::GetPreferredHeightForWidth(const View* host, int width) const {
  DCHECK(host_ == host);
  gfx::Size pref;
  SizeRowsAndColumns(false, width, 0, &pref);
  return pref.height();
}

void GridLayout::SizeRowsAndColumns(bool layout,
                                    int width,
                                    int height,
                                    gfx::Size* pref) const {
  // Protect against clients asking for metrics during the addition of a View.
  // The View is in the hierarchy, but it will not be accounted for in the
  // layout calculations at this point, so the result will be incorrect.
  DCHECK(!adding_view_) << "GridLayout queried while adding a view.";

  // Make sure the master columns have been calculated.
  CalculateMasterColumnsIfNecessary();
  pref->SetSize(0, 0);
  if (rows_.empty())
    return;

  // Calculate the preferred width of each of the columns. Some views'
  // preferred heights are derived from their width, as such we need to
  // calculate the size of the columns first.
  for (const auto& column_set : column_sets_) {
    column_set->CalculateSize(ColumnSet::SizeCalculationType::kPreferred);
    pref->set_width(std::max(pref->width(), column_set->LayoutWidth()));
  }
  const gfx::Insets& insets = host_->GetInsets();
  pref->set_width(pref->width() + insets.width());

  // Go over the columns again and set them all to the size we settled for.
  width = width ? width : pref->width();
  for (const auto& column_set : column_sets_) {
    // We're doing a layout, divvy up any extra space.
    column_set->Resize(width - column_set->LayoutWidth() - insets.width(),
                       honors_min_width_);
    // And reset the x coordinates.
    column_set->ResetColumnXCoordinates();
  }

  // Reset the height of each row.
  LayoutElement::ResetSizes(&rows_);

  // Do the following:
  // . If the view is aligned along it's baseline, obtain the baseline from the
  //   view and update the rows ascent/descent.
  // . Reset the remaining_height of each view state.
  // . If the width the view will be given is different than it's pref, ask
  //   for the height given the actual width.
  for (const auto& view_state : view_states_) {
    view_state->remaining_height = view_state->height;

    if (view_state->v_align == BASELINE)
      view_state->baseline = view_state->view->GetBaseline();

    if (!view_state->pref_height_fixed) {
      // If the view is given a different width than it's preferred width
      // requery for the preferred height. This is necessary as the preferred
      // height may depend upon the width.
      int actual_width = view_state->column_set->GetColumnWidth(
          view_state->start_col, view_state->col_span);
      int x = 0;  // Not used in this stage.
      CalculateSize(view_state->width, view_state->h_align, &x, &actual_width);
      if (actual_width != view_state->width) {
        // The width this view will get differs from its preferred. Some Views
        // pref height varies with its width; ask for the preferred again.
        view_state->height = view_state->view->GetHeightForWidth(actual_width);
        view_state->remaining_height = view_state->height;
      }
    }
  }

  // Update the height/ascent/descent of each row from the views.
  auto view_states_iterator = view_states_.begin();
  for (; view_states_iterator != view_states_.end() &&
         (*view_states_iterator)->row_span == 1;
       ++view_states_iterator) {
    ViewState* view_state = view_states_iterator->get();
    Row* row = rows_[view_state->start_row].get();
    row->AdjustSize(view_state->remaining_height);
    if (view_state->baseline != -1 &&
        view_state->baseline <= view_state->height) {
      row->AdjustSizeForBaseline(view_state->baseline,
                                 view_state->height - view_state->baseline);
    }
    view_state->remaining_height = 0;
  }

  // Distribute the height of each view with a row span > 1.
  for (; view_states_iterator != view_states_.end(); ++view_states_iterator) {
    ViewState* view_state = view_states_iterator->get();

    // Update the remaining_width from columns this view_state touches.
    UpdateRemainingHeightFromRows(view_state);

    // Distribute the remaining height.
    DistributeRemainingHeight(view_state);
  }

  // Update the location of each of the rows.
  LayoutElement::CalculateLocationsFromSize(&rows_);

  // We now know the preferred height, set it here.
  pref->set_height(rows_.back()->Location() + rows_.back()->Size() +
                   insets.height());

  if (layout && height != pref->height()) {
    // We're doing a layout, and the height differs from the preferred height,
    // divvy up the extra space.
    LayoutElement::DistributeDelta(height - pref->height(), &rows_);

    // Reset y locations.
    LayoutElement::CalculateLocationsFromSize(&rows_);
  }
}

void GridLayout::CalculateMasterColumnsIfNecessary() const {
  if (!calculated_master_columns_) {
    calculated_master_columns_ = true;
    for (const auto& column_set : column_sets_)
      column_set->CalculateMasterColumns();
  }
}

void GridLayout::AddViewState(std::unique_ptr<ViewState> view_state) {
  DCHECK(view_state->view && view_state->view->parent() == host_);
  remaining_row_span_ = std::max(remaining_row_span_, view_state->row_span);
  next_column_ += view_state->col_span;
  current_row_col_set_->AddViewState(view_state.get());
  // view_states are ordered by row_span (in ascending order).
  auto i = std::lower_bound(view_states_.begin(), view_states_.end(),
                            view_state.get(), CompareByRowSpan);
  view_states_.insert(i, std::move(view_state));
  SkipPaddingColumns();
}

void GridLayout::AddRow(std::unique_ptr<Row> row) {
  current_row_++;
  remaining_row_span_--;
  // GridLayout requires that if you add a View with a row span you use the same
  // column set for each of the rows the view lands it. This DCHECK verifies
  // that.
  DCHECK(remaining_row_span_ <= 0 || row->column_set() == nullptr ||
         row->column_set() == GetLastValidColumnSet());
  next_column_ = 0;
  current_row_col_set_ = row->column_set();
  rows_.push_back(std::move(row));
  SkipPaddingColumns();
}

void GridLayout::UpdateRemainingHeightFromRows(ViewState* view_state) const {
  view_state->remaining_height -= LayoutElement::TotalSize(
      view_state->start_row, view_state->row_span, &rows_);
}

void GridLayout::DistributeRemainingHeight(ViewState* view_state) const {
  int height = view_state->remaining_height;
  if (height <= 0)
    return;

  // Determine the number of resizable rows the view touches.
  int start_row = view_state->start_row;
  int max_row = view_state->start_row + view_state->row_span;
  const int resizable_rows =
      std::count_if(rows_.cbegin() + start_row, rows_.cbegin() + max_row,
                    [](const auto& row) { return row->IsResizable(); });

  if (resizable_rows > 0) {
    // There are resizable rows, give the remaining height to them.
    int to_distribute = height / resizable_rows;
    for (int i = start_row; i < max_row; ++i) {
      if (rows_[i]->IsResizable()) {
        height -= to_distribute;
        if (height < to_distribute) {
          // Give all slop to the last column.
          to_distribute += height;
        }
        rows_[i]->SetSize(rows_[i]->Size() + to_distribute);
      }
    }
  } else {
    // None of the rows are resizable, divvy the remaining height up equally
    // among all rows the view touches.
    int each_row_height = height / view_state->row_span;
    for (int i = start_row; i < max_row; ++i) {
      height -= each_row_height;
      if (height < each_row_height)
        each_row_height += height;
      rows_[i]->SetSize(rows_[i]->Size() + each_row_height);
    }
    view_state->remaining_height = 0;
  }
}

void GridLayout::SkipPaddingColumns() {
  if (!current_row_col_set_)
    return;
  while (next_column_ < current_row_col_set_->num_columns() &&
         current_row_col_set_->columns_[next_column_]->is_padding_) {
    next_column_++;
  }
}

ColumnSet* GridLayout::GetLastValidColumnSet() {
  const auto i =
      std::find_if(rows_.crend() - current_row_, rows_.crend(),
                   [](const auto& row) { return row->column_set(); });
  return (i == rows_.crend()) ? nullptr : (*i)->column_set();
}

}  // namespace views