//
//	File:		nfa_matrix.h
//      Version:        ASTL 1.1
//	Copyright:	Vincent LE MAOUT
//	Date:		Tue Dec 15 15:25:57 MET 1998
//	Descrition:	Non Determinisic Finite Automaton Class Template
//                      Representation by a 3D matrix
//

#ifndef ASTL_CLASS_NFA_MATRIX
#define ASTL_CLASS_NFA_MATRIX

#include <vector>
// #include <function.h>
// #include <algo.h>
#include <iterator>
// #include <limits.h>
// #include <math.h>
#include <astl.h>
#include <state_set.h>

template <class _Sigma    = Type_alphabet<char>, 
          class _Tag      = empty_tag,
          class Allocator = default_allocator>
class NFA_matrix
{
public:
  typedef _Sigma          Sigma;
  typedef typename _Sigma::Alphabet Alphabet;
  class StateData;
  typedef State_set<StateData, Allocator>::State          State;
  typedef State_set<StateData, Allocator>::const_iterator const_iterator;
  typedef _Tag            Tag;

private:
  typedef NFA_matrix self;
  typedef vector<bool, Allocator> set_F;

public:
  class _Edges
  {
    friend self;
  private:
    typedef vector<vector<State, Allocator>, Allocator> Storage;
    Storage v;
    unsigned long _size;
    
  public:
    typedef Alphabet                 key_type;
    typedef pair<const key_type, State>   value_type;
    typedef less<Alphabet>           key_compare;
    
    typedef Storage::const_pointer   const_pointer;
    typedef Storage::pointer         pointer;
    typedef Storage::reference       reference;
    typedef Storage::const_reference const_reference;
    typedef Storage::size_type       size_type;
    typedef Storage::difference_type difference_type;

    class const_iterator : bidirectional_iterator<value_type, Storage::difference_type>
    {
    private:
      const Storage*                      container;
      Storage::const_iterator             letter_iterator;
      Storage::value_type::const_iterator aim_iterator;

      typedef const_iterator self;
      const_iterator(const Storage::const_iterator &i, const Storage &c,
		     const Storage::value_type::const_iterator &a) 
	: container(&c), letter_iterator(i), aim_iterator(a)  { }

    public:
      friend _Edges;
      const_iterator() { }
      friend bool operator == (const self &left, const self &right) { 
	return (left.aim_iterator == right.aim_iterator &&
		left.letter_iterator == right.letter_iterator);
      }
      value_type operator * () const { 
	return (value_type(Sigma::unmap(letter_iterator - container->begin()), *aim_iterator));
      }
      self& operator ++ ()
      {
	++aim_iterator;
	if (aim_iterator == (*letter_iterator).end())
	{
	  // find next letter
	  Storage::const_iterator finish = container->end();
	  for(++letter_iterator; 
	      letter_iterator != finish && (*letter_iterator).empty(); 
	      ++letter_iterator);
	  if (letter_iterator != finish)
	    aim_iterator = (*letter_iterator).begin();  // next aim
	}
	return (*this);
      }

      self operator ++ (int)
      {
	const_iterator tmp = (*this);
	++(*this);
	return tmp;
      }

      self& operator -- ()
      {
	if (aim_iterator == (*letter_iterator).begin())     
	{
	  // find previous letter
	  Storage::const_iterator start = container->begin();
	  for(;
	      letter_iterator != start && (*letter_iterator).empty(); 
	      ++letter_iterator);
	  if (letter_iterator == start && !(*letter_iterator).empty())
	    aim_iterator = (*letter_iterator).end() - 1;  // previous aim
	  else
	    aim_iterator = (*letter_iterator).begin();
	}
	else
	  --aim_iterator;
	return (*this);
      }
	  
      const_iterator operator -- (int)
      {
	const_iterator tmp = (*this);
	--(*this);
	return tmp;
      }
    };

    // Back to _Edges class
    
    _Edges(size_type n) : v(n), _size(0UL) { }

    const_iterator begin() const
    {
      if (empty())
	return (end());
      Storage::const_iterator x;
      Storage::const_iterator finish = v.end();
      for (x = v.begin(); x != finish && (*x).empty(); ++x);
      return (const_iterator(x, v, (*x).begin())); 
    }

    const_iterator end() const { 
      return (const_iterator(v.end(), v, (*(v.end() - 1)).end())); 
    }

    size_type size() const {
      return (_size);
    }

    bool empty() const {
      return (size() == 0);
    }
    
  public:
    size_type count(const key_type &k) const {
      return (v[Sigma::map(k)].size());
    }

    const_iterator lower_bound(const key_type &k) const {
      if (v[Sigma::map(k)].empty())
	return (end());
      else
	return (const_iterator(v + Sigma::map(k), v, v[Sigma::map(k)].begin()));
    }

    const_iterator upper_bound(const key_type &k) const {
      if (v[Sigma::map(k)].empty())
	return (end());
      else
	return (const_iterator(v + Sigma::map(k), v, v[Sigma::map(k)].end()));
    }

    pair<const_iterator, const_iterator> equal_range(const key_type &k) const {
      return (make_pair(lower_bound(k), upper_bound(k)));
    }

  };
  
private:
  struct StateData
  {
    Tag   tag;
    _Edges edges;

  public:
    StateData() : tag(Tag()), edges(Sigma::size())
    { }
  };

  typedef allocator_interface<StateData, Allocator> state_allocator;

  StateData bogus;
  state_allocator alloc;
  State_set<StateData, Allocator> Q;
  vector<State>                   I;     // Initial states
  set_F                           F;     // Final states
  unsigned long _trans_count;

public:
  State null_state;
  typedef const _Edges& Edges;

  const vector<State>& initial() const { 
    return (I); 
  }

  vector<State>& initial() { 
    return (I); 
  }

  set_F::reference final(State s) 
  { 
    if (s > F.size())
      F.resize(s, false);
    return (F[s - 1]); 
  }

  set_F::const_reference final(State s) const 
  { 
    if (s > F.size())
      return (false);
    return (F[s - 1]); 
  }

  template <class InputIterator>
  bool final(InputIterator first, InputIterator last) const
  {
    for(; first != last; ++first)
      if (final(*first))
	return (true);
    return (false);
  }

  State new_state() 
  { 
    StateData *where = alloc.allocate(1);
    alloc.construct(where, bogus);
    return (Q.add(where));
  }

  template <class OutputIterator>
  OutputIterator new_state(unsigned long how_many, OutputIterator x)
  {
    for(; how_many > 0; --how_many)
      *x++ = new_state();
    return (x);
  }

  void del_state(State s) 
  { 
    _trans_count -= Q[s]->edges.size();
    alloc.destroy(Q[s]);
    alloc.deallocate(Q[s], 1);
    Q.del(s);
  }

  void set_trans(State s, const Alphabet &l, State aim)
  {
    Q[s]->edges.v[Sigma::map(l)].push_back(l);
    ++_trans_count;
  }

  template <class InputIterator>
  void set_trans(State s, const Alphabet &l, InputIterator first, InputIterator last)
  {
    for(; first != last; ++first, ++_trans_count)
      Q[s]->edges.v[Sigma::map(l)].push_back(*first);
  }
    
  void del_trans(State s, const Alphabet &l)
  {
    _Edges &e = Q[s]->edges;
    unsigned long mapped_letter = Sigma::map(l);

    _trans_count -= e.v[mapped_letter].size();
    e._size -= e.v[mapped_letter].size();
    e.v[mapped_letter].clear();
  }

  void del_trans(State s, const Alphabet &l, State aim)
  {
    _Edges &e = Q[s]->egdes;
    unsigned long mapped_letter = Sigma::map(l);

    e.v[mapped_letter].erase(find(e.v[mapped_letter].begin(), e.v[mapped_letter].end(), s));
    --e._size;
    __trans_count;
  }

  // Redirection of transition
  void change_trans(State s, const Alphabet &l, State former_aim, State new_aim) {
    *(find(Q[s]->edges.v[Sigma::map(l)].begin(), 
	   Q[s]->edges.v[Sigma::map(l)].end(), s)) = new_aim; 
  }


  void copy_state(State from, State to)
  {
    _trans_count += Q[from]->edges.size() - Q[to]->edges.size();
    *Q[to] = *Q[from];
  }

  template <class OutputIterator>
  OutputIterator delta1(State s, const Alphabet &l, OutputIterator x) const
  {
    return (copy(Q[s]->edges.v[Sigma::map(l)].begin(), 
		 Q[s]->edges.v[Sigma::map(l)].end(), x));
  }
		 
  template <class OutputIterator, class InputIterator>
  OutputIterator delta1(InputIterator first, InputIterator last, const Alphabet &l,
			OutputIterator x) const
  {
    for (; first != last; ++first)
      x = delta1(*first, l, x);
    return (x);
  }

  State duplicate_state(State q)
  {
    State s = new_state();
    *Q[s] = *Q[q];
    _trans_count += Q[q]->edges.size();
    return (s);
  }

  unsigned long state_count() const { return (Q.card()); }
  unsigned long trans_count() const { return (_trans_count); }
  
  Tag& tag(State s) { 
    return (Q[s]->tag); 
  }

  const Tag& tag(State s) const { 
    return (Q[s]->tag); 
  }

  const_iterator begin() const { 
    return (Q.begin()); 
  }
  
  const_iterator end() const { 
    return (Q.end()); 
  }

  Edges delta2(State s) const { return (Q[s]->edges); }

  NFA_matrix(unsigned long n = 0, Allocator a = Allocator()) : 
    alloc(a), Q(), I(0), F(0), _trans_count(0UL), 
    null_state(0)
  { 
    Q.reserve(n + 1);
  }

  ~NFA_matrix()
  {
    const_iterator start, finish = end();
    for(start = begin(); start != finish; ++start)
      del_state(*start);
  }

};

#endif  // CLASS_DFA_MATRIX