/*
 * ASTL - the Automaton Standard Template Library.
 * C++ generic components for Finite State Machine handling.
 * Copyright (C) 2000 Vincent Le Maout (vlemaout@lexiquest.fr).
 * 
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 * 
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 */


//
//	File:		    dfa_bin.h
//  Version:    ASTL 1.2
//	Copyright:	Vincent LE MAOUT
//	Date:		    Tue Feb 13 15:34:37  2001
//	Descrition:	Determinisic Finite Automaton Class Template ASTL1.2
//              Representation by arrays with binary search
//            

#ifndef ASTL_CLASS_DFA_BIN
#define ASTL_CLASS_DFA_BIN

#include <vector>
#include <algorithm>         // lower_bound()
#include <astl.h>
#include <functional>

template <class _Sigma    = plain, 
          class _Tag      = empty_tag>
class DFA_bin : public DFA_concept
{
  struct StateData;  

public:
  typedef DFA_bin                       self;
  typedef _Sigma                        Sigma;
  typedef typename _Sigma::Alphabet     Alphabet;
  typedef _Tag                          Tag;
  typedef vector<StateData*>::size_type State;
  
private:
  typedef vector<char> set_F;
  typedef vector<pair<Alphabet, State> > _Edges;  // internal edges structure

public:
	// Order relation taking in account only transitions letters:
  struct pair_lower_than 
    : public binary_function<pair<Alphabet, State>, pair<Alphabet, State>, bool>
  {
    bool operator () (const pair<Alphabet, State> &x, const pair<Alphabet, State> &y) const {
      return (x.first < y.first);
    }
  }; 

  class Edges
  {
    friend class DFA_bin;
    friend struct StateData;
  private:
    const _Edges *container;

  public:
    typedef Alphabet                    key_type;
    typedef pair<const key_type, State> value_type;
    typedef less<key_type>              key_compare;
    typedef value_type*                 pointer;
    typedef const value_type*           const_pointer;
    typedef value_type&                 reference;
    typedef const value_type&           const_reference;
    typedef unsigned long               size_type;
    typedef long                        difference_type;

		typedef typename _Edges::const_iterator const_iterator ;
    typedef typename _Edges::const_reverse_iterator const_reverse_iterator ;

    // allocation/deallocation:
    Edges(const _Edges *c = NULL)
      : container(c) 
		{ }
    
    Edges(const Edges& x) 
			: container(x.container) 
		{ }

    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 { 
#ifdef WIN32
      typename _Edges::const_iterator i = 
		std::lower_bound(container->begin(), container->end(), make_pair(x, 0), pair_lower_than());
#else
      typename _Edges::const_iterator i = 
		::lower_bound(container->begin(), container->end(), make_pair(x, 0), pair_lower_than());
#endif
      if (i == container->end() || (*i).first != x)
	return (container->end());
      else
	return (i);
    }

    size_type count(const key_type& x) const { 
      return ((find(x) == end()) ? 0 : 1); 
    }

    const_iterator lower_bound(const key_type& x) const {
#ifdef WIN32
      return (std::lower_bound(container->begin(), container->end(), 
				       make_pair(x, 0), pair_lower_than())); 
#else
      return (::lower_bound(container->begin(), container->end(), 
				       make_pair(x, 0), pair_lower_than())); 
#endif
    }

    const_iterator upper_bound(const key_type& x) const { 
#ifdef WIN32
      return (std::upper_bound(container->begin(), container->end(), 
															 make_pair(x, 0), pair_lower_than()));
#else
      return (::upper_bound(container->begin(), container->end(), 
														make_pair(x, 0), pair_lower_than()));
#endif
   }

    pair<const_iterator, const_iterator> equal_range(const key_type& x) const {
#ifdef WIN32
      return (std::equal_range(container->begin(), container->end(), make_pair(x, 0), pair_lower_than()));
#else
      return (::equal_range(container->begin(), container->end(), make_pair(x, 0), pair_lower_than()));
#endif
    }
    
    // comparison:
    
    friend bool operator == (const Edges& x, const Edges& y) {
      return (x.container == y.container || *x.container == *y.container);
    }
  };

private:
  struct StateData
  {
    Tag    tag;
    _Edges edges;

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

  vector<StateData*> Q;
  State I;     // Initial state
  set_F F;     // Final states
  unsigned long _trans_count;
  unsigned long _state_count;
	mutable pair<Alphabet, State> p;  // to be passed to algorithm lower_bound

public:
  typedef skip_blanks_iterator<StateData> const_iterator;
  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 (F[s] != '\0'); 
  }

  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) 
  { 
		if (s == initial()) initial(null_state);
    _trans_count -= Q[s]->edges.size();
    delete Q[s];
    Q[s] = NULL;
    --_state_count;
    F[s] = '\0';
  }

  void set_trans(State s, const Alphabet &a, State aim)
  {
		p.first = a;
		p.second = aim;
    _Edges &edges = Q[s]->edges;
    edges.insert(lower_bound(edges.begin(), edges.end(), p, pair_lower_than()), p);
    ++_trans_count;
  }

  void del_trans(State s, const Alphabet &a)
  {
    _Edges &edges = Q[s]->edges;
		p.first = a;
		edges.erase(lower_bound(edges.begin(), edges.end(), p, pair_lower_than()));
    --_trans_count;
  }

  void change_trans(State s, const Alphabet &a, State new_aim) {
    _Edges &edges = Q[s]->edges;
		p.first = a;
    (*lower_bound(edges.begin(), edges.end(), p, pair_lower_than())).second = new_aim;
  }

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

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

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

  State delta1(State s, const Alphabet &a) const
  {
		p.first = a;
	  typename _Edges::const_iterator i = 
			lower_bound(Q[s]->edges.begin(), Q[s]->edges.end(), p, pair_lower_than());

    return (i == Q[s]->edges.end() || (*i).first != a) ? null_state : (*i).second;
	}

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

  unsigned long state_count() const { 
    return (_state_count); 
  }
  
  unsigned long trans_count() const { 
    return (_trans_count); 
  }

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

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

#endif