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

  Program:   Visualization Toolkit
  Module:    $RCSfile: vtkExtentSplitter.cxx,v $

  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 "vtkExtentSplitter.h"

#include "vtkObjectFactory.h"

#include <vtkstd/map>
#include <vtkstd/queue>
#include <vtkstd/vector>

vtkCxxRevisionMacro(vtkExtentSplitter, "$Revision: 1.4 $");
vtkStandardNewMacro(vtkExtentSplitter);

//----------------------------------------------------------------------------
struct vtkExtentSplitterExtent
{
  int extent[6];
};

struct vtkExtentSplitterSource
{
  int extent[6];
  int priority;
};

struct vtkExtentSplitterSubExtent
{
  int extent[6];
  int source;
};

class vtkExtentSplitterInternals
{
public:
  typedef vtkstd::queue<vtkExtentSplitterExtent> QueueType;
  typedef vtkstd::map<int, vtkExtentSplitterSource> SourcesType;
  typedef vtkstd::vector<vtkExtentSplitterSubExtent> SubExtentsType;
  SourcesType Sources;
  QueueType Queue;
  SubExtentsType SubExtents;
};

//----------------------------------------------------------------------------
vtkExtentSplitter::vtkExtentSplitter()
{
  this->Internal = new vtkExtentSplitterInternals;
  this->PointMode = 0;
}

//----------------------------------------------------------------------------
vtkExtentSplitter::~vtkExtentSplitter()
{
  delete this->Internal;
}

//----------------------------------------------------------------------------
void vtkExtentSplitter::PrintSelf(ostream& os, vtkIndent indent)
{
  this->Superclass::PrintSelf(os, indent);
  vtkIndent nextIndent = indent.GetNextIndent();
  os << indent << "PointMode: " << this->PointMode << "\n";
  if(this->Internal->Sources.empty())
    {
    os << indent << "Extent Sources: (none)\n";
    }
  else
    {
    os << indent << "Extent Sources: (format = \"id priority: extent\")\n";
    for(vtkExtentSplitterInternals::SourcesType::const_iterator src =
          this->Internal->Sources.begin();
        src != this->Internal->Sources.end(); ++src)
      {
      const int* extent = src->second.extent;
      os << nextIndent << src->first
         << " " << src->second.priority << ": "
         << extent[0] << " " << extent[1] << "  "
         << extent[2] << " " << extent[3] << "  "
         << extent[4] << " " << extent[5] << "\n";
      }
    }
  os << indent << "Number of Extents in Queue: " << 
    (int)this->Internal->Queue.size() << "\n";
  if(this->Internal->SubExtents.empty())
    {
    os << indent << "SubExtents: (none)\n";
    }
  else
    {
    os << indent << "SubExtents: (format = \"id: extent\")\n";
    for(vtkExtentSplitterInternals::SubExtentsType::const_iterator i =
          this->Internal->SubExtents.begin();
        i != this->Internal->SubExtents.end(); ++i)
      {
      const int* extent = i->extent;
      os << nextIndent << i->source << ": "
         << extent[0] << " " << extent[1] << "  "
         << extent[2] << " " << extent[3] << "  "
         << extent[4] << " " << extent[5] << "\n";        
      }
    }
}

//----------------------------------------------------------------------------
void vtkExtentSplitter::AddExtentSource(int id, int priority, int x0, int x1,
                                        int y0, int y1, int z0, int z1)
{
  // Add the source.
  vtkExtentSplitterSource& source = this->Internal->Sources[id];
  source.extent[0] = x0;
  source.extent[1] = x1;
  source.extent[2] = y0;
  source.extent[3] = y1;
  source.extent[4] = z0;
  source.extent[5] = z1;
  source.priority = priority;
  
  // Previously calculated sub-extents are now invalid.
  this->Internal->SubExtents.clear();
}

//----------------------------------------------------------------------------
void vtkExtentSplitter::AddExtentSource(int id, int priority, int* extent)
{
  this->AddExtentSource(id, priority, extent[0], extent[1], extent[2],
                        extent[3], extent[4], extent[5]);
}

//----------------------------------------------------------------------------
void vtkExtentSplitter::RemoveExtentSource(int id)
{
  // Remove the source.
  this->Internal->Sources.erase(id);

  // Previously calculated sub-extents are now invalid.
  this->Internal->SubExtents.clear();
}

//----------------------------------------------------------------------------
void vtkExtentSplitter::RemoveAllExtentSources()
{
  // Clear the set of sources.
  this->Internal->Sources.clear();
  
  // Previously calculated sub-extents are now invalid.
  this->Internal->SubExtents.clear();
}

//----------------------------------------------------------------------------
void vtkExtentSplitter::AddExtent(int x0, int x1, int y0, int y1,
                                  int z0, int z1)
{
  // Queue the extent.
  vtkExtentSplitterExtent e;
  e.extent[0] = x0;
  e.extent[1] = x1;
  e.extent[2] = y0;
  e.extent[3] = y1;
  e.extent[4] = z0;
  e.extent[5] = z1;
  this->Internal->Queue.push(e);
  
  // Previously calculated sub-extents are now invalid.
  this->Internal->SubExtents.clear();
}

//----------------------------------------------------------------------------
void vtkExtentSplitter::AddExtent(int* extent)
{
  this->AddExtent(extent[0], extent[1], extent[2],
                  extent[3], extent[4], extent[5]);
}

//----------------------------------------------------------------------------
int vtkExtentSplitter::GetNumberOfSubExtents()
{
  return static_cast<int>(this->Internal->SubExtents.size());
}

//----------------------------------------------------------------------------
int* vtkExtentSplitter::GetSubExtent(int index)
{
  if(index < 0 || index >= this->GetNumberOfSubExtents())
    {
    static int dummy[6] = {0, -1, 0, -1, 0, -1};
    vtkErrorMacro("SubExtent index " << index << " is out of range [0,"
                  << this->GetNumberOfSubExtents()-1 << "]");
    return dummy;
    }
  return this->Internal->SubExtents[index].extent;
}

//----------------------------------------------------------------------------
void vtkExtentSplitter::GetSubExtent(int index, int* extent)
{
  if(index < 0 || index >= this->GetNumberOfSubExtents())
    {
    vtkErrorMacro("SubExtent index " << index << " is out of range [0,"
                  << this->GetNumberOfSubExtents()-1 << "]");
    extent[0] = 0;
    extent[1] = -1;
    extent[2] = 0;
    extent[3] = -1;
    extent[4] = 0;
    extent[5] = -1;
    }
  else
    {
    int i;
    int* e = this->Internal->SubExtents[index].extent;
    for(i=0; i < 6; ++i)
      {
      extent[i] = e[i];
      }
    }
}

//----------------------------------------------------------------------------
int vtkExtentSplitter::GetSubExtentSource(int index)
{
  if(index < 0 || index >= this->GetNumberOfSubExtents())
    {
    vtkErrorMacro("SubExtent index " << index << " is out of range [0,"
                  << this->GetNumberOfSubExtents()-1 << "]");
    return -1;
    }
  return this->Internal->SubExtents[index].source;  
}

//----------------------------------------------------------------------------
int vtkExtentSplitter::ComputeSubExtents()
{
  // Assume success.
  int result = 1;
  
  vtkExtentSplitterInternals::SubExtentsType subExtents;
  int bestPriority;
  int dimensionality = 0;
  
  while(!this->Internal->Queue.empty())
    {
    // Pop the next extent off the queue.
    vtkExtentSplitterExtent e = this->Internal->Queue.front();
    this->Internal->Queue.pop();
    
    // In non-PointMode, intersections must have the same topological
    // dimension as the original extent.  This will prevent
    // high-priority source extents from repeatedly producing
    // single-point-wide intersections.
    if(!this->PointMode)
      {
      dimensionality = (((e.extent[1]-e.extent[0] > 0)?1:0)+
                        ((e.extent[3]-e.extent[2] > 0)?1:0)+
                        ((e.extent[5]-e.extent[4] > 0)?1:0));
      }
    
    // Intersect the extent with each extent source.
    subExtents.clear();
    bestPriority = -1;
    vtkExtentSplitterSubExtent se;
    for(vtkExtentSplitterInternals::SourcesType::const_iterator src =
          this->Internal->Sources.begin();
        src != this->Internal->Sources.end(); ++src)
      {
      se.source = src->first;
      if(this->IntersectExtents(e.extent, src->second.extent, se.extent) &&
         (this->PointMode ||
          (dimensionality == (((se.extent[1]-se.extent[0] > 0)?1:0)+
                              ((se.extent[3]-se.extent[2] > 0)?1:0)+
                              ((se.extent[5]-se.extent[4] > 0)?1:0)))))
        {
        // Non-zero intersection volume.  Add the extent as a
        // candidate for best extent.
        if(src->second.priority > bestPriority)
          {
          // New highest priority.  Clear previous intersections with
          // lower priority.
          subExtents.clear();
          subExtents.push_back(se);
          bestPriority = src->second.priority;
          }
        else if(src->second.priority == bestPriority)
          {
          // Matching priority.  Add this intersection to the list.
          subExtents.push_back(se);
          }
        }
      }
    
    // Check whether any extent sources intersected the extent.
    if(subExtents.empty())
      {
      // No extent source intersected the extent.  Add the extent as
      // an error.
      int i;
      result = 0;
      se.source = -1;
      for(i=0; i < 6; ++i)
        {
        se.extent[i] = e.extent[i];
        }
      this->Internal->SubExtents.push_back(se);
      }
    else
      {
      // Choose the extent intersection with the largest volume.
      int bestVolume = 0;
      int bestIndex = 0;
      int i;
      for(i=0; i < static_cast<int>(subExtents.size()); ++i)
        {
        int* extent = subExtents[i].extent;
        int volume = ((extent[1]-extent[0]+1)*
                      (extent[3]-extent[2]+1)*
                      (extent[5]-extent[4]+1));
        if(volume > bestVolume)
          {
          bestVolume = volume;
          bestIndex = i;
          }
        }
      
      // Add this extent source with its sub-extent.
      se.source = subExtents[bestIndex].source;
      for(i=0; i < 6; ++i)
        {
        se.extent[i] = subExtents[bestIndex].extent[i];
        }
      this->Internal->SubExtents.push_back(se);
      
      // Subtract the sub-extent from the extent and split the rest of
      // the volume into more sub-extents.
      this->SplitExtent(e.extent, se.extent);
      }
    }
  
  return result;
}

//----------------------------------------------------------------------------
void vtkExtentSplitter::SplitExtent(int* extent, int* subextent)
{
  // Subtract the volume described by subextent from that described by
  // extent.  Split the remaining region into rectangular solids and
  // queue them as additional extents.  We may assume that subextent
  // is completely contained by extent.
  vtkExtentSplitterExtent e;
  
  // In PointMode, there are no cell data, so we can skip over cells.
  int pointMode = this->PointMode?1:0;
  
  // Split with xy-planes.
  if(extent[4] < subextent[4])
    {
    e.extent[0] = extent[0];
    e.extent[1] = extent[1];
    e.extent[2] = extent[2];
    e.extent[3] = extent[3];
    e.extent[4] = extent[4];
    e.extent[5] = subextent[4]-pointMode;
    this->Internal->Queue.push(e);
    
    extent[4] = subextent[4];
    }
  if(extent[5] > subextent[5])
    {
    e.extent[0] = extent[0];
    e.extent[1] = extent[1];
    e.extent[2] = extent[2];
    e.extent[3] = extent[3];
    e.extent[4] = subextent[5]+pointMode;
    e.extent[5] = extent[5];
    this->Internal->Queue.push(e);
    
    extent[5] = subextent[5];
    }
  
  // Split with xz-planes.
  if(extent[2] < subextent[2])
    {
    e.extent[0] = extent[0];
    e.extent[1] = extent[1];
    e.extent[2] = extent[2];
    e.extent[3] = subextent[2]-pointMode;
    e.extent[4] = extent[4];
    e.extent[5] = extent[5];
    this->Internal->Queue.push(e);
    
    extent[2] = subextent[2];
    }
  if(extent[3] > subextent[3])
    {
    e.extent[0] = extent[0];
    e.extent[1] = extent[1];
    e.extent[2] = subextent[3]+pointMode;
    e.extent[3] = extent[3];
    e.extent[4] = extent[4];
    e.extent[5] = extent[5];
    this->Internal->Queue.push(e);
    
    extent[3] = subextent[3];
    }
  
  // Split with yz-planes.
  if(extent[0] < subextent[0])
    {
    e.extent[0] = extent[0];
    e.extent[1] = subextent[0]-pointMode;
    e.extent[2] = extent[2];
    e.extent[3] = extent[3];
    e.extent[4] = extent[4];
    e.extent[5] = extent[5];
    this->Internal->Queue.push(e);
    
    extent[0] = subextent[0];
    }
  if(extent[1] > subextent[1])
    {
    e.extent[0] = subextent[1]+pointMode;
    e.extent[1] = extent[1];
    e.extent[2] = extent[2];
    e.extent[3] = extent[3];
    e.extent[4] = extent[4];
    e.extent[5] = extent[5];
    this->Internal->Queue.push(e);
    
    // Leave this line out because the value will not be used:
    //extent[1] = subextent[1];
    }
  
  // At this point, we should have extent[i] == subextent[i] for 0 <= i < 6.
  // No more volume remains.
}

//----------------------------------------------------------------------------
int vtkExtentSplitter::IntersectExtents(const int* extent1, const int* extent2,
                                        int* result)
{
  if((extent1[0] > extent2[1]) || (extent1[2] > extent2[3]) ||
     (extent1[4] > extent2[5]) || (extent1[1] < extent2[0]) ||
     (extent1[3] < extent2[2]) || (extent1[5] < extent2[4]))
    {
    // No intersection of extents.
    return 0;
    }
  
  // Get the intersection of the extents.
  result[0] = this->Max(extent1[0], extent2[0]);
  result[1] = this->Min(extent1[1], extent2[1]);
  result[2] = this->Max(extent1[2], extent2[2]);
  result[3] = this->Min(extent1[3], extent2[3]);
  result[4] = this->Max(extent1[4], extent2[4]);
  result[5] = this->Min(extent1[5], extent2[5]);
  
  return 1;
}

//----------------------------------------------------------------------------
int vtkExtentSplitter::Min(int a, int b)
{
  return (a < b)? a : b;
}

//----------------------------------------------------------------------------
int vtkExtentSplitter::Max(int a, int b)
{
  return (a > b)? a : b;
}