dfa.H

/*
 * This file is part of the "Archon" framework.
 * (http://files3d.sourceforge.net)
 *
 * Copyright © 2002 by Kristian Spangsege and Brian Kristiansen.
 *
 * Permission to use, copy, modify, and distribute this software and
 * its documentation under the terms of the GNU General Public License is
 * hereby granted. No representations are made about the suitability of
 * this software for any purpose. It is provided "as is" without express
 * or implied warranty. See the GNU General Public License
 * (http://www.gnu.org/copyleft/gpl.html) for more details.
 *
 * The characters in this file are ISO8859-1 encoded.
 *
 * The documentation in this file is in "Doxygen" style
 * (http://www.doxygen.org).
 */

#ifndef ARCHON_UTILITIES_DFA_H
#define ARCHON_UTILITIES_DFA_H

#include <string>
#include <vector>
#include <set>
#include <iostream>

#include <archon/util/exception.H>
#include <archon/util/unicode.H>

namespace Archon
{
  namespace Utilities
  {
    using namespace std;

    struct NFA;

    class DFA
    {
      friend class NFA;

    public:
      struct State;

      class Edge
      {
        friend class DFA;
        friend class State;

        unsigned begin;
        unsigned end; // inclusive
        int targetState;
        Edge(unsigned begin, unsigned end, int targetState):
          begin(begin), end(end), targetState(targetState) {}

        struct Cmp
        {
          bool operator()(const Edge &e1, unsigned e2) const
          {
            return e1.begin < e2;
          }
        };

      public:
        unsigned getBegin() const { return begin; }
        unsigned getEnd() const { return end; }
        int getTargetState() const { return targetState; }
      };

      class State
      {
        friend class DFA;

        int finalValue; // -1 for non-final
        vector<Edge> edges;
        State(int finalValue): finalValue(finalValue) {}

      public:
        int getFinalValue() const { return finalValue; }
        int getNumberOfEdges() const { return edges.size(); }
        const Edge &getEdge(int i) const { return edges[i]; }

        int step(unsigned symbol) const
        {
          // Do binary search
          vector<Edge>::const_iterator i =
            lower_bound(edges.begin(), edges.end(), symbol, Edge::Cmp());
          if(i != edges.end() && i->begin == symbol) return i->targetState;
          if(i != edges.begin() && (i-1)->end >= symbol)
            return (i-1)->targetState;
          return -1;
        }
      };

    private:
      // Making this a vector of vectors might a bad thing, since a
      // resize of states might copy all sub-vectors.
      vector<State> states;
      vector<int> startStates; // State indices

      bool testEquivalence(int s1, int s2, const vector<int> &partitionMap) const;
      void minimize(DFA *) const;
      void makeNFA(NFA *) const;

      int addStartState(int finalValue = -1);

      int addState(int finalValue = -1);

      void addEdgeRange(unsigned begin, unsigned end,
                        int originalState, int targetState);

    public:
      struct AnchorInfo
      {
        unsigned start;
        unsigned numberOf;
        AnchorInfo(unsigned start, unsigned numberOf):
          start(start), numberOf(numberOf) {}
      };

      DFA(const NFA &, vector<set<int> > *stateSets=0, AnchorInfo *anchorInfo=0);

      struct Minimize
      {
        const DFA &a;
        Minimize(const DFA &a): a(a) {}
      };

      DFA(Minimize);

      int getNumberOfStates() const { return states.size(); }
      const State &getState(int i) const { return states[i]; }

      struct Printer
      {
        virtual string printSymbol(unsigned) const = 0;
        virtual ~Printer() {}
      };

      static const Printer &getDefaultPrinter();

      string print(const Printer &printer = getDefaultPrinter(), int width = 0) const;
    };
  }
}

#endif // ARCHON_UTILITIES_DFA_H

---