1 //
2 // libsemigroups - C++ library for semigroups and monoids
3 // Copyright (C) 2019 James D. Mitchell
4 //
5 // This program is free software: you can redistribute it and/or modify
6 // it under the terms of the GNU General Public License as published by
7 // the Free Software Foundation, either version 3 of the License, or
8 // (at your option) any later version.
9 //
10 // This program is distributed in the hope that it will be useful,
11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13 // GNU General Public License for more details.
14 //
15 // You should have received a copy of the GNU General Public License
16 // along with this program.  If not, see <http://www.gnu.org/licenses/>.
17 //
18 
19 // This file contains some functionality missing in some implementations of the
20 // stl, or to augment the stl implementations.
21 
22 #ifndef LIBSEMIGROUPS_INCLUDE_STL_HPP_
23 #define LIBSEMIGROUPS_INCLUDE_STL_HPP_
24 
25 #include <cstddef>      // for size_t
26 #include <memory>       // for unique_ptr
27 #include <type_traits>  // for enable_if, forward, hash, is_function, is_same
28 #include <vector>       // for vector
29 
30 namespace libsemigroups {
31 
32   namespace detail {
33     // Pass parameter p by value because this function modifies p.
34     template <typename TContainer, typename TPerm>
apply_permutation(TContainer & cont,TPerm p)35     void apply_permutation(TContainer& cont, TPerm p) {
36       size_t const n = p.size();
37       for (size_t i = 0; i < n; ++i) {
38         size_t current = i;
39         while (i != p[current]) {
40           size_t next = p[current];
41           std::swap(cont[current], cont[next]);
42           p[current] = current;
43           current    = next;
44         }
45         p[current] = current;
46       }
47     }
48 
49     // C++11 is missing make_unique. The following implementation is from Item
50     // 21 in "Effective Modern C++" by Scott Meyers.
51     template <typename T, typename... Ts>
make_unique(Ts &&...params)52     std::unique_ptr<T> make_unique(Ts&&... params) {
53       return std::unique_ptr<T>(new T(std::forward<Ts>(params)...));
54     }
55 
56     // Since std::is_invocable is only introduced in C++17, we use this
57     // from: https://stackoverflow.com/q/15393938/
58     // Only works if there are no overloads of operator() in type T.
59     template <typename T, typename = void>
60     struct IsCallable : std::is_function<T> {};
61 
62     template <typename T>
63     struct IsCallable<
64         T,
65         typename std::enable_if<
66             std::is_same<decltype(void(&T::operator())), void>::value>::type>
67         : std::true_type {};
68 
69   }  // namespace detail
70 }  // namespace libsemigroups
71 
72 namespace std {
73   template <typename TValueType, size_t N>
74   struct hash<std::array<TValueType, N>> {
operator ()std::hash75     size_t operator()(std::array<TValueType, N> const& ar) const {
76       size_t seed = 0;
77       for (auto const& x : ar) {
78         seed ^= std::hash<TValueType>{}(x) + 0x9e3779b9 + (seed << 6)
79                 + (seed >> 2);
80       }
81       return seed;
82     }
83   };
84 
85   template <typename TValueType>
86   struct hash<std::vector<TValueType>> {
operator ()std::hash87     size_t operator()(std::vector<TValueType> const& vec) const {
88       size_t seed = 0;
89       for (auto const& x : vec) {
90         seed ^= std::hash<TValueType>{}(x) + 0x9e3779b9 + (seed << 6)
91                 + (seed >> 2);
92       }
93       return seed;
94     }
95   };
96 }  // namespace std
97 #endif  // LIBSEMIGROUPS_INCLUDE_STL_HPP_
98