Debian Codegraph @

src/perfect-hashing/frozen/bits/algorithms.h

raw
1 /*
2 * Frozen
3 * Copyright 2016 QuarksLab
4 *
5 * Licensed to the Apache Software Foundation (ASF) under one
6 * or more contributor license agreements. See the NOTICE file
7 * distributed with this work for additional information
8 * regarding copyright ownership. The ASF licenses this file
9 * to you under the Apache License, Version 2.0 (the
10 * "License"); you may not use this file except in compliance
11 * with the License. You may obtain a copy of the License at
12 *
13 * http://www.apache.org/licenses/LICENSE-2.0
14 *
15 * Unless required by applicable law or agreed to in writing,
16 * software distributed under the License is distributed on an
17 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
18 * KIND, either express or implied. See the License for the
19 * specific language governing permissions and limitations
20 * under the License.
21 */
22
23 #ifndef FROZEN_LETITGO_BITS_ALGORITHMS_H
24 #define FROZEN_LETITGO_BITS_ALGORITHMS_H
25
26 #include "frozen/bits/basic_types.h"
27
28 #include <limits>
29 #include <tuple>
30
31 namespace frozen {
32
33 namespace bits {
34
35 auto constexpr next_highest_power_of_two(std::size_t v) {
36 // https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
37 constexpr auto trip_count = std::numeric_limits<decltype(v)>::digits;
38 v--;
39 for (std::size_t i = 1; i < trip_count; i <<= 1) v |= v >> i;
40 v++;
41 return v;
42 }
43
44 template <class T> auto constexpr log(T v) {
45 std::size_t n = 0;
46 while (v > 1) {
47 n += 1;
48 v >>= 1;
49 }
50 return n;
51 }
52
53 constexpr std::size_t
54 bit_weight(std::size_t n) {
55 return (n <= 8 * sizeof(unsigned int)) + (n <= 8 * sizeof(unsigned long)) + (n <= 8 * sizeof(unsigned long long)) + (n <= 128);
56 }
57
58 unsigned int select_uint_least(std::integral_constant<std::size_t, 4>);
59 unsigned long select_uint_least(std::integral_constant<std::size_t, 3>);
60 unsigned long long select_uint_least(std::integral_constant<std::size_t, 2>);
61 template <std::size_t N>
62 unsigned long long
63 select_uint_least(std::integral_constant<std::size_t, N>) {
64 static_assert(N < 2, "unsupported type size");
65 return {};
66 }
67
68
69 template <std::size_t N> using select_uint_least_t = decltype(select_uint_least(std::integral_constant<std::size_t, bit_weight(N)>()));
70
71 template <typename Iter, typename Compare>
72 constexpr auto
73 min_element(Iter begin, const Iter end, Compare const &compare) {
74 auto result = begin;
75 while (begin != end) {
76 if (compare(*begin, *result)) { result = begin; }
77 ++begin;
78 }
79 return result;
80 }
81
82 template <class T>
83 constexpr void
84 cswap(T &a, T &b) {
85 auto tmp = a;
86 a = b;
87 b = tmp;
88 }
89
90 template <class T, class U>
91 constexpr void
92 cswap(std::pair<T, U> &a, std::pair<T, U> &b) {
93 cswap(a.first, b.first);
94 cswap(a.second, b.second);
95 }
96
97 template <class... Tys, std::size_t... Is>
98 constexpr void
99 cswap(std::tuple<Tys...> &a, std::tuple<Tys...> &b, std::index_sequence<Is...>) {
100 using swallow = int[];
101 (void)swallow{(cswap(std::get<Is>(a), std::get<Is>(b)), 0)...};
102 }
103
104 template <class... Tys>
105 constexpr void
106 cswap(std::tuple<Tys...> &a, std::tuple<Tys...> &b) {
107 cswap(a, b, std::make_index_sequence<sizeof...(Tys)>());
108 }
109
110 template <typename Iterator, class Compare>
111 constexpr Iterator
112 partition(Iterator left, Iterator right, Compare const &compare) {
113 auto pivot = left + (right - left) / 2;
114 auto value = *pivot;
115 cswap(*right, *pivot);
116 for (auto it = left; 0 < right - it; ++it) {
117 if (compare(*it, value)) {
118 cswap(*it, *left);
119 left++;
120 }
121 }
122 cswap(*right, *left);
123 return left;
124 }
125
126 template <typename Iterator, class Compare>
127 constexpr void
128 quicksort(Iterator left, Iterator right, Compare const &compare) {
129 while (0 < right - left) {
130 auto new_pivot = bits::partition(left, right, compare);
131 quicksort(left, new_pivot, compare);
132 left = new_pivot + 1;
133 }
134 }
135
136 template <typename T, std::size_t N, class Compare>
137 constexpr bits::carray<T, N>
138 quicksort(bits::carray<T, N> const &array, Compare const &compare) {
139 bits::carray<T, N> res = array;
140 quicksort(res.begin(), res.end() - 1, compare);
141 return res;
142 }
143
144 template <class T, class Compare> struct LowerBound {
145 T const &value_;
146 Compare const &compare_;
147 constexpr LowerBound(T const &value, Compare const &compare) : value_(value), compare_(compare) {}
148
149 template <class ForwardIt>
150 inline constexpr ForwardIt
151 doit_fast(ForwardIt first, std::integral_constant<std::size_t, 0>) {
152 return first;
153 }
154
155 template <class ForwardIt, std::size_t N>
156 inline constexpr ForwardIt
157 doit_fast(ForwardIt first, std::integral_constant<std::size_t, N>) {
158 auto constexpr step = N / 2;
159 static_assert(N / 2 == N - N / 2 - 1, "power of two minus 1");
160 auto it = first + step;
161 auto next_it = compare_(*it, value_) ? it + 1 : first;
162 return doit_fast(next_it, std::integral_constant<std::size_t, N / 2>{});
163 }
164
165 template <class ForwardIt, std::size_t N>
166 inline constexpr ForwardIt
167 doitfirst(ForwardIt first, std::integral_constant<std::size_t, N>, std::integral_constant<bool, true>) {
168 return doit_fast(first, std::integral_constant<std::size_t, N>{});
169 }
170
171 template <class ForwardIt, std::size_t N>
172 inline constexpr ForwardIt
173 doitfirst(ForwardIt first, std::integral_constant<std::size_t, N>, std::integral_constant<bool, false>) {
174 auto constexpr next_power = next_highest_power_of_two(N);
175 auto constexpr next_start = next_power / 2 - 1;
176 auto it = first + next_start;
177 if (compare_(*it, value_)) {
178 auto constexpr next = N - next_start - 1;
179 return doitfirst(it + 1, std::integral_constant<std::size_t, next>{}, std::integral_constant<bool, next_highest_power_of_two(next) - 1 == next>{});
180 } else return doit_fast(first, std::integral_constant<std::size_t, next_start>{});
181 }
182
183 template <class ForwardIt>
184 inline constexpr ForwardIt
185 doitfirst(ForwardIt first, std::integral_constant<std::size_t, 1>, std::integral_constant<bool, false>) {
186 return doit_fast(first, std::integral_constant<std::size_t, 1>{});
187 }
188 };
189
190 template <std::size_t N, class ForwardIt, class T, class Compare>
191 constexpr ForwardIt
192 lower_bound(ForwardIt first, const T &value, Compare const &compare) {
193 return LowerBound<T, Compare>{value, compare}.doitfirst(
194 first, std::integral_constant<std::size_t, N>{}, std::integral_constant<bool, next_highest_power_of_two(N) - 1 == N>{});
195 }
196
197 template <std::size_t N, class Compare, class ForwardIt, class T>
198 constexpr bool
199 binary_search(ForwardIt first, const T &value, Compare const &compare) {
200 ForwardIt where = lower_bound<N>(first, value, compare);
201 return (!(where == first + N) && !(compare(value, *where)));
202 }
203
204
205 template <class InputIt1, class InputIt2>
206 constexpr bool
207 equal(InputIt1 first1, InputIt1 last1, InputIt2 first2) {
208 for (; first1 != last1; ++first1, ++first2) {
209 if (!(*first1 == *first2)) { return false; }
210 }
211 return true;
212 }
213
214 template <class InputIt1, class InputIt2>
215 constexpr bool
216 lexicographical_compare(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2) {
217 for (; (first1 != last1) && (first2 != last2); ++first1, ++first2) {
218 if (*first1 < *first2) return true;
219 if (*first2 < *first1) return false;
220 }
221 return (first1 == last1) && (first2 != last2);
222 }
223
224 } // namespace bits
225 } // namespace frozen
226
227 #endif