//
//	File:		dfa_map.hh
//	Copyright:	Vincent LE MAOUT
//	Date:		Mon Nov  2 12:24:35 MET 1998
//	Descrition:	Determinisic Finite Automaton Class Template ASTL1.10
//                      Representation by STL map
//                      ASTL 1.1 (g++ 2.8.0) see std1.1.txt file
//

#ifndef ASTL_CLASS_DFA_MAP
#define ASTL_CLASS_DFA_MAP

#include <map>                // map<>
#include <vector>             // vector<>, vector<bool>
#include <astl.h>

template <class _Sigma    = Type_alphabet<char>, 
          class _Tag      = empty_tag>
class DFA_map : public DFA_base
{
public:
  typedef typename _Sigma::Alphabet Alphabet; 
  typedef _Sigma                    Sigma; 
  typedef _Tag                      Tag;
  struct StateData;
  typedef vector<StateData*>::size_type State;

  struct StateData
  {
    Tag            tag;
    map<Alphabet, State> edges;
  };

  typedef skip_blanks_iterator<StateData> const_iterator;

private:
  typedef vector<char> set_F;
  typedef map<Alphabet, State> container_type;

public:
  // Edges class is a proxy allowing to access outgoing transitions of
  // a state through its STL map interface.
  // Modifying transitions is not possible through this class, thus it only
  // implements constant map methods. 
  class Edges
  {
    friend class DFA_map;
    friend class StateData;
  private:
    const map<Alphabet, State> *container;
    
  public:
    typedef container_type::key_type        key_type;
    typedef container_type::value_type      value_type;
    typedef container_type::key_compare     key_compare;
    typedef container_type::const_reference const_reference;
    typedef container_type::size_type       size_type;
    typedef container_type::difference_type difference_type;
    typedef container_type::value_compare   value_compare;

    typedef typename map<Alphabet, State>::const_iterator         const_iterator;
    typedef typename map<Alphabet, State>::const_reverse_iterator const_reverse_iterator;

    // allocation/deallocation:
    
  public: // pour des question d'heritage dans la class dfa_online 
    Edges(const container_type *c)
      : container(c) { }

  public:
    Edges(const Edges& x) : container(x.container) { }
    ~Edges() { }
    
    // accessors:
    
    key_compare key_comp() const { return (container->key_comp()); } 
    value_compare value_comp() const { return (container->value_comp()); }
    const_iterator begin() const { return (container->begin()); }
    const_iterator end() const { return (container->end()); }
    const_reverse_iterator rbegin() const { return (container->rbegin()); }
    const_reverse_iterator rend() const { return (container->rend()); }
    bool empty() const { return (container->empty()); }
    size_type size() const { return (container->size()); }
    size_type max_size() const { return (container->max_size()); }
    

    // map operations:
    
    const_iterator find(const key_type& x) const { return (container->find(x)); }
    size_type count(const key_type& x) const { return (container->count(x)); }
    const_iterator lower_bound(const key_type& x) const { return (container->lower_bound(x)); }
    const_iterator upper_bound(const key_type& x) const { return (container->upper_bound(x)); }
    pair<const_iterator, const_iterator> equal_range(const key_type& x) const {
      return (container->equal_range(x));
    }

    // comparison:
    
    friend bool operator == (const Edges& x, const Edges& y) {
      return (x.container == y.container || *x.container == *y.container);
    }
  };

private:
  vector<StateData*> Q;
  State              I;     // Initial state
  set_F              F;     // Final states
  unsigned long      _trans_count;
  unsigned long      _state_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())); 
  }

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

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

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

  bool final(State s) const { 
    return ((bool) 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]->edges.size();
    delete Q[s];
    Q[s] = NULL;
    --_state_count;
    F[s] = '\0';
  }

  void del_trans(State s, const Alphabet &l)
  {
    Q[s]->edges.erase(l);
    --_trans_count;
  }

  void change_trans(State s, const Alphabet &l, State aim) {
    Q[s]->edges[l] = aim;
  }

  State delta1(State s, const Alphabet &l) const
  {
    container_type::iterator vi = Q[s]->edges.find(l);
    if (vi == Q[s]->edges.end())             // No edges by this letter
      return (null_state);
    else return ((*vi).second);
  }

  void set_trans(State s, const Alphabet &l, State aim)
  {
    Q[s]->edges[l] = aim;
    ++_trans_count;
  }

  void copy_state(State from, State to)
  {
    _trans_count += Q[from]->edges.size() - Q[to]->edges.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]->edges.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]->edges))); }

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

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

};

#endif   // CLASS_DFA_MAP