#ifndef ASTL_CLASS_DFA_MIN_HASH
#define ASTL_CLASS_DFA_MIN_HASH

#include <iostream>
#include <set>
#include <vector>
#include <utility>
#include <functional>
#include <string>
#include <astl.h>    // Type_alphabet< >
#include <cursor.h>  // stack_cursor< >
#include <cstring>   // memcpy
#include <bitset>
#include <iterator>
#include <utility>

#ifndef LETTER_COMPARATOR
#define LETTER_COMPARATOR
struct letter_comparator :  binary_function<long , long, bool>
{
  bool operator () ( long a, long b) { return a < b ; }
 static  bool lower( long a, long b) { return a > b ; }
};
#endif 
struct lower_than_transition;

// On stocke une transition dans un ensemble de 32 bits:
// 1 octet pour la lettre, 3 octets pour le n° de l'état destination
// D'où les limitations: alphabet à 256 caractères, environ 16 millions d'états maximum
class transition
{
protected:
	typedef bitset<32> bitset_type; 
	static const bitset_type   letter_mask;  // le masque d'extraction de la lettre
	static const bitset_type   aim_mask;     // le masque d'extraction du but
	static const unsigned long LETTER_SHIFT;  // le décalage pour insérer la lettre

 	bitset_type data;  
	friend lower_than_transition;

public:
	transition()
		: data(0UL) 
	{ }
 	transition(char a, unsigned long aim = 0)
		: data((bitset_type(a) << LETTER_SHIFT) | bitset_type(aim))
	{ }
	char letter() const {
		return (char) (((data & letter_mask) >> LETTER_SHIFT).to_ulong());
	}
	unsigned long aim() const {
		return (data & aim_mask).to_ulong();
	}
	void aim(unsigned long new_aim) {
		data &= letter_mask;  // positionne le but à 0 en gardant la lettre
		data |= bitset_type(new_aim);      // positionne le but à new aim
	}
	// Une relation d'ordre sur les transitions (à utiliser pour comparer les états):
	bool operator< (const transition &x) const {
		return data.to_ulong() < x.data.to_ulong();
	}
};

const transition::bitset_type transition::letter_mask(0xFF000000);
const transition::bitset_type transition::aim_mask(0x00FFFFFF);
const unsigned long           transition::LETTER_SHIFT = 24;  // le décalage pour insérer la lettre

// Ces comparaisons ne tiennent pas compte des buts. Elles ne servent qu'à accéder au
// tableau des transitions triées. La clé est la lettre.

struct lower_than_transition : binary_function<transition, transition, bool>
{
	bool operator()(const transition &x, const transition &y) const {
		return letter_comparator::lower( (x.data & transition::letter_mask).to_ulong() ,  (y.data & transition::letter_mask).to_ulong());
	}
};

// Pour l'instant, l'allocateur ne fait rien de spécial:
template <class T>
class astl_allocator
{
public:
	typedef T            value_type;
	typedef unsigned int size_type;
	typedef int          difference_type;
	typedef T*           pointer;
	typedef const T*     const_pointer;
	typedef T&           reference;
	typedef const T&     const_reference;
	
	unsigned long bytes_allocated, bytes_deallocated;
	unsigned long allocated_objects, deallocated_objects;
	unsigned long constructed_objects, destroyed_objects;

	astl_allocator()
		: bytes_allocated(0), bytes_deallocated(0),
			allocated_objects(0), deallocated_objects(0),
			constructed_objects(0), destroyed_objects(0)
	{ }

	ostream& report(ostream &out) const {
		out << "Octets alloués    " << bytes_allocated << ", désalloués " << bytes_deallocated << endl;
		out << "Objets alloués    " << allocated_objects << ", désalloués " << deallocated_objects << endl;
		out << "Objets construits " << constructed_objects << ", détruis " << destroyed_objects << endl;
		return out;
	}

	pointer allocate(size_type n, const_pointer = NULL) {
		bytes_allocated += n*sizeof(T);
		allocated_objects += n;
		return (pointer) new char[n * sizeof(T)];
	}

	void deallocate(pointer p, size_type n = 1) {
		bytes_deallocated += n * sizeof(T);
		deallocated_objects += n;
		delete [] ((char*) p);
	}

	void construct(pointer p, const_reference t) {
		constructed_objects++;
		new ((void*) p) T(t);
	}

	void    destroy(pointer p) {
		destroyed_objects++;
		p->~T();
	}
};

// Concept:
// Un état possède les attributs suivants:
// - Degré entrant (nombre de transitions pointant vers l'état)
// - Booléen final/non final
// - Hauteur (taille du plus grand mot appartenant au langage de l'état)
// - Cardinal (nombre de transitions sortant de l'état et taille du tableau)
// Implémentation:
// - Le degré entrant et le drapeau final/non final sont stockés sur 32 bits:
//   31 bits pour le nombre de transition entrantes et 1 bit pour le drapeau
// - La hauteur et le cardinal sont stockés sur 32 bits:
//   24 bits pour la hauteur et 8 bits pour le nombre de transitions
// D'où les limitations suivantes: longueur des mots limitée à environ 16Mo, transitions entrantes
// limitées à environ 2 milliards.
//
// Optimisation supplémentaire:
// Après observation, on constate que 
// pour des mots du français ou de l'anglais, près de la moitié des états n'a qu'une
// transition sortante => lorsque card() == 1, la transition est stockée à la place du
// pointeur de tableau de transition (union entre un pointeur et une transition).

typedef bitset<32> bitset_type;


static const bitset_type final_mask(1);
static const bitset_type degree_in_mask(0xFFFFFFFF << 1);
static const bitset_type card_mask(0x000000FF);
static const bitset_type height_mask(0xFFFFFF00);
static const unsigned long      DEGREE_IN_SHIFT = 1;
static const unsigned long      HEIGHT_SHIFT = 8;

template <class letag>
class state
{
protected:
	
	typedef letag                Tag;


	bitset_type degree_in_final; // 31 bits pour le nb de transition entrantes et 1 bit pour final/non final
	bitset_type height_card;    // 24 bits pour la hauteur et 8 bits pour le nb de transitions sortantes
	
	union {
	private:
		transition *_t;// le tableau des transitions sortantes trié grâce à la relation d'ordre lower_than_transition
		char _tr[sizeof(transition)]; // lorsqu'il n'y a qu'une transition (card() == 1), elle est stockée ici
	public:
		// Accesseurs:
		transition*& t() {
			return _t;
		}
		transition& tr() {
			return *((transition*) _tr);
		}
		transition* const & t() const {
			return _t;
		}
		const transition& tr() const {
			return *((transition*) _tr);
		}
	} tunion;
	 Tag ww;
public:
	typedef transition*       iterator;
	typedef const transition* const_iterator;

	state()
	  : degree_in_final(0UL), height_card(0UL),ww()
	{ 
		tunion.t() = NULL;
	}
	Tag&      tag() { return ww; }
        const Tag& tag() const { return ww; }
  
	state(const state &x)
	  : degree_in_final(x.degree_in_final), height_card(x.height_card)  //,ww(x.ww)
	{
		degree_in_final &= final_mask; // degree entrant positionné à 0
		unsigned long n = x.card();
		switch (n) {
		case	0 : tunion.t() = NULL; break;
		case	1 : tunion.tr() = x.tunion.tr(); break;
		default :
			tunion.t() = new transition[n];
			memcpy(tunion.t(), x.tunion.t(), sizeof(transition) * n);  // Warning: la classe DFA_min_hash est responsable de la
			                                         // mise à jour des degrés entrants
		}
	}

	~state() {
		if (card() > 1) delete [] tunion.t();
	}
	
	
	unsigned long delta1(char a) const {
		const_iterator where = lower_bound(begin(), end(), transition(a), lower_than_transition());
		return (where == end() || (*where).letter() != a) ? 0 : (*where).aim();
	}

	const_iterator begin() const {
		return card() == 1 ? &(tunion.tr()) : tunion.t();
	}

	const_iterator end() const {
		return card() == 1 ? &(tunion.tr()) + 1 : (tunion.t() + card());
	}

	iterator begin() {
		return card() == 1 ? &(tunion.tr()) : tunion.t();
	}

	iterator end() {
		return card() == 1 ? &(tunion.tr()) + 1 : (tunion.t() + card());
	}

	unsigned long size() const {
		return card();
	}

	const_iterator find(char a) const {
		const_iterator where = lower_bound(begin(), end(), transition(a), lower_than_transition());
		return (where == end() || (*where).letter() != a) ? end() : where;
	}

	iterator find(char a) {
		iterator where = lower_bound(begin(), end(), transition(a), lower_than_transition());
		return (where == end() || (*where).letter() != a) ? end() : where;
	}

	void insert(const transition &x) {  // Precondition: la transition étiquetée par x.letter() n'existe pas
		unsigned long n = card();
		if (n == 0) 
			tunion.tr() = x; 
		else {
			iterator where = lower_bound(begin(), end(), x, lower_than_transition());
			unsigned long i = where - begin();
			transition *tmp = new transition[n + 1];
			memcpy(tmp, begin(), i * sizeof(transition));
			tmp[i] = x;
			memcpy(tmp + i + 1, where, (end() - where) * sizeof(transition));
			if (n > 1) delete [] tunion.t();
			tunion.t() = tmp;
		}
		// cerr << " insertion de transition " << card() << endl ;
		inc_card();
		// cerr << " insertion de transition " << card() << endl ;
	}

	void change_trans(const transition &x) {   // Redirige la transition étiquetée par x.letter() vers x.aim()
		                                         // Précondition: la transition redirigée existe
		(*(lower_bound(begin(), end(), x, lower_than_transition()))) = x;
	}

	void erase(const transition &x) {  // Precondition: la transition étiquetée par x.letter() existe
		unsigned long n = card();
		switch (n) {
		case 1 : tunion.t() = NULL; break;
		case 2 : 
			{
				transition *tmp = tunion.t();
				tunion.tr() = x.letter() < tmp[1].letter() ? tmp[1] : tmp[0];
				delete [] tmp;
				break;
			}
		default :
			{
				iterator where = lower_bound(begin(), end(), x, lower_than_transition());
				transition *tmp = new transition[n - 1];
				memcpy(tmp, begin(), (where - begin()) * sizeof(transition));
				memcpy(tmp + (where - begin()), where + 1, (end() - (where + 1)) * sizeof(transition));
				delete [] tunion.t();
				tunion.t() = tmp;
			}
		}
		dec_card();
	}

	unsigned long degree_in() const {
		return ((degree_in_final & degree_in_mask) >> DEGREE_IN_SHIFT).to_ulong();
	}

	void inc_degree_in() {
		unsigned long d = degree_in() + 1;
		degree_in_final &= final_mask;   // on ne garde que le bit (final/non final)
		degree_in_final |= bitset_type(d) << DEGREE_IN_SHIFT;
	}

	void dec_degree_in() {
		unsigned long d = degree_in() - 1;
		degree_in_final &= final_mask;
		degree_in_final |= bitset_type(d) << DEGREE_IN_SHIFT;
	}

	unsigned long card() const {
		return (height_card & card_mask).to_ulong();
	}

	void inc_card() {
		unsigned long c = card() + 1;
		height_card &= height_mask;
		height_card |= bitset_type(c);
	}

	void dec_card() {
		unsigned long c = card() - 1;
		height_card &= height_mask;
		height_card |= bitset_type(c);
	}
		
	unsigned long height() const {
		return ((height_card & height_mask) >> HEIGHT_SHIFT).to_ulong();
	}

	void height(unsigned long h) {
		height_card &= card_mask;
		height_card |= bitset_type(h) << HEIGHT_SHIFT;
	}

	bool final() const {
		return (degree_in_final & final_mask).to_ulong() == 1;
	}

	class bool_reference
	{
		bitset_type &r;
	public:
		bool_reference(bitset_type &ref)
			: r(ref)
		{ }
		operator bool () const {
			return (r & final_mask).to_ulong() == 1;
		}
		bool_reference& operator= (const bool_reference &x) {
			if (x == true) r |= final_mask;
			else r &= degree_in_mask;
			return *this;
		}
		bool_reference& operator= (bool b) {
			if (b == true) r |= final_mask;
			else r &= degree_in_mask;
			return *this;
		}
		bool operator== (const bool_reference &x) const {
			return (r & final_mask) == (x.r & final_mask);
		}
		bool operator== (bool b) const {
			return ((r & final_mask).to_ulong() != 0) == b;
		}
	};

	bool_reference final() {
		return bool_reference(degree_in_final);
	}

	// Relation d'ordre utilisée pour trouver les états équivalents:
	// pour deux états q, p, on a (q == p) <=> !(q < p) && !(p < q)
	bool operator< (const state &x) const {
		if (final() < x.final()) return true;
		if (final() == x.final())
			if (size() < x.size()) return true;
			else
				// si les 2 états ont le même nombre de transitions, on utilise
				// la comparaison lexicographique suivante basée sur l'opérateur < des transitions:
				if (size() == x.size()) { 
					const_iterator i(begin()), j(end()), k(x.begin());
					while (i != j)
						if (*i < *k) return true;
						else if (*k < *i) return false;
						else { ++i; ++k; }
					return false;
				}
		return false;
	}
};

// L'objet fonction de comparaison suivant stocke une référence sur le tableau de 
// pointeurs vers les états de l'automate, il réalise l'indirection identifiant->état
template <class u>
struct compare_state 
	: public binary_function<vector<state<u>*>::size_type, vector<state<u>*>::size_type, bool> 
{
	const vector<state<u>*> &Q;
	compare_state(const vector<state<u>*> &r)
		: Q(r)
	{ }
	result_type operator() (first_argument_type x, second_argument_type y) const {
		return *Q[x] < *Q[y];
	}
};


template <class letag = empty_tag,class TransitionAllocator= astl_allocator<transition>, class StateAllocator=astl_allocator<state<letag> > >
class DFA_min_hash : public DFA_concept
{
public:
	typedef ASCII                                      Sigma;
	typedef vector<typename StateAllocator::pointer>::size_type State;
	typedef char                                       Alphabet;
        typedef DFA_min_hash                                self;
        typedef letag                                         Tag;
      //typedef empty_tag                                   Tag;

	State null_state;

protected:
	TransitionAllocator t_alloc;
	StateAllocator      s_alloc;
	State i;
	bool ready;  // l'automate a-t-il été préparé ?
	unsigned long _state_count, _trans_count;

	typedef set<State, compare_state<Tag> > container;
	vector<container*> _pool;  // chaque hauteur a son set
	vector<typename StateAllocator::pointer>     Q;
	compare_state<Tag> cmp_state;
	State hole;  // indice du premier trou libre dans le vecteur d'état
	unsigned long wc; // word count

	container& pool(unsigned long h) { 
		for(; _pool.size() < h + 1; _pool.push_back(new container(cmp_state))); 
		return *(_pool[h]);
	}

	void prepare();

	state<Tag>::bool_reference final(State q) {
		return Q[q]->final();
	}

	void initial(State q) {
		i = q;
	}

	State new_state(const typename StateAllocator::value_type &s = typename StateAllocator::value_type()) {
		++_state_count;
		while (hole < Q.size())
			if (Q[hole] == NULL) {
				Q[hole] = s_alloc.allocate(1);
				s_alloc.construct(Q[hole], s);
				return hole++;
			}
			else ++hole;
		Q.push_back(s_alloc.allocate(1));
		s_alloc.construct(Q.back(), s);
		++hole;
		return Q.size() - 1;
	}

	void del_state(State q) {
		--_state_count;
		_trans_count -= Q[q]->size();
		state<Tag>::iterator i = Q[q]->begin(), j = Q[q]->end();
		for(; i != j; ++i)
			Q[(*i).aim()]->dec_degree_in();
		s_alloc.destroy(Q[q]);
		s_alloc.deallocate(Q[q], 1);
		Q[q] = NULL;
		hole = min(hole, q);
	}

	void set_trans(State q, Alphabet a, State p) {
		++_trans_count;
		Q[q]->insert(transition(a, p));
		Q[p]->inc_degree_in();
	}

	State duplicate_state(State q) {
		_trans_count += Q[q]->size();
		State p = new_state(*Q[q]);
		state<Tag>::iterator i = Q[p]->begin(), j = Q[p]->end();
		for(; i != j; ++i)
			Q[(*i).aim()]->inc_degree_in();
		return p;
	}
	
	void del_trans(State q, Alphabet a) {
		--_trans_count;
		Q[Q[q]->delta1(a)]->dec_degree_in();
		Q[q]->erase(transition(a));
	}

	void change_trans(State q, Alphabet a, State p) {
		Q[Q[q]->delta1(a)]->dec_degree_in();
		Q[q]->change_trans(transition(a,p));
		Q[p]->inc_degree_in();
	}

public: // TMP
	void height(State q, unsigned long h) {
		Q[q]->height(h);
	}

	unsigned long height(State q) const {
		return Q[q]->height();
	}

	unsigned long degree_in(State q) const {
		return Q[q]->degree_in();
	}

	void degree_in(State q, unsigned long d) {
		Q[q]->degree_in(d);
	}

	template <class InputIterator>
	bool _insert(InputIterator first, InputIterator last);
	
public:
	typedef skip_blanks_iterator<state<Tag> > const_iterator;

	DFA_min_hash()
		: null_state(0), i(0),  ready(false),
			_state_count(0), _trans_count(0), Q(1, (state<Tag>*) 0), cmp_state(Q), 
			hole(2), wc(0)
	{ 
		i = new_state();
	}

	const StateAllocator& state_allocator() const {
		return s_alloc;
	}

	const_iterator begin() const {
		return const_iterator(&Q, initial());
	}

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

	~DFA_min_hash() {
		freeze();
		vector<typename StateAllocator::pointer>::iterator i = Q.begin(), j = Q.end();
		for(; i != j; ++i)
			if (*i != NULL) {
				s_alloc.destroy(*i);
				s_alloc.deallocate(*i, 1);
			}
	}

	bool final(State q) const {
		return Q[q]->final();
	}
	
	void freeze() {  // on n'a plus l'intention d'ajouter de mot. On se débarasse de la structure de donnée
		for(vector<container*>::iterator i = _pool.begin(); i != _pool.end(); ++i)
			delete *i;
		_pool.clear();
		ready = false;
	}

	template <class InputIterator>
	bool insert(InputIterator first, InputIterator last) {
		if (_insert(first, last)) {
			++wc;
			return true;
		}
		return false;
	}
	
	bool insert(const char *s) {
		return insert(s, s + strlen(s));
	}

	bool insert(const string &s) {
		return insert(s.begin(), s.end());
	}
	
	State initial() const {
		return i;
	}

	State delta1(State q, Alphabet a) const {
		return Q[q]->delta1(a);
	}

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

        template <class Tag>
	class Edges_t
	{
	protected:
		state<Tag> *q;

	public:
		Edges_t(state<Tag> *p)
			: q(p)
		{ }

		Edges_t()
		{}

		bool empty() const {
			return q->size() == 0;
		}

		unsigned int size() const {
			return q->size();
		}

		class const_iterator : public bidirectional_iterator<pair<Alphabet, State>, ptrdiff_t>
		{
		protected:
			state<Tag>::const_iterator i;

		public:
			typedef const_iterator self;

			const_iterator()
			{ }
			const_iterator(state<Tag>::const_iterator j)
				: i(j)
			{ }
			pair<Alphabet, State> operator* () const {
				return make_pair((*i).letter(), (*i).aim());
			}
			self& operator++ () {
				++i;
				return *this;
			}
			self operator++ (int) {
				self tmp = *this;
				++*this;
				return tmp;
			}
			bool operator== (const self &x) const {
				return i == x.i;
			}
			self& operator--() {
				--i;
				return *this;
			}
			self operator-- (int) {
				self tmp = *this;
				--*this;
				return tmp;
			}
		};
		
		const_iterator begin() const {
			return const_iterator(q->begin());
		}

		const_iterator end() const {
			return const_iterator(q->end());
		}

		const_iterator find(Alphabet a) const {
			return const_iterator(q->find(a));
		}
	};
        typedef Edges_t<Tag> Edges;
	Edges delta2(State q) const {
		return Edges(Q[q]);
	}

	unsigned long state_count() const {
		return _state_count;
	}

	unsigned long trans_count() const {
		return _trans_count;
	}

	unsigned long size() const {
		return wc;
	}
};

template <class Tag,class TAllocator, class SAllocator>
void DFA_min_hash<Tag, TAllocator, SAllocator>::prepare() {
	const_iterator first = begin(), last = end();
	for(; first != last; ++first)
		pool(height(*first)).insert(*first);
	ready = true;
}

template <class Tag,class TAllocator, class SAllocator> template <class InputIterator>
bool DFA_min_hash<Tag,TAllocator, SAllocator>::_insert(InputIterator first, InputIterator last)
{
	if (is_in(first, last, plainc(*this))) return false;  // mot déjà présent ?
	if (!ready) prepare();  // construit la structure de donnée si nécessaire
	//stack_cursor<forward_cursor_trace<forward_cursor<self> > > c( tracec(forwardc(*this)));
	stack_cursor<forward_cursor<self> > c( forwardc (*this));
	bool duplicating;
// cerr  << "// Descente" << endl;
	for(duplicating = false; first != last; ++first) {

		if (!duplicating)
			pool(height(c.src())).erase(c.src());
// cerr  << "erase(" << c.src() << ") de hauteur " << height(c.src()) << endl;

		if (!c.find(*first)) {
		  State uu;
// cerr  << "Création d'une transition par '" << (char) *first << "' vers un nouvel état" ;
			set_trans(c.src(), *first, uu= new_state());  // transition non définie => création
			duplicating = true;
			// cerr  << uu<< endl ;
			c.first_transition();
		}
		else 
			if (Q[c.aim()]->degree_in() > 1) {
// cerr  << "But " << c.aim() << " de degré " << Q[c.aim()]->degree_in() << ", duplication et redirection de la transition par '" << (char) *first << "'" << endl;
				change_trans(c.src(), *first, duplicate_state(c.aim()));   // il faut dupliquer l'état but
				duplicating = true;
			}

		// else  cerr  << "on suit le préfixe sur (" << c.src() << ", '" << (char) *first << "', " << c.aim() << ")" << endl;

		// cerr << c.src()<< " " ; 
		c.forward(*first);
		// cerr << c.src()<< endl ; 
	}
	if (!duplicating) 
		pool(height(c.src())).erase(c.src());
	// cerr  << "erase(" << c.src() << ") de hauteur " << height(c.src()) << endl;

         final(c.src()) = true;
 //hash
	        Q[c.src()]->tag().hash() += 1 ;
	unsigned long h = height(c.src());

	// cerr  << "// Remontée" << endl;
	for(; c.backward(); ) {
	  	        Q[c.src()]->tag().hash() += 1 ;
		// On essaie d'insérer l'état but dans l'ensemble qui correspond à sa hauteur.
		// Si un état équivalent existe, il sera renvoyé, sinon il sera inséré
		//		cerr  << "Sur la transition (" << c.src() << ", '" << (char) c.letter() << "', " << c.aim() << ")" << endl;
		pair<container::iterator, bool> i = pool(height(c.aim())).insert(c.aim());
		if (i.second == false) {  // l'état n'a pas été inséré ?
// cerr  << c.aim() << " de hauteur " << height(c.aim()) << " a pour équivalent " << *i.first << endl;
			State tmp = c.aim(); // on va rediriger la transition donc on va perdre le but
			change_trans(c.src(), c.letter(), *i.first); // on redirige la transition vers l'état équivalent
			del_state(tmp);
		}
		h = max(height(c.src()), h+1); // Précondition: les états sont créés avec une hauteur initialisée à 0
		height(c.src(), h);
       // cerr  << "Hauteur de " << c.src() << " == " << height(c.src()) << "Hval = " << Q[c.src()]->tag().hash() <<  endl;
	}
	pool(height(initial())).insert(initial());
	return true;
}


 


#endif // ASTL_CLASS_DFA_MIN_HASH