Quelle bipart.hpp Sprache: C

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2021 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(later)
// 1) benchmarks
// 2) use Duf/Suf were possible (later?)
// 3) Template like transformations/pperms etc (later?)

#include <algorithm>         // for max
#include <cstddef>           // for size_t
#include <cstdint>           // for uint32_t, int32_t
#include <initializer_list>  // for initializer_list
#include <stdlib.h>          // for abs
#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 "constants.hpp"            // for UNDEFINED
#include "exception.hpp"            // for LIBSEMIGROUPS_EXCEPTION
#include "libsemigroups/debug.hpp"  // for LIBSEMIGROUPS_ASSERT

namespace libsemigroups {

  //! Defined ``bipart.hpp``.
  //!
  //! Blocks is a class representing signed partitions of the set
  //! \f$\{0, \ldots, n - 1\}\f$.
  //!
  //! It is possible to associate to every Bipartition a pair of blocks,
  //! Bipartition::left_blocks() and Bipartition::right_blocks(), which
  //! determine the Green's \f$\mathscr{L}\f$- and \f$\mathscr{R}\f$-classes of
  //! the Bipartition in the monoid of all bipartitions. This is the purpose of
  //! this class.
  //!
  //! The Blocks class is not currently used widely in ``libsemigroups``
  //! but are used extensively in the GAP package
  //! [Semigroups package for GAP](https://semigroups.github.io/Semigroups/).
  class Blocks final {
   public:
    //! Type for const iterators pointing to the transverse block lookup.
    using lookup_const_iterator = std::vector<bool>::const_iterator;

    //! Type for iterators pointing to the index of the block.
    using iterator = typename std::vector<uint32_t>::iterator;

    //! Type for const iterators pointing to the index of the block.
    using const_iterator = typename std::vector<uint32_t>::const_iterator;

    //! Constructs a blocks object of size 0.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    //!
    //! \parameters
    //! (None)
    Blocks() noexcept = default;

    //! Constructs a blocks object from iterators.
    //!
    //! The degree of the blocks object constructed is `last - first / 2`.
    //!
    //! \param first the index of the block containing the first point
    //! \param last  the index of the block containing the first point
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \complexity
    //! Linear in `last - first`.
    //!
    //! \warning
    //! No checks are made on the validity of the arguments to this function.
    //!
    //! \sa validate(Blocks const&)
    Blocks(const_iterator first, const_iterator last);

    //! Constructs a blocks object of given degree.
    //!
    //! \param degree the degree of the blocks object to construct.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \complexity
    //! Linear in \p degree.
    Blocks(size_t degree) : _blocks(degree), _lookup() {}

    //! Default copy assignment operator.
    Blocks& operator=(Blocks const&) = default;

    //! Default move assignment operator.
    Blocks& operator=(Blocks&&) = default;

    //! Default copy constructor.
    Blocks(Blocks const& copy) = default;

    //! Default move constructor.
    Blocks(Blocks&& copy) = default;

    ~Blocks();

    //! Set whether or not the block containing a point is transverse.
    //!
    //! \param i the point.
    //! \param val whether or not the block containing \p i is transverse.
    //!
    //! \returns
    //! (None)
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \complexity
    //! Constant.
    //!
    //! \warning
    //! No checks are made on the validity of the arguments to this function.
    void set_is_transverse_block(size_t i, bool val) {
      LIBSEMIGROUPS_ASSERT(i < _lookup.size());
      _lookup[i] = val;
    }

    //! Set the block that a point belongs to.
    //!
    //! \param i the point.
    //! \param val the block that \p i should belong to.
    //!
    //! \returns
    //! (None)
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \complexity
    //! At worst linear in `degree()`.
    //!
    //! \warning
    //! No checks are made on the validity of the arguments to this function.
    void set_block(size_t i, uint32_t val) {
      LIBSEMIGROUPS_ASSERT(i < _blocks.size());
      _blocks[i] = val;
      if (val >= _lookup.size()) {
        _lookup.resize(val + 1);
      }
    }

    //! Compare two blocks objects for equality.
    //!
    //! Two Blocks objects are equal if and only if their underlying signed
    //! partitions are equal. It is ok to compare blocks of different
    //! degree with this operator.
    //!
    //! \param that a Blocks instance
    //!
    //! \returns \c true if \c this equals \p that.
    //!
    //! \exceptions
    //! This function only throws if \c std::vector<uint32_t>::operator== does.
    //!
    //! \complexity
    //! At worst linear in `degree()`.
    bool operator==(Blocks const& that) const;

    //! Compare two blocks objects for inequality.
    //!
    //! Two Blocks objects are equal if and only if their underlying signed
    //! partitions are equal. It is ok to compare blocks of different
    //! degree with this operator.
    //!
    //! \param that a Blocks instance
    //!
    //! \returns \c true if \c this equals \p that.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \complexity
    //! At worst linear in `degree()`.
    bool operator!=(Blocks const& that) const {
      return !(*this == that);
    }

    //! Compare two blocks objects for less.
    //!
    //! This operator defines a total order on the set of all Blocks objects
    //! (including those of different degree).
    //!
    //! \param that a Blocks instance
    //!
    //! \returns \c true if \c this is less than \p that.
    //!
    //! \exceptions
    //! This function only throws if \c std::vector<uint32_t>::operator[] does.
    //!
    //!
    //! \complexity
    //! Linear in `degree()`.
    bool operator<(Blocks const& that) const;

    //! Returns the degree of a blocks object.
    //!
    //! The *degree* of a Blocks object is the size of the set of
    //! which it is a partition, or the size of the \p blocks parameter to
    //! Blocks::Blocks.
    //!
    //! \returns The degree of a Blocks object.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \parameters
    //! (None)
    uint32_t degree() const noexcept {
      return _blocks.size();
    }

    //! Check if a block is a transverse block.
    //!
    //! This function returns \c true if the block with index \p index is a
    //! transverse (or signed) block and it returns \c false if it is not
    //! transverse (or unsigned).
    //!
    //! \param index the index of a block
    //!
    //! \returns \c true if the block with index \p index is transverse, and \c
    //! false if not.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    bool is_transverse_block(size_t index) const noexcept {
      LIBSEMIGROUPS_ASSERT(index < _lookup.size());
      return _lookup[index];
    }

    //! Returns the number of blocks in a Blocks object.
    //!
    //! This function returns the number of parts in the partition that
    //! instances of this class represent.
    //!
    //! \returns The number of blocks in a Bipartition object.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! At worst \f$O(2n)\f$ where \f$n\f$ is the degree().
    //!
    //! \parameters
    //! (None)
    uint32_t number_of_blocks() const noexcept {
      return _lookup.size();
    }

    //! Returns the number of transverse blocks.
    //!
    //! This function returns the number of \c true values in
    //! lookup().
    //!
    //! \returns The number of signed (transverse) blocks in \c this.
    //!
    //! \exceptions
    //! Throws if `std::count` throws.
    //!
    //! \complexity
    //! At most linear in the number of blocks.
    //!
    //! \parameters
    //! (None)
    uint32_t rank() const;

    //! Returns a hash value for a Blocks instance.
    //!
    //! This value is recomputed every time this function is called.
    //!
    //! \returns A hash value for a \c this.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Linear in `degree()`.
    //!
    //! \parameters
    //! (None)
    size_t hash_value() const noexcept;

    //! Returns a const iterator pointing to the first transverse
    //! block lookup.
    //!
    //! The value pointed to is \c true if the \c i th block of \c this is a
    //! transverse block; and \c false otherwise.
    //!
    //! \returns A \ref lookup_const_iterator.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    //!
    //! \parameters
    //! (None)
    lookup_const_iterator cbegin_lookup() const noexcept {
      return _lookup.cbegin();
    }

    //! Returns a const iterator pointing to the first transverse
    //! block lookup.
    //!
    //! \sa cbegin_lookup.
    lookup_const_iterator cend_lookup() const noexcept {
      return _lookup.cend();
    }

    //! Returns a const iterator pointing to the index of the first block.
    //!
    //! \returns A value of type \ref const_iterator.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    //!
    //! \parameters
    //! (None)
    const_iterator cbegin() const noexcept {
      return _blocks.cbegin();
    }

    //! Returns a const iterator pointing one past-the-end of the last block.
    //!
    //! \returns A value of type \ref const_iterator
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    //!
    //! \parameters
    //! (None)
    const_iterator cend() const noexcept {
      return _blocks.cend();
    }

    //! Returns a const reference to the index of the block containing a point.
    //!
    //! \param i the point.
    //!
    //! \returns A value const reference to a value of type \c uint32_t.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \complexity
    //! Constant.
    uint32_t const& operator[](size_t i) const {
      LIBSEMIGROUPS_ASSERT(i < _blocks.size());
      return _blocks[i];
    }

   private:
    std::vector<uint32_t> _blocks;
    std::vector<bool>     _lookup;
  };

  //! Validates a Blocks object.
  //!
  //! \param x the blocks object to validate.
  //!
  //! \returns
  //! (None)
  //!
  //! \throws LibsemigroupsException if \p x is invalid.
  void validate(Blocks const& x);

  // Forward decl
  class Bipartition;

  //! Validates a bipartition.
  //!
  //! \param x the bipartition
  //!
  //! \returns
  //! (None)
  //!
  //! \throws LibsemigroupsException if \p x is invalid.
  void validate(Bipartition const& x);

  //! Defined in ``bipart.hpp``.
  //!
  //! A *bipartition* is a partition of the set \f$\{0, ..., 2n - 1\}\f$ for
  //! some non-negative integer \f$n\f$; see the [Semigroups package for GAP
  //! documentation](https://semigroups.github.io/Semigroups/doc/chap3_mj.html)
  //! for more details.  The Bipartition class is more complex (i.e. has more
  //! member functions) than are used in ``libsemigroups`` because they are
  //! used in the GAP package [Semigroups package for
  //! GAP](https://semigroups.github.io/Semigroups/).
  //!
  //! \sa libsemigroups::validate(Bipartition const&).
  // TODO(later) add more explanation to the doc here
  class Bipartition final {
   public:
    //! Type for iterators pointing to the lookup for the blocks of a
    //! bipartition.
    using iterator = std::vector<uint32_t>::iterator;

    //! Type for const iterators pointing to the lookup for the blocks of a
    //! bipartition.
    using const_iterator = std::vector<uint32_t>::const_iterator;

    //! Type for  iterators pointing to the lookup for transverse blocks of a
    //! bipartition.
    using lookup_const_iterator = typename std::vector<bool>::const_iterator;

    //! Constructs an uninitialised bipartition of degree \c 0.
    Bipartition();

    //! Constructs an uninitialised bipartition of given degree.
    //!
    //! \param N the degree of the bipartition.
    explicit Bipartition(size_t N);

    //! Constructs a bipartition from a const reference to blocks lookup.
    //!
    //! The parameter `blocks`:
    //! * is copied;
    //! * must have length \f$2n\f$ for some  positive integer \f$n\f$;
    //! * consist of non-negative integers; and
    //! * have the property that if \f$i\f$, \f$i > 0\f$ occurs in \p blocks,
    //! then \f$i - 1\f$ occurs earlier in \p blocks.  The value of \p block[i]
    //! should represent the index of the block containing \c i.
    //!
    //! None of the conditions above is verified.
    //!
    //! \param blocks a lookup for the blocks of the bipartition being
    //! constructed.
    //!
    //! \sa libsemigroups::validate(Bipartition const&).
    explicit Bipartition(std::vector<uint32_t> const& blocks);

    //! Constructs a bipartition from an rvalue reference to blocks lookup.
    //!
    //! \param blocks a lookup for the blocks of the bipartition being
    //! constructed.
    //!
    //! \sa Bipartition(std::vector<uint32_t> const&)
    //!  and libsemigroups::validate(Bipartition const&).
    explicit Bipartition(std::vector<uint32_t>&& blocks);

    //! Constructs a bipartition from an initializer list blocks lookup.
    //!
    //! \param blocks a lookup for the blocks of the bipartition being
    //! constructed.
    //!
    //! \sa Bipartition(std::vector<uint32_t> const&)
    //!  and libsemigroups::validate(Bipartition const&).
    Bipartition(std::initializer_list<uint32_t> const& blocks);

    //! Constructs a bipartition from a partition.
    //!
    //! The items in \p blocks should be:
    //! * duplicate-free;
    //! * pairwise disjoint; and
    //! * partition the set \f$\{-n, \ldots,  1\}\cup \{1, \ldots, n\}\f$
    //! for some positive integer \f$n\f$.
    //!
    //! None of these conditions is checked by the constructor.
    //!
    //! \param blocks the partition.
    //!
    //! \sa libsemigroups::validate(Bipartition const&).
    Bipartition(std::initializer_list<std::vector<int32_t>> const& blocks);

    //! Default copy constructor.
    Bipartition(Bipartition const&);

    //! Default move constructor.
    Bipartition(Bipartition&&);

    //! Default copy assignment operator.
    Bipartition& operator=(Bipartition const&);

    //! Default move assignment operator.
    Bipartition& operator=(Bipartition&&);

    ~Bipartition();

    //! Validates the arguments, constructs a bipartition and validates it.
    //!
    //! \tparam T the type of the parameter \p cont
    //!
    //! \param cont either a vector providing a lookup for the blocks of the
    //! bipartition or a vector of vectors (or initializer list).
    //!
    //! \throws LibsemigroupsException if the arguments do not describe a
    //! bipartition.
    //!
    //! \throws LibsemigroupsException if the constructed bipartition is not
    //! valid.
    template <typename T>
    static Bipartition make(T const& cont) {
      validate_args(cont);
      Bipartition result(cont);
      validate(result);
      return result;
    }

    //! Validates the arguments, constructs a bipartition and validates it.
    //!
    //! See make(T const&) for full details.
    static Bipartition make(std::initializer_list<uint32_t> const& cont) {
      return make<std::initializer_list<uint32_t>>(cont);
    }

    //! Validates the arguments, constructs a bipartition and validates it.
    //!
    //! See make(T const&) for full details.
    static Bipartition
    make(std::initializer_list<std::vector<int32_t>> const& cont) {
      return make<std::initializer_list<std::vector<int32_t>>>(cont);
    }

    //! Compare two bipartitions for equality.
    //!
    //! \param that a Bipartition object
    //!
    //! \returns \c true if \c this equals \p that, and \c false otherwise.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \complexity
    //! At worst linear in degree().
    bool operator==(Bipartition const& that) const {
      return _vector == that._vector;
    }

    //! Compare two bipartitions for less.
    //!
    //! \param that a Bipartition object
    //!
    //! \returns \c true if \c this is less than \p that, and \c false
    //! otherwise.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \complexity
    //! At worst linear in degree().
    bool operator<(Bipartition const& that) const {
      return _vector < that._vector;
    }

    //! Returns a hash value.
    //!
    //! \parameters
    //! (None)
    //!
    //! \returns
    //! A value of \c size_t.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \complexity
    //! Linear in degree().
    // not noexcept because Hash<T>::operator() isn't
    size_t hash_value() const {
      return Hash<std::vector<uint32_t>>()(_vector);
    }

    //! Returns the index of the block containing a value.
    //!
    //! No bound checks are performed on the parameter \p i.
    //!
    //! \param i an integer
    //!
    //! \returns A reference to the index of the block containing \p i.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \complexity
    //! Constant.
    uint32_t& operator[](size_t i) {
      return _vector[i];
    }

    //! Returns the index of the block containing a value.
    //!
    //! No bound checks are performed on the parameter \p i.
    //!
    //! \param i an integer
    //!
    //! \returns A const reference to the index of the block containing \p i.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \complexity
    //! Constant.
    uint32_t const& operator[](size_t i) const {
      return _vector[i];
    }

    //! Returns a reference to the index of the block containing a value.
    //!
    //! \param i an integer
    //!
    //! \returns A reference to the index of the block containing \p i.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \throws std::out_of_range if the parameter \p i is out of range.
    //!
    //! \complexity
    //! Constant.
    uint32_t& at(size_t i) {
      return _vector.at(i);
    }

    //! Returns a const reference to the index of the block containing a value.
    //!
    //! \param i an integer
    //!
    //! \returns A const reference to the index of the block containing \p i.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \throws std::out_of_range if the parameter \p i is out of range.
    //!
    //! \complexity
    //! Constant.
    uint32_t const& at(size_t i) const {
      return _vector.at(i);
    }

    //! Returns a const iterator pointing to the index of the first block.
    //!
    //! \returns A value of type \ref const_iterator.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    //!
    //! \parameters
    //! (None)
    const_iterator cbegin() const noexcept {
      return _vector.cbegin();
    }

    //! Returns a const iterator pointing one passed the last index of the
    //! last block.
    //!
    //! \returns A value of type \ref const_iterator.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    //!
    //! \parameters
    //! (None)
    const_iterator cend() const noexcept {
      return _vector.cend();
    }

    //! Returns a const iterator pointing to the index of the first left
    //! block.
    //!
    //! \returns A value of type \ref const_iterator.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    //!
    //! \parameters
    //! (None)
    const_iterator cbegin_left_blocks() const noexcept {
      return cbegin();
    }

    //! Returns a const iterator pointing one passed the last index of the
    //! last left block.
    //!
    //! \returns A value of type \ref const_iterator.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    //!
    //! \parameters
    //! (None)
    const_iterator cend_left_blocks() const noexcept {
      return cbegin() + degree();
    }

    //! Returns a const iterator pointing to the index of the first right
    //! block.
    //!
    //! \returns A value of type \ref const_iterator.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    //!
    //! \parameters
    //! (None)
    const_iterator cbegin_right_blocks() const noexcept {
      return cend_left_blocks();
    }

    //! Returns a const iterator pointing one passed the last index of the
    //! last right block.
    //!
    //! \returns A value of type \ref const_iterator.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    //!
    //! \parameters
    //! (None)
    const_iterator cend_right_blocks() const noexcept {
      return cend();
    }

    //! Returns the degree of the bipartition.
    //!
    //! A bipartition is of degree \f$n\f$ if it is a partition of
    //! \f$\{0, \ldots, 2n -  1\}\f$.
    //!
    //! \returns A value of type `size_t`.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \parameters
    //! (None)
    size_t degree() const noexcept;

    //! Returns an identity bipartition.
    //!
    //! The *identity bipartition* of degree \f$n\f$ has blocks \f$\{i, -i\}\f$
    //! for all \f$i\in \{0, \ldots, n - 1\}\f$. This member function returns a
    //! new identity bipartition of degree equal to the degree of \c this.
    //!
    //! \returns A newly constructed Bipartition.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \parameters
    //! (None)
    Bipartition identity() const;

    //! Returns an identity bipartition.
    //!
    //! The *identity bipartition* of degree \f$n\f$ has blocks \f$\{i, -i\}\f$
    //! for all \f$i\in \{0, \ldots, n - 1\}\f$. This member function returns a
    //! new identity bipartition of degree equal to \p n.
    //!
    //! \param n the degree of the identity to be returned.
    //!
    //! \returns A newly constructed Bipartition.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    static Bipartition identity(size_t n);

    //! Modify the current bipartition in-place to contain the product of two
    //! bipartitions.
    //!
    //! The parameter \p thread_id can be used some temporary storage is
    //! required to find the product of \p x and \p y.
    //!
    //! \param x the first bipartition to multiply
    //! \param y the second bipartition to multiply
    //! \param thread_id the index of the calling thread (defaults to \c 0)
    //!
    //! \returns
    //! (None)
    //!
    //! \warning
    //! If different threads call this function concurrently with the same
    //! parameter \p thread_id, then bad things will happen.
    void product_inplace(Bipartition const& x,
                         Bipartition const& y,
                         size_t             thread_id = 0);

    //! Returns the number of transverse blocks.
    //!
    //! The *rank* of a bipartition is the number of blocks containing both
    //! positive and negative values.
    //!
    //! \returns A value of type \c size_t.
    //!
    //! \parameters
    //! (None)
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \complexity
    //! \f$O(2n)\f$ where \f$n\f$ is the degree().
    size_t rank();

    //! Returns the number of blocks in a Bipartition.
    //!
    //! This function returns the number of parts in the partition that
    //! instances of this class represent.
    //!
    //! \returns The number of blocks in a Blocks object.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \complexity
    //! At worst \f$O(2n)\f$ where \f$n\f$ is the degree().
    //!
    //! \parameters
    //! (None)
    uint32_t number_of_blocks() const;

    //! Returns the number of blocks containing a positive integer.
    //!
    //! The *left blocks* of a bipartition is the partition of
    //! \f$\{0, \ldots, n - 1\}\f$ induced by the bipartition. This member
    //! function returns the number of blocks in this partition.
    //!
    //! \returns
    //! A value of type \c uint32_t.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \complexity
    //! At worst \f$O(n)\f$ where \f$n\f$ is the degree().
    //!
    //! \parameters
    //! (None)
    uint32_t number_of_left_blocks();

    //! Returns the number of blocks containing a negative integer.
    //!
    //! The *right blocks* of a bipartition is the partition of
    //! \f$\{n, \ldots, 2n - 1\}\f$ induced by the bipartition. This member
    //! function returns the number of blocks in this partition.
    //!
    //! \returns
    //! A value of type \c uint32_t.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \complexity
    //! At worst \f$O(n)\f$ where \f$n\f$ is the degree().
    //!
    //! \parameters
    //! (None)
    uint32_t number_of_right_blocks();

    //! Check if a block is a transverse block.
    //!
    //! A block of a biparition is *transverse* if it contains integers less
    //! than and greater than \f$n\f$, which is the degree of the bipartition.
    //! This member function asserts that the parameter \p index is less than
    //! the number of blocks in the bipartition.
    //!
    //! \param index the index of a block
    //!
    //! \returns \c true if the block with index \p index is transverse, and \c
    //! false if not.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \complexity
    //! At worst \f$O(n)\f$ where \f$n\f$ is the degree().
    bool is_transverse_block(size_t index);

    //! Return a pointer to the left blocks of a bipartition.
    //!
    //! The *left blocks* of a bipartition is the partition of
    //! \f$\{0, \ldots, n - 1\}\f$ induced by the bipartition. This member
    //! function returns a Blocks object representing this partition.
    //!
    //! \returns
    //! A pointer to a newly constructed Blocks object.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \complexity
    //! \f$O(n)\f$ where \f$n\f$ is the degree().
    //!
    //! \parameters
    //! (None)
    // TODO(later) remove this
    Blocks* left_blocks();

    //! Return a pointer to the right blocks of a bipartition.
    //!
    //! The *right blocks* of a bipartition is the partition of
    //! \f$\{n, \ldots, 2n - 1\}\f$ induced by the bipartition.
    //!
    //! \returns
    //! A pointer to a newly constructed Blocks object.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \complexity
    //! \f$O(n)\f$ where \f$n\f$ is the degree().
    //!
    //! \parameters
    //! (None)
    // TODO(later) remove this
    Blocks* right_blocks();

    //! Set the number of blocks.
    //!
    //! This function sets the number of blocks of \c this to \p n. No checks
    //! are performed.
    //!
    //! \param n the number of blocks.
    //!
    //! \returns
    //! (None)
    //!
    //! \complexity
    //! Constant.
    //!
    //! \exceptions
    //! \noexcept
    void set_number_of_blocks(size_t n) noexcept;

    //! Set the number of left blocks.
    //!
    //! This function sets the number of left blocks of \c this to \p n. No
    //! checks are performed.
    //!
    //! \param n the number of blocks.
    //!
    //! \returns
    //! (None)
    //!
    //! \complexity
    //! Constant.
    //!
    //! \exceptions
    //! \noexcept
    void set_number_of_left_blocks(size_t n) noexcept;

    //! Set the rank.
    //!
    //! This function sets the \c rank of \c this to \p n. No
    //! checks are performed.
    //!
    //! \param n the rank.
    //!
    //! \returns
    //! (None)
    //!
    //! \complexity
    //! Constant.
    //!
    //! \exceptions
    //! \noexcept
    void set_rank(size_t n) noexcept;

    //! Returns a const iterator pointing to the first transverse
    //! block lookup.
    //!
    //! The value pointed to is \c true if the \c i th block of \c this is a
    //! transverse block; and \c false otherwise.
    //!
    //! \returns A \ref lookup_const_iterator.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    //!
    //! \parameters
    //! (None)
    lookup_const_iterator cbegin_lookup() noexcept {
      init_trans_blocks_lookup();
      return _trans_blocks_lookup.cbegin();
    }

    //! Returns a const iterator pointing to the first transverse
    //! block lookup.
    //!
    //! \sa cbegin_lookup.
    lookup_const_iterator cend_lookup() noexcept {
      init_trans_blocks_lookup();
      return _trans_blocks_lookup.cend();
    }

   private:
    static void validate_args(std::vector<uint32_t> const&) {
      // relevant checks are conducted in validate
    }

    template <typename T>
    static void
    validate_args(std::initializer_list<std::vector<T>> const& blocks) {
      static_assert(std::is_signed<T>::value,
                    "the template parameter T must be signed");
      int32_t               m   = 0;
      int32_t               deg = 0;
      std::unordered_set<T> vals;
      for (std::vector<T> const& block : blocks) {
        for (T x : block) {
          vals.insert(x);
          x = std::abs(x);
          if (x == 0) {
            LIBSEMIGROUPS_EXCEPTION(
                "value out of bounds, expected non-zero value found 0");
          }
          m = std::max(x, m);
          deg++;
        }
      }

      if (m >= static_cast<int32_t>(0x40000000)) {
        LIBSEMIGROUPS_EXCEPTION(
            "too many points, expected at most %d, found %d",
            int32_t(0x40000000),
            int32_t(m));
      } else if (deg != 2 * m || vals.size() != size_t(deg)) {
        LIBSEMIGROUPS_EXCEPTION("the union of the given blocks is not "
                                "[%d, -1] ∪ [1, %d], only %d values were given",
                                -m,
                                m,
                                deg);
      }
    }

    void init_trans_blocks_lookup();

    mutable size_t        _nr_blocks;
    size_t                _nr_left_blocks;
    std::vector<bool>     _trans_blocks_lookup;
    size_t                _rank;
    std::vector<uint32_t> _vector;
  };

  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;

  //! Multiply two bipartitions.
  //!
  //! Returns a newly constructed bipartition equal to the product of \p x and
  //! \p y.
  //!
  //! \param x a bipartition
  //! \param y a bipartition
  //!
  //! \returns
  //! A value of type \c Bipartition
  //!
  //! \exceptions
  //! \no_libsemigroups_except
  //!
  //! \complexity
  //! Quadratic in degree().
  Bipartition operator*(Bipartition const& x, Bipartition const& y);

  //! Check bipartitions for inequality.
  //!
  //! \param x a bipartition
  //! \param y a bipartition
  //!
  //! \returns
  //! A value of type \c bool.
  //!
  //! \exceptions
  //! \no_libsemigroups_except
  //!
  //! \complexity
  //! At worst linear in the degree of \p x and \p y.
  inline bool operator!=(Bipartition const& x, Bipartition const& y) {
    return !(x == y);
  }

  //! Convenience function that just calls ``operator<`` and ``operator==``.
  inline bool operator<=(Bipartition const& x, Bipartition const& y) {
    return x < y || x == y;
  }

  //! Convenience function that just calls ``operator<``.
  inline bool operator>(Bipartition const& x, Bipartition const& y) {
    return y < x;
  }

  //! Convenience function that just calls ``operator<=``.
  inline bool operator>=(Bipartition const& x, Bipartition const& y) {
    return y <= x;
  }

  ////////////////////////////////////////////////////////////////////////
  // Adapters
  ////////////////////////////////////////////////////////////////////////

  //! Returns the approximate time complexity of multiplication.
  //!
  //! In the case of a Bipartition of degree *n* the value *2n ^ 2* is
  //! returned.
  template <>
  struct Complexity<Bipartition> {
    //! Call operator.
    //!
    //! \param x a const reference to a bipartition.
    //!
    //! \returns
    //! A value of type `size_t` representing the complexity of multiplying the
    //! parameter \p x by another bipartition of the same degree.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    size_t operator()(Bipartition const& x) const noexcept {
      return x.degree() * x.degree();
    }
  };

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

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

  template <>
  struct One<Bipartition> {
    Bipartition operator()(Bipartition const& x) const {
      return (*this)(x.degree());
    }

    Bipartition operator()(size_t N = 0) const {
      return Bipartition::identity(N);
    }
  };

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

  template <>
  struct IncreaseDegree<Bipartition> {
    void operator()(Bipartition&, size_t) {}
  };

}  // namespace libsemigroups
#endif  // LIBSEMIGROUPS_BIPART_HPP_

quality99%

¤ Dauer der Verarbeitung: 0.18 Sekunden ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.