dfa.C

/*
 * 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).
 */

#include <stack>
#include <map>
#include <list>
#include <algorithm>

#include <archon/util/text.H>
#include <archon/util/nfa.H>

#include <archon/util/dfa.H>

using namespace std;

namespace Archon
{
  namespace Utilities
  {
    bool DFA::testEquivalence(int s1, int s2, const vector<int> &partitionMap) const
    {
      const State &state1 = states[s1];
      const State &state2 = states[s2];

      vector<Edge>::const_iterator e1 = state1.edges.begin();
      vector<Edge>::const_iterator e2 = state2.edges.begin();

      while(e1 != state1.edges.end() || e2 != state2.edges.end())
      {
        if(e2 == state2.edges.end())
        {
          if(partitionMap[e1->targetState]) return false;
          ++e1;
          continue;
        }

        if(e1 == state1.edges.end())
        {
          if(partitionMap[e2->targetState]) return false;
          ++e2;
          continue;
        }

        if(e1->begin < e2->begin)
        {
          if(partitionMap[e1->targetState]) return false;

          if(e1->end < e2->begin)
          {
            ++e1;
            continue;
          }
        }
        else if(e1->begin > e2->begin)
        {
          if(partitionMap[e2->targetState]) return false;

          if(e1->begin > e2->end)
          {
            ++e2;
            continue;
          }
        }

        for(;;)
        {
          if(partitionMap[e1->targetState] !=
             partitionMap[e2->targetState]) return false;

          if(e1->end < e2->end)
          {
            const unsigned u = e1->end;
            ++e1;
            if(e1 == state1.edges.end() || u < e1->begin-1) break;
          }
          else if(e1->end > e2->end)
          {
            const unsigned u = e2->end;
            ++e2;
            if(e2 == state2.edges.end() || u < e2->begin-1) break;
          }
          else
          {
            ++e1;
            ++e2;
            break;
          }
        }
      }

      return true;
    }

    void DFA::minimize(DFA *targetDFA) const
    {
      vector<int> partitionMap(states.size());

      // Construct the initial partitioning
      {
        map<int, int> m;
        m.insert(make_pair(-1, 0)).first->second;
        for(unsigned i=0; i<states.size(); ++i)
        {
          const int r = states[i].finalValue;
          partitionMap[i] = m.insert(make_pair(r < 0 ? -1 : r, m.size())).first->second;
        }
      }

      bool again;

      do
      {
        again = false;

        // Gather the states of each partition
        map<int, list<int> > partitions;
        for(unsigned i=0; i<partitionMap.size(); ++i)
          partitions[partitionMap[i]].push_back(i);

        // First partition (index 0) is always the dead one (the one
        // containing the virtual dead state)
        int newPartitionIndex = 1;

        // Subdivide each partition
        for(map<int, list<int> >::iterator i=partitions.begin();
            i!=partitions.end(); ++i)
        {
          list<int> &p = i->second;

          // Handle the dead partition
          if(i->first == 0)
          {
            list<int>::iterator j1=p.begin();
            while(j1 != p.end())
            {
              list<int>::iterator j2 = j1;
              ++j1;

              const vector<Edge> &e = states[*j2].edges;
              vector<Edge>::const_iterator i=e.begin();
              while(i!=e.end())
              {
                if(partitionMap[i->targetState]) break;
                ++i;
              }
              if(i!=e.end())
              {
                again = true;
                continue;
              }

              partitionMap[*j2] = 0;

              p.erase(j2);
            }
          }

          while(p.size())
          {
            int s = p.front();
            p.pop_front();

            list<int>::iterator j1=p.begin();
            while(j1 != p.end())
            {
              list<int>::iterator j2 = j1;
              ++j1;

              if(!testEquivalence(s, *j2, partitionMap))
              {
                again = true;
                continue;
              }

              partitionMap[*j2] = newPartitionIndex;

              p.erase(j2);
            }

            partitionMap[s] = newPartitionIndex;
            ++newPartitionIndex;
          }
        }
      }
      while(again);

      // Construct the new minimized DFA from the reachable partitions
      // of the old one.
      {
        map<int, int> newStateMap; // Maps partition index to new state index
        stack<int> uncheckedStates;

        // Add a new start state for each unique start partition
        for(unsigned i=0; i<startStates.size(); ++i)
        {
          const int s = startStates[i];
          pair<map<int, int>::iterator, bool> r =
            newStateMap.insert(make_pair(partitionMap[s], i));
          if(r.second)
          {
            targetDFA->startStates.push_back(targetDFA->states.size());
            targetDFA->states.push_back(State(states[s].finalValue));
            uncheckedStates.push(s);
          }
        }

        while(uncheckedStates.size())
        {
          const int s = uncheckedStates.top();
          uncheckedStates.pop();
          const int f = newStateMap[partitionMap[s]];
          const vector<Edge> &v = states[s].edges;
          for(vector<Edge>::const_iterator e=v.begin(); e<v.end(); ++e)
          {
            const int p = partitionMap[e->targetState];
            if(!p) continue; // Dont ever jump to the dead partition
            pair<map<int, int>::iterator, bool> r =
              newStateMap.insert(make_pair(p, targetDFA->states.size()));
            if(r.second)
            {
              targetDFA->states.push_back(State(states[e->targetState].finalValue));
              uncheckedStates.push(e->targetState);
            }
            vector<Edge> &w = targetDFA->states[f].edges;
            if(w.size() && w.back().end == e->begin-1 &&
               w.back().targetState == r.first->second) w.back().end = e->end;
            else w.push_back(Edge(e->begin, e->end, r.first->second));
          }
        }
      }
    }

    void DFA::makeNFA(NFA *a) const
    {
      a->states.resize(states.size());
      for(unsigned i=0; i<states.size(); ++i)
      {
        const State &s = states[i];
        NFA::State &t = a->states[i];
        t.finalValue = s.finalValue;
        t.symbolEdges.reserve(s.edges.size());
        for(unsigned j=0; j<s.edges.size(); ++j)
        {
          const Edge &e = s.edges[j];
          t.symbolEdges.push_back(NFA::Edge(e.begin, e.end, e.targetState));
        }
      }
      a->startStates = startStates;
    }

    int DFA::addStartState(int finalValue)
    {
      startStates.push_back(states.size());
      return addState(finalValue);
    }

    int DFA::addState(int finalValue)
    {
      states.push_back(State(finalValue));
      return states.size()-1;
    }

    void DFA::addEdgeRange(unsigned begin, unsigned end,
                           int originalState, int targetState)
    {
      states[originalState].edges.push_back(Edge(begin, end, targetState));
    }

    DFA::DFA(const NFA &nfa, vector<set<int> > *stateSets, AnchorInfo *anchorInfo)
    {
      if(!nfa.states.size())
        ARCHON_THROW1(ArgumentException, "Cannot create a DFA from a null NFA");
      nfa.constructDFA(this, stateSets, anchorInfo);
    }

    DFA::DFA(Minimize m)
    {
      m.a.minimize(this);
    }

    struct DefaultPrinter: DFA::Printer
    {
      string printSymbol(unsigned s) const
      {
        return Text::toString(s);
      }
    };

    const DFA::Printer &DFA::getDefaultPrinter()
    {
      static DefaultPrinter defaultPrinter;
      return defaultPrinter;
    }

    string DFA::print(const Printer &printer, int width) const
    {
      vector<double> columnWidthFractions;
      columnWidthFractions.push_back(0.1);
      columnWidthFractions.push_back(0.1);
      columnWidthFractions.push_back(0.8);
      Text::Table<string> table(states.size()+1, columnWidthFractions);
      table(0, 0) = "State";
      table(0, 1) = "Final";
      table(0, 2) = "DFA-transitions";
      for(unsigned i=0; i<states.size(); ++i)
      {
        const State &s = states[i];
        table(i+1, 0) = Text::toString(i);
        if(find(startStates.begin(), startStates.end(), static_cast<int>(i))!=startStates.end())
          table(i+1, 0) += "*";
        if(s.finalValue >= 0) table(i+1, 1) = Text::toString(s.finalValue);
        for(unsigned j=0; j<s.edges.size(); ++j)
        {
          if(j) table(i+1, 2) += ", ";
          const Edge &e = s.edges[j];
          table(i+1, 2) += "'" + printer.printSymbol(e.begin) + "'";
          if(e.begin < e.end)
            table(i+1, 2) += "-'" + printer.printSymbol(e.end) + "'";
          table(i+1, 2) += " -> " + Text::toString(e.targetState);
        }
      }

      return Text::format(table, width, 2, true);      
    }
  }
}

---