perm16.hpp

Go to the documentation of this file.

//****************************************************************************//
//     Copyright (C) 2016-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/>.               //
//****************************************************************************//
 
#ifndef HPCOMBI_PERM16_HPP_
#define HPCOMBI_PERM16_HPP_
 
#include <cstddef>           // for size_t
#include <cstdint>           // for uint8_t, uint64_t, uint32_t
#include <initializer_list>  // for initializer_list
#include <memory>            // for hash
#include <type_traits>       // for is_trivial
#include <vector>            // for vector
 
#include "epu8.hpp"    // for epu8, permuted, etc
#include "power.hpp"   // for pow
#include "vect16.hpp"  // for hash, is_partial_permutation
 
#include "simde/x86/sse4.1.h"
#include "simde/x86/sse4.2.h"
 
namespace HPCombi {
 
// Forward declaration
struct Perm16;
struct PTransf16;
struct Transf16;
 
struct alignas(16) PTransf16 : public Vect16 {
    static constexpr size_t size() { return 16; }
 
    using vect = HPCombi::Vect16;
    using array = typename decltype(Epu8)::array;
 
    PTransf16() = default;
 
    constexpr PTransf16(const vect v) : Vect16(v) {}
    constexpr PTransf16(const epu8 x) : Vect16(x) {}
    PTransf16(std::vector<uint8_t> dom, std::vector<uint8_t> rng,
              size_t = 0 /* unused */);
    PTransf16(std::initializer_list<uint8_t> il);
 
    bool validate(size_t k = 16) const {
        return HPCombi::is_partial_transformation(v, k);
    }
 
    static constexpr PTransf16 one() { return Epu8.id(); }
    PTransf16 operator*(const PTransf16 &p) const {
        return HPCombi::permuted(v, p.v) | (p.v == Epu8(0xFF));
    }
 
    epu8 image_mask_cmpestrm(bool complement = false) const;
    epu8 image_mask_ref(bool complement = false) const;
    epu8 image_mask(bool complement = false) const {
#ifdef SIMDE_X86_SSE4_2_NATIVE
        return image_mask_cmpestrm(complement);
#else
        return image_mask_ref(complement);
#endif
    }
    uint32_t image_bitset(bool complement = false) const;
    epu8 domain_mask(bool complement = false) const;
    uint32_t domain_bitset(bool complement = false) const;
 
    PTransf16 right_one() const;
    PTransf16 left_one() const;
 
    uint32_t rank_ref() const;
    uint32_t rank() const;
    uint32_t rank_cmpestrm() const;
 
    epu8 fix_points_mask(bool complement = false) const;
    uint32_t fix_points_bitset(bool complement = false) const;
    uint8_t smallest_fix_point() const;
    uint8_t smallest_moved_point() const;
    uint8_t largest_fix_point() const;
    uint8_t largest_moved_point() const;
    uint8_t nb_fix_points() const;
};
 
struct Transf16 : public PTransf16 {
    Transf16() = default;
    constexpr Transf16(const Transf16 &v) = default;
    /* implicit */ constexpr Transf16(const vect v) : PTransf16(v) {}  // NOLINT
    /* implicit */ constexpr Transf16(const epu8 x) : PTransf16(x) {}  // NOLINT
    Transf16(std::initializer_list<uint8_t> il) : PTransf16(il) {}
    Transf16 &operator=(const Transf16 &) = default;
 
    bool validate(size_t k = 16) const {
        return HPCombi::is_transformation(v, k);
    }
 
    static constexpr Transf16 one() { return Epu8.id(); }
    Transf16 operator*(const Transf16 &p) const {
        return HPCombi::permuted(v, p.v);
    }
 
    explicit Transf16(uint64_t compressed);
    explicit operator uint64_t() const;
};
 
struct PPerm16 : public PTransf16 {
    PPerm16() = default;
    constexpr PPerm16(const PPerm16 &v) = default;
    /* implicit */ constexpr PPerm16(const vect v) : PTransf16(v) {}  // NOLINT
    /* implicit */ constexpr PPerm16(const epu8 x) : PTransf16(x) {}  // NOLINT
    PPerm16(std::vector<uint8_t> dom, std::vector<uint8_t> rng,
            size_t = 0 /* unused */)
        : PTransf16(dom, rng) {}
    PPerm16(std::initializer_list<uint8_t> il) : PTransf16(il) {}
    PPerm16 &operator=(const PPerm16 &) = default;
 
    bool validate(size_t k = 16) const {
        return HPCombi::is_partial_permutation(v, k);
    }
 
    static constexpr PPerm16 one() { return Epu8.id(); }
    PPerm16 operator*(const PPerm16 &p) const {
        return this->PTransf16::operator*(p);
    }
 
    PPerm16 inverse_ref() const;
#ifdef SIMDE_X86_SSE4_2_NATIVE
    PPerm16 inverse_find() const;
#endif
 
    PPerm16 right_one() const { return PTransf16::right_one(); }
    PPerm16 left_one() const { return PTransf16::left_one(); }
};
 
struct Perm16 : public Transf16 /* public PPerm : diamond problem */ {
    Perm16() = default;
    constexpr Perm16(const Perm16 &) = default;
    /* implicit */ constexpr Perm16(const vect v) : Transf16(v) {}  // NOLINT
    /* implicit */ constexpr Perm16(const epu8 x) : Transf16(x) {}  // NOLINT
    Perm16 &operator=(const Perm16 &) = default;
    Perm16(std::initializer_list<uint8_t> il) : Transf16(il) {}
 
    bool validate(size_t k = 16) const { return HPCombi::is_permutation(v, k); }
 
    // It's not possible to have a static constexpr member of same type as class
    // being defined (see https://stackoverflow.com/questions/11928089/)
    // therefore we chose to have functions.
    static constexpr Perm16 one() { return Epu8.id(); }
    Perm16 operator*(const Perm16 &p) const {
        return HPCombi::permuted(v, p.v);
    }
 
    explicit Perm16(uint64_t compressed) : Transf16(compressed) {}
 
    Perm16 inverse_ref() const;
    Perm16 inverse_arr() const;
    Perm16 inverse_sort() const;
    Perm16 inverse_find() const { return permutation_of(v, one()); }
    Perm16 inverse_pow() const;
    Perm16 inverse_cycl() const;
    Perm16 inverse() const { return inverse_cycl(); }
 
    static Perm16 elementary_transposition(uint64_t i);
    static Perm16 random(uint64_t n = 16);
    static Perm16 unrankSJT(int n, int r);
 
    epu8 lehmer_ref() const;
    epu8 lehmer_arr() const;
    epu8 lehmer() const;
 
    uint8_t length_ref() const;
    uint8_t length_arr() const;
    uint8_t length() const;
 
    uint8_t nb_descents_ref() const;
    uint8_t nb_descents() const;
 
    epu8 cycles_partition() const;
 
    uint8_t nb_cycles_ref() const;
    uint8_t nb_cycles_unroll() const;
    uint8_t nb_cycles() const { return nb_cycles_unroll(); }
 
    bool left_weak_leq_ref(Perm16 other) const;
    bool left_weak_leq_length(Perm16 other) const;
    bool left_weak_leq(Perm16 other) const;
};
 
 
static_assert(sizeof(epu8) == sizeof(Perm16),
              "epu8 and Perm16 have a different memory layout !");
static_assert(std::is_trivial<epu8>(), "epu8 is not a trivial class !");
static_assert(std::is_trivial<Perm16>(), "Perm16 is not a trivial class !");
 
}  // namespace HPCombi
 
#include "perm16_impl.hpp"
 
namespace std {
 
template <> struct hash<HPCombi::PTransf16> {
    size_t operator()(const HPCombi::PTransf16 &ar) const {
        return std::hash<HPCombi::epu8>{}(ar.v);
    }
};
 
template <> struct hash<HPCombi::Transf16> {
    size_t operator()(const HPCombi::Transf16 &ar) const {
        return uint64_t(ar);
    }
};
 
template <> struct hash<HPCombi::PPerm16> {
    size_t operator()(const HPCombi::PPerm16 &ar) const {
        return std::hash<HPCombi::epu8>{}(ar.v);
    }
};
 
template <> struct hash<HPCombi::Perm16> {
    size_t operator()(const HPCombi::Perm16 &ar) const { return uint64_t(ar); }
};
 
}  // namespace std
 
#endif  // HPCOMBI_PERM16_HPP_