reg::dfa::builder::pImpl Struct Reference

Private implementation details of DFA builders. More...

Classes
struct	ValarrayBoolEqual
	Comparison object for valarray<bool>s, so they can be used as unordered_set keys. More...
struct	ValarrayBoolEqualTo
	Comparison object for valarray<bool>s against a specific instance. More...
struct	ValarrayBoolHasher
	Hasher object for valarray<bool>s, so they can be used as unordered_set keys. More...

Public Member Functions
	pImpl ()=default
	Constructs empty private implementation object. More...
	pImpl (string &initial, unordered_set< char32_t > &alphabet, unordered_set< string > &acceptingStates, Dtransitionmap &transitions)
	Constructs private implementation object with provided members. More...
bool	isTrashState (string const &q) const
	Tests whether all of a state's outgoing transitions point to itself. More...
string const &	generateNewState ()
	Generates a uniquely named new state and adds it to the set of states. More...
void	complete ()
	Totalizes a partial transition function by pointing any undefined transitions towards a trash state. More...

Static Public Member Functions
static bool	valarrayFullTrue (valarray< bool > const &a)
	Tests whether all of a valarray<bool>'s entries are true. More...

Public Attributes
string	initial
	Name of the prospective DFA's initial state. More...
unordered_set< char32_t >	alphabet
	Set of symbols processable by the prospective DFA. More...
unordered_set< string >	acceptingStates
	Set of names of the prospective DFA's accept states. More...
Dtransitionmap	transitions
	Transition function (state × symbol → state) of the prospective DFA. More...

Detailed Description

Private implementation details of DFA builders.

Definition at line 383 of file dfa.cpp.

Constructor & Destructor Documentation

pImpl() [1/2]

reg::dfa::builder::pImpl::pImpl ( )

default

Constructs empty private implementation object.

pImpl() [2/2]

reg::dfa::builder::pImpl::pImpl ( string &  initial, unordered_set< char32_t > &  alphabet, unordered_set< string > &  acceptingStates, Dtransitionmap &  transitions  )

inline

Constructs private implementation object with provided members.

Definition at line 395 of file dfa.cpp.

      : initial(move(initial)),
        alphabet(move(alphabet)),
        acceptingStates(move(acceptingStates)),
        transitions(move(transitions)) {}

Member Function Documentation

complete()

void reg::dfa::builder::pImpl::complete ( )

inline

Totalizes a partial transition function by pointing any undefined transitions towards a trash state.

If there is no state satisfying trashiness, a new one will be generated.

Definition at line 435 of file dfa.cpp.

                  {
    bool trashUsed(false);
    string const& trashState = [&]{
      for (auto const& entry : this->transitions) {
        if (this->isTrashState(entry.first)) {
          trashUsed = true;
          return entry.first;
        }
      }
      return this->generateNewState();
    }();
    for (auto& from : transitions) {
      for (char32_t symbol : alphabet) {
        if (from.second.find(symbol) == from.second.end()) {
          from.second[symbol] = trashState;
          trashUsed |= (from.first != trashState);
        }
      }
    }
    if (!trashUsed) {
      transitions.erase(trashState);
    }
  }

generateNewState()

string const& reg::dfa::builder::pImpl::generateNewState ( )

inline

Generates a uniquely named new state and adds it to the set of states.

Definition at line 421 of file dfa.cpp.

                                   {
    size_t q(0);
    string newState;
    while (transitions.find(newState = string("q").append(std::to_string(q))) != transitions.end()) {
      q++;
    }
    if (transitions.empty()) {
      initial = newState;
    }
    return transitions.insert(std::make_pair(newState, unordered_map<char32_t, string>())).first->first;
  }

isTrashState()

bool reg::dfa::builder::pImpl::isTrashState ( string const &  q ) const

inline

Tests whether all of a state's outgoing transitions point to itself.

Definition at line 406 of file dfa.cpp.

                                            {
    if (acceptingStates.count(q) != 0) {
      return false;
    }
    auto const& from = transitions.at(q);
    for (char32_t symbol : alphabet) {
      auto via = from.find(symbol);
      if (via != from.end() && (*via).second != q) {
        return false;
      }
    }
    return true;
  }

valarrayFullTrue()

static bool reg::dfa::builder::pImpl::valarrayFullTrue ( valarray< bool > const &  a )

inlinestatic

Tests whether all of a valarray<bool>'s entries are true.

Definition at line 472 of file dfa.cpp.

                                                        {
    bool fullTrue = true;
    for (bool b : a) {
      fullTrue &= b;
    }
    return fullTrue;
  }

Member Data Documentation

acceptingStates

unordered_set<string> reg::dfa::builder::pImpl::acceptingStates

Set of names of the prospective DFA's accept states.

Definition at line 386 of file dfa.cpp.

alphabet

unordered_set<char32_t> reg::dfa::builder::pImpl::alphabet

Set of symbols processable by the prospective DFA.

Definition at line 385 of file dfa.cpp.

initial

string reg::dfa::builder::pImpl::initial

Name of the prospective DFA's initial state.

Definition at line 384 of file dfa.cpp.

transitions

Dtransitionmap reg::dfa::builder::pImpl::transitions

Transition function (state × symbol → state) of the prospective DFA.

Also encodes the set of states in its set of keys.

Definition at line 387 of file dfa.cpp.

---

The documentation for this struct was generated from the following file:

• dfa.cpp