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

// UNDER CONSTRUCTION !!!!!!
// USE AT YOUR OWN RISKS !!!!!

#ifndef ASTL_REGEXP_CURSOR
#define ASTL_REGEXP_CURSOR

#include <vector>
#include <iostream>

struct node;

#include <set>
typedef set<node*> S;

struct node {
  char token;
  bool annulable;
  S premiere_pos, derniere_pos, pos_suivante;

  node(char t)
    : token(t), annulable(false)
  { }

  bool final() const {
    return token == '#';
  }
};

ostream& operator<< (ostream &out, const node &x) 
{
  out << "Node " << &x << " ";
  switch (x.token) {
  case '|' : out << "OU    "; break;
  case ' ' : out << "CONCAT"; break;
  case '*' : out << "ETOILE"; break;
  default :  out << "'" << x.token << "'"; break;
  }
  out << " " << (x.annulable ? "" : "non ") << "annulable" << endl;
  out << "Premières positions (" << x.premiere_pos.size() << "): ";
  copy(x.premiere_pos.begin(), x.premiere_pos.end(), ostream_iterator<node*>(out, " "));
  out << endl << "Dernières positions (" << x.derniere_pos.size() << "): ";
  copy(x.derniere_pos.begin(), x.derniere_pos.end(), ostream_iterator<node*>(out, " "));
  out << endl << "Positions suivantes (" << x.pos_suivante.size() << "): ";
  copy(x.pos_suivante.begin(), x.pos_suivante.end(), ostream_iterator<node*>(out, " "));
  out << endl;
  return out;
}

class regexp_cursor
{
protected:
  S q;

public:
  typedef regexp_cursor self;
  typedef S State;
	typedef char Alphabet;

  node* parse(char const *&first, const char *last, node *left) {
    node *right, *here;

    switch (*first) {
    case '|' : 
      right = parse(++first, last, NULL);
      here = new node('|');
      here->annulable = right->annulable || left->annulable;

      // premiere_pos(here) = premiere_pos(left) U premiere_pos(right):
      here->premiere_pos.insert(left->premiere_pos.begin(), left->premiere_pos.end());
      here->premiere_pos.insert(right->premiere_pos.begin(), right->premiere_pos.end());
      here->derniere_pos.insert(left->derniere_pos.begin(), left->derniere_pos.end());
      here->derniere_pos.insert(right->derniere_pos.begin(), right->derniere_pos.end());
#ifdef EBUG
      cerr << *here << endl;
#endif
      return here;

    case '*' :
      here = new node('*');
      here->annulable = true;
      here->premiere_pos = left->premiere_pos;
      here->derniere_pos = left->derniere_pos;

      // pos_suivante(derniere_pos(here)) += premiere_pos(here):
      for(S::const_iterator i = here->derniere_pos.begin(); i != here->derniere_pos.end(); ++i)
				(*i)->pos_suivante.insert(here->premiere_pos.begin(), here->premiere_pos.end());
#ifdef EBUG
      cerr << *here << endl;
#endif
      return here;

    case ' ' :
      right = parse(++first, last, NULL);
      here = new node(' ');
      here->annulable = left->annulable && right->annulable;
      if (left->annulable) {
				here->premiere_pos.insert(left->premiere_pos.begin(), left->premiere_pos.end());
				here->premiere_pos.insert(right->premiere_pos.begin(), right->premiere_pos.end());
      }
      else
				here->premiere_pos = left->premiere_pos;

      if (right->annulable) {
				here->derniere_pos.insert(right->derniere_pos.begin(), right->derniere_pos.end());
				here->derniere_pos.insert(left->derniere_pos.begin(), left->derniere_pos.end());
      }
      else
				here->derniere_pos = right->derniere_pos;
      
      // pos_suivante(derniere_pos(left)) += premiere_pos(right):
      for(S::const_iterator i = left->derniere_pos.begin(); i != left->derniere_pos.end(); ++i)
				(*i)->pos_suivante.insert(right->premiere_pos.begin(), right->premiere_pos.end());

#ifdef EBUG
      cerr << *here << endl;
#endif
      return here;
      
    default :
      here = new node(*first);
      here->annulable = false;
      here->premiere_pos.insert(here);
      here->derniere_pos.insert(here);
#ifdef EBUG
      cerr << *here << endl;
#endif
      return here;
    }
  }
      
  regexp_cursor(const char *expression)
  {
    const char *first = expression, *last = expression + strlen(expression);
    node *root;
    for(root = NULL; first != last; ++first)
      root = parse(first, last, root);
    q = root->premiere_pos;
  }

	self& operator=(const State &s) {
		q = s;
		return *this;
	}
  
  State src() const {
    return q;
  }

  bool forward(unsigned int letter) {
#ifdef EBUG
    cerr << "forward('" << (char) letter << "')";
#endif
    State p;
    for(S::const_iterator i = q.begin(); i != q.end(); ++i)
      if ((*i)->token == (char) letter || (*i)->token == '.' )
				p.insert((*i)->pos_suivante.begin(), (*i)->pos_suivante.end());
    q = p;
    return !q.empty();
  }
    
  bool src_final() const {
    for(S::const_iterator i = q.begin(); i != q.end(); ++i)
      if ((*i)->final()) return true;
    return false;
  }
     
  bool sink() const {
    return q.empty();
  }
  //  Tag tag() const;
};

#endif // ASTL_REGEXP_CURSOR