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

Program:   ParaView
Module:    vtkCleanUnstructuredGridCells.cxx

Copyright (c) Kitware, Inc.
All rights reserved.
See Copyright.txt or http://www.paraview.org/HTML/Copyright.html 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 "vtkCleanUnstructuredGridCells.h"

#include "vtkCell.h"
#include "vtkCellData.h"
#include "vtkCollection.h"
#include "vtkInformation.h"
#include "vtkInformationVector.h"
#include "vtkIntArray.h"
#include "vtkObjectFactory.h"
#include "vtkPointData.h"
#include "vtkPoints.h"
#include "vtkUnstructuredGrid.h"

#include <set>

vtkStandardNewMacro(vtkCleanUnstructuredGridCells);

//----------------------------------------------------------------------------
vtkCleanUnstructuredGridCells::vtkCleanUnstructuredGridCells()
{
}

//----------------------------------------------------------------------------
vtkCleanUnstructuredGridCells::~vtkCleanUnstructuredGridCells()
{
}

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

//----------------------------------------------------------------------------
int vtkCleanUnstructuredGridCells::RequestData(vtkInformation* vtkNotUsed(request),
  vtkInformationVector** inputVector, vtkInformationVector* outputVector)
{
  vtkInformation* inInfo = inputVector[0]->GetInformationObject(0);
  vtkInformation* outInfo = outputVector->GetInformationObject(0);

  vtkUnstructuredGrid* input =
    vtkUnstructuredGrid::SafeDownCast(inInfo->Get(vtkDataObject::DATA_OBJECT()));
  vtkUnstructuredGrid* output =
    vtkUnstructuredGrid::SafeDownCast(outInfo->Get(vtkDataObject::DATA_OBJECT()));

  if (input->GetNumberOfCells() == 0)
  {
    // set up a ugrid with same data arrays as input, but
    // no points, cells or data.
    output->Allocate(1);
    output->GetPointData()->CopyAllocate(input->GetPointData(), VTK_CELL_SIZE);
    vtkPoints* pts = vtkPoints::New();
    pts->SetDataTypeToDouble();

    output->SetPoints(pts);
    pts->Delete();
    return 1;
  }

  // Copy over the original points. Assume there are no degenerate points.
  output->SetPoints(input->GetPoints());

  // remove duplicate cells
  std::set<std::set<int> > cellSet;
  std::set<std::set<int> >::iterator cellIter;

  // Now copy the cells.
  vtkIdList* cellPoints = vtkIdList::New();
  const int numberOfCells = input->GetNumberOfCells();
  vtkIdType progressStep = numberOfCells / 100;
  if (progressStep == 0)
  {
    progressStep = 1;
  }

  output->Allocate(numberOfCells);
  int ndeg = 0;
  int ndup = 0;

  for (int id = 0; id < numberOfCells; id++)
  {
    if (id % progressStep == 0)
    {
      this->UpdateProgress(0.8 + 0.2 * (static_cast<float>(id) / numberOfCells));
    }

    // duplicate points do not make poly verticies or triangle
    // strips degenerate so don't remove them
    int cellType = input->GetCellType(id);
    if (cellType == VTK_POLY_VERTEX || cellType == VTK_TRIANGLE_STRIP)
    {
      input->GetCellPoints(id, cellPoints);
      output->InsertNextCell(cellType, cellPoints);
      continue;
    }

    input->GetCellPoints(id, cellPoints);
    std::set<int> nn;
    for (int i = 0; i < cellPoints->GetNumberOfIds(); i++)
    {
      int cellPtId = cellPoints->GetId(i);
      nn.insert(cellPtId);
    }

    // this conditional may generate non-referenced nodes
    cellIter = cellSet.find(nn);

    // only copy a cell to the output if it is neither degenerate nor duplicate
    if (nn.size() == static_cast<unsigned int>(cellPoints->GetNumberOfIds()) &&
      cellIter == cellSet.end())
    {
      output->InsertNextCell(input->GetCellType(id), cellPoints);
      cellSet.insert(nn);
    }
    else if (nn.size() != static_cast<unsigned int>(cellPoints->GetNumberOfIds()))
    {
      ndeg++; // a node appeared more than once in a cell
    }
    else if (cellIter != cellSet.end())
    {
      ndup++; // cell has duplicate(s)
    }
  }
  if (ndeg)
  {
    vtkDebugMacro(<< "vtkCleanUnstructuredGridCells : WARNING, " << ndeg
                  << " degenerated cells (i.e. cells with coincident nodes) have been"
                  << " removed, which may result in disconnected nodes. It is"
                  << " recommended to clean the grid." << endl);
  }

  if (ndup)
  {
    vtkDebugMacro(<< "vtkCleanUnstructuredGridCells : " << ndup
                  << " duplicate cells (multiple instances of a cell) have been"
                  << " removed." << endl);

    cellPoints->Delete();
    output->Squeeze();
  }

  return 1;
}

int vtkCleanUnstructuredGridCells::FillInputPortInformation(
  int vtkNotUsed(port), vtkInformation* info)
{
  info->Set(vtkAlgorithm::INPUT_REQUIRED_DATA_TYPE(), "vtkUnstructuredGrid");
  return 1;
}
