tools.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_TOOLS_H
#define ASTL_TOOLS_H

#include <astl.h>
#include <memory>
#include <utility>
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>
#include <list>
#include <set>

#ifndef _MSC_VER
#include <unistd.h>   // getopt
#define POPEN popen
#define PCLOSE pclose
#else
#include <cstdio>
#define POPEN _popen
#define PCLOSE _pclose
#define max _MAX
#endif

#include <cstdio>     // perror, fread
#include <ctime>      // clock
#include <functional>

using namespace std;

ASTL_BEGIN_NAMESPACE

// Define class smart pointer with following properties:
// 1. A smart pointer allocates automatically the pointed object
// 2. A smart pointer share the pointed object with its copies
// 3. A smart pointer deallocates the pointed object when no other smart pointer points to the object
// 4. operator== returns true if both pointers point to the same object

template <typename T>
class smart_ptr
{
protected:
  struct object
  {
    T data;
    unsigned int count;

    object()
      : count(1)
    { }
  };

  object *p;

public:
  typedef smart_ptr self;

  smart_ptr()
    : p(new object)
  { }

  smart_ptr(const self &x)
    : p(x.p) {
    ++p->count;
  }

  ~smart_ptr() {
    if (--p->count == 0) delete p;
  }

  smart_ptr& operator=(const self &x) {
    if (--p->count == 0) delete p;
    p = x.p;
    ++p->count;
    return *this;
  }

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

  T& operator*() {
    return p->data;
  }

  const T& operator*() const {
    return p->data;
  }

  T* operator->() {
    return &(p->data);
  }

  const T* operator->() const {
    return &(p->data);
  }
};


// Make sure a C++ builtin data type is constructed with a default value:
#ifndef _MSC_VER
template <class T, T value = (T) 0>
#else
template <class T>
#endif
struct safe
{
  T q;
  safe(T p)
    : q(p)
  { }

#ifndef _MSC_VER
  safe()
    : q(value)
  { }
#else
  safe()
    : q(0)
  { }
#endif

  operator T () const {
    return q;
  }

  safe& operator=(T p) {
    q = p;
    return *this;
  }
};

// Equivalent to popen(command, "r") (RTFM)
// remove the last \n if any
string execute(const string &command)
{
  FILE *f = POPEN(command.c_str(), "r");
  if (f == NULL) return "";
  string r;
  size_t n;
  for(char buffer[1024]; 
      (n = fread(buffer, sizeof(char), 1023, f)) > 0; 
      r += buffer)
    buffer[n] = '\0';
  PCLOSE(f);
  if (r[r.size() - 1] == '\n')
    r.erase(r.size() - 1);
  return r;
}
     
// A memory mappable vector used by DFA_compact. It does not cope with
// the standard (minimal interface). Use with caution, once mapped, a
// vector only supports read-only operations.
// Type requirements: T shall be a POD type.

template <typename T>
class mapable_vector
{
protected:
  bool mapped;
  T   *first, *last, *eos;

public:
  typedef size_t   size_type;
  typedef T        value_type;
  typedef T*       iterator;
  typedef const T* const_iterator;
  typedef T&       reference;
  typedef const T& const_reference;
  typedef mapable_vector self;

  mapable_vector()
    : mapped(false), first(NULL), last(NULL), eos(NULL)
  { }

  mapable_vector(size_type s)
    : mapped(false) {
    first = new T[s];
    last = eos = first + s;
    memset(first, 0, s * sizeof(T));
  }

  void clear() {
#ifndef _MSC_VER
    if (mapped)
      munmap();
    else 
#endif
      {
	delete [] first;
	first = last = eos = NULL;
      }
  }

  self& operator=(const self &x) {
    if (&x != this) {
      clear();  // set first to NULL
      if (!x.empty()) first = new T[x.size()];
      last = eos = first + x.size();
      copy(x.first, x.last, first);
    }
    return *this;
  }

  size_t size() const {
    return last - first;
  }

  bool empty() const {
    return size() == 0;
  }

  T& back() {
    return last[-1];
  }

  const T& back() const {
    return last[-1];
  }

  T& front() {
    return *first;
  }

  const T& front() const {
    return *first;
  }

  T& operator[](size_type s) {
    return first[s];
  }

  const T& operator[](size_type s) const {
    return first[s];
  }

  bool write(ostream& out) const {
    size_type s = size();
    out.write((const char*) &s, sizeof(size_type));
    out.write((const char*) first, sizeof(T) * size());
    return (bool) out;
  }

  bool read(istream& in) {
    size_type s;
    in.read((char*) &s, sizeof(size_type));
    clear();
    if (s > 0) first = new T[s];
    last = eos = first + s;
    in.read((char*) first, sizeof(T) * s);
    return (bool) in;
  }

#ifndef _MSC_VER	
  bool mmap(int file_desc) {
    delete [] first;
    size_t p;
    ::read(file_desc, &p, sizeof(size_type));
    first = (T*) ::mmap(0, p * sizeof(T), PROT_READ, MAP_FILE | MAP_PRIVATE, file_desc, 0);
    if (first == (T*) -1)	return false;
    last = eos = first + p;
    lseek(file_desc, p * sizeof(T), SEEK_CUR);
    mapped = true;
    return true;
  }

  void munmap() {
    if (mapped) {
      ::munmap((char*) first, size() * sizeof(T));
      first = last = eos = NULL;
      mapped = false;
    }
  }
#endif

  size_type capacity() const {
    return eos - first;
  }

  void resize(size_type s, const T& x) {
    if (s < size()) erase(begin() + s, end());
    else insert(end(), s - size(), x);
  }

  void erase(iterator i, iterator j) {
    copy(j, last, first);
    last -= j - i;
  }

  void insert(iterator i, size_type s, const T& x = T()) {
    if (s + size() > capacity()) {
      T *p = new T[s + size()];
      copy(first, i, p);
      copy_backward(i, last, p + (i - first) + s);
      i = p + (i - first);
      last = p + size() + s;
      delete [] first;
      first = p;
      eos = last;
    }
    else {
      copy_backward(i, last, i + s);
      last += s;
    }
    fill(i, i + s, x);
  }
			
  iterator begin() {
    return first;
  }

  iterator end() {
    return last;
  }

  const_iterator begin() const {
    return first;
  }

  const_iterator end() const {
    return last;
  }

  void push_back(const T& x) {
    if (last == eos) {
      T *p = new T[max((size_t) 1, size()) * 2];
      copy(first, last, p);
      delete [] first;
      eos = p + 2 * max((size_t) 1, size());
      last = p + size();
      first = p;
    }

    *last++ = x;			
  }

  ~mapable_vector() {
    clear();
  }
};

// A compact table maps integers to static arrays of element of type T
// To use the read/write functionalities, T must be a POD type
// For example, say t is a compact table, the sequence #4 is defined 
// by the range t[4],t[5] or t.range(4)
// a mapped compact table is a static object
template <typename T>
class compact_table
{
protected:
  mapable_vector<typename mapable_vector<T>::size_type> index;
  T *data, *eos;  // data and end-of-storage
  int fd;         // file descriptor for memory mapping

  bool mapped() const {
    return fd > -1;
  }

  void mapped(bool b) {
    if (b && fd < 0) fd = 0;
    else fd = -1;
  }

public:
  typedef typename mapable_vector<typename mapable_vector<T>::size_type>::size_type size_type;

  compact_table()
    : index(1), data(NULL), eos(NULL), fd(-1)
  { }

  ~compact_table() {
#ifndef _MSC_VER
    if (mapped()) munmap();
    else
#endif
      delete [] data;
  }
  
  size_t size() const {
    return index.size() - 1;
  }

  bool empty() const {
    return size() == 0;
  }

  bool mmap(const string &path) {
    fd = open(path.c_str(), O_RDONLY);
    if (fd == -1) return false;
    return mmap(fd);
  }

  bool mmap(int f) {
    mapped(true);
    if (index.mmap(f)) {
      data = (T*) ::mmap(0, index.back() * sizeof(T), 
			 PROT_READ, MAP_FILE | MAP_PRIVATE, f, 0);
      if (data = (T*) -1) return false;
      eos = data + index.back();
      return true;
    }
    return false;
  }

#ifndef _MSC_VER
  void munmap() {
    index.munmap();
    if (fd > 0) close(fd);
    mapped(false);
  }    
#endif

  istream& read(istream& i) {
    mapped(false);
    index.read(i);
    data = new T[index.back()];
    i.read((char*) data, index.back() * sizeof(T));
    eos = data + index.back();
    return i;
  }

  ostream& write(ostream& o) const {
    index.write(o);
    o.write((char*) data, index.back() * sizeof(T));
    return o;
  }

  const T* operator[](size_t i) const {
    return data + index[i];
  }

  pair<const T*, const T*> range(size_t i) const {
    return make_pair((*this)[i], (*this)[i + 1]);
  }

  vector<T> find(size_t i) const {
    return vector<T>((*this)[i], (*this)[i + 1]);
  } 

  template <typename OutputIterator>
  OutputIterator find_and_write(size_t i, OutputIterator x) const {
    return copy((*this)[i], (*this)[i + 1] - 1, x);
  }

  size_type capacity() const {
    return eos - data;
  }

  template <typename RandomAccessIterator>
  void push_back(RandomAccessIterator start, RandomAccessIterator finish) 
  {
    if (capacity() - index.back() < (size_type) (finish - start)) {
      if (data == NULL) {
	data = new T[finish - start];
	eos = data + (finish - start);
	copy(start, finish, data);
      }
      else {
	size_type new_size;
	for(new_size = 2 * capacity(); 
	    new_size - index.back() < (size_type) (finish - start);
	    new_size *= 2);
      
	T *tmp = new T[new_size];
	copy(start, finish, copy(data, data + index.back(), tmp));
	delete [] data;
	data = tmp;
	eos = data + new_size;
      }
    }
    else copy(start, finish, data + index.back()); 
    index.push_back(index.back() + (finish - start));
  }
};


#ifndef CONFIG_NEW_SCHOOL
// Command line parser
// User Options: -m {yes|no} /* state marks */
//               -r {matrix|map|bin|mtf|tr}
//               -v verbose mode
// Parameters:   number of inputs
//               allowed representations for automata

struct config
{
  bool state_mark;
  string representation;
  bool verbose_mode;
  string aux_file;
  ifstream aux_input;
  FILE *aux_handle;
  ofstream output;
  int argc;
  char** argv;
  int inputs;
  int arg_pos;
  vector<string> representations;
  list<string> options;
  string use, description;

  void usage()
  {
    cerr << "Usage: " << argv[0] << " [-v] [-m {yes|no}]";
    if (representations.size() > 1) {
      cerr << " [-r {";
      vector<string>::const_iterator i = representations.begin();
      while (1) {
	cerr << *i;
	if (++i != representations.end()) cerr << "|";
	else break;
      }
      cerr << "}]";
    }
    cerr << " " << use;
    if (!use.empty()) cerr << " ";
    if (inputs == 2) cerr << "file";
    cerr << endl;
    cerr << "  " << description << endl;
    cerr << "   -v\tverbose output to stderr" << endl;
    cerr << "   -m\tmark states during traversal (disabled by default)" << endl;
    if (representations.size() > 1)
      cerr << "   -r\tchoose DFA representation, default is " << representations.front() << endl; 
    if (representation.empty() && !representations.empty()) 
      representation = representations.front();
    exit(1);
  }

  config(int argc_, char** argv_, int inputs_, const string representations_ = "", 
	 const string &use_ = "", const string &desc = "")
    : state_mark(false), verbose_mode(false), argc(argc_), argv(argv_), 
      inputs(inputs_), use(use_), description(desc) {

    aux_handle = NULL;
    string tmpr = representations_;
    if (tmpr == "all") tmpr = "map matrix bin tr mtf";
    string::iterator i, j = tmpr.begin();
    for(;;) {
      i = j;
      j = find(j, tmpr.end(), ' ');
      representations.push_back(string(i, j));
      if (j == tmpr.end()) break;
      ++j;
    }

    copy(argv_ + 1, argv_ + argc, back_inserter(options));
    arg_pos = 1;
    for(list<string>::iterator x = options.begin(); x != options.end(); ++arg_pos)
      if (x->operator[](0) != '-') {
	if (inputs > 1 && aux_file.empty()) {
	  aux_file = *x;
	  aux_input.open(aux_file.c_str());
	  if (!aux_input) {
	    string msg = argv_[0];
	    msg = msg + ": " + aux_file;
	    perror(msg.c_str());
	    exit(2);
	  }
	  aux_handle = fopen(aux_file.c_str(), "rb");
	  if (aux_handle == NULL) {
	    perror(aux_file.c_str());
	    exit(2);
	  }
	  options.erase(x++);
	}
	else break;
      }
      else if (*x == "-v") {
	verbose_mode = true;
	options.erase(x++);
      }
      else if (*x == "-m") {
	options.erase(x++);
	if (x == options.end()) usage();
	++arg_pos;
	if (*x == "yes") state_mark = true;
	else
	  if (*x == "no") state_mark = false;
	  else usage();
	options.erase(x++);
      }
      else if (*x == "-r") {
	if (representations.size() < 2) usage();