bipart.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2021-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 Bipartition and Blocks classes.
 
#ifndef LIBSEMIGROUPS_BIPART_HPP_
#define LIBSEMIGROUPS_BIPART_HPP_
 
// TODO(2)
// * benchmarks
// * use Duf/Suf where possible (later?)
// * template like transformations/pperms etc (later?)
 
#include <algorithm>         // for max
#include <cstddef>           // for size_t
#include <cstdint>           // for uint32_t, int32_t
#include <cstdlib>           // for abs
#include <initializer_list>  // for initializer_list
#include <string_view>       // for string_view
#include <type_traits>       // for decay_t, false_type, is_signed, true_type
#include <unordered_set>     // for unordered_set
#include <vector>            // for vector
 
#include "adapters.hpp"   // for Hash
#include "debug.hpp"      // for LIBSEMIGROUPS_ASSERT
#include "exception.hpp"  // for LIBSEMIGROUPS_EXCEPTION
#include "types.hpp"      // for enable_if_is_same
 
#include "detail/fmt.hpp"
 
namespace libsemigroups {
 
  // Forward decls
  class Bipartition;
  class Blocks;

  namespace blocks {
    void throw_if_invalid(Blocks const& x);

    [[nodiscard]] std::vector<std::vector<int32_t>>
    underlying_partition(Blocks const& x);
 
  }  // namespace blocks

  namespace bipartition {
    [[nodiscard]] Bipartition one(Bipartition const& f);

    [[nodiscard]] std::vector<std::vector<int32_t>>
    underlying_partition(Bipartition const& x);

    void throw_if_invalid(Bipartition const& x);
 
  }  // namespace bipartition
 
  namespace detail {
 
    template <typename T>
    struct IsBipartitionHelper : std::false_type {};
 
    template <>
    struct IsBipartitionHelper<Bipartition> : std::true_type {};
 
  }  // namespace detail

  template <typename T>
  static constexpr bool IsBipartition
      = detail::IsBipartitionHelper<std::decay_t<T>>::value;
 
  namespace detail {

    template <typename BipartitionOrBlocks, typename Scalar>
    static void
    throw_if_bad_args(std::vector<std::vector<Scalar>> const& blocks) {
      static_assert(std::is_same_v<BipartitionOrBlocks, Bipartition>
                    || std::is_same_v<BipartitionOrBlocks, Blocks>);
      static_assert(std::is_signed<Scalar>::value,
                    "the 2nd template parameter Scalar must be signed");
      int32_t offset = 2;
      if (!IsBipartition<BipartitionOrBlocks>) {
        offset = 1;
      }
      int32_t                    m   = 0;
      int32_t                    deg = 0;
      std::unordered_set<Scalar> vals;
      for (size_t i = 0; i < blocks.size(); ++i) {
        auto const& block = blocks[i];
        if (block.empty()) {
          LIBSEMIGROUPS_EXCEPTION("the argument (blocks) is invalid, "
                                  "expected all blocks to be non-empty, but "
                                  "found empty block in position {}",
                                  i);
        }
        bool positive = block[0] >= 0;
 
        for (size_t j = 0; j < block.size(); ++j) {
          auto x = block[j];
          vals.insert(x);
          if (x == 0) {
            LIBSEMIGROUPS_EXCEPTION("the argument (blocks) is invalid, "
                                    "expected non-zero values but found 0 in "
                                    "position {} of the block with index {}",
                                    j,
                                    i);
          } else if (!IsBipartition<BipartitionOrBlocks> && positive && x < 0) {
            LIBSEMIGROUPS_EXCEPTION(
                "the argument (blocks) is invalid, expected every value in the "
                "block with index {} to be {}tive, but found {} in position {}",
                i,
                positive ? "posi" : "nega",
                x,
                j);
          }
          x = std::abs(x);
 
          m = std::max(x, m);
          deg++;
        }
      }
 
      if (m >= static_cast<int32_t>(0x40000000)) {
        LIBSEMIGROUPS_EXCEPTION(
            "too many points, expected at most {}, found {}", 0x40000000, m);
      } else if (deg != offset * m || vals.size() != size_t(deg)) {
        std::string range, prefix;
        if (IsBipartition<BipartitionOrBlocks>) {
          prefix = "the union of";
          range  = fmt::format("{{{}, ..., -1, 1, ..., {}}}", -m, m);
        } else {
          prefix
              = "the set consisting of the absolute values of the entries in ";
          range = fmt::format("[1, {}]", m);
        }
        LIBSEMIGROUPS_EXCEPTION("{} the given blocks is not {},"
                                " only {} values were given",
                                prefix,
                                range,
                                deg);
      }
    }

    template <typename BipartitionOrBlocks, typename Scalar>
    static void throw_if_bad_args(
        std::initializer_list<std::vector<Scalar>> const& blocks) {
      std::vector<std::vector<Scalar>> arg(blocks);
      throw_if_bad_args<BipartitionOrBlocks>(arg);
    }

    template <typename BipartitionOrBlocks, typename Scalar>
    static void throw_if_bad_args(std::vector<Scalar> const&) {
      // checks for this argument type are done in throw_if_invalid
    }

    template <typename BipartitionOrBlocks, typename Scalar>
    static void throw_if_bad_args(std::initializer_list<Scalar> const&) {
      // checks for this argument type are done in throw_if_invalid
    }
  }  // namespace detail

  class Blocks {
   private:
    std::vector<uint32_t> _blocks;
    std::vector<bool>     _lookup;
 
   public:
    using lookup_const_iterator = std::vector<bool>::const_iterator;

    using iterator = typename std::vector<uint32_t>::iterator;

    using const_iterator = typename std::vector<uint32_t>::const_iterator;

    Blocks() noexcept = default;

    Blocks(const_iterator first, const_iterator last);

    explicit Blocks(size_t degree) : _blocks(degree), _lookup() {}

    // TODO(0) this should be a make function not a constructor
    explicit Blocks(std::vector<std::vector<int32_t>> const& blocks);

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

    Blocks& operator=(Blocks&&) = default;

    Blocks(Blocks const& copy) = default;

    Blocks(Blocks&& copy) = default;
 
    ~Blocks();

    Blocks& is_transverse_block_no_checks(size_t i, bool val) {
      LIBSEMIGROUPS_ASSERT(i < _lookup.size());
      _lookup[i] = val;
      return *this;
    }

    Blocks& is_transverse_block(size_t i, bool val) {
      throw_if_class_index_out_of_range(i);
      return is_transverse_block_no_checks(i, val);
    }

    [[nodiscard]] bool is_transverse_block_no_checks(size_t index) const {
      LIBSEMIGROUPS_ASSERT(index < _lookup.size());
      return _lookup[index];
    }

    [[nodiscard]] bool is_transverse_block(size_t index) const {
      throw_if_class_index_out_of_range(index);
      return is_transverse_block_no_checks(index);
    }

    Blocks& block_no_checks(size_t i, uint32_t val);

    Blocks& block(size_t i, uint32_t val);

    [[nodiscard]] bool operator==(Blocks const& that) const {
      return _blocks == that._blocks && _lookup == that._lookup;
    }

    [[nodiscard]] bool operator!=(Blocks const& that) const {
      return !(*this == that);
    }

    [[nodiscard]] bool operator<(Blocks const& that) const;
 
    // TODO(2) operator<=, operator>, operator>=

    [[nodiscard]] uint32_t degree() const noexcept {
      return _blocks.size();
    }

    [[nodiscard]] uint32_t number_of_blocks() const noexcept {
      return _lookup.size();
    }

    [[nodiscard]] uint32_t rank() const;

    [[nodiscard]] size_t hash_value() const noexcept;

    [[nodiscard]] lookup_const_iterator cbegin_lookup() const noexcept {
      return _lookup.cbegin();
    }

    [[nodiscard]] lookup_const_iterator cend_lookup() const noexcept {
      return _lookup.cend();
    }

    [[nodiscard]] std::vector<bool> const& lookup() const noexcept {
      return _lookup;
    }

    [[nodiscard]] const_iterator cbegin() const noexcept {
      return _blocks.cbegin();
    }

    [[nodiscard]] const_iterator cend() const noexcept {
      return _blocks.cend();
    }

    [[nodiscard]] uint32_t const& operator[](size_t i) const {
      LIBSEMIGROUPS_ASSERT(i < _blocks.size());
      return _blocks[i];
    }

    [[nodiscard]] uint32_t const& at(size_t i) const {
      // TODO(2) better error
      return _blocks.at(i);
    }
 
   private:
    void throw_if_class_index_out_of_range(size_t index) const;
  };  // class Blocks



  template <typename Return, typename Container>
  [[nodiscard]] enable_if_is_same<Return, Blocks> make(Container const& cont) {
    detail::throw_if_bad_args<Blocks>(cont);
    Blocks result(cont);
    blocks::throw_if_invalid(result);
    return result;
  }

  template <typename Return>
  [[nodiscard]] enable_if_is_same<Return, Blocks>
  make(std::initializer_list<std::vector<int32_t>> const& cont) {
    return make<Blocks, std::initializer_list<std::vector<int32_t>>>(cont);
  }

  [[nodiscard]] std::string to_human_readable_repr(Blocks const&    x,
                                                   std::string_view braces
                                                   = "{}",
                                                   size_t max_width = 72);

  // TODO(2) add more explanation to the doc here
  class Bipartition {
   private:
    mutable size_t            _nr_blocks;
    mutable size_t            _nr_left_blocks;
    mutable std::vector<bool> _trans_blocks_lookup;
    mutable size_t            _rank;
    std::vector<uint32_t>     _vector;
 
   public:
    using iterator = std::vector<uint32_t>::iterator;

    using const_iterator = std::vector<uint32_t>::const_iterator;

    using lookup_const_iterator = typename std::vector<bool>::const_iterator;

    Bipartition();

    explicit Bipartition(size_t N);

    explicit Bipartition(std::vector<uint32_t> const& blocks);

    explicit Bipartition(std::vector<uint32_t>&& blocks);

    Bipartition(std::initializer_list<uint32_t> const& blocks);

    Bipartition(std::initializer_list<std::vector<int32_t>> const& blocks);

    explicit Bipartition(std::vector<std::vector<int32_t>> const& blocks);

    Bipartition(Bipartition const&);

    Bipartition(Bipartition&&);

    Bipartition& operator=(Bipartition const&);

    Bipartition& operator=(Bipartition&&);
 
    ~Bipartition();

    [[nodiscard]] bool operator==(Bipartition const& that) const {
      return _vector == that._vector;
    }

    [[nodiscard]] bool operator<(Bipartition const& that) const {
      return _vector < that._vector;
    }
 
    // TODO(2) other operators <=, >, >=, !=

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

    [[nodiscard]] uint32_t& operator[](size_t i) {
      return _vector[i];
    }

    [[nodiscard]] uint32_t const& operator[](size_t i) const {
      return _vector[i];
    }

    [[nodiscard]] uint32_t& at(size_t i) {
      return _vector.at(i);
    }

    [[nodiscard]] uint32_t const& at(size_t i) const {
      return _vector.at(i);
    }

    [[nodiscard]] const_iterator cbegin() const noexcept {
      return _vector.cbegin();
    }

    [[nodiscard]] const_iterator cend() const noexcept {
      return _vector.cend();
    }

    [[nodiscard]] const_iterator cbegin_left_blocks() const noexcept {
      return cbegin();
    }

    [[nodiscard]] const_iterator cend_left_blocks() const noexcept {
      return cbegin() + degree();
    }

    [[nodiscard]] const_iterator cbegin_right_blocks() const noexcept {
      return cend_left_blocks();
    }

    [[nodiscard]] const_iterator cend_right_blocks() const noexcept {
      return cend();
    }

    [[nodiscard]] size_t degree() const noexcept;

    [[nodiscard]] static Bipartition one(size_t n);

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

    [[nodiscard]] size_t rank() const;

    [[nodiscard]] uint32_t number_of_blocks() const;

    [[nodiscard]] uint32_t number_of_left_blocks() const;

    [[nodiscard]] uint32_t number_of_right_blocks() const;

    [[nodiscard]] bool is_transverse_block_no_checks(size_t index) const;

    [[nodiscard]] bool is_transverse_block(size_t index) const;

    // TODO(2) remove this
    [[nodiscard]] Blocks* left_blocks() const;

    [[nodiscard]] Blocks* left_blocks_no_checks() const;

    // TODO(2) remove this
    [[nodiscard]] Blocks* right_blocks() const;

    [[nodiscard]] Blocks* right_blocks_no_checks() const;

    void set_number_of_blocks(size_t n) noexcept;

    void set_number_of_left_blocks(size_t n) noexcept;

    void set_rank(size_t n) noexcept;

    [[nodiscard]] lookup_const_iterator cbegin_lookup() const noexcept {
      init_trans_blocks_lookup();
      return _trans_blocks_lookup.cbegin();
    }

    [[nodiscard]] lookup_const_iterator cend_lookup() const noexcept {
      init_trans_blocks_lookup();
      return _trans_blocks_lookup.cend();
    }

    [[nodiscard]] std::vector<bool> const& lookup() const noexcept {
      return _trans_blocks_lookup;
    }
 
   private:
    void init_trans_blocks_lookup() const;
  };  // class Bipartition


  template <typename Return, typename Container>
  [[nodiscard]] enable_if_is_same<Return, Bipartition>
  make(Container const& cont) {
    detail::throw_if_bad_args<Bipartition>(cont);
    Bipartition result(cont);
    bipartition::throw_if_invalid(result);
    return result;
  }

  template <typename Return>
  [[nodiscard]] enable_if_is_same<Return, Bipartition>
  make(std::initializer_list<uint32_t> const& cont) {
    return make<Bipartition, std::initializer_list<uint32_t>>(cont);
  }

  template <typename Return>
  [[nodiscard]] enable_if_is_same<Return, Bipartition>
  make(std::initializer_list<std::vector<int32_t>> const& cont) {
    return make<Bipartition, std::initializer_list<std::vector<int32_t>>>(cont);
  }

  [[nodiscard]] std::string to_human_readable_repr(Bipartition const& x,
                                                   std::string_view   braces
                                                   = "{}",
                                                   size_t max_width = 72);

  [[nodiscard]] Bipartition operator*(Bipartition const& x,
                                      Bipartition const& y);

  [[nodiscard]] inline bool operator!=(Bipartition const& x,
                                       Bipartition const& y) {
    return !(x == y);
  }

  [[nodiscard]] inline bool operator<=(Bipartition const& x,
                                       Bipartition const& y) {
    return x < y || x == y;
  }

  [[nodiscard]] inline bool operator>(Bipartition const& x,
                                      Bipartition const& y) {
    return y < x;
  }

  [[nodiscard]] inline bool operator>=(Bipartition const& x,
                                       Bipartition const& y) {
    return y <= x;
  }

  // Adapters

  template <>
  struct Complexity<Bipartition> {
    [[nodiscard]] size_t operator()(Bipartition const& x) const noexcept {
      return x.degree() * x.degree();
    }
  };
 
  template <>
  struct Degree<Bipartition> {
    [[nodiscard]] size_t operator()(Bipartition const& x) const noexcept {
      return x.degree();
    }
  };
 
  template <>
  struct Hash<Bipartition> {
    [[nodiscard]] size_t operator()(Bipartition const& x) const {
      return x.hash_value();
    }
  };
 
  template <>
  struct One<Bipartition> {
    [[nodiscard]] Bipartition operator()(Bipartition const& x) const {
      return (*this)(x.degree());
    }
 
    [[nodiscard]] Bipartition operator()(size_t N = 0) const {
      return Bipartition::one(N);
    }
  };
 
  template <>
  struct Product<Bipartition> {
    void operator()(Bipartition&       xy,
                    Bipartition const& x,
                    Bipartition const& y,
                    size_t             thread_id = 0) {
      xy.product_inplace_no_checks(x, y, thread_id);
    }
  };
 
  template <>
  struct IncreaseDegree<Bipartition> {
    void operator()(Bipartition&, size_t) {}
  };
 
}  // namespace libsemigroups
#endif  // LIBSEMIGROUPS_BIPART_HPP_