dfa_compact.h

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

      return (end());
    }
    
    size_type count(const Key& k) const
    {
		long mapped = self::char_traits::to_int_type(k);
      state_type result = s + mapped;
      if (result < ml->size())
	if ((*ml)[result] == k)
	  return (1);
      return (0);
    }

    iterator lower_bound(const Key &k) const {
      return (find(k));
    }

    iterator upper_bound(const Key &k) const {
      return (find(k));
    }

    pair<iterator, iterator> equal_range(const Key &k) const
    {
      iterator tmp = find(k);
      return (pair<iterator, iterator>(tmp, ++tmp));
    }
  };

  // Back to DFA_compact class

private:
  mapable_vector<char_type>  letters;
  mapable_vector<state_type> aims;
  mapable_vector<Tag>        tags;
  state_type I;
  unsigned long _state_count;
  unsigned long _trans_count;

#ifndef _MSC_VER
  int fd;        // Memory mapping
#endif
  set_F F;

  bool free_cell(state_type s) const { 
    return (letters[s] == (char_type) 0 && aims[s] == (state_type) 0);
  }

  bool tagged_cell(state_type s) const {
    return (letters[s] == (char_type) 0 && aims[s] != (state_type) 0);
  }

public:
#ifndef _MSC_VER
  static const state_type null_state = 0;
#else
  static const state_type null_state;
#endif

  // Binary save
  ostream& write(ostream &out) const
  { 
    out.write((const char *) &I, sizeof(I));
    out.write((const char *) &_state_count, sizeof(_state_count));
    out.write((const char *) &_trans_count, sizeof(_trans_count));
    letters.write(out);
    aims.write(out);
    tags.write(out);
    F.write(out);
    return out;
  }

  // Binary read
  istream& read(istream &in)
  {
    in.read((char *)&I, sizeof(I));
    in.read((char *)&_state_count, sizeof(_state_count));
    in.read((char *)&_trans_count, sizeof(_trans_count));
    letters.read(in);
    aims.read(in);
    tags.read(in);
    F.read(in);
    return in;
  }

#ifndef _MSC_VER
  // Memory mapping
  bool mmap(const string &path)
  {
    fd = open(path.c_str(), O_RDONLY);
    if (fd == -1) return false;

    return mmap(fd);
  }

  bool mmap(int f)
  {
    ::read(f, (void*) &I, sizeof(I));
    ::read(f, (void*) &_state_count, sizeof(_state_count));
    ::read(f, (void*) &_trans_count, sizeof(_trans_count));

    if (!letters.mmap(f) || !aims.mmap(f) || !tags.mmap(f) || !F.mmap(f))
      return false;
    return true;
  }

  void munmap()
  {
    letters.munmap();
    aims.munmap();
    tags.munmap();
    F.munmap();
  }
#endif

  state_type initial() const { 
    return I; 
  }

  set_F::const_reference final(state_type s) const {
    return F[s];
  }

  state_type delta1(state_type s, const char_type &l) const
  {
	  state_type q = s + self::char_traits::to_int_type(l);
    if (letters[q] == l) return aims[q];
    return null_state;
  }

  unsigned long state_count() const { 
    return _state_count; 
  }

  unsigned long trans_count() const { 
    return _trans_count; 
  }
  
  const Tag& tag(state_type s) const { 
    return tags[aims[s - 1]]; 
  }

  edges_type delta2(state_type s) const { 
    return edges_type(s, letters, aims); 
  }

  const_iterator begin() const
  {
    if (state_count() > 0)
      return const_iterator((state_type) 1, &letters, &aims);
    else
      return end();
  }

  const_iterator end() const {
    return const_iterator(letters.size(), &letters, &aims);
  }

  float density() const
  {
    unsigned long occupied_cells = 0;
    state_type i, fin = letters.size();
    
    for (i = 0; i != fin; ++i)
      if (!free_cell(i))
	++occupied_cells;

    return ((float) occupied_cells / (float) fin);
  }

  void stats(ostream &out = cout) const
  {
    out << "Matrix size       : " << letters.size() << " cells (" 
	<< aims.size() * sizeof(state_type) + letters.size() * sizeof(char_type) +
      tags.size() * sizeof(tag_type) + F.size() * sizeof(bool) << " bytes)" << endl;
    out << "Matrix density    : " << density() << endl;
    out << "States            : " << state_count() << " (" << aims.size() * sizeof(state_type)
	<< " bytes)" << endl;
    out << "Transitions       : " << trans_count() << " (" << letters.size() * sizeof(char_type) 
	<< " bytes)" << endl;
    out << "Tags              : " << tags.size() << " (" << tags.size() * sizeof(tag_type)
	<< " bytes)" << endl;
    out << "Final states bool : " << F.size() << " (" << F.size() * sizeof(bool) 
	<< " bytes)" << endl;
    out << "Space waste ratio : " << (1. - density()) * 100. << "%" << endl;
  }

  ~DFA_compact() {
#ifndef _MSC_VER
    letters.munmap();
    aims.munmap();
    tags.munmap();
    F.munmap();
    if (fd > 0) close(fd);
#endif
  }

  // TEMPORARY CODE:
  DFA_compact()
#ifndef _MSC_VER
    : fd(0)
#endif
  { }

  DFA_compact(istream &in) 
#ifndef _MSC_VER
   : fd(0)
#endif
  {
    read(in);
  }
  
  DFA_compact(const DFA &dfa, long opt_value = 2) 
    : letters((unsigned int) (dfa.state_count() * 2 + dfa.trans_count())), 
      aims((unsigned int) (dfa.state_count() * 2 + dfa.trans_count())), 
      tags((unsigned int) 1), I(null_state), _state_count(0), _trans_count(0),
#ifndef _MSC_VER
      fd(0), 
#endif
      F((unsigned int) dfa.state_count())
  {
    if (dfa.state_count() > 0)
      {
	tag_mapping map_tag;
	typename DFA::const_iterator i, end_i = dfa.end();
	vector<state_type> old2new(dfa.state_count());  // vector indexed by DFA::state_type
	state_type pos, solid_first_free = 0UL, first_free = 0UL;
	typename DFA::edges_type::const_iterator trans, edg_end;
	long count = 0;                // For time optimization of compacting process

	for (i = dfa.begin(); i != end_i; ++i)
	  {
	    ++count;
	    ++_state_count;

	    if (count == opt_value) {  // discard solid_first_free ?
	      for(++solid_first_free; solid_first_free < letters.size() && 
		    !free_cell(solid_first_free); ++solid_first_free);
	      count = 0;
	    }

		while (solid_first_free + self::char_traits::size >= letters.size())   // Matrix is too small
	      {
		// Doubling the size
		letters.resize(2 * letters.size(), (char_type) 0);
		aims.resize(2 * aims.size(), (state_type) 0);
	      }

	    first_free = solid_first_free;

	    while (1)
	      {
		pos = first_free + 1;  // Because we put the tag at first_free
		//		cout << "\t" << pos << endl;
		typename DFA::edges_type edg = dfa.delta2(*i);
		edg_end = edg.end();

		// Trying to put every transition by beginning at pos (first_free)
		for (trans = edg.begin(); trans != edg_end; ++trans)
			if (!free_cell(pos + self::char_traits::to_int_type((*trans).first)))
				break;
	      
		if (trans == edg_end)   // Ok, insert state
		  {
		    //		    cout << "ok insert state" << endl;
		    // Storing new "name" of the state
		    if (old2new.size() <= (unsigned long) *i)
		      old2new.resize((unsigned long) (*i) * 2, null_state);
		    old2new[(unsigned long) *i] = pos;

		    // Putting the tag if not already in vector tags
		    Tag t_tmp = map_tag(dfa.tag(*i));
		    typename mapable_vector<Tag>::iterator position = find(tags.begin() + 1, tags.end(), t_tmp);
		    aims[pos - 1] = (state_type) (position - tags.begin()); 
		    if (position == tags.end()) 
		      tags.push_back(t_tmp);

		    // Put the state in F if needed
		    if (dfa.final(*i))
		      {
			if (F.size() <= pos) F.resize(pos * 2, false);
			F[pos] = true;
		      }

		    // Puting transitions
		    unsigned long mapped_letter;
		    for (trans = edg.begin(); trans != edg_end; ++trans)
		      {
				mapped_letter = self::char_traits::to_int_type((*trans).first);
			letters[pos + mapped_letter] = (*trans).first;
			aims[pos + mapped_letter] = (state_type) (*trans).second;
			++_trans_count;
		      }
		    if (first_free == solid_first_free)
		      count = opt_value - 1;        // Force solid_first_free updating
		    break;    // move on to the next state
		  }

		// first_free is updated
		for(++first_free; first_free < letters.size() && !free_cell(first_free); ++first_free);

		while (first_free + self::char_traits::size >= letters.size())   // Matrix is too small
		  {
		    // Doubling the size
		    letters.resize(2 * letters.size(), (char_type) 0);
		    aims.resize(2 * aims.size(), (state_type) 0);
		  }
	      }
	  }
	
	// Setting edges aim to states new "names"
	state_type last_one = 0;
	for (pos = 0; pos != letters.size(); ++pos)
	  if (letters[pos] != (char_type) 0)
	    aims[pos] = old2new[aims[pos]];
	  else
	    if (aims[pos] != 0) // letter == 0, aim != 0 => aim is a tag index
			last_one = pos + 1 + self::char_traits::size;

	if (dfa.initial() != dfa.null_state)
	  I = old2new[(unsigned long) dfa.initial()];
	letters.resize(last_one + 1, (char_type) 0);
	aims.resize(last_one + 1, (state_type) 0);
	F.resize(last_one + 1, false);
      }
  }
};

#ifndef _MSC_VER
template <typename DFA, typename TagMapping>
const typename DFA_compact<DFA, TagMapping>::state_type 
DFA_compact<DFA, TagMapping>::null_state;
#else
template <typename DFA, typename TagMapping>
const typename DFA_compact<DFA, TagMapping>::state_type 
DFA_compact<DFA, TagMapping>::null_state = 0;
#endif

ASTL_END_NAMESPACE

#endif   // ASTL_DFA_COMPACT_H