//
//	File:		nfa_mmap.h
//      Version:        ASTL 1.1
//	Copyright:	Vincent LE MAOUT
//	Date:		Fri Oct 30 19:16:10 MET 1998
//	Descrition:	ASTL 1.1 Non Determinisic Finite Automaton Class Template
//                      Representation by STL multimap
//

#ifndef ASTL_CLASS_NFA_MMAP
#define ASTL_CLASS_NFA_MMAP

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

template <class _Sigma    = Type_alphabet<char>,
          class _Tag      = empty_tag, 
          class Allocator = default_allocator>
class NFA_mmap : public NFA_base
{
public:
  typedef typename _Sigma::Alphabet Alphabet; 
  typedef _Sigma                    Sigma; 
  typedef _Tag                      Tag;

  class StateData;  
  typedef State_set<StateData, Allocator>::State State;
  typedef State_set<StateData, Allocator>::const_iterator const_iterator;
  
private:
  typedef vector<bool, Allocator> set_F;

  struct StateData
  {
    Tag   tag;
    multimap<Alphabet, State, less<Alphabet>, Allocator> edges;

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

  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:
  class Edges
  {
    friend class NFA_mmap;
  private:
    const multimap<Alphabet, State, less<Alphabet>, Allocator> *container;

  public:
    typedef multimap<Alphabet, State, less<Alphabet>, Allocator >::key_type        key_type;
    typedef multimap<Alphabet, State, less<Alphabet>, Allocator >::value_type      value_type;
    typedef multimap<Alphabet, State, less<Alphabet>, Allocator >::key_compare     key_compare;
    typedef multimap<Alphabet, State, less<Alphabet>, Allocator >::const_reference const_reference;
    typedef multimap<Alphabet, State, less<Alphabet>, Allocator >::const_pointer   const_pointer;
    typedef multimap<Alphabet, State, less<Alphabet>, Allocator >::size_type       size_type;
    typedef multimap<Alphabet, State, less<Alphabet>, Allocator >::difference_type difference_type;
    typedef multimap<Alphabet, State, less<Alphabet>, Allocator >::value_compare   value_compare;
    
    typedef multimap<Alphabet, State, less<Alphabet>, Allocator >::const_iterator const_iterator;
    typedef multimap<Alphabet, State, less<Alphabet>, 
                     Allocator >::const_reverse_iterator const_reverse_iterator;

    // allocation/deallocation:
  
  private:
    Edges(multimap<Alphabet, State, less<Alphabet>, Allocator> *c)
      : container(c) { }
    
  public:
    Edges(const Edges& x) : container(x.container) { }
    ~Edges() { }
  
    key_compare key_comp() const { return (container->key_comp()); } 

    // accessors:

    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()); }
    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));
    }

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

  // Back to NFA_map class

public:
  State null_state;

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

  const vector<State>& initial() const { 
    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.insert(make_pair(l, aim));
    ++_trans_count;
  }

  template <class InputIterator>
  void set_trans(State s, const Alphabet &l, InputIterator first, InputIterator last)
  {
    multimap<Alphabet, State, less<Alphabet>, Allocator> &e = Q[s]->edges;
    unsigned long count;

    for (count = 0; first != last; ++first, ++count)
      e.insert(make_pair(l, *first));

    _trans_count += count;
  }

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

  void del_trans(State s, const Alphabet &l, State aim)
  {
    multimap<Alphabet, State, less<Alphabet> > &e = Q[s]->edges;
    multimap<Alphabet, State, less<Alphabet> >::const_iterator p = e.find(l);
    for(; (*p).second != aim; ++p);
    e.erase(p);
    --_trans_count;
  }
    
  void change_trans(State s, const Alphabet &l, State former_aim, State new_aim)
  {
    multimap<Alphabet, State, less<Alphabet>, Allocator> &e = Q[s]->edges;
    multimap<Alphabet, State, less<Alphabet>, Allocator >::iterator p = e.find(l);
    for(; (*p).second != former_aim; ++p);
    (*p).second = 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
  {
    pair<multimap<Alphabet, State, less<Alphabet>, Allocator>::const_iterator, 
         multimap<Alphabet, State, less<Alphabet>, Allocator>::const_iterator> p 
      = Q[s]->edges.equal_range(l);
    for (; p.first != p.second; ++p.first)
      *x++ = (*p.first).second;
    return (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); }

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

  const_iterator begin() const { return (Q.begin()); }
  const_iterator end() const { return (Q.end()); }
  
  NFA_mmap(unsigned long n = 0, Allocator a = Allocator()) 
    : alloc(a), Q(), I(0), F(0), _trans_count(0), null_state(0) { 
      Q.reserve(n + 1);
  }

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

#endif   // CLASS_NFA_MMAP