#include <assert.h>
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <vector>

#include <GL/glut.h>

#include <LEDA/mw_matching.h>
#include <LEDA/p_queue.h>
#include <LEDA/impl/bin_heap.h>

#include "vector3.h"
#include "stripper.h"
#include "matching.h"

using namespace leda;

Stripper::Stripper(PLYObject& ply)
	: _ply(ply), _dual(0), _displayer(0)
{
  _matching.clear();
  _matching2.clear();
  _matching3.clear();
  _junctions.clear();
}

Stripper::~Stripper()
{
  if (_dual)
    delete _dual;
}


void Stripper::makeDual()
{
  if (_dual)
    delete _dual;
  _dual = new dual(_ply);

  if (_displayer)
    delete _displayer;
  _displayer = new Displayer(this, _dual);
}


void Stripper::draw()
{
  if (_displayer)
    _displayer->draw();
}


/* Preprocess Boundary to make it all boundary triangles having one boundary edge */
void Stripper::preprocessBoundary()
{
  fprintf(stderr,"Preprocessing Boundary\n");

  int number_of_splits = 0;
  /* Iterate over the nodes */
  for(unsigned int n=0 ; n<_dual->_nodes.size() ; n++)
    {
      /* Check if boundary node */
      int bedges = _dual->boundaryEdges(n);
      //fprintf(stderr,"%d\n",bedges);

      if (0==bedges)
        continue; // non boundary

      if (1==bedges)
        {
          //fprintf(stderr,"%d\n",bedges);
          continue; // single boundary edge => no preprocessing
        }

      if (2==bedges)
        {
          //fprintf(stderr,"%d\n",bedges);
          splitEdge(_dual->otherEdge(n,-1,-1));
          number_of_splits++;
          //return;
        }
    }

  fprintf(stderr,"Total number of steiner vertices in first phase = %d\n",number_of_splits);

  /* Now again, check if any node has 2 neighboring boundary nodes, then 
     split against non-boundary node to make just one boundary neighbor */

#if 1
  /* Iterate again over the nodes */
  for(int iter = 0 ; iter < 2 ; iter++)
    for(unsigned int n=0 ; n<_dual->_nodes.size() ; n++)
      {
        /* Check if boundary node */
        int bedges = _dual->boundaryEdges(n);
        //fprintf(stderr,"%d\n",bedges);

        if (0==bedges)
          {
            int bnbrs = _dual->boundaryNeighbors(n);
            if (bnbrs == 0)
              ;
            else if (bnbrs == 1)
              ;
            else if (bnbrs == 2)
              {
                splitEdge(_dual->nonBoundaryNeighborEdge(n));
                number_of_splits++;
              }
            else
              {
                //fprintf(stderr,"3 boundary neighbors\n");

                /* Requires 2 splits along the direction of any boundary neighbor */
                doubleSplitEdge(n);
              }
          }

        if (1==bedges)
          {
            //fprintf(stderr,"%d\n",bedges);
            continue; // single boundary edge => no preprocessing
          }

        if (2==bedges)
          {
            fprintf(stderr,"ERROR\n");
            return;
          }
      }

#endif
  fprintf(stderr,"Total number of steiner vertices = %d\n",number_of_splits);

#if 0
  /* Arbitrary testing */
  static int E = 0;
  //for(unsigned int e=0 ; e<_dual->_edges.size() ; e++)
    {
      std::cout << E << std::endl;
      splitEdge(E);
      _dual->draw();
      E++;
      return;
    }
#endif
}



/* Find Matching */
/* Boundary nodes(with 1 boundary edge necessarily) are excluded from the matching
   Also, edges going to boundary nodes are excluded */
/* In essence, the boundary nodes are sort of hypothetically matched outside */

void Stripper::findMatching()
{
  Matching perfect(_dual);
  fprintf(stderr,"Dual Graph : Vertices : %d \t Edges : %d\n",_dual->_nodes.size(), _dual->_edges.size());
  _matching.resize(_dual->_edges.size());
  perfect.findMatching(_matching);
}





/* Do a dfs on the dual graph */
void Stripper::dfsTraversal()
{
  _dfs = new dfs(_dual);
  _cutedges = _dfs->findCutEdges();
  delete _dfs;
}


/* Remove the cut edges */
void Stripper::removeCutEdges()
{
  fprintf(stderr,"# of Cut Edges : %d\n",_cutedges.size());
  /* Now remove the cut-edges */
  for(unsigned int e=0 ; e <_cutedges.size() ; e++)
    {
      int cutedge = _cutedges[e];
      _cutedges.erase(_cutedges.begin() + e);
      splitEdge(cutedge);
      
      e--;
    }
}