nfa.h

Go to the documentation of this file.

#ifndef REG_NFA_H
#define REG_NFA_H

#include <vector>

#include <valarray>

#include <string>

#include "utils.h"

namespace reg {

class dfa;

class nfa {
public:
  struct hash_reference_string_const;
  struct equal_to_reference_string_const ;
  typedef std::unordered_set<std::reference_wrapper<std::string const>, hash_reference_string_const, equal_to_reference_string_const> state_set;
  class builder;
  nfa();
  nfa(nfa const& n);
  nfa(nfa&& n);
  nfa& operator=(nfa const& n);
  nfa& operator=(nfa&& n);
  virtual ~nfa ();

  operator dfa const&() const; 
  bool operator==(nfa const& n) const;
  bool operator!=(nfa const& n) const;
  std::valarray<bool> const& delta(size_t qi, size_t si) const;
  std::valarray<bool> const& delta(size_t qi, char32_t symbol) const;
  std::valarray<bool> const& delta(size_t qi, std::string const& utf8Symbol) const;
  state_set delta(std::string const& q, char32_t symbol) const;
  state_set delta(std::string const& q, std::string const& utf8Symbol) const;
  std::valarray<bool> deltaHat(size_t qi, std::u32string const& word) const;
  std::valarray<bool> deltaHat(size_t qi, std::string const& utf8Word) const;
  state_set deltaHat(std::string const& q, std::u32string const& word) const;
  state_set deltaHat(std::string const& q, std::string const& utf8Word) const;
  std::valarray<bool> deltaHat(std::valarray<bool> const& qs, std::u32string const& word) const;
  std::valarray<bool> deltaHat(std::valarray<bool> const& qs, std::string const& utf8Word) const;
  state_set deltaHat(state_set const& qs, std::u32string const& word) const;
  state_set deltaHat(state_set const& qs, std::string const& utf8Word) const;
  std::valarray<bool> const& epsilonClosure(size_t qi) const;
  state_set epsilonClosure(std::string const& q) const;
  std::valarray<bool> epsilonClosure(std::valarray<bool> const& qs) const;
  state_set epsilonClosure(state_set const& qs) const;
  std::u32string getShortestWord() const;
  std::string getShortestUtf8Word() const;
  std::string const& getLabelOf(size_t q) const;
  std::string getLabelOf(std::valarray<bool> const& qs) const;
  std::string getLabelOf(state_set const& qs) const;
  std::string to_string(std::valarray<bool> const& qs) const;
  std::string to_string(state_set const& qs) const;
  state_set decodeSet(std::valarray<bool> const& qs) const;
  std::valarray<bool> encodeSet(state_set const& qs) const;
  std::string const& getInitialState() const;
  std::vector<std::string> const& getStates() const;
  state_set getStatesSet() const;
  std::valarray<bool> getStatesBools() const;
  std::vector<char32_t> const& getAlphabet() const;
  std::vector<std::string> const& getUtf8Alphabet() const;
  size_t getNumberOfStates() const;
  size_t getNumberOfSymbols() const;
  bool isAccepting(size_t qi) const;
  bool isAccepting(std::string const& q) const;
  bool isAccepting(std::valarray<bool> const& qs) const;
  bool isAccepting(state_set const& qs) const;
  bool hasAccepting(std::valarray<bool> const& qs) const;
  bool hasAccepting(state_set const& qs) const;
  static nfa::builder unite(nfa const& n1, nfa const& n2);
  static nfa::builder intersect(nfa const& n1, nfa const& n2);
  static nfa::builder subtract(nfa const& n1, nfa const& n2);
  static nfa::builder complement(nfa const& n);
  friend std::u32string findShortestWord(nfa const& n);
  friend std::string findShortestUtf8Word(nfa const& n);

  class builder {
  public:
    builder();
    builder(nfa const& nfa);
    builder(dfa const& dfa);
    builder(builder const& b);
    builder(builder&& b);
    builder& operator=(builder const& b);
    builder& operator=(builder&& b);
    virtual ~builder ();

    operator nfa();
    builder& addSymbol(char32_t symbol);
    builder& addSymbol(std::string const& utf8Symbol);
    builder& setAccepting(std::string const& state, bool accept);
    builder& makeInitial(std::string const& state);
    builder& addTransition(std::string const& from, std::string const& to, char32_t symbol);
    builder& addTransition(std::string const& from, std::string const& to, std::string const& utf8Symbol);
    builder& unite(nfa const& other);
    builder& intersect(nfa const& other);
    builder& normalizeStateNames(std::string const& prefix);
    nfa build();
  private:
    struct pImpl;
    std::unique_ptr<pImpl> p;
  };
  struct hash_reference_string_const {
    size_t operator()(std::reference_wrapper<std::string const> const& ref) const {
      return std::hash<std::string>()(ref.get());
    }
  };
  struct equal_to_reference_string_const {
    bool operator()(std::reference_wrapper<std::string const> const& lhs, std::reference_wrapper<std::string const> const& rhs) const {
      return lhs.get() == rhs.get();
    }
  };
private:
  struct pImpl;
  std::unique_ptr<pImpl> p;
  nfa(
      std::vector<char32_t>& alphabet,
      std::vector<std::vector<std::valarray<bool>>>& transitions,
      std::vector<std::string>& labels,
      std::valarray<bool>& acceptingStates
    );
};
std::u32string findShortestWord(nfa const& n);
std::string findShortestUtf8Word(nfa const& n);
} // namespace reg

#endif