libsemigroups
semiring.h
1 //
2 // libsemigroups - C++ library for semigroups and monoids
3 // Copyright (C) 2016 James D. Mitchell
4 //
5 // This program is free software: you can redistribute it and/or modify
6 // it under the terms of the GNU General Public License as published by
7 // the Free Software Foundation, either version 3 of the License, or
8 // (at your option) any later version.
9 //
10 // This program is distributed in the hope that it will be useful,
11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 // GNU General Public License for more details.
14 //
15 // You should have received a copy of the GNU General Public License
16 // along with this program. If not, see <http://www.gnu.org/licenses/>.
17 //
18 
19 #ifndef LIBSEMIGROUPS_SRC_SEMIRING_H_
20 #define LIBSEMIGROUPS_SRC_SEMIRING_H_
21 
22 #include <limits.h>
23 
24 #include <algorithm>
25 #include <cstdint>
26 
27 #include "libsemigroups-debug.h"
28 
29 namespace libsemigroups {
30 
48  template <typename T> class Semiring {
49  public:
51  static const T UNDEFINED;
52 
54  static const T MINUS_INFTY;
55 
57  static const T INFTY;
58 
60  virtual ~Semiring() {}
61 
63  virtual T one() const = 0;
64 
66  virtual T zero() const = 0;
67 
69  virtual T plus(T x, T y) const = 0;
70 
72  virtual T prod(T x, T y) const = 0;
73  };
74 
75  template <typename T>
76  const T Semiring<T>::UNDEFINED = std::numeric_limits<T>::max();
77 
78  template <typename T>
79  const T Semiring<T>::MINUS_INFTY = std::numeric_limits<T>::min();
80 
81  template <typename T>
82  const T Semiring<T>::INFTY = std::numeric_limits<T>::max();
83 
85  class BooleanSemiring : public Semiring<bool> {
86  public:
87  BooleanSemiring() : Semiring() {}
88 
90  bool one() const override {
91  return true;
92  }
93 
95  bool zero() const override {
96  return false;
97  }
98 
100  bool prod(bool x, bool y) const override {
101  return x && y;
102  }
103 
105  bool plus(bool x, bool y) const override {
106  return x || y;
107  }
108  };
109 
111  class Integers : public Semiring<int64_t> {
112  public:
113  Integers() : Semiring<int64_t>() {}
114 
116  int64_t one() const override {
117  return 1;
118  }
119 
121  int64_t zero() const override {
122  return 0;
123  }
124 
126  int64_t prod(int64_t x, int64_t y) const override {
127  return x * y;
128  }
129 
131  int64_t plus(int64_t x, int64_t y) const override {
132  return x + y;
133  }
134  };
135 
139  class MaxPlusSemiring : public Semiring<int64_t> {
140  public:
142 
144  int64_t one() const override {
145  return 0;
146  }
147 
149  int64_t zero() const override {
150  return MINUS_INFTY;
151  }
152 
155  int64_t prod(int64_t x, int64_t y) const override {
156  if (x == MINUS_INFTY || y == MINUS_INFTY) {
157  return MINUS_INFTY;
158  }
159  return x + y;
160  }
161 
163  int64_t plus(int64_t x, int64_t y) const override {
164  return std::max(x, y);
165  }
166  };
167 
171  class MinPlusSemiring : public Semiring<int64_t> {
172  public:
174 
176  int64_t one() const override {
177  return 0;
178  }
179 
181  int64_t zero() const override {
182  return INFTY;
183  }
184 
188  int64_t prod(int64_t x, int64_t y) const override {
189  if (x == INFTY || y == INFTY) {
190  return INFTY;
191  }
192  return x + y;
193  }
194 
196  int64_t plus(int64_t x, int64_t y) const override {
197  return std::min(x, y);
198  }
199  };
200 
203  class SemiringWithThreshold : public Semiring<int64_t> {
204  public:
209  explicit SemiringWithThreshold(int64_t threshold)
210  : Semiring<int64_t>(), _threshold(threshold) {}
211 
213  int64_t threshold() const {
214  return _threshold;
215  }
216 
217  private:
218  int64_t _threshold;
219  };
220 
226  public:
230  explicit TropicalMaxPlusSemiring(int64_t threshold)
231  : SemiringWithThreshold(threshold) {}
232 
233  // Returns the integer 0.
234  int64_t one() const override {
235  return 0;
236  }
237 
239  int64_t zero() const override {
240  return MINUS_INFTY;
241  }
242 
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())
252  if (x == MINUS_INFTY || y == MINUS_INFTY) {
253  return MINUS_INFTY;
254  }
255  return std::min(x + y, threshold());
256  }
257 
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);
266  }
267  };
268 
274  public:
278  explicit TropicalMinPlusSemiring(int64_t threshold)
279  : SemiringWithThreshold(threshold) {}
280 
282  int64_t one() const override {
283  return 0;
284  }
285 
287  int64_t zero() const override {
288  return INFTY;
289  }
290 
294  int64_t prod(int64_t x, int64_t y) const override {
295  LIBSEMIGROUPS_ASSERT((x >= 0 && x <= this->threshold())
296  || x == Semiring<int64_t>::INFTY);
297  LIBSEMIGROUPS_ASSERT((y >= 0 && y <= this->threshold())
298  || y == Semiring<int64_t>::INFTY);
299  if (x == INFTY || y == INFTY) {
300  return INFTY;
301  }
302  return std::min(x + y, threshold());
303  }
304 
308  int64_t plus(int64_t x, int64_t y) const override {
309  LIBSEMIGROUPS_ASSERT((x >= 0 && x <= this->threshold())
310  || x == Semiring<int64_t>::INFTY);
311  LIBSEMIGROUPS_ASSERT((y >= 0 && y <= this->threshold())
312  || y == Semiring<int64_t>::INFTY);
313  if (x == INFTY && y == INFTY) {
314  return INFTY;
315  }
316  return std::min(x, y);
317  }
318  };
319 
325  public:
336  NaturalSemiring(int64_t t, int64_t p)
337  : SemiringWithThreshold(t), _period(p) {
338  LIBSEMIGROUPS_ASSERT(_period > 0);
339  LIBSEMIGROUPS_ASSERT(this->threshold() >= 0);
340  }
341 
343  int64_t one() const override {
344  return 1;
345  }
346 
348  int64_t zero() const override {
349  return 0;
350  }
351 
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);
358  }
359 
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);
366  }
367 
369  int64_t period() const {
370  return _period;
371  }
372 
373  private:
374  int64_t thresholdperiod(int64_t x) const {
375  int64_t threshold = this->threshold();
376  if (x > threshold) {
377  return threshold + (x - threshold) % _period;
378  }
379  return x;
380  }
381 
382  int64_t _period;
383  };
384 } // namespace libsemigroups
385 
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, and otherwise the minimum of x, y, and the threshold of the semiring.
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, otherwise returns x + y.
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, otherwise returns the minimum of x + y and the threshold of the semiring.
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, TropicalMinPlusSemiring, and NaturalSemiring.
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