bmat8.hpp

Go to the documentation of this file.

//****************************************************************************//
//    Copyright (C) 2018-2024 Finn Smith <fls3@st-andrews.ac.uk>              //
//    Copyright (C) 2018-2024 James Mitchell <jdm3@st-andrews.ac.uk>          //
//    Copyright (C) 2018-2024 Florent Hivert <Florent.Hivert@lisn.fr>,        //
//                                                                            //
//  This file is part of HP-Combi <https://github.com/libsemigroups/HPCombi>  //
//                                                                            //
//  HP-Combi 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.                                       //
//                                                                            //
//  HP-Combi 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 HP-Combi. If not, see <https://www.gnu.org/licenses/>.               //
//****************************************************************************//
 
// This file contains a declaration of fast boolean matrices up to dimension 8.
 
#ifndef HPCOMBI_BMAT8_HPP_
#define HPCOMBI_BMAT8_HPP_
 
#include <array>       // for array
#include <bitset>      // for bitset
#include <cstddef>     // for size_t
#include <cstdint>     // for uint64_t, uint8_t
#include <functional>  // for hash, __scalar_hash
#include <iostream>    // for ostream
#include <memory>      // for hash
#include <utility>     // for pair, swap
#include <vector>      // for vector
 
#include "debug.hpp"   // for HPCOMBI_ASSERT
#include "epu8.hpp"    // for epu8
#include "perm16.hpp"  // for Perm16
 
namespace HPCombi {
 
class BMat8 {
 public:
    BMat8() noexcept = default;
 
    explicit BMat8(uint64_t mat) noexcept : _data(mat) {}
 
    // Not sure if this is noexcept or not
    explicit BMat8(std::vector<std::vector<bool>> const &mat);
 
    BMat8(BMat8 const &) noexcept = default;
 
    BMat8(BMat8 &&) noexcept = default;
 
    BMat8 &operator=(BMat8 const &) noexcept = default;
 
    BMat8 &operator=(BMat8 &&) noexcept = default;
 
    ~BMat8() = default;
 
    bool operator==(BMat8 const &that) const noexcept {
        return _data == that._data;
    }
 
    bool operator!=(BMat8 const &that) const noexcept {
        return _data != that._data;
    }
 
    bool operator<(BMat8 const &that) const noexcept {
        return _data < that._data;
    }
 
    bool operator>(BMat8 const &that) const noexcept {
        return _data > that._data;
    }
 
    bool operator()(size_t i, size_t j) const noexcept;
 
    void set(size_t i, size_t j, bool val) noexcept;
 
    uint64_t to_int() const noexcept { return _data; }
 
    BMat8 transpose() const noexcept;
 
    BMat8 transpose_mask() const noexcept;
 
    BMat8 transpose_maskd() const noexcept;
 
    static void transpose2(BMat8 &, BMat8 &) noexcept;
 
    BMat8 mult_transpose(BMat8 const &that) const noexcept;
 
    BMat8 operator*(BMat8 const &that) const noexcept {
        return mult_transpose(that.transpose());
    }
 
    BMat8 row_space_basis() const noexcept;
 
    BMat8 col_space_basis() const noexcept {
        return transpose().row_space_basis().transpose();
    }
 
    size_t nr_rows() const noexcept;
 
    // Not noexcept because it constructs a vector
    std::vector<uint8_t> rows() const;
 
    // Not noexcept because row_space_bitset_ref isn't
    uint64_t row_space_size_ref() const;
 
    // Not noexcept because it creates a vector
    std::bitset<256> row_space_bitset_ref() const;
 
    void row_space_bitset(epu8 &res1, epu8 &res2) const noexcept;
 
    uint64_t row_space_size_bitset() const noexcept;
 
    uint64_t row_space_size_incl() const noexcept;
 
    uint64_t row_space_size_incl1() const noexcept;
 
    uint64_t row_space_size() const noexcept { return row_space_size_incl(); }
 
    bool row_space_included_ref(BMat8 other) const noexcept;
 
    bool row_space_included_bitset(BMat8 other) const noexcept;
 
    epu8 row_space_mask(epu8 vects) const noexcept;
 
    bool row_space_included(BMat8 other) const noexcept;
 
    // Not noexcept because std::make_pair is not
    static std::pair<bool, bool> row_space_included2(BMat8 a1, BMat8 b1,
                                                     BMat8 a2, BMat8 b2);
 
    BMat8 row_permuted(Perm16 p) const noexcept;
 
    BMat8 col_permuted(Perm16 p) const noexcept;
 
    static BMat8 row_permutation_matrix(Perm16 p) noexcept;
 
    static BMat8 col_permutation_matrix(Perm16 p) noexcept;
 
    Perm16 right_perm_action_on_basis(BMat8) const noexcept;
 
    // Not noexcept because vectors are allocated
    Perm16 right_perm_action_on_basis_ref(BMat8) const;
 
    static BMat8 one(size_t dim = 8) noexcept {
        HPCOMBI_ASSERT(dim <= 8);
        static std::array<uint64_t, 9> const ones = {
            0x0000000000000000, 0x8000000000000000, 0x8040000000000000,
            0x8040200000000000, 0x8040201000000000, 0x8040201008000000,
            0x8040201008040000, 0x8040201008040200, 0x8040201008040201};
        return BMat8(ones[dim]);
    }
 
    // Not noexcept because random things aren't
    static BMat8 random();
 
    // Not noexcept because BMat8::random above is not
    static BMat8 random(size_t dim);
 
    void swap(BMat8 &that) noexcept { std::swap(this->_data, that._data); }
 
    // Not noexcept
    std::ostream &write(std::ostream &os) const;
 
#ifdef HPCOMBI_HAVE_DENSEHASHMAP
    // FIXME do this another way
    BMat8 empty_key() const noexcept { return BMat8(0xFF7FBFDFEFF7FBFE); }
#endif
 
 private:
    uint64_t _data;
 
    epu8 row_space_basis_internal() const noexcept;
};
 
}  // namespace HPCombi
 
#include "bmat8_impl.hpp"
 
namespace std {
template <> struct hash<HPCombi::BMat8> {
    inline size_t operator()(HPCombi::BMat8 const &bm) const {
        return hash<uint64_t>()(bm.to_int());
    }
};
}  // namespace std
#endif  // HPCOMBI_BMAT8_HPP_