combinatory.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_COMBINATORY_H
#define ASTL_COMBINATORY_H

#include <vector>
#include <string>
#include <cursor.h>  // forward_cursor_concept
#include <tag.h>
#include <concept.h>
#include <alphabet.h>

// Defines:
// 1. combination_cursor (forward cursor)
// 2. permutation_cursor (forward cursor)

// A combination_cursor simulates a DFA whose language is the combinations
// with p intergers out of n (C(n,p))
//
// Constructor:
// 1. n, p

class combination_cursor : public forward_cursor_concept
{
protected:
  std::vector<bool> visited;
  unsigned int current;
  int          remaining;

public:
  typedef combination_cursor    self;
  typedef empty_tag             tag_type;
  typedef std::vector<bool>     state_type;
  typedef unsigned int          char_type;
  typedef CHAR_TRAITS<int> char_traits;

  combination_cursor(unsigned int n, unsigned int p) 
    : visited(n, false), current(0), remaining(p)
  { }

  state_type src() const {
    return visited;
  }

  state_type aim() const {
    vector<bool> tmp = visited;
    tmp[current] = true;
    return tmp;
  }

  bool sink() const {
    return visited.empty();
  }

  state_type sink_state() const {
    return vector<bool>();
  }

  void forward() {
    --remaining;
    visited[current] = true;
  }

  bool forward(unsigned int letter) {
    if (visited[letter - 1] == false) {
      visited[letter - 1] = true;
      --remaining;
      return true;
    }
    visited.clear();
    return false;
  }

  bool first_transition() {
    for(vector<bool>::const_iterator i = visited.begin(); i != visited.end(); ++i)
      if (*i == false) {
	current = i - visited.begin();
	return true;
      }
    return false;
  }

  bool next_transition() {
    for(vector<bool>::const_iterator i = visited.begin() + current + 1; i != visited.end(); ++i)
      if (*i == false) {
	current = i - visited.begin();
	return true;
      }
    return false;
  }

  unsigned int letter() const {
    return current + 1;
  }

  bool src_final() const {
    return remaining < 1;
  }

  bool aim_final() const {
    return remaining < 2;
  }

  bool operator== (const self &x) const {
    return remaining == x.remaining && current == x.current && 
      visited[current] == x.visited[current];
  }

  bool find(unsigned int letter) {
    if (visited[letter - 1] == false) {
      current = letter - 1;
      return true;
    }
    return false;
  }
};

// A permutation_cursor simulates a DFA whose language is all permutations
// of the word 1234...n 
//
// Constructor:
// 1. n

class permutation_cursor : public forward_cursor_concept
{
protected:
  std::vector<bool> visited;
  int          current;
  int          remaining;

public:
  typedef permutation_cursor self;
  typedef empty_tag          tag_type;
  typedef std::vector<bool>  state_type;
  typedef unsigned int       char_type;
  typedef CHAR_TRAITS<int> char_traits;

  permutation_cursor(unsigned int n)
    : visited(n, false), current(0), remaining(n)
  { }

  bool sink() const {
    return current == -1;
  }

  state_type src() const {
    return visited;
  }

  state_type aim() const {
    std::vector<bool> tmp = visited;
    tmp[current] = true;
    return tmp;
  }

  void forward() {
    --remaining;
    visited[current] = true;
  }

  bool forward(int letter) {
    if (visited[letter - 1] == false) {
      visited[letter - 1] = true;
      --remaining;
      return true;
    }
    current = -1;
    return false;
  }

  bool first_transition() {
    for(std::vector<bool>::const_iterator i = visited.begin(); i != visited.end(); ++i)
      if (*i == false) {
	current = i - visited.begin();
	return true;
      }
    return false;
  }

  bool next_transition() {
    for(std::vector<bool>::const_iterator i = visited.begin() + current + 1; i != visited.end(); ++i)
      if (*i == false) {
	current = i - visited.begin();
	return true;
      }
    return false;
  }

  int letter() const {
    return current + 1;
  }

  bool src_final() const {
    return remaining == 0;
  }

  bool aim_final() const {
    return remaining == 1;
  }

  bool operator== (const self &x) const {
    return remaining == x.remaining && current == x.current && 
      visited[current] == x.visited[current];
  }

  bool find(unsigned int letter) {
    if (visited[letter - 1] == false) {
      current = letter - 1;
      return true;
    }
    return false;
  }

  bool exists(int letter) const {
    return visited[letter - 1] == false;
  }
};

// Helper functions:
inline
permutation_cursor permutationc(unsigned int n) {
  return permutation_cursor(n);
}

inline
combination_cursor combinationc(unsigned int n, unsigned int p) {
  return combination_cursor(n, p);
}

#endif // ASTL_COMBINATORY_H