/*
 * 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
 *
 */

#ifndef ASTL_CLASS_DFA_HASH
#define ASTL_CLASS_DFA_HASH

#include <hash_map>
#include <utility>  // pair<>
#include <functional>
#include <astl.h>

// Intérêt de cette classe: complexité spatiale dépendant uniquement du
// nombre de transitions et pas du nombre d'état (donc pas de tags...)
// Requirements: la fonction de hachage utilise Sigma::map()

template <class _Sigma = plain>
class DFA_hash : public DFA_concept
{
public:
	typedef _Sigma                     Sigma;
	typedef typename _Sigma::char_type Alphabet;
	typedef size_t                     State;
	typedef empty_tag                  Tag;

protected:
	typedef pair<State, Alphabet> key;
	typedef State                 data;
	struct hash_function : public unary_function<pair<State, Alphabet>, size_t>
	{
		// On essaie de minimiser les collisions: 
		// Valeur de hachage pour un état q = q * la taille de l'alphabet + la lettre
		result_type operator() (const argument_type &x) const {
			return x.first * Sigma::size + Sigma::map(x.second);
		}
	};
	
	// La map associe des paires (état, lettre) au but de la transition
	typedef hash_map<key, data, hash_function, equal_to<key> > hasher_type;
	hasher_type hasher;

	unsigned long _state_count;
	State         current;
	State         I;
	vector<char>  F;
	Tag           bogus;

public:
	State null_state;

	class Edges 
	{
	protected:
		State  q;
		const hasher_type *h;

	public:
		Edges()
			: q(0), h(NULL)
		{ }

		Edges(State p, const hasher_type &H)
			: q(p), h(&H)
		{ }

		typedef size_t                      size_type;
		typedef Alphabet                    key_type;
		typedef State                       data_type;
		typedef pair<const Alphabet, State> value_type;

		class const_iterator : public bidirectional_iterator<Edges::value_type, ptrdiff_t>
		{
		protected:
			State q;
			typename Sigma::const_iterator i;
			const hasher_type *h;

		public:
			typedef const_iterator self;

			const_iterator()
			{ }

			const_iterator(State p, typename Sigma::const_iterator j, const hasher_type &H)
				: q(p), i(j), h(&H)
			{ }

			Edges::value_type operator* () const {
				return make_pair(*i, (*(h->find(make_pair(q, *i)))).second);
			}
			
			self& operator++ () {
				for(++i; i != Sigma::end() && h->find(make_pair(q, *i)) == h->end(); ++i);
				return *this;
			}
			
			self operator++ (int) {
				self tmp = *this;
				++*this;
				return tmp;
			}
			
			bool operator== (const self &x) const {
				return i == x.i;
			}
		};

		const_iterator begin() const {    // linéaire !!!!!!
			const_iterator r(q, Sigma::begin(), *h);
			if (h->find(make_pair(q, *(Sigma::begin()))) == h->end())
				++r;
			return r;
		}

		const_iterator end() const {
			return const_iterator(q, Sigma::end(), *h);
		}

		size_t size() const {     // linéaire !!!!!
			size_t r = 0;
			distance(begin(), end(), r);
			return r;
		}

		bool empty() const {      // linéaire !!!!!!
			const_iterator i = begin();
			return i == end();
		}

		bool operator== (const Edges &x) const {
			return lexicographical_compare_3way(begin(), end(), x.begin(), x.end()) == 0;
		}

		const_iterator find(const key_type &k) const {
			hasher_type::const_iterator i = h->find(make_pair(q, k));
			if (i == h->end())
				return end();
			return const_iterator(q, k, *h);
		}

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

		pair<const_iterator, const_iterator> equal_range(const key_type &k) const {
			const_iterator r = find(k);
			if (r == end()) return make_pair(r, r);
			return make_pair(r, ++r);
		}
	};      // class Edges

	DFA_hash(unsigned long = 0)
		: _state_count(0), current(0), 
			I(0), F(1, '\0'), null_state(0)
	{ }

	State new_state() {
		++_state_count;
		F.push_back('\0');
		return ++current;
	}

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

	bool final(State s) const {
		return F[s] == '\1';
	}

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

	void del_state(State s) {   // Ca fait très mal... (linéaire en le nb de transitions)
		if (s == initial()) initial(null_state);
		pair<State, Alphabet> p(s, Alphabet());
		for(typename _Sigma::const_iterator i = _Sigma::begin(); i != _Sigma::end(); ++i) {
			p.second = *i;
			hasher.erase(p);
		}
		--_state_count;
	}

	void copy_state(State from, State to) {   // linéaire !!!!!!!!
		del_state(to);
		++_state_count;  // because del_state decrements state_count
		pair<State, Alphabet> pfrom(from, Alphabet()), pto(to, Alphabet());
		for(typename _Sigma::const_iterator i = _Sigma::begin(); i != _Sigma::end(); ++i) {
			pfrom.second = *i;
			hasher_type::const_iterator j = hasher.find(pfrom);
			if (j != hasher.end()) {
				pto.second = *i;
				hasher[pto] = (*j).second;
			}
		}
		final(to) = final(from);
	}
		
	State duplicate_state(State q) {     // linéaire !!!!!!!
		State p = new_state();
		pair<State, Alphabet> pfrom(q, Alphabet()), pto(p, Alphabet());
		for(typename _Sigma::const_iterator i = _Sigma::begin(); i != _Sigma::end(); ++i) {
			pfrom.second = *i;
			hasher_type::const_iterator j = hasher.find(pfrom);
			if (j != hasher.end()) {
				pto.second = *i;
				hasher[pto] = (*j).second;
			}
		}
		final(p) = final(q);
		return q;
	}
		
  State initial() const { 
    return (I); 
  }

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

	void set_trans(State s, const Alphabet &a, State aim) {
		hasher[make_pair(s, a)] = aim;
	}

	void del_trans(State s, const Alphabet &a) {
		hasher.erase(make_pair(s, a));
	}

	void change_trans(State s, const Alphabet &a, State new_aim) {
		hasher[make_pair(s, a)] = new_aim;
	}

	State delta1(State s, const Alphabet &a) const {
		hasher_type::const_iterator i = hasher.find(make_pair(s, a));
		return i == hasher.end() ? null_state : (*i).second;
	}

	Edges delta2(State s) const {
		return Edges(s, hasher);
	}

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

  unsigned long trans_count() const { 
		return hasher.size();
	}

	Tag& tag(State) {
		return bogus;
	}
	
	const Tag& tag(State) const {
		return bogus;
	}
};

#endif // ASTL_CLASS_DFA_HASH