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


// Ajoute les informations necessaires au hachage
// necessite unsigned long& Tag::hash()
// retourne le nombre de mots dans l'automate 

#ifndef ASTL_HASH
#define ASTL_HASH

template <class DFA>
unsigned long hash(DFA &dfa)
{
  if (dfa.initial() != dfa.null_state)
    return (_hash(dfa, dfa.initial()));
  else
    return (0);
}

template <class DFA>
unsigned long _hash(DFA &dfa, typename DFA::State s)
{
  unsigned long &h = dfa.tag(s).hash();
  if (dfa.final(s)) 
    h = 1;
  else 
    h = 0;

  typename DFA::Edges e = dfa.delta2(s);
  typename DFA::Edges::const_iterator i, e_end = e.end();
  for (i = e.begin(); i != e_end; ++i)
    h += _hash(dfa, (*i).second);

  return (h);
}

//
//      File:           hash_cursor.hh
//      Copyright:      Vincent LE MAOUT
//      Date:           Thu Mar  5 14:44:05 MET 1998
//      Descrition:     object allowing moves along a hash DFA (ASTL1.10)
//

#ifndef ASTLW32_CLASS_HASHCURSOR
#define ASTLW32_CLASS_HASHCURSOR

// Precondition : unsigned long & DFA_hash::Tag::hash()


template <class DFA_h>
class hash_cursor
{
private:
  typedef typename DFA_h::State State;

  State         current_state;
  DFA_h         &dfa_hash;
  unsigned long hash_value;

public:
  hash_cursor(DFA_h &a) : dfa_hash(a), hash_value(0) { }

  bool operator == (const hash_cursor &x) {
    return (current_state == x.current_state);
  }

  bool operator != (const hash_cursor &x) {
    return (!(*this == x));
  }

  // Set the cursor on a specific state
  hash_cursor& operator = (State s)
  {
    current_state = s;
    return (*this);
  }

  hash_cursor& operator = (const hash_cursor &x)
  {
    current_state = x.current_state;
//    dfa_hash = x.dfa_hash;
    hash_value = x.hash_value;
    return (*this);
  }

  operator State() const {
    return (current_state);
  }


  // Return the current state the cursor is on
  State operator * () const
  {
    return (current_state);
  }

  // Moves one transition forward
  // Return (true) if transition exists and update hash value
  bool forward(const typename DFA_h::Alphabet &a)  
  {
    typename DFA_h::Edges e = dfa_hash.delta2(current_state);
    typename DFA_h::Edges::const_iterator trans, e_end = e.end();
    unsigned long tmp_hash_value = 0;

    for(trans = e.begin(); trans != e_end && (*trans).first != a; ++trans)
      tmp_hash_value += dfa_hash.tag((*trans).second).hash();

    if (trans == e_end)
      return (false);   // Pas de transition par cette lettre

    current_state = (*trans).second;
    if (dfa_hash.final(current_state) == true)
      ++tmp_hash_value;
      
    hash_value += tmp_hash_value;
    return (true);
  }

  // Moves last-first transitions forward
  // Precondition:InputIterator::value_type == DFA_h::Alphabet
  // Returns true if the ENTIRE range [first, last) is accepted
  template <class InputIterator>
  bool forward(InputIterator first, InputIterator last)
  {
    for(; first != last && forward(*first); ++first);
    return (first == last);
  }
  
  // Sets current hash value to 0
  void reset() {
    hash_value = 0;
  }

  // Returns current hash value
  unsigned long hash() {
    return (hash_value);
  }

};

#endif



/*
#ifndef STATDICW32_CLASS
#define STATDICW32_CLASS

#include <dfa_compact.h>
#include <iostream>
#include <errno.h>
#include <iterator>
//#include <vectorio.h>
#include <astl_tree.h>
#include <minimize.h>
#include <fstream>
#include "stat_dic_tag.h"
#include <string>

//
// Algorithm    : language_id
// Description  : output the language of a hash dfa
// Input        : a hash dfa
// Output       : result is written through OutputIterator on chars
// Precondition : bool Tag::final()
//                unsigned long& Tag::card()
// Uses         : _language_id
//

template <class DFA, class OutputIterator>
void 
_language_id(DFA &A, DFA::State s, vector<DFA::Alphabet> &w, OutputIterator out, char separator, unsigned long h)
{
  if (A.tag(s).final() == true)
  {
    copy(w.begin(), w.end(), out);
    char tmp[11];
    *out++ = ' '; 
    copy(tmp, tmp+sprintf(tmp, "%lu", h), out);
    *out++ = separator;
  }

  typename DFA::Edges edg = A.delta2(s);
  typename DFA::Edges::const_iterator s_trans, edg_end = edg.end();
  for (s_trans = edg.begin(); s_trans != edg_end; ++s_trans)
    {
      w.push_back((*s_trans).first);
      _language_id(A, (*s_trans).second, w, out, separator, 
				h + (A.tag((*s_trans).second).final() == true ? 1 : 0));
      w.pop_back();
      h += A.tag((*s_trans).second).card();
     }
}

template <class DFA, class OutputIterator>
void 
language_id(DFA &A, OutputIterator out, char separator = '\n')
{
  vector<typename DFA::Alphabet> w;
  _language_id(A, A.initial(), w, out, separator, 0UL);
}

// Description   : Static dictionary class 
//                 Adapter of class DFA
// Preconditions : unsigned long DFA::Tag::mark()
//                 void DFA::Tag::mark(unsigned long)
//                 unsigned long DFA::Tag::trans()
//                 void DFA::Tag::trans(unsigned long)
//                 bool DFA::Tag::final()
//                 void DFA::Tag::final(bool)
//                 unsigned long& DFA::Tag::card() 
//                 unsigned long DFA::Tag::card() const
template <class T, class U>
class pair_alphabet
{
public:
  struct Alphabet : public pair<T, U>
  {
    typedef Alphabet self;
    
    hash_alphabet() : pair() 
    { }
    hash_alphabet(const T &x, const U &y = U()) : pair(x, y)
    { }
    friend bool operator == (const self &x, const self &y) {
      return (x.first == y.first);
    }
    friend bool operator < (const self &x, const self &y) {
      return (x.first < y.first);
    }
  };

  static unsigned long size() {
    return (Type_alphabet<T>::size());
  }

  static unsigned long map(const Alphabet &a) {
    return (Type_alphabet<T>::map(a.first));
  }

  static unsigned long map(const T &a) {
    return (Type_alphabet<T>::map(a));
  }

  static Alphabet unmap(unsigned long i) {
    return (Alphabet(Type_alphabet<T>::unmap(i)));
  }
};

template <class _Tag = empty_tag, 
          class Allocator = default_allocator>
class DFA_hash : public DFA_bin<pair_alphabet<char, _ID>, _Tag, Allocator>
{
private:
  typedef DFA_bin<pair_alphabet<char _ID>, _Tag, Allocator> super;
  unsigned long _wc;

public:
  typedef _ID ID;
  typedef char Alphabet;

  DFA_hash(unsigned long n = 0, Allocator alloc = Allocator()) 
    : DFA_bin(n, alloc), _wc = 0
  { }

  DFA_hash(istream &in) : dfa()
  { }

  DFA_hash(const char *file_name) : dfa()
  {
    ifstream in(file_name, ios::in);
    if (!in)
    {
      perror(file_name);
      exit(1);
    }
  }

  ~DFA_hash()
  {  }
  
  unsigned long wc() const { 
    return (_wc);
  }

  ID add_single(const string &s) { 
    tree_build(this, s.begin(), s.end(), Tag());
    return (::hash(this));
  }

  template <class InputIterator>
  ID add_single(InputIterator start, InputIterator finish) { 
    tree_build(this, start, finish, Tag());
    return (::hash(this));
  }

  template <class InputIterator>
  unsigned long add_list(InputIterator first, InputIterator last) { 
    tree_build(this, first, last);
    return (::hash(this));
  }      

  unsigned long hash(const char *s) { }
  template <class InputIterator>
  unsigned long hash(InputIterator start, InputIterator finish) { }
  unsigned long hash(const string &s) { }
  ID operator [] (const string &s) { }
  ID operator [] (const char *s) { }

  









  void build(istream &in, int val_opt = 0)
  {
    if (dfam) delete dfam;
    if (dfac) delete dfac;
    dfam = new DFA();

    // Construction de l'arbre
 //   tree(*dfam, istream_iterator<vector<DFA::Alphabet> > (in), 
//			istream_iterator<vector<DFA::Alphabet> > ()); 
    tree(*dfam, istream_iterator<string> (in), 
			istream_iterator<string> ()); 

    // Minimisation
    acyclic_minimization(*dfam);

    // Calcul des valeurs de hachage
    hash(*dfam);

    // Compaction
    dfac = new compact(*dfam, val_opt);
    delete dfam;
    dfam = NULL;
  }

  void build(const char *file_name, int val_opt = 0)
  {
    ifstream in(file_name, ios::in);
    if (!in)
    {
      perror(file_name);
      exit(1);
    }
    build(in, val_opt);
  }
  
  // Retourne 0 si le mot n'existe pas
	template <class InputIterator>
  unsigned long string_to_ID(InputIterator start, InputIterator finish)
  {
    hash_cursor<compact> c(*dfac);
    
    for(c = dfac->initial(); 
				start != finish && c.forward(*start); ++start);
    if (start == finish && dfac->tag(*c).final())
      return (c.hash());
    return (0UL);
  }

  // Retourne un interval vide si i incorrect 
  pair<DFA::Alphabet *, DFA::Alphabet *> ID_to_string(unsigned long i)
  {
    compact::State s = dfac->initial();
		DFA::Alphabet* buffer_ptr = buffer.begin();
	  DFA_compact<DFA, tag_map>::Edges e; 
    DFA_compact<DFA, tag_map>::Edges::const_iterator trans;
    unsigned long h = 0UL;

    if (i > dfac->tag(s).card() || i < 1)
			return (make_pair(buffer.begin(), buffer.begin()));

    for(;;)
    {
      if (dfac->tag(s).final() == true)
				++h;
      if (h == i)           // Ok, mot trouve
				return (make_pair(buffer.begin(), buffer_ptr));
      e = dfac->delta2(s);
      for (trans = e.begin(); ; ++trans)
      {
				h += dfac->tag((*trans).second).card();
				if (h >= i) break;
      }
      s = (*trans).second;
      *buffer_ptr++ = (*trans).first;
      h -= dfac->tag(s).card();
    }
  }

  // Ecriture binaire sur flux
  void write(ostream &out)
  {
    dfac->write(out);
  }

  // Lecture binaire sur flux
  void read(istream &in)
  {
    if (dfac)
      delete dfac;
    dfac = new compact(in);
  }
    
  void stats(ostream &out = cout) const
  {
    dfac->stats(out);
  }
  
  unsigned long wc() const
  {
    return (dfac->tag(dfac->initial()).card());
  }
}; 

#endif




*/

  
#endif