is-transf.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2025-2026 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 some functions for checking whether or not a container
// defines a partial transformation, full transformation, partial permutation,
// or permutation. These are used in transf.hpp for argument checking, and also
// in hpcombi.hpp for the same.
 
#ifndef LIBSEMIGROUPS_IS_TRANSF_HPP_
#define LIBSEMIGROUPS_IS_TRANSF_HPP_
 
#include <algorithm>      // for none_of, find_if
#include <cstddef>        // for size_t
#include <iterator>       // for distance
#include <limits>         // for numeric_limits
#include <string_view>    // for string_view
#include <type_traits>    // for decay_t, is_unsigned_v
#include <unordered_map>  // for unordered_map
#include <utility>        // for declval, pair
 
#include "constants.hpp"  // for UNDEFINED
 
#include "detail/print.hpp"  // for to_printable
#include "detail/stl.hpp"    // for is_array_v
 
namespace libsemigroups {
 
  namespace detail {
 
    // Returns "{it, pos}" where "it" is an iterator point to the first
    // repeated element and "pos" is the position of the first occurrence of
    // that element. Returns {last, std::distance(first, last)} if not
    // duplicates.
    template <typename Iterator>
    std::pair<Iterator, size_t> find_duplicates(
        Iterator                                                    first,
        Iterator                                                    last,
        std::unordered_map<std::decay_t<decltype(*first)>, size_t>& seen);
 
    template <typename Iterator>
    [[nodiscard]] std::pair<Iterator, size_t> find_duplicates(Iterator first,
                                                              Iterator last) {
      std::unordered_map<std::decay_t<decltype(*first)>, size_t> seen;
      return find_duplicates(first, last, seen);
    }
 
    template <typename Iterator>
    [[nodiscard]] bool has_duplicates(Iterator first, Iterator last) {
      return find_duplicates(first, last).first != last;
    }
 
    template <typename Iterator>
    void throw_if_duplicates(
        Iterator                                                    first,
        Iterator                                                    last,
        std::unordered_map<std::decay_t<decltype(*first)>, size_t>& seen,
        std::string_view                                            where);
 
    template <typename Iterator>
    void throw_if_duplicates(Iterator         first,
                             Iterator         last,
                             std::string_view where) {
      std::unordered_map<std::decay_t<decltype(*first)>, size_t> seen;
      throw_if_duplicates(first, last, seen, where);
    }
 
    // The maximum degree a PTransf could have. This is the largest value such
    // that each point in the image can be unique.
    template <typename Point>
    size_t max_degree();
 
    template <typename Point>
    bool is_valid_degree(size_t deg) {
      return deg <= max_degree<Point>();
    }
 
    template <typename Point>
    void throw_if_degree_too_large(size_t deg);
 
    template <typename Iterator, typename Func>
    void throw_if_value_out_of_range(Iterator         first,
                                     Iterator         last,
                                     Func&&           func,
                                     std::string_view where);
 
    template <typename Iterator>
    void throw_if_not_ptransf(Iterator first, Iterator last, size_t deg);
 
    template <typename Iterator>
    void throw_if_not_ptransf(Iterator first, Iterator last) {
      throw_if_not_ptransf(first, last, std::distance(first, last));
    }
 
    template <typename Iterator>
    void throw_if_not_ptransf(Iterator dom_first,
                              Iterator dom_last,
                              Iterator img_first,
                              Iterator img_last,
                              size_t   deg);
 
    template <typename Iterator>
    void throw_if_not_transf(Iterator first, Iterator last, size_t deg);
 
    template <typename Iterator>
    void throw_if_not_transf(Iterator first, Iterator last) {
      throw_if_not_transf(first, last, std::distance(first, last));
    }
 
    template <typename Iterator>
    void throw_if_not_perm(Iterator first, Iterator last, size_t deg) {
      throw_if_not_transf(first, last, deg);
      throw_if_duplicates(first, last, "image");
    }
 
    template <typename Iterator>
    void throw_if_not_perm(Iterator first, Iterator last) {
      throw_if_not_perm(first, last, std::distance(first, last));
    }
 
    template <typename Iterator>
    void throw_if_not_pperm(Iterator first, Iterator last, size_t deg) {
      throw_if_not_ptransf(first, last, deg);
      throw_if_duplicates(first, last, "image");
    }
 
    template <typename Iterator>
    void throw_if_not_pperm(Iterator first, Iterator last) {
      throw_if_not_ptransf(first, last);
      throw_if_duplicates(first, last, "image");
    }
 
    template <typename Iterator>
    void throw_if_not_pperm(Iterator dom_first,
                            Iterator dom_last,
                            Iterator img_first,
                            Iterator img_last,
                            size_t   deg) {
      throw_if_not_ptransf(dom_first, dom_last, img_first, img_last, deg);
      throw_if_duplicates(img_first, img_last, "image");
    }
  }  // namespace detail

  template <typename Iterator>
  [[nodiscard]] bool is_ptransf(Iterator first, Iterator last, size_t deg) {
    static_assert(
        std::is_unsigned_v<std::decay_t<decltype(*std::declval<Iterator>())>>);
    return std::none_of(first, last, [&deg](auto val) {
      return val >= deg && val != UNDEFINED;
    });
  }

  template <typename Iterator>
  [[nodiscard]] bool is_ptransf(Iterator first, Iterator last) {
    return is_ptransf(first, last, std::distance(first, last));
  }

  template <typename Iterator>
  [[nodiscard]] bool is_transf(Iterator first, Iterator last, size_t deg) {
    static_assert(
        std::is_unsigned_v<std::decay_t<decltype(*std::declval<Iterator>())>>);
    return std::none_of(first, last, [&deg](auto val) { return val >= deg; });
  }

  template <typename Iterator>
  [[nodiscard]] bool is_transf(Iterator first, Iterator last) {
    return is_transf(first, last, std::distance(first, last));
  }

  template <typename Iterator>
  [[nodiscard]] bool is_pperm(Iterator first, Iterator last, size_t deg) {
    return is_ptransf(first, last, deg) && !detail::has_duplicates(first, last);
  }

  template <typename Iterator>
  [[nodiscard]] bool is_pperm(Iterator first, Iterator last) {
    return is_pperm(first, last, std::distance(first, last));
  }

  template <typename Iterator>
  [[nodiscard]] bool is_perm(Iterator first, Iterator last, size_t deg) {
    return is_transf(first, last, deg) && !detail::has_duplicates(first, last);
  }

  template <typename Iterator>
  [[nodiscard]] bool is_perm(Iterator first, Iterator last) {
    return is_perm(first, last, std::distance(first, last));
  }
}  // namespace libsemigroups
 
#include "is-transf.tpp"
 
#endif  // LIBSEMIGROUPS_IS_TRANSF_HPP_