66 std::shared_ptr<const regex_node>
node;
69 inline std::size_t
hash()
const;
83 inline void render(std::string &out)
const;
107 node->kids.size() != o.
node->kids.size())
109 for(std::size_t i = 0; i <
node->kids.size(); ++i)
110 if(
node->kids[i] != o.
node->kids[i])
117 case EMPTY: out +=
"∅";
return;
118 case EPSILON: out +=
"ε";
return;
119 case ATOM: out +=
node->label;
return;
122 const char *sep =
kind() ==
UNION ?
" | " :
" · ";
124 for(
const auto &k :
node->kids) {
144 const std::string &t = k.
node->label;
145 for(std::size_t i = 1; i < t.size(); ++i)
146 if(((
unsigned char) t[i] & 0xC0) != 0x80)
150 out += k.
node->label;
169 std::vector<regex_t> kids) {
170 std::size_t h = std::hash<std::string>()(label) * 31 + k + 1;
171 for(
const auto &x : kids)
172 h = h * 1000003 ^ x.
hash();
174 r.
node = std::make_shared<const regex_node>(
175 regex_node{k, std::move(label), std::move(kids), h});
186 std::vector<regex_t> alts;
187 bool epsilon =
false, starred =
false;
188 const auto add = [&](
const regex_t &a) {
201 for(
const auto &b : alts)
206 for(
const auto &x : v)
208 for(
const auto &a : x.node->kids)
215 if(epsilon && !starred)
216 alts.insert(alts.begin(),
atom(
""));
224 std::vector<regex_t> factors;
225 for(
const auto &x : v)
232 factors.insert(factors.end(), x.node->kids.begin(),
236 factors.push_back(x);
240 if(factors.size() == 1)
255 std::vector<regex_t> alts;
256 for(
const auto &x : a.
node->kids)
260 return star(alts[0]);
261 if(alts.size() < a.
node->kids.size())
297 "The regular-expression semiring computes no monus (outer "
298 "joins, EXCEPT and NOT EXISTS need one): its monus, the "
299 "difference of languages, needs automata to compute, and would "
300 "not register an absence (1 minus a language without the empty "
Generic directed-acyclic-graph circuit template and gate identifier.
Abstract semiring interface for provenance evaluation.
A refusal by design, or a known gap, rather than an error.
The regular-expression semiring over regex_t.
virtual value_type zero() const override
Return the additive identity .
virtual bool exact_equality() const override
Equality is syntactic.
virtual value_type one() const override
Return the multiplicative identity .
virtual bool idempotent() const override
Union is idempotent.
virtual value_type delta(value_type x) const override
Apply the operator.
virtual bool has_star() const override
Every language has a Kleene star.
value_type parse_leaf(const char *v) const
virtual value_type star(const value_type &a) const override
, the sum of the powers of a.
virtual value_type times(const std::vector< value_type > &v) const override
Apply the multiplicative operation to a list of values.
virtual value_type plus(const std::vector< value_type > &v) const override
Apply the additive operation to a list of values.
std::string to_text(const value_type &v) const
The expression, as text.
virtual value_type monus(value_type, value_type) const override
Apply the monus (m-semiring difference) operation.
virtual bool commutative() const override
Concatenation does not commute.
Abstract base class for (m-)semirings.
std::vector< regex_t > kids
The operands of STAR, CONCAT and UNION.
std::string label
The label of an ATOM.
regex_t::Kind kind
Its operator.
std::size_t hash
Of the whole expression.
Operations on regular expressions, shared by Regex and TropicalPaths.
static regex_t atom(const std::string &label)
A one-letter language; for an empty label.
static regex_t plus(const std::vector< regex_t > &v)
The union of v.
static regex_t star(const regex_t &a)
The Kleene star of a.
static regex_t times(const std::vector< regex_t > &v)
The concatenation of v, in this order.
static regex_t make(regex_t::Kind k, std::string label, std::vector< regex_t > kids)
A node of kind k.
A regular expression: an immutable tree, shared between the expressions built from it.
bool operator!=(const regex_t &o) const
Syntactic inequality.
Kind
The operator at the root of the expression.
bool operator==(const regex_t &o) const
Syntactic equality.
std::string render() const
The expression, as text.
std::shared_ptr< const regex_node > node
The root; null for ∅