/*=========================================================================

  Program:   Visualization Toolkit
  Module:    vtkPixelExtent.cxx

  Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
  All rights reserved.
  See Copyright.txt or http://www.kitware.com/Copyright.htm for details.

     This software is distributed WITHOUT ANY WARRANTY; without even
     the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
     PURPOSE.  See the above copyright notice for more information.

=========================================================================*/
#include "vtkPixelExtent.h"

using std::deque;
using std::ostream;

//------------------------------------------------------------------------------
vtkPixelExtent vtkPixelExtent::Grow(
  const vtkPixelExtent& inputExt, const vtkPixelExtent& problemDomain, int n)
{
  vtkPixelExtent outputExt = vtkPixelExtent::Grow(inputExt, n);
  outputExt &= problemDomain;
  return outputExt;
}

//------------------------------------------------------------------------------
vtkPixelExtent vtkPixelExtent::Grow(const vtkPixelExtent& inputExt, int n)
{
  vtkPixelExtent outputExt(inputExt);
  outputExt.Grow(0, n);
  outputExt.Grow(1, n);
  return outputExt;
}

//------------------------------------------------------------------------------
vtkPixelExtent vtkPixelExtent::GrowLow(const vtkPixelExtent& inputExt, int q, int n)
{
  vtkPixelExtent outputExt(inputExt);
  outputExt[2 * q] -= n;
  return outputExt;
}

//------------------------------------------------------------------------------
vtkPixelExtent vtkPixelExtent::GrowHigh(const vtkPixelExtent& inputExt, int q, int n)
{
  vtkPixelExtent outputExt(inputExt);
  outputExt[2 * q + 1] += n;
  return outputExt;
}

//------------------------------------------------------------------------------
vtkPixelExtent vtkPixelExtent::Shrink(const vtkPixelExtent& inputExt, int n)
{
  return vtkPixelExtent::Grow(inputExt, -n);
}

//------------------------------------------------------------------------------
vtkPixelExtent vtkPixelExtent::Shrink(
  const vtkPixelExtent& inputExt, const vtkPixelExtent& problemDomain, int n)
{
  vtkPixelExtent outputExt(inputExt);

  outputExt.Grow(0, -n);
  outputExt.Grow(1, -n);

  // don't shrink at the problem domain
  // because you don't grow outside the problem domain.
  for (int i = 0; i < 4; ++i)
  {
    if (inputExt[i] == problemDomain[i])
    {
      outputExt[i] = problemDomain[i];
    }
  }

  return outputExt;
}

//------------------------------------------------------------------------------
vtkPixelExtent vtkPixelExtent::CellToNode(const vtkPixelExtent& inputExt)
{
  vtkPixelExtent outputExt(inputExt);
  ++outputExt[1];
  ++outputExt[3];
  return outputExt;
}

//------------------------------------------------------------------------------
vtkPixelExtent vtkPixelExtent::NodeToCell(const vtkPixelExtent& inputExt)
{
  vtkPixelExtent outputExt(inputExt);
  --outputExt[1];
  --outputExt[3];
  return outputExt;
}

//------------------------------------------------------------------------------
void vtkPixelExtent::Shift(int* ij, int n)
{
  ij[0] += n;
  ij[1] += n;
}

//------------------------------------------------------------------------------
void vtkPixelExtent::Shift(int* ij, int* n)
{
  ij[0] += n[0];
  ij[1] += n[1];
}

//------------------------------------------------------------------------------
void vtkPixelExtent::Split(
  int i1, int j1, const vtkPixelExtent& ext, deque<vtkPixelExtent>& newExts)
{
  // cell is inside, split results in as many as
  // 4 new extents. check for each one.
  int i0 = i1 - 1;
  int j0 = j1 - 1;

  int outside = 1;

  // lower left
  if (ext.Contains(i0, j0))
  {
    newExts.emplace_back(ext[0], i0, ext[2], j0);
    outside = 0;
  }
  // lower right
  if (ext.Contains(i1, j0))
  {
    newExts.emplace_back(i1, ext[1], ext[2], j0);
    outside = 0;
  }
  // upper left
  if (ext.Contains(i0, j1))
  {
    newExts.emplace_back(ext[0], i0, j1, ext[3]);
    outside = 0;
  }
  // upper right
  if (ext.Contains(i1, j1))
  {
    newExts.emplace_back(i1, ext[1], j1, ext[3]);
    outside = 0;
  }

  // split cell is outside, pass through
  if (outside)
  {
    newExts.push_back(ext);
    return;
  }
}

//------------------------------------------------------------------------------
void vtkPixelExtent::Subtract(
  const vtkPixelExtent& A, const vtkPixelExtent& B, deque<vtkPixelExtent>& C)
{
  // split method requires split point inside the extent
  vtkPixelExtent I(A);
  I &= B;

  if (I.Empty())
  {
    // do nothing if disjoint
    C.push_back(A);
    return;
  }
  if (B.Contains(A))
  {
    // if A is covered by B then remove A
    return;
  }

  // split left and below this cells
  I.CellToNode();

  deque<vtkPixelExtent> tmpA0;
  tmpA0.push_back(A);
  for (int q = 0; q < 4; ++q)
  {
    const int ids[8] = { 0, 2, 1, 2, 1, 3, 0, 3 };
    int qq = 2 * q;
    int i = I[ids[qq]];
    int j = I[ids[qq + 1]];
    deque<vtkPixelExtent> tmpA1;
    while (!tmpA0.empty())
    {
      vtkPixelExtent ext = tmpA0.back();
      tmpA0.pop_back();
      vtkPixelExtent::Split(i, j, ext, tmpA1);
    }
    tmpA0 = tmpA1;
  }

  // remove anything covered by B
  size_t n = tmpA0.size();
  for (size_t q = 0; q < n; ++q)
  {
    const vtkPixelExtent& ext = tmpA0[q];
    if (!B.Contains(ext))
    {
      C.push_back(ext);
    }
  }
}

//------------------------------------------------------------------------------
void vtkPixelExtent::Merge(deque<vtkPixelExtent>& exts)
{
  size_t ne = exts.size();

  // working in point space simplifies things because
  // points overlap in adjacent extents while cells do not
  deque<vtkPixelExtent> tmpExts(ne);
  for (size_t t = 0; t < ne; ++t)
  {
    vtkPixelExtent ext(exts[t]);
    ext.CellToNode();
    tmpExts[t] = ext;
  }

  // one pass for each direction
  for (int q = 0; q < 2; ++q)
  {
    int qq = 2 * q;
    // consider each extent as a target to be merged
    for (size_t t = 0; t < ne; ++t)
    {
      // if a merger occurs the merged extent is added
      // as a new target with the constituents marked empty
      // and the current pass is terminated early
      bool nextPass = false;

      // current target
      vtkPixelExtent& ext0 = tmpExts[t];
      if (ext0.Empty())
      {
        // was merged in preceding pass
        continue;
      }

      for (size_t c = 0; c < ne; ++c)
      {
        if (c == t)
        {
          // don't attempt merge with self
          continue;
        }

        // candidate
        vtkPixelExtent& ext1 = tmpExts[c];
        if (ext1.Empty())
        {
          // was merged in preceding pass
          continue;
        }

        // must be same size and coordinate in merge dir
        if ((ext0[qq] == ext1[qq]) && (ext0[qq + 1] == ext1[qq + 1]))
        {
          // must overlap overlap
          vtkPixelExtent ext2(ext0);
          ext2 &= ext1;
          if (!ext2.Empty())
          {
            // merge and add as new target
            // in a later pass
            vtkPixelExtent ext3(ext0);
            ext3 |= ext1;
            tmpExts.push_back(ext3);
            ++ne;

            // mark the merged extents empty
            ext0.Clear();
            ext1.Clear();

            // move to next target
            nextPass = true;
          }
        }
        if (nextPass)
        {
          break;
        }
      }
    }
  }
  // discard merged targets copy to output
  exts.clear();
  for (size_t t = 0; t < ne; ++t)
  {
    vtkPixelExtent& ext = tmpExts[t];
    if (!ext.Empty())
    {
      ext.NodeToCell();
      exts.push_back(ext);
    }
  }
}

//*****************************************************************************
ostream& operator<<(ostream& os, const vtkPixelExtent& ext)
{
  if (ext.Empty())
  {
    os << "(empty)";
  }
  else
  {
    os << "(" << ext[0] << ", " << ext[1] << ", " << ext[2] << ", " << ext[3] << ")";
  }
  return os;
}