semigroups.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/>.
//

#ifndef LIBSEMIGROUPS_SRC_SEMIGROUPS_H_
#define LIBSEMIGROUPS_SRC_SEMIGROUPS_H_

#include <algorithm>
#include <mutex>
#include <string>
#include <thread>
#include <unordered_map>
#include <utility>
#include <vector>

#include "elements.h"
#include "libsemigroups-debug.h"
#include "recvec.h"
#include "report.h"

namespace libsemigroups {

  class RWSE;

  // This object is used for printing information during a computation.  The
  // reason it is global is that we must be able to report from different
  // threads running concurrently.
  extern Reporter glob_reporter;

  typedef size_t letter_t;

  typedef std::vector<letter_t> word_t;

  typedef std::pair<word_t, word_t> relation_t;

  class Semigroup {
    typedef RecVec<bool> flags_t;

    // Type used for indexing elements in a Semigroup, use this when not
    // specifically referring to a position in _elements. It should be possible
    // to change this type and everything will just work, provided the size of
    // the semigroup is less than the maximum value of this type of integer.
    typedef size_t index_t;

    // The elements of a semigroup are stored in _elements, but because of the
    // way add_generators/closure work, it might not be the case that all the
    // words of a given length are contiguous in _elements. Hence we require a
    // means of finding the next element of a given length. In
    // _enumerate_order, the first K_1 values are element_index_t's
    // equal to the positions in _elements of the words of length 1,
    // the next K_2 values are the element_index_t's equal to the positions in
    // _elements of the words of length 2, and so on.
    //
    // This typedef is used to distinguish variables that refer to positions in
    // _elements (element_index_t) from those that refer to positions in
    // _enumerate_order (enumerate_index_t).
    typedef index_t enumerate_index_t;

   public:
    typedef index_t element_index_t;

    typedef RecVec<element_index_t> cayley_graph_t;

   public:
    Semigroup& operator=(Semigroup const& semigroup) = delete;

    explicit Semigroup(std::vector<Element const*> const* gens);

    explicit Semigroup(std::vector<Element*> const* gens)
        : Semigroup(
              reinterpret_cast<std::vector<Element const*> const*>(gens)) {}

    explicit Semigroup(std::vector<Element*>* gens)
        : Semigroup(const_cast<std::vector<Element*> const*>(gens)) {}

    explicit Semigroup(std::vector<Element const*>* gens)
        : Semigroup(const_cast<std::vector<Element const*> const*>(gens)) {}

    explicit Semigroup(std::vector<Element const*> const& gens);

    explicit Semigroup(std::vector<Element*> const& gens)
        : Semigroup(
              reinterpret_cast<std::vector<Element const*> const&>(gens)) {}

    explicit Semigroup(std::initializer_list<Element*> gens)
        : Semigroup(static_cast<std::vector<Element*>>(gens)) {}

    Semigroup(const Semigroup& copy);

   private:
    // Partial copy.
    // \p copy a semigroup
    // \p coll a collection of additional generators
    //
    // This is a constructor for a semigroup generated by the generators of the
    // Semigroup copy and the (possibly) additional generators coll.
    //
    // The relevant parts of the data structure of copy are copied and
    // \c this will be corrupt unless add_generators or closure is called
    // subsequently. This is why this method is private.
    //
    // The same effect can be obtained by copying copy using the copy
    // constructor and then calling add_generators or closure. However,
    // this constructor avoids copying those parts of the data structure of
    // copy that add_generators invalidates anyway. If copy has not been
    // enumerated at all, then these two routes for adding more generators are
    // equivalent.
    Semigroup(Semigroup const& copy, std::vector<Element const*> const* coll);

   public:
    ~Semigroup();

    element_index_t word_to_pos(word_t const& w) const;

    Element* word_to_element(word_t const& w) const;

    size_t current_max_word_length() const {
      if (is_done()) {
        return _lenindex.size() - 2;
      } else if (_nr > _lenindex.back()) {
        return _lenindex.size();
      } else {
        return _lenindex.size() - 1;
      }
    }

    size_t degree() const {
      return _degree;
    }

    size_t nrgens() const {
      return _gens.size();
    }

    Element const* gens(letter_t pos) const {
      LIBSEMIGROUPS_ASSERT(pos < _gens.size());
      return _gens[pos];
    }

    bool is_done() const {
      return (_pos >= _nr);
    }

    bool is_begun() const {
      LIBSEMIGROUPS_ASSERT(_lenindex.size() > 1);
      return (_pos >= _lenindex[1]);
    }

    element_index_t current_position(Element const* x) const {
      if (x->degree() != _degree) {
        return UNDEFINED;
      }

      auto it = _map.find(x);
      return (it == _map.end() ? UNDEFINED : it->second);
    }

    size_t current_size() const {
      return _elements.size();
    }

    size_t current_nrrules() const {
      return _nrrules;
    }

    element_index_t prefix(element_index_t pos) const {
      LIBSEMIGROUPS_ASSERT(pos < _nr);
      return _prefix[pos];
    }

    element_index_t suffix(element_index_t pos) const {
      LIBSEMIGROUPS_ASSERT(pos < _nr);
      return _suffix[pos];
    }

    letter_t first_letter(element_index_t pos) const {
      LIBSEMIGROUPS_ASSERT(pos < _nr);
      return _first[pos];
    }

    letter_t final_letter(element_index_t pos) const {
      LIBSEMIGROUPS_ASSERT(pos < _nr);
      return _final[pos];
    }

    size_t batch_size() const {
      return _batch_size;
    }

    size_t length_const(element_index_t pos) const {
      LIBSEMIGROUPS_ASSERT(pos < _nr);
      return _length[pos];
    }

    size_t length_non_const(element_index_t pos) {
      if (pos >= _nr) {
        enumerate();
      }
      return length_const(pos);
    }

    element_index_t product_by_reduction(element_index_t i,
                                         element_index_t j) const;

    element_index_t fast_product(element_index_t i, element_index_t j) const;

    element_index_t letter_to_pos(letter_t i) const {
      LIBSEMIGROUPS_ASSERT(i < _nrgens);
      return _letter_to_pos[i];
    }

    size_t nridempotents();

    bool is_idempotent(element_index_t pos);

    size_t nrrules() {
      enumerate();
      return _nrrules;
    }

    // FIXME Make _batch_size mutable and this const
    void set_batch_size(size_t batch_size) {
      _batch_size = batch_size;
    }

    void reserve(size_t n);

    size_t size() {
      enumerate();
      return _elements.size();
    }

    bool test_membership(Element const* x) {
      return (position(x) != UNDEFINED);
    }

    element_index_t position(Element const* x);

    element_index_t sorted_position(Element const* x);

    element_index_t position_to_sorted_position(element_index_t pos);

    Element const* at(element_index_t pos);

    Element const* operator[](element_index_t pos) const {
      return _elements[pos];
    }

    Element const* sorted_at(element_index_t pos);

    inline element_index_t right(element_index_t i, letter_t j) {
      enumerate();
      return _right.get(i, j);
    }

    cayley_graph_t* right_cayley_graph_copy() {
      enumerate();
      return new cayley_graph_t(_right);
    }

    inline element_index_t left(element_index_t i, letter_t j) {
      enumerate();
      return _left.get(i, j);
    }

    cayley_graph_t* left_cayley_graph_copy() {
      enumerate();
      return new cayley_graph_t(_left);
    }

    void minimal_factorisation(word_t& word, element_index_t pos);

    word_t* minimal_factorisation(element_index_t pos);

    word_t* minimal_factorisation(Element const* x);

    void factorisation(word_t& word, element_index_t pos) {
      minimal_factorisation(word, pos);
    }

    word_t* factorisation(element_index_t pos) {
      return minimal_factorisation(pos);
    }

    word_t* factorisation(Element const* x);

    void reset_next_relation() {
      _relation_pos = UNDEFINED;
      _relation_gen = 0;
    }

    void next_relation(word_t& relation);

    void enumerate(std::atomic<bool>& killed, size_t limit = LIMIT_MAX);

    void enumerate(size_t limit = LIMIT_MAX) {
      std::atomic<bool> killed(false);
      enumerate(killed, limit);
    }

    void add_generators(std::vector<Element const*> const* coll);

    void add_generators(std::vector<Element*> const* coll) {
      add_generators(
          reinterpret_cast<std::vector<Element const*> const*>(coll));
    }

    void add_generators(std::vector<Element const*> const& coll);

    void add_generators(std::vector<Element*> const& coll) {
      add_generators(
          reinterpret_cast<std::vector<Element const*> const&>(coll));
    }

    void add_generators(std::initializer_list<Element*> coll) {
      add_generators(static_cast<std::vector<Element*>>(coll));
    }

    Semigroup*
    copy_add_generators(std::vector<Element const*> const* coll) const;

    Semigroup* copy_add_generators(std::vector<Element*> const* coll) const {
      return copy_add_generators(
          reinterpret_cast<std::vector<Element const*> const*>(coll));
    }

    void closure(std::vector<Element const*> const* coll);

    void closure(std::vector<Element const*> const& coll);

    void closure(std::vector<Element*> const& coll) {
      closure(reinterpret_cast<std::vector<Element const*> const&>(coll));
    }

    void closure(std::initializer_list<Element*> coll) {
      closure(static_cast<std::vector<Element*>>(coll));
    }

    Semigroup* copy_closure(std::vector<Element const*> const* coll);

    Semigroup* copy_closure(std::vector<Element*> const* gens) {
      return copy_closure(
          reinterpret_cast<std::vector<Element const*> const*>(gens));
    }

    static index_t const UNDEFINED;

    static index_t const LIMIT_MAX;

    //
    void set_report(bool val) const {
      glob_reporter.set_report(val);
    }

    void set_max_threads(size_t nr_threads) {
      unsigned int n
          = static_cast<unsigned int>(nr_threads == 0 ? 1 : nr_threads);
      _max_threads = std::min(n, std::thread::hardware_concurrency());
    }

   private:
    template <typename T, class C> class iterator_base {
     public:
      typedef typename std::vector<Element const*>::size_type  size_type;
      typedef typename std::vector<T>::difference_type         difference_type;
      typedef typename std::vector<Element const*>::value_type value_type;
      typedef typename std::vector<Element const*>::const_reference reference;
      typedef typename std::vector<Element const*>::const_pointer   pointer;
      typedef std::random_access_iterator_tag iterator_category;

      explicit iterator_base(typename std::vector<T>::const_iterator it_vec)
          : _it_vec(it_vec) {}

      iterator_base(iterator_base const& that) : iterator_base(that._it_vec) {}

      iterator_base& operator=(iterator_base const& that) {
        _it_vec = that._it_vec;
        return *this;
      }

      virtual ~iterator_base() {}

      bool operator==(iterator_base const& that) const {
        return _it_vec == that._it_vec;
      }

      bool operator!=(iterator_base const& that) const {
        return _it_vec != that._it_vec;
      }

      bool operator<(iterator_base const& that) const {
        return _it_vec < that._it_vec;
      }

      bool operator>(iterator_base const& that) const {
        return _it_vec > that._it_vec;
      }

      bool operator<=(iterator_base const& that) const {
        return operator<(that) || operator==(that);
      }

      bool operator>=(iterator_base const& that) const {
        return operator>(that) || operator==(that);
      }

      iterator_base operator++(int) {  // postfix
        iterator_base tmp(*this);
        operator++();
        return tmp;
      }

      iterator_base operator--(int) {
        iterator_base tmp(*this);
        operator--();
        return tmp;
      }

      iterator_base operator+(size_type val) const {
        iterator_base out(*this);
        return out += val;
      }

      friend iterator_base operator+(size_type val, iterator_base const& it) {
        return it + val;
      }

      iterator_base operator-(size_type val) const {
        iterator_base out(*this);
        return out -= val;
      }

      reference operator[](size_type pos) const {
        return *(*this + pos);
      }

      iterator_base& operator++() {  // prefix
        ++_it_vec;
        return *this;
      }

      iterator_base& operator--() {
        --_it_vec;
        return *this;
      }

      iterator_base& operator+=(size_type val) {
        _it_vec += val;
        return *this;
      }

      iterator_base& operator-=(size_type val) {
        _it_vec -= val;
        return *this;
      }

      difference_type operator-(iterator_base that) const {
        return _it_vec - that._it_vec;
      }

      reference operator*() const {
        return _methods.indirection(_it_vec);
      }

      pointer operator->() const {
        return _methods.addressof(_it_vec);
      }

     protected:
      typename std::vector<T>::const_iterator _it_vec;
      static C const                          _methods;
    };  // iterator_base definition ends

    struct IteratorMethods {
      IteratorMethods() {}
      typename std::vector<Element const*>::const_reference indirection(
          typename std::vector<Element const*>::const_iterator it) const {
        return *it;
      }
      typename std::vector<Element const*>::const_pointer
      addressof(typename std::vector<Element const*>::const_iterator it) const {
        return &(*it);
      }
    };

    struct IteratorMethodsPairFirst {
      IteratorMethodsPairFirst() {}
      typename std::vector<Element const*>::const_reference indirection(
          typename std::vector<std::pair<Element const*, element_index_t>>::
              const_iterator it) const {
        return (*it).first;
      }

      typename std::vector<Element const*>::const_pointer addressof(
          typename std::vector<std::pair<Element const*, element_index_t>>::
              const_iterator it) const {
        return &((*it).first);
      }
    };

    typedef iterator_base<Element const*, IteratorMethods> const_iterator;
    typedef iterator_base<std::pair<Element const*, element_index_t>,
                          IteratorMethodsPairFirst>
                                                  const_iterator_pair_first;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
    typedef std::reverse_iterator<const_iterator_pair_first>
        const_reverse_iterator_pair_first;

    typedef const_iterator_pair_first         const_iterator_sorted;
    typedef const_iterator_pair_first         const_iterator_idempotents;
    typedef const_reverse_iterator_pair_first const_reverse_iterator_sorted;
    typedef const_reverse_iterator_pair_first
        const_reverse_iterator_idempotents;

   public:
    const_iterator cbegin() const {
      return const_iterator(_elements.cbegin());
    }

    const_iterator begin() const {
      return cbegin();
    }

    const_iterator cend() const {
      return const_iterator(_elements.cend());
    }

    const_iterator end() const {
      return cend();
    }

    const_reverse_iterator crbegin() const {
      return const_reverse_iterator(cend());
    }

    const_reverse_iterator crend() const {
      return const_reverse_iterator(cbegin());
    }

    const_iterator_sorted cbegin_sorted() {
      init_sorted();
      return const_iterator_pair_first(_sorted.cbegin());
    }

    const_iterator_sorted cend_sorted() {
      init_sorted();
      return const_iterator_pair_first(_sorted.cend());
    }

    const_reverse_iterator_sorted crbegin_sorted() {
      init_sorted();
      return const_reverse_iterator_pair_first(cend_sorted());
    }

    const_reverse_iterator_sorted crend_sorted() {
      init_sorted();
      return const_reverse_iterator_pair_first(cbegin_sorted());
    }

    const_iterator_idempotents cbegin_idempotents() {
      init_idempotents();
      return const_iterator_pair_first(_idempotents.cbegin());
    }

    const_iterator_idempotents cend_idempotents() {
      init_idempotents();
      return const_iterator_pair_first(_idempotents.cend());
    }

   private:
    // Expand the data structures in the semigroup with space for nr elements
    void inline expand(index_t nr) {
      _left.add_rows(nr);
      _reduced.add_rows(nr);
      _right.add_rows(nr);
    }

    // Check if an element is the identity, x should be in the position pos
    // of _elements.
    void inline is_one(Element const* x, element_index_t pos) {
      if (!_found_one && *x == *_id) {
        _pos_one   = pos;
        _found_one = true;
      }
    }

    void copy_gens();

    void inline closure_update(element_index_t i,
                               letter_t        j,
                               letter_t        b,
                               element_index_t s,
                               index_t         old_nr,
                               size_t const&   thread_id);

    // Initialise the data member _sorted. We store a list of pairs consisting
    // of an Element* and element_index_t which is sorted on the first entry
    // using the operator< of the Element class. The second component is then
    // inverted (as a permutation) so that we can then find the position of an
    // element in the sorted list of elements.
    void init_sorted();

    typedef std::pair<Element const*, element_index_t> idempotent_value_t;

    // Find the idempotents and store their pointers and positions in a
    // std::pair of type idempotent_value_t.
    void init_idempotents();

    // Find the idempotents in the range [first, last) and store
    // the corresponding std::pair of type idempotent_value_t in the 4th
    // parameter. The parameter threshold is the point, calculated in
    // init_idempotents, at which it is better to simply multiply elements
    // rather than trace in the left/right Cayley graph.
    void idempotents(enumerate_index_t const          first,
                     enumerate_index_t const          last,
                     enumerate_index_t const          threshold,
                     std::vector<idempotent_value_t>& idempotents);

    size_t          _batch_size;
    element_index_t _degree;
    std::vector<std::pair<letter_t, letter_t>> _duplicate_gens;
    std::vector<Element const*>     _elements;
    std::vector<element_index_t>    _enumerate_order;
    std::vector<letter_t>           _final;
    std::vector<letter_t>           _first;
    bool                            _found_one;
    std::vector<Element const*>     _gens;
    Element const*                  _id;
    std::vector<idempotent_value_t> _idempotents;
    bool                            _idempotents_found;
    std::vector<bool>               _is_idempotent;
    cayley_graph_t                  _left;
    std::vector<index_t>            _length;
    std::vector<enumerate_index_t>  _lenindex;
    std::vector<element_index_t>    _letter_to_pos;
    std::unordered_map<Element const*,
                       element_index_t,
                       Element::Hash,
                       Element::Equal>
                                 _map;
    size_t                       _max_threads;
    std::mutex                   _mtx;
    index_t                      _nr;
    letter_t                     _nrgens;
    size_t                       _nrrules;
    enumerate_index_t            _pos;
    element_index_t              _pos_one;
    std::vector<element_index_t> _prefix;
    flags_t                      _reduced;
    letter_t                     _relation_gen;
    enumerate_index_t            _relation_pos;
    cayley_graph_t               _right;
    std::vector<std::pair<Element const*, element_index_t>> _sorted;
    std::vector<element_index_t> _suffix;
    Element*                     _tmp_product;
    size_t                       _wordlen;

    static std::vector<element_index_t> _tmp_inverter;
    static std::vector<bool>            _old_new;
#ifdef LIBSEMIGROUPS_STATS
    size_t _nr_products;
#endif
  };

  typedef Semigroup::cayley_graph_t cayley_graph_t;

  template <typename T, typename C>
  C const Semigroup::iterator_base<T, C>::_methods;
}  // namespace libsemigroups

#endif  // LIBSEMIGROUPS_SRC_SEMIGROUPS_H_