#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"


/* Functions to resolve the junction nodes */



/* Move the junction nodes A->B closer */
/* Given the initial matching M1, find a matching M2 in the remaining edges, 
   and M3 in the remaining. Then, M1+M2 and M1+M3 are alternating paths. 
   Do a dfs in the resulting paths, and find a path that is closest to B 
   along the unmatched path from A->B */

void Stripper::findAlternatingPath(std::vector<int> trail)
{
  //int start = *trail.begin();
  //int end = *trail.begin();

  /* Find a matching in the remaining graph */
  /* Remove the current matching */

  Matching perfect(_dual);
  //fprintf(stderr,"Dual Graph : Vertices : %d \t Edges : %d\n",_dual->_nodes.size(), _dual->_edges.size());

  _matching2.resize(_dual->_edges.size());
  perfect.findMatching(_matching, _matching2);

  Matching perfect2(_dual);
  //fprintf(stderr,"Dual Graph : Vertices : %d \t Edges : %d\n",_dual->_nodes.size(), _dual->_edges.size());

  _matching3.resize(_dual->_edges.size());

  /* Discard _matching and _matching2 */
  std::vector<bool> matching12;
  matching12.resize(_dual->_edges.size());
  fill(matching12.begin(), matching12.end(), false);

  for(unsigned int e=0 ; e<matching12.size() ; e++)
    {
      if (_matching[e] || _matching2[e])
        matching12[e] = true;
    }

  perfect2.findMatching(matching12, _matching3);

}





void Stripper::connectJunctions()
{
  /* Consider all pairs of junctions that can be reached 
     from one another using the unmatched edges */

  /* ie, follow the 3 outgoing edges from the junction nodes.
     either all of them lead to some other junction nodes
     or come back to this guy forming a cycle */
  /* So, follow edge paths till you reach some junction node */

  /* Then, split along the paths of jn nodes that start and 
     end at different jn nodes */


  /* Resolved jn nodes */
  std::vector<int> resolved;
  resolved.resize(0);

  /* Iterate over junction nodes */
  for(unsigned int j=0 ; j<_junctions.size() ; j++)
    {
      fprintf(stderr,"Jn Node : %d\n",j);

      /* Check if not already resolved */
      std::vector<int>::iterator searchjn = 
        find(resolved.begin(), resolved.end(), _junctions[j]);

      if (searchjn != resolved.end()) // present !!!
        {
          //fprintf(stderr, "Already resolved \n");
          continue;
        }
      //fprintf(stderr, "Not resolved \n");

      /* iterate over the 3 trails if not already done */
      /* The junction node is _dual->_nodes[_junctions[j]] */
      int e1 = _dual->_nodes[_junctions[j]].e1;
      int e2 = _dual->_nodes[_junctions[j]].e2;
      int e3 = _dual->_nodes[_junctions[j]].e3;

      /* All these edges must be unmatched */
      assert((!_matching[e1])&&(!_matching[e2])&&(!_matching[e3]));
      int junction_dest, edge_dest;
      
      /* Atleast one of these should lead to some other junction node */
      bool done = false;

      if (!done)
        {
          //fprintf(stderr,"Following trail1\n");
          /* Start a new trail to get to a junction */
          std::vector<int> trail = followTrail(_junctions[j], e1, junction_dest, edge_dest);

          std::vector<int>::iterator newjn = 
            find(_junctions.begin(), _junctions.end(), junction_dest);
          assert(newjn != _junctions.end());
          
          /* Check if different jn node */
          if (junction_dest != _junctions[j]) // different
            {
              done = true;
              splitTrail(trail);
                  
              /* Both these junction nodes are resolved */
              resolved.push_back(_junctions[j]);
              resolved.push_back(junction_dest);
              //fprintf(stderr, "Resolving %d and %d\n", j, newjn - _junctions.begin());
            }
        }
      if (!done)
        {
          //fprintf(stderr,"Following trail1\n");
          /* Start a new trail to get to a junction */
          std::vector<int> trail = followTrail(_junctions[j], e2, junction_dest, edge_dest);

          std::vector<int>::iterator newjn = 
            find(_junctions.begin(), _junctions.end(), junction_dest);
          assert(newjn != _junctions.end());
          
          /* Check if different jn node */
          if (junction_dest != _junctions[j]) // different
            {
              done = true;
              splitTrail(trail);
                  
              /* Both these junction nodes are resolved */
              resolved.push_back(_junctions[j]);
              resolved.push_back(junction_dest);
              //fprintf(stderr, "Resolving %d and %d\n", j, newjn - _junctions.begin());
            }
        }
      if (!done)
        {
          //fprintf(stderr,"Following trail1\n");
          /* Start a new trail to get to a junction */
          std::vector<int> trail = followTrail(_junctions[j], e3, junction_dest, edge_dest);

          std::vector<int>::iterator newjn = 
            find(_junctions.begin(), _junctions.end(), junction_dest);
          assert(newjn != _junctions.end());
          
          /* Check if different jn node */
          if (junction_dest != _junctions[j]) // different
            {
              done = true;
              splitTrail(trail);
                  
              /* Both these junction nodes are resolved */
              resolved.push_back(_junctions[j]);
              resolved.push_back(junction_dest);
              //fprintf(stderr, "Resolving %d and %d\n", j, newjn - _junctions.begin());
            }
        }
    }


}



/* Split along a trail from one junction node to another */
void Stripper::splitTrail(std::vector<int> trail)
{
  fprintf(stderr, "Splitting along trail of length %d\n", trail.size());

  /* Iterate over the edges in the trail and split alternate edges */
  //bool odd = (trail.size() % 2);
  //fprintf(stderr,"Trail is odd : %d\n",odd);

  for(unsigned int n=0 ; n<trail.size()-1; n+=2)
    {
      //fprintf(stderr,"%d\n",n);
      //int e = _dual->commonEdge(trail[n], trail[n+1]);
      splitEdge(trail[n], trail[n+1], true);
    }
  //fprintf(stderr, "Splitting done\n");

}



/* Follow a trail along unmatched edges only till you get to a junction node */
/* return the list of nodes on the way */
/* List Starting and ending with junction nodes */
std::vector<int> Stripper::followTrail(int n, int e, int& ndest, int& edest)
{
  std::vector<int> path;
  int prevn = n;
  int preve = e;
  int nextn = _dual->neighbor(prevn, preve);
  assert(_dual->neighbor(nextn,preve) == prevn);
  
  int trail_length = 1;
  path.push_back(n);
  path.push_back(nextn);

  while(!isJunction(nextn)) // while non-junction nodes
    {
      /* go on */
      int e1 = _dual->otherEdge(nextn, preve);
      int e2 = _dual->otherEdge(nextn, preve, e1);

      /* Both cannot be unmatched, else a junction node */
      /* Atleast one guy must be matched */
      //fprintf(stderr,"%d \t %d\n",e1, e2);
      assert((e1 != -1)||(e2 != -1));
      if ((e1 != -1)&&(e2 != -1))
        {
          //fprintf(stderr,"%d \t %d\n",(int)_matching[e1], (int)_matching[e2]);
          assert((_matching[e1])||(_matching[e2]));
        }
      if (e1 != -1)
        if (!_matching[e1])
          preve = e1;
      if (e2 != -1)
        if (!_matching[e2])
          preve = e2;

      nextn = _dual->neighbor(nextn, preve);
      trail_length++;
      path.push_back(nextn);
    }

  /* Got a junction node, return it */
  ndest = nextn;
  edest = preve;
  //fprintf(stderr,"Trail length = %d nodes \n", path.size());
  //fprintf(stderr,"Start node = %d | Destination node = %d  \n", n, ndest);
  return path;
}


/* Check if already visited ie edge at start of trail is already done */
bool Stripper::alreadyVisited(std::vector<int>& l, int e)
{
  assert(l.size()>0);
  for(unsigned int i=0 ; i<l.size() ; i++)
    {
      if (l[i] == e)
        return true;
    }
  return false;
}



/* Given a matching, find the rest ie the loops and paths and junction nodes */
void Stripper::findJunctionsLoopsPaths()
{
  _junctions.clear();
  _junctions.resize(0);
  
  /* Iterate over the nodes and find the junction nodes */
  for(unsigned int n=0 ; n<_dual->_nodes.size() ; n++)
    {
      if (isJunction(n))
        _junctions.push_back(n);
    }

  fprintf(stderr,"%d Junction Nodes\n",_junctions.size());

  for(unsigned int n=0 ; n<_junctions.size() ; n++)
    {
      //fprintf(stderr,"%d : %d\n", n, _junctions[n]);
    }

}


/* Check if a node is a junction node */
bool Stripper::isJunction(int n)
{
  /* Must have atleast one matched edge else it is a junction node */
  /* unless of course it is a boundary guy */
  if (_dual->boundaryEdges(n) == 0)
    {
      /* if atleast one matched edge, it is cool */
      if ((_matching[_dual->_nodes[n].e1])||(_matching[_dual->_nodes[n].e2])
          ||(_matching[_dual->_nodes[n].e3]))
        return false;
      else
        return true;
    }
  else
    return false;
}