#ifndef CONVEXREGIONSD2_H
#define CONVEXREGIONSD2_H

#include <cassert>
#include <vector>
using namespace std;

#include <halfspaceD2.h>
#include <partitionspace.h>
#include <polytopeD2linked.h>
#include <typedefs.h>

/*!
\brief Construct regions by cutting specified regions
 with a 2D half spaces. 

The region is assumed to be convex.
*/
template< typename PT, typename PD >
class convexregionsD2
{
public:

  /** List of points. */
  vector< PT > & pts;
  /** Linked region that are convex. */
  vector< polytopeD2linked > vi;

  /** Pass in the global points. */
  convexregionsD2(vector<PT> & pts_);

  /** Split the region with the half space. */
  boolc split(uintc k, halfspaceD2<PT,PD> const & h);

  /** When split fails if the half space touches a
      line segment this flag is set. */
  static bool splittouchesface;
  /** When split fails if the half space touches a 
      one point this flag is set. */
  static bool splittouchespoint;
  /** If the split touches this index is the first 
      index position. */
  static uint splittouchesindex;

};

//---------------------------------------------------------
// Implementation

template< typename PT, typename PD >
bool convexregionsD2<PT,PD>::splittouchesface=false;
template< typename PT, typename PD >
bool convexregionsD2<PT,PD>::splittouchespoint=false;
template< typename PT, typename PD >
uint convexregionsD2<PT,PD>::splittouchesindex=0;

template< typename PT, typename PD >
convexregionsD2<PT,PD>::convexregionsD2(vector<PT> & pts_)
  : pts(pts_) 
{
  vi.push_back( polytopeD2linked() );
  assert(pts.size()>0);
}


template< typename PT, typename PD >
boolc convexregionsD2<PT,PD>::split
(
  uintc k, 
  halfspaceD2<PT,PD> const & h
)
{
  assert(k<vi.size());

  polytopeD2linked & x(vi[k]);

  uintc sz = x.pi.size();
  assert(sz>1);

  uint ci[sz];

  PT *beg = & x.pi[0]; 
  h.classify(ci,beg,beg+sz);

  // The two cutting positions
  uint cut[2];

  // Problem with templates so cut and paste the type.
  enum { undefined, below, on, above };

//  cut[0] = undefined;
//  cut[1] = undefined;

  uint index = 0;
  uint i2;

  for (uint i=0; i<sz; ++i)
  {
    if (ci[i]==on)
    {
      cut[index] = i;
      ++index;
      if (index==2)
        i=sz;
      continue;
    }

    i2 = (i+1)%sz;
    if (ci[i]==above)
    {
      if (ci[i2]==below)
      {
        cut[index] = i;
        ++index;
        if (index==2)
          i=sz;
        continue;
      } 
    }
  }

  // There should be two cuts.
  if (index==0)
    return false;

  if (index==1)
  {
    splittouchesface=false;
    splittouchespoint=true;
    splittouchesindex = cut[0];
    return false;
  }

  //uint a;
  uint status=0;
  if(cut[0]==on)
    status += 1;
  if(cut[1]==on)
    status += 2;

  switch (status)
  {
    // Two new points to be created.
    case 0:
      break;

    // First on, second to be made.
    case 1:
      break;

    // Second on, first to be made.
    case 2:
      break;

    // No new points to be created.
    case 3:
      // Handle line cutting face by rejection.
      if (cut[1] == (cut[0]+1)%sz)
      {
        splittouchesface = true;
        splittouchespoint = false;
        splittouchesindex = cut[0];
        return false;
      }
      if (cut[0] == (cut[1]+1)%sz)
      {
        splittouchesface = true;
        splittouchespoint = false;
        splittouchesindex = cut[1];
        return false;
      }
      break;
  }


  return true;
}




#endif