gnfa.cpp

Go to the documentation of this file.

#include "gnfa.h"
using std::vector;
using std::pair;
using std::string;

#include <unordered_map>
using std::unordered_map;

#include <functional>
using std::reference_wrapper;

#include <forward_list>
using std::forward_list;

#include "nfa.h"
#include "dfa.h"

namespace reg {

struct gnfa::pImpl {
  std::shared_ptr<nfa const> mutable equivalent;
  unordered_map<string,unordered_map<string,expression::exptr>> transitions;
  string initial;
  string accepting;

  pImpl() : initial("p0"), accepting("pF") {
    transitions[initial];
    transitions[accepting];
  }

  pImpl(unordered_map<string,unordered_map<string,expression::exptr>>& transitionMap,
      string const& initialState,
      forward_list<reference_wrapper<string const>>& acceptingStates,
      nfa const* eq) : equivalent(eq), transitions(move(transitionMap)) {
    initial = generateState('p',  '0');
    auto const& epsilon = expression::spawnEmptyString();
    transitions[initial][initialState] = epsilon;
    accepting = generateState('p', 'F');
    for (string const& a : acceptingStates) {
      transitions[a][accepting] = epsilon;
    }
  }


  expression::exptr const& getTransition(string const& qLabel, string const& pLabel) const {
    auto const& from = transitions.at(qLabel);
    auto reIt = from.find(pLabel);
    if (reIt == from.end() || !reIt->second) {
      return expression::spawnEmptySet();
    }
    return reIt->second;
  }


  void addTransition(string const& qLabel, string const& pLabel, expression::exptr re, bool optimized = true, bool aggressive = false) {
    transitions[qLabel][pLabel] = expression::spawnAlternation(getTransition(qLabel, pLabel), re, optimized, aggressive);
  }


  string const& generateState(char prefix = 'q', char suffix = '\0') {
    string state;
    if (suffix == '\0') {
      state = string(1, prefix).append(std::to_string(0));
      for (size_t q(1); transitions.count(state) != 0; q++) {
        state = string(1, prefix).append(std::to_string(q));
      }
    } else {
      for (state = string(1, prefix).append(1, suffix);
          transitions.count(state) != 0;
          state.append(1, suffix)
        ) {}
    }
    return transitions.insert(std::make_pair(state, unordered_map<string, expression::exptr>())).first->first;
  }
};


gnfa::gnfa(dfa const& d) {
  unordered_map<string,unordered_map<string,expression::exptr>> transitions(d.getNumberOfStates()+2);
  forward_list<reference_wrapper<string const>> acceptingStates;
  for (size_t qi(0); qi < d.getNumberOfStates(); qi++) {
    auto const& qLabel = d.getLabelOf(qi);
    auto& entry = transitions[qLabel];
    if (d.isAccepting(qi)) {
      acceptingStates.push_front(qLabel);
    }
    for (size_t si(0); si < d.getNumberOfSymbols(); si++) {
      char32_t symbol = d.getAlphabet()[si];
      size_t pi = d.delta(qi, si);
      auto& dest = entry[d.getStates()[pi]];
      if (!dest) {
        dest = expression::spawnSymbol(symbol);
      } else {
        dest = expression::spawnAlternation(dest, expression::spawnSymbol(symbol));
      }
    }
  }
  p = std::make_unique<pImpl>(transitions, d.getLabelOf(0), acceptingStates, new nfa(d));
}


gnfa::gnfa(nfa const& n) {
  unordered_map<string,unordered_map<string,expression::exptr>> transitions(n.getNumberOfStates()+2);
  forward_list<reference_wrapper<string const>> acceptingStates;
  for (size_t qi(0); qi < n.getNumberOfStates(); qi++) {
    auto const& qLabel = n.getLabelOf(qi);
    auto& entry = transitions[qLabel];
    if (n.isAccepting(qi)) {
      acceptingStates.push_front(qLabel);
    }
    for (auto const& symbol : n.getAlphabet()) {
      auto& pSet = n.delta(qi, symbol);
      for (size_t pi(0); pi < pSet.size(); pi++) {
        if (pSet[pi]) {
          auto& dest = entry[n.getLabelOf(pi)];
          if (!dest) {
            dest = expression::spawnSymbol(symbol);
          } else {
            dest = expression::spawnAlternation(dest, expression::spawnSymbol(symbol));
          }
        }
      }
    }
  }
  p = std::make_unique<pImpl>(transitions, n.getLabelOf(0), acceptingStates, new nfa(n));
}


gnfa::gnfa(expression::exptr r) : p(new pImpl) {
  p->transitions[p->initial][p->accepting] = r;
}

gnfa::gnfa(expression const& r) : p(new pImpl) {
  switch (r.getOperation()) {
    case expression::operation::alternation :
    p->transitions[p->initial][p->accepting] = expression::spawnAlternation(*r.begin(), *(r.begin()+1));
    break;
    case expression::operation::concatenation :
    p->transitions[p->initial][p->accepting] = expression::spawnConcatenation(*r.begin(), *(r.begin()+1));
    break;
    case expression::operation::kleene :
    p->transitions[p->initial][p->accepting] = expression::spawnKleene(*r.begin());
    break;
    case expression::operation::symbol :
    p->transitions[p->initial][p->accepting] = expression::spawnSymbol(r.extractSymbol());
    break;
    case expression::operation::empty :
    p->transitions[p->initial][p->accepting] = expression::spawnEmptySet();
    break;
  }
}

string const& gnfa::getInitialState() const {
  return p->initial;
}

string const& gnfa::getAcceptingState() const {
  return p->accepting;
}

vector<reference_wrapper<string const>> gnfa::getActiveStates() const {
  vector<reference_wrapper<string const>> active;
  for (auto const& entry : p->transitions) {
    if (entry.first != p->initial && entry.first != p->accepting) {
      active.push_back(std::cref(entry.first));
    }
  }
  return active;
}

expression::exptr gnfa::getTransition(string const& qLabel, string const& pLabel) const {
  return p->getTransition(qLabel, pLabel);
}


vector<pair<reference_wrapper<string const>, reference_wrapper<string const>>> gnfa::getSplittableTransitions() const {
  vector<pair<reference_wrapper<string const>, reference_wrapper<string const>>> splittable;
  splittable.reserve(p->transitions.size()*p->transitions.size());
  for (pair<string const, unordered_map<string, expression::exptr>> const& from : p->transitions) {
    for (pair<string const, expression::exptr> const& to : from.second) {
      if (to.second && to.second->getOperation() > expression::operation::symbol) {
        splittable.push_back(std::make_pair(std::ref(from.first), std::ref(to.first)));
      }
    }
  }
  splittable.shrink_to_fit();
  return splittable;
}


vector<reference_wrapper<string const>> gnfa::splitTransition(string const& qLabel, string const& pLabel) {
  vector<reference_wrapper<string const>> newStates;
  auto const& re = p->getTransition(qLabel, pLabel);
  switch (re->getOperation()) {
    case expression::operation::alternation : {
      auto sub1 = *(re->begin());
      auto sub2 = *(re->begin()+1);
      p->transitions[qLabel][pLabel] = expression::spawnEmptySet();
      newStates.reserve(4);
      for (size_t i(0); i < 4; i++) {
        newStates.push_back(p->generateState());
      }
      auto const& epsilon = expression::spawnEmptyString();
      p->transitions[qLabel][newStates[0]] = epsilon;
      p->transitions[newStates[0]][newStates[1]] = sub1;
      p->transitions[newStates[1]][pLabel] = epsilon;
      p->transitions[qLabel][newStates[2]] = epsilon;
      p->transitions[newStates[2]][newStates[3]] = sub2;
      p->transitions[newStates[3]][pLabel] = epsilon;
      break;
    }
    case expression::operation::concatenation : {
      auto sub1 = *(re->begin());
      auto sub2 = *(re->begin()+1);
      p->transitions[qLabel][pLabel] = expression::spawnEmptySet();
      newStates.reserve(2);
      for (size_t i(0); i < 2; i++) {
        newStates.push_back(p->generateState());
      }
      p->transitions[qLabel][newStates[0]] = sub1;
      p->transitions[newStates[0]][newStates[1]] = expression::spawnEmptyString();
      p->transitions[newStates[1]][pLabel] = sub2;
      break;
    }
    case expression::operation::kleene : {
      auto sub = *(re->begin());
      auto const& epsilon = expression::spawnEmptyString();
      p->transitions[qLabel][pLabel] = epsilon;
      newStates.reserve(2);
      for (size_t i(0); i < 2; i++) {
        newStates.push_back(p->generateState());
      }
      p->transitions[qLabel][newStates[0]] = epsilon;
      p->transitions[newStates[1]][pLabel] = epsilon;
      p->transitions[newStates[1]][newStates[0]] = epsilon;
      p->transitions[newStates[0]][newStates[1]] = sub;
      break;
    }
    case expression::operation::symbol :
    case expression::operation::empty :
    ;
  }
  return newStates;
}


nfa gnfa::splitAllTransitions() {
  for (auto splittable = getSplittableTransitions(); !splittable.empty(); splittable = getSplittableTransitions()) {
    for (auto const& nodes : splittable) {
      splitTransition(nodes.first, nodes.second);
    }
  }
  nfa::builder b;
  auto const& empty = expression::spawnEmptySet();
  for (auto const& from : p->transitions) {
    for (auto const& to : from.second) {
      if (to.second != empty) {
        b.addTransition(from.first, to.first, to.second->extractSymbol());
      }
    }
  }
  b.makeInitial(p->initial);
  b.setAccepting(p->accepting, true);
  return b.build();
}

void gnfa::bypassTransition(string const& qLabel, string const& pLabel) {
  auto const& re = p->getTransition(qLabel, pLabel);
  if (re == expression::spawnEmptySet()) {
    return;
  }
  auto const& selfRe = p->getTransition(qLabel, qLabel);
  for (auto const& from : p->transitions) {
    if (from.first != qLabel) {
      auto to = from.second.find(qLabel);
      if (to != from.second.end() && to->second) {
        p->addTransition(
            from.first,
            pLabel,
            expression::spawnConcatenation(
                to->second,
                expression::spawnConcatenation(
                    expression::spawnKleene(selfRe),
                    re
                )
            )
        );
      }
    }
  }
  p->transitions[qLabel].erase(pLabel);
}

void gnfa::ripState(string const& qLabel) {
  forward_list<reference_wrapper<string const>> right;
  for (auto const& to : p->transitions[qLabel]) {
    right.push_front(to.first);
  }
  for (auto const& to : right) {
    if (to.get() != qLabel) {
      bypassTransition(qLabel, to);
    }
  }
  for (auto& from : p->transitions) {
    from.second.erase(qLabel);
  }
  p->transitions.erase(qLabel);
}


expression::exptr gnfa::ripAllStates() {
  for (auto const& rippable : getActiveStates()) {
    ripState(rippable);
  }
  return getTransition(getInitialState(), getAcceptingState());
}

gnfa::gnfa(gnfa const& n) : p(new pImpl(*(n.p))) {}


gnfa::gnfa(gnfa&& n) : p(new pImpl) {p.swap(n.p);}

#ifndef DOXYGEN_SHOULD_SKIP_THIS
gnfa::operator nfa const&() const {
  if (!p->equivalent) {
    p->equivalent = std::make_shared<nfa const>(gnfa(*this).splitAllTransitions());
  }
  return *p->equivalent;
}
#endif // DOXYGEN_SHOULD_SKIP_THIS


bool gnfa::operator==(nfa const& other) const {
  return other.operator==(*this);
}


bool gnfa::operator!=(nfa const& other) const {
  return !operator==(other);
}

gnfa& gnfa::operator=(gnfa const& n) {
  if (this != &n) {
    p.reset(new pImpl(*(n.p)));
  }
  return *this;
}


gnfa& gnfa::operator=(gnfa&& n) {
  if (this != &n) {
    p.reset(new pImpl);
    p.swap(n.p);
  }
  return *this;
}

gnfa::~gnfa() = default;
}