set_operation.h

一个类似STL的自动机的源代码库

/*
 * ASTL - the Automaton Standard Template Library.
 * C++ generic components for Finite State Automata handling.
 * Copyright (C) 2000-2003 Vincent Le Maout ([e-mail]).
 * 
 * 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_H
#define ASTL_SET_OPERATION_H

#include <astl.h>

// 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>
#include <map>

#ifdef _MSC_VER
#define min _MIN
#endif

using namespace std;

ASTL_BEGIN_NAMESPACE

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_type, 
	       typename ForwardCursor2::state_type> state_type;
  typedef pair<typename ForwardCursor1::tag_type, 
	       typename ForwardCursor2::tag_type>   tag_type;
  typedef typename ForwardCursor1::char_type        char_type;
  typedef typename ForwardCursor1::char_traits      char_traits;

  // Backward compatibility typedefs:
  typedef tag_type Tag;
  typedef char_type Alphabet;
  typedef state_type State;

  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_type& src_tag() const {
    return tag_type(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 = 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_type, 
	       typename ForwardCursor2::state_type> state_type;
  typedef pair<typename ForwardCursor1::tag_type, 
	       typename ForwardCursor2::tag_type>   tag_type;
  typedef typename ForwardCursor1::char_type        char_type;
  typedef typename ForwardCursor1::char_traits      char_traits;

  // Backward compatibility typedefs:
  typedef tag_type Tag;
  typedef char_type Alphabet;
  typedef state_type State;

  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) {
    bool r = first.find(a);  // we don't want any lazy boolean evaluation
    return second.find(a) && r;
  }

  bool forward(const Alphabet &a) {
    if (first.forward(a) && second.forward(a)) return true;
    *this = sink_state();
    return false;
  }

  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);
  }

  Tag src_tag() const {
    return Tag(first.src_tag(), second.src_tag());
  }

  Tag aim_tag() const {
    return Tag(first.aim_tag(), second.aim_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_type, 
	       typename ForwardCursor2::state_type> state_type;
  typedef typename ForwardCursor1::char_type        char_type;
  typedef typename ForwardCursor1::tag_type         tag_type;
  typedef typename ForwardCursor1::char_traits      char_traits;

  // Backward compatibility typedefs:
  typedef tag_type Tag;
  typedef char_type Alphabet;
  typedef state_type State;

  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();
  }
};

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

  sym_diff_cursor(const C1 &x1, const C2 &x2)
    : super(unionc(x1, x2), intersectionc(x1, x2))
  { }

  self& operator=(const state_type &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閞閒閞en鏰ble. Invariant: x1.sink() && ok1 == false (on ne peut
  // pas avoir x1 sur le puits ET ok1 vrai simultan閙ent
  // x1.sink() == true => ok1 == false). M阭e chose pour les curseurs de
  // x2 qui poss鑔ent leur bool閑n associ