includefrozen algorithm.h1/* * Frozen * Copyright 2016 QuarksLab * * Licensed to the Apache Software Foundation (ASF) under one * or more contributor license agreements. See the NOTICE file * distributed with this work for additional information * regarding copyright ownership. The ASF licenses this file * to you under the Apache License, Version 2.0 (the * "License"); you may not use this file except in compliance * with the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, * software distributed under the License is distributed on an * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * KIND, either express or implied. See the License for the * specific language governing permissions and limitations * under the License. */ #ifndef FROZEN_LETITGO_ALGORITHM_H #define FROZEN_LETITGO_ALGORITHM_H #include "frozen/bits/basic_types.h" #include "frozen/bits/version.h" #include "frozen/string.h" namespace frozen { // 'search' implementation if C++17 is not available // https://en.cppreference.com/w/cpp/algorithm/search template ForwardIterator search(ForwardIterator first, ForwardIterator last, const Searcher & searcher) { return searcher(first, last).first; } // text book implementation from // https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm template class knuth_morris_pratt_searcher { bits::carray step_; bits::carray needle_; static constexpr bits::carray build_kmp_cache(char const (&needle)[size + 1]) { std::ptrdiff_t cnd = 0; bits::carray cache(-1); for (std::size_t pos = 1; pos < size; ++pos) { if (needle[pos] == needle[cnd]) { cache[pos] = cache[cnd]; cnd += 1; } else { cache[pos] = cnd; cnd = cache[cnd]; while (cnd >= 0 && needle[pos] != needle[cnd]) cnd = cache[cnd]; cnd += 1; } } return cache; } public: constexpr knuth_morris_pratt_searcher(char const (&needle)[size + 1]) : step_{build_kmp_cache(needle)}, needle_(needle) {} template constexpr std::pair operator()(ForwardIterator first, ForwardIterator last) const { std::size_t i = 0; ForwardIterator iter = first; while (iter != last) { if (needle_[i] == *iter) { if (i == (size - 1)) return { iter - i, iter - i + size }; ++i; ++iter; } else { if (step_[i] > -1) { i = step_[i]; } else { ++iter; i = 0; } } } return { last, last }; } }; template constexpr knuth_morris_pratt_searcher make_knuth_morris_pratt_searcher(char const (&needle)[N]) { return {needle}; } // text book implementation from // https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm template class boyer_moore_searcher { using skip_table_type = bits::carray; using suffix_table_type = bits::carray; skip_table_type skip_table_; suffix_table_type suffix_table_; bits::carray needle_; constexpr auto build_skip_table(char const (&needle)[size + 1]) { skip_table_type skip_table(size); for (std::size_t i = 0; i < size - 1; ++i) skip_table[needle[i]] -= i + 1; return skip_table; } constexpr bool is_prefix(char const (&needle)[size + 1], std::size_t pos) { std::size_t suffixlen = size - pos; for (std::size_t i = 0; i < suffixlen; i++) { if (needle[i] != needle[pos + i]) return false; } return true; } constexpr std::size_t suffix_length(char const (&needle)[size + 1], std::size_t pos) { // increment suffix length slen to the first mismatch or beginning // of the word for (std::size_t slen = 0; slen < pos ; slen++) if (needle[pos - slen] != needle[size - 1 - slen]) return slen; return pos; } constexpr auto build_suffix_table(char const (&needle)[size + 1]) { suffix_table_type suffix; std::ptrdiff_t last_prefix_index = size - 1; // first loop for (std::ptrdiff_t p = size - 1; p >= 0; p--) { if (is_prefix(needle, p + 1)) last_prefix_index = p + 1; suffix[p] = last_prefix_index + (size - 1 - p); } // second loop for (std::size_t p = 0; p < size - 1; p++) { auto slen = suffix_length(needle, p); if (needle[p - slen] != needle[size - 1 - slen]) suffix[size - 1 - slen] = size - 1 - p + slen; } return suffix; } public: constexpr boyer_moore_searcher(char const (&needle)[size + 1]) : skip_table_{build_skip_table(needle)}, suffix_table_{build_suffix_table(needle)}, needle_(needle) {} template constexpr std::pair operator()(RandomAccessIterator first, RandomAccessIterator last) const { if (size == 0) return { first, first }; if (size > size_t(last - first)) return { last, last }; RandomAccessIterator iter = first + size - 1; while (true) { std::ptrdiff_t j = size - 1; while (j > 0 && (*iter == needle_[j])) { --iter; --j; } if (j == 0 && *iter == needle_[0]) return { iter, iter + size}; std::ptrdiff_t jump = std::max(skip_table_[*iter], suffix_table_[j]); if (jump >= last - iter) return { last, last }; iter += jump; } } }; template constexpr boyer_moore_searcher make_boyer_moore_searcher(char const (&needle)[N]) { return {needle}; } } // namespace frozen #endif bits algorithms.h+/* * Frozen * Copyright 2016 QuarksLab * * Licensed to the Apache Software Foundation (ASF) under one * or more contributor license agreements. See the NOTICE file * distributed with this work for additional information * regarding copyright ownership. The ASF licenses this file * to you under the Apache License, Version 2.0 (the * "License"); you may not use this file except in compliance * with the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, * software distributed under the License is distributed on an * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * KIND, either express or implied. See the License for the * specific language governing permissions and limitations * under the License. */ #ifndef FROZEN_LETITGO_BITS_ALGORITHMS_H #define FROZEN_LETITGO_BITS_ALGORITHMS_H #include "frozen/bits/basic_types.h" #include #include namespace frozen { namespace bits { auto constexpr next_highest_power_of_two(std::size_t v) { // https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 constexpr auto trip_count = std::numeric_limits::digits; v--; for(std::size_t i = 1; i < trip_count; i <<= 1) v |= v >> i; v++; return v; } template auto constexpr log(T v) { std::size_t n = 0; while (v > 1) { n += 1; v >>= 1; } return n; } constexpr std::size_t bit_weight(std::size_t n) { return (n <= 8*sizeof(unsigned int)) + (n <= 8*sizeof(unsigned long)) + (n <= 8*sizeof(unsigned long long)) + (n <= 128); } unsigned int select_uint_least(std::integral_constant); unsigned long select_uint_least(std::integral_constant); unsigned long long select_uint_least(std::integral_constant); template unsigned long long select_uint_least(std::integral_constant) { static_assert(N < 2, "unsupported type size"); return {}; } template using select_uint_least_t = decltype(select_uint_least(std::integral_constant())); template constexpr auto min_element(Iter begin, const Iter end, Compare const &compare) { auto result = begin; while (begin != end) { if (compare(*begin, *result)) { result = begin; } ++begin; } return result; } template constexpr void cswap(T &a, T &b) { auto tmp = a; a = b; b = tmp; } template constexpr void cswap(std::pair & a, std::pair & b) { cswap(a.first, b.first); cswap(a.second, b.second); } template constexpr void cswap(std::tuple &a, std::tuple &b, std::index_sequence) { using swallow = int[]; (void) swallow{(cswap(std::get(a), std::get(b)), 0)...}; } template constexpr void cswap(std::tuple &a, std::tuple &b) { cswap(a, b, std::make_index_sequence()); } template constexpr void iter_swap(Iter a, Iter b) { cswap(*a, *b); } template constexpr Iterator partition(Iterator left, Iterator right, Compare const &compare) { auto pivot = left + (right - left) / 2; iter_swap(right, pivot); pivot = right; for (auto it = left; 0 < right - it; ++it) { if (compare(*it, *pivot)) { iter_swap(it, left); left++; } } iter_swap(pivot, left); pivot = left; return pivot; } template constexpr void quicksort(Iterator left, Iterator right, Compare const &compare) { while (0 < right - left) { auto new_pivot = bits::partition(left, right, compare); quicksort(left, new_pivot, compare); left = new_pivot + 1; } } template constexpr Container quicksort(Container const &array, Compare const &compare) { Container res = array; quicksort(res.begin(), res.end() - 1, compare); return res; } template struct LowerBound { T const &value_; Compare const &compare_; constexpr LowerBound(T const &value, Compare const &compare) : value_(value), compare_(compare) {} template inline constexpr ForwardIt doit_fast(ForwardIt first, std::integral_constant) { return first; } template inline constexpr ForwardIt doit_fast(ForwardIt first, std::integral_constant) { auto constexpr step = N / 2; static_assert(N/2 == N - N / 2 - 1, "power of two minus 1"); auto it = first + step; auto next_it = compare_(*it, value_) ? it + 1 : first; return doit_fast(next_it, std::integral_constant{}); } template inline constexpr ForwardIt doitfirst(ForwardIt first, std::integral_constant, std::integral_constant) { return doit_fast(first, std::integral_constant{}); } template inline constexpr ForwardIt doitfirst(ForwardIt first, std::integral_constant, std::integral_constant) { auto constexpr next_power = next_highest_power_of_two(N); auto constexpr next_start = next_power / 2 - 1; auto it = first + next_start; if (compare_(*it, value_)) { auto constexpr next = N - next_start - 1; return doitfirst(it + 1, std::integral_constant{}, std::integral_constant{}); } else return doit_fast(first, std::integral_constant{}); } template inline constexpr ForwardIt doitfirst(ForwardIt first, std::integral_constant, std::integral_constant) { return doit_fast(first, std::integral_constant{}); } }; template constexpr ForwardIt lower_bound(ForwardIt first, const T &value, Compare const &compare) { return LowerBound{value, compare}.doitfirst(first, std::integral_constant{}, std::integral_constant{}); } template constexpr bool binary_search(ForwardIt first, const T &value, Compare const &compare) { ForwardIt where = lower_bound(first, value, compare); return (!(where == first + N) && !(compare(value, *where))); } template constexpr bool equal(InputIt1 first1, InputIt1 last1, InputIt2 first2) { for (; first1 != last1; ++first1, ++first2) { if (!(*first1 == *first2)) { return false; } } return true; } template constexpr bool lexicographical_compare(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2) { for (; (first1 != last1) && (first2 != last2); ++first1, ++first2) { if (*first1 < *first2) return true; if (*first2 < *first1) return false; } return (first1 == last1) && (first2 != last2); } } // namespace bits } // namespace frozen #endif basic_types.h|/* * Frozen * Copyright 2016 QuarksLab * * Licensed to the Apache Software Foundation (ASF) under one * or more contributor license agreements. See the NOTICE file * distributed with this work for additional information * regarding copyright ownership. The ASF licenses this file * to you under the Apache License, Version 2.0 (the * "License"); you may not use this file except in compliance * with the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, * software distributed under the License is distributed on an * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * KIND, either express or implied. See the License for the * specific language governing permissions and limitations * under the License. */ #ifndef FROZEN_LETITGO_BASIC_TYPES_H #define FROZEN_LETITGO_BASIC_TYPES_H #include "frozen/bits/exceptions.h" #include #include #include #include namespace frozen { namespace bits { // used as a fake argument for frozen::make_set and frozen::make_map in the case of N=0 struct ignored_arg {}; template class cvector { T data [N] = {}; // zero-initialization for scalar type T, default-initialized otherwise std::size_t dsize = 0; public: // Container typdefs using value_type = T; using reference = value_type &; using const_reference = const value_type &; using pointer = value_type *; using const_pointer = const value_type *; using iterator = pointer; using const_iterator = const_pointer; using size_type = std::size_t; using difference_type = std::ptrdiff_t; // Constructors constexpr cvector(void) = default; constexpr cvector(size_type count, const T& value) : dsize(count) { for (std::size_t i = 0; i < N; ++i) data[i] = value; } // Iterators constexpr iterator begin() noexcept { return data; } constexpr iterator end() noexcept { return data + dsize; } constexpr const_iterator begin() const noexcept { return data; } constexpr const_iterator end() const noexcept { return data + dsize; } // Capacity constexpr size_type size() const { return dsize; } // Element access constexpr reference operator[](std::size_t index) { return data[index]; } constexpr const_reference operator[](std::size_t index) const { return data[index]; } constexpr reference back() { return data[dsize - 1]; } constexpr const_reference back() const { return data[dsize - 1]; } // Modifiers constexpr void push_back(const T & a) { data[dsize++] = a; } constexpr void push_back(T && a) { data[dsize++] = std::move(a); } constexpr void pop_back() { --dsize; } constexpr void clear() { dsize = 0; } }; template class carray { T data_ [N] = {}; // zero-initialization for scalar type T, default-initialized otherwise template constexpr carray(Iter iter, std::index_sequence) : data_{((void)I, *iter++)...} {} template constexpr carray(const T& value, std::index_sequence) : data_{((void)I, value)...} {} public: // Container typdefs using value_type = T; using reference = value_type &; using const_reference = const value_type &; using pointer = value_type *; using const_pointer = const value_type *; using iterator = pointer; using const_iterator = const_pointer; using size_type = std::size_t; using difference_type = std::ptrdiff_t; // Constructors constexpr carray() = default; constexpr carray(const value_type& val) : carray(val, std::make_index_sequence()) {} template ::value, std::size_t> M> constexpr carray(U const (&init)[M]) : carray(init, std::make_index_sequence()) { static_assert(M >= N, "Cannot initialize a carray with an smaller array"); } template ::value, std::size_t> M> constexpr carray(std::array const &init) : carray(init.begin(), std::make_index_sequence()) { static_assert(M >= N, "Cannot initialize a carray with an smaller array"); } template ::value>* = nullptr> constexpr carray(std::initializer_list init) : carray(init.begin(), std::make_index_sequence()) { // clang & gcc doesn't recognize init.size() as a constexpr // static_assert(init.size() >= N, "Cannot initialize a carray with an smaller initializer list"); } template ::value>* = nullptr> constexpr carray(const carray& rhs) : carray(rhs.begin(), std::make_index_sequence()) { } // Iterators constexpr iterator begin() noexcept { return data_; } constexpr const_iterator begin() const noexcept { return data_; } constexpr iterator end() noexcept { return data_ + N; } constexpr const_iterator end() const noexcept { return data_ + N; } // Capacity constexpr size_type size() const { return N; } constexpr size_type max_size() const { return N; } // Element access constexpr reference operator[](std::size_t index) { return data_[index]; } constexpr const_reference operator[](std::size_t index) const { return data_[index]; } constexpr reference at(std::size_t index) { if (index > N) FROZEN_THROW_OR_ABORT(std::out_of_range("Index (" + std::to_string(index) + ") out of bound (" + std::to_string(N) + ')')); return data_[index]; } constexpr const_reference at(std::size_t index) const { if (index > N) FROZEN_THROW_OR_ABORT(std::out_of_range("Index (" + std::to_string(index) + ") out of bound (" + std::to_string(N) + ')')); return data_[index]; } constexpr reference front() { return data_[0]; } constexpr const_reference front() const { return data_[0]; } constexpr reference back() { return data_[N - 1]; } constexpr const_reference back() const { return data_[N - 1]; } constexpr value_type* data() noexcept { return data_; } constexpr const value_type* data() const noexcept { return data_; } }; template class carray { public: // Container typdefs using value_type = T; using reference = value_type &; using const_reference = const value_type &; using pointer = value_type *; using const_pointer = const value_type *; using iterator = pointer; using const_iterator = const_pointer; using size_type = std::size_t; using difference_type = std::ptrdiff_t; // Constructors constexpr carray(void) = default; }; } // namespace bits } // namespace frozen #endif constexpr_assert.h€/* * Frozen * Copyright 2016 QuarksLab * * Licensed to the Apache Software Foundation (ASF) under one * or more contributor license agreements. See the NOTICE file * distributed with this work for additional information * regarding copyright ownership. The ASF licenses this file * to you under the Apache License, Version 2.0 (the * "License"); you may not use this file except in compliance * with the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, * software distributed under the License is distributed on an * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * KIND, either express or implied. See the License for the * specific language governing permissions and limitations * under the License. */ #ifndef FROZEN_LETITGO_CONSTEXPR_ASSERT_H #define FROZEN_LETITGO_CONSTEXPR_ASSERT_H #include #ifdef _MSC_VER // FIXME: find a way to implement that correctly for msvc #define constexpr_assert(cond, msg) #else #define constexpr_assert(cond, msg)\ assert(cond && msg); #endif #endif defines.hê/* * Frozen * Copyright 2016 QuarksLab * * Licensed to the Apache Software Foundation (ASF) under one * or more contributor license agreements. See the NOTICE file * distributed with this work for additional information * regarding copyright ownership. The ASF licenses this file * to you under the Apache License, Version 2.0 (the * "License"); you may not use this file except in compliance * with the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, * software distributed under the License is distributed on an * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * KIND, either express or implied. See the License for the * specific language governing permissions and limitations * under the License. */ #ifndef FROZEN_LETITGO_DEFINES_H #define FROZEN_LETITGO_DEFINES_H #if defined(_MSVC_LANG) && !(defined(__EDG__) && defined(__clang__)) // TRANSITION, VSO#273681 #define FROZEN_LETITGO_IS_MSVC #endif // Code taken from https://stackoverflow.com/questions/43639122/which-values-can-msvc-lang-have #if defined(FROZEN_LETITGO_IS_MSVC) #if _MSVC_LANG > 201402 #define FROZEN_LETITGO_HAS_CXX17 1 #else /* _MSVC_LANG > 201402 */ #define FROZEN_LETITGO_HAS_CXX17 0 #endif /* _MSVC_LANG > 201402 */ #else /* _MSVC_LANG etc. */ #if __cplusplus > 201402 #define FROZEN_LETITGO_HAS_CXX17 1 #else /* __cplusplus > 201402 */ #define FROZEN_LETITGO_HAS_CXX17 0 #endif /* __cplusplus > 201402 */ #endif /* _MSVC_LANG etc. */ // End if taken code #if FROZEN_LETITGO_HAS_CXX17 == 1 && defined(FROZEN_LETITGO_IS_MSVC) #define FROZEN_LETITGO_HAS_STRING_VIEW // We assume Visual Studio always has string_view in C++17 #else #if FROZEN_LETITGO_HAS_CXX17 == 1 && __has_include() #define FROZEN_LETITGO_HAS_STRING_VIEW #endif #endif #ifdef __cpp_char8_t #define FROZEN_LETITGO_HAS_CHAR8T #endif #if defined(__cpp_deduction_guides) && __cpp_deduction_guides >= 201703L #define FROZEN_LETITGO_HAS_DEDUCTION_GUIDES #endif #if defined(__cpp_lib_constexpr_string) && __cpp_lib_constexpr_string >= 201907L #define FROZEN_LETITGO_HAS_CONSTEXPR_STRING #endif #endif // FROZEN_LETITGO_DEFINES_H elsa.h5/* * Frozen * Copyright 2016 QuarksLab * * Licensed to the Apache Software Foundation (ASF) under one * or more contributor license agreements. See the NOTICE file * distributed with this work for additional information * regarding copyright ownership. The ASF licenses this file * to you under the Apache License, Version 2.0 (the * "License"); you may not use this file except in compliance * with the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, * software distributed under the License is distributed on an * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * KIND, either express or implied. See the License for the * specific language governing permissions and limitations * under the License. */ #ifndef FROZEN_LETITGO_ELSA_H #define FROZEN_LETITGO_ELSA_H #include namespace frozen { template struct elsa { static_assert(std::is_integral::value || std::is_enum::value, "only supports integral types, specialize for other types"); constexpr std::size_t operator()(T const &value, std::size_t seed) const { std::size_t key = seed ^ static_cast(value); key = (~key) + (key << 21); // key = (key << 21) - key - 1; key = key ^ (key >> 24); key = (key + (key << 3)) + (key << 8); // key * 265 key = key ^ (key >> 14); key = (key + (key << 2)) + (key << 4); // key * 21 key = key ^ (key >> 28); key = key + (key << 31); return key; } }; template <> struct elsa { template constexpr std::size_t operator()(T const &value, std::size_t seed) const { return elsa{}(value, seed); } }; template using anna = elsa; } // namespace frozen #endif elsa_std.h)#ifndef FROZEN_LETITGO_BITS_ELSA_STD_H #define FROZEN_LETITGO_BITS_ELSA_STD_H #include "defines.h" #include "elsa.h" #include "hash_string.h" #ifdef FROZEN_LETITGO_HAS_STRING_VIEW #include #endif #include namespace frozen { #ifdef FROZEN_LETITGO_HAS_STRING_VIEW template struct elsa> { constexpr std::size_t operator()(const std::basic_string_view& value) const { return hash_string(value); } constexpr std::size_t operator()(const std::basic_string_view& value, std::size_t seed) const { return hash_string(value, seed); } }; #endif template struct elsa> { constexpr std::size_t operator()(const std::basic_string& value) const { return hash_string(value); } constexpr std::size_t operator()(const std::basic_string& value, std::size_t seed) const { return hash_string(value, seed); } }; } // namespace frozen #endif // FROZEN_LETITGO_BITS_ELSA_STD_H exceptions.h¿/* * Frozen * Copyright 2016 QuarksLab * * Licensed to the Apache Software Foundation (ASF) under one * or more contributor license agreements. See the NOTICE file * distributed with this work for additional information * regarding copyright ownership. The ASF licenses this file * to you under the Apache License, Version 2.0 (the * "License"); you may not use this file except in compliance * with the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, * software distributed under the License is distributed on an * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * KIND, either express or implied. See the License for the * specific language governing permissions and limitations * under the License. */ #ifndef FROZEN_LETITGO_EXCEPTIONS_H #define FROZEN_LETITGO_EXCEPTIONS_H #if defined(FROZEN_NO_EXCEPTIONS) || (defined(_MSC_VER) && !defined(_CPPUNWIND)) || (!defined(_MSC_VER) && !defined(__cpp_exceptions)) #include #define FROZEN_THROW_OR_ABORT(_) std::abort() #else #include #define FROZEN_THROW_OR_ABORT(err) throw err #endif #endif hash_string.hL#ifndef FROZEN_LETITGO_BITS_HASH_STRING_H #define FROZEN_LETITGO_BITS_HASH_STRING_H #include namespace frozen { template constexpr std::size_t hash_string(const String& value) { std::size_t d = 5381; for (const auto& c : value) d = d * 33 + static_cast(c); return d; } // https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function // With the lowest bits removed, based on experimental setup. template constexpr std::size_t hash_string(const String& value, std::size_t seed) { std::size_t d = (0x811c9dc5 ^ seed) * static_cast(0x01000193); for (const auto& c : value) d = (d ^ static_cast(c)) * static_cast(0x01000193); return d >> 8 ; } } // namespace frozen #endif // FROZEN_LETITGO_BITS_HASH_STRING_Hmpl.hÖ/* * Frozen * Copyright 2022 Giel van Schijndel * * Licensed to the Apache Software Foundation (ASF) under one * or more contributor license agreements. See the NOTICE file * distributed with this work for additional information * regarding copyright ownership. The ASF licenses this file * to you under the Apache License, Version 2.0 (the * "License"); you may not use this file except in compliance * with the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, * software distributed under the License is distributed on an * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * KIND, either express or implied. See the License for the * specific language governing permissions and limitations * under the License. */ #ifndef FROZEN_LETITGO_BITS_MPL_H #define FROZEN_LETITGO_BITS_MPL_H #include namespace frozen { namespace bits { // Forward declarations template class carray; template struct remove_cv : std::remove_cv {}; template struct remove_cv> { using type = std::pair::type...>; }; template struct remove_cv> { using type = carray::type, N>; }; template using remove_cv_t = typename remove_cv::type; } // namespace bits } // namespace frozen #endif pmh.h#Ÿ/* * Frozen * Copyright 2016 QuarksLab * * Licensed to the Apache Software Foundation (ASF) under one * or more contributor license agreements. See the NOTICE file * distributed with this work for additional information * regarding copyright ownership. The ASF licenses this file * to you under the Apache License, Version 2.0 (the * "License"); you may not use this file except in compliance * with the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, * software distributed under the License is distributed on an * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * KIND, either express or implied. See the License for the * specific language governing permissions and limitations * under the License. */ // inspired from http://stevehanov.ca/blog/index.php?id=119 #ifndef FROZEN_LETITGO_PMH_H #define FROZEN_LETITGO_PMH_H #include "frozen/bits/algorithms.h" #include "frozen/bits/basic_types.h" #include #include #include #include namespace frozen { namespace bits { // Function object for sorting buckets in decreasing order of size struct bucket_size_compare { template bool constexpr operator()(B const &b0, B const &b1) const { return b0.size() > b1.size(); } }; // Step One in pmh routine is to take all items and hash them into buckets, // with some collisions. Then process those buckets further to build a perfect // hash function. // pmh_buckets represents the initial placement into buckets. template struct pmh_buckets { // Step 0: Bucket max is 2 * sqrt M // TODO: Come up with justification for this, should it not be O(log M)? static constexpr auto bucket_max = 2 * (1u << (log(M) / 2)); using bucket_t = cvector; carray buckets; std::uint64_t seed; // Represents a reference to a bucket. This is used because the buckets // have to be sorted, but buckets are big, making it slower than sorting refs struct bucket_ref { unsigned hash; const bucket_t * ptr; // Forward some interface of bucket using value_type = typename bucket_t::value_type; using const_iterator = typename bucket_t::const_iterator; constexpr auto size() const { return ptr->size(); } constexpr const auto & operator[](std::size_t idx) const { return (*ptr)[idx]; } constexpr auto begin() const { return ptr->begin(); } constexpr auto end() const { return ptr->end(); } }; // Make a bucket_ref for each bucket template carray constexpr make_bucket_refs(std::index_sequence) const { return {{ bucket_ref{Is, &buckets[Is]}... }}; } // Makes a bucket_ref for each bucket and sorts them by size carray constexpr get_sorted_buckets() const { carray result{this->make_bucket_refs(std::make_index_sequence())}; bits::quicksort(result.begin(), result.end() - 1, bucket_size_compare{}); return result; } }; template pmh_buckets constexpr make_pmh_buckets(const carray & items, Hash const & hash, Key const & key, PRG & prg) { using result_t = pmh_buckets; // Continue until all items are placed without exceeding bucket_max while (1) { result_t result{}; result.seed = prg(); bool rejected = false; for (std::size_t i = 0; i < items.size(); ++i) { auto & bucket = result.buckets[hash(key(items[i]), static_cast(result.seed)) % M]; if (bucket.size() >= result_t::bucket_max) { rejected = true; break; } bucket.push_back(i); } if (!rejected) { return result; } } } // Check if an item appears in a cvector template constexpr bool all_different_from(cvector & data, T & a) { for (std::size_t i = 0; i < data.size(); ++i) if (data[i] == a) return false; return true; } // Represents either an index to a data item array, or a seed to be used with // a hasher. Seed must have high bit of 1, value has high bit of zero. struct seed_or_index { using value_type = std::uint64_t; private: static constexpr value_type MINUS_ONE = std::numeric_limits::max(); static constexpr value_type HIGH_BIT = ~(MINUS_ONE >> 1); value_type value_ = 0; public: constexpr value_type value() const { return value_; } constexpr bool is_seed() const { return value_ & HIGH_BIT; } constexpr seed_or_index(bool is_seed, value_type value) : value_(is_seed ? (value | HIGH_BIT) : (value & ~HIGH_BIT)) {} constexpr seed_or_index() = default; constexpr seed_or_index(const seed_or_index &) = default; constexpr seed_or_index & operator =(const seed_or_index &) = default; }; // Represents the perfect hash function created by pmh algorithm template struct pmh_tables : private Hasher { std::uint64_t first_seed_; carray first_table_; carray second_table_; constexpr pmh_tables( std::uint64_t first_seed, carray first_table, carray second_table, Hasher hash) noexcept : Hasher(hash) , first_seed_(first_seed) , first_table_(first_table) , second_table_(second_table) {} constexpr Hasher const& hash_function() const noexcept { return static_cast(*this); } template constexpr std::size_t lookup(const KeyType & key) const { return lookup(key, hash_function()); } // Looks up a given key, to find its expected index in carray // Always returns a valid index, must use KeyEqual test after to confirm. template constexpr std::size_t lookup(const KeyType & key, const HasherType& hasher) const { auto const d = first_table_[hasher(key, static_cast(first_seed_)) % M]; if (!d.is_seed()) { return static_cast(d.value()); } // this is narrowing std::uint64 -> std::size_t but should be fine else { return second_table_[hasher(key, static_cast(d.value())) % M]; } } }; // Make pmh tables for given items, hash function, prg, etc. template pmh_tables constexpr make_pmh_tables(const carray & items, Hash const &hash, Key const &key, PRG prg) { // Step 1: Place all of the keys into buckets auto step_one = make_pmh_buckets(items, hash, key, prg); // Step 2: Sort the buckets to process the ones with the most items first. auto buckets = step_one.get_sorted_buckets(); // Special value for unused slots. This is purposefully the index // one-past-the-end of 'items' to function as a sentinel value. Both to avoid // the need to apply the KeyEqual predicate and to be easily convertible to // end(). // Unused entries in both hash tables (G and H) have to contain this value. const auto UNUSED = items.size(); // G becomes the first hash table in the resulting pmh function carray G({false, UNUSED}); // H becomes the second hash table in the resulting pmh function carray H(UNUSED); // Step 3: Map the items in buckets into hash tables. for (const auto & bucket : buckets) { auto const bsize = bucket.size(); if (bsize == 1) { // Store index to the (single) item in G // assert(bucket.hash == hash(key(items[bucket[0]]), step_one.seed) % M); G[bucket.hash] = {false, static_cast(bucket[0])}; } else if (bsize > 1) { // Repeatedly try different H of d until we find a hash function // that places all items in the bucket into free slots seed_or_index d{true, prg()}; cvector bucket_slots; while (bucket_slots.size() < bsize) { auto slot = hash(key(items[bucket[bucket_slots.size()]]), static_cast(d.value())) % M; if (H[slot] != UNUSED || !all_different_from(bucket_slots, slot)) { bucket_slots.clear(); d = {true, prg()}; continue; } bucket_slots.push_back(slot); } // Put successful seed in G, and put indices to items in their slots // assert(bucket.hash == hash(key(items[bucket[0]]), step_one.seed) % M); G[bucket.hash] = d; for (std::size_t i = 0; i < bsize; ++i) H[bucket_slots[i]] = bucket[i]; } } return {step_one.seed, G, H, hash}; } } // namespace bits } // namespace frozen #endif version.hú/* * Frozen * Copyright 2016 QuarksLab * * Licensed to the Apache Software Foundation (ASF) under one * or more contributor license agreements. See the NOTICE file * distributed with this work for additional information * regarding copyright ownership. The ASF licenses this file * to you under the Apache License, Version 2.0 (the * "License"); you may not use this file except in compliance * with the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, * software distributed under the License is distributed on an * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * KIND, either express or implied. See the License for the * specific language governing permissions and limitations * under the License. */ #ifndef FROZEN_LETITGO_VERSION_H #define FROZEN_LETITGO_VERSION_H #define FROZEN_MAJOR_VERSION 1 #define FROZEN_MINOR_VERSION 1 #define FROZEN_PATCH_VERSION 1 #endif map.h3/* * Frozen * Copyright 2016 QuarksLab * * Licensed to the Apache Software Foundation (ASF) under one * or more contributor license agreements. See the NOTICE file * distributed with this work for additional information * regarding copyright ownership. The ASF licenses this file * to you under the Apache License, Version 2.0 (the * "License"); you may not use this file except in compliance * with the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, * software distributed under the License is distributed on an * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * KIND, either express or implied. See the License for the * specific language governing permissions and limitations * under the License. */ #ifndef FROZEN_LETITGO_MAP_H #define FROZEN_LETITGO_MAP_H #include "frozen/bits/algorithms.h" #include "frozen/bits/basic_types.h" #include "frozen/bits/constexpr_assert.h" #include "frozen/bits/exceptions.h" #include "frozen/bits/mpl.h" #include "frozen/bits/version.h" #include #include namespace frozen { namespace impl { template class CompareKey : private Comparator { public: constexpr Comparator const& key_comp() const noexcept { return static_cast(*this); } constexpr CompareKey(Comparator const &comparator) : Comparator(comparator) {} template constexpr int operator()(std::pair const &self, std::pair const &other) const { return key_comp()(std::get<0>(self), std::get<0>(other)); } template constexpr int operator()(Key1 const &self_key, std::pair const &other) const { return key_comp()(self_key, std::get<0>(other)); } template constexpr int operator()(std::pair const &self, Key2 const &other_key) const { return key_comp()(std::get<0>(self), other_key); } template constexpr int operator()(Key1 const &self_key, Key2 const &other_key) const { return key_comp()(self_key, other_key); } }; } // namespace impl template > class map : private impl::CompareKey { using container_type = bits::carray, N>; container_type items_; public: using key_type = Key; using mapped_type = Value; using value_type = typename container_type::value_type; using size_type = typename container_type::size_type; using difference_type = typename container_type::difference_type; using key_compare = Compare; using value_compare = impl::CompareKey; using reference = typename container_type::reference; using const_reference = typename container_type::const_reference; using pointer = typename container_type::pointer; using const_pointer = typename container_type::const_pointer; using iterator = typename container_type::iterator; using const_iterator = typename container_type::const_iterator; using reverse_iterator = std::reverse_iterator; using const_reverse_iterator = std::reverse_iterator; public: /* constructors */ constexpr map(container_type items, Compare const &compare) : impl::CompareKey{compare} , items_{bits::quicksort(bits::remove_cv_t(items), value_comp())} {} explicit constexpr map(container_type items) : map{items, Compare{}} {} constexpr map(std::initializer_list items, Compare const &compare) : map{container_type {items}, compare} { constexpr_assert(items.size() == N, "Inconsistent initializer_list size and type size argument"); } constexpr map(std::initializer_list items) : map{items, Compare{}} {} /* element access */ constexpr Value const& at(Key const &key) const { return at_impl(*this, key); } constexpr Value& at(Key const &key) { return at_impl(*this, key); } /* iterators */ constexpr iterator begin() { return items_.begin(); } constexpr const_iterator begin() const { return items_.begin(); } constexpr const_iterator cbegin() const { return items_.begin(); } constexpr iterator end() { return items_.end(); } constexpr const_iterator end() const { return items_.end(); } constexpr const_iterator cend() const { return items_.end(); } constexpr reverse_iterator rbegin() { return reverse_iterator{items_.end()}; } constexpr const_reverse_iterator rbegin() const { return const_reverse_iterator{items_.end()}; } constexpr const_reverse_iterator crbegin() const { return const_reverse_iterator{items_.end()}; } constexpr reverse_iterator rend() { return reverse_iterator{items_.begin()}; } constexpr const_reverse_iterator rend() const { return const_reverse_iterator{items_.begin()}; } constexpr const_reverse_iterator crend() const { return const_reverse_iterator{items_.begin()}; } /* capacity */ constexpr bool empty() const { return !N; } constexpr size_type size() const { return N; } constexpr size_type max_size() const { return N; } /* lookup */ template constexpr std::size_t count(KeyType const &key) const { return bits::binary_search(items_.begin(), key, value_comp()); } template constexpr const_iterator find(KeyType const &key) const { return map::find_impl(*this, key); } template constexpr iterator find(KeyType const &key) { return map::find_impl(*this, key); } template constexpr bool contains(KeyType const &key) const { return this->find(key) != this->end(); } template constexpr std::pair equal_range(KeyType const &key) const { return equal_range_impl(*this, key); } template constexpr std::pair equal_range(KeyType const &key) { return equal_range_impl(*this, key); } template constexpr const_iterator lower_bound(KeyType const &key) const { return lower_bound_impl(*this, key); } template constexpr iterator lower_bound(KeyType const &key) { return lower_bound_impl(*this, key); } template constexpr const_iterator upper_bound(KeyType const &key) const { return upper_bound_impl(*this, key); } template constexpr iterator upper_bound(KeyType const &key) { return upper_bound_impl(*this, key); } /* observers */ constexpr const key_compare& key_comp() const { return value_comp().key_comp(); } constexpr const value_compare& value_comp() const { return static_cast const&>(*this); } private: template static inline constexpr auto& at_impl(This&& self, KeyType const &key) { auto where = self.find(key); if (where != self.end()) return where->second; else FROZEN_THROW_OR_ABORT(std::out_of_range("unknown key")); } template static inline constexpr auto find_impl(This&& self, KeyType const &key) { auto where = self.lower_bound(key); if (where != self.end() && !self.value_comp()(key, *where)) return where; else return self.end(); } template static inline constexpr auto equal_range_impl(This&& self, KeyType const &key) { auto lower = self.lower_bound(key); using lower_t = decltype(lower); if (lower != self.end() && !self.value_comp()(key, *lower)) return std::pair{lower, lower + 1}; else return std::pair{lower, lower}; } template static inline constexpr auto lower_bound_impl(This&& self, KeyType const &key) -> decltype(self.end()) { return bits::lower_bound(self.items_.begin(), key, self.value_comp()); } template static inline constexpr auto upper_bound_impl(This&& self, KeyType const &key) { auto lower = self.lower_bound(key); if (lower != self.end() && !self.value_comp()(key, *lower)) return lower + 1; else return lower; } }; template class map : private impl::CompareKey { using container_type = bits::carray, 0>; public: using key_type = Key; using mapped_type = Value; using value_type = typename container_type::value_type; using size_type = typename container_type::size_type; using difference_type = typename container_type::difference_type; using key_compare = Compare; using value_compare = impl::CompareKey; using reference = typename container_type::reference; using const_reference = typename container_type::const_reference; using pointer = typename container_type::pointer; using const_pointer = typename container_type::const_pointer; using iterator = pointer; using const_iterator = const_pointer; using reverse_iterator = pointer; using const_reverse_iterator = const_pointer; public: /* constructors */ constexpr map(const map &other) = default; constexpr map(std::initializer_list, Compare const &compare) : impl::CompareKey{compare} {} constexpr map(std::initializer_list items) : map{items, Compare{}} {} /* element access */ template constexpr mapped_type at(KeyType const &) const { FROZEN_THROW_OR_ABORT(std::out_of_range("invalid key")); } template constexpr mapped_type at(KeyType const &) { FROZEN_THROW_OR_ABORT(std::out_of_range("invalid key")); } /* iterators */ constexpr iterator begin() { return nullptr; } constexpr const_iterator begin() const { return nullptr; } constexpr const_iterator cbegin() const { return nullptr; } constexpr iterator end() { return nullptr; } constexpr const_iterator end() const { return nullptr; } constexpr const_iterator cend() const { return nullptr; } constexpr reverse_iterator rbegin() { return nullptr; } constexpr const_reverse_iterator rbegin() const { return nullptr; } constexpr const_reverse_iterator crbegin() const { return nullptr; } constexpr reverse_iterator rend() { return nullptr; } constexpr const_reverse_iterator rend() const { return nullptr; } constexpr const_reverse_iterator crend() const { return nullptr; } /* capacity */ constexpr bool empty() const { return true; } constexpr size_type size() const { return 0; } constexpr size_type max_size() const { return 0; } /* lookup */ template constexpr std::size_t count(KeyType const &) const { return 0; } template constexpr const_iterator find(KeyType const &) const { return end(); } template constexpr iterator find(KeyType const &) { return end(); } template constexpr std::pair equal_range(KeyType const &) const { return {end(), end()}; } template constexpr std::pair equal_range(KeyType const &) { return {end(), end()}; } template constexpr const_iterator lower_bound(KeyType const &) const { return end(); } template constexpr iterator lower_bound(KeyType const &) { return end(); } template constexpr const_iterator upper_bound(KeyType const &) const { return end(); } template constexpr iterator upper_bound(KeyType const &) { return end(); } /* observers */ constexpr key_compare const& key_comp() const { return value_comp().key_comp(); } constexpr value_compare const& value_comp() const { return static_cast const&>(*this); } }; template > constexpr auto make_map(bits::ignored_arg = {}/* for consistency with the initializer below for N = 0*/) { return map{}; } template constexpr auto make_map(std::pair const (&items)[N]) { return map{items}; } template constexpr auto make_map(std::array, N> const &items) { return map{items}; } template constexpr auto make_map(std::pair const (&items)[N], Compare const& compare = Compare{}) { return map{items, compare}; } template constexpr auto make_map(std::array, N> const &items, Compare const& compare = Compare{}) { return map{items, compare}; } } // namespace frozen #endif random.h ê/* * Frozen * Copyright 2016 QuarksLab * * Licensed to the Apache Software Foundation (ASF) under one * or more contributor license agreements. See the NOTICE file * distributed with this work for additional information * regarding copyright ownership. The ASF licenses this file * to you under the Apache License, Version 2.0 (the * "License"); you may not use this file except in compliance * with the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, * software distributed under the License is distributed on an * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * KIND, either express or implied. See the License for the * specific language governing permissions and limitations * under the License. */ #ifndef FROZEN_LETITGO_RANDOM_H #define FROZEN_LETITGO_RANDOM_H #include "frozen/bits/algorithms.h" #include "frozen/bits/version.h" #include #include namespace frozen { template class linear_congruential_engine { static_assert(std::is_unsigned::value, "UIntType must be an unsigned integral type"); template static constexpr UIntType modulo(T val, std::integral_constant) { return static_cast(val); } template static constexpr UIntType modulo(T val, std::integral_constant) { // the static cast below may end up doing a truncation return static_cast(val % M); } public: using result_type = UIntType; static constexpr result_type multiplier = a; static constexpr result_type increment = c; static constexpr result_type modulus = m; static constexpr result_type default_seed = 1u; linear_congruential_engine() = default; constexpr linear_congruential_engine(result_type s) { seed(s); } void seed(result_type s = default_seed) { state_ = s; } constexpr result_type operator()() { using uint_least_t = bits::select_uint_least_t; uint_least_t tmp = static_cast(multiplier) * state_ + increment; state_ = modulo(tmp, std::integral_constant()); return state_; } constexpr void discard(unsigned long long n) { while (n--) operator()(); } static constexpr result_type min() { return increment == 0u ? 1u : 0u; } static constexpr result_type max() { return modulus - 1u; } friend constexpr bool operator==(linear_congruential_engine const &self, linear_congruential_engine const &other) { return self.state_ == other.state_; } friend constexpr bool operator!=(linear_congruential_engine const &self, linear_congruential_engine const &other) { return !(self == other); } private: result_type state_ = default_seed; }; using minstd_rand0 = linear_congruential_engine; using minstd_rand = linear_congruential_engine; // This generator is used by default in unordered frozen containers using default_prg_t = minstd_rand; } // namespace frozen #endif set.h$y/* * Frozen * Copyright 2016 QuarksLab * * Licensed to the Apache Software Foundation (ASF) under one * or more contributor license agreements. See the NOTICE file * distributed with this work for additional information * regarding copyright ownership. The ASF licenses this file * to you under the Apache License, Version 2.0 (the * "License"); you may not use this file except in compliance * with the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, * software distributed under the License is distributed on an * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * KIND, either express or implied. See the License for the * specific language governing permissions and limitations * under the License. */ #ifndef FROZEN_SET_H #define FROZEN_SET_H #include "frozen/bits/algorithms.h" #include "frozen/bits/basic_types.h" #include "frozen/bits/constexpr_assert.h" #include "frozen/bits/version.h" #include "frozen/bits/defines.h" #include #include namespace frozen { template > class set : private Compare { using container_type = bits::carray; container_type keys_; public: /* container typedefs*/ using key_type = Key; using value_type = Key; using size_type = typename container_type::size_type; using difference_type = typename container_type::size_type; using key_compare = Compare; using value_compare = Compare; using reference = typename container_type::const_reference; using const_reference = reference; using pointer = typename container_type::const_pointer; using const_pointer = pointer; using iterator = typename container_type::const_iterator; using reverse_iterator = std::reverse_iterator; using const_iterator = iterator; using const_reverse_iterator = std::reverse_iterator; public: /* constructors */ constexpr set(const set &other) = default; constexpr set(container_type keys, Compare const & comp) : Compare{comp} , keys_(bits::quicksort(keys, value_comp())) { } explicit constexpr set(container_type keys) : set{keys, Compare{}} {} constexpr set(std::initializer_list keys, Compare const & comp) : set{container_type{keys}, comp} { constexpr_assert(keys.size() == N, "Inconsistent initializer_list size and type size argument"); } constexpr set(std::initializer_list keys) : set{keys, Compare{}} {} constexpr set& operator=(const set &other) = default; /* capacity */ constexpr bool empty() const { return !N; } constexpr size_type size() const { return N; } constexpr size_type max_size() const { return N; } /* lookup */ template constexpr std::size_t count(KeyType const &key) const { return bits::binary_search(keys_.begin(), key, value_comp()); } template constexpr const_iterator find(KeyType const &key) const { const_iterator where = lower_bound(key); if ((where != end()) && !value_comp()(key, *where)) return where; else return end(); } template constexpr bool contains(KeyType const &key) const { return this->find(key) != keys_.end(); } template constexpr std::pair equal_range(KeyType const &key) const { auto const lower = lower_bound(key); if (lower == end()) return {lower, lower}; else return {lower, lower + 1}; } template constexpr const_iterator lower_bound(KeyType const &key) const { auto const where = bits::lower_bound(keys_.begin(), key, value_comp()); if ((where != end()) && !value_comp()(key, *where)) return where; else return end(); } template constexpr const_iterator upper_bound(KeyType const &key) const { auto const where = bits::lower_bound(keys_.begin(), key, value_comp()); if ((where != end()) && !value_comp()(key, *where)) return where + 1; else return end(); } /* observers */ constexpr const key_compare& key_comp() const { return value_comp(); } constexpr const key_compare& value_comp() const { return static_cast(*this); } /* iterators */ constexpr const_iterator begin() const { return keys_.begin(); } constexpr const_iterator cbegin() const { return keys_.begin(); } constexpr const_iterator end() const { return keys_.end(); } constexpr const_iterator cend() const { return keys_.end(); } constexpr const_reverse_iterator rbegin() const { return const_reverse_iterator{keys_.end()}; } constexpr const_reverse_iterator crbegin() const { return const_reverse_iterator{keys_.end()}; } constexpr const_reverse_iterator rend() const { return const_reverse_iterator{keys_.begin()}; } constexpr const_reverse_iterator crend() const { return const_reverse_iterator{keys_.begin()}; } /* comparison */ constexpr bool operator==(set const& rhs) const { return bits::equal(begin(), end(), rhs.begin()); } constexpr bool operator!=(set const& rhs) const { return !(*this == rhs); } constexpr bool operator<(set const& rhs) const { return bits::lexicographical_compare(begin(), end(), rhs.begin(), rhs.end()); } constexpr bool operator<=(set const& rhs) const { return (*this < rhs) || (*this == rhs); } constexpr bool operator>(set const& rhs) const { return bits::lexicographical_compare(rhs.begin(), rhs.end(), begin(), end()); } constexpr bool operator>=(set const& rhs) const { return (*this > rhs) || (*this == rhs); } }; template class set : private Compare { using container_type = bits::carray; // just for the type definitions public: /* container typedefs*/ using key_type = Key; using value_type = Key; using size_type = typename container_type::size_type; using difference_type = typename container_type::size_type; using key_compare = Compare; using value_compare = Compare; using reference = typename container_type::const_reference; using const_reference = reference; using pointer = typename container_type::const_pointer; using const_pointer = pointer; using iterator = pointer; using reverse_iterator = pointer; using const_iterator = const_pointer; using const_reverse_iterator = const_pointer; public: /* constructors */ constexpr set(const set &other) = default; constexpr set(bits::carray, Compare const &) {} explicit constexpr set(bits::carray) {} constexpr set(std::initializer_list, Compare const &comp) : Compare{comp} {} constexpr set(std::initializer_list keys) : set{keys, Compare{}} {} constexpr set& operator=(const set &other) = default; /* capacity */ constexpr bool empty() const { return true; } constexpr size_type size() const { return 0; } constexpr size_type max_size() const { return 0; } /* lookup */ template constexpr std::size_t count(KeyType const &) const { return 0; } template constexpr const_iterator find(KeyType const &) const { return end(); } template constexpr std::pair equal_range(KeyType const &) const { return {end(), end()}; } template constexpr const_iterator lower_bound(KeyType const &) const { return end(); } template constexpr const_iterator upper_bound(KeyType const &) const { return end(); } /* observers */ constexpr const key_compare& key_comp() const { return value_comp(); } constexpr const key_compare& value_comp() const { return static_cast(*this); } /* iterators */ constexpr const_iterator begin() const { return nullptr; } constexpr const_iterator cbegin() const { return nullptr; } constexpr const_iterator end() const { return nullptr; } constexpr const_iterator cend() const { return nullptr; } constexpr const_reverse_iterator rbegin() const { return nullptr; } constexpr const_reverse_iterator crbegin() const { return nullptr; } constexpr const_reverse_iterator rend() const { return nullptr; } constexpr const_reverse_iterator crend() const { return nullptr; } }; template constexpr auto make_set(bits::ignored_arg = {}/* for consistency with the initializer below for N = 0*/) { return set{}; } template constexpr auto make_set(const T (&args)[N]) { return set(args); } template constexpr auto make_set(std::array const &args) { return set(args); } template constexpr auto make_set(const T (&args)[N], Compare const& compare = Compare{}) { return set(args, compare); } template constexpr auto make_set(std::array const &args, Compare const& compare = Compare{}) { return set(args, compare); } #ifdef FROZEN_LETITGO_HAS_DEDUCTION_GUIDES template set(T, Args...) -> set; #endif // FROZEN_LETITGO_HAS_DEDUCTION_GUIDES } // namespace frozen #endif string.hg/* * Frozen * Copyright 2016 QuarksLab * * Licensed to the Apache Software Foundation (ASF) under one * or more contributor license agreements. See the NOTICE file * distributed with this work for additional information * regarding copyright ownership. The ASF licenses this file * to you under the Apache License, Version 2.0 (the * "License"); you may not use this file except in compliance * with the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, * software distributed under the License is distributed on an * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * KIND, either express or implied. See the License for the * specific language governing permissions and limitations * under the License. */ #ifndef FROZEN_LETITGO_STRING_H #define FROZEN_LETITGO_STRING_H #include "frozen/bits/elsa.h" #include "frozen/bits/hash_string.h" #include "frozen/bits/version.h" #include "frozen/bits/defines.h" #include #include #ifdef FROZEN_LETITGO_HAS_STRING_VIEW #include #endif namespace frozen { template class basic_string { using chr_t = _CharT; chr_t const *data_; std::size_t size_; public: template constexpr basic_string(chr_t const (&data)[N]) : data_(data), size_(N - 1) {} constexpr basic_string(chr_t const *data, std::size_t size) : data_(data), size_(size) {} #ifdef FROZEN_LETITGO_HAS_STRING_VIEW constexpr basic_string(std::basic_string_view data) : data_(data.data()), size_(data.size()) {} #endif constexpr basic_string(const basic_string &) noexcept = default; constexpr basic_string &operator=(const basic_string &) noexcept = default; constexpr std::size_t size() const { return size_; } constexpr chr_t operator[](std::size_t i) const { return data_[i]; } constexpr bool operator==(basic_string other) const { if (size_ != other.size_) return false; for (std::size_t i = 0; i < size_; ++i) if (data_[i] != other.data_[i]) return false; return true; } constexpr bool operator<(const basic_string &other) const { unsigned i = 0; while (i < size() && i < other.size()) { if ((*this)[i] < other[i]) { return true; } if ((*this)[i] > other[i]) { return false; } ++i; } return size() < other.size(); } friend constexpr bool operator>(const basic_string& lhs, const basic_string& rhs) { return rhs < lhs; } constexpr const chr_t *data() const { return data_; } constexpr const chr_t *begin() const { return data(); } constexpr const chr_t *end() const { return data() + size(); } }; template struct elsa> { constexpr std::size_t operator()(basic_string<_CharT> value) const { return hash_string(value); } constexpr std::size_t operator()(basic_string<_CharT> value, std::size_t seed) const { return hash_string(value, seed); } }; using string = basic_string; using wstring = basic_string; using u16string = basic_string; using u32string = basic_string; #ifdef FROZEN_LETITGO_HAS_CHAR8T using u8string = basic_string; #endif namespace string_literals { constexpr string operator"" _s(const char *data, std::size_t size) { return {data, size}; } constexpr wstring operator"" _s(const wchar_t *data, std::size_t size) { return {data, size}; } constexpr u16string operator"" _s(const char16_t *data, std::size_t size) { return {data, size}; } constexpr u32string operator"" _s(const char32_t *data, std::size_t size) { return {data, size}; } #ifdef FROZEN_LETITGO_HAS_CHAR8T constexpr u8string operator"" _s(const char8_t *data, std::size_t size) { return {data, size}; } #endif } // namespace string_literals } // namespace frozen namespace std { template struct hash> { std::size_t operator()(frozen::basic_string<_CharT> s) const { return frozen::elsa>{}(s); } }; } // namespace std #endif unordered_map.h¢/* * Frozen * Copyright 2016 QuarksLab * * Licensed to the Apache Software Foundation (ASF) under one * or more contributor license agreements. See the NOTICE file * distributed with this work for additional information * regarding copyright ownership. The ASF licenses this file * to you under the Apache License, Version 2.0 (the * "License"); you may not use this file except in compliance * with the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, * software distributed under the License is distributed on an * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * KIND, either express or implied. See the License for the * specific language governing permissions and limitations * under the License. */ #ifndef FROZEN_LETITGO_UNORDERED_MAP_H #define FROZEN_LETITGO_UNORDERED_MAP_H #include "frozen/bits/basic_types.h" #include "frozen/bits/constexpr_assert.h" #include "frozen/bits/elsa.h" #include "frozen/bits/exceptions.h" #include "frozen/bits/pmh.h" #include "frozen/bits/version.h" #include "frozen/random.h" #include #include #include namespace frozen { namespace bits { struct GetKey { template constexpr auto const &operator()(KV const &kv) const { return kv.first; } }; } // namespace bits template , class KeyEqual = std::equal_to> class unordered_map : private KeyEqual { static constexpr std::size_t storage_size = bits::next_highest_power_of_two(N) * (N < 32 ? 2 : 1); // size adjustment to prevent high collision rate for small sets using container_type = bits::carray, N>; using tables_type = bits::pmh_tables; container_type items_; tables_type tables_; public: /* typedefs */ using Self = unordered_map; using key_type = Key; using mapped_type = Value; using value_type = typename container_type::value_type; using size_type = typename container_type::size_type; using difference_type = typename container_type::difference_type; using hasher = Hash; using key_equal = KeyEqual; using reference = typename container_type::reference; using const_reference = typename container_type::const_reference; using pointer = typename container_type::pointer; using const_pointer = typename container_type::const_pointer; using iterator = typename container_type::iterator; using const_iterator = typename container_type::const_iterator; public: /* constructors */ unordered_map(unordered_map const &) = default; constexpr unordered_map(container_type items, Hash const &hash, KeyEqual const &equal) : KeyEqual{equal} , items_{items} , tables_{ bits::make_pmh_tables( items_, hash, bits::GetKey{}, default_prg_t{})} {} explicit constexpr unordered_map(container_type items) : unordered_map{items, Hash{}, KeyEqual{}} {} constexpr unordered_map(std::initializer_list items, Hash const & hash, KeyEqual const & equal) : unordered_map{container_type{items}, hash, equal} { constexpr_assert(items.size() == N, "Inconsistent initializer_list size and type size argument"); } constexpr unordered_map(std::initializer_list items) : unordered_map{items, Hash{}, KeyEqual{}} {} /* iterators */ constexpr iterator begin() { return items_.begin(); } constexpr iterator end() { return items_.end(); } constexpr const_iterator begin() const { return items_.begin(); } constexpr const_iterator end() const { return items_.end(); } constexpr const_iterator cbegin() const { return items_.begin(); } constexpr const_iterator cend() const { return items_.end(); } /* capacity */ constexpr bool empty() const { return !N; } constexpr size_type size() const { return N; } constexpr size_type max_size() const { return N; } /* lookup */ template constexpr std::size_t count(KeyType const &key) const { return find(key) != end(); } template constexpr Value const &at(KeyType const &key) const { return at_impl(*this, key); } template constexpr Value &at(KeyType const &key) { return at_impl(*this, key); } template constexpr const_iterator find(KeyType const &key) const { return find_impl(*this, key, hash_function(), key_eq()); } template constexpr iterator find(KeyType const &key) { return find_impl(*this, key, hash_function(), key_eq()); } template constexpr bool contains(KeyType const &key) const { return this->find(key) != this->end(); } template constexpr std::pair equal_range(KeyType const &key) const { return equal_range_impl(*this, key); } template constexpr std::pair equal_range(KeyType const &key) { return equal_range_impl(*this, key); } /* bucket interface */ constexpr std::size_t bucket_count() const { return storage_size; } constexpr std::size_t max_bucket_count() const { return storage_size; } /* observers*/ constexpr const hasher& hash_function() const { return tables_.hash_function(); } constexpr const key_equal& key_eq() const { return static_cast(*this); } private: template static inline constexpr auto& at_impl(This&& self, KeyType const &key) { auto it = self.find(key); if (it != self.end()) return it->second; else FROZEN_THROW_OR_ABORT(std::out_of_range("unknown key")); } template static inline constexpr auto find_impl(This&& self, KeyType const &key, Hasher const &hash, Equal const &equal) { auto const pos = self.tables_.lookup(key, hash); auto it = self.items_.begin() + pos; if (it != self.items_.end() && equal(it->first, key)) return it; else return self.items_.end(); } template static inline constexpr auto equal_range_impl(This&& self, KeyType const &key) { auto const it = self.find(key); if (it != self.end()) return std::make_pair(it, it + 1); else return std::make_pair(self.end(), self.end()); } }; template constexpr auto make_unordered_map(std::pair const (&items)[N]) { return unordered_map{items}; } template constexpr auto make_unordered_map( std::pair const (&items)[N], Hasher const &hash = elsa{}, Equal const &equal = std::equal_to{}) { return unordered_map{items, hash, equal}; } template constexpr auto make_unordered_map(std::array, N> const &items) { return unordered_map{items}; } template constexpr auto make_unordered_map( std::array, N> const &items, Hasher const &hash = elsa{}, Equal const &equal = std::equal_to{}) { return unordered_map{items, hash, equal}; } } // namespace frozen #endif unordered_set.hå/* * Frozen * Copyright 2016 QuarksLab * * Licensed to the Apache Software Foundation (ASF) under one * or more contributor license agreements. See the NOTICE file * distributed with this work for additional information * regarding copyright ownership. The ASF licenses this file * to you under the Apache License, Version 2.0 (the * "License"); you may not use this file except in compliance * with the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, * software distributed under the License is distributed on an * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * KIND, either express or implied. See the License for the * specific language governing permissions and limitations * under the License. */ #ifndef FROZEN_LETITGO_UNORDERED_SET_H #define FROZEN_LETITGO_UNORDERED_SET_H #include "frozen/bits/basic_types.h" #include "frozen/bits/constexpr_assert.h" #include "frozen/bits/elsa.h" #include "frozen/bits/pmh.h" #include "frozen/bits/version.h" #include "frozen/random.h" #include namespace frozen { namespace bits { struct Get { template constexpr T const &operator()(T const &key) const { return key; } }; } // namespace bits template , class KeyEqual = std::equal_to> class unordered_set : private KeyEqual { static constexpr std::size_t storage_size = bits::next_highest_power_of_two(N) * (N < 32 ? 2 : 1); // size adjustment to prevent high collision rate for small sets using container_type = bits::carray; using tables_type = bits::pmh_tables; container_type keys_; tables_type tables_; public: /* typedefs */ using key_type = Key; using value_type = Key; using size_type = typename container_type::size_type; using difference_type = typename container_type::difference_type; using hasher = Hash; using key_equal = KeyEqual; using const_reference = typename container_type::const_reference; using reference = const_reference; using const_pointer = typename container_type::const_pointer; using pointer = const_pointer; using const_iterator = typename container_type::const_iterator; using iterator = const_iterator; public: /* constructors */ unordered_set(unordered_set const &) = default; constexpr unordered_set(container_type keys, Hash const &hash, KeyEqual const &equal) : KeyEqual{equal} , keys_{keys} , tables_{bits::make_pmh_tables( keys_, hash, bits::Get{}, default_prg_t{})} {} explicit constexpr unordered_set(container_type keys) : unordered_set{keys, Hash{}, KeyEqual{}} {} constexpr unordered_set(std::initializer_list keys) : unordered_set{keys, Hash{}, KeyEqual{}} {} constexpr unordered_set(std::initializer_list keys, Hash const & hash, KeyEqual const & equal) : unordered_set{container_type{keys}, hash, equal} { constexpr_assert(keys.size() == N, "Inconsistent initializer_list size and type size argument"); } /* iterators */ constexpr const_iterator begin() const { return keys_.begin(); } constexpr const_iterator end() const { return keys_.end(); } constexpr const_iterator cbegin() const { return keys_.begin(); } constexpr const_iterator cend() const { return keys_.end(); } /* capacity */ constexpr bool empty() const { return !N; } constexpr size_type size() const { return N; } constexpr size_type max_size() const { return N; } /* lookup */ template constexpr std::size_t count(KeyType const &key) const { return find(key, hash_function(), key_eq()) != end(); } template constexpr const_iterator find(KeyType const &key, Hasher const &hash, Equal const &equal) const { auto const pos = tables_.lookup(key, hash); auto it = keys_.begin() + pos; if (it != keys_.end() && equal(*it, key)) return it; else return keys_.end(); } template constexpr const_iterator find(KeyType const &key) const { auto const pos = tables_.lookup(key, hash_function()); auto it = keys_.begin() + pos; if (it != keys_.end() && key_eq()(*it, key)) return it; else return keys_.end(); } template constexpr bool contains(KeyType const &key) const { return this->find(key) != keys_.end(); } template constexpr std::pair equal_range(KeyType const &key) const { auto const it = find(key); if (it != end()) return {it, it + 1}; else return {keys_.end(), keys_.end()}; } /* bucket interface */ constexpr std::size_t bucket_count() const { return storage_size; } constexpr std::size_t max_bucket_count() const { return storage_size; } /* observers*/ constexpr const hasher& hash_function() const { return tables_.hash_function(); } constexpr const key_equal& key_eq() const { return static_cast(*this); } }; template constexpr auto make_unordered_set(T const (&keys)[N]) { return unordered_set{keys}; } template constexpr auto make_unordered_set(T const (&keys)[N], Hasher const& hash, Equal const& equal) { return unordered_set{keys, hash, equal}; } template constexpr auto make_unordered_set(std::array const &keys) { return unordered_set{keys}; } template constexpr auto make_unordered_set(std::array const &keys, Hasher const& hash, Equal const& equal) { return unordered_set{keys, hash, equal}; } #ifdef FROZEN_LETITGO_HAS_DEDUCTION_GUIDES template unordered_set(T, Args...) -> unordered_set; #endif } // namespace frozen #endif sharecmakefrozenfrozenConfig.cmake,# Generated by CMake if("${CMAKE_MAJOR_VERSION}.${CMAKE_MINOR_VERSION}" LESS 2.8) message(FATAL_ERROR "CMake >= 3.1.0 required") endif() if(CMAKE_VERSION VERSION_LESS "3.1.0") message(FATAL_ERROR "CMake >= 3.1.0 required") endif() cmake_policy(PUSH) cmake_policy(VERSION 3.1.0...4.2) #---------------------------------------------------------------- # Generated CMake target import file. #---------------------------------------------------------------- # Commands may need to know the format version. set(CMAKE_IMPORT_FILE_VERSION 1) # Protect against multiple inclusion, which would fail when already imported targets are added once more. set(_cmake_targets_defined "") set(_cmake_targets_not_defined "") set(_cmake_expected_targets "") foreach(_cmake_expected_target IN ITEMS frozen::frozen frozen::frozen-headers) list(APPEND _cmake_expected_targets "${_cmake_expected_target}") if(TARGET "${_cmake_expected_target}") list(APPEND _cmake_targets_defined "${_cmake_expected_target}") else() list(APPEND _cmake_targets_not_defined "${_cmake_expected_target}") endif() endforeach() unset(_cmake_expected_target) if(_cmake_targets_defined STREQUAL _cmake_expected_targets) unset(_cmake_targets_defined) unset(_cmake_targets_not_defined) unset(_cmake_expected_targets) unset(CMAKE_IMPORT_FILE_VERSION) cmake_policy(POP) return() endif() if(NOT _cmake_targets_defined STREQUAL "") string(REPLACE ";" ", " _cmake_targets_defined_text "${_cmake_targets_defined}") string(REPLACE ";" ", " _cmake_targets_not_defined_text "${_cmake_targets_not_defined}") message(FATAL_ERROR "Some (but not all) targets in this export set were already defined.\nTargets Defined: ${_cmake_targets_defined_text}\nTargets not yet defined: ${_cmake_targets_not_defined_text}\n") endif() unset(_cmake_targets_defined) unset(_cmake_targets_not_defined) unset(_cmake_expected_targets) # Compute the installation prefix relative to this file. get_filename_component(_IMPORT_PREFIX "${CMAKE_CURRENT_LIST_FILE}" PATH) get_filename_component(_IMPORT_PREFIX "${_IMPORT_PREFIX}" PATH) get_filename_component(_IMPORT_PREFIX "${_IMPORT_PREFIX}" PATH) get_filename_component(_IMPORT_PREFIX "${_IMPORT_PREFIX}" PATH) if(_IMPORT_PREFIX STREQUAL "/") set(_IMPORT_PREFIX "") endif() # Create imported target frozen::frozen add_library(frozen::frozen INTERFACE IMPORTED) set_target_properties(frozen::frozen PROPERTIES INTERFACE_COMPILE_FEATURES "cxx_std_14" INTERFACE_INCLUDE_DIRECTORIES "${_IMPORT_PREFIX}/include" ) # Create imported target frozen::frozen-headers add_library(frozen::frozen-headers INTERFACE IMPORTED) set_target_properties(frozen::frozen-headers PROPERTIES INTERFACE_LINK_LIBRARIES "frozen::frozen" INTERFACE_SOURCES "${_IMPORT_PREFIX}/include/frozen/algorithm.h;${_IMPORT_PREFIX}/include/frozen/map.h;${_IMPORT_PREFIX}/include/frozen/random.h;${_IMPORT_PREFIX}/include/frozen/set.h;${_IMPORT_PREFIX}/include/frozen/string.h;${_IMPORT_PREFIX}/include/frozen/unordered_map.h;${_IMPORT_PREFIX}/include/frozen/unordered_set.h;${_IMPORT_PREFIX}/include/frozen/bits/algorithms.h;${_IMPORT_PREFIX}/include/frozen/bits/basic_types.h;${_IMPORT_PREFIX}/include/frozen/bits/elsa.h;${_IMPORT_PREFIX}/include/frozen/bits/pmh.h" ) # Load information for each installed configuration. file(GLOB _cmake_config_files "${CMAKE_CURRENT_LIST_DIR}/frozenConfig-*.cmake") foreach(_cmake_config_file IN LISTS _cmake_config_files) include("${_cmake_config_file}") endforeach() unset(_cmake_config_file) unset(_cmake_config_files) # Cleanup temporary variables. set(_IMPORT_PREFIX) # Loop over all imported files and verify that they actually exist foreach(_cmake_target IN LISTS _cmake_import_check_targets) if(CMAKE_VERSION VERSION_LESS "3.28" OR NOT DEFINED _cmake_import_check_xcframework_for_${_cmake_target} OR NOT IS_DIRECTORY "${_cmake_import_check_xcframework_for_${_cmake_target}}") foreach(_cmake_file IN LISTS "_cmake_import_check_files_for_${_cmake_target}") if(NOT EXISTS "${_cmake_file}") message(FATAL_ERROR "The imported target \"${_cmake_target}\" references the file \"${_cmake_file}\" but this file does not exist. Possible reasons include: * The file was deleted, renamed, or moved to another location. * An install or uninstall procedure did not complete successfully. * The installation package was faulty and contained \"${CMAKE_CURRENT_LIST_FILE}\" but not all the files it references. ") endif() endforeach() endif() unset(_cmake_file) unset("_cmake_import_check_files_for_${_cmake_target}") endforeach() unset(_cmake_target) unset(_cmake_import_check_targets) # This file does not depend on other imported targets which have # been exported from the same project but in a separate export set. # Commands beyond this point should not need to know the version. set(CMAKE_IMPORT_FILE_VERSION) cmake_policy(POP) frozenConfigVersion.cmakeÿ# This is a basic version file for the Config-mode of find_package(). # It is used by write_basic_package_version_file() as input file for configure_file() # to create a version-file which can be installed along a config.cmake file. # # The created file sets PACKAGE_VERSION_EXACT if the current version string and # the requested version string are exactly the same and it sets # PACKAGE_VERSION_COMPATIBLE if the current version is >= requested version, # but only if the requested major version is the same as the current one. # The variable CVF_VERSION must be set before calling configure_file(). set(PACKAGE_VERSION "1.1.0") if(PACKAGE_VERSION VERSION_LESS PACKAGE_FIND_VERSION) set(PACKAGE_VERSION_COMPATIBLE FALSE) else() if("1.1.0" MATCHES "^([0-9]+)\\.") set(CVF_VERSION_MAJOR "${CMAKE_MATCH_1}") if(NOT CVF_VERSION_MAJOR VERSION_EQUAL 0) string(REGEX REPLACE "^0+" "" CVF_VERSION_MAJOR "${CVF_VERSION_MAJOR}") endif() else() set(CVF_VERSION_MAJOR "1.1.0") endif() if(PACKAGE_FIND_VERSION_RANGE) # both endpoints of the range must have the expected major version math (EXPR CVF_VERSION_MAJOR_NEXT "${CVF_VERSION_MAJOR} + 1") if (NOT PACKAGE_FIND_VERSION_MIN_MAJOR STREQUAL CVF_VERSION_MAJOR OR ((PACKAGE_FIND_VERSION_RANGE_MAX STREQUAL "INCLUDE" AND NOT PACKAGE_FIND_VERSION_MAX_MAJOR STREQUAL CVF_VERSION_MAJOR) OR (PACKAGE_FIND_VERSION_RANGE_MAX STREQUAL "EXCLUDE" AND NOT PACKAGE_FIND_VERSION_MAX VERSION_LESS_EQUAL CVF_VERSION_MAJOR_NEXT))) set(PACKAGE_VERSION_COMPATIBLE FALSE) elseif(PACKAGE_FIND_VERSION_MIN_MAJOR STREQUAL CVF_VERSION_MAJOR AND ((PACKAGE_FIND_VERSION_RANGE_MAX STREQUAL "INCLUDE" AND PACKAGE_VERSION VERSION_LESS_EQUAL PACKAGE_FIND_VERSION_MAX) OR (PACKAGE_FIND_VERSION_RANGE_MAX STREQUAL "EXCLUDE" AND PACKAGE_VERSION VERSION_LESS PACKAGE_FIND_VERSION_MAX))) set(PACKAGE_VERSION_COMPATIBLE TRUE) else() set(PACKAGE_VERSION_COMPATIBLE FALSE) endif() else() if(PACKAGE_FIND_VERSION_MAJOR STREQUAL CVF_VERSION_MAJOR) set(PACKAGE_VERSION_COMPATIBLE TRUE) else() set(PACKAGE_VERSION_COMPATIBLE FALSE) endif() if(PACKAGE_FIND_VERSION STREQUAL PACKAGE_VERSION) set(PACKAGE_VERSION_EXACT TRUE) endif() endif() endif()