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

  Program:   Visualization Toolkit
  Module:    vtkBSPCuts.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.

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

/*----------------------------------------------------------------------------
 Copyright (c) Sandia Corporation
 See Copyright.txt or http://www.paraview.org/HTML/Copyright.html for details.
----------------------------------------------------------------------------*/

#include "vtkBSPCuts.h"
#include "vtkKdNode.h"
#include "vtkKdTree.h"
#include "vtkObjectFactory.h"

vtkStandardNewMacro(vtkBSPCuts);

//------------------------------------------------------------------------------
vtkBSPCuts::vtkBSPCuts()
{
  this->Top = nullptr;
  this->NumberOfCuts = 0;
  this->Dim = nullptr;
  this->Coord = nullptr;
  this->Lower = nullptr;
  this->Upper = nullptr;
  this->LowerDataCoord = nullptr;
  this->UpperDataCoord = nullptr;
  this->Npoints = nullptr;
}

//------------------------------------------------------------------------------
vtkBSPCuts::~vtkBSPCuts()
{
  if (this->Top)
  {
    vtkBSPCuts::DeleteAllDescendants(this->Top);
    this->Top->Delete();
  }

  this->ResetArrays();
}

//------------------------------------------------------------------------------
void vtkBSPCuts::Initialize()
{
  if (this->Top)
  {
    vtkBSPCuts::DeleteAllDescendants(this->Top);
    this->Top->Delete();
    this->Top = nullptr;
  }
  this->ResetArrays();
  this->Superclass::Initialize();
}

//------------------------------------------------------------------------------
void vtkBSPCuts::ResetArrays()
{
  delete[] this->Dim;
  this->Dim = nullptr;

  delete[] this->Coord;
  this->Coord = nullptr;

  delete[] this->Lower;
  this->Lower = nullptr;

  delete[] this->Upper;
  this->Upper = nullptr;

  delete[] this->LowerDataCoord;
  this->LowerDataCoord = nullptr;

  delete[] this->UpperDataCoord;
  this->UpperDataCoord = nullptr;

  delete[] this->Npoints;
  this->Npoints = nullptr;

  this->NumberOfCuts = 0;
}
//------------------------------------------------------------------------------
void vtkBSPCuts::AllocateArrays(int nNodes)
{
  this->Dim = new int[nNodes];
  this->Coord = new double[nNodes];
  this->Lower = new int[nNodes];
  this->Upper = new int[nNodes];
  this->LowerDataCoord = new double[nNodes];
  this->UpperDataCoord = new double[nNodes];
  this->Npoints = new int[nNodes];
}
//------------------------------------------------------------------------------
void vtkBSPCuts::DeleteAllDescendants(vtkKdNode* nd)
{
  vtkKdNode* left = nd->GetLeft();
  vtkKdNode* right = nd->GetRight();

  if (left && left->GetLeft())
  {
    vtkBSPCuts::DeleteAllDescendants(left);
  }

  if (right && right->GetLeft())
  {
    vtkBSPCuts::DeleteAllDescendants(right);
  }

  if (left && right)
  {
    nd->DeleteChildNodes(); // undo AddChildNodes
    left->Delete();         // undo vtkKdNode::New()
    right->Delete();
  }
}

//------------------------------------------------------------------------------
void vtkBSPCuts::ShallowCopy(vtkDataObject* src)
{
  this->Superclass::ShallowCopy(src);
  vtkBSPCuts* srcCuts = vtkBSPCuts::SafeDownCast(src);

  this->ResetArrays();
  if (this->Top)
  {
    vtkBSPCuts::DeleteAllDescendants(this->Top);
    this->Top->Delete();
    this->Top = nullptr;
  }

  if (srcCuts)
  {
    if (srcCuts->Top)
    {
      this->CreateCuts(srcCuts->Top);
    }
  }
}

//------------------------------------------------------------------------------
void vtkBSPCuts::DeepCopy(vtkDataObject* src)
{
  this->Superclass::DeepCopy(src);
  this->ResetArrays();
  if (this->Top)
  {
    vtkBSPCuts::DeleteAllDescendants(this->Top);
    this->Top->Delete();
    this->Top = nullptr;
  }

  vtkBSPCuts* srcCuts = vtkBSPCuts::SafeDownCast(src);
  if (srcCuts)
  {
    if (srcCuts->Top)
    {
      this->CreateCuts(srcCuts->Top);
    }
  }
}

//------------------------------------------------------------------------------
void vtkBSPCuts::CreateCuts(vtkKdNode* kd)
{
  // Given a tree of vtkKdNodes, create the arrays that describe this
  // spatial partitioning.

  kd->GetBounds(this->Bounds);

  // preallocate vectors

  this->ResetArrays();

  int nNodes = vtkBSPCuts::CountNodes(kd);

  this->AllocateArrays(nNodes);

  // convert kd node tree to vector form

  this->NumberOfCuts = this->WriteArray(kd, 0);

  // keep a copy of vtkKdNode tree

  if (this->Top)
  {
    vtkBSPCuts::DeleteAllDescendants(this->Top);
    this->Top->Delete();
    this->Top = nullptr;
  }

  this->Top = vtkKdTree::CopyTree(kd);
}
//------------------------------------------------------------------------------
int vtkBSPCuts::CountNodes(vtkKdNode* kd)
{
  int leftCount = 0;
  int rightCount = 0;

  if (kd->GetLeft())
  {
    leftCount = vtkBSPCuts::CountNodes(kd->GetLeft());
    rightCount = vtkBSPCuts::CountNodes(kd->GetRight());
  }

  return leftCount + rightCount + 1;
}
//------------------------------------------------------------------------------
int vtkBSPCuts::WriteArray(vtkKdNode* kd, int loc)
{
  int nextloc = loc + 1;

  int dim = kd->GetDim(); // 0 (X), 1 (Y), 2 (Z)

  this->Npoints[loc] = kd->GetNumberOfPoints();

  if (kd->GetLeft())
  {
    this->Dim[loc] = dim;

    vtkKdNode* left = kd->GetLeft();
    vtkKdNode* right = kd->GetRight();

    this->Coord[loc] = left->GetMaxBounds()[dim];
    this->LowerDataCoord[loc] = left->GetMaxDataBounds()[dim];
    this->UpperDataCoord[loc] = right->GetMinDataBounds()[dim];

    int locleft = loc + 1;

    int locright = this->WriteArray(left, locleft);

    nextloc = this->WriteArray(right, locright);

    this->Lower[loc] = locleft;
    this->Upper[loc] = locright;
  }
  else
  {
    this->Dim[loc] = -1;
    this->Coord[loc] = 0.0;
    this->LowerDataCoord[loc] = 0.0;
    this->UpperDataCoord[loc] = 0.0;
    this->Lower[loc] = kd->GetID() * -1; // partition ID
    this->Upper[loc] = kd->GetID() * -1;
  }

  return nextloc; // next available array location
}
//------------------------------------------------------------------------------
void vtkBSPCuts::CreateCuts(double* bnds, int ncuts, int* dim, double* coord, int* lower,
  int* upper, double* lowerDataCoord, double* upperDataCoord, int* npoints)
{
  // Keep a copy of these arrays

  vtkBSPCuts::ResetArrays();
  vtkBSPCuts::AllocateArrays(ncuts);

  for (int i = 0; i < 6; i++)
  {
    this->Bounds[i] = bnds[i];
  }

  this->NumberOfCuts = ncuts;

  memcpy(this->Dim, dim, sizeof(int) * ncuts);
  memcpy(this->Coord, coord, sizeof(double) * ncuts);
  memcpy(this->Lower, lower, sizeof(int) * ncuts);
  memcpy(this->Upper, upper, sizeof(int) * ncuts);

  if (lowerDataCoord)
  {
    memcpy(this->LowerDataCoord, lowerDataCoord, sizeof(double) * ncuts);
  }
  else
  {
    delete[] this->LowerDataCoord;
    this->LowerDataCoord = nullptr;
  }

  if (upperDataCoord)
  {
    memcpy(this->UpperDataCoord, upperDataCoord, sizeof(double) * ncuts);
  }
  else
  {
    delete[] this->UpperDataCoord;
    this->UpperDataCoord = nullptr;
  }

  if (npoints)
  {
    memcpy(this->Npoints, npoints, sizeof(int) * ncuts);
  }
  else
  {
    delete[] this->Npoints;
    this->Npoints = nullptr;
  }

  // Now build tree from arrays

  if (this->Top)
  {
    vtkBSPCuts::DeleteAllDescendants(this->Top);
    this->Top->Delete();
    this->Top = nullptr;
  }

  this->Top = vtkKdNode::New();
  this->Top->SetBounds(bnds[0], bnds[1], bnds[2], bnds[3], bnds[4], bnds[5]);
  this->Top->SetDataBounds(bnds[0], bnds[1], bnds[2], bnds[3], bnds[4], bnds[5]);

  this->BuildTree(this->Top, 0);

  vtkBSPCuts::SetMinMaxId(this->Top);
}
//------------------------------------------------------------------------------
void vtkBSPCuts::BuildTree(vtkKdNode* kd, int idx)
{
  int dim = this->Dim[idx];

  if (this->Npoints)
  {
    kd->SetNumberOfPoints(this->Npoints[idx]);
  }

  if (this->Lower[idx] > 0)
  {
    vtkKdNode* left = vtkKdNode::New();
    vtkKdNode* right = vtkKdNode::New();

    kd->SetDim(dim);

    double b2[6];
    double db2[6];

    kd->GetBounds(b2);
    kd->GetDataBounds(db2);

    b2[dim * 2 + 1] = this->Coord[idx]; // new upper bound for lower half

    if (this->LowerDataCoord)
    {
      db2[dim * 2 + 1] = this->LowerDataCoord[idx];
    }
    else
    {
      db2[dim * 2 + 1] = this->Coord[idx];
    }

    left->SetBounds(b2[0], b2[1], b2[2], b2[3], b2[4], b2[5]);
    left->SetDataBounds(db2[0], db2[1], db2[2], db2[3], db2[4], db2[5]);

    kd->GetBounds(b2);
    kd->GetDataBounds(db2);

    b2[dim * 2] = this->Coord[idx]; // new lower bound for upper half

    if (this->UpperDataCoord)
    {
      db2[dim * 2] = this->UpperDataCoord[idx];
    }
    else
    {
      db2[dim * 2] = this->Coord[idx];
    }

    right->SetBounds(b2[0], b2[1], b2[2], b2[3], b2[4], b2[5]);
    right->SetDataBounds(db2[0], db2[1], db2[2], db2[3], db2[4], db2[5]);

    kd->AddChildNodes(left, right);

    this->BuildTree(left, this->Lower[idx]);
    this->BuildTree(right, this->Upper[idx]);
  }
  else
  {
    kd->SetID(this->Lower[idx] * -1); // partition ID of leaf node
  }
}
//------------------------------------------------------------------------------
void vtkBSPCuts::SetMinMaxId(vtkKdNode* kd)
{
  if (kd->GetLeft())
  {
    vtkBSPCuts::SetMinMaxId(kd->GetLeft());
    vtkBSPCuts::SetMinMaxId(kd->GetRight());
  }
  else
  {
    kd->SetMinID(kd->GetID());
    kd->SetMaxID(kd->GetID());
    return;
  }

  int min1 = kd->GetLeft()->GetMinID();
  int max1 = kd->GetLeft()->GetMaxID();
  int min2 = kd->GetRight()->GetMinID();
  int max2 = kd->GetRight()->GetMaxID();

  kd->SetMinID((min1 < min2) ? min1 : min2);
  kd->SetMaxID((max1 > max2) ? max1 : max2);
}

//------------------------------------------------------------------------------
int vtkBSPCuts::GetArrays(int len, int* dim, double* coord, int* lower, int* upper,
  double* lowerDataCoord, double* upperDataCoord, int* npoints)
{
  int l = (len < this->NumberOfCuts) ? len : this->NumberOfCuts;

  if (l < 1)
    return 1;

  if (dim)
  {
    memcpy(dim, this->Dim, l * sizeof(int));
  }
  if (coord)
  {
    memcpy(coord, this->Coord, l * sizeof(double));
  }
  if (lower)
  {
    memcpy(lower, this->Lower, l * sizeof(int));
  }
  if (upper)
  {
    memcpy(upper, this->Upper, l * sizeof(int));
  }

  if (lowerDataCoord && this->LowerDataCoord)
  {
    memcpy(lowerDataCoord, this->LowerDataCoord, l * sizeof(double));
  }
  if (upperDataCoord && this->UpperDataCoord)
  {
    memcpy(upperDataCoord, this->UpperDataCoord, l * sizeof(double));
  }
  if (npoints && this->Npoints)
  {
    memcpy(npoints, this->Npoints, l * sizeof(int));
  }

  return 0;
}

//------------------------------------------------------------------------------
int vtkBSPCuts::Equals(vtkBSPCuts* other, double tolerance)
{
#define EQ(x, y) (((x) - (y) <= tolerance) && (y) - (x) <= tolerance)
  if (!other)
  {
    return 0;
  }

  if (this->NumberOfCuts != other->NumberOfCuts)
  {
    return 0;
  }

  for (int i = 0; i < this->NumberOfCuts; i++)
  {
    if (this->Dim[i] != other->Dim[i])
    {
      return 0;
    }

    if (this->Dim[i] < 0)
    {
      // Leaf nodes have no real data.
      continue;
    }

    if (!EQ(this->Coord[i], other->Coord[i]))
    {
      return 0;
    }
    if (this->Lower[i] != other->Lower[i])
    {
      return 0;
    }
    if (this->Upper[i] != other->Upper[i])
    {
      return 0;
    }
    if (this->LowerDataCoord && other->LowerDataCoord)
    {
      if (!EQ(this->LowerDataCoord[i], other->LowerDataCoord[i]))
      {
        return 0;
      }
    }
    else if (this->LowerDataCoord || other->LowerDataCoord)
    {
      return 0;
    }
    if (this->UpperDataCoord && other->UpperDataCoord)
    {
      if (!EQ(this->UpperDataCoord[i], other->UpperDataCoord[i]))
      {
        return 0;
      }
    }
    else if (this->UpperDataCoord || other->UpperDataCoord)
    {
      return 0;
    }
    if (this->Npoints && other->Npoints)
    {
      if (this->Npoints[i] != other->Npoints[i])
      {
        return 0;
      }
    }
    else if (this->Npoints || other->Npoints)
    {
      return 0;
    }
  }

  return 1;
}

//------------------------------------------------------------------------------
void vtkBSPCuts::PrintArrays()
{
  int i;
  if (this->NumberOfCuts == 0)
  {
    return;
  }

  cout << "xmin: " << this->Bounds[0] << " xmax: " << this->Bounds[1] << endl;
  cout << "ymin: " << this->Bounds[2] << " ymax: " << this->Bounds[3] << endl;
  cout << "zmin: " << this->Bounds[4] << " zmax: " << this->Bounds[5] << endl;

  cout << "index / dimension / coordinate / lower region / upper region" << endl;

  for (i = 0; i < this->NumberOfCuts; i++)
  {
    cout << i << " / " << this->Dim[i] << " / " << this->Coord[i];
    cout << " / " << this->Lower[i] << " / " << this->Upper[i] << endl;
  }

  if (this->LowerDataCoord)
  {
    cout << "index / lower data bdry / upper data bdry / data points" << endl;

    for (i = 0; i < this->NumberOfCuts; i++)
    {
      cout << i << " / " << this->LowerDataCoord[i] << " / " << this->UpperDataCoord[i];
      cout << " / " << this->Npoints[i] << endl;
    }
  }
}
//------------------------------------------------------------------------------
void vtkBSPCuts::PrintTree()
{
  if (this->Top == nullptr)
  {
    return;
  }

  vtkBSPCuts::PrintTree_(this->Top, 0);
}
//------------------------------------------------------------------------------
void vtkBSPCuts::PrintTree_(vtkKdNode* kd, int depth)
{
  kd->PrintNode(depth);

  if (kd->GetLeft())
  {
    vtkBSPCuts::PrintTree_(kd->GetLeft(), depth + 1);
    vtkBSPCuts::PrintTree_(kd->GetRight(), depth + 1);
  }
}

//------------------------------------------------------------------------------
vtkBSPCuts* vtkBSPCuts::GetData(vtkInformation* info)
{
  return vtkBSPCuts::SafeDownCast(vtkDataObject::GetData(info));
}
//------------------------------------------------------------------------------
vtkBSPCuts* vtkBSPCuts::GetData(vtkInformationVector* v, int i)
{
  return vtkBSPCuts::SafeDownCast(vtkDataObject::GetData(v, i));
}

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

  os << indent << "Top: " << this->Top << endl;
  os << indent << "NumberOfCuts: " << this->NumberOfCuts << endl;
  os << indent << "Dim: " << this->Dim << endl;
  os << indent << "Coord: " << this->Coord << endl;
  os << indent << "Lower: " << this->Lower << endl;
  os << indent << "Upper: " << this->Upper << endl;
  os << indent << "LowerDataCoord: " << this->LowerDataCoord << endl;
  os << indent << "UpperDataCoord: " << this->UpperDataCoord << endl;
  os << indent << "Npoints: " << this->Npoints << endl;
}