//
//	File:		minimize.h
//      Version:        ASTL 1.1
//	Copyright:	Vincent Le Maout
//	Date:		Fri Jul 18 1997
//	Descrition:	defines acyclic_minimization and struct minimization_tag
//

/** Université de Marne la Vallée - Institut Gaspard Monge *
  File minimize.h
  Copyright: Dominique Revuz
  Revised on 31/05/99 15:53:36
  Comments:
 * pour plus d'informations sur ce projet dr@univ-mlv.fr **/


#include <iostream>
#ifndef __DFA_GLIMPSE_H_
#include <vector>
#endif
#include <iterator>
#include <algorithm>

#ifdef WIN32
 #define MAXOP _MAX
#else
#define MAXOP max
#endif

using namespace std;

// Algorithm    : acyclic_minimization
// Description  : minimize an acyclic dfa
// Input        : a dfa
// Output       : result is written in the argument
// Precondition : dfa must be acyclic
//              : long Tag::degree_in()
//              : void Tag::degree_in(long)
//              : long Tag::equivalent_to()
//              : void Tag::equivalent_to(long)
// Uses         : height, fusion, redirect_edges, group_equivalent_states, refine_partition
//

struct minimization_tag 
{
  unsigned long _degree_in, _equivalent_to;
  unsigned char _height;

  minimization_tag() : _degree_in(0), _equivalent_to(0), _height(0) { }
  unsigned char height() const { return (_height); }
  void          height(unsigned char x) { _height = x; }
  unsigned long degree_in() const { return (_degree_in); }
  void          degree_in(unsigned long x) { _degree_in = x; }
  unsigned long equivalent_to() const { return (_equivalent_to); }
  void          equivalent_to(unsigned long x) { _equivalent_to = x; }
  friend bool operator == (const minimization_tag &x, const minimization_tag &y) {
    return (x.degree_in() == y.degree_in() && x.equivalent_to() == y.equivalent_to());
  }
};

	ostream& operator << (ostream &out, const struct minimization_tag &t)
	{
		out << t.degree_in() << " " << t.equivalent_to();
		return (out);
	}

// Computes the height of each state in A and
// stores it in a matrix (height x state)
// yields a partition of Q 
// if q is in Q, height(q) = Max {height(p) such that (q, a, p) is in T}
// and height(q) = 0 if q has no outgoing edges
// Uses method Tag::degree_in(long) to store the number of ingoing edges of each state
// Needs template functions swap and max 

template <class DFA, class Dstate>
unsigned char 
height(DFA& A, Dstate q, vector<vector < Dstate> *> &partition)
{
  const typename DFA::Edges& edg = A.delta2(q);
  unsigned char max_height = 0;
  typename DFA::Edges::const_iterator q_trans, edg_end = edg.end();
  Dstate aim;

  for (q_trans = edg.begin(); q_trans != edg_end; ++q_trans)
    {
      aim = (*q_trans).second;
      A.tag(aim).degree_in(A.tag(aim).degree_in() + 1);
      if (A.tag(aim).degree_in()>1) //la hauteur est deja calculée
      max_height = MAXOP(max_height,(unsigned char)(A.tag(aim).height()+1));       
	else 
      max_height = MAXOP(max_height,(unsigned char)(height(A,aim,partition)+1));
   }
  if (partition.size() <= max_height)
    partition.push_back(new vector<Dstate>(1, q));
  else
    partition[max_height]->push_back(q);
  A.tag(q).height(max_height); 
  return (max_height);
}

// Set default transition of each state in [start, finish) toward
// start state (start is the reference state of the partition)

template <class DFA, class iterator>
void 
fusion(DFA &A, iterator start, iterator finish)
{
	typedef typename DFA::State Dstate;
  vector<Dstate>::iterator where;
  Dstate reference = *start;
  
  for (where = start + 1; where != finish; ++where)
    A.tag(*where).equivalent_to((unsigned long) reference);  
}

// Redirect the outgoing edges of a partition based on height
// to the partition reference state and decrease the number of
// ingoing edges of aim. (delete aim if it has no ingoing edges any more) 
template <class DFA, class State>
void
redirect_edges(DFA &A, vector<State> &v)
{
  vector<State>::iterator where;
  for (where = v.begin(); where != v.end(); ++where)
    {
      //      cout << " redirect " << (where - v.begin());
      const typename DFA::Edges& edg = A.delta2(*where);
      typename DFA::Edges::const_iterator trans, edg_end = edg.end();
      typename DFA::State new_aim, aim;
      for (trans = edg.begin(); trans != edg_end; ++trans)
	{
	  aim = (*trans).second;
	  new_aim = (typename DFA::State) A.tag(aim).equivalent_to();
	  if (new_aim != A.null_state)
	    {
	      A.change_trans(*where, (*trans).first, new_aim);
	      A.tag(aim).degree_in(A.tag(aim).degree_in() - 1);
	      if (A.tag(aim).degree_in() == 0)  // no more ingoing edges to the aim
		A.del_state(aim);
	    }
	}
    }
}

// Compares two states and returns int <0 or ==0 or >0
template <class DFA, class State>
int
compare_states(DFA &A, State q, State p)
{
  bool fq = A.final(q);
  bool fp = A.final(p);
  if (fq != fp)
    return ((int) fq - (int) fp);

  typename DFA::Edges::size_type q_trans_count = A.delta2(q).size();
  typename DFA::Edges::size_type p_trans_count = A.delta2(p).size();
  if (q_trans_count - p_trans_count != 0) 
    return (q_trans_count - p_trans_count);
  if (q_trans_count == 0) return (0);

  // Both states have the same finality and the same number of transitions
  // We apply a kind of lexicographical comparison
  typename DFA::Edges::const_iterator left_edg_end = A.delta2(q).end();
  typename DFA::Edges::const_iterator left = A.delta2(q).begin();
  typename DFA::Edges::const_iterator right = A.delta2(p).begin();

  for (; left != left_edg_end; ++left, ++right)
  {
    typedef typename DFA::Alphabet Dalph;
    typedef typename DFA::State Dstate;
    const pair<const Dalph, Dstate>& q_trans = *left;
    const pair<const Dalph, Dstate>& p_trans = *right;
    
    if (q_trans.first == p_trans.first) // Same letter
    {
      if (q_trans.second < p_trans.second)
	return (-1);
      else
	if (p_trans.second < q_trans.second)
	  return (1);
    }
    else
      if (q_trans.first < p_trans.first)
	return (-1);
      else
	return (1);
  }
  return (0);
}
  

// Groups equivalent states and returns the range they are in
template <class DFA, class Size_type, class State>
void
group_equivalent_states(DFA &A, vector<State> &v, Size_type start, 
			Size_type finish,
			pair<Size_type, Size_type> &range)
{
  // Result is placed in 'range' argument
  Size_type g, d, pg;
  pg = g = start + 1;
  d = finish;
  State e = v[start];  // Reference state
  int res;

  while (g <= d)
    {
      res = compare_states(A, v[g], e);
      if (res == 0)
	{
	  swap(v[pg],v[g]);
	  pg++;
	  g++;
	}
      else
	if (res < 0) 
	  {
	    g++;
	  }
	else
	  {
	    res = compare_states(A, v[d], e);
	    if (res == 0)
	      if(g == pg)
		{
		  swap(v[pg],v[d]);
		  pg++;
		  g++;
		}
	      else
		{  
		  swap(v[pg],v[g]);
		  swap(v[pg],v[d]);
		  pg++;
		}
	    else
	      if(res > 0) d--;
	      else
		{   
		  swap(v[g],v[d]);
		  g++;
		}
	  }
    }
  
  range.second = d;
  range.first  = pg;
}   

// Refine the partition based on state height
// All equivalent states are placed together in the vector then merged
template <class DFA, class Size_type, class State>
void 
refine_partition(DFA &A, vector<State> &v,
		 Size_type start, Size_type finish)
{
  if (start < finish)
    {
      pair<vector<State>::size_type, vector<State>::size_type> range;
  
      group_equivalent_states(A, v, start, finish, range);
      if (start < range.first - 1) fusion(A, v.begin() + start, v.begin() + range.first);
      if (range.first < range.second) refine_partition(A, v, range.first, range.second);
      if (range.second + 1 < finish) refine_partition(A, v, range.second + 1, finish);
    }
}


// Main minimization function
template <class DFA>
void 
acyclic_minimization(DFA &dfa)
{
  if (dfa.state_count() > 0)
    {
		typedef typename DFA::State Dstate;
			typedef vector<vector < Dstate> *> matrix;
      matrix partition(1, new vector< Dstate>); 
      height(dfa,dfa.initial(),partition);

      if (partition[0]->empty() == false)
	{
	  //fusion(dfa, partition[0]->begin(), partition[0]->end());
	  matrix::iterator where;
	  //delete partition[0]; 
	  for (where = partition.begin() /*+ 1*/; where != partition.end(); ++where)
	    {
	      redirect_edges(dfa, **where);
	      refine_partition(dfa, **where, (matrix::size_type) 0, (**where).size() - 1);
	      delete (*where);
	    }
	}
    }
}