elements.h

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2016 James D. Mitchell
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
//

// This file contains the declaration of the element class and its subclasses.

#ifndef LIBSEMIGROUPS_SRC_ELEMENTS_H_
#define LIBSEMIGROUPS_SRC_ELEMENTS_H_

#include <math.h>

#include <algorithm>
#include <functional>
#include <iostream>
#include <unordered_set>
#include <vector>

#include "blocks.h"
#include "libsemigroups-debug.h"
#include "recvec.h"
#include "semiring.h"

// It appears that GCC 4.8.1 (at least) has a bug that causes an internal
// compiler error when trying to compile templated static thread_local storage,
// see https://gcc.gnu.org/bugzilla/show_bug.cgi?id=58624
#ifdef __GNUC_PREREQ
#if !(__GNUC_PREREQ(4, 9))
#define DO_NOT_USE_THREAD_LOCAL
#endif
#elif defined(__clang__)
#if !(__has_feature(cxx_thread_local))
#define DO_NOT_USE_THREAD_LOCAL
#endif
#endif

namespace libsemigroups {

  class Element {
   public:
    enum elm_t {
      RWSE = 0,
      NOT_RWSE = 1
    };

    explicit Element(elm_t type = Element::elm_t::NOT_RWSE)
        : _hash_value(UNDEFINED), _type(type) {}

    virtual ~Element() {}

    elm_t get_type() const {
      return _type;
    }

    virtual bool operator==(const Element& that) const = 0;

    virtual bool operator<(const Element& that) const = 0;

    virtual size_t complexity() const = 0;

    virtual size_t degree() const = 0;

    inline size_t hash_value() const {
      if (_hash_value == UNDEFINED) {
        this->cache_hash_value();
      }
      return this->_hash_value;
    }

    virtual Element* identity() const = 0;

    virtual Element* really_copy(size_t increase_deg_by = 0) const = 0;

    virtual void copy(Element const* x) = 0;

    virtual void swap(Element* x) = 0;

    virtual void really_delete() = 0;

    virtual void redefine(Element const* x, Element const* y) {
      redefine(x, y, 0);
    }

    virtual void
    redefine(Element const* x, Element const* y, size_t const& thread_id) {
      (void) thread_id;
      redefine(x, y);
    }

    struct Equal {
      size_t operator()(Element const* x, Element const* y) const {
        return *x == *y;
      }
    };

    struct Hash {
      size_t operator()(Element const* x) const {
        return x->hash_value();
      }
    };

   protected:
    virtual void cache_hash_value() const = 0;

    void reset_hash_value() const {
      _hash_value = UNDEFINED;
    }

    static size_t const UNDEFINED;

    mutable size_t _hash_value;

   private:
    elm_t _type;
  };

  template <typename TValueType, class TSubclass>
  class ElementWithVectorData : public Element {
   public:
    ElementWithVectorData()
        : Element(), _vector(new std::vector<TValueType>()) {}

    explicit ElementWithVectorData(std::vector<TValueType>* vector)
        : Element(), _vector(vector) {}

    explicit ElementWithVectorData(std::vector<TValueType> const& vector)
        : ElementWithVectorData(new std::vector<TValueType>(vector)) {}

    inline TValueType operator[](size_t pos) const {
      return (*_vector)[pos];
    }

    inline TValueType at(size_t pos) const {
      return _vector->at(pos);
    }

    bool operator==(Element const& that) const override {
      return *(static_cast<TSubclass const&>(that)._vector) == *(this->_vector);
    }

    bool operator<(Element const& that) const override {
      TSubclass const& ewvd = static_cast<TSubclass const&>(that);
      if (this->_vector->size() != ewvd._vector->size()) {
        return this->_vector->size() < ewvd._vector->size();
      }
      for (size_t i = 0; i < this->_vector->size(); i++) {
        if ((*this)[i] != ewvd[i]) {
          return (*this)[i] < ewvd[i];
        }
      }
      return false;
    }

    Element* really_copy(size_t increase_deg_by = 0) const override {
      LIBSEMIGROUPS_ASSERT(increase_deg_by == 0);
      (void) increase_deg_by;
      std::vector<TValueType>* vector(new std::vector<TValueType>(*_vector));
      TSubclass*               copy = new TSubclass(vector);
      copy->_hash_value             = this->_hash_value;
      return copy;
    }

    void copy(Element const* x) override {
      LIBSEMIGROUPS_ASSERT(x->degree() == this->degree());
      ElementWithVectorData const* xx
          = static_cast<ElementWithVectorData const*>(x);
      _vector->assign(xx->_vector->cbegin(), xx->_vector->cend());
      this->_hash_value = xx->_hash_value;
    }

    void swap(Element* x) override {
      LIBSEMIGROUPS_ASSERT(x->degree() == this->degree());
      ElementWithVectorData* xx = static_cast<ElementWithVectorData*>(x);
      _vector->swap(*(xx->_vector));
      std::swap(this->_hash_value, xx->_hash_value);
    }

    void really_delete() override {
      delete _vector;
    }

    inline typename std::vector<TValueType>::iterator begin() const {
      return _vector->begin();
    }

    inline typename std::vector<TValueType>::iterator end() const {
      return _vector->end();
    }

    inline typename std::vector<TValueType>::iterator cbegin() const {
      return _vector->cbegin();
    }

    inline typename std::vector<TValueType>::iterator cend() const {
      return _vector->cend();
    }

   protected:
    // Cannot declare cache_hash_value here, since PBR's are vectors of
    // vectors, and there is not std::hash<vector<whatever>>.
    template <typename T>
    static inline size_t vector_hash(std::vector<T> const* vec) {
      size_t seed = 0;
      for (auto const& x : *vec) {
        seed ^= std::hash<T>{}(x) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
      }
      return seed;
    }

    std::vector<TValueType>* _vector;
  };

  template <typename TValueType, class TSubclass>
  class ElementWithVectorDataDefaultHash
      : public ElementWithVectorData<TValueType, TSubclass> {
    using ElementWithVectorData<TValueType, TSubclass>::ElementWithVectorData;

   protected:
    void cache_hash_value() const override {
      this->_hash_value = this->vector_hash(this->_vector);
    }
  };

  template <typename TValueType, typename TSubclass>
  class PartialTransformation
      : public ElementWithVectorDataDefaultHash<TValueType, TSubclass> {
   public:
    using ElementWithVectorDataDefaultHash<TValueType, TSubclass>::
        ElementWithVectorDataDefaultHash;

    size_t complexity() const override {
      return this->_vector->size();
    }

    size_t degree() const override {
      return this->_vector->size();
    }

    size_t crank() const {
      _lookup.clear();
      _lookup.resize(degree(), false);
      size_t r = 0;
      for (auto const& x : *(this->_vector)) {
        if (x != UNDEFINED && !_lookup[x]) {
          _lookup[x] = true;
          r++;
        }
      }
      return r;
    }

    Element* identity() const override {
      std::vector<TValueType>* vector(new std::vector<TValueType>());
      vector->reserve(this->degree());
      for (size_t i = 0; i < this->degree(); i++) {
        vector->push_back(i);
      }
      return new TSubclass(vector);
    }

    static TValueType const UNDEFINED;

   private:
// Used for determining rank
#ifdef DO_NOT_USE_THREAD_LOCAL
    static std::vector<bool> _lookup;
#else
    static thread_local std::vector<bool> _lookup;
#endif
  };

  template <typename TValueType, typename TSubclass>
#ifndef DO_NOT_USE_THREAD_LOCAL
  thread_local
#endif
      std::vector<bool>
          PartialTransformation<TValueType, TSubclass>::_lookup
      = std::vector<bool>();

  template <typename TValueType, typename TSubclass>
  TValueType const PartialTransformation<TValueType, TSubclass>::UNDEFINED
      = std::numeric_limits<TValueType>::max();

  template <typename T>
  class Transformation : public PartialTransformation<T, Transformation<T>> {
   public:
    using PartialTransformation<T, Transformation<T>>::PartialTransformation;

    Element* really_copy(size_t increase_deg_by = 0) const override {
      Transformation<T>* copy
          = new Transformation<T>(new std::vector<T>(*this->_vector));
      if (increase_deg_by == 0) {
        copy->_hash_value = this->_hash_value;
      } else {
        size_t n = copy->_vector->size();
        copy->_vector->reserve(n + increase_deg_by);
        for (size_t i = n; i < n + increase_deg_by; i++) {
          copy->_vector->push_back(i);
        }
      }
      return copy;
    }

    void redefine(Element const* x, Element const* y) override {
      LIBSEMIGROUPS_ASSERT(x->degree() == y->degree());
      LIBSEMIGROUPS_ASSERT(x->degree() == this->degree());
      LIBSEMIGROUPS_ASSERT(x != this && y != this);
      Transformation<T> const* xx(static_cast<Transformation<T> const*>(x));
      Transformation<T> const* yy(static_cast<Transformation<T> const*>(y));
      size_t const             n = this->_vector->size();
      for (T i = 0; i < n; i++) {
        (*this->_vector)[i] = (*yy)[(*xx)[i]];
      }
      this->reset_hash_value();
    }

   protected:
    void cache_hash_value() const override {
      size_t seed = 0;
      size_t deg  = this->_vector->size();
      for (auto const& val : *(this->_vector)) {
        seed *= deg;
        seed += val;
      }
      this->_hash_value = seed;
    }
  };

  template <typename T>
  class PartialPerm : public PartialTransformation<T, PartialPerm<T>> {
   public:
    using PartialTransformation<T, PartialPerm<T>>::PartialTransformation;
    using PartialTransformation<T, PartialPerm<T>>::UNDEFINED;

    explicit PartialPerm(std::vector<T> const& dom,
                         std::vector<T> const& ran,
                         size_t                deg)
        : PartialTransformation<T, PartialPerm<T>>() {
      LIBSEMIGROUPS_ASSERT(dom.size() == ran.size());
      LIBSEMIGROUPS_ASSERT(dom.empty()
                           || deg >= *std::max_element(dom.begin(), dom.end()));

      this->_vector->resize(deg + 1, UNDEFINED);
      for (size_t i = 0; i < dom.size(); i++) {
        (*this->_vector)[dom[i]] = ran[i];
      }
    }

    bool operator<(const Element& that) const override {
      auto pp_this = static_cast<const PartialPerm<T>*>(this);
      auto pp_that = static_cast<const PartialPerm<T>&>(that);

      size_t deg_this = pp_this->degree();
      for (auto it = pp_this->_vector->end() - 1;
           it >= pp_this->_vector->begin();
           it--) {
        if (*it == UNDEFINED) {
          deg_this--;
        } else {
          break;
        }
      }
      size_t deg_that = pp_that.degree();
      for (auto it = pp_that._vector->end() - 1;
           it >= pp_that._vector->begin() && deg_that >= deg_this;
           it--) {
        if (*it == UNDEFINED) {
          deg_that--;
        } else {
          break;
        }
      }

      if (deg_this != deg_that) {
        return deg_this < deg_that;
      }

      for (size_t i = 0; i < deg_this; i++) {
        if ((*pp_this)[i] != pp_that[i]) {
          return (*pp_this)[i] == UNDEFINED
                 || (pp_that[i] != UNDEFINED && (*pp_this)[i] < pp_that[i]);
        }
      }
      return false;
    }

    Element* really_copy(size_t increase_deg_by = 0) const override {
      PartialPerm<T>* copy
          = new PartialPerm<T>(new std::vector<T>(*this->_vector));
      if (increase_deg_by == 0) {
        copy->_hash_value = this->_hash_value;
      } else {
        size_t n = copy->_vector->size();
        copy->_vector->reserve(n + increase_deg_by);
        for (size_t i = n; i < n + increase_deg_by; i++) {
          copy->_vector->push_back(UNDEFINED);
        }
      }
      return copy;
    }

    void redefine(Element const* x, Element const* y) override {
      LIBSEMIGROUPS_ASSERT(x->degree() == y->degree());
      LIBSEMIGROUPS_ASSERT(x->degree() == this->degree());
      LIBSEMIGROUPS_ASSERT(x != this && y != this);
      PartialPerm<T> const* xx(static_cast<PartialPerm<T> const*>(x));
      PartialPerm<T> const* yy(static_cast<PartialPerm<T> const*>(y));
      size_t const          n = this->degree();
      for (T i = 0; i < n; i++) {
        (*this->_vector)[i]
            = ((*xx)[i] == UNDEFINED ? UNDEFINED : (*yy)[(*xx)[i]]);
      }
      this->reset_hash_value();
    }

    size_t crank() const {
      return this->_vector->size() - std::count(this->_vector->cbegin(),
                                                this->_vector->cend(),
                                                UNDEFINED);
    }
  };



  class Bipartition
      : public ElementWithVectorDataDefaultHash<u_int32_t, Bipartition> {
    // TODO add more explanation to the doc here
   public:
    explicit Bipartition(size_t degree)
        : ElementWithVectorDataDefaultHash<u_int32_t, Bipartition>(),
          _nr_blocks(Bipartition::UNDEFINED),
          _nr_left_blocks(Bipartition::UNDEFINED),
          _trans_blocks_lookup(),
          _rank(Bipartition::UNDEFINED) {
      this->_vector->resize(2 * degree);
    }

    explicit Bipartition(std::vector<u_int32_t>* blocks)
        : ElementWithVectorDataDefaultHash<u_int32_t, Bipartition>(blocks),
          _nr_blocks(Bipartition::UNDEFINED),
          _nr_left_blocks(Bipartition::UNDEFINED),
          _trans_blocks_lookup(),
          _rank(Bipartition::UNDEFINED) {}

    explicit Bipartition(std::vector<u_int32_t> const& blocks)
        : Bipartition(new std::vector<u_int32_t>(blocks)) {}

    // TODO another constructor that accepts an actual partition

    size_t complexity() const override;

    size_t degree() const override;

    Element* identity() const override;

    void redefine(Element const* x,
                  Element const* y,
                  size_t const&  thread_id) override;

    size_t rank();

    u_int32_t const_nr_blocks() const;

    u_int32_t nr_blocks();

    u_int32_t nr_left_blocks();

    u_int32_t nr_right_blocks();

    bool is_transverse_block(size_t index);

    Blocks* left_blocks();

    Blocks* right_blocks();

    inline void set_nr_blocks(size_t nr_blocks) {
      LIBSEMIGROUPS_ASSERT(_nr_blocks == Bipartition::UNDEFINED
                           || _nr_blocks == nr_blocks);
      _nr_blocks = nr_blocks;
    }

    inline void set_nr_left_blocks(size_t nr_left_blocks) {
      LIBSEMIGROUPS_ASSERT(_nr_left_blocks == Bipartition::UNDEFINED
                           || _nr_left_blocks == nr_left_blocks);
      _nr_left_blocks = nr_left_blocks;
    }

    inline void set_rank(size_t rank) {
      LIBSEMIGROUPS_ASSERT(_rank == Bipartition::UNDEFINED || _rank == rank);
      _rank = rank;
    }

   private:
    u_int32_t fuseit(std::vector<u_int32_t>& fuse, u_int32_t pos);
    void init_trans_blocks_lookup();

    static std::vector<std::vector<u_int32_t>> _fuse;
    static std::vector<std::vector<u_int32_t>> _lookup;

    size_t            _nr_blocks;
    size_t            _nr_left_blocks;
    std::vector<bool> _trans_blocks_lookup;
    size_t            _rank;

    static u_int32_t const UNDEFINED;
  };

  template <typename TValueType, class TSubclass>
  class MatrixOverSemiringBase
      : public ElementWithVectorDataDefaultHash<TValueType, TSubclass> {
   public:
    MatrixOverSemiringBase(std::vector<TValueType>*    matrix,
                           Semiring<TValueType> const* semiring)
        : ElementWithVectorDataDefaultHash<TValueType, TSubclass>(matrix),
          _degree(sqrt(matrix->size())),
          _semiring(semiring) {
      LIBSEMIGROUPS_ASSERT(semiring != nullptr);
      LIBSEMIGROUPS_ASSERT(!matrix->empty());
      LIBSEMIGROUPS_ASSERT(matrix->size() == _degree * _degree);
    }

    MatrixOverSemiringBase(std::vector<std::vector<TValueType>> const& matrix,
                           Semiring<TValueType> const*                 semiring)
        : ElementWithVectorDataDefaultHash<TValueType, TSubclass>(),
          _degree(matrix[0].size()),
          _semiring(semiring) {
      LIBSEMIGROUPS_ASSERT(semiring != nullptr);
      LIBSEMIGROUPS_ASSERT(!matrix.empty());
      LIBSEMIGROUPS_ASSERT(all_of(
          matrix.begin(), matrix.end(), [matrix](std::vector<TValueType> row) {
            return row.size() == matrix.size();
          }));

      this->_vector->reserve(matrix.size() * matrix.size());
      for (auto const& row : matrix) {
        this->_vector->insert(this->_vector->end(), row.begin(), row.end());
      }
    }

    Semiring<TValueType> const* semiring() const {
      return _semiring;
    }

    size_t complexity() const override {
      return pow(this->degree(), 3);
    }

    size_t degree() const override {
      return _degree;
    }

    Element* identity() const override {
      std::vector<TValueType>* vec(new std::vector<TValueType>());
      vec->resize(this->_vector->size(), _semiring->zero());
      size_t n = this->degree();
      for (auto it = vec->begin(); it < vec->end(); it += n + 1) {
        (*it) = _semiring->one();
      }
      return new TSubclass(vec, _semiring);
    }

    Element* really_copy(size_t increase_deg_by = 0) const override {
      LIBSEMIGROUPS_ASSERT(increase_deg_by == 0);
      (void) increase_deg_by;
      MatrixOverSemiringBase* copy = static_cast<MatrixOverSemiringBase*>(
          ElementWithVectorDataDefaultHash<TValueType,
                                           TSubclass>::really_copy());
      LIBSEMIGROUPS_ASSERT(copy->_semiring == nullptr
                           || copy->_semiring == this->_semiring);
      copy->_semiring = _semiring;
      return copy;
    }

    void redefine(Element const* x, Element const* y) override {
      auto xx = static_cast<MatrixOverSemiringBase const*>(x);
      auto yy = static_cast<MatrixOverSemiringBase const*>(y);
      LIBSEMIGROUPS_ASSERT(xx->degree() == yy->degree());
      LIBSEMIGROUPS_ASSERT(xx->degree() == this->degree());
      LIBSEMIGROUPS_ASSERT(xx != this && yy != this);
      // It can be that the elements are defined over semirings that are
      // distinct in memory but equal (for example, when one element comes
      // from a semigroup and another from an ideal of that semigroup).
      // LIBSEMIGROUPS_ASSERT(xx->semiring() == yy->semiring() &&
      // xx->semiring() == this->semiring());
      // TODO verify that x, y, and this are defined over the same semiring.
      size_t deg = this->degree();

      for (size_t i = 0; i < deg; i++) {
        for (size_t j = 0; j < deg; j++) {
          int64_t v = _semiring->zero();
          for (size_t k = 0; k < deg; k++) {
            v = _semiring->plus(
                v, _semiring->prod((*xx)[i * deg + k], (*yy)[k * deg + j]));
          }
          (*this->_vector)[i * deg + j] = v;
        }
      }
      after();  // post process this
      this->reset_hash_value();
    }

   protected:
    friend class ElementWithVectorData<TValueType, TSubclass>;
    explicit MatrixOverSemiringBase(std::vector<TValueType>* matrix)
        : ElementWithVectorDataDefaultHash<TValueType, TSubclass>(matrix),
          _degree(sqrt(matrix->size())),
          _semiring(nullptr) {}

   private:
    // A function applied after redefinition
    virtual inline void         after() {}
    size_t                      _degree;
    Semiring<TValueType> const* _semiring;
  };

  template <typename TValueType>
  class MatrixOverSemiring
      : public MatrixOverSemiringBase<TValueType,
                                      MatrixOverSemiring<TValueType>> {
    friend class ElementWithVectorData<TValueType,
                                       MatrixOverSemiring<TValueType>>;
    using MatrixOverSemiringBase<TValueType, MatrixOverSemiring<TValueType>>::
        MatrixOverSemiringBase;
  };

  class ProjectiveMaxPlusMatrix
      : public MatrixOverSemiringBase<int64_t, ProjectiveMaxPlusMatrix> {
   public:
    ProjectiveMaxPlusMatrix(std::vector<int64_t>*    matrix,
                            Semiring<int64_t> const* semiring)
        : MatrixOverSemiringBase(matrix, semiring) {
      after();  // this is to put the matrix in normal form
    }

    ProjectiveMaxPlusMatrix(std::vector<std::vector<int64_t>> const& matrix,
                            Semiring<int64_t> const*                 semiring)
        : MatrixOverSemiringBase(matrix, semiring) {
      after();  // this is to put the matrix in normal form
    }

   private:
    friend class ElementWithVectorData<int64_t, ProjectiveMaxPlusMatrix>;
    explicit ProjectiveMaxPlusMatrix(std::vector<int64_t>* matrix)
        : MatrixOverSemiringBase(matrix) {}

    // A function applied after redefinition
    inline void after() final {
      int64_t norm = *std::max_element(_vector->begin(), _vector->end());
      for (auto& x : *_vector) {
        if (x != LONG_MIN) {
          x -= norm;
        }
      }
    }
  };

  class BooleanMat : public MatrixOverSemiringBase<bool, BooleanMat> {
   public:
    explicit BooleanMat(std::vector<bool>* matrix)
        : MatrixOverSemiringBase<bool, BooleanMat>(matrix, _semiring) {}

    explicit BooleanMat(std::vector<std::vector<bool>> const& matrix)
        : MatrixOverSemiringBase<bool, BooleanMat>(matrix,
                                                   BooleanMat::_semiring) {}

    void redefine(Element const* x, Element const* y) final;

    // There is a specialization of std::hash for std::vector<bool> but for
    // some reason it causes a dramatic slow down in some of the benchmarks if
    // it is used by cache_hash_value below. So, we leave this commented out as
    // a reminder not to use it.

    // protected:
    // void cache_hash_value() const override {
    //  this->_hash_value = std::hash<std::vector<bool>>{}(*this->_vector);
    // }

   private:
    // The next constructor only exists to allow the identity method for
    // MatrixOverSemiringBase to work.
    friend class MatrixOverSemiringBase<bool, BooleanMat>;
    explicit BooleanMat(std::vector<bool>*    matrix,
                        Semiring<bool> const* semiring)
        : MatrixOverSemiringBase<bool, BooleanMat>(matrix, semiring) {}

    static BooleanSemiring const* const _semiring;
  };

  class PBR : public ElementWithVectorData<std::vector<u_int32_t>, PBR> {
   public:
    using ElementWithVectorData<std::vector<u_int32_t>,
                                PBR>::ElementWithVectorData;

    size_t complexity() const override;

    size_t degree() const override;

    Element* identity() const override;

    void redefine(Element const* x,
                  Element const* y,
                  size_t const&  thread_id) override;

   protected:
    void cache_hash_value() const override;

   private:
    void unite_rows(RecVec<bool>& out,
                    RecVec<bool>& tmp,
                    size_t const& vertex1,
                    size_t const& vertex2);

    void x_dfs(std::vector<bool>& x_seen,
               std::vector<bool>& y_seen,
               RecVec<bool>&      tmp,
               u_int32_t const&   n,
               u_int32_t const&   i,
               PBR const* const   x,
               PBR const* const   y,
               size_t const&      adj);

    void y_dfs(std::vector<bool>& x_seen,
               std::vector<bool>& y_seen,
               RecVec<bool>&      tmp,
               u_int32_t const&   n,
               u_int32_t const&   i,
               PBR const* const   x,
               PBR const* const   y,
               size_t const&      adj);

    static std::vector<std::vector<bool>> _x_seen;
    static std::vector<std::vector<bool>> _y_seen;
    static std::vector<RecVec<bool>>      _out;
    static std::vector<RecVec<bool>>      _tmp;
  };

  template <typename T> static inline void really_delete_cont(T cont) {
    for (Element const* x : cont) {
      const_cast<Element*>(x)->really_delete();
      delete x;
    }
  }

  template <typename T> static inline void really_delete_cont(T* cont) {
    for (Element const* x : *cont) {
      const_cast<Element*>(x)->really_delete();
      delete x;
    }
    delete cont;
  }
}  // namespace libsemigroups
#endif  // LIBSEMIGROUPS_SRC_ELEMENTS_H_