dfa.h

Go to the documentation of this file.

#ifndef REG_DFA_H
#define REG_DFA_H

#include <memory>

#include <vector>

#include <valarray>

#include <string>

#include <locale>

#include <codecvt>

namespace reg {
class nfa;

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

  bool operator==(const dfa& d) const;
  bool operator!=(const dfa& d) const;
  size_t delta(size_t qi, size_t si) const;
  size_t delta(size_t qi, char32_t symbol) const;
  size_t delta(size_t qi, std::string const& utf8Symbol) const;
  std::string const& delta(std::string const& q, char32_t symbol) const;
  std::string const& delta(std::string const& q, std::string const& utf8Symbol) const;
  size_t deltaHat(size_t qi, std::u32string const& word) const;
  size_t deltaHat(size_t qi, std::string const& utf8Word) const;
  std::string const& deltaHat(std::string const& q, std::u32string const& word) const;
  std::string const& deltaHat(std::string const& q, std::string const& utf8Word) const;
  std::u32string getShortestWord() const;
  std::string getShortestUtf8Word() const;
  std::string const& getLabelOf(size_t qi) const;
  std::string const& getInitialState() const;
  std::vector<std::string> const& getStates() 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;
  static dfa::builder unite(dfa const& d1, dfa const& d2);
  static dfa::builder intersect(dfa const& d1, dfa const& d2);
  static dfa::builder subtract(dfa const& d1, dfa const& d2);
  static dfa::builder complement(dfa const& d);
  friend std::u32string findShortestWord(dfa const& d);
  friend std::string findShortestUtf8Word(dfa const& d);

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

    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& defineTransition(std::string const& from, std::string const& to, char32_t symbol);
    builder& defineTransition(std::string const& from, std::string const& to, std::string const& utf8Symbol);
    builder& merge();
    builder& purge();
    builder& minimize();
    builder& unite(dfa const& other);
    builder& intersect(dfa const& other);
    builder& complement();
    builder& normalizeStateNames(std::string const& prefix);
    dfa build();
  private:
    struct pImpl;
    std::unique_ptr<pImpl> p;
  };
private:
  struct pImpl;
  std::unique_ptr<pImpl> p;
  dfa(
    std::vector<char32_t>& alphabet,
    std::vector<std::vector<size_t>>& transitions,
    std::vector<std::string>& labels,
    std::valarray<bool>& acceptingStates
  );
};
std::u32string findShortestWord(dfa const& d);
std::string findShortestUtf8Word(dfa const& d);


template<class C,class T> size_t index_of(C const& container, T const& element) {
  static_assert(std::is_same<typename C::value_type,T>::value, "C must be a container with T as value_type.");
  return static_cast<size_t>(std::distance(container.begin(), std::find(container.begin(), container.end(), element)));
}

extern std::wstring_convert<std::codecvt_utf8<char32_t>,char32_t> converter; 
} // namespace reg

#endif