/*
 * 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_NEIGHBOR_CURSOR
#define ASTL_NEIGHBOR_CURSOR

#include <list>
#include <stack>
#include <cursor.h>
#include <iostream>

// Defines:
// neighbor_cursor (stack cursor)

// A neighborood cursor hides the automaton parts straying too far from the
// specified word.

// Instanciation parameters:
// 1. ForwardCursor: a forward cursor type
//
// Requirements:
// None
//
// Constructor: 
// 1. A forward cursor, a word, a max editing distance

// TODO:
// Genericize the distance computing with an object function

// warning: do not reorder symbols:
typedef enum { SUBSTITUTION = 0,  INSERTION,  END, DELETION } edit_type;

template <class ForwardCursor>
class context
{
public:
  ForwardCursor cursor;
  int           operation;
  int           distance;
  const char   *word;
  context(const ForwardCursor &x, int d, const char *w, int op = SUBSTITUTION)
    : cursor(x), operation(op), distance(d), word(w)
  { }
	bool operator==(const context &x) const {
		return cursor == x.cursor && operation == x.operation && distance == x.distance;
	}
};

template <class ForwardCursor>
class neighbor_cursor 
  : public stack<context<ForwardCursor> >, public stack_cursor_concept
{
public:
  typedef stack<context<ForwardCursor> > super;
  typedef neighbor_cursor               self;
  typedef typename ForwardCursor::State State;
  typedef typename ForwardCursor::Tag   Tag;

public:
  neighbor_cursor(const ForwardCursor &x, const char *w, int d)
    : super() { 
    super::push(context<ForwardCursor>(x, d, w));    // default to SUBSTITUTION
  }
  
  neighbor_cursor()
    : super()
  { }

	bool sink() const {
		return false;
	}

  bool operator == (const self &x) const {
    return (super) *this == (super) x;
  }
	
  int updated_distance(const context<ForwardCursor> &x)
	{
		switch (x.operation) {
			
		case SUBSTITUTION :
			if (x.word[0] == 0) return -1;   // end of words, only INSERTION/DELETION allowed
			return x.distance - !(x.cursor.letter() == x.word[0]);
			
		case INSERTION : 
			return x.distance - 1;
			
		case DELETION : 
			return x.distance - 1;
			
		default : 
			return -1;
		}
	}
	
  bool first_transition() {
    if (top().cursor.first_transition())     // if any transition
      {
				do {
					for(top().operation = SUBSTITUTION; top().operation != END 
								&& updated_distance(top()) < 0; ++top().operation); 
					if (top().operation != END) 
						return true;
				} while (top().cursor.next_transition());
      }
		
    // No substitution or insertion possible, trying deletion
    top().operation = DELETION;
    if (updated_distance(top()) >= 0)
      {
				super::push(top());
				if (top().word[0] != 0) ++top().word;
				top().distance = updated_distance(top());
				if (first_transition())
					return true;
				else
					{
						super::pop();
						return false;
					}
      }
    return false; 
  }

  bool next_transition() {
    ++top().operation;
    do {
      // Trying substitution and insertion:
      for(; top().operation != END; ++top().operation)
				if (updated_distance(top()) >= 0) return true;
      top().operation = SUBSTITUTION;
    } while (top().cursor.next_transition());
		
    // No substitution or insertion possible, trying deletion:
    top().operation = DELETION;
    if (updated_distance(top()) >= 0)
      {
				super::push(top());
				top().distance = updated_distance(top()); 
				if (top().word[0] != 0) ++top().word;
				if (!first_transition())
					{
						super::pop();
						return false;
					}
				return true;
      }
    return false;
  }

  void forward() {
    super::push(top());
    switch (top().operation) {
    case SUBSTITUTION : 
      top().distance = updated_distance(top());
      ++top().word;
      top().cursor.forward();
      return;
    case INSERTION : 
      top().distance = updated_distance(top());
      top().cursor.forward();
      return;
    }
    // never forward when on DELETION
  }

  bool backward() {
    // one pop, then while current op is DELETION, pop
    for(super::pop(); top().operation == DELETION && !empty(); super::pop());
    return !empty();
  }

  bool find(int letter) const {
    return top().cursor.find(letter) && top().distance - !((int) letter == top().word[0]) >= 0;
  }

  bool forward(int letter) {
    if (find(letter))
      {
				super::push(top());
				top().distance -= !((int) letter == top().word[0]);
				top().cursor.forward(letter);
				if (top().word[0] != 0) ++top().word;
				return true;
      }
    top().forward(letter);
    return false;
  }
	
  bool src_final() const {
    if (top().word[0] == 0 || top().word[1] == 0)
      return top().cursor.src_final();
    return false;
  }

  bool aim_final() const {
    if (top().word[0] == 0 || top().word[1] == 0)
      return top().cursor.aim_final();
    return false;
  }

  // Return letter:
  int letter() const {
    return top().cursor.letter();
  }
};

template <class ForwardCursor>
neighbor_cursor<ForwardCursor>
neighborc(const ForwardCursor &x, const char *w, int d) {
	return neighbor_cursor<ForwardCursor>(x, w, d);
}

#endif