| 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 |