/*
 * 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_HASH_CURSOR
#define ASTL_CLASS_HASH_CURSOR

// Defines:
// template hash_cursor

// A hash_cursor computes a hash value along its path (D. Revuz PhD. Thesis)
// Underlying DFA has to be prepared beforehand

// Instanciation parameters:
// 1. DFA class type
//
// Requirements: 
// 1. DFA::Tag is an integer type
// Ifdef DR
// 1. DFA::Tag::hash() is an integer 
// 
// Constructors:
// Same as default forward_cursor (cursor.h)

#ifdef DR
template <class DFA>
class hash_cursor : public forward_cursor<DFA>
{
protected:
  int hash_value;

public:
  typedef hash_cursor         self;
  typedef forward_cursor<DFA> super;

  hash_cursor(const DFA &a, unsigned int p, unsigned int letter) 
    : super(a, p, letter), hash_value(0)
  { }
  
  hash_cursor(const DFA &a, unsigned int p, edges_iterator t)
    : super(a, p, t), hash_value(0)
  { }
  
  hash_cursor(const DFA &a, unsigned int p)
    : super(a, p), hash_value(0)
  { }

  hash_cursor(const DFA &a)
    : super(a), hash_value(0)
  { }

  bool operator == (const self &x) const {
    return (q == x.q && transition == x.transition);
  }

  void forward() {
    for(edges_iterator tmp = dfa->delta2(q).begin(); tmp != transition; ++tmp)
      hash_value += dfa->tag((*tmp).second).hash();
    q = (*tmp).second;
  }
    
  bool forward(unsigned int letter) {
    int tmp_hash_value = 0;
    edges_iterator tmp;
    for(tmp = dfa->delta2(q).begin(); 
	tmp != dfa->delta2(q).end() && (*tmp).first != letter; ++tmp)
      tmp_hash_value += dfa->tag((*tmp).second).hash();

    // letter not found ?
    if (tmp == dfa->delta2(q).end())
      return false;

    hash_value += tmp_hash_value;
    q = (*tmp).second;
    return true;
  }

  int hash() const {
    return hash_value;
  }
};

#else 
template <class DFA>
class hash_cursor : public forward_cursor<DFA>
{
protected:
  int hash_value;

public:
  typedef hash_cursor         self;
  typedef forward_cursor<DFA> super;

  hash_cursor(const DFA &a, unsigned int p, unsigned int letter) 
    : super(a, p, letter), hash_value(0)
  { }
  
  hash_cursor(const DFA &a, unsigned int p, edges_iterator t)
    : super(a, p, t), hash_value(0)
  { }
  
  hash_cursor(const DFA &a, unsigned int p)
    : super(a, p), hash_value(0)
  { }

  hash_cursor(const DFA &a)
    : super(a), hash_value(0)
  { }

  bool operator == (const self &x) const {
    return (q == x.q && transition == x.transition);
  }

  void forward() {
    for(edges_iterator tmp = dfa->delta2(q).begin(); tmp != transition; ++tmp)
      hash_value += dfa->tag((*tmp).second);
    q = (*tmp).second;
  }
    
  bool forward(unsigned int letter) {
    int tmp_hash_value = 0;
    edges_iterator tmp;
    for(tmp = dfa->delta2(q).begin(); 
	tmp != dfa->delta2(q).end() && (*tmp).first != letter; ++tmp)
      tmp_hash_value += dfa->tag((*tmp).second);

    // letter not found ?
    if (tmp == dfa->delta2(q).end())
      return false;

    hash_value += tmp_hash_value;
    q = (*tmp).second;
    return true;
  }

  int hash() const {
    return hash_value;
  }
};
#endif //DR
#endif // ASTL_HASH_CURSOR