tools.h

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

	options.erase(x++);
	if (x == options.end()) usage();
	++arg_pos;
	if (find(representations.begin(), representations.end(), *x) != representations.end())
	  representation = *x;
	else
	  usage();
	options.erase(x++);
      }
      else ++x;
	
    if (representation.empty() && !representations.empty()) 
      representation = representations.front();
    
    if (inputs > 1 && aux_file.empty()) usage();

    if (verbose_mode) {
      char buffer[1024];
      FILE *f = POPEN("date", "r");
      buffer[max((int) fread(buffer, sizeof(char), 1023, f) - 1, 0)] = '\0';
      PCLOSE(f);
      cerr << buffer << " \"";
      copy(argv, argv + argc, ostream_iterator<char*>(cerr, " "));
      cerr << "\"" << endl;
    }
  }

  ~config() 
  {
    if (verbose_mode) 
      cerr << argv[0] << ": " << clock() / (double) CLOCKS_PER_SEC << " s CPU time" << endl;

    if (!aux_file.empty())
      aux_input.close();
    if (aux_handle != NULL)
      fclose(aux_handle);
  }

  typedef list<string>::const_iterator const_iterator;
  const_iterator begin() const {
    return options.begin();
  }
  const_iterator end() const {
    return options.end();
  }
};
#else
// options o("-v(verbose mode)-r(choose DFA representation):{map,matrix,bin}-m{yes,no}file()[file2()]")
class command_line
{
protected:
  set<string> options;                  // options found on the command line
  map<string, string> options_descriptions;
  
public:
  string name, synopsis, description;   // remember something ? :-)
  map<string, string> args;             // arguments for options

  void usage(ostream &out = cerr);
  command_line(int argc, char **argv, const string &command_desc, const string &synopsis_ = "")
    : name(argv[0]), synopsis(synopsis_), description(command_desc) 
  { }
    
  bool operator[](const string &s) {
    return options.find(s) != options.end();
  }
};

void command_line::usage(ostream &out)
{
  out << "Usage: " << name << " " << synopsis << endl << "\t" << description << endl;
  for(map<string, string>::const_iterator i = options_descriptions.begin(); i != options_descriptions.end(); ++i)
    out << "\t" << i->first << " " << i->second << endl;
}

#endif // CONFIG_NEW_SCHOOL


template <class T1, class T2, class T3>
struct triple : public std::pair<T1, T2>
{
  T3 third;

  triple() : pair<T1, T2>(), third() { }
  triple(const T1 &t1, const T2 &t2, const T3 &t3)
    : std::pair<T1, T2>(t1, t2), third(t3) { }
};

template <class T1, class T2, class T3>
inline bool operator == (const triple<T1, T2, T3> &x,
			 const triple<T1, T2, T3> &y) {
  return (x.first == y.first && x.second == y.second && x.third == y.third);
}

template <class T1, class T2, class T3>
inline triple<T1, T2, T3> make_triple(const T1 &x, const T2 &y,
				      const T3 &z) {
  return (triple<T1, T2, T3>(x, y, z));
}

template <class T1, class T2, class T3>
inline triple<T1, T2, T3> make_triple(const T1 &x, const pair<T2, T3> &y) {
  return (triple<T1, T2, T3>(x, y.first, y.second));
}

// File iterator classes
//  Descrition: - input and random access iterators on a file accessed
//                through the system call read. It is implemented with a reference
//                counting buffer allowing efficient by-value calls to function
//              - Define a specialized version of the standard STL copy algorithm
//
//  Template Parameters: 1. The buffer size in bytes (default 8192)
//                       2. A unary object function from char to any type used as 
//                          output filter (default identity<char>)
//  Constructor args:    1. A file descriptor. The default constructor is used to
//                          build a past-the-end iterator
//  Remarks: No checks are made on the value returned by read. If an error occurs,
//  i.e. read returns -1, the behavior is undefined. Also, all operations regarding
//  file opening and closing are left up to the user.
//

// This one should be used to read "once and only once" streams (i.e. pipes), it is
// an input iterator. It is then forbidden to iterate through a sequence with two
// iterators simultaneously. The reference counting functionnality is only provided
// for the copy constructor to be efficient.

template <int BUFFER_SIZE = 8192>
class finput_iterator : public iterator<input_iterator_tag, char>
{
protected:
  struct shared_buffer
  {
    FILE* file;
    unsigned int references;
    char buffer[BUFFER_SIZE];
    
    shared_buffer(FILE *handle) 
      : file(handle), references(1)
    { }
  } *b;

  char *c, *eob;  // eob == end of buffer

public:
  typedef finput_iterator self;

  finput_iterator(FILE* handle)
    : b(new shared_buffer(handle)), c(b->buffer) { 
    eob = c + fread(c, sizeof(char), BUFFER_SIZE, b->file);
  }
  
  finput_iterator()
    : b(NULL), eob(NULL)
  { }
  
  ~finput_iterator() {
    if (b && --b->references == 0) 
      delete b;
  }
  
  finput_iterator(const self &x) 
    : b(x.b), c(x.c), eob(x.eob) {
    if (b) ++b->references;
  }
  
  self& operator++ () {
    if (++c == eob) {
      c = b->buffer;
      eob = c + fread(c, sizeof(char), BUFFER_SIZE, b->file);
      if (c == eob) eob = NULL;  // end of file
    }
    return *this;
  }

  self operator++ (int) {
    self tmp = *this;
    ++(*this);
    return tmp;
  }

  self::value_type operator* () const {
    return *c;
  }

  bool operator==(const self &x) const {
    return eob == x.eob;   // useful only for end of range equality testing
  }
};

template <int BUFFER_SIZE = 8192 >
class frandom_iterator : public iterator<random_access_iterator_tag, char>
{
protected:
  struct shared_buffer
  {
    FILE* file;
    unsigned int references;
    char buffer[BUFFER_SIZE];
    
    shared_buffer(FILE *handle) 
      : file(handle), references(1)
    { }
  } *buff;

  long _offset;
  char *c, *eob;  // current char and end-of-buffer

public:
  typedef frandom_iterator self;

  frandom_iterator()
    : buff(NULL), c(NULL) 
  { }

  frandom_iterator(FILE *handle)
    : buff(new shared_buffer(handle)), 
      _offset(fseek(handle, 0, SEEK_CUR)), c(buff->buffer) { 
    eob = c + fread(c, sizeof(char), BUFFER_SIZE, buff->file);
    if (c == eob) c = NULL;
  }

  int offset() const {
    return _offset;
  }
  
  ~frandom_iterator() {
    if (buff != NULL && --buff->references == 0) 
      delete buff;
  }
  
  frandom_iterator(const self &x) 
    : buff(x.buff), _offset(x._offset),  c(x.c), eob(x.eob) {
    if (buff != NULL) ++buff->references;
  }
  
  self& operator++ () {
    ++_offset;
    if (++c == eob) {
      if (buff->references > 1) {
	--buff->references;
	buff = new shared_buffer(buff->file);
      }
      fseek(buff->file, _offset, SEEK_SET);
      eob = buff->buffer + fread(buff->buffer, sizeof(char), BUFFER_SIZE, buff->file);
      if (eob == buff->buffer) c = NULL;      // EOF
      else c = buff->buffer;

    }
    return *this;
  }

  self operator++ (int) {
    self tmp = *this;
    ++(*this);
    return tmp;
  }

  self& operator=(const self &x) {
    if (this != &x) {
      if (buff != NULL && --buff->references == 0) delete buff;
      buff = x.buff; c = x.c; _offset = x._offset; eob = x.eob;
      if (buff != NULL) ++buff->references;
    }
    return *this;
  }

  self::value_type operator* () const {
    return *c;
  }

  bool operator==(const self &x) const {
    if (c == NULL) return x.c == NULL;
    return (x.c != NULL) && (_offset == x._offset);
  }

  self operator+(int x) const {
    if (c + x >= eob || c + x < buff->buffer) {
      fseek(buff->file, _offset + x, SEEK_SET);
      return frandom_iterator(buff->file);
    }
    frandom_iterator r(*this);
    r.c += x; r._offset += x; 
    return r;
  }
		
  self& operator+=(int x) {
    c += x; 
    _offset += x;
    if (c >= eob || c < buff->buffer) {
      fseek(buff->file, _offset, SEEK_SET);
      c = buff->buffer;
      eob = c + fread(c, sizeof(char), BUFFER_SIZE, buff->file);
    }
    return *this;
  }

  self operator-(int x) const {
    if (c == NULL || c - x < buff->buffer || c - x >= eob) {
      fseek(buff->file, _offset - x, SEEK_SET);
      return frandom_iterator(buff->file);
    }
    frandom_iterator r(*this);
    r.c -= x; r._offset -= x;
    return r;
  }

  int operator-(const self &x) const {
    return _offset - x._offset;
  }
	
  self& operator-=(int x) {
    _offset -= x;
    if (c == NULL || c - x < buff->buffer || c - x >= eob) {
      fseek(buff->file, _offset, SEEK_SET);
      c = buff->buffer;
      eob = c + fread(c, sizeof(char), BUFFER_SIZE, buff->file);
    }
    else c -= x; 
    return *this;
  }

  bool operator<(const self &x) const {
    return _offset < x._offset;
  }
  
  self::value_type operator[](int x) const {
    return *(*this + x);
  }
};

// Equivalent to UNIX command "tr" (RTFM)
template <typename InputIterator>
class translate 
  : public iterator<input_iterator_tag, char>
{
protected:
  InputIterator i;
  vector<char> tr;

public:
  typedef translate self;

  translate()
  { }

  translate(const InputIterator &x)
    : i(x)
  { }

  translate(const InputIterator &x, const string& src, const string& trg)
    : i(x), tr(256)
  {
    for(vector<char>::size_type j = 0; j < 256; ++j)  // identity
      tr[j] = (char) j;

    for(string::const_iterator j = src.begin(), k = trg.end(); 
	j != src.end(); ++j, ++k)
      tr[(vector<char>::size_type) *j] = *k;
  }
    
  value_type operator*() const {
    return tr[(vector<char>::size_type) *i];
  }

  self& operator++() {
    ++i;
    return *this;
  }

  self operator++(int) {
    self tmp = *this;
    ++(*this);
    return tmp;
  }

#ifndef _MSC_VER
  friend bool operator==<>(const self&, const self&);
#else
  friend bool operator==(const self&, const self&);
#endif
};

template <typename InputIterator>
bool operator==(const translate<InputIterator> &x,
		const translate<InputIterator> &y) {
  return x.i == y.i;
}

template <typename InputIterator>
bool operator!=(const translate<InputIterator> &x,
		const translate<InputIterator> &y) {
  return !(x == y);
}

// Equivalent to UNIX command "tr -s" (RTFM)
template <typename InputIterator>
class squeeze 
  : public iterator<input_iterator_tag, char>
{
protected:
  InputIterator first, last;
  vector<char>  squeeze_me;
  char          c;

public:
  typedef squeeze self;

  squeeze()
  { }

  squeeze(const string& chars, const InputIterator &start, 
	  const InputIterator &finish = InputIterator())
    : first(start), last(finish), squeeze_me(256, (char) 0)
  {
    for(string::const_iterator j = chars.begin();
	j != chars.end(); ++j)
      squeeze_me[(vector<char>::size_type) *j] = (char) 1;
    if (first != last) c = *first;
  }
    
  value_type operator*() const {
    return c;
  }

  self& operator++() {
    if (squeeze_me[(vector<char>::size_type) c] == (char) 0) {
      ++first;
      c = *first;
    }
    else {
      char d;
      while(++first != last) {
	d = *first;
	if (d != c) {
	  c = d;
	  break;
	}
      }
    }
    return *this;
  }

  self operator++(int) {
    self tmp = *this;
    ++(*this);
    return tmp;
  }

#ifndef _MSC_VER
  friend bool operator==<>(const self&, const self&);
#else
  friend bool operator==(const self&, const self&);
#endif
};

template <typename InputIterator>
bool operator==(const squeeze<InputIterator> &x,
		const squeeze<InputIterator> &y) {
  return x.first == y.first;
}

template <typename InputIterator>
bool operator!=(const squeeze<InputIterator> &x,
		const squeeze<InputIterator> &y) {
  return !(x == y);
}

// Equivalent to UNIX command "tr -d" (RTFM)
template <typename InputIterator>
class ignore 
  : public iterator<input_iterator_tag, char>
{
protected:
  InputIterator first, last;
  vector<char>  ignore_me;
  char          c;

public:
  typedef ignore self;

  ignore()  // end of sequence
  { }

  ignore(const string& chars, const InputIterator &start, 
	 const InputIterator &finish = InputIterator())
    : first(start), last(finish), ignore_me(256, (char) 0)
  {
    for(string::const_iterator j = chars.begin();
	j != chars.end(); ++j)
      ignore_me[(vector<char>::size_type) *j] = (char) 1;
    if (first != last) {
      c = *first;
      if (ignore_me[(vector<char>::size_type) c] == (char) 1)
	++(*this);
    }
  }
    
  value_type operator*() const {
    return c;
  }

  self& operator++() {
    while(++first != last) {
      c = *first;
      if (ignore_me[(vector<char>::size_type) c] == (char) 0) 
	break;
    }
    return *this;
  }
	
  self operator++(int) {
    self tmp = *this;
    ++(*this);
    return tmp;
  }

#ifndef _MSC_VER
  friend bool operator==<>(const self&, const self&);
#else
  friend bool operator==(const self&, const self&);
#endif
};

template <typename InputIterator>
bool operator==(const ignore<InputIterator> &x,
		const ignore<InputIterator> &y) {
  return x.first == y.first;
}

template <typename InputIterator>
bool operator!=(const ignore<InputIterator> &x,
		const ignore<InputIterator> &y) {
  return !(x == y);
}

template <class T, class U>
ostream& operator<< (ostream &out, const pair<T, U> &p) {
  out << "<" << p.first << ", " << p.second << ">";
  return out;
}

template <class T, class Allocator>
ostream& operator<<(ostream &out, const vector<T, Allocator> &v) 
{
  out << "(";
  if (v.empty()) return out << " )";
  typename vector<T, Allocator>::const_iterator i = v.begin();
  while (1) {
    out << *i;
    if (++i != v.end()) out << ",";
    else return out << ")";
  }
}

template <class T>
ostream& operator<<(ostream &out, const set<T> &v) 
{
  out << "(";
  if (v.empty()) return out << " )";
  typename set<T>::const_iterator i = v.begin();
  while (1) {
    out << *i;
    if (++i != v.end()) out << ",";
    else return out << ")";
  }
}


#ifdef _MSC_VER
const char *optarg;

int getopt(int argc, char* const* argv, const char *opt)
{
  static char* const* prev_argv = NULL;
  static int          offset = 0;

  optarg = NULL;
  int r = -1;

  if (argv != prev_argv) {
    prev_argv = argv;
    offset = 0;
  }

  if (++offset < argc) {
    if (argv[offset][0] == '-') {
      const char* p = find(opt, opt + strlen(opt), argv[offset][1]);
      if (*p != '\0' && strlen(argv[offset]) == 2) {
	r = *p;
	if (p[1] == ':')
	  if (offset + 1 == argc || argv[offset + 1][0] == '-') 
	    return ':'; // missing argument to option
	  else optarg = argv[++offset];
      }
    }
  }
  return r;
}
#endif  // _MSC_VER

ASTL_END_NAMESPACE

#endif