Quelle bmat8.hpp Sprache: C

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2019 Finn Smith
//
// 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 a declaration of fast boolean matrices up to dimension 8.

#ifndef LIBSEMIGROUPS_BMAT8_HPP_
#define LIBSEMIGROUPS_BMAT8_HPP_

#include <algorithm>  // for uniform_int_distribution, swap
#include <cstddef>    // for size_t
#include <cstdint>    // for uint64_t
#include <iosfwd>     // for operator<<, ostringstream
#include <random>     // for mt19937, random_device
#include <utility>    // for hash
#include <vector>     // for vector

#include "adapters.hpp"  // for Complexity, Degree, etc . . .
#include "debug.hpp"     // for LIBSEMIGROUPS_ASSERT
#include "string.hpp"    // for detail::to_string

namespace libsemigroups {
  namespace bmat8_helpers {
    //! Returns the identity boolean matrix of a given dimension.
    //!
    //! \tparam T the type of the boolean matrix being constructed, should be
    //! BMat8 or HPCombi::BMat8.
    //!
    //! \param dim the dimension of the identity matrix, must be at most 7.
    //!
    //! \returns
    //! A value of type \p T with the first \p dim values on the main diagonal
    //! equal to 1 and every other entry equal to 0.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    //!
    //! \sa BMat8::one.
    // TODO(later) noexcept should depend on whether or not the constructor of
    // T is noexcept
    template <typename T>
    T one(size_t dim) noexcept {
      LIBSEMIGROUPS_ASSERT(dim <= 8);
      static std::array<uint64_t, 9> const ones = {0x0000000000000000,
                                                   0x8000000000000000,
                                                   0x8040000000000000,
                                                   0x8040200000000000,
                                                   0x8040201000000000,
                                                   0x8040201008000000,
                                                   0x8040201008040000,
                                                   0x8040201008040200,
                                                   0x8040201008040201};
      return T(ones[dim]);
    }
  }  // namespace bmat8_helpers

  //! Defined in ``bmat8.hpp``.
  //!
  //! Class for fast boolean matrices of dimension up to 8 x 8
  //!
  //! The member functions for these small matrices over the boolean semiring
  //! are more optimised than the generic member functions for boolean matrices.
  //! Note that all BMat8 are represented internally as an 8 x 8 matrix;
  //! any entries not defined by the user are taken to be 0. This does
  //! not affect the results of any calculations.
  //!
  //! BMat8 is a trivial class.
  class BMat8 final {
   public:
    //! Default constructor.
    //!
    //! There is no guarantee about the contents of the matrix constructed.
    //!
    //! \par Parameters
    //! (None)
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    BMat8() noexcept = default;

    //! Construct from uint64_t.
    //!
    //! This constructor initializes a BMat8 to have rows equal to the
    //! 8 chunks, of 8 bits each, of the binary representation of \p mat.
    //!
    //! \param mat the integer representation of the matrix being constructed.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    explicit BMat8(uint64_t mat) noexcept : _data(mat) {}

    //! A constructor.
    //!
    //! This constructor initializes a matrix where the rows of the matrix
    //! are the vectors in \p mat.
    //!
    //! \param mat the vector of vectors representation of the matrix being
    //! constructed.
    //!
    //! \throws LibsemigroupsException if \p mat has 0 rows.
    //! \throws LibsemigroupsException if \p mat has more than 8 rows.
    //! \throws LibsemigroupsException if the rows of \p mat are not all of the
    //! same length.
    //!
    //! \complexity
    //! Constant.
    explicit BMat8(std::vector<std::vector<bool>> const& mat);

    //! Default copy constructor.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    BMat8(BMat8 const&) noexcept = default;

    //! Default move constructor.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    BMat8(BMat8&&) noexcept = default;

    //! Default copy assignment operator.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    BMat8& operator=(BMat8 const&) noexcept = default;

    //! Default move assignment operator.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    BMat8& operator=(BMat8&&) noexcept = default;

    ~BMat8() = default;

    //! Returns \c true if \c this equals \p that.
    //!
    //! This member function checks the mathematical equality of two BMat8
    //! objects.
    //!
    //! \param that the BMat8 for comparison.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    bool operator==(BMat8 const& that) const noexcept {
      return _data == that._data;
    }

    //! Returns \c true if \c this does not equal \p that
    //!
    //! This member function checks the mathematical inequality of two BMat8
    //! objects.
    //!
    //! \param that the BMat8 for comparison.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    bool operator!=(BMat8 const& that) const noexcept {
      return _data != that._data;
    }

    //! Returns \c true if \c this is less than \p that.
    //!
    //! This member function checks whether a BMat8 objects is less than
    //! another. We order by the results of to_int() for each matrix.
    //!
    //! \param that the BMat8 for comparison.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    bool operator<(BMat8 const& that) const noexcept {
      return _data < that._data;
    }

    //! Returns \c true if \c this is greater than \p that.
    //!
    //! This member function checks whether a BMat8 objects is greater than
    //! another. We order by the results of to_int() for each matrix.
    //!
    //! \param that the BMat8 for comparison.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    bool operator>(BMat8 const& that) const noexcept {
      return _data > that._data;
    }

    //! Returns the entry in the (\p i, \p j)th position.
    //!
    //! This member function returns the entry in the (\p i, \p j)th position.
    //!
    //! \param i the row of the entry sought.
    //! \param j the column of the entry sought.
    //!
    //! \returns
    //! A ``bool``.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    //!
    //! \note
    //! Note that since all matrices are internally represented as 8 x 8, it
    //! is possible to access entries that you might not believe exist.
    //!
    //! \warning
    //! No checks on the parameters \p i and \p j are performed, if \p i or \p
    //! j is greater than 7, then bad things will happen.
    bool get(size_t i, size_t j) const noexcept {
      LIBSEMIGROUPS_ASSERT(i < 8);
      LIBSEMIGROUPS_ASSERT(j < 8);
      return (_data << (8 * i + j)) >> 63;
    }

    // TODO(later) at method

    //! Sets the (\p i, \p j)th position to \p val.
    //!
    //! This member function sets the (\p i, \p j)th entry of \c this to \p val.
    //! Uses the bit twiddle for setting bits found
    //! <a href=http://graphics.stanford.edu/~seander/bithacks>here</a>.
    //!
    //! \param i the row
    //! \param j the column
    //! \param val the value to set in position (\p i, \p j)th
    //!
    //! \returns
    //! (None)
    //!
    //! \throws LibsemigroupsException if \p i or \p j is out of bounds.
    //!
    //! \complexity
    //! Constant.
    void set(size_t i, size_t j, bool val);

    //! Returns the integer representation of \c this.
    //!
    //! Returns an unsigned integer obtained by interpreting an 8 x 8
    //! BMat8 as a sequence of 64 bits (reading rows left to right,
    //! from top to bottom) and then realising this sequence as an unsigned
    //! int.
    //!
    //! \returns
    //! A ``uint64_t``.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    //!
    //! \par Parameters
    //! (None)
    inline uint64_t to_int() const noexcept {
      return _data;
    }

    //! Returns the transpose of \c this.
    //!
    //! Uses the technique found in [Knu09](../biblio.html#knuth2009aa).
    //!
    //! \returns
    //! A BMat8.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    //!
    //! \par Parameters
    //! (None)
    inline BMat8 transpose() const noexcept {
      uint64_t x = _data;
      uint64_t y = (x ^ (x >> 7)) & 0xAA00AA00AA00AA;
      x          = x ^ y ^ (y << 7);
      y          = (x ^ (x >> 14)) & 0xCCCC0000CCCC;
      x          = x ^ y ^ (y << 14);
      y          = (x ^ (x >> 28)) & 0xF0F0F0F0;
      x          = x ^ y ^ (y << 28);
      return BMat8(x);
    }

    //! Returns the matrix product of \c this and \p that
    //!
    //! This member function returns the standard matrix product (over the
    //! boolean semiring) of two BMat8 objects.
    //! Uses the technique given [here](https://stackoverflow.com/a/18448513).
    //!
    //! \param that the matrix we want to multiply by \c this.
    //!
    //! \returns
    //! A BMat8.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    BMat8 operator*(BMat8 const& that) const noexcept;

    //! Insertion operator
    //!
    //! This member function allows BMat8 objects to be inserted into an
    //! std::ostringstream.
    friend std::ostringstream& operator<<(std::ostringstream& os,
                                          BMat8 const&        bm);

    //! Insertion operator
    //!
    //! This member function allows BMat8 objects to be inserted into a
    //! std::ostream.
    friend std::ostream& operator<<(std::ostream& os, BMat8 const& bm) {
      os << detail::to_string(bm);
      return os;
    }

    //! Construct a random BMat8.
    //!
    //! This static member function returns a BMat8 chosen at random.
    //!
    //! \returns
    //! A BMat8.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \par Parameters
    //! (None)
    // Not noexcept since std::uniform_int_distribution::operator() is not
    // noexcept.
    static BMat8 random() {
      return BMat8(_dist(_gen));
    }

    //! Construct a random BMat8 of dimension at most \p dim.
    //!
    //! This static member function returns a BMat8 chosen at random, where
    //! only the top-left \p dim x \p dim entries can be non-zero.
    //!
    //! \returns
    //! A BMat8.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \par Parameters
    //! (None)
    // Not noexcept since std::uniform_int_distribution::operator() is not
    // noexcept.
    static BMat8 random(size_t dim);

    //! Swaps \c this with \p that.
    //!
    //! This member function swaps the values of \c this and \p that.
    //!
    //! \param that the BMat8 to swap \c this with.
    //!
    //! \returns
    //! (None)
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    inline void swap(BMat8& that) noexcept {
      std::swap(this->_data, that._data);
    }

    //! Find a basis for the row space of \c this.
    //!
    //! This member function returns a BMat8 whose non-zero rows form a basis
    //! for the row space of \c this.
    //!
    //! \returns
    //! A BMat8.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    //!
    //! \par Parameters
    //! (None)
    BMat8 row_space_basis() const noexcept;

    //! Find a basis for the column space of \c this.
    //!
    //! This member function returns a BMat8 whose non-zero columns form a basis
    //! for the column space of \c this.
    //!
    //! \returns
    //! A BMat8.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    //!
    //! \par Parameters
    //! (None)
    BMat8 col_space_basis() const noexcept {
      return this->transpose().row_space_basis().transpose();
    }

    //! Returns a vector containing the rows of \c this
    //!
    //! This member function returns a std::vector of uint8_ts representing the
    //! rows of \c this. The vector will always be of length 8, even if \c this
    //! was constructed with fewer rows.
    //!
    //! \returns
    //! A std::vector<uint8_t>.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \complexity
    //! Constant.
    //!
    //! \par Parameters
    //! (None)
    // TODO(later) make this return an array instead of a vector
    std::vector<uint8_t> rows() const;

    //! Find the size of the row space of \c this.
    //!
    //! \returns
    //! A \c size_t.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \complexity
    //! \f$O(n)\f$ where \f$n\f$ is the return value of this function.
    //!
    //! \par Parameters
    //! (None)
    //!
    //! \sa bmat8_helpers::col_space_size.
    size_t row_space_size() const;

    //! Returns the number of non-zero rows in \c this.
    //!
    //! BMat8s do not know their "dimension" - in effect they are all of
    //! dimension 8. However, this member function can be used to obtain the
    //! number of non-zero rows of \c this.
    //!
    //! \returns
    //! A \c size_t.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    //!
    //! \par Parameters
    //! (None)
    //!
    //! \sa bmat8_helpers::number_of_cols and bmat8_helpers::minimum_dim.
    size_t number_of_rows() const noexcept {
      size_t count = 0;
      for (size_t i = 0; i < 8; ++i) {
        if (_data << (8 * i) >> 56 > 0) {
          count++;
        }
      }
      return count;
    }

    //! Check whether \c this is a regular element of the full boolean matrix
    //! monoid of appropriate dimension.
    //!
    //! \returns
    //! A \c true if there exists a boolean matrix \c y such that `x * y * x =
    //! x` where \c x is \c *this.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    //!
    //! \par Parameters
    //! (None)
    bool is_regular_element() const noexcept {
      return *this
                 * BMat8(
                       ~(*this * BMat8(~_data).transpose() * (*this)).to_int())
                       .transpose()
                 * (*this)
             == *this;
    }

    //! Returns the identity BMat8.
    //!
    //! This member function returns the BMat8 with the first \c dim entries in
    //! the main diagonal equal to \c 1 and every other value equal to \c 0.
    //!
    //! \param dim the dimension of the identity (default: 8)
    //!
    //! \returns
    //! A BMat8.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    static BMat8 one(size_t dim = 8) noexcept {
      return bmat8_helpers::one<BMat8>(dim);
    }

   private:
    void sort_rows() noexcept;

    uint64_t                                       _data;
    static std::random_device                      _rd;
    static std::mt19937                            _gen;
    static std::uniform_int_distribution<uint64_t> _dist;
  };

  static_assert(std::is_trivial<BMat8>(), "BMat8 is not a trivial class!");

  //! Defined in ``bmat8.hpp``.
  //!
  //! This namespace contains various helper functions for the class BMat8.
  //! These functions could be member functions of BMat8 but they only use
  //! public member functions of BMat8, and so they are declared as free
  //! functions instead.
  namespace bmat8_helpers {
    // TODO(later) these should be templated to allow using HPCombi::BMat8's
    // here too.
    //! Returns the number of non-zero columns in \p x.
    //!
    //! BMat8s do not know their "dimension" - in effect they are all of
    //! dimension 8. However, this member function can be used to obtain the
    //! number of non-zero rows of \c this.
    //!
    //! \param x the BMat8 whose number of columns we want.
    //!
    //! \returns
    //! A \c size_t.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    //!
    //! \sa BMat8::number_of_rows and bmat8_helpers::minimum_dim.
    // noexcept because transpose and number_of_rows are.
    static inline size_t number_of_cols(BMat8 const& x) noexcept {
      return x.transpose().number_of_rows();
    }

    //! Find the size of the column space of \c x.
    //!
    //! \param x a BMat8.
    //!
    //! \returns
    //! A \c size_t.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \complexity
    //! \f$O(n)\f$ where \f$n\f$ is the return value of this function.
    //!
    //! \sa BMat8::row_space_size.
    // Not noexcept because row_space_size isn't.
    static inline size_t col_space_size(BMat8 const& x) {
      return x.transpose().row_space_size();
    }

    //! Find the minimum dimension of \p x.
    //!
    //! This member function returns the maximal \c i such that row \c i or
    //! column \c i contains a \c 1.
    //!
    //! \param x a BMat8.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    size_t minimum_dim(BMat8 const& x) noexcept;

  }  // namespace bmat8_helpers
}  // namespace libsemigroups

namespace std {
  template <>
  struct hash<libsemigroups::BMat8> {
    size_t operator()(libsemigroups::BMat8 const& bm) const {
      return hash<uint64_t>()(bm.to_int());
    }
  };
}  // namespace std

namespace libsemigroups {
  //! Specialization of the adapter Complexity for instances of BMat8.
  //!
  //! \sa Complexity.
  template <>
  struct Complexity<BMat8> {
    //! Returns 0; BMat8 multiplication is constant complexity.
    constexpr inline size_t operator()(BMat8 const&) const noexcept {
      return 0;
    }
  };

  //! Specialization of the adapter Degree for instances of BMat8.
  //!
  //! \sa Degree.
  template <>
  struct Degree<BMat8> {
    //! Returns 8; all BMat8s have degree 8.
    constexpr inline size_t operator()(BMat8 const&) const noexcept {
      return 8;
    }
  };

  //! Specialization of the adapter IncreaseDegree for instances of BMat8.
  //!
  //! \sa IncreaseDegree.
  template <>
  struct IncreaseDegree<BMat8> {
    //! Does nothing.
    inline void operator()(BMat8 const&, size_t) const noexcept {}
  };

  //! Specialization of the adapter One for instances of BMat8.
  //!
  //! \sa One.
  template <>
  struct One<BMat8> {
    //! Returns \p x.one()
    inline BMat8 operator()(BMat8 const& x) const noexcept {
      return x.one();
    }
    //! Returns BMat8::one(dim)
    inline BMat8 operator()(size_t dim = 8) const noexcept {
      return BMat8::one(dim);
    }
  };

  //! Specialization of the adapter Product for instances of BMat8.
  //!
  //! \sa Product.
  template <>
  struct Product<BMat8> {
    //! Changes \p xy in place to hold the product of \p x and \p y
    inline void operator()(BMat8&       xy,
                           BMat8 const& x,
                           BMat8 const& y,
                           size_t = 0) const noexcept {
      xy = x * y;
    }
  };

  //! Specialization of the adapter ImageRightAction for instances of BMat8.
  //!
  //! \sa ImageRightAction.
  template <>
  struct ImageRightAction<BMat8, BMat8> {
    //! Changes \p res in place to hold the image of \p pt under the right
    //! action of \p x.
    void operator()(BMat8&       res,
                    BMat8 const& pt,
                    BMat8 const& x) const noexcept {
      res = (pt * x).row_space_basis();
    }
  };

  //! Specialization of the adapter ImageLeftAction for instances of BMat8.
  //!
  //! \sa ImageLeftAction.
  template <>
  struct ImageLeftAction<BMat8, BMat8> {
    //! Changes \p res in place to hold the image of \p pt under the left
    //! action of \p x.
    void operator()(BMat8&       res,
                    BMat8 const& pt,
                    BMat8 const& x) const noexcept {
      res = (x * pt).col_space_basis();
    }
  };

  //! Specialization of the adapter Inverse for instances of BMat8.
  //!
  //! \sa Inverse.
  template <>
  struct Inverse<BMat8> {
    //! Returns the group inverse of \p x.
    inline BMat8 operator()(BMat8 const& x) const noexcept {
      LIBSEMIGROUPS_ASSERT(x * x.transpose() == x.one());
      return x.transpose();
    }
  };

  //! Specialization of the adapter LambdaValue for instances of BMat8.
  //!
  //! \sa LambdaValue
  template <>
  struct LambdaValue<BMat8> {
    //! The type of Lambda values for BMat8 is also BMat8; this provides an
    //! efficient representation of row space bases.
    using type = BMat8;
  };

  //! Specialization of the adapter RhoValue for instances of BMat8.
  //!
  //! \sa RhoValue
  template <>
  struct RhoValue<BMat8> {
    //! The type of Rho values for BMat8 is also BMat8; this provides an
    //! efficient representation of column space bases.
    using type = BMat8;
  };

  //! Specialization of the adapter Lambda for instances of BMat8.
  //!
  //! \sa Lambda.
  template <>
  struct Lambda<BMat8, BMat8> {
    //! Returns the lambda value of \p x as used in the Konieczny algorithm; for
    //! BMat8 this is the row space basis.
    // noexcept because BMat8::row_space_basis is noexcept
    inline void operator()(BMat8& res, BMat8 const& x) const noexcept {
      res = x.row_space_basis();
    }
  };

  //! Specialization of the adapter Rho for instances of BMat8.
  //!
  //! \sa Rho.
  template <>
  struct Rho<BMat8, BMat8> {
    //! Returns the rho value of \p x as used in the Konieczny algorithm; for
    //! BMat8 this is the column space basis.
    // noexcept because BMat8::col_space_basis is noexcept
    inline void operator()(BMat8& res, BMat8 const& x) const noexcept {
      res = x.col_space_basis();
    }
  };

  //! Specialization of the adapter Rank for instances of BMat8.
  //!
  //! \sa Rank.
  template <>
  struct Rank<BMat8> {
    //! Returns the rank of \p x as used in the Konieczny algorithm; for BMat8
    //! this is the size of the row space.
    inline size_t operator()(BMat8 const& x) const noexcept {
      return x.row_space_size();
    }
  };
}  // namespace libsemigroups

#endif  // LIBSEMIGROUPS_BMAT8_HPP_

quality100%

¤ Dauer der Verarbeitung: 0.11 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.