19 #ifndef LIBSEMIGROUPS_SRC_SEMIRING_H_ 20 #define LIBSEMIGROUPS_SRC_SEMIRING_H_ 27 #include "libsemigroups-debug.h" 63 virtual T
one()
const = 0;
66 virtual T
zero()
const = 0;
69 virtual T
plus(T x, T y)
const = 0;
72 virtual T
prod(T x, T y)
const = 0;
90 bool one()
const override {
95 bool zero()
const override {
100 bool prod(
bool x,
bool y)
const override {
105 bool plus(
bool x,
bool y)
const override {
116 int64_t
one()
const override {
121 int64_t
zero()
const override {
126 int64_t
prod(int64_t x, int64_t y)
const override {
131 int64_t
plus(int64_t x, int64_t y)
const override {
144 int64_t
one()
const override {
149 int64_t
zero()
const override {
155 int64_t
prod(int64_t x, int64_t y)
const override {
163 int64_t
plus(int64_t x, int64_t y)
const override {
164 return std::max(x, y);
176 int64_t
one()
const override {
181 int64_t
zero()
const override {
188 int64_t
prod(int64_t x, int64_t y)
const override {
196 int64_t
plus(int64_t x, int64_t y)
const override {
197 return std::min(x, y);
234 int64_t
one()
const override {
239 int64_t
zero()
const override {
247 int64_t
prod(int64_t x, int64_t y)
const override {
248 LIBSEMIGROUPS_ASSERT((x >= 0 && x <= this->
threshold())
250 LIBSEMIGROUPS_ASSERT((y >= 0 && y <= this->
threshold())
260 int64_t
plus(int64_t x, int64_t y)
const override {
261 LIBSEMIGROUPS_ASSERT((x >= 0 && x <= this->
threshold())
263 LIBSEMIGROUPS_ASSERT((y >= 0 && y <= this->
threshold())
265 return std::max(x, y);
282 int64_t
one()
const override {
287 int64_t
zero()
const override {
294 int64_t
prod(int64_t x, int64_t y)
const override {
295 LIBSEMIGROUPS_ASSERT((x >= 0 && x <= this->
threshold())
297 LIBSEMIGROUPS_ASSERT((y >= 0 && y <= this->
threshold())
308 int64_t
plus(int64_t x, int64_t y)
const override {
309 LIBSEMIGROUPS_ASSERT((x >= 0 && x <= this->
threshold())
311 LIBSEMIGROUPS_ASSERT((y >= 0 && y <= this->
threshold())
316 return std::min(x, y);
338 LIBSEMIGROUPS_ASSERT(_period > 0);
339 LIBSEMIGROUPS_ASSERT(this->
threshold() >= 0);
343 int64_t
one()
const override {
348 int64_t
zero()
const override {
354 int64_t
prod(int64_t x, int64_t y)
const override {
355 LIBSEMIGROUPS_ASSERT(x >= 0 && x <= _period + this->
threshold() - 1);
356 LIBSEMIGROUPS_ASSERT(y >= 0 && y <= _period + this->
threshold() - 1);
357 return thresholdperiod(x * y);
362 int64_t
plus(int64_t x, int64_t y)
const override {
363 LIBSEMIGROUPS_ASSERT(x >= 0 && x <= _period + this->
threshold() - 1);
364 LIBSEMIGROUPS_ASSERT(y >= 0 && y <= _period + this->
threshold() - 1);
365 return thresholdperiod(x + y);
374 int64_t thresholdperiod(int64_t x)
const {
386 #endif // LIBSEMIGROUPS_SRC_SEMIRING_H_ static const T INFTY
Value representing .
Definition: semiring.h:57
virtual T prod(T x, T y) const =0
Returns the product of x and y.
The tropical max-plus semiring consists of the integers for some value (called the threshold of the...
Definition: semiring.h:225
The usual ring of integers.
Definition: semiring.h:111
int64_t zero() const override
Returns the Semiring<int64_t>::INFTY.
Definition: semiring.h:287
int64_t zero() const override
Returns Semiring<int64_t>::INFTY.
Definition: semiring.h:181
The usual Boolean semiring.
Definition: semiring.h:85
This class its subclasses provide very basic functionality for creating semirings.
Definition: semiring.h:48
int64_t zero() const override
Returns the integer 0.
Definition: semiring.h:121
int64_t plus(int64_t x, int64_t y) const override
Returns x + y modulo the congruence where and are the threshold and period of the semiring,...
Definition: semiring.h:362
int64_t prod(int64_t x, int64_t y) const override
Returns x * y modulo the congruence where and are the threshold and period of the semiring,...
Definition: semiring.h:354
int64_t plus(int64_t x, int64_t y) const override
Returns the maximum of x and y.
Definition: semiring.h:163
int64_t plus(int64_t x, int64_t y) const override
Returns Semiring<int64_t>::INFTY if either of x and y is Semiring<int64_t>::INFTY,...
Definition: semiring.h:308
int64_t threshold() const
Returns the threshold of a semiring with threshold.
Definition: semiring.h:213
virtual ~Semiring()
A default destructor.
Definition: semiring.h:60
int64_t plus(int64_t x, int64_t y) const override
Returns the sum .
Definition: semiring.h:131
The min-plus semiring consists of the integers together with infinity with operations min and plus....
Definition: semiring.h:171
virtual T plus(T x, T y) const =0
Returns the sum of x and y.
int64_t zero() const override
Returns the Semiring<int64_t>::MINUS_INFTY.
Definition: semiring.h:239
int64_t prod(int64_t x, int64_t y) const override
Returns Semiring<int64_t>::INFTY if x or y equals Semiring<int64_t>::INFTY, otherwise return the mini...
Definition: semiring.h:294
TropicalMaxPlusSemiring(int64_t threshold)
Construct from threshold.
Definition: semiring.h:230
bool prod(bool x, bool y) const override
Returns the product .
Definition: semiring.h:100
TropicalMinPlusSemiring(int64_t threshold)
Construct from threshold.
Definition: semiring.h:278
bool plus(bool x, bool y) const override
Returns the sum .
Definition: semiring.h:105
Namespace for everything in the libsemigroups library.
Definition: blocks.cc:32
int64_t prod(int64_t x, int64_t y) const override
Returns Semiring<int64_t>::MINUS_INFTY if x or y equals Semiring<int64_t>::MINUS_INFTY,...
Definition: semiring.h:155
int64_t one() const override
Return the integer 1.
Definition: semiring.h:343
bool zero() const override
Returns the integer 0.
Definition: semiring.h:95
int64_t one() const override
Returns the integer 1.
Definition: semiring.h:116
static const T MINUS_INFTY
Value representing .
Definition: semiring.h:54
int64_t one() const override
Returns the integer 0.
Definition: semiring.h:282
int64_t period() const
Returns the period of the semiring.
Definition: semiring.h:369
int64_t plus(int64_t x, int64_t y) const override
Returns the minimum of x and y.
Definition: semiring.h:196
int64_t zero() const override
Return the integer 0.
Definition: semiring.h:348
static const T UNDEFINED
Value representing an undefined quantity.
Definition: semiring.h:51
int64_t plus(int64_t x, int64_t y) const override
Returns the minimum of (the maximum of x and y) and the threshold of the semiring.
Definition: semiring.h:260
int64_t prod(int64_t x, int64_t y) const override
Returns the product .
Definition: semiring.h:126
SemiringWithThreshold(int64_t threshold)
A class for semirings with a threshold.
Definition: semiring.h:209
int64_t zero() const override
Returns Semiring<int64_t>::MINUS_INFTY.
Definition: semiring.h:149
int64_t one() const override
Returns the integer 0.
Definition: semiring.h:176
int64_t prod(int64_t x, int64_t y) const override
Returns Semiring<int64_t>::MINUS_INFTY if x or y equals Semiring<int64_t>::MINUS_INFTY,...
Definition: semiring.h:247
virtual T zero() const =0
Returns the additive identity, or zero, of the semiring.
int64_t prod(int64_t x, int64_t y) const override
Returns Semiring<int64_t>::INFTY if x or y equals Semiring<int64_t>::INFTY, otherwise returns x + y.
Definition: semiring.h:188
This class implements the semiring consisting of for some threshold and period with operations add...
Definition: semiring.h:324
This abstract class provides common methods for its subclasses TropicalMaxPlusSemiring,...
Definition: semiring.h:203
NaturalSemiring(int64_t t, int64_t p)
Construct from threshold and period.
Definition: semiring.h:336
virtual T one() const =0
Returns the multiplicative identity, or one, of the semiring.
int64_t one() const override
Returns the multiplicative identity, or one, of the semiring.
Definition: semiring.h:234
The tropical min-plus semiring consists of the integers for some value (called the threshold of the...
Definition: semiring.h:273
int64_t one() const override
Returns the integer 0.
Definition: semiring.h:144
bool one() const override
Returns the integer 1.
Definition: semiring.h:90
The max-plus semiring consists of the integers together with negative infinity with operations max an...
Definition: semiring.h:139