pbr.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2019-2025 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 PBR class.
 
#ifndef LIBSEMIGROUPS_PBR_HPP_
#define LIBSEMIGROUPS_PBR_HPP_
 
#include <cstddef>           // for size_t
#include <cstdint>           // for uint32_t, int32_t
#include <initializer_list>  // for initializer_list
#include <iosfwd>            // for ostream, ostringstream
#include <string>            // for string
#include <type_traits>       // for forward
#include <utility>           // for forward
#include <vector>            // for vector, operator<, operator==, allocator
 
#include "adapters.hpp"  // for Hash
#include "types.hpp"     // for enable_if_is_same
 
namespace libsemigroups {


  class PBR {
   public:
    template <typename T>
    using vector_type = std::vector<std::vector<T>> const&;

    template <typename T>
    using initializer_list_type = std::initializer_list<std::vector<T>> const&;

    PBR() = delete;

    PBR(PBR const&) = default;

    PBR(PBR&&) = default;

    PBR& operator=(PBR const&) = default;

    PBR& operator=(PBR&&) = default;

    explicit PBR(vector_type<uint32_t> x);

    explicit PBR(initializer_list_type<uint32_t> x);

    explicit PBR(size_t n);

    PBR(initializer_list_type<int32_t> left,
        initializer_list_type<int32_t> right);

    PBR(vector_type<int32_t> left, vector_type<int32_t> right);

    size_t degree() const noexcept;

    size_t number_of_points() const noexcept;

    void product_inplace_no_checks(PBR const& x,
                                   PBR const& y,
                                   size_t     thread_id = 0);

    void product_inplace(PBR const& x, PBR const& y, size_t thread_id = 0);

    // TODO(later): a better explanation of what equality means for PBRs
    bool operator==(PBR const& that) const {
      return _vector == that._vector;
    }

    bool operator<(PBR const& that) const {
      return _vector < that._vector;
    }

    std::vector<uint32_t>& operator[](size_t i) {
      return _vector[i];
    }

    std::vector<uint32_t> const& operator[](size_t i) const {
      return _vector[i];
    }

    std::vector<uint32_t>& at(size_t i);

    std::vector<uint32_t> const& at(size_t i) const;

    // not noexcept because Hash<T>::operator() isn't
    size_t hash_value() const {
      return Hash<std::vector<std::vector<uint32_t>>>()(_vector);
    }

    friend std::ostringstream& operator<<(std::ostringstream&, PBR const&);

    friend std::ostream& operator<<(std::ostream&, PBR const&);
 
   private:
    std::vector<std::vector<uint32_t>> _vector;
  };

  namespace pbr {
    PBR one(size_t n);

    PBR one(PBR const& x);
 
    // TODO(later) analogue of bipartition::underlying_partition?

    void throw_if_not_even_length(PBR const& x);

    void throw_if_entry_out_of_bounds(PBR const& x);

    void throw_if_adjacencies_unsorted(PBR const& x);

    void inline throw_if_invalid(PBR const& x) {
      throw_if_not_even_length(x);
      throw_if_entry_out_of_bounds(x);
      throw_if_adjacencies_unsorted(x);
    }
 
  }  // namespace pbr
 
  // end pbr_group
 
  namespace detail {
    std::vector<std::vector<uint32_t>>
    process_left_right(PBR::vector_type<int32_t> left,
                       PBR::vector_type<int32_t> right);
  }

  template <typename Return, typename... T>
  [[nodiscard]] enable_if_is_same<Return, PBR> make(T... args) {
    // TODO(later) throw_if_bad_args
    PBR result(std::forward<T>(args)...);
    pbr::throw_if_invalid(result);
    return result;
  }


  template <typename Return>
  [[nodiscard]] enable_if_is_same<Return, PBR>
  make(PBR::initializer_list_type<uint32_t> args) {
    return make<PBR, decltype(args)>(args);
  }

  template <typename Return>
  [[nodiscard]] enable_if_is_same<Return, PBR>
  make(PBR::initializer_list_type<int32_t> left,
       PBR::initializer_list_type<int32_t> right) {
    return PBR(detail::process_left_right(left, right));
  }

  template <typename Return>
  [[nodiscard]] enable_if_is_same<Return, PBR>
  make(PBR::vector_type<int32_t> left, PBR::vector_type<int32_t> right) {
    return PBR(detail::process_left_right(left, right));
  }

  [[nodiscard]] std::string to_human_readable_repr(PBR const& x);

  PBR operator*(PBR const& x, PBR const& y);

  inline bool operator!=(PBR const& x, PBR const& y) {
    return !(x == y);
  }

  inline bool operator>(PBR const& x, PBR const& y) {
    return y < x;
  }

  inline bool operator<=(PBR const& x, PBR const& y) {
    return x < y || x == y;
  }

  inline bool operator>=(PBR const& x, PBR const& y) {
    return y <= x;
  }
 
  namespace detail {
 
    template <typename T>
    struct IsPBRHelper : std::false_type {};
 
    template <>
    struct IsPBRHelper<PBR> : std::true_type {};
 
  }  // namespace detail

  template <typename T>
  static constexpr bool IsPBR = detail::IsPBRHelper<T>::value;

  // Adapters


  template <>
  struct Complexity<PBR> {
    size_t operator()(PBR const& x) const noexcept {
      return 8 * x.degree() * x.degree() * x.degree();
    }
  };

  template <>
  struct Degree<PBR> {
    size_t operator()(PBR const& x) const noexcept {
      return x.degree();
    }
  };

  template <>
  struct Hash<PBR> {
    size_t operator()(PBR const& x) const {
      return x.hash_value();
    }
  };

  template <>
  struct One<PBR> {
    PBR operator()(PBR const& x) const {
      return pbr::one(x);
    }

    PBR operator()(size_t N = 0) const {
      return pbr::one(N);
    }
  };

  template <>
  struct Product<PBR> {
    void operator()(PBR& xy, PBR const& x, PBR const& y, size_t thread_id = 0) {
      xy.product_inplace_no_checks(x, y, thread_id);
    }
  };

  template <>
  struct IncreaseDegree<PBR> {
    void operator()(PBR&, size_t) {}
  };
 
  // end adapters_pbr_group
 
}  // namespace libsemigroups
#endif  // LIBSEMIGROUPS_PBR_HPP_