// SPDX-FileCopyrightText: Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
// SPDX-License-Identifier: BSD-3-Clause

#include "vtkExplicitStructuredGrid.h"

#include "vtkCell.h"
#include "vtkCellArray.h"
#include "vtkCellData.h"
#include "vtkCellLinks.h"
#include "vtkDataSetAttributes.h"
#include "vtkEmptyCell.h"
#include "vtkGarbageCollector.h"
#include "vtkGenericCell.h"
#include "vtkHexahedron.h"
#include "vtkInformation.h"
#include "vtkInformationVector.h"
#include "vtkNew.h"
#include "vtkObjectFactory.h"
#include "vtkPointData.h"
#include "vtkStaticCellLinks.h"
#include "vtkStructuredData.h"
#include "vtkUnsignedCharArray.h"

#include <algorithm>

VTK_ABI_NAMESPACE_BEGIN
static constexpr unsigned char MASKED_CELL_VALUE =
  vtkDataSetAttributes::HIDDENCELL | vtkDataSetAttributes::REFINEDCELL;

static int HEXAHEDRON_POINT_MAP[] = {
  0, 1, 3, 2, 4, 5, 7, 6, //
  1, 0, 2, 3, 5, 4, 6, 7, //
  0, 3, 1, 2, 4, 7, 5, 6, //
  3, 0, 2, 1, 7, 4, 6, 5, //
  0, 4, 1, 5, 2, 6, 3, 7, //
  4, 0, 5, 1, 6, 2, 7, 3  //
};

static int SWAP_HEXAHEDRON_POINT_MAP[] = {
  0, 1, 5, 4, 3, 2, 6, 7, //
  0, 4, 7, 3, 1, 5, 6, 2, //
  0, 3, 2, 1, 4, 7, 6, 5  //
};

static int MIRROR_HEXAHEDRON_POINT_MAP[] = {
  1, 0, 3, 2, 5, 4, 7, 6, //
  3, 2, 1, 0, 7, 6, 5, 4, //
  4, 5, 6, 7, 0, 1, 2, 3  //
};

vtkStandardNewMacro(vtkExplicitStructuredGrid);

//------------------------------------------------------------------------------
vtkExplicitStructuredGrid::vtkExplicitStructuredGrid()
{
  this->Cells = vtkSmartPointer<vtkCellArray>::New();
  this->Cells->UseFixedSizeDefaultStorage(8);

  this->FacesConnectivityFlagsArrayName = nullptr;

  int extent[6] = { 0, -1, 0, -1, 0, -1 };
  std::copy(this->Extent, this->Extent + 6, extent);

  this->Information->Set(vtkDataObject::DATA_EXTENT_TYPE(), VTK_3D_EXTENT);
  this->Information->Set(vtkDataObject::DATA_EXTENT(), this->Extent, 6);
}

//------------------------------------------------------------------------------
vtkExplicitStructuredGrid::~vtkExplicitStructuredGrid()
{
  this->SetFacesConnectivityFlagsArrayName(nullptr);
  this->SetCells(nullptr);
}

//------------------------------------------------------------------------------
void vtkExplicitStructuredGrid::Initialize()
{
  this->Superclass::Initialize();

  if (this->Information)
  {
    this->SetDimensions(0, 0, 0);
  }

  this->SetCells(nullptr);
  if (this->Links)
  {
    this->Links->Initialize();
  }
}

//------------------------------------------------------------------------------
int vtkExplicitStructuredGrid::GetCellType(vtkIdType cellId)
{
  return this->IsCellVisible(cellId) ? VTK_HEXAHEDRON : VTK_EMPTY_CELL;
}

//------------------------------------------------------------------------------
vtkIdType vtkExplicitStructuredGrid::GetCellSize(vtkIdType cellId)
{
  return this->IsCellVisible(cellId) ? 8 : 0;
}

//------------------------------------------------------------------------------
vtkIdType vtkExplicitStructuredGrid::GetNumberOfCells()
{
  return vtkStructuredData::GetNumberOfCells(this->Extent);
}

//------------------------------------------------------------------------------
vtkCell* vtkExplicitStructuredGrid::GetCell(vtkIdType cellId)
{
  this->GetCell(cellId, this->GenericCell);
  return this->GenericCell->GetRepresentativeCell();
}

//------------------------------------------------------------------------------
void vtkExplicitStructuredGrid::GetCell(vtkIdType cellId, vtkGenericCell* cell)
{
  if (!this->IsCellVisible(cellId))
  {
    cell->SetCellTypeToEmptyCell();
    return;
  }
  cell->SetCellTypeToHexahedron();
  this->Cells->GetCellAtId(cellId, cell->PointIds);
  this->Points->GetPoints(cell->PointIds, cell->Points);
}

//------------------------------------------------------------------------------
// Support GetCellBounds()
namespace
{ // anonymous
struct ComputeCellBoundsVisitor : public vtkCellArray::DispatchUtilities
{
  // vtkCellArray::Visit entry point:
  template <class OffsetsT, class ConnectivityT>
  void operator()(OffsetsT* offsets, ConnectivityT* conn, vtkPoints* points, vtkIdType cellId,
    double bounds[6]) const
  {
    const vtkIdType beginOffset = GetBeginOffset(offsets, cellId);

    const auto pointIds = GetRange(conn).begin() + beginOffset;
    vtkBoundingBox::ComputeBounds(points, pointIds, 8, bounds);
  }
};
} // anonymous

//------------------------------------------------------------------------------
// Fast implementation of GetCellBounds().
// Bounds are calculated without constructing a cell.
void vtkExplicitStructuredGrid::GetCellBounds(vtkIdType cellId, double bounds[6])
{
  if (!this->Points)
  {
    vtkErrorMacro(<< "No data");
    return;
  }
  this->Cells->Dispatch(ComputeCellBoundsVisitor{}, this->Points, cellId, bounds);
}

//------------------------------------------------------------------------------
void vtkExplicitStructuredGrid::GetPointCells(vtkIdType ptId, vtkIdList* cellIds)
{
  if (!this->Links)
  {
    this->BuildLinks();
  }
  cellIds->Reset();

  // Use the correct cell links. Use an explicit cast for performance reasons
  // (virtuals, and templated functions were tested to be slow -- if you make
  // changes, please make sure to measure performance impacts).
  vtkIdType numCells, *cells;
  if (!this->Editable)
  {
    vtkStaticCellLinks* links = static_cast<vtkStaticCellLinks*>(this->Links.Get());
    numCells = links->GetNcells(ptId);
    cells = links->GetCells(ptId);
  }
  else
  {
    vtkCellLinks* links = static_cast<vtkCellLinks*>(this->Links.Get());
    numCells = links->GetNcells(ptId);
    cells = links->GetCells(ptId);
  }

  cellIds->SetNumberOfIds(numCells);
  for (auto i = 0; i < numCells; i++)
  {
    cellIds->SetId(i, cells[i]);
  }
}

//------------------------------------------------------------------------------
vtkIdType* vtkExplicitStructuredGrid::GetCellPoints(vtkIdType cellId)
{
  vtkIdType unused;
  const vtkIdType* result;
  this->Cells->GetCellAtId(cellId, unused, result);
  return const_cast<vtkIdType*>(result);
}

//------------------------------------------------------------------------------
// Get the points defining a cell. (See vtkDataSet for more info.)
void vtkExplicitStructuredGrid::GetCellPoints(vtkIdType cellId, vtkIdList* ptIds)
{
  ptIds->Reset();
  ptIds->SetNumberOfIds(8);
  vtkIdType* indices = this->GetCellPoints(cellId);
  for (int i = 0; i < 8; i++)
  {
    ptIds->SetId(i, indices[i]);
  }
}

//------------------------------------------------------------------------------
// Return a pointer to a list of point ids defining cell.
// More efficient than alternative method.
void vtkExplicitStructuredGrid::GetCellPoints(vtkIdType cellId, vtkIdType& npts, vtkIdType*& pts)
{
  npts = 8;
  pts = this->GetCellPoints(cellId);
}

//------------------------------------------------------------------------------
void vtkExplicitStructuredGrid::GetCellPoints(
  vtkIdType cellId, vtkIdType& npts, vtkIdType const*& pts, vtkIdList* ptIds)
{
  this->Cells->GetCellAtId(cellId, npts, pts, ptIds);
}

//------------------------------------------------------------------------------
void vtkExplicitStructuredGrid::GetCellNeighbors(
  vtkIdType cellId, vtkIdType neighbors[6], int* wholeExtent)
{
  int ci, cj, ck;
  this->ComputeCellStructuredCoords(cellId, ci, cj, ck, true);
  int* extent = wholeExtent;
  if (!wholeExtent)
  {
    // If the whole extent have not been defined, use own extent
    extent = new int[6];
    this->GetExtent(extent);
  }
  int dims[3];
  vtkStructuredData::GetDimensionsFromExtent(extent, dims);
  dims[0]--;
  dims[1]--;
  dims[2]--;
  for (int faceId = 0; faceId < 6; faceId++)
  {
    int c[] = { ci - extent[0], cj - extent[2], ck - extent[4] };
    c[faceId / 2] += (faceId % 2) ? 1 : -1;
    bool invalidCellId =
      (c[0] < 0 || c[1] < 0 || c[2] < 0 || c[0] >= dims[0] || c[1] >= dims[1] || c[2] >= dims[2]);
    neighbors[faceId] = invalidCellId ? -1 : (c[0] + c[1] * dims[0] + c[2] * dims[0] * dims[1]);
  }
  if (!wholeExtent)
  {
    delete[] extent;
  }
}

namespace
{
// Identify the neighbors to the specified cell, where the neighbors
// use all the points in the points list (pts).
template <class TLinks>
struct GetCellNeighborsImpl : public vtkCellArray::DispatchUtilities
{
  // vtkCellArray::Visit entry point:
  template <class OffsetsT, class ConnectivityT>
  void operator()(OffsetsT* offsets, ConnectivityT* conn, TLinks* links, vtkIdType cellId,
    vtkIdType nPts, const vtkIdType* pts, vtkIdList* cellIds) const
  {
    using ValueType = GetAPIType<OffsetsT>;

    // Find the shortest linked list
    auto minPtId = pts[0];
    auto minNumCells = links->GetNcells(minPtId);
    vtkIdType numCells;
    for (vtkIdType i = 1; i < nPts; ++i)
    {
      const auto& ptId = pts[i];
      numCells = links->GetNcells(ptId);
      if (numCells < minNumCells)
      {
        minNumCells = numCells;
        minPtId = ptId;
      }
    }
    const auto minCells = links->GetCells(minPtId);

    // Now for each cell, see if it contains all the face points
    // in the facePts list. If so, then this is not a boundary face.
    const auto connRange = GetRange(conn);
    const auto offsetsRange = GetRange(offsets);
    bool match;
    vtkIdType j;
    ValueType k;
    for (vtkIdType i = 0; i < minNumCells; ++i)
    {
      const auto& minCellId = minCells[i];
      if (minCellId != cellId) // don't include current cell
      {
        // get cell points
        const ValueType nCellPts = offsetsRange[minCellId + 1] - offsetsRange[minCellId];
        const auto cellPts = connRange.begin() + offsetsRange[minCellId];
        match = true;
        for (j = 0; j < nPts && match; ++j) // for all pts in input boundary entity
        {
          const auto& ptId = pts[j];
          if (ptId != minPtId) // of course minPtId is contained by cell
          {
            match = false;
            for (k = 0; k < nCellPts; ++k) // for all points in candidate cell
            {
              if (ptId == cellPts[k])
              {
                match = true; // a match was found
                break;
              }
            } // for all points in current cell
          }   // if not guaranteed match
        }     // for all input points
        if (match)
        {
          cellIds->InsertNextId(minCellId);
        }
      } // if not the reference cell
    }   // for each cell in minimum linked list
  }
};
} // end anonymous namespace

//----------------------------------------------------------------------------
// Return the cells that use all of the ptIds provided. This is a set
// (intersection) operation - it can have significant performance impacts on
// certain filters like vtkGeometryFilter.
void vtkExplicitStructuredGrid::GetCellNeighbors(
  vtkIdType cellId, vtkIdList* ptIds, vtkIdList* cellIds)
{
  // Empty the list
  cellIds->Reset();

  // Ensure that a proper neighborhood request is made.
  const vtkIdType npts = ptIds->GetNumberOfIds();
  if (npts <= 0)
  {
    return;
  }
  const vtkIdType* pts = ptIds->GetPointer(0);

  // Ensure that links are built.
  if (!this->Links)
  {
    this->BuildLinks();
  }

  // Get the cell links based on the current state.
  if (!this->Editable)
  {
    using CellLinksType = vtkStaticCellLinks;
    using TGetCellNeighbors = GetCellNeighborsImpl<CellLinksType>;
    auto links = static_cast<CellLinksType*>(this->Links.Get());
    this->Cells->Dispatch(TGetCellNeighbors{}, links, cellId, npts, pts, cellIds);
  }
  else
  {
    using CellLinksType = vtkCellLinks;
    using TGetCellNeighbors = GetCellNeighborsImpl<CellLinksType>;
    auto links = static_cast<CellLinksType*>(this->Links.Get());
    this->Cells->Dispatch(TGetCellNeighbors{}, links, cellId, npts, pts, cellIds);
  }
}

//------------------------------------------------------------------------------
void vtkExplicitStructuredGrid::InternalCopy(vtkExplicitStructuredGrid* src)
{
  // Internal method used for copying specific members
  this->SetExtent(src->GetExtent());
  this->SetFacesConnectivityFlagsArrayName(src->GetFacesConnectivityFlagsArrayName());
}

//------------------------------------------------------------------------------
// Copy the topological structure of an input structured grid.
void vtkExplicitStructuredGrid::CopyStructure(vtkDataSet* ds)
{
  vtkExplicitStructuredGrid* grid = vtkExplicitStructuredGrid::SafeDownCast(ds);
  if (!grid)
  {
    vtkErrorMacro("Input dataset is not a " << this->GetClassName());
    return;
  }
  this->Superclass::CopyStructure(ds);
  this->InternalCopy(grid);
  this->SetCells(grid->GetCells());
}

//------------------------------------------------------------------------------
void vtkExplicitStructuredGrid::ShallowCopy(vtkDataObject* dataObject)
{
  vtkExplicitStructuredGrid* grid = vtkExplicitStructuredGrid::SafeDownCast(dataObject);
  if (this == grid)
  {
    return;
  }

  this->Superclass::ShallowCopy(dataObject);
  if (grid)
  {
    this->InternalCopy(grid);

    this->SetCells(grid->GetCells());

    if (grid->Links)
    {
      this->Links = vtkSmartPointer<vtkAbstractCellLinks>::Take(grid->Links->NewInstance());
      this->Links->SetDataSet(this);
      this->Links->ShallowCopy(grid->Links);
    }
    else
    {
      this->Links = nullptr;
    }
  }
}

//------------------------------------------------------------------------------
void vtkExplicitStructuredGrid::DeepCopy(vtkDataObject* dataObject)
{
  auto mkhold = vtkMemkindRAII(this->GetIsInMemkind());

  vtkExplicitStructuredGrid* grid = vtkExplicitStructuredGrid::SafeDownCast(dataObject);
  this->Superclass::DeepCopy(dataObject);

  if (grid)
  {
    this->InternalCopy(grid);

    if (grid->Cells)
    {
      this->Cells = vtkSmartPointer<vtkCellArray>::New();
      this->Cells->DeepCopy(grid->Cells);
    }
    else
    {
      this->Cells = nullptr;
    }
    if (grid->Links)
    {
      this->Links = vtkSmartPointer<vtkAbstractCellLinks>::Take(grid->Links->NewInstance());
      this->Links->SetDataSet(this);
      this->Links->DeepCopy(grid->Links);
    }
    else
    {
      this->Links = nullptr;
    }
  }
}

//------------------------------------------------------------------------------
void vtkExplicitStructuredGrid::SetDimensions(int i, int j, int k)
{
  this->SetExtent(0, i - 1, 0, j - 1, 0, k - 1);
}

//------------------------------------------------------------------------------
void vtkExplicitStructuredGrid::SetDimensions(int dim[3])
{
  this->SetDimensions(dim[0], dim[1], dim[2]);
}

//------------------------------------------------------------------------------
void vtkExplicitStructuredGrid::SetExtent(int x0, int x1, int y0, int y1, int z0, int z1)
{
  this->Extent[0] = x0;
  this->Extent[1] = x1;
  this->Extent[2] = y0;
  this->Extent[3] = y1;
  this->Extent[4] = z0;
  this->Extent[5] = z1;

  if (this->Links)
  {
    this->Links->Initialize();
  }

  vtkIdType expectedCells = (this->Extent[1] - this->Extent[0]) *
    (this->Extent[3] - this->Extent[2]) * (this->Extent[5] - this->Extent[4]);

  vtkNew<vtkCellArray> cells;
  cells->UseFixedSize64BitStorage(8);
  this->SetCells(cells);

  // Initialize the cell array
  if (expectedCells > 0)
  {
    cells->AllocateEstimate(expectedCells, 8);
    vtkIdType ids[8] = { 0, 0, 0, 0, 0, 0, 0, 0 };
    for (vtkIdType i = 0; i < expectedCells; i++)
    {
      cells->InsertNextCell(8, ids);
    }
  }
}

//------------------------------------------------------------------------------
void vtkExplicitStructuredGrid::SetExtent(int extent[6])
{
  this->SetExtent(extent[0], extent[1], extent[2], extent[3], extent[4], extent[5]);
}

//------------------------------------------------------------------------------
void vtkExplicitStructuredGrid::BuildLinks()
{
  // Remove the old links if they are already built
  if (!this->Points)
  {
    return;
  }

  // Different types of links depending on whether the data can be edited after
  // initial creation.
  if (!this->Links)
  {
    if (!this->Editable)
    {
      this->Links = vtkSmartPointer<vtkStaticCellLinks>::New();
    }
    else
    {
      this->Links = vtkSmartPointer<vtkCellLinks>::New();
      static_cast<vtkCellLinks*>(this->Links.Get())->Allocate(this->GetNumberOfPoints());
    }
    this->Links->SetDataSet(this);
  }
  else if (this->Points->GetMTime() > this->Links->GetMTime())
  {
    this->Links->SetDataSet(this);
  }
  this->Links->BuildLinks();
}

//------------------------------------------------------------------------------
void vtkExplicitStructuredGrid::GenerateGhostArray(int zeroExt[6], bool vtkNotUsed(cellOnly))
{
  int extent[6];
  this->Information->Get(vtkDataObject::DATA_EXTENT(), extent);

  this->AllocateCellGhostArray();
  this->AllocatePointGhostArray();

  bool sameExtent = true;
  for (int i = 0; i < 6; i++)
  {
    if (extent[i] != zeroExt[i])
    {
      sameExtent = false;
      break;
    }
  }
  if (sameExtent)
  {
    return;
  }

  vtkUnsignedCharArray* ghostCells = this->GetCellGhostArray();

  vtkIdType index = 0;

  // Loop through the cells in this image.
  // Cells may be 2d or 1d ... Treat all as 3D
  if (extent[0] == extent[1])
  {
    ++extent[1];
    ++zeroExt[1];
  }
  if (extent[2] == extent[3])
  {
    ++extent[3];
    ++zeroExt[3];
  }
  if (extent[4] == extent[5])
  {
    ++extent[5];
    ++zeroExt[5];
  }

  // Loop
  for (int k = extent[4]; k < extent[5]; ++k)
  { // Determine the Manhattan distances to zero extent.
    int dk = 0;
    if (k < zeroExt[4])
    {
      dk = zeroExt[4] - k;
    }
    if (k >= zeroExt[5])
    {
      dk = k - zeroExt[5] + 1;
    }
    for (int j = extent[2]; j < extent[3]; ++j)
    {
      int dj = 0;
      if (j < zeroExt[2])
      {
        dj = zeroExt[2] - j;
      }
      if (j >= zeroExt[3])
      {
        dj = j - zeroExt[3] + 1;
      }
      for (int i = extent[0]; i < extent[1]; ++i)
      {
        int di = 0;
        if (i < zeroExt[0])
        {
          di = zeroExt[0] - i;
        }
        if (i >= zeroExt[1])
        {
          di = i - zeroExt[1] + 1;
        }
        // Compute Manhattan distance.
        int dist = di;
        dist = std::max(dj, dist);
        dist = std::max(dk, dist);
        unsigned char value = ghostCells->GetValue(index);
        if (dist > 0)
        {
          value |= vtkDataSetAttributes::DUPLICATECELL;
        }
        ghostCells->SetValue(index, value);
        index++;
      }
    }
  }
}

//------------------------------------------------------------------------------
void vtkExplicitStructuredGrid::ComputeFacesConnectivityFlagsArray()
{
  vtkIdType nbCells = this->GetNumberOfCells();

  const char* name = this->FacesConnectivityFlagsArrayName ? this->FacesConnectivityFlagsArrayName
                                                           : "ConnectivityFlags";
  this->SetFacesConnectivityFlagsArrayName(name);

  vtkNew<vtkUnsignedCharArray> connectivity;
  connectivity->SetName(name);
  connectivity->SetNumberOfComponents(1);
  connectivity->SetNumberOfTuples(nbCells);
  this->GetCellData()->AddArray(connectivity.GetPointer());

  for (vtkIdType c = 0; c < nbCells; c++)
  {
    vtkIdType* cellPtsIds = this->GetCellPoints(c);

    unsigned char mask = 0;
    vtkIdType neighbors[6];
    this->GetCellNeighbors(c, neighbors);
    for (int f = 0, n = 0; f < 6; f++, n += 8)
    {
      vtkIdType neighbor = neighbors[f];
      if (neighbor >= 0)
      {
        vtkIdType* neiCellPtsIds = this->GetCellPoints(neighbor);
        if (cellPtsIds[HEXAHEDRON_POINT_MAP[n + 0]] == neiCellPtsIds[HEXAHEDRON_POINT_MAP[n + 1]] &&
          cellPtsIds[HEXAHEDRON_POINT_MAP[n + 2]] == neiCellPtsIds[HEXAHEDRON_POINT_MAP[n + 3]] &&
          cellPtsIds[HEXAHEDRON_POINT_MAP[n + 4]] == neiCellPtsIds[HEXAHEDRON_POINT_MAP[n + 5]] &&
          cellPtsIds[HEXAHEDRON_POINT_MAP[n + 6]] == neiCellPtsIds[HEXAHEDRON_POINT_MAP[n + 7]])
        {
          mask |= (1 << f);
        }
      }
    }
    connectivity->SetValue(c, mask);
  }
}

//------------------------------------------------------------------------------
bool vtkExplicitStructuredGrid::HasAnyBlankCells()
{
  return this->CellData->HasAnyGhostBitSet(vtkDataSetAttributes::HIDDENCELL);
}

//------------------------------------------------------------------------------
// Turn off a particular data cell.
void vtkExplicitStructuredGrid::BlankCell(vtkIdType cellId)
{
  vtkUnsignedCharArray* ghosts = this->GetCellGhostArray();
  if (!ghosts)
  {
    ghosts = this->AllocateCellGhostArray();
  }
  ghosts->SetValue(cellId, ghosts->GetValue(cellId) | vtkDataSetAttributes::HIDDENCELL);
  assert(!this->IsCellVisible(cellId));
}

//------------------------------------------------------------------------------
// Turn on a particular data cell.
void vtkExplicitStructuredGrid::UnBlankCell(vtkIdType cellId)
{
  vtkUnsignedCharArray* ghosts = this->GetCellGhostArray();
  if (ghosts)
  {
    ghosts->SetValue(cellId, ghosts->GetValue(cellId) & ~vtkDataSetAttributes::HIDDENCELL);
  }
}

//------------------------------------------------------------------------------
// Return non-zero if the specified cell is visible (i.e., not blanked)
unsigned char vtkExplicitStructuredGrid::IsCellVisible(vtkIdType cellId)
{
  vtkUnsignedCharArray* ghosts = this->GetCellGhostArray();
  return (ghosts && (ghosts->GetValue(cellId) & MASKED_CELL_VALUE)) ? 0 : 1;
}

//------------------------------------------------------------------------------
// Return non-zero if the specified cell is a ghost cell
unsigned char vtkExplicitStructuredGrid::IsCellGhost(vtkIdType cellId)
{
  vtkUnsignedCharArray* ghosts = this->GetCellGhostArray();
  return (ghosts && (ghosts->GetValue(cellId) & vtkDataSetAttributes::DUPLICATECELL)) ? 1 : 0;
}

//------------------------------------------------------------------------------
bool vtkExplicitStructuredGrid::HasAnyGhostCells()
{
  return this->CellData->HasAnyGhostBitSet(vtkDataSetAttributes::DUPLICATECELL);
}

//------------------------------------------------------------------------------
void vtkExplicitStructuredGrid::Crop(const int* updateExtent)
{
  this->Crop(this, updateExtent, false);
}

//------------------------------------------------------------------------------
void vtkExplicitStructuredGrid::Crop(
  vtkExplicitStructuredGrid* input, const int* updateExtent, bool generateOriginalCellIds)
{
  // The old extent
  int oldExtent[6];
  input->GetExtent(oldExtent);

  if (updateExtent[1] < updateExtent[0] || updateExtent[3] < updateExtent[2] ||
    updateExtent[5] < updateExtent[4])
  {
    return;
  }

  // The new extent
  int newExtent[6];
  for (int i = 0; i < 3; ++i)
  {
    newExtent[i * 2] = updateExtent[i * 2];
    newExtent[i * 2] = std::max(newExtent[i * 2], oldExtent[i * 2]);
    newExtent[i * 2 + 1] = updateExtent[i * 2 + 1];
    newExtent[i * 2 + 1] = std::min(newExtent[i * 2 + 1], oldExtent[i * 2 + 1]);
    if (newExtent[i * 2] == newExtent[i * 2 + 1])
    {
      if (newExtent[i * 2 + 1] == oldExtent[i * 2 + 1])
      {
        newExtent[i * 2] -= 1;
      }
      else
      {
        newExtent[i * 2 + 1] += 1;
      }
    }
  }

  // If extents already match, then we don't need to do anything.
  if (oldExtent[0] == newExtent[0] && oldExtent[1] == newExtent[1] &&
    oldExtent[2] == newExtent[2] && oldExtent[3] == newExtent[3] && oldExtent[4] == newExtent[4] &&
    oldExtent[5] == newExtent[5])
  {
    if (this != input)
    {
      this->ShallowCopy(input);
    }

    if (generateOriginalCellIds)
    {
      // CellArray which links the new cells ids with the old ones
      vtkNew<vtkIdTypeArray> originalCellIds;
      originalCellIds->SetName("vtkOriginalCellIds");
      originalCellIds->SetNumberOfComponents(1);
      this->GetCellData()->AddArray(originalCellIds.GetPointer());
      vtkIdType inSize = this->GetNumberOfCells();
      originalCellIds->Allocate(inSize);
      for (vtkIdType i = 0; i < inSize; i++)
      {
        originalCellIds->InsertValue(i, i);
      }
    }
  }
  else
  {
    // Check the points to avoid empty data objects.
    if (!input->GetPoints())
    {
      return;
    }

    // shallow copy points and point data to this ESG
    this->SetPoints(input->GetPoints());
    this->GetPointData()->ShallowCopy(input->GetPointData());

    vtkDebugMacro("Cropping Explicit Structured Grid");

    // Compute cells extent
    int oldCellExtent[6], newCellExtent[6];
    vtkStructuredData::GetCellExtentFromPointExtent(oldExtent, oldCellExtent);
    vtkStructuredData::GetCellExtentFromPointExtent(newExtent, newCellExtent);

    // Allocate necessary objects
    int outSize = (newCellExtent[1] - newCellExtent[0] + 1) *
      (newCellExtent[3] - newCellExtent[2] + 1) * (newCellExtent[5] - newCellExtent[4] + 1);
    this->SetExtent(newExtent);

    vtkCellData* inCD = input->GetCellData();
    vtkCellData* outCD = this->GetCellData();
    outCD->CopyAllocate(inCD, outSize, outSize);

    vtkNew<vtkCellArray> cells;
    cells->UseFixedSize64BitStorage(8);
    cells->AllocateEstimate(outSize, 8);

    // CellArray which links the new cells ids with the old ones
    vtkNew<vtkIdTypeArray> originalCellIds;
    if (generateOriginalCellIds)
    {
      originalCellIds->SetName("vtkOriginalCellIds");
      originalCellIds->SetNumberOfComponents(1);
      originalCellIds->Allocate(outSize);
    }

    // Browse input data and copy cell attributes to output
    for (int k = newCellExtent[4]; k <= newCellExtent[5]; ++k)
    {
      for (int j = newCellExtent[2]; j <= newCellExtent[3]; ++j)
      {
        for (int i = newCellExtent[0]; i <= newCellExtent[1]; ++i)
        {
          int idx = input->ComputeCellId(i, j, k);
          vtkNew<vtkIdList> ptIds;
          input->GetCellPoints(idx, ptIds);

          // insert cell and copy cell data
          vtkIdType nCellId = cells->InsertNextCell(ptIds);
          outCD->CopyData(inCD, idx, nCellId);

          if (generateOriginalCellIds)
          {
            originalCellIds->InsertValue(nCellId, idx);
          }
        }
      }
    }

    if (generateOriginalCellIds)
    {
      outCD->AddArray(originalCellIds);
      originalCellIds->Squeeze();
    }
    cells->Squeeze();
    this->SetCells(cells);

    if (this->GetLinks())
    {
      this->BuildLinks();
    }

    this->ComputeFacesConnectivityFlagsArray();
  }
}

//------------------------------------------------------------------------------
void vtkExplicitStructuredGrid::ReportReferences(vtkGarbageCollector* collector)
{
  this->Superclass::ReportReferences(collector);
  vtkGarbageCollectorReport(collector, this->Links, "Links");
}

//------------------------------------------------------------------------------
unsigned long vtkExplicitStructuredGrid::GetActualMemorySize()
{
  unsigned long size = this->Superclass::GetActualMemorySize();

  if (this->Cells)
  {
    size += this->Cells->GetActualMemorySize();
  }

  if (this->Links)
  {
    size += this->Links->GetActualMemorySize();
  }

  return size;
}

//------------------------------------------------------------------------------
void vtkExplicitStructuredGrid::PrintSelf(ostream& os, vtkIndent indent)
{
  this->Superclass::PrintSelf(os, indent);

  int dim[3];
  this->GetDimensions(dim);
  os << indent << "Dimensions: (" << dim[0] << ", " << dim[1] << ", " << dim[2] << ")\n";

  os << indent << "Extent: (" << this->Extent[0] << ", " << this->Extent[1] << ", "
     << this->Extent[2] << ", " << this->Extent[3] << ", " << this->Extent[4] << ", "
     << this->Extent[5] << ")\n";
}

//------------------------------------------------------------------------------
// Override this method because of blanking
void vtkExplicitStructuredGrid::ComputeScalarRange()
{
  if (this->GetMTime() > this->ScalarRangeComputeTime)
  {
    vtkDataArray* ptScalars = this->PointData->GetScalars();
    vtkDataArray* cellScalars = this->CellData->GetScalars();

    double ptRange[2];
    ptRange[0] = VTK_DOUBLE_MAX;
    ptRange[1] = VTK_DOUBLE_MIN;
    if (ptScalars)
    {
      int num = this->GetNumberOfPoints();
      for (int id = 0; id < num; id++)
      {
        double s = ptScalars->GetComponent(id, 0);
        ptRange[0] = std::min(s, ptRange[0]);
        ptRange[1] = std::max(s, ptRange[1]);
      }
    }

    double cellRange[2];
    cellRange[0] = ptRange[0];
    cellRange[1] = ptRange[1];
    if (cellScalars)
    {
      int num = this->GetNumberOfCells();
      for (int id = 0; id < num; id++)
      {
        double s = cellScalars->GetComponent(id, 0);
        cellRange[0] = std::min(s, cellRange[0]);
        cellRange[1] = std::max(s, cellRange[1]);
      }
    }

    this->ScalarRange[0] = (cellRange[0] >= VTK_DOUBLE_MAX ? 0.0 : cellRange[0]);
    this->ScalarRange[1] = (cellRange[1] <= VTK_DOUBLE_MIN ? 1.0 : cellRange[1]);

    this->ScalarRangeComputeTime.Modified();
  }
}

//------------------------------------------------------------------------------
vtkExplicitStructuredGrid* vtkExplicitStructuredGrid::GetData(vtkInformation* info)
{
  return info ? vtkExplicitStructuredGrid::SafeDownCast(info->Get(DATA_OBJECT())) : nullptr;
}

//------------------------------------------------------------------------------
vtkExplicitStructuredGrid* vtkExplicitStructuredGrid::GetData(vtkInformationVector* v, int i)
{
  return vtkExplicitStructuredGrid::GetData(v->GetInformationObject(i));
}

//------------------------------------------------------------------------------
void vtkExplicitStructuredGrid::CheckAndReorderFaces()
{
  // Check faces are on the correct axis
  this->InternalCheckAndReorderFaces(true);

  // Check if faces are mirrored or not
  this->InternalCheckAndReorderFaces(false);
}

//------------------------------------------------------------------------------
void vtkExplicitStructuredGrid::InternalCheckAndReorderFaces(bool swapFlag)
{
  // Find connected faces
  int foundFaces[3] = { -1, -1, -1 };
  this->FindConnectedFaces(foundFaces);

  // Compute correcting transformation
  int* ptsMap;
  int transformFlag[3] = { 0, 0, 0 };
  if (swapFlag)
  {
    vtkExplicitStructuredGrid::ComputeSwapFlag(foundFaces, transformFlag);
    ptsMap = SWAP_HEXAHEDRON_POINT_MAP;
  }
  else
  {
    vtkExplicitStructuredGrid::ComputeMirrorFlag(foundFaces, transformFlag);
    ptsMap = MIRROR_HEXAHEDRON_POINT_MAP;
  }

  // Reorder cell points accordingly
  this->ReorderCellsPoints(ptsMap, transformFlag);
}

//------------------------------------------------------------------------------
int vtkExplicitStructuredGrid::FindConnectedFaces(int foundFaces[3])
{
  int extent[6];
  this->GetExtent(extent);
  int nFoundFaces = 0;
  int neiAxisMod[3] = { 0, 0, 0 };
  vtkIdType ijkId[3];
  vtkIdType id0, neiCellId;
  vtkIdType* cellPtsIds;
  vtkIdType* neiCellPtsIds;

  // Look for continuous connected visible cells for each axis in the whole dataset
  // And identify connected faces
  for (ijkId[0] = extent[0]; ijkId[0] < extent[1]; ijkId[0]++)
  {
    for (ijkId[1] = extent[2]; ijkId[1] < extent[3]; ijkId[1]++)
    {
      for (ijkId[2] = extent[4]; ijkId[2] < extent[5]; ijkId[2]++)
      {
        id0 = this->ComputeCellId(ijkId[0], ijkId[1], ijkId[2]);
        if (this->IsCellVisible(id0))
        {
          for (int axis = 0; axis < 3; axis++)
          {
            // A visible cell have been found
            if (foundFaces[axis] == -1 && ijkId[axis] + 1 < extent[axis * 2 + 1])
            {
              neiAxisMod[axis]++;

              // find it's neighbour in the current axis
              neiCellId = this->ComputeCellId(
                ijkId[0] + neiAxisMod[0], ijkId[1] + neiAxisMod[1], ijkId[2] + neiAxisMod[2]);
              if (this->IsCellVisible(neiCellId))
              {
                // Find if they are connected and by which faces they are connected
                cellPtsIds = this->GetCellPoints(id0);
                neiCellPtsIds = this->GetCellPoints(neiCellId);
                for (int n = 0; n < 6; n++)
                {
                  if (cellPtsIds[HEXAHEDRON_POINT_MAP[n * 8 + 0]] ==
                      neiCellPtsIds[HEXAHEDRON_POINT_MAP[n * 8 + 1]] &&
                    cellPtsIds[HEXAHEDRON_POINT_MAP[n * 8 + 2]] ==
                      neiCellPtsIds[HEXAHEDRON_POINT_MAP[n * 8 + 3]] &&
                    cellPtsIds[HEXAHEDRON_POINT_MAP[n * 8 + 4]] ==
                      neiCellPtsIds[HEXAHEDRON_POINT_MAP[n * 8 + 5]] &&
                    cellPtsIds[HEXAHEDRON_POINT_MAP[n * 8 + 6]] ==
                      neiCellPtsIds[HEXAHEDRON_POINT_MAP[n * 8 + 7]])
                  {
                    // Correctly ordered faces would be the following
                    // Axis 0 -> face 1
                    // Axis 1 -> face 3
                    // Axis 2 -> face 5
                    // See vtkHexahedron.h for doc
                    foundFaces[axis] = n;
                    nFoundFaces++;
                    break;
                  }
                }
              }
              neiAxisMod[axis]--;
            }
          }
        }
      }
    }
  }
  vtkExplicitStructuredGrid::CheckConnectedFaces(nFoundFaces, foundFaces);
  return nFoundFaces;
}

//------------------------------------------------------------------------------
void vtkExplicitStructuredGrid::CheckConnectedFaces(int& nFoundFaces, int foundFaces[3])
{
  // Check foundFaces coherence and extrapolate to find a missing faces if any
  switch (nFoundFaces)
  {
    case 1:
      // Only one face have been found, we will probably draw incorrect interior faces
      for (int axis = 0; axis < 3; axis++)
      {
        int foundFace = foundFaces[axis];
        // Check if the foundFace point to another axis
        if (foundFace != -1 && !(foundFace == 2 * axis) && !(foundFace == 2 * axis + 1))
        {
          // A single foundFace which changes face on multiple axis is incoherent and can't be
          // extrapolated from so we remove it. This means that incorrect interior faces will be
          // drawn.
          foundFaces[axis] = -1;
          nFoundFaces--;
        }
      }
      break;
    case 2:
    {
      // Two faces have been found, we can try to extapolate the last one
      int missingFaceAxis = -1;
      for (int axis = 0; axis < 3; axis++)
      {
        if (foundFaces[axis] == -1)
        {
          // Identify the axis missing a face
          missingFaceAxis = axis;
          break;
        }
      }
      int foundFaceAxisSum = 0;
      int faceSwitch = 1;
      for (int axis = 0; axis < 3; axis++)
      {
        if (axis != missingFaceAxis)
        {
          int foundFace = foundFaces[axis];
          int foundFaceAxis = static_cast<int>(std::floor((static_cast<double>(foundFace)) / 2.0));

          // The sum of the found face axis will always be 3, so compute the sum
          foundFaceAxisSum += foundFaceAxis;
          if (!(foundFace == 2 * axis) && !(foundFace == 2 * axis + 1))
          {
            // when switching axis, we still need to know if there is some mirroring
            // this identify mirroring
            faceSwitch = foundFace - foundFaceAxis * 2;
          }
        }
      }
      // Compute the actual missing face
      foundFaces[missingFaceAxis] = (3 - foundFaceAxisSum) * 2 + faceSwitch;
      nFoundFaces++;
    }
    break;
    default:
      break;
  }
}

//------------------------------------------------------------------------------
void vtkExplicitStructuredGrid::ComputeSwapFlag(int foundFaces[3], int swap[3])
{
  int permuWise = 1;
  for (int axis = 0; axis < 3; axis++)
  {
    int foundFace = foundFaces[axis];
    if (foundFace != -1)
    {
      int foundFaceAxis = static_cast<int>(std::floor((static_cast<double>(foundFace)) / 2.0));
      if (foundFaceAxis != axis)
      {
        // Compute the swap
        swap[3 - foundFaceAxis - axis] = true;
        if (axis - foundFaceAxis == 1)
        {
          // In case of permutation, we need to know in which order the permutation have been done
          permuWise = 0;
        }
      }
    }
  }
  // Manage the permutation case
  if (swap[0] && swap[1] && swap[2])
  {
    swap[1 + permuWise] = false;
  }
}

//------------------------------------------------------------------------------
void vtkExplicitStructuredGrid::ComputeMirrorFlag(int foundFaces[3], int mirror[3])
{
  for (int axis = 0; axis < 3; axis++)
  {
    int foundFace = foundFaces[axis];
    if (foundFace != -1)
    {
      if (foundFace % 2 == 0)
      {
        mirror[axis] = true;
      }
    }
  }
}

//------------------------------------------------------------------------------
void vtkExplicitStructuredGrid::ReorderCellsPoints(const int* ptsMap, const int transformFlag[3])
{
  // Reorder all cells if necessary
  vtkIdType ids[8] = { 0, 0, 0, 0, 0, 0, 0, 0 };
  vtkIdType ids2[8] = { 0, 0, 0, 0, 0, 0, 0, 0 };
  vtkIdType npts, *pts, *ptsTmp, *ptsTmp2;
  vtkCellArray* cells = this->GetCells();
  for (vtkIdType cellId = 0; cellId < this->GetNumberOfCells(); cellId++)
  {
    if (this->IsCellVisible(cellId))
    {
      this->GetCellPoints(cellId, npts, pts);
      for (int ptIdx = 0; ptIdx < 8; ptIdx++)
      {
        ids[ptIdx] = pts[ptIdx];
      }
      ptsTmp = ids;
      ptsTmp2 = ids2;
      for (int axis = 0; axis < 3; axis++)
      {
        if (transformFlag[axis])
        {
          for (int ptIdx = 0; ptIdx < 8; ptIdx++)
          {
            ptsTmp2[ptIdx] = ptsTmp[ptsMap[axis * 8 + ptIdx]];
          }
          std::swap(ptsTmp, ptsTmp2);
        }
      }
      cells->ReplaceCellAtId(cellId, 8, ptsTmp);
      this->GetCellPoints(cellId, npts, pts);
    }
  }
}
VTK_ABI_NAMESPACE_END