//
//	File:	    dfa_matrix.h
//      Version:    ASTL 1.1
//	Copyright:  Vincent LE MAOUT
//	Date:	    Wed Jan 14 10:35:15 MET 1998
//	Descrition: Determinisic Finite Automaton Class Template ASTL1.1
//                  Representation by matrix
// 

#ifndef ASTL_CLASS_DFA_MATRIX
#define ASTL_CLASS_DFA_MATRIX

#include <iterator>   // iterator_tag
#include <functional> // less
#include <utility>    // pair
#include <astl.h>     // alphabets
#include <vector>

template <class _Sigma    = Type_alphabet<char>, 
          class _Tag      = empty_tag>
class DFA_matrix : public DFA_base
{
public:
  typedef _Sigma                   Sigma;
  typedef typename Sigma::Alphabet Alphabet;
  typedef _Tag                     Tag;

  struct StateData;
  typedef vector<StateData*>::size_type State;
  struct StateData
  {
    Tag tag;
    unsigned long size;
    State *v;
    StateData() : tag(Tag()), size(0UL), v(new State[Sigma::size()]) { 
      memset(v, 0, Sigma::size() * sizeof(State));
    }
    ~StateData() {
      delete [] v;
    }
    StateData(const StateData &x)
      : tag(x.tag), size(x.size)
      {
	v = new State[Sigma::size()];
	memcpy(v, x.v, Sigma::size() * sizeof(State));
      }
    StateData& operator = (const StateData &x)
      {
	tag = x.tag;
	size = x.size;
	memcpy(v, x.v, Sigma::size() * sizeof(State));
	return (*this);
      }
  };
  typedef skip_blanks_iterator<StateData> const_iterator;

private:
  typedef DFA_matrix<_Sigma, _Tag> self;
  typedef vector<char> set_F;

public:  
  class Edges
  {
    friend class DFA_matrix;
  private:
    typedef StateData Container;
    const Container *container;

  public:
    typedef Alphabet                    key_type;
    typedef pair<const Alphabet, State> value_type;
    typedef less<Alphabet>              key_compare;
    typedef value_type*                 pointer;
    typedef const value_type*           const_pointer;
    typedef const value_type&           const_reference;
    typedef unsigned long               size_type;
    typedef long                        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));
      }
    };

    class const_iterator : public bidirectional_iterator<value_type, ptrdiff_t>
    {
      friend class Edges;
      typedef const_iterator self;

    private:
      State *i;
      const Container *c;

      const_iterator(State *_i, const Container *_c)
	: i(_i), c(_c) 
	{ }

    public:
      const_iterator()
      { }

      bool operator == (const self& x) const {
	return (x.i == i); 
      }

      self::value_type operator * () const { 
	return (make_pair(Sigma::unmap(i - c->v), *i)); 
      }

      self& operator ++ ()       
      { 
	for(++i; i != c->v + Sigma::size() && *i == 0; ++i);
	return (*this);
      }

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

      self& operator -- () 
      { 
	for(--i; *i == 0; --i);
	return (*this);
      }

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

    typedef reverse_iterator<const_iterator> const_reverse_iterator;

    // allocation/deallocation:
    
    Edges() : container(NULL) { }
    
  private:
    Edges(const Container *c)
      : container(c) { }
    
  public:
//    key_compare key_comp() const { 
//      return (container->key_comp()); 
//    }
    
//    value_compare value_comp() const { 
//      return (value_compare(key_comp())); 
//    }
    
    const_iterator begin() const { 
      const_iterator result(container->v, container);
      if (*(result.i) == 0)
	++result;
      return (result); 
    }
    
    const_iterator end() const {
      const_iterator result(container->v + Sigma::size(), container);
      return (result);
    }

    const_reverse_iterator rbegin() const { 
      return (const_reverse_iterator(end())); 
    }
    
    const_reverse_iterator rend() const {
      return (const_reverse_iterator(begin())); 
    }
    
    bool empty() const { 
      return (container->size == 0); 
    }
    
    size_type size() const { 
      return (container->size); 
    }

    size_type max_size() const { 
      return (Sigma::size()); 
    }
    
    // map operations:
    
    const_iterator find(const key_type& x) const { 
      if (container->v[Sigma::map(x)] == 0)
	return (end());
      else
	return (const_iterator(container->v + Sigma::map(x), container));
    }
    
    size_type count(const key_type& x) const { 
      return ((container->v[Sigma::map(x)] == 0) ? 0 : 1);
    }
    
    const_iterator lower_bound(const key_type& x) const { 
      return (find(x));
    }
    
    const_iterator upper_bound(const key_type& x) const { 
      const_iterator result = find(x);
      if (result != end())
	++result;
      return (result);
    }
    
    pair<const_iterator, const_iterator> equal_range(const key_type& x) const {
      return (make_pair(lower_bound(x), upper_bound(x)));
    }
    
    // comparison:
    
    friend bool operator == (const Edges& x, const Edges& y) {
      return (x.container == y.container || *x.container == *y.container);
    }
  };

  // Back to DFA_matrix class

private:
  vector<StateData*> Q;
  State              I;     // Initial state
  set_F              F;     // Final states
  unsigned long      _state_count;
  unsigned long      _trans_count;


public:
  State null_state;

  const_iterator begin() const { 
    const_iterator result(&Q, 0);
    ++result;
    return (result);
  }

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

  void initial(State s) { 
    I = s; 
  }

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

  bool final(State s) const { 
    return ((bool) F[s]); 
  }
  
  char& final(State s) { 
    return (F[s]); 
  }

  State new_state() {
    Q.push_back(new StateData);
    F.push_back('\0');
    ++_state_count;
    return (Q.size() - 1);
  }

  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]->size;
    delete Q[s];
    Q[s] = NULL;
    --_state_count;
    F[s] = '\0';
  }

  void del_trans(State s, const Alphabet &l)
  {
    Q[s]->v[Sigma::map(l)] = 0;
    --(Q[s]->size);
    --_trans_count;
  }

  void change_trans(State s, const Alphabet &l, State new_aim) {
    Q[s]->v[Sigma::map(l)] = new_aim;
  }

  State delta1(State s, const Alphabet &l) const {
    return (Q[s]->v[Sigma::map(l)]);
  }

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

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

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

  unsigned long state_count() const { 
    return (_state_count); 
  }
  
  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); 
  }

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

  DFA_matrix(unsigned long n = 0) :
    Q(1, (StateData*) 0), I(0), F(1, '\0'), _state_count(0UL), 
    _trans_count(0UL), null_state(0) { 
      Q.reserve(n + 1);
  }

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

#endif  // CLASS_DFA_MATRIX