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