/*
 * 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_SET_OPERATION_CURSORS
#define ASTL_SET_OPERATION_CURSORS

// Defines:
// template union_cursor (forward cursor adapter)
// template intersection_cursor (forward cursor adapter)
// template diff_cursor (forward cursor adapter)
// template sym_diff_cursor (forward cursor adapter) (not tested)
// template concatenation_cursor (forward cursor adapter) (not tested)
// template not_cursor (forward cursor adapter) (not tested)

// These adapters are binary adapters: they adapt two forward cursors

// Instanciation parameters:
// 1. ForwardCursor1: left cursor type which is a model of forward cursor
// 2. ForwardCursor2: right cursor type which is a model of forward cursor
// 3. CharTraits:     a type which is a model of Char Traits for integers (must
//                    define static bool CharTraits::lt(int, int))
//
// Requirements: 
// 1. Outgoing transitions must be sorted in increasing order
//
// Constructors:
// 1. Two forward cursors

#include <list>
#include <vector>
#include <utility>  // pair<>
#include <cursor.h> // cursor concepts
#include <string>   // char_traits
#include <functional>
#include <iostream>
#include <algorithm>

#ifdef _WIN32
#define min _MIN
#endif

template <class Alphabet1, class Alphabet2>
struct default_lower_than : public binary_function<Alphabet1, Alphabet2, bool>
{
  bool operator() (const Alphabet1 &x, const Alphabet2 &y) const {
    return x < y;
  }
};

#ifdef _WIN32
template <class ForwardCursor1, class ForwardCursor2, 
  class LowerThan = default_lower_than<ForwardCursor1::Alphabet,
  ForwardCursor2::Alphabet> >
#else
template <class ForwardCursor1, class ForwardCursor2, 
  class LowerThan = default_lower_than<typename ForwardCursor1::Alphabet,
  typename ForwardCursor2::Alphabet> >
#endif
class union_cursor : public forward_cursor_concept
{
protected:
  ForwardCursor1 x1;
  ForwardCursor2 x2;
  bool x1_at_end, x2_at_end;

public:
  typedef union_cursor self;

  typedef pair<typename ForwardCursor1::State, typename ForwardCursor2::State> State;
  typedef pair<typename ForwardCursor1::Tag, typename ForwardCursor2::Tag> Tag;
  typedef typename ForwardCursor1::Alphabet Alphabet;

  union_cursor(const ForwardCursor1 &x1, const ForwardCursor2 &x2)
    : x1(x1), x2(x2)
  { }

  bool operator== (const self &x) const {
    return x1 == x.x1 && x2 == x.x2;
  }

  void forward() {
    if (x1_at_end) {
      x1 = x1.sink_state();
      x2.forward();  // case (0, q2)
      return;
    }
    if (x2_at_end) {
      x2 = x2.sink_state();
      x1.forward();  // case (q1, 0)
      return;
    }
    // case (q1, q2)
    if (LowerThan()(x1.letter(), x2.letter())) {  // x1.letter() < x2.letter()
      x2 = x2.sink_state();
      x1.forward(); 
      return;
    }
    if (LowerThan()(x2.letter(),x1.letter())) {   // x2.letter() < x1.letter()
      x1 = x1.sink_state();
      x2.forward();
      return;
    }
    // x1.letter() == x2.letter()
    x1.forward();
    x2.forward();
  }

  bool first_transition() {
    x1_at_end = x1.sink() || !x1.first_transition();
    x2_at_end = x2.sink() || !x2.first_transition();
    return !(x1_at_end && x2_at_end);
  }

  bool next_transition() {
    if (x1_at_end) {
      x2_at_end = !x2.next_transition();   // (0, q2)
      return !x2_at_end;
    }
    if (x2_at_end) {
      x1_at_end = !x1.next_transition();   // (q1, 0)
      return !x1_at_end;
    }
    // case (q1, q2)
    if (LowerThan()(x1.letter(), x2.letter())) {         // x1.letter() < x2.letter()
      x1_at_end = !x1.next_transition();
      return true;
    }
    if (LowerThan()(x2.letter(), x1.letter())) {              // x2.letter() < x1.letter()
      x2_at_end = !x2.next_transition();
      return true;
    } 
    // x2.letter() == x1.letter()
    x1_at_end = !x1.next_transition();              
    x2_at_end = !x2.next_transition();
    return !(x1_at_end && x2_at_end);
  }

  Alphabet letter() const {
    return x1_at_end ? x2.letter() : x2_at_end ? x1.letter() : min(x1.letter(), x2.letter(), LowerThan());
  }

  bool find(const Alphabet &a) {
    x1_at_end = x1.sink() || !x1.find(a);
    x2_at_end = x2.sink() || !x2.find(a);
    return !(x1_at_end && x2_at_end);
  }

  bool forward(const Alphabet &a) {
    if (!x1.sink()) x1.forward(a);
    if (!x2.sink()) x2.forward(a);
    return !sink();
  }

  State src() const {
    return State(x1.src(), x2.src());
  }

  State aim() const {
    if (x1_at_end)
      return State(x1.sink_state(), x2.aim());
    if (x2_at_end)
      return State(x1.aim(), x2.sink_state());
    if (LowerThan()(x2.letter(), x1.letter()))
      return State(x1.sink_state(), x2.aim());
    if (LowerThan()(x1.letter(), x2.letter())) 
      return State(x1.aim(), x2.sink_state());
    return State(x1.aim(), x2.aim());
  }

  bool src_final() const {
    return (!x1.sink() && x1.src_final()) || (!x2.sink() && x2.src_final());
  }

  bool aim_final() const {
    if (x1_at_end) return x2.aim_final();
    if (x2_at_end) return x1.aim_final();
    if (LowerThan()(x1.letter(), x2.letter()))
      return x1.aim_final();
    if (LowerThan()(x2.letter(), x1.letter()))
      return x2.aim_final();
    return x1.aim_final() || x2.aim_final();
  }

  bool sink() const {
    return x1.sink() && x2.sink();
  }

  void to_sink() {
    x1.to_sink();
    x2.to_sink();
  }

  bool exists(const Alphabet &a) const {
    if (x1.sink()) return x2.exists(a);
    return x1.exists(a) || (!x2.sink() && x2.exists(a));
  }

  const Tag& src_tag() const {
    return Tag(x1.sink() ? x2.src_tag() : x1.src_tag(), 
	       x2.sink() ? x1.src_tag() : x2.src_tag());
  }

  self& operator= (const State &x) {
    x1 = x.first;
    x2 = x.second;
    x1_at_end = x2_at_end = true;
    return *this;
  }

  // Not a standard requirement, do not use in algorithms (needed by wgrep):
  ForwardCursor1& first() {
    return x1;
  }
  ForwardCursor2& second() {
    return x2;
  }
  void reset() {
    x1_dead = x1.sink();
    x2_dead = x2.sink();
  }
};

/*
template <class ForwardCursor1, class ForwardCursor2, class LowerThan>
ostream& operator<< (ostream &out, 
		     const State_<ForwardCursor1, ForwardCursor2, LowerThan> &q)
{
  switch (q.c) {
  case 0 : return out << "<0,0>";
  case 1 : return out << "<" << q.q1 << ",0>";
  case 2 : return out << "<0," << q.q2 << ">";
  default : return out << "<" << q.q1 << "," << q.q2 << ">";
  }
}
*/

template <class ForwardCursor1, class ForwardCursor2, 
  class LowerThan = default_lower_than<typename ForwardCursor1::Alphabet,
  typename ForwardCursor2::Alphabet> >
class intersection_cursor 
  : public pair<ForwardCursor1, ForwardCursor2>, public forward_cursor_concept
{
public:
  typedef pair<ForwardCursor1, ForwardCursor2> super;
  typedef intersection_cursor                  self;
  typedef pair<typename ForwardCursor1::State, typename ForwardCursor2::State> State;
  typedef pair<typename ForwardCursor1::Tag, typename ForwardCursor2::Tag> Tag;
  typedef typename ForwardCursor1::Alphabet Alphabet;

  intersection_cursor(const ForwardCursor1 &x1, const ForwardCursor2 &x2)
    : super(x1, x2)
  { }

  bool sink() const {
    return first.sink() || second.sink();
  }

  State sink_state() const {
    return State(first.sink_state(), second.sink_state());
  }

  State src() const {
    return State(first.src(), second.src());
  }

  State aim() const {
    return State(first.aim(), second.aim());
  }

  self& operator= (const State &p) {
    first = p.first;
    second = p.second;
    return *this;
  }

  void forward() {
    first.forward();
    second.forward();
  }

  bool first_transition() {
    if (first.first_transition() && second.first_transition())
      while(1) 
	if (LowerThan()(first.letter(), second.letter())) {
	  if (!first.next_transition()) return false;
	}
	else
	  if (LowerThan()(second.letter(), first.letter())) {
	    if (!second.next_transition()) return false;
	  }
	  else    //  *first == *second 
	    return true;
    return false;
  }

  bool next_transition() {
    if (first.next_transition() && second.next_transition())
      while(1) 
	if (LowerThan()(first.letter(), second.letter())) {
	  if (!first.next_transition()) return false;
	}
	else
	  if (LowerThan()(second.letter(), first.letter())) {
	    if (!second.next_transition()) return false;
	  }
	  else    //  *first == *second 
	    return true;
    return false;
  }

  Alphabet letter() const {
    return first.letter();
  }

  bool find(const Alphabet &a) {
    return first.find(a) && second.find(a);
  }

  bool forward(const Alphabet &a) {
    return first.forward(a) && second.forward(a);
  }

  bool src_final() const {
    return first.src_final() && second.src_final();
  }

  bool aim_final() const {
    return first.aim_final() && second.aim_final();
  }

  bool exists(const Alphabet &a) const {
    return first.exists(a) && second.exists(a);
  }

  const Tag& src_tag() const {
    return Tag(first.src_tag(), second.src_tag());
  }
};
  
template <class ForwardCursor1, class ForwardCursor2>
class diff_cursor : public forward_cursor_concept
{
protected:
  ForwardCursor1         x1;
  mutable ForwardCursor2 x2;  // mutable because methods *_final() are const 

public:
  typedef pair<typename ForwardCursor1::State, typename ForwardCursor2::State>  State;
  typedef typename ForwardCursor1::Alphabet Alphabet;
  typedef typename ForwardCursor1::Tag      Tag;

  diff_cursor(const ForwardCursor1 &x1, const ForwardCursor2 &x2)
    : x1(x1), x2(x2)
  { }
  
  bool operator== (const diff_cursor &y) const {
    return x1 == y.x1 && x2 == y.x2;
  }

  Alphabet letter() const {
    return x1.letter();
  }

  void forward() {
    if (!x2.sink()) x2.forward(x1.letter());
    x1.forward();
  }

  bool first_transition() {
    return x1.first_transition();
  }

  bool next_transition() {
    return x1.next_transition();
  }

  bool find(const Alphabet &a) {
    return x1.find(a);
  }

  bool forward(const Alphabet &a) {
    if (!x1.forward(a)) {
      x2 = x2.sink_state();
      return false;
    }
    if (!x2.sink()) x2.forward(a);
    return true;
  }

  State src() const {
    return State(x1.src(), x2.src());
  }

  State aim() const {
    if (!x2.sink() && x2.find(x1.letter()))
      return State(x1.aim(), x2.aim());
    return State(x1.aim(), x2.sink_state());
  }

  bool src_final() const {
    return x1.src_final() && (x2.sink() || !x2.src_final());
  }

  bool aim_final() const {
    return x1.aim_final() && (x2.sink() || !x2.find(x1.letter()) || !x2.aim_final());
  }

  bool sink() const {
    return x1.sink();
  }
  
  State sink_state() const {
    return State(x1.sink_state(), x2.sink_state());
  }

  bool exists(const Alphabet &a) const {
    return x1.exists(a);
  }

  const Tag& src_tag() const {
    return x1.src_tag();
  }

  const Tag& aim_tag() const {
    return x1.aim_tag();
  }
};

#include <debug.h>

// Symmetrical Difference
// (A1 || A2) \ (A1 && A2)
template <class C1, class C2>   // C1,C2 forward cursor types
class sym_diff_cursor 
  : public diff_cursor<forward_cursor_trace<union_cursor<C1, C2> >, 
  forward_cursor_trace<intersection_cursor<C1, C2> > >
{
public:
  typedef diff_cursor<forward_cursor_trace<union_cursor<C1, C2> >, 
    forward_cursor_trace<intersection_cursor<C1, C2> > > super; 
  typedef sym_diff_cursor self;
  //  typedef pair<union_cursor<C1, C2>::State, intersection_cursor::State> State;

  sym_diff_cursor(const C1 &x1, const C2 &x2)
    : super(tracec(union_cursor<C1, C2>(x1, x2)), tracec(intersection_cursor<C1, C2>(x1, x2)))
  { }

  self& operator=(const State &q) {
    super::operator=(q);
    return *this;
  }
};


template <class ForwardCursor1, class ForwardCursor2>
class concatenation_cursor : public forward_cursor_concept
{
protected:
  typedef list<pair<bool, ForwardCursor2> > container;

  ForwardCursor1 x1;
  ForwardCursor2 i;
  container      x2;
  bool ok1; // ok1 == true signifie x1 est actif et sur une transition
  // déréférençable. Invariant: x1.sink() && ok1 == false (on ne peut
  // pas avoir x1 sur le puits ET ok1 vrai simultanément
  // x1.sink() == true => ok1 == false). Même chose pour les curseurs de
  // x2 qui possèdent leur booléen associé (cf typedef container).
  typename ForwardCursor2::Alphabet current_letter;

public:
  typedef typename ForwardCursor1::Tag Tag;
  typedef pair<typename ForwardCursor1::State, vector<typename ForwardCursor2::State> > State;
  typedef typename ForwardCursor1::Alphabet Alphabet;

  concatenation_cursor(const ForwardCursor1 &c1, const ForwardCursor2 &c2)
    : x1(c1), i(c2), ok1(false) { 
    if (!x1.sink() && x1.src_final() && !i.sink()) x2.push_back(make_pair(false, i));
  }

  bool sink() const {
    return x1.sink() && x2.empty();
  }

  State sink_state() const {
    return State(x1.sink_state(), container());
  }

  State src() const {
    State result(x1.src(), vector<typename ForwardCursor2::State>());
    result.second.reserve(4);
    for(container::const_iterator j = x2.begin(); j != x2.end(); ++j)
      result.second.push_back((*j).second.src());
    return result;
  }

  State aim() const {
    State result;

    result.second.reserve(4);
    for(container::const_iterator j = x2.begin(); j != x2.end(); ++j)
      if ((*j).first && (*j).second.letter() == current_letter) 
	result.second.push_back((*j).second.aim());

    if (ok1 && x1.letter() == current_letter) {
      result.first = x1.aim();
      if (x1.aim_final()) result.second.push_back(i.src());
    }
    else result.first = x1.sink_state();
    return result;
  }
    
  void forward() {
    for(container::iterator j = x2.begin(); j != x2.end(); )
      if ((*j).first && (*j).second.letter() == current_letter) (*j++).second.forward();
      else x2.erase(j++);
    
    if (ok1 && x1.letter() == current_letter) {
      x1.forward();
      if (x1.src_final()) x2.push_back(make_pair(false, i));
    }
    else {
      x1 = x1.sink_state();
      ok1 = false;
    }
  }

  bool first_transition() {
    if (!x2.empty()) {
      container::iterator j;
      for(j = x2.begin(); j != x2.end() && !(*j).second.first_transition(); ++j)
	(*j).first = false;

      if (j != x2.end()) {
	(*j).first = true;
	current_letter = (*j).second.letter();
	for(++j; j != x2.end(); ++j) {
	  (*j).first = (*j).second.first_transition();
	  if ((*j).first) current_letter = min(current_letter, (*j).second.letter());
	}
	if (!x1.sink()) {
	  ok1 = x1.first_transition();
	  if (ok1) current_letter = min(current_letter, x1.letter());
	}
	return true;
      }
    }
    ok1 = !x1.sink() && x1.first_transition();
    if (ok1) current_letter = x1.letter();
    return ok1;
  }

  bool next_transition() {
    Alphabet next_letter;
    if (!x2.empty()) {
      container::iterator j;
      for(j = x2.begin(); j != x2.end(); ++j)
	if ((*j).first && (*j).second.letter() == current_letter) {
	  (*j).first = (*j).second.next_transition();
	  if ((*j).first) {
	    next_letter = (*j).second.letter();
	    break;
	  }
	}

      if (j != x2.end()) {
	for(++j; j != x2.end(); ++j) {
	  if ((*j).first && (*j).second.letter() == current_letter) {
	    (*j).first = (*j).second.next_transition();
	    if ((*j).first) next_letter = min(next_letter, (*j).second.letter());
	  }
	}

	if (ok1 && x1.letter() == current_letter) {
	  ok1 = x1.next_transition();
	  if (ok1) next_letter = min(next_letter, x1.letter());
	}

	current_letter = next_letter;
	return true;
      }
    }
    if (ok1 && x1.letter() == current_letter) {
      ok1 = x1.next_transition();
      if (ok1) current_letter = x1.letter();
      return ok1;
    }
    return false;
  }
    
  Alphabet letter() const {
    return current_letter;
  }
 
  bool find(const Alphabet &a) {
    bool result = ok1 = !x1.sink() && x1.find(a);
    for(container::iterator j = x2.begin(); j != x2.end(); ++j) {
      (*j).first = (*j).second.find(a);
      result = result || (*j).first;
    }
    return result;
  } 
  
  bool forward(const Alphabet &a) {
    result = false;
    for(container::iterator j = x2.begin(); j != x2.end();) 
      if ((*j).second.forward(a)) {
	result = true;
	++j;
      }
      else x2.erase(j++);
    
    if (!x1.sink())
      if (x1.forward(a)) { 
	if (x1.src_final())
	  x2.push_back(i);
	return true;
      }
    
    return result;
  }
  
  bool src_final() const {
    for(container::const_iterator j = x2.begin(); j != x2.end(); ++j)
      if ((*j).second.src_final()) return true;
    return false;
  }

  bool aim_final() const {
    for(container::const_iterator j = x2.begin(); j != x2.end(); ++j)
      if ((*j).first && (*j).second.letter() == current_letter && (*j).second.aim_final()) 
	return true;

    return false;
  }

  bool operator== (const concatenation_cursor &x) const {
    return x1 == x.x1 && ok1 == x.ok1 && x2 == x.x2;
  }

  Tag src_tag() const {
    if (!x1.sink()) return x1.src_tag();
    else return Tag();
  }

  Tag aim_tag() const {
    if (ok1) return x1.aim_tag();
    else return Tag();
  }
};    

/*
template <class ForwardCursor1, class ForwardCursor2>
ostream& operator<< (ostream &out, 
		     const pair<typename ForwardCursor1::State, vector<typename ForwardCursor2::State> > &q)
{
  out << "<" << q.first << ",";
  if (q.second.empty()) out << "0";
  else {
    out << "(";
    copy(q.second.begin(), q.second.end(), ostream_iterator<typename ForwardCursor2::State>(out, ","));
    out << ")";
  }
  out << ">";
  return out;
}
*/

template <class ForwardCursor, unsigned int alphabet_size = 256>
class not_cursor : public forward_cursor_concept
{
protected:
  static typename ForwardCursor::Tag sink_tag;
  static const int SRC, AIM;
  ForwardCursor c;
  unsigned int l;
  bool _sink[2];

public:
  typedef not_cursor                    self;
  typedef typename ForwardCursor::State State;
  typedef typename ForwardCursor::Tag   Tag;
  typedef typename ForwardCursor::Alphabet Alphabet;
  
  not_cursor(const ForwardCursor &x)
    : c(x), l(0) { 
    _sink[SRC] = _sink[AIM] = false;
  }

  bool sink() const {
    return _sink[AIM];
  }

  State src() const {
    return _sink[SRC] ? State() : c.src();
  }

  State aim() const {
    return _sink[AIM] ? State() : c.aim();
  }    

  const Tag& src_tag() const {
    return _sink[SRC] ? sink_tag : c.src_tag();
  }
  
  const Tag& aim_tag() const {
    return _sink[AIM] ? sink_tag : c.aim_tag();
  }    
  
  bool src_final() const {
    return _sink[SRC] || !c.src_final();
  }
  
  bool aim_final() const {
    return _sink[AIM] || !c.aim_final();
  }

  unsigned int letter() const {
    return l;
  }

  void forward() {
    if (!_sink[SRC])
      if (!_sink[AIM]) 
        c.forward();
      else _sink[SRC] = true;
  }
  
  bool forward(unsigned int a) {
    _sink[SRC] = _sink[SRC] || !c.forward(a);
    return true;
  }
  
  bool first_transition() {
    l = 0;
    _sink[AIM] = !_sink[SRC] && !c.find(0); 
    return true;
  }
  
  bool next_transition() {
    ++l;
    if (l < max_letter && !_sink[SRC])
      _sink[AIM] = !c.find(l);
    return l < max_letter;
  }

  bool find(unsigned int a) {
    if (!_sink[SRC])
      _sink[AIM] = !c.find(a);
    l = a;
    return true;
  }

  bool operator== (const self &x) const {
    if (_sink[SRC])
      return x._sink[SRC];
    if (x._sink[SRC])
      return false;
    return src() == x.src() && letter() == x.letter();
  }
};    

template <class T, unsigned int ma>
const int not_cursor<T, ma>::SRC = 0;

template <class T, unsigned int ma>
const int not_cursor<T, ma>::AIM = 1;

// Helper functions:
// Build a forward cursor adapter intersection from two forward cursors:
template <class ForwardCursor1, class ForwardCursor2>
intersection_cursor<ForwardCursor1, ForwardCursor2>
intersectionc(const ForwardCursor1 &x1, const ForwardCursor2 &x2) {
  return intersection_cursor<ForwardCursor1, ForwardCursor2>(x1, x2);
}

template <class ForwardCursor1, class ForwardCursor2>
union_cursor<ForwardCursor1, ForwardCursor2>
unionc(const ForwardCursor1 &x1, const ForwardCursor2 &x2) {
  return union_cursor<ForwardCursor1, ForwardCursor2>(x1, x2);
}

template <class ForwardCursor1, class ForwardCursor2>
diff_cursor<ForwardCursor1, ForwardCursor2>
diffc(const ForwardCursor1 &x1, const ForwardCursor2 &x2) {
  return diff_cursor<ForwardCursor1, ForwardCursor2>(x1, x2);
}

template <class ForwardCursor1, class ForwardCursor2>
sym_diff_cursor<ForwardCursor1, ForwardCursor2>
sym_diffc(const ForwardCursor1 &x1, const ForwardCursor2 &x2) {
  return sym_diff_cursor<ForwardCursor1, ForwardCursor2>(x1, x2);
}

template <class ForwardCursor1, class ForwardCursor2>
concatenation_cursor<ForwardCursor1, ForwardCursor2>
concatenationc(const ForwardCursor1 &x1, const ForwardCursor2 &x2) {
  return concatenation_cursor<ForwardCursor1, ForwardCursor2>(x1, x2);
}

template <class ForwardCursor>
not_cursor<ForwardCursor> notc(const ForwardCursor &x) {
  return not_cursor<ForwardCursor>(x);
}

#endif