/*
 * 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:		    aho_corasick.h
//  Version:    ASTL 1.1
//	Copyright:	Vincent LE MAOUT
//	Date:		    Wed Dec 2 15:50:07 MET 1998
//	Descrition:	Defines class DFA_aho_corasick (DFA adapter).
//              DFA_aho_corasick is a DFA_default with following methods:
//              void build();  // builds data structure for matching
//                             // the trie must be created by the user before calling this function
//              template <class InputIterator>
//              Tag next_match(InputIterator &start, InputIterator &finish);
//                             // returns the accepting state tag
//                             // if no matches are found, returns Tag()
//              void reset(State q = initial());  // set the current state to q
//


#ifndef ASTL_CLASS_DFA_AHO_CORASICK
#define ASTL_CLASS_DFA_AHO_CORASICK


#include <astl.h> 
#include <queue>
#include <set>
#include <dfa_compact.h>

template <class DFA>
class DFA_aho_corasick : public DFA_concept
{
private:
  DFA dfa;
  typename DFA::Tag default_contructed_tag;

public:
  typedef typename DFA::Sigma          Sigma;
  typedef typename DFA::Alphabet       Alphabet;
  typedef typename DFA::State          State;
  typedef typename DFA::Tag            Tag;
  typedef typename DFA::Edges          Edges;
  typedef typename DFA::const_iterator const_iterator;
  
  State&   null_state;
  Alphabet default_letter;   

private:
  State current_state;

public:
  DFA_aho_corasick(const Alphabet &def_letter, unsigned long n = 0)
    : dfa(n), default_contructed_tag(),
      null_state(dfa.null_state), default_letter(def_letter)
    { }

  ~DFA_aho_corasick()
    { }

  State new_state() {
    return (dfa.new_state());
  }

  template <class OutputIterator>
  OutputIterator new_state(unsigned long how_many, OutputIterator x) {
    return (dfa.new_state(how_many, x));
  }

  void del_state(State s) {
    dfa.del_state(s);
  }

  void set_trans(State from, const Alphabet &a, State to) {
    dfa.set_trans(from, a, to);
  }

  void del_trans(State s, const Alphabet &a) {
    dfa.del_trans(s, a);
  }

  void change_trans(State s, const Alphabet &a, State new_aim) {
    dfa.change_trans(s, a, new_aim);
  }

  void copy_state(State from, State to) {
    dfa.copy_state(from, to);
  }

  State duplicate_state(State s) {
    return (dfa.duplicate_state(s));
  }

  Tag&           tag(State s) {
    return (dfa.tag(s));
  }

  const Tag& tag(State s) const {
    return (dfa.tag(s));
  }

  State delta1(State s, const Alphabet &a) const {
    State aim;
    return (((aim = dfa.delta1(s, a)) == null_state) ? 
	    dfa.delta1(s, default_letter) : aim);
  }

  // No use of default transitions:
  State delta0(State s, const Alphabet &a) const {
    return (dfa.delta1(s, a));
  }

  Edges delta2(State s) const {
    return (dfa.delta2(s));
  }

  State initial() const {
    return (dfa.initial());
  }
  
  void initial(State s) {
    dfa.initial(s);
  }

  unsigned long  state_count() const {
    return (dfa.state_count());
  }

  unsigned long  trans_count() const {
    return (dfa.trans_count());
  }

  const_iterator begin() const {
    return (dfa.begin());
  }

  const_iterator end() const {
    return (dfa.end());
  }

  // Encapsulating DFA::bool_reference for final() return value
  class bool_reference
  {
    DFA &dfa;
    State s;

  public:
    bool_reference(DFA &_dfa, State q)
      : dfa(_dfa), s(q)
      { }
    
    operator bool() const {
      return (dfa.final(s));
    }

    template <class T>
    bool_reference operator = (T t) {
      dfa.final(s) = t;
      return (*this);
    }

    template <class T>
    bool operator == (T t) const { 
      return (dfa.final(s) == t);
    }
  };
		   
  class const_bool_reference
  {
    const DFA &dfa;
    State s;

  public:
    const_bool_reference(const DFA &_dfa, State q)
      : dfa(_dfa), s(q)
      { }
    
    operator bool() const {
      return (dfa.final(s));
    }

    template <class T>       // ok if T is castable to bool
    bool operator == (T t) const { 
      return (dfa.final(s) == t);
    }
  };

  const_bool_reference final(State s) const {
    return (const_bool_reference(dfa, s));
  }
	
  bool_reference final(State s) {
    return (bool_reference(dfa, s));
  }
	
  void build()
    {
      Edges edges; 
      typename Edges::const_iterator trans, trans_end;
		
      // Initialize subsitutes to null_state for i and to i for others
      const_iterator start, finish;
      for(start = begin(), finish = end(); start != finish; ++start)
	if (*start != initial())
	  set_trans(*start, default_letter, initial());
	else
	  set_trans(*start, default_letter, null_state);
			
      // Queue-in the initial state transitions aims:
      State p_aim, p, q;
      queue<State> path;
      set<State> visited;
      edges = delta2(initial());
      for(trans = edges.begin(), trans_end = edges.end(); trans != trans_end; ++trans)
	if ((*trans).first != default_letter)
	  path.push((*trans).second);
				
      for(; !path.empty();)
	{
	  q = path.front();
	  path.pop();
	  edges = delta2(q);
	  for(trans = edges.begin(), trans_end = edges.end(); trans != trans_end; ++trans)
	    {
	      if ((*trans).first != default_letter)
		{
		  for(p = delta0(q, default_letter);  // p is q's subsitute
		      (p_aim = delta0(p, (*trans).first)) == null_state && p != initial();
		      p = delta0(p, default_letter));

		  if (p_aim != null_state)
		    {
		      change_trans((*trans).second, default_letter, p_aim);
		      if (final(p_aim))
			{
			  final((*trans).second) = true;
			  if (tag(p_aim) > tag((*trans).second))
			    tag((*trans).second) = tag(p_aim);  
			}
		    }
		  else
		    change_trans((*trans).second, default_letter, initial());

		  if (visited.find((*trans).second) == visited.end())   // not already visited ?
		    {
		      path.push((*trans).second);
		      visited.insert((*trans).second);
		    }
		}
	    }
	}
      reset();
    }
	
  State ac_delta1(State p, const Alphabet &a)
    {
      State q, tmp = p;
      while(1)
	{
	  q = delta0(p, a);
	  if (q != null_state)
	    {
	      if (tmp != p)
		set_trans(tmp, a, q);      // lazy optimization
	      return (q);
	    }
	  if (p == initial())
	    {
	      set_trans(tmp, a, p);        // lazy optimization
	      return (p);
	    }
	  p = delta0(p, default_letter);
	}
    }

  template <class InputIterator>
  Tag next_match(InputIterator &start, InputIterator &finish)
    {
      while(start != finish)
	{
	  current_state = ac_delta1(current_state, *start);
	  ++start; // ++start; aho-corasick hacking: read one char out of two
	  if (final(current_state)) return (tag(current_state));
	}
      return (default_contructed_tag);
    }

  void reset(State q) {
    current_state = q;
  }

  void reset() {
    current_state = initial();
  }
};  

template <class DFA>
class DFA_aho_corasick_compact : public DFA_compact<DFA>
{
private:
  typedef DFA_compact<DFA> super;
  State current_state;
  Alphabet default_letter;
  Tag default_constructed;

public:
  DFA_aho_corasick_compact(istream &in, const Alphabet &def_letter)
    : super(in), default_letter(def_letter), default_constructed()
    { }

  DFA_aho_corasick_compact(const Alphabet &def_letter)
    : default_letter(def_letter)
    { }

  // Delta1 const method: no lazy optimization
  State ac_delta1(State p, const Alphabet &a) const
    {
      State q;
      for(q = delta1(p, a); q == null_state && p != initial(); p = delta1(p, default_letter), q = delta1(p, a));
      return (q == null_state ? initial() : q);
    }

  template <class InputIterator>
  Tag next_match(InputIterator &start, InputIterator &finish)
    {
      while(start != finish)
	{
	  current_state = ac_delta1(current_state, *start);
	  ++start; 
	  //// TEMPORAIRE:
	  ////++start;
	  if (final(current_state)) 
	    return (tag(current_state));
	}
      return (default_constructed);
    }

  void reset(State q) {
    current_state = q;
  }

  void reset() {
    current_state = initial();
  }
};  

#endif // ASTL_CLASS_DFA_DEFAULT