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_STL_HPP_ 23 #define LIBSEMIGROUPS_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 template <typename TContainer, typename TPerm> apply_permutation(TContainer & cont1,TContainer & cont2,TPerm p)50 void apply_permutation(TContainer& cont1, TContainer& cont2, TPerm p) { 51 size_t const n = p.size(); 52 for (size_t i = 0; i < n; ++i) { 53 size_t current = i; 54 while (i != p[current]) { 55 size_t next = p[current]; 56 std::swap(cont1[current], cont1[next]); 57 std::swap(cont2[current], cont2[next]); 58 p[current] = current; 59 current = next; 60 } 61 p[current] = current; 62 } 63 } 64 65 // C++11 is missing make_unique. The following implementation is from Item 66 // 21 in "Effective Modern C++" by Scott Meyers. 67 template <typename T, typename... Ts> make_unique(Ts &&...params)68 std::unique_ptr<T> make_unique(Ts&&... params) { 69 return std::unique_ptr<T>(new T(std::forward<Ts>(params)...)); 70 } 71 72 // Since std::is_invocable is only introduced in C++17, we use this 73 // from: https://stackoverflow.com/q/15393938/ 74 // Only works if there are no overloads of operator() in type T. 75 template <typename T, typename = void> 76 struct IsCallable : std::is_function<T> {}; 77 78 template <typename T> 79 struct IsCallable< 80 T, 81 typename std::enable_if< 82 std::is_same<decltype(void(&T::operator())), void>::value>::type> 83 : std::true_type {}; 84 85 } // namespace detail 86 } // namespace libsemigroups 87 88 namespace std { 89 template <typename TValueType, size_t N> 90 struct hash<std::array<TValueType, N>> { operator ()std::hash91 size_t operator()(std::array<TValueType, N> const& ar) const { 92 size_t seed = 0; 93 for (auto const& x : ar) { 94 seed ^= std::hash<TValueType>{}(x) + 0x9e3779b9 + (seed << 6) 95 + (seed >> 2); 96 } 97 return seed; 98 } 99 }; 100 101 template <typename TValueType> 102 struct hash<std::vector<TValueType>> { operator ()std::hash103 size_t operator()(std::vector<TValueType> const& vec) const { 104 size_t seed = 0; 105 for (auto const& x : vec) { 106 seed ^= std::hash<TValueType>{}(x) + 0x9e3779b9 + (seed << 6) 107 + (seed >> 2); 108 } 109 return seed; 110 } 111 }; 112 } // namespace std 113 #endif // LIBSEMIGROUPS_STL_HPP_ 114