libsemigroups
elements.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 // This file contains the declaration of the element class and its subclasses.
20 
21 #ifndef LIBSEMIGROUPS_SRC_ELEMENTS_H_
22 #define LIBSEMIGROUPS_SRC_ELEMENTS_H_
23 
24 #include <math.h>
25 
26 #include <algorithm>
27 #include <functional>
28 #include <iostream>
29 #include <unordered_set>
30 #include <vector>
31 
32 #include "blocks.h"
33 #include "libsemigroups-debug.h"
34 #include "recvec.h"
35 #include "semiring.h"
36 
37 namespace libsemigroups {
38 
44  class Element {
45  public:
52  enum elm_t {
54  RWSE = 0,
57  };
58 
63  explicit Element(elm_t type = Element::elm_t::NOT_RWSE)
64  : _hash_value(UNDEFINED), _type(type) {}
65 
70  virtual ~Element() {}
71 
73  elm_t get_type() const {
74  return _type;
75  }
76 
81  virtual bool operator==(const Element& that) const = 0;
82 
89  virtual bool operator<(const Element& that) const = 0;
90 
104  virtual size_t complexity() const = 0;
105 
116  virtual size_t degree() const = 0;
117 
123  inline size_t hash_value() const {
124  if (_hash_value == UNDEFINED) {
125  this->cache_hash_value();
126  }
127  return this->_hash_value;
128  }
129 
135  virtual Element* identity() const = 0;
136 
151  virtual Element* really_copy(size_t increase_deg_by = 0) const = 0;
152 
156  virtual void copy(Element const* x) = 0;
157 
161  virtual void swap(Element* x) = 0;
162 
173  virtual void really_delete() = 0;
174 
185  virtual void redefine(Element const* x, Element const* y) {
186  redefine(x, y, 0);
187  }
188 
208  virtual void
209  redefine(Element const* x, Element const* y, size_t const& thread_id) {
210  (void) thread_id;
211  redefine(x, y);
212  }
213 
219  struct Equal {
221  bool operator()(Element const* x, Element const* y) const {
222  return *x == *y;
223  }
224  };
225 
232  struct Hash {
235  size_t operator()(Element const* x) const {
236  return x->hash_value();
237  }
238  };
239 
240  protected:
244  virtual void cache_hash_value() const = 0;
245 
252  void reset_hash_value() const {
253  _hash_value = UNDEFINED;
254  }
255 
261  static size_t const UNDEFINED;
262 
268  mutable size_t _hash_value;
269 
270  private:
271  elm_t _type;
272  };
273 
288  template <typename TValueType, class TSubclass>
290  public:
295  : Element(), _vector(new std::vector<TValueType>()) {}
296 
304  explicit ElementWithVectorData(std::vector<TValueType>* vector)
305  : Element(), _vector(vector) {}
306 
313  explicit ElementWithVectorData(std::vector<TValueType> const& vector)
314  : ElementWithVectorData(new std::vector<TValueType>(vector)) {}
315 
321  inline TValueType operator[](size_t pos) const {
322  return (*_vector)[pos];
323  }
324 
329  inline TValueType at(size_t pos) const {
330  return _vector->at(pos);
331  }
332 
337  bool operator==(Element const& that) const override {
338  return *(static_cast<TSubclass const&>(that)._vector) == *(this->_vector);
339  }
340 
346  bool operator<(Element const& that) const override {
347  TSubclass const& ewvd = static_cast<TSubclass const&>(that);
348  if (this->_vector->size() != ewvd._vector->size()) {
349  return this->_vector->size() < ewvd._vector->size();
350  }
351  for (size_t i = 0; i < this->_vector->size(); i++) {
352  if ((*this)[i] != ewvd[i]) {
353  return (*this)[i] < ewvd[i];
354  }
355  }
356  return false;
357  }
358 
366  Element* really_copy(size_t increase_deg_by = 0) const override {
367  LIBSEMIGROUPS_ASSERT(increase_deg_by == 0);
368  (void) increase_deg_by;
369  std::vector<TValueType>* vector(new std::vector<TValueType>(*_vector));
370  TSubclass* copy = new TSubclass(vector);
371  copy->_hash_value = this->_hash_value;
372  return copy;
373  }
374 
382  void copy(Element const* x) override {
383  LIBSEMIGROUPS_ASSERT(x->degree() == this->degree());
384  ElementWithVectorData const* xx
385  = static_cast<ElementWithVectorData const*>(x);
386  _vector->assign(xx->_vector->cbegin(), xx->_vector->cend());
387  this->_hash_value = xx->_hash_value;
388  }
389 
397  void swap(Element* x) override {
398  LIBSEMIGROUPS_ASSERT(x->degree() == this->degree());
399  ElementWithVectorData* xx = static_cast<ElementWithVectorData*>(x);
400  _vector->swap(*(xx->_vector));
401  std::swap(this->_hash_value, xx->_hash_value);
402  }
403 
405  void really_delete() override {
406  delete _vector;
407  }
408 
413  inline typename std::vector<TValueType>::iterator begin() const {
414  return _vector->begin();
415  }
416 
421  inline typename std::vector<TValueType>::iterator end() const {
422  return _vector->end();
423  }
424 
429  inline typename std::vector<TValueType>::iterator cbegin() const {
430  return _vector->cbegin();
431  }
432 
437  inline typename std::vector<TValueType>::iterator cend() const {
438  return _vector->cend();
439  }
440 
441  protected:
442  // Cannot declare cache_hash_value here, since PBR's are vectors of
443  // vectors, and there is not std::hash<vector<whatever>>.
446  template <typename T>
447  static inline size_t vector_hash(std::vector<T> const* vec) {
448  size_t seed = 0;
449  for (auto const& x : *vec) {
450  seed ^= std::hash<T>{}(x) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
451  }
452  return seed;
453  }
454 
458  std::vector<TValueType>* _vector;
459  };
460 
467  template <typename TValueType, class TSubclass>
469  : public ElementWithVectorData<TValueType, TSubclass> {
471 
472  protected:
479  void cache_hash_value() const override {
480  this->_hash_value = this->vector_hash(this->_vector);
481  }
482  };
483 
514  template <typename TValueType, typename TSubclass>
516  : public ElementWithVectorDataDefaultHash<TValueType, TSubclass> {
517  public:
519  ElementWithVectorDataDefaultHash;
520 
526  size_t complexity() const override {
527  return this->_vector->size();
528  }
529 
535  size_t degree() const override {
536  return this->_vector->size();
537  }
538 
544  size_t crank() const {
545  _lookup.clear();
546  _lookup.resize(degree(), false);
547  size_t r = 0;
548  for (auto const& x : *(this->_vector)) {
549  if (x != UNDEFINED && !_lookup[x]) {
550  _lookup[x] = true;
551  r++;
552  }
553  }
554  return r;
555  }
556 
562  Element* identity() const override {
563  std::vector<TValueType>* vector(new std::vector<TValueType>());
564  vector->reserve(this->degree());
565  for (size_t i = 0; i < this->degree(); i++) {
566  vector->push_back(i);
567  }
568  return new TSubclass(vector);
569  }
570 
575  static TValueType const UNDEFINED;
576 
577  private:
578  // Used for determining rank
579  static std::vector<bool> _lookup;
580  };
581 
582  template <typename TValueType, typename TSubclass>
584  = std::vector<bool>();
585 
586  template <typename TValueType, typename TSubclass>
588  = std::numeric_limits<TValueType>::max();
589 
601  template <typename T>
602  class Transformation : public PartialTransformation<T, Transformation<T>> {
603  public:
605 
612  Element* really_copy(size_t increase_deg_by = 0) const override {
614  = new Transformation<T>(new std::vector<T>(*this->_vector));
615  if (increase_deg_by == 0) {
616  copy->_hash_value = this->_hash_value;
617  } else {
618  size_t n = copy->_vector->size();
619  copy->_vector->reserve(n + increase_deg_by);
620  for (size_t i = n; i < n + increase_deg_by; i++) {
621  copy->_vector->push_back(i);
622  }
623  }
624  return copy;
625  }
626 
633  void redefine(Element const* x, Element const* y) override {
634  LIBSEMIGROUPS_ASSERT(x->degree() == y->degree());
635  LIBSEMIGROUPS_ASSERT(x->degree() == this->degree());
636  LIBSEMIGROUPS_ASSERT(x != this && y != this);
637  Transformation<T> const* xx(static_cast<Transformation<T> const*>(x));
638  Transformation<T> const* yy(static_cast<Transformation<T> const*>(y));
639  size_t const n = this->_vector->size();
640  for (T i = 0; i < n; i++) {
641  (*this->_vector)[i] = (*yy)[(*xx)[i]];
642  }
643  this->reset_hash_value();
644  }
645 
646  protected:
649  void cache_hash_value() const override {
650  size_t seed = 0;
651  size_t deg = this->_vector->size();
652  for (auto const& val : *(this->_vector)) {
653  seed *= deg;
654  seed += val;
655  }
656  this->_hash_value = seed;
657  }
658  };
659 
673  template <typename T>
674  class PartialPerm : public PartialTransformation<T, PartialPerm<T>> {
675  public:
678 
686  explicit PartialPerm(std::vector<T> const& dom,
687  std::vector<T> const& ran,
688  size_t deg)
690  LIBSEMIGROUPS_ASSERT(dom.size() == ran.size());
691  LIBSEMIGROUPS_ASSERT(dom.empty()
692  || deg >= *std::max_element(dom.begin(), dom.end()));
693 
694  this->_vector->resize(deg + 1, UNDEFINED);
695  for (size_t i = 0; i < dom.size(); i++) {
696  (*this->_vector)[dom[i]] = ran[i];
697  }
698  }
699 
707  bool operator<(const Element& that) const override {
708  auto pp_this = static_cast<const PartialPerm<T>*>(this);
709  auto pp_that = static_cast<const PartialPerm<T>&>(that);
710 
711  size_t deg_this = pp_this->degree();
712  for (auto it = pp_this->_vector->end() - 1;
713  it >= pp_this->_vector->begin();
714  it--) {
715  if (*it == UNDEFINED) {
716  deg_this--;
717  } else {
718  break;
719  }
720  }
721  size_t deg_that = pp_that.degree();
722  for (auto it = pp_that._vector->end() - 1;
723  it >= pp_that._vector->begin() && deg_that >= deg_this;
724  it--) {
725  if (*it == UNDEFINED) {
726  deg_that--;
727  } else {
728  break;
729  }
730  }
731 
732  if (deg_this != deg_that) {
733  return deg_this < deg_that;
734  }
735 
736  for (size_t i = 0; i < deg_this; i++) {
737  if ((*pp_this)[i] != pp_that[i]) {
738  return (*pp_this)[i] == UNDEFINED
739  || (pp_that[i] != UNDEFINED && (*pp_this)[i] < pp_that[i]);
740  }
741  }
742  return false;
743  }
744 
751  Element* really_copy(size_t increase_deg_by = 0) const override {
753  = new PartialPerm<T>(new std::vector<T>(*this->_vector));
754  if (increase_deg_by == 0) {
755  copy->_hash_value = this->_hash_value;
756  } else {
757  size_t n = copy->_vector->size();
758  copy->_vector->reserve(n + increase_deg_by);
759  for (size_t i = n; i < n + increase_deg_by; i++) {
760  copy->_vector->push_back(UNDEFINED);
761  }
762  }
763  return copy;
764  }
765 
772  void redefine(Element const* x, Element const* y) override {
773  LIBSEMIGROUPS_ASSERT(x->degree() == y->degree());
774  LIBSEMIGROUPS_ASSERT(x->degree() == this->degree());
775  LIBSEMIGROUPS_ASSERT(x != this && y != this);
776  PartialPerm<T> const* xx(static_cast<PartialPerm<T> const*>(x));
777  PartialPerm<T> const* yy(static_cast<PartialPerm<T> const*>(y));
778  size_t const n = this->degree();
779  for (T i = 0; i < n; i++) {
780  (*this->_vector)[i]
781  = ((*xx)[i] == UNDEFINED ? UNDEFINED : (*yy)[(*xx)[i]]);
782  }
783  this->reset_hash_value();
784  }
785 
794  size_t crank() const {
795  return this->_vector->size()
796  - std::count(
797  this->_vector->cbegin(), this->_vector->cend(), UNDEFINED);
798  }
799  };
800 
808 
813 
815  : public ElementWithVectorDataDefaultHash<u_int32_t, Bipartition> {
816  // TODO add more explanation to the doc here
817  public:
821  explicit Bipartition(size_t degree)
823  _nr_blocks(Bipartition::UNDEFINED),
824  _nr_left_blocks(Bipartition::UNDEFINED),
825  _trans_blocks_lookup(),
826  _rank(Bipartition::UNDEFINED) {
827  this->_vector->resize(2 * degree);
828  }
829 
839  explicit Bipartition(std::vector<u_int32_t>* blocks)
840  : ElementWithVectorDataDefaultHash<u_int32_t, Bipartition>(blocks),
841  _nr_blocks(Bipartition::UNDEFINED),
842  _nr_left_blocks(Bipartition::UNDEFINED),
843  _trans_blocks_lookup(),
844  _rank(Bipartition::UNDEFINED) {}
845 
855  explicit Bipartition(std::vector<u_int32_t> const& blocks)
856  : Bipartition(new std::vector<u_int32_t>(blocks)) {}
857 
858  // TODO another constructor that accepts an actual partition
859 
864  size_t complexity() const override;
865 
870  size_t degree() const override;
871 
877  Element* identity() const override;
878 
890  void redefine(Element const* x,
891  Element const* y,
892  size_t const& thread_id) override;
893 
899  size_t rank();
900 
905  u_int32_t const_nr_blocks() const;
906 
910  u_int32_t nr_blocks();
911 
917  u_int32_t nr_left_blocks();
918 
924  u_int32_t nr_right_blocks();
925 
933  bool is_transverse_block(size_t index);
934 
940  Blocks* left_blocks();
941 
947  Blocks* right_blocks();
948 
954  inline void set_nr_blocks(size_t nr_blocks) {
955  LIBSEMIGROUPS_ASSERT(_nr_blocks == Bipartition::UNDEFINED
956  || _nr_blocks == nr_blocks);
957  _nr_blocks = nr_blocks;
958  }
959 
966  inline void set_nr_left_blocks(size_t nr_left_blocks) {
967  LIBSEMIGROUPS_ASSERT(_nr_left_blocks == Bipartition::UNDEFINED
968  || _nr_left_blocks == nr_left_blocks);
969  _nr_left_blocks = nr_left_blocks;
970  }
971 
977  inline void set_rank(size_t rank) {
978  LIBSEMIGROUPS_ASSERT(_rank == Bipartition::UNDEFINED || _rank == rank);
979  _rank = rank;
980  }
981 
982  private:
983  u_int32_t fuseit(std::vector<u_int32_t>& fuse, u_int32_t pos);
984  void init_trans_blocks_lookup();
985 
986  static std::vector<std::vector<u_int32_t>> _fuse;
987  static std::vector<std::vector<u_int32_t>> _lookup;
988 
989  size_t _nr_blocks;
990  size_t _nr_left_blocks;
991  std::vector<bool> _trans_blocks_lookup;
992  size_t _rank;
993 
994  static u_int32_t const UNDEFINED;
995  };
996 
1012  template <typename TValueType, class TSubclass>
1014  : public ElementWithVectorDataDefaultHash<TValueType, TSubclass> {
1015  public:
1031  MatrixOverSemiringBase(std::vector<TValueType>* matrix,
1033  : ElementWithVectorDataDefaultHash<TValueType, TSubclass>(matrix),
1034  _degree(sqrt(matrix->size())),
1035  _semiring(semiring) {
1036  LIBSEMIGROUPS_ASSERT(semiring != nullptr);
1037  LIBSEMIGROUPS_ASSERT(!matrix->empty());
1038  LIBSEMIGROUPS_ASSERT(matrix->size() == _degree * _degree);
1039  }
1040 
1062  MatrixOverSemiringBase(std::vector<std::vector<TValueType>> const& matrix,
1064  : ElementWithVectorDataDefaultHash<TValueType, TSubclass>(),
1065  _degree(matrix[0].size()),
1066  _semiring(semiring) {
1067  LIBSEMIGROUPS_ASSERT(semiring != nullptr);
1068  LIBSEMIGROUPS_ASSERT(!matrix.empty());
1069  LIBSEMIGROUPS_ASSERT(all_of(
1070  matrix.begin(), matrix.end(), [matrix](std::vector<TValueType> row) {
1071  return row.size() == matrix.size();
1072  }));
1073 
1074  this->_vector->reserve(matrix.size() * matrix.size());
1075  for (auto const& row : matrix) {
1076  this->_vector->insert(this->_vector->end(), row.begin(), row.end());
1077  }
1078  }
1079 
1082  return _semiring;
1083  }
1084 
1089  size_t complexity() const override {
1090  return pow(this->degree(), 3);
1091  }
1092 
1097  size_t degree() const override {
1098  return _degree;
1099  }
1100 
1106  Element* identity() const override {
1107  std::vector<TValueType>* vec(new std::vector<TValueType>());
1108  vec->resize(this->_vector->size(), _semiring->zero());
1109  size_t n = this->degree();
1110  for (auto it = vec->begin(); it < vec->end(); it += n + 1) {
1111  (*it) = _semiring->one();
1112  }
1113  return new TSubclass(vec, _semiring);
1114  }
1115 
1120  Element* really_copy(size_t increase_deg_by = 0) const override {
1121  LIBSEMIGROUPS_ASSERT(increase_deg_by == 0);
1122  (void) increase_deg_by;
1125  TSubclass>::really_copy());
1126  LIBSEMIGROUPS_ASSERT(copy->_semiring == nullptr
1127  || copy->_semiring == this->_semiring);
1128  copy->_semiring = _semiring;
1129  return copy;
1130  }
1131 
1138  void redefine(Element const* x, Element const* y) override {
1139  auto xx = static_cast<MatrixOverSemiringBase const*>(x);
1140  auto yy = static_cast<MatrixOverSemiringBase const*>(y);
1141  LIBSEMIGROUPS_ASSERT(xx->degree() == yy->degree());
1142  LIBSEMIGROUPS_ASSERT(xx->degree() == this->degree());
1143  LIBSEMIGROUPS_ASSERT(xx != this && yy != this);
1144  // It can be that the elements are defined over semirings that are
1145  // distinct in memory but equal (for example, when one element comes
1146  // from a semigroup and another from an ideal of that semigroup).
1147  // LIBSEMIGROUPS_ASSERT(xx->semiring() == yy->semiring() &&
1148  // xx->semiring() == this->semiring());
1149  // TODO verify that x, y, and this are defined over the same semiring.
1150  size_t deg = this->degree();
1151 
1152  for (size_t i = 0; i < deg; i++) {
1153  for (size_t j = 0; j < deg; j++) {
1154  int64_t v = _semiring->zero();
1155  for (size_t k = 0; k < deg; k++) {
1156  v = _semiring->plus(
1157  v, _semiring->prod((*xx)[i * deg + k], (*yy)[k * deg + j]));
1158  }
1159  (*this->_vector)[i * deg + j] = v;
1160  }
1161  }
1162  after(); // post process this
1163  this->reset_hash_value();
1164  }
1165 
1166  protected:
1167  friend class ElementWithVectorData<TValueType, TSubclass>;
1171  explicit MatrixOverSemiringBase(std::vector<TValueType>* matrix)
1172  : ElementWithVectorDataDefaultHash<TValueType, TSubclass>(matrix),
1173  _degree(sqrt(matrix->size())),
1174  _semiring(nullptr) {}
1175 
1176  private:
1177  // A function applied after redefinition
1178  virtual inline void after() {}
1179  size_t _degree;
1180  Semiring<TValueType> const* _semiring;
1181  };
1182 
1189  template <typename TValueType>
1191  : public MatrixOverSemiringBase<TValueType,
1192  MatrixOverSemiring<TValueType>> {
1193  friend class ElementWithVectorData<TValueType,
1194  MatrixOverSemiring<TValueType>>;
1197  };
1198 
1209  : public MatrixOverSemiringBase<int64_t, ProjectiveMaxPlusMatrix> {
1210  public:
1218  ProjectiveMaxPlusMatrix(std::vector<int64_t>* matrix,
1219  Semiring<int64_t> const* semiring)
1220  : MatrixOverSemiringBase(matrix, semiring) {
1221  after(); // this is to put the matrix in normal form
1222  }
1223 
1231  ProjectiveMaxPlusMatrix(std::vector<std::vector<int64_t>> const& matrix,
1232  Semiring<int64_t> const* semiring)
1233  : MatrixOverSemiringBase(matrix, semiring) {
1234  after(); // this is to put the matrix in normal form
1235  }
1236 
1237  private:
1238  friend class ElementWithVectorData<int64_t, ProjectiveMaxPlusMatrix>;
1239  explicit ProjectiveMaxPlusMatrix(std::vector<int64_t>* matrix)
1240  : MatrixOverSemiringBase(matrix) {}
1241 
1242  // A function applied after redefinition
1243  inline void after() final {
1244  int64_t norm = *std::max_element(_vector->begin(), _vector->end());
1245  for (auto& x : *_vector) {
1246  if (x != LONG_MIN) {
1247  x -= norm;
1248  }
1249  }
1250  }
1251  };
1252 
1265  template <typename T> class Permutation : public Transformation<T> {
1266  public:
1273  size_t const n = this->_vector->size();
1274  Permutation* id = static_cast<Permutation<T>*>(this->identity());
1275  for (T i = 0; i < n; i++) {
1276  (*id->_vector)[(*this->_vector)[i]] = i;
1277  }
1278  return id;
1279  }
1280  };
1281 
1289  class BooleanMat : public MatrixOverSemiringBase<bool, BooleanMat> {
1290  public:
1301  explicit BooleanMat(std::vector<bool>* matrix)
1302  : MatrixOverSemiringBase<bool, BooleanMat>(matrix, _semiring) {}
1303 
1309  explicit BooleanMat(std::vector<std::vector<bool>> const& matrix)
1310  : MatrixOverSemiringBase<bool, BooleanMat>(matrix,
1311  BooleanMat::_semiring) {}
1312 
1317  void redefine(Element const* x, Element const* y) final;
1318 
1319  // There is a specialization of std::hash for std::vector<bool> but for
1320  // some reason it causes a dramatic slow down in some of the benchmarks if
1321  // it is used by cache_hash_value below. So, we leave this commented out as
1322  // a reminder not to use it.
1323 
1324  // protected:
1325  // void cache_hash_value() const override {
1326  // this->_hash_value = std::hash<std::vector<bool>>{}(*this->_vector);
1327  // }
1328 
1329  private:
1330  // The next constructor only exists to allow the identity method for
1331  // MatrixOverSemiringBase to work.
1332  friend class MatrixOverSemiringBase<bool, BooleanMat>;
1333  explicit BooleanMat(std::vector<bool>* matrix,
1334  Semiring<bool> const* semiring)
1335  : MatrixOverSemiringBase<bool, BooleanMat>(matrix, semiring) {}
1336 
1337  static BooleanSemiring const* const _semiring;
1338  };
1339 
1345  class PBR : public ElementWithVectorData<std::vector<u_int32_t>, PBR> {
1346  public:
1357 
1362  size_t complexity() const override;
1363 
1369  size_t degree() const override;
1370 
1377  Element* identity() const override;
1378 
1390  void redefine(Element const* x,
1391  Element const* y,
1392  size_t const& thread_id) override;
1393 
1394  protected:
1395  void cache_hash_value() const override;
1396 
1397  private:
1398  void unite_rows(RecVec<bool>& out,
1399  RecVec<bool>& tmp,
1400  size_t const& vertex1,
1401  size_t const& vertex2);
1402 
1403  void x_dfs(std::vector<bool>& x_seen,
1404  std::vector<bool>& y_seen,
1405  RecVec<bool>& tmp,
1406  u_int32_t const& n,
1407  u_int32_t const& i,
1408  PBR const* const x,
1409  PBR const* const y,
1410  size_t const& adj);
1411 
1412  void y_dfs(std::vector<bool>& x_seen,
1413  std::vector<bool>& y_seen,
1414  RecVec<bool>& tmp,
1415  u_int32_t const& n,
1416  u_int32_t const& i,
1417  PBR const* const x,
1418  PBR const* const y,
1419  size_t const& adj);
1420 
1421  static std::vector<std::vector<bool>> _x_seen;
1422  static std::vector<std::vector<bool>> _y_seen;
1423  static std::vector<RecVec<bool>> _out;
1424  static std::vector<RecVec<bool>> _tmp;
1425  };
1426 
1427  template <typename T> static inline void really_delete_cont(T cont) {
1428  for (Element const* x : cont) {
1429  const_cast<Element*>(x)->really_delete();
1430  delete x;
1431  }
1432  }
1433 
1434  template <typename T> static inline void really_delete_cont(T* cont) {
1435  for (Element const* x : *cont) {
1436  const_cast<Element*>(x)->really_delete();
1437  delete x;
1438  }
1439  delete cont;
1440  }
1441 } // namespace libsemigroups
1442 #endif // LIBSEMIGROUPS_SRC_ELEMENTS_H_
Class for bipartitions.
Definition: elements.h:814
virtual T prod(T x, T y) const =0
Returns the product of x and y.
Element(elm_t type=Element::elm_t::NOT_RWSE)
A constructor.
Definition: elements.h:63
size_t operator()(Element const *x) const
Returns the value of Element::hash_value applied to the Element pointed to by x.
Definition: elements.h:235
BooleanMat(std::vector< bool > *matrix)
A constructor.
Definition: elements.h:1301
Class for partitioned binary relations (PBR).
Definition: elements.h:1345
ElementWithVectorData()
A constructor.
Definition: elements.h:294
ProjectiveMaxPlusMatrix(std::vector< int64_t > *matrix, Semiring< int64_t > const *semiring)
A constructor.
Definition: elements.h:1218
virtual void redefine(Element const *x, Element const *y, size_t const &thread_id)
Multiplies x and y and stores the result in this.
Definition: elements.h:209
Matrices over a semiring.
Definition: elements.h:1190
virtual void swap(Element *x)=0
Swap another Element with this.
static TValueType const UNDEFINED
Undefined image value.
Definition: elements.h:575
virtual size_t degree() const =0
Returns the degree of an Element.
MatrixOverSemiringBase(std::vector< TValueType > *matrix, Semiring< TValueType > const *semiring)
A constructor.
Definition: elements.h:1031
size_t degree() const override
Returns the degree of a PBR.
Definition: elements.cc:284
bool is_transverse_block(size_t index)
Returns true if the block with index index is transverse.
Definition: elements.cc:203
u_int32_t nr_left_blocks()
Returns the number of blocks containing a positive integer.
Definition: elements.cc:179
Matrices over the boolean semiring.
Definition: elements.h:1289
Class for signed partitions of the set .
Definition: blocks.h:45
std::vector< TValueType >::iterator cend() const
Returns a const iterator.
Definition: elements.h:437
bool operator<(Element const &that) const override
Returns true if this is less than that.
Definition: elements.h:346
size_t complexity() const override
Returns the approximate time complexity of multiplying two partial transformations.
Definition: elements.h:526
size_t degree() const override
Returns the degree of the bipartition.
Definition: elements.cc:71
MatrixOverSemiringBase(std::vector< TValueType > *matrix)
Constructs a MatrixOverSemiringBase with whose underlying semiring is not defined. The underlying semiring must be set by any class deriving from this one.
Definition: elements.h:1171
Bipartition(std::vector< u_int32_t > const &blocks)
A constructor.
Definition: elements.h:855
virtual void cache_hash_value() const =0
Calculate and cache a hash value.
MatrixOverSemiringBase(std::vector< std::vector< TValueType >> const &matrix, Semiring< TValueType > const *semiring)
A constructor.
Definition: elements.h:1062
std::vector< TValueType >::iterator cbegin() const
Returns a const iterator.
Definition: elements.h:429
void redefine(Element const *x, Element const *y, size_t const &thread_id) override
Multiply x and y and stores the result in this.
Definition: elements.cc:88
Abstract base class for elements using a vector to store their defining data.
Definition: elements.h:289
Provides a call operator for comparing Elements via pointers.
Definition: elements.h:219
virtual void copy(Element const *x)=0
Copy another Element into this.
PartialPerm(std::vector< T > const &dom, std::vector< T > const &ran, size_t deg)
A constructor.
Definition: elements.h:686
Abstract base class for semigroup elements.
Definition: elements.h:44
Blocks * right_blocks()
Return the left blocks of a bipartition.
Definition: elements.cc:242
void redefine(Element const *x, Element const *y) override
Multiply x and y and stores the result in this.
Definition: elements.h:772
void set_nr_blocks(size_t nr_blocks)
Set the cached number of blocks.
Definition: elements.h:954
Template class for permutations.
Definition: elements.h:1265
Element * identity() const override
Returns the identity transformation with degrees of this.
Definition: elements.h:562
size_t complexity() const override
Returns the approximate time complexity of multiplying two matrices.
Definition: elements.h:1089
Element * identity() const override
Returns an identity bipartition.
Definition: elements.cc:76
Template class for partial permutations.
Definition: elements.h:674
Matrices over a semiring.
Definition: elements.h:1013
ElementWithVectorData(std::vector< TValueType > const &vector)
A constructor.
Definition: elements.h:313
ElementWithVectorData(std::vector< TValueType > *vector)
A constructor.
Definition: elements.h:304
Element * really_copy(size_t increase_deg_by=0) const override
Returns a pointer to a copy of this.
Definition: elements.h:1120
void redefine(Element const *x, Element const *y) override
Multiply x and y and stores the result in this.
Definition: elements.h:633
void reset_hash_value() const
Reset the cached value used by Element::hash_value.
Definition: elements.h:252
Type for Element objects not arising from a rewriting system RWS.
Definition: elements.h:56
u_int32_t const_nr_blocks() const
Returns the number of blocks in a bipartition.
Definition: elements.cc:162
Bipartition(std::vector< u_int32_t > *blocks)
A constructor.
Definition: elements.h:839
virtual T plus(T x, T y) const =0
Returns the sum of x and y.
void cache_hash_value() const override
This method is included because it seems to give superior performance in some benchmarks.
Definition: elements.h:649
u_int32_t nr_blocks()
Returns the number of blocks in a bipartition.
Definition: elements.cc:172
TValueType operator[](size_t pos) const
Returns the pos entry in the vector containing the defining data.
Definition: elements.h:321
void swap(Element *x) override
Swap another Element with this.
Definition: elements.h:397
ProjectiveMaxPlusMatrix(std::vector< std::vector< int64_t >> const &matrix, Semiring< int64_t > const *semiring)
A constructor.
Definition: elements.h:1231
void cache_hash_value() const override
Calculate and cache a hash value.
Definition: elements.cc:288
void cache_hash_value() const override
This method implements the default hash function for an ElementWithVectorData, which uses ElementWith...
Definition: elements.h:479
elm_t get_type() const
Returns the type libsemigroups::Element::elm_t of an Element object.
Definition: elements.h:73
Template class for transformations.
Definition: elements.h:602
Element * really_copy(size_t increase_deg_by=0) const override
Returns a pointer to a copy of this.
Definition: elements.h:751
bool operator()(Element const *x, Element const *y) const
Returns true if x and y point to equal Element&#39;s.
Definition: elements.h:221
Namespace for everything in the libsemigroups library.
Definition: blocks.cc:32
size_t hash_value() const
Return the hash value of an Element.
Definition: elements.h:123
bool operator<(const Element &that) const override
Returns true if this is less than that.
Definition: elements.h:707
size_t complexity() const override
Returns the approximate time complexity of multiplication.
Definition: elements.cc:67
void set_rank(size_t rank)
Set the cached rank.
Definition: elements.h:977
Permutation * inverse()
Returns the inverse of a permutation.
Definition: elements.h:1272
void copy(Element const *x) override
Copy another Element into this.
Definition: elements.h:382
elm_t
This enum contains some different types of Element.
Definition: elements.h:52
static size_t vector_hash(std::vector< T > const *vec)
Returns a hash value for a vector provided there is a specialization of std::hash for the template ty...
Definition: elements.h:447
Abstract base class for elements using a vector to store their defining data and the default hash fun...
Definition: elements.h:468
Element * identity() const override
Returns the identity PBR with degree equal to that of this.
Definition: elements.cc:295
virtual bool operator==(const Element &that) const =0
Returns true if this equals that.
size_t degree() const override
Returns the degree of a partial transformation.
Definition: elements.h:535
virtual void really_delete()=0
Deletes the defining data of an Element.
void set_nr_left_blocks(size_t nr_left_blocks)
Set the cached number of left blocks.
Definition: elements.h:966
Element * really_copy(size_t increase_deg_by=0) const override
Returns a pointer to a copy of this.
Definition: elements.h:612
void redefine(Element const *x, Element const *y) final
Multiplies x and y and stores the result in this.
Definition: elements.cc:36
static size_t const UNDEFINED
UNDEFINED value.
Definition: elements.h:261
void redefine(Element const *x, Element const *y, size_t const &thread_id) override
Multiply x and y and stores the result in this.
Definition: elements.cc:311
size_t crank() const
Returns the rank of a partial transformation.
Definition: elements.h:544
std::vector< TValueType >::iterator begin() const
Returns an iterator.
Definition: elements.h:413
size_t complexity() const override
Returns the approximate time complexity of multiplying PBRs.
Definition: elements.cc:280
std::vector< TValueType > * _vector
The vector containing the defining data of this.
Definition: elements.h:458
u_int32_t nr_right_blocks()
Returns the number of blocks containing a negative integer.
Definition: elements.cc:193
virtual ~Element()
A default destructor.
Definition: elements.h:70
virtual void redefine(Element const *x, Element const *y)
Multiplies x and y and stores the result in this.
Definition: elements.h:185
Element * identity() const override
Returns the identity matrix with dimension of this.
Definition: elements.h:1106
virtual Element * really_copy(size_t increase_deg_by=0) const =0
Returns a new element completely independent of this.
virtual bool operator<(const Element &that) const =0
Returns true if this is less than that.
Subclass of Element that wraps an libsemigroups::rws_word_t.
Definition: rwse.h:37
size_t crank() const
Returns the rank of a partial permutation.
Definition: elements.h:794
Blocks * left_blocks()
Return the left blocks of a bipartition.
Definition: elements.cc:231
BooleanMat(std::vector< std::vector< bool >> const &matrix)
A constructor.
Definition: elements.h:1309
virtual T zero() const =0
Returns the additive identity, or zero, of the semiring.
std::vector< TValueType >::iterator end() const
Returns an iterator.
Definition: elements.h:421
Element * really_copy(size_t increase_deg_by=0) const override
Returns a pointer to a copy of this.
Definition: elements.h:366
Abstract class for partial transformations.
Definition: elements.h:515
Semiring< TValueType > const * semiring() const
Returns a pointer to the Semiring over which the matrix is defined.
Definition: elements.h:1081
Provides a call operator returning a hash value for an Element via a pointer.
Definition: elements.h:232
size_t degree() const override
Returns the dimension of the matrix.
Definition: elements.h:1097
virtual Element * identity() const =0
Returns a new copy of the identity element.
Class for projective max-plus matrices.
Definition: elements.h:1208
virtual size_t complexity() const =0
Returns the approximate time complexity of multiplying two Element objects in a given subclass...
virtual T one() const =0
Returns the multiplicative identity, or one, of the semiring.
TValueType at(size_t pos) const
Returns the pos entry in the vector containing the defining data.
Definition: elements.h:329
Bipartition(size_t degree)
A constructor.
Definition: elements.h:821
size_t rank()
Returns the number of transverse blocks.
Definition: elements.cc:222
void really_delete() override
Deletes the defining data of an ElementWithVectorData.
Definition: elements.h:405
bool operator==(Element const &that) const override
Returns true if this equals that.
Definition: elements.h:337
void redefine(Element const *x, Element const *y) override
Multiply x and y and stores the result in this.
Definition: elements.h:1138