//
//	File:		dfa_compact.h
//      Version:        ASTL 1.1
//	Copyright:	Vincent LE MAOUT
//	Date:		Tue Jun 23 18:32:06 MET DST 1998
//	Descrition:	Determinisic Finite Automaton Class Template ASTL1.10
//                      Compact Representation (dfa_compact class is an adapter for DFA_* classes)
//                      See standard.txt for automaton class requirements
//      Precondition:   DFA class must define iterators on Q (matrix)
//                      The letter (DFA::Alphabet) 0 is reserved

// Trois tableaux:
// 1. vecteur v1 contenant des donnees de type DFA::Alphabet
// 2. vecteur v2 contenant des donnees de type State (designation d'un etat => u_long) 
// 3. vecteur de bits F pour les etats finaux 

// Une cellule de la matrice d'indice n est constituee des deux cellules n des vecteurs
// 1 et 2.
// si v1[n] == 0 alors il n'y a pas de transitions dans cette cellule
//   alors si v2[n] != 0 alors v2[n] est le tag de l'etat se trouvant en n+1
//   sinon si v2[n] == 0 alors la cellule est vide
// sinon si v1[n] != 0 alors v1[n] est la lettre de la transition et v2[n] son but

#ifndef ASTL_CLASS_DFA_COMPACT
#define ASTL_CLASS_DFA_COMPACT

#ifndef WIN32
#include <unistd.h>   // close(int)
#include <sys/mman.h>  // mmap
#include <fcntl.h>     // read
#include <errno.h>     // debuggage du mapping
#else
#define min _MIN
#endif

#include <vector>
#include <utility>     // pair<>
#include <functional>      // function identity (guess what ? not implemented by Microsoft...)
// is then defined in astl.h for WIN32
#include <astl.h>

// Object function reading & writing on binary streams
// To be used with STL algorithm for_each
template <class Tag>
struct tag_save : unary_function<Tag, void>
{
  ostream &out;
  tag_save(ostream &x) : out(x) 
    { }
  void operator () (const Tag &x) {
    ///		cout << "tag_traits::save(" << x << ")" << endl;
    tag_traits<Tag>::write(out, x);
  }
};

template <class Tag>
struct tag_load : unary_function<Tag, void>
{
  istream &in;
  tag_load(istream &x): in(x)
    { }
  void operator () (Tag &x) {
    tag_traits<Tag>::read(in, x);
    ///		cout << "tag_traits::load(" << x << ")" << endl;
  }
};

#ifndef WIN32
template <class DFA, 
  class tag_mapping_object_function = identity<typename DFA::Tag> >
#else
template <class DFA, 
  class tag_mapping_object_function = identity<DFA::Tag> >
#endif

class DFA_compact : public DFA_base
{
public: 
  typedef typename DFA::Sigma    Sigma;
  typedef typename DFA::Alphabet Alphabet;
  typedef unsigned long          State;
  typedef typename tag_mapping_object_function::result_type Tag;

  State null_state;

private:
  typedef vector<int>::size_type size_type;
  typedef vector<bool> set_F;
  typedef DFA_compact self;

public:
#ifdef WIN32
  class const_iterator : public iterator<forward_iterator_tag, State>
#else
  class const_iterator : public forward_iterator<State, ptrdiff_t>
#endif
  {
    friend self;
  private:
    State state;
    const vector<Alphabet> *ml;
    const vector<State> *ma;

    const_iterator(State x, const vector<Alphabet> *a, const vector<State> *s) 
      : state(x), ml(a), ma(s) { }    

  public:

    const_iterator() : ml(NULL), ma(NULL) { }
    State operator * () const { return (state); }
    const_iterator& operator ++ ()
      {
	for (; state < ml->size(); ++state)
	{
	  if ((*ml)[state] == (Alphabet) 0 && (*ma)[state] != 0)   // this is a cell holding a tag index
	  {
	    ++state;                                // there is a state after a tag
	    break;
	  }
	}
	return (*this);
      }
    const_iterator operator ++ (int)
      {
	const_iterator tmp = *this;
	++(*this);
	return (tmp);
      }
    const_iterator& operator = (const const_iterator &x) 
      {
	state = x.state;
	ml = x.ml;
	ma = x.ma;
	return (*this);
      }
    bool operator == (const const_iterator &x) const {
      return (state == x.state);
    }
    bool operator != (const const_iterator &x) const {
      return (!(*this == x));
    }
  };

  class Edges
  {
    //    friend self;
  private:
    State                             s;
    const vector<Alphabet> *ml;
    const vector<State>    *ma;

  public:
    Edges(State st, const vector<Alphabet> &l, 
	  const vector<State> &a) 
      : s(st), ml(&l), ma(&a) { }

    typedef Alphabet Key;
    typedef pair<const Key, State> value_type;
    typedef less<Alphabet> key_compare;

    typedef value_type* pointer;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef State size_type;
    typedef typename DFA::Edges::difference_type difference_type;
    
    class value_compare : public binary_function<value_type, value_type, bool>
    {
      friend class _Edges;
      
    protected:
      key_compare comp;
      value_compare(key_compare c) : comp(c) { }
      
    public:
      bool operator () (const value_type& x, const value_type& y)
	{
	  return (comp(x.first, y.first));
	}
    };

#ifdef WIN32
    class const_iterator : iterator<bidirectional_iterator_tag, value_type>
#else
    class const_iterator : bidirectional_iterator<value_type, ptrdiff_t>
#endif
    {
      friend Edges;
    private:
      const vector<Alphabet> *ml;
      const vector<State>    *ma;
      State                   state;
      size_type               pos;

      const_iterator(State s, const vector<Alphabet> &l, 
		     const vector<State> &a, size_type _pos = 0) 
	: ml(&l), ma(&a), state(s), pos(_pos) { }

    public:
      const_iterator() { }
      const_iterator(const const_iterator& i) 
	: ml(i.ml), ma(i.ma), state(i.state), pos(i.pos) { }

      bool operator == (const const_iterator &x) const {
	return (pos == x.pos && state == x.state); /// && ml == x.ml && ma == x.ma);
      }
      bool operator != (const const_iterator &x) const {
        return (!(*this == x));
      }
      value_type operator * () const {
	return (value_type((*ml)[state + pos], (*ma)[state + pos]));
      }
      const_iterator& operator ++ ()
	{
	  size_type max_offset = min((size_type) (ml->size() - state), (size_type) Sigma::size());
	  for (++pos; pos < max_offset; ++pos)
	  if ((*ml)[state + pos] != (Alphabet) 0)
	  if (Sigma::map((*ml)[state + pos]) == pos)
	  break;
	  return (*this);
	}
      const_iterator operator ++ (int)
	{
	  const_iterator tmp = (*this);
	  ++(*this);
	  return tmp;
	}
      const_iterator& operator -- ()
	{
	  for (--pos; pos != 0; --pos)
	  if (Sigma::map((*ml)[state + pos]) == pos) 
	  break;
	  return (*this);
	}
      const_iterator operator -- (int)
	{
	  const_iterator tmp = (*this);
	  --(*this);
	  return tmp;
	}
    };

    // Back to Edges class

    typedef const_iterator iterator;

    Edges() : s((State) 0), ml(NULL), ma(NULL) { }

    key_compare key_comp() const
      { 
	key_compare tmp;
	return (tmp); 
      }

    value_compare value_comp() const { return (value_compare(key_comp())); }

    State operator [] (const Key& k) const
      {
	State q = s + Sigma::map(k);
	if ((*ml)[q] == k)
	return ((*ma)[q]);
	else
	return ((State) 0);
      }

    iterator begin() const
      {
	size_type offset;
	size_type max_offset = min((size_type) (ml->size() - s), (size_type) Sigma::size());

	// Looking for the first transition of the state
	for (offset = 0; offset < max_offset; ++offset)
	if ((*ml)[s + offset] != (Alphabet) 0)
	if (Sigma::map((*ml)[s + offset]) == offset)
	break;

	return (iterator(s, *ml ,*ma, offset));
      }
    iterator end() const
      {
	return (iterator(s, *ml , *ma, min((size_type) (ml->size() - s), (size_type) Sigma::size())));
      }
    size_type size() const
      {
	size_type offset;
	size_type result = 0;
	size_type max_offset = min((size_type) (ml->size() - s), (size_type) Sigma::size());

	for (offset = 0; offset < max_offset; ++offset)
	{
	  if (Sigma::map((*ml)[s + offset]) == offset)
	  ++result;
	}
	return (result);
      }

    bool empty() const
      {
	return (size() == 0);
      }

    iterator find(const Key &k) const
      {
	unsigned long mapped = Sigma::map(k);
	State result = s + mapped;
	if (result < ml->size())
	if ((*ml)[result] == k)
	return (iterator(s, *ml, *ma, mapped));
	return (end());
      }
    
    size_type count(const Key& k) const
      {
	size_type mapped = Sigma::map(k);
	State result = s + mapped;
	if (result < ml->size())
	if ((*ml)[result] == k)
	return (1);
	return (0);
      }

    iterator lower_bound(const Key &k) const {
      return (find(k));
    }

    iterator upper_bound(const Key &k) const {
      return (find(k));
    }

    pair<iterator, iterator> equal_range(const Key &k) const
      {
	iterator tmp = find(k);
	return (pair<iterator, iterator>(tmp, ++tmp));
      }
  };

  // Back to DFA_compact class

private:
  vector<Alphabet> letters;
  vector<State>    aims;
  vector<Tag>      tags;
  State I;
  unsigned long _state_count;
  unsigned long _trans_count;
  unsigned long _final_count;
#ifndef WIN32
  int fd;        // Pour le mapping
#endif
  set_F F;

  bool free_cell(State s) const { 
    return (letters[s] == (Alphabet) 0 && aims[s] == (State) 0);
  }

  bool tagged_cell(State s) const {
    return (letters[s] == (Alphabet) 0 && aims[s] != (State) 0);
  }

public:
  // Binary save
  void write(ostream &out) 
    { 
      out.write((const char *) &I, sizeof(I));
      out.write((const char *) &_state_count, sizeof(_state_count));
      out.write((const char *) &_trans_count, sizeof(_trans_count));
      unsigned int letters_size = letters.size(), aims_size = aims.size(), tags_size = tags.size(), F_size = F.size();
      out.write((const char *) &letters_size, sizeof(letters_size));
      out.write((const char *) letters.begin(), sizeof(Alphabet) * letters.size()); 
      out.write((const char *) &aims_size, sizeof(aims_size));
      out.write((const char *) aims.begin(), sizeof(State) * aims.size());  
      out.write((const char *) &tags_size, sizeof(tags_size));
      for_each(tags.begin(), tags.end(), tag_save<Tag>(out));
      out.write((const char *) &F_size, sizeof(F_size));
      out.write((const char *) &_final_count, sizeof(_final_count));
      for(const_iterator q = begin(); q != end(); ++q)
      {
	if (final(*q))
	{
	  State tmp = *q;
	  out.write((const char *) &tmp, sizeof(tmp));
	}
      }
    }

  // Binary read
  void read(istream &in)
    {
      unsigned int sizes;
      in.read((char *)&I, sizeof(I));
      in.read((char *)&_state_count, sizeof(_state_count));
      in.read((char *)&_trans_count, sizeof(_trans_count));
      in.read((char *)&sizes, sizeof(sizes));
      letters.resize(sizes);
      in.read((char *)letters.begin(), sizes * sizeof(Alphabet));  
      in.read((char *)&sizes, sizeof(sizes));
      aims.resize(sizes);
      in.read((char *)aims.begin(), sizes * sizeof(State));  
      in.read((char *)&sizes, sizeof(sizes));
      tags.resize(sizes);
      for_each(tags.begin(), tags.end(), tag_load<Tag>(in));
      in.read((char *)&sizes, sizeof(sizes));
      F.resize(sizes, false);
      in.read((char *)&_final_count, sizeof(_final_count));
      State tmp;
      for(unsigned long k = 0; k < _final_count; ++k)
      {
	in.read((char *)&tmp, sizeof(tmp));
	F[tmp] = true;
      }
    }      

#ifndef WIN32
  // Memory mapping
  void map(const char *path_name)
    {
      fd = open(path_name, O_RDONLY);
      if (fd == -1)
      {
	perror(path_name);
	exit(1);
      }
      unsigned long * map_address;
    
      // On recupere la taille du fichier
      unsigned long file_size = lseek(fd, 0, SEEK_END);

      map_address = (unsigned long *) mmap(0, file_size, PROT_READ, MAP_FILE | MAP_PRIVATE, fd, 0);
      if (map_address == (unsigned long *) -1)
      {
	perror("mmap");
	exit(1);
      }

      I = *map_address++;
      _state_count = *map_address++;
      _trans_count = *map_address++;

      // On recupere la taille de la matrice
      unsigned long matrix_size = *map_address++;

      // Positionnement de v1
      letters.is_here((Alphabet *) map_address, matrix_size);

      // Recherche de v2
      map_address = (unsigned long *) ((char *) map_address + matrix_size * sizeof(Alphabet));
      matrix_size = *map_address++; // Recuperation de la taille de v2

      // Positionnement de v2
      aims.is_here((State *) map_address, matrix_size);

      // Recherche de tags
      map_address = (unsigned long *) ((char *) map_address + matrix_size * sizeof(State));
      matrix_size = *map_address++;

      // Positionnement de tags
      tags.is_here((Tag *) map_address, matrix_size);
    }
#endif

  State initial() const { 
    return (I); 
  }

  set_F::const_reference final(State s) const {
    return (F[s]);
  }

  State delta1(State s, const Alphabet &l) const
    {
      State q = s + Sigma::map(l);
      if (letters[q] == l) return (aims[q]);
      return (null_state);
    }

  unsigned long state_count() const { return (_state_count); }
  unsigned long trans_count() const { return (_trans_count); }
  
  const Tag& tag(State s) const { return (tags[aims[s - 1]]); }

  // WARNING: due to tag compacting, be careful modifying tag value
  Tag& tag(State s) { return (tags[aims[s - 1]]); }

  Edges delta2(State s) const { return (Edges(s, letters, aims)); }

  const_iterator begin() const
    {
      if (state_count() > 0)
      return (const_iterator((State) 1, &letters, &aims));
      else
      return (end());
    }

  const_iterator end() const {
    return (const_iterator(letters.size(), &letters, &aims));
  }

  float occupation_ratio() const
    {
      unsigned long occupied_cells = 0;
      State i, fin = letters.size();
    
      for (i = 0; i != fin; ++i)
      if (!free_cell(i))
      ++occupied_cells;

      return ((float) occupied_cells / (float) fin);
    }

  void stats(ostream &out = cout) const
    {
      out << "Taille matrice : (" << letters.size() << ") " << letters.size() * sizeof(Alphabet) +
      aims.size() * sizeof(State) + tags.size() * sizeof(Tag) << endl;
      out << "    lettres (" << letters.size() << ") " << letters.size() * sizeof(Alphabet) 
      << " Octets" << endl;
      out << "    buts    (" << aims.size() << ") " << aims.size() * sizeof(State) 
      << " Octets" << endl;
      out << "    tags    (" << tags.size() << ") " << tags.size() * sizeof(Tag) 
      << " Octets" << endl;
      out << "Etats          : " << state_count() << endl;
      out << "Transitions    : " << trans_count() << endl;
      out << "Taux d'occupation : " << occupation_ratio() * 100. << "%" << endl;
    }

  ~DFA_compact() {
#ifndef WIN32
    if (fd != 0) close(fd);
#endif
  }

  // TEMPORARY CODE:
  DFA_compact() : null_state(0)
    { }

  DFA_compact(istream &in) 
    : null_state(0)
#ifndef WIN32
    , fd(0)
#endif
    {
      read(in);
    }
  
  DFA_compact(const DFA &dfa, long opt_value = 0) 
    : null_state(0), letters((unsigned int) (dfa.state_count() * 2 + dfa.trans_count()), (Alphabet) 0), 
      aims((unsigned int) (dfa.state_count() * 2 + dfa.trans_count()),  (State) 0), 
      tags((unsigned int) 1, Tag()), I(null_state), _state_count(0), _trans_count(0), _final_count(0),
#ifndef WIN32
      fd(0), 
#endif
      F((unsigned int) dfa.state_count(), false)
    {
      if (dfa.state_count() > 0)
      {
	tag_mapping_object_function map_tag;
	typename DFA::const_iterator i, end_i = dfa.end();
	vector<State> old2new(dfa.state_count());  // vector indexed by DFA::State
	State pos, solid_first_free = 0UL, first_free;
	typename DFA::Edges::const_iterator trans, edg_end;
	long count = 0;                // For time optimization of compacting process

	for (i = dfa.begin(); i != end_i; ++i)
	{
	  ++count;
	  ++_state_count;

	  if (count == opt_value)   // We discard solid_first_free
	  {
	    do
	    {
	      ++solid_first_free;
	    }
	    while (solid_first_free + Sigma::size() < letters.size() && !free_cell(solid_first_free));
	    if (solid_first_free + Sigma::size() >= letters.size())   // Matrix is too small
	    {
	      // Doubling the size
	      size_type p = letters.size();
	      letters.resize(2 * p, (Alphabet) 0);
	      aims.resize(2 * p, (State) 0);
	      solid_first_free = p;
	    }
	    count = 0;
	  }
	  first_free = solid_first_free;

	  while (1)
	  {
	    pos = first_free + 1;  // Because we put the tag at first_free
	    typename DFA::Edges edg = dfa.delta2(*i);
	    edg_end = edg.end();

	    // Trying to put every transition by beginning at pos (first_free)
	    for (trans = edg.begin(); trans != edg_end; ++trans)
	    if (!free_cell(pos + Sigma::map((*trans).first)))
	    break;
	      
	    if (trans == edg_end)   // Ok, insert state
	    {
	      // Storing new "name" of the state
	      if (old2new.size() <= (unsigned long) *i)
	      old2new.resize((unsigned long) (*i) * 2, null_state);
	      old2new[(unsigned long) *i] = pos;

	      // Putting the tag if not already in vector tags
	      Tag t_tmp = map_tag(dfa.tag(*i));
	      vector<Tag>::iterator position = find(tags.begin() + 1, tags.end(), t_tmp);
	      aims[pos - 1] = (State) (position - tags.begin()); 
	      if (position == tags.end()) 
	      tags.push_back(t_tmp);

	      // Put the state in F if needed
	      if (dfa.final(*i))
	      {
		if (F.size() <= pos)
		F.resize(pos + 1, false);
		F[pos] = true;
		///				cout << "compactage: " << pos << " est final" << endl;
		++_final_count;
	      }

	      // Puting transitions
	      unsigned long mapped_letter;
	      for (trans = edg.begin(); trans != edg_end; ++trans)
	      {
		mapped_letter = Sigma::map((*trans).first);
		letters[pos + mapped_letter] = (*trans).first;
		aims[pos + mapped_letter] = (State) (*trans).second;
		++_trans_count;
	      }
	      if (first_free == solid_first_free)
	      count = opt_value - 1;        // Force solid_first_free updating
	      break;    // move on to the next state
	    }

	    // first_free is updated
	    do
	    {
	      ++first_free;
	    }
	    while (first_free + Sigma::size() < letters.size() && !free_cell(first_free));
	    if (first_free + Sigma::size() >= letters.size())   // Matrix is too small
	    {
	      // Doubling the size
	      size_type p = letters.size();
	      letters.resize(2 * p, (Alphabet) 0);
	      aims.resize(2 * p, (State) 0);
	      first_free = p;
	    }
	  }
	}

	// Setting edges aim to states new "names"
	State last_one = 0;
	for (pos = 0; pos != letters.size(); ++pos)
	if (letters[pos] != (Alphabet) 0)
	aims[pos] = old2new[aims[pos]];
	else
	if (aims[pos] != 0) // letter == 0, aim != 0 => aim is a tag index
	last_one = pos + 1 + Sigma::size();

	if (dfa.initial() != dfa.null_state)
	I = old2new[(unsigned long) dfa.initial()];
	///			cout << "Taille de l'alphabet = " << Sigma::size() << endl;
	letters.resize(last_one + 1, (Alphabet) 0);
	aims.resize(last_one + 1, (State) 0);
	F.resize(last_one + 1, false);
      }
    }
};

// TEMPORARY CODE:
#ifdef DFA_DEFAULT_COMPACT_NEEDED

#ifndef WIN32
template <class DFA, 
  class tag_mapping_object_function = identity<typename DFA::Tag> >
#else
template <class DFA, 
  class tag_mapping_object_function = identity<DFA::Tag> >
#endif

class DFA_default_compact : public DFA_base
{
public: 
  typedef typename DFA::Sigma    Sigma;
  typedef typename DFA::Alphabet Alphabet;
  typedef unsigned long          State;
  typedef typename tag_mapping_object_function::result_type Tag;

  State null_state;

private:
  typedef vector<int>::size_type size_type;
  typedef vector<bool> set_F;
  typedef DFA_default_compact self;

public:
#ifdef WIN32
  class const_iterator : public iterator<forward_iterator_tag, State>
#else
  class const_iterator : public forward_iterator<State, ptrdiff_t>
#endif
  {
    friend self;
  private:
    State state;
    const vector<Alphabet> *ml;
    const vector<State> *ma;

    const_iterator(State x, const vector<Alphabet> *a, const vector<State> *s) 
      : state(x), ml(a), ma(s) { }    
    
  public:

    const_iterator() : ml(NULL), ma(NULL) { }
    State operator * () const { return (state); }
    const_iterator& operator ++ ()
      {
	for (; state < ml->size(); ++state)
	{
	  if ((*ml)[state] == (Alphabet) 0 && (*ma)[state] != 0)   // this is a cell holding a tag index
	  {
	    ++state;                                // there is a state after a tag
	    break;
	  }
	}
	return (*this);
      }
    const_iterator operator ++ (int)
      {
	const_iterator tmp = *this;
	++(*this);
	return (tmp);
      }
    const_iterator& operator = (const const_iterator &x) 
      {
	state = x.state;
	ml = x.ml;
	ma = x.ma;
	return (*this);
      }
    bool operator == (const const_iterator &x) const {
      return (state == x.state);
    }
    bool operator != (const const_iterator &x) const {
      return (!(*this == x));
    }
  };

  class Edges
  {
    //    friend self;
  private:
    State                             s;
    const vector<Alphabet> *ml;
    const vector<State>    *ma;

  public:
    Edges(State st, const vector<Alphabet> &l, 
	  const vector<State> &a) 
      : s(st), ml(&l), ma(&a) { }

    typedef Alphabet Key;
    typedef pair<const Key, State> value_type;
    typedef less<Alphabet> key_compare;

    typedef value_type* pointer;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef State size_type;
    typedef typename DFA::Edges::difference_type difference_type;
    
    class value_compare : public binary_function<value_type, value_type, bool>
    {
      friend class _Edges;
      
    protected:
      key_compare comp;
      value_compare(key_compare c) : comp(c) { }
      
    public:
      bool operator () (const value_type& x, const value_type& y)
	{
	  return (comp(x.first, y.first));
	}
    };

#ifdef WIN32
    class const_iterator : iterator<bidirectional_iterator_tag, value_type>
#else
    class const_iterator : bidirectional_iterator<value_type, ptrdiff_t>
#endif
    {
      friend Edges;
    private:
      const vector<Alphabet> *ml;
      const vector<State>    *ma;
      State                   state;
      size_type               pos;

      const_iterator(State s, const vector<Alphabet> &l, 
		     const vector<State> &a, size_type _pos = 0) 
	: ml(&l), ma(&a), state(s), pos(_pos) { }

    public:
      const_iterator() { }
      const_iterator(const const_iterator& i) 
	: ml(i.ml), ma(i.ma), state(i.state), pos(i.pos) { }

      bool operator == (const const_iterator &x) const {
	return (pos == x.pos); /// && state == x.state && ml == x.ml && ma == x.ma);
      }
      bool operator != (const const_iterator &x) const {
        return (!(*this == x));
      }
      value_type operator * () const {
	return (value_type((*ml)[state + pos], (*ma)[state + pos]));
      }
      const_iterator& operator ++ ()
	{
	  ///	size_type max_offset = min((size_type) (ml->size() - state), (size_type) Sigma::size());
	  size_type max_offset = min((size_type) (ml->size() - state), (size_type) Sigma::size());
	  for (++pos; pos < max_offset; ++pos)
	  if ((*ml)[state + pos] != (Alphabet) 0)
	  if (Sigma::map((*ml)[state + pos]) == pos)
	  break;
	  return (*this);
	}
      const_iterator operator ++ (int)
	{
	  const_iterator tmp = (*this);
	  ++(*this);
	  return tmp;
	}
      const_iterator& operator -- ()
	{
	  for (--pos; pos != 0; --pos)
	  if (Sigma::map((*ml)[state + pos]) == pos) 
	  break;
	  return (*this);
	}
      const_iterator operator -- (int)
	{
	  const_iterator tmp = (*this);
	  --(*this);
	  return tmp;
	}
    };

    // Back to Edges class

    typedef const_iterator iterator;

    Edges() : s((State) 0), ml(NULL), ma(NULL) { }

    key_compare key_comp() const
      { 
	key_compare tmp;
	return (tmp); 
      }

    value_compare value_comp() const { return (value_compare(key_comp())); }

    State operator [] (const Key& k) const
      {
	State q = s + Sigma::map(k);
	if ((*ml)[q] == k)
	return ((*ma)[q]);
	else
	return ((State) 0);
      }

    iterator begin() const
      {
	size_type offset;
	size_type max_offset = min((size_type) (ml->size() - s), (size_type) Sigma::size());

	// Looking for the first transition of the state
	for (offset = 0; offset < max_offset; ++offset)
	if ((*ml)[s + offset] != (Alphabet) 0)
	if (Sigma::map((*ml)[s + offset]) == offset)
	break;

	return (iterator(s, *ml ,*ma, offset));
      }
    iterator end() const
      {
	return (iterator(s, *ml , *ma, min((size_type) (ml->size() - s), (size_type) Sigma::size())));
      }
    size_type size() const
      {
	size_type offset;
	size_type result = 0;
	size_type max_offset = min((size_type) (ml->size() - s), (size_type) Sigma::size());

	for (offset = 0; offset < max_offset; ++offset)
	{
	  if (Sigma::map((*ml)[s + offset]) == offset)
	  ++result;
	}
	return (result);
      }

    bool empty() const
      {
	return (size() == 0);
      }

    iterator find(const Key &k) const
      {
	unsigned long mapped = Sigma::map(k);
	State result = s + mapped;
	if (result < ml->size())
	if ((*ml)[result] == k)
	return (iterator(s, *ml, *ma, mapped));
	return (end());
      }
    
    size_type count(const Key& k) const
      {
	size_type mapped = Sigma::map(k);
	State result = s + mapped;
	if (result < ml->size())
	if ((*ml)[result] == k)
	return (1);
	return (0);
      }

    iterator lower_bound(const Key &k) const {
      return (find(k));
    }

    iterator upper_bound(const Key &k) const {
      return (find(k));
    }

    pair<iterator, iterator> equal_range(const Key &k) const
      {
	iterator tmp = find(k);
	return (pair<iterator, iterator>(tmp, ++tmp));
      }
  };

  // Back to DFA_default_compact class

private:
  vector<Alphabet> letters;
  vector<State>    aims;
  vector<Tag>      tags;
  State I;
  unsigned long _state_count;
  unsigned long _trans_count;
  unsigned long _final_count;
  Alphabet default_letter;
#ifndef WIN32
  int fd;        // Pour le mapping
#endif
  set_F F;

  bool free_cell(State s) const { 
    return (letters[s] == (Alphabet) 0 && aims[s] == (State) 0);
  }

  bool tagged_cell(State s) const {
    return (letters[s] == (Alphabet) 0 && aims[s] != (State) 0);
  }

public:
  // Binary save
  void write(ostream &out) 
    { 
      out.write((const char *) &I, sizeof(I));
      out.write((const char *) &_state_count, sizeof(_state_count));
      out.write((const char *) &_trans_count, sizeof(_trans_count));
      unsigned int letters_size = letters.size(), aims_size = aims.size(), tags_size = tags.size(), F_size = F.size();
      out.write((const char *) &letters_size, sizeof(letters_size));
      out.write((const char *) letters.begin(), sizeof(Alphabet) * letters.size()); 
      out.write((const char *) &aims_size, sizeof(aims_size));
      out.write((const char *) aims.begin(), sizeof(State) * aims.size());  
      out.write((const char *) &tags_size, sizeof(tags_size));
      for_each(tags.begin(), tags.end(), tag_save<Tag>(out));
      out.write((const char *) &F_size, sizeof(F_size));
      out.write((const char *) &_final_count, sizeof(_final_count));
      for(const_iterator q = begin(); q != end(); ++q)
      {
	if (final(*q))
	{
	  State tmp = *q;
	  out.write((const char *) &tmp, sizeof(tmp));
	}
      }
    }

  // Binary read
  void read(istream &in)
    {
      ///		cout << "DFA_default_compact::read" << endl;
      unsigned int sizes;
      in.read((char *)&I, sizeof(I));
      in.read((char *)&_state_count, sizeof(_state_count));
      in.read((char *)&_trans_count, sizeof(_trans_count));
      ///		cout << "I = " << I << endl;
      ///		cout << "Q = " << _state_count << endl;
      ///		cout << "T = " << _trans_count << endl;
      in.read((char *)&sizes, sizeof(sizes));
      letters.resize(sizes);
      in.read((char *)letters.begin(), sizes * sizeof(Alphabet));  
      in.read((char *)&sizes, sizeof(sizes));
      aims.resize(sizes);
      in.read((char *)aims.begin(), sizes * sizeof(State));  
      in.read((char *)&sizes, sizeof(sizes));
      tags.resize(sizes);
      for_each(tags.begin(), tags.end(), tag_load<Tag>(in));
      in.read((char *)&sizes, sizeof(sizes));
      F.resize(sizes, false);
      in.read((char *)&_final_count, sizeof(_final_count));
      //		cout << "F = " << F.size() << endl;
      //		cout << "Final count = " << _final_count << endl;
      State tmp;
      for(unsigned long k = 0; k < _final_count; ++k)
      {
	in.read((char *)&tmp, sizeof(tmp));
	F[tmp] = true;
      }
    }      

#ifndef WIN32
  // Memory mapping
  void map(const char *path_name)
    {
      fd = open(path_name, O_RDONLY);
      if (fd == -1)
      {
	perror(path_name);
	exit(1);
      }
      unsigned long * map_address;
    
      // On recupere la taille du fichier
      unsigned long file_size = lseek(fd, 0, SEEK_END);

      map_address = (unsigned long *) mmap(0, file_size, PROT_READ, MAP_FILE | MAP_PRIVATE, fd, 0);
      if (map_address == (unsigned long *) -1)
      {
	perror("mmap");
	exit(1);
      }

      I = *map_address++;
      _state_count = *map_address++;
      _trans_count = *map_address++;

      // On recupere la taille de la matrice
      unsigned long matrix_size = *map_address++;

      // Positionnement de v1
      letters.is_here((Alphabet *) map_address, matrix_size);

      // Recherche de v2
      map_address = (unsigned long *) ((char *) map_address + matrix_size * sizeof(Alphabet));
      matrix_size = *map_address++; // Recuperation de la taille de v2

      // Positionnement de v2
      aims.is_here((State *) map_address, matrix_size);

      // Recherche de tags
      map_address = (unsigned long *) ((char *) map_address + matrix_size * sizeof(State));
      matrix_size = *map_address++;

      // Positionnement de tags
      tags.is_here((Tag *) map_address, matrix_size);
    }
#endif

  State initial() const { 
    return (I); 
  }

  set_F::const_reference final(State s) const {
    return (F[s]);
  }

  // No use of default transitions:
  State delta0(State s, const Alphabet &l) const
    {
      State q = s + Sigma::map(l);
      if (letters[q] == l) return (aims[q]);
      return (null_state);
    }

  State delta1(State s, const Alphabet &l) const
    {
      State q = delta0(s, l);
      if (q == null_state) return (delta0(s, default_letter));
      return (q);
    }


  unsigned long state_count() const { return (_state_count); }
  unsigned long trans_count() const { return (_trans_count); }
  
  const Tag& tag(State s) const { return (tags[aims[s - 1]]); }

  // WARNING: due to tag compacting, be careful modifying tag value
  Tag& tag(State s) { return (tags[aims[s - 1]]); }

  Edges delta2(State s) const { return (Edges(s, letters, aims)); }

  const_iterator begin() const
    {
      if (state_count() > 0)
      return (const_iterator((State) 1, &letters, &aims));
      else
      return (end());
    }

  const_iterator end() const
    {
      return (const_iterator(letters.size(), &letters, &aims));
    }

  float occupation_ratio() const
    {
      unsigned long occupied_cells = 0;
      State i, fin = letters.size();
    
      for (i = 0; i != fin; ++i)
      if (!free_cell(i))
      ++occupied_cells;

      return ((float) occupied_cells / (float) fin);
    }

  void stats(ostream &out = cout) const
    {
      out << "Taille matrice : (" << letters.size() << ") " << letters.size() * sizeof(Alphabet) +
      aims.size() * sizeof(State) + tags.size() * sizeof(Tag) << endl;
      out << "    lettres (" << letters.size() << ") " << letters.size() * sizeof(Alphabet) 
      << " Octets" << endl;
      out << "    buts    (" << aims.size() << ") " << aims.size() * sizeof(State) 
      << " Octets" << endl;
      out << "    tags    (" << tags.size() << ") " << tags.size() * sizeof(Tag) 
      << " Octets" << endl;
      out << "Etats          : " << state_count() << endl;
      out << "Transitions    : " << trans_count() << endl;
      out << "Taux d'occupation : " << occupation_ratio() * 100. << "%" << endl;
    }

  ~DFA_default_compact() {
#ifndef WIN32
    if (fd != 0) close(fd);
#endif
  }

  DFA_default_compact(const Alphabet &def_letter)
    : default_letter(def_letter)
    { }
  
  DFA_default_compact(istream &in, const Alphabet &def_letter) 
    : null_state(0), default_letter(def_letter)
#ifndef WIN32
    , fd(0)
#endif
    {
      read(in);
    }

  DFA_default_compact(const DFA &dfa, long opt_value = 0) 
    : null_state(0), letters((unsigned int) (dfa.state_count() * 2 + dfa.trans_count()), (Alphabet) 0), 
      aims((unsigned int) (dfa.state_count() * 2 + dfa.trans_count()),  (State) 0), 
      tags((unsigned int) 1, Tag()), I(null_state), _state_count(0), _trans_count(0), _final_count(0),
#ifndef WIN32
      fd(0), 
#endif
      F((unsigned int) dfa.state_count(), false)
    {
      if (dfa.state_count() > 0)
      {
	tag_mapping_object_function map_tag;
	typename DFA::const_iterator i, end_i = dfa.end();
	vector<State> old2new(dfa.state_count());  // vector indexed by DFA::State
	State pos, solid_first_free = 0UL, first_free;
	typename DFA::Edges::const_iterator trans, edg_end;
	long count = 0;                // For time optimization of compacting process

	for (i = dfa.begin(); i != end_i; ++i)
	{
	  ++count;
	  ++_state_count;

	  if (count == opt_value)   // We discard solid_first_free
	  {
	    do
	    {
	      ++solid_first_free;
	    }
	    while (solid_first_free + Sigma::size() < letters.size() && !free_cell(solid_first_free));
	    if (solid_first_free + Sigma::size() >= letters.size())   // Matrix is too small
	    {
	      // Doubling the size
	      size_type p = letters.size();
	      letters.resize(2 * p, (Alphabet) 0);
	      aims.resize(2 * p, (State) 0);
	      solid_first_free = p;
	    }
	    count = 0;
	  }
	  first_free = solid_first_free;

	  while (1)
	  {
	    pos = first_free + 1;  // Because we put the tag at first_free
	    typename DFA::Edges edg = dfa.delta2(*i);
	    edg_end = edg.end();

	    // Trying to put every transition by beginning at pos (first_free)
	    for (trans = edg.begin(); trans != edg_end; ++trans)
	    if (!free_cell(pos + Sigma::map((*trans).first)))
	    break;
	      
	    if (trans == edg_end)   // Ok, insert state
	    {
	      // Storing new "name" of the state
	      if (old2new.size() <= (unsigned long) *i)
	      old2new.resize((unsigned long) (*i) * 2, null_state);
	      old2new[(unsigned long) *i] = pos;

	      // Putting the tag if not already in vector tags
	      Tag t_tmp = map_tag(dfa.tag(*i));
	      vector<Tag>::iterator position = find(tags.begin() + 1, tags.end(), t_tmp);
	      aims[pos - 1] = (State) (position - tags.begin()); 
	      if (position == tags.end()) 
	      tags.push_back(t_tmp);

	      // Put the state in F if needed
	      if (dfa.final(*i))
	      {
		if (F.size() <= pos)
		F.resize(pos + 1, false);
		F[pos] = true;
		++_final_count;
	      }

	      // Puting transitions
	      unsigned long mapped_letter;
	      for (trans = edg.begin(); trans != edg_end; ++trans)
	      {
		mapped_letter = Sigma::map((*trans).first);
		letters[pos + mapped_letter] = (*trans).first;
		aims[pos + mapped_letter] = (State) (*trans).second;
		++_trans_count;
	      }
	      if (first_free == solid_first_free)
	      count = opt_value - 1;        // Force solid_first_free updating
	      break;    // move on to the next state
	    }

	    // first_free is updated
	    do
	    {
	      ++first_free;
	    }
	    while (first_free + Sigma::size() < letters.size() && !free_cell(first_free));
	    if (first_free + Sigma::size() >= letters.size())   // Matrix is too small
	    {
	      // Doubling the size
	      size_type p = letters.size();
	      letters.resize(2 * p, (Alphabet) 0);
	      aims.resize(2 * p, (State) 0);
	      first_free = p;
	    }
	  }
	}

	// Setting edges aim to states new "names"
	State last_one = 0;
	if (letters[pos] != (Alphabet) 0)
	aims[pos] = old2new[aims[pos]];
	else
	if (aims[pos] != 0) // letter == 0, aim != 0 => aim is a tag index
	last_one = pos + 1 + Sigma::size();

	if (dfa.initial() != dfa.null_state)
	I = old2new[(unsigned long) dfa.initial()];
	///			cout << "Taille de l'alphabet = " << Sigma::size() << endl;
	letters.resize(last_one + 1, (Alphabet) 0);
	aims.resize(last_one + 1, (State) 0);
	F.resize(last_one + 1, false);
      }
    }
};

#endif // dfa_default_compact_needed
#endif   // CLASS_DFA_COMPACT_HASH