/*
 * 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_CLASS_COMBINATORY_CURSORS
#define ASTL_CLASS_COMBINATORY_CURSORS

#include <vector>
#include <cursor.h>  // forward_cursor_concept
#include <tag.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:
  vector<bool> visited;
  unsigned int current;
  int          remaining;

public:
  typedef combination_cursor self;
  typedef empty_tag          Tag;
  typedef vector<bool>       State;
  typedef unsigned int       Alphabet;

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

  State src() const {
    return visited;
  }

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

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

  bool forward(unsigned int letter) {
    if (visited[letter - 1] == false) {
      visited[letter - 1] = true;
      --remaining;
      return true;
    }
    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;
  }

  unsigned int operator*() const {
    return letter();
  }

  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:
  vector<bool> visited;
  int          current;
  int          remaining;

public:
  typedef permutation_cursor self;
  typedef empty_tag          Tag;
  typedef vector<bool>       State;
  typedef unsigned int       Alphabet;

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

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

  State src() const {
    return visited;
  }

  State aim() const {
    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(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;
  }

  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:
permutation_cursor permutationc(unsigned int n) {
  return permutation_cursor(n);
}

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

#endif // ASTL_CLASS_COMBINATORY_CURSORS