1 files changed, 229 insertions, 0 deletions
diff --git a/include/frozen/bits/algorithms.h b/include/frozen/bits/algorithms.h
new file mode 100644
index 0000000..8d1ffbc
--- /dev/null
+++ b/include/frozen/bits/algorithms.h
@@ -0,0 +1,229 @@
+/*
+ * 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 <limits>
+#include <tuple>
+
+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<decltype(v)>::digits;
+  v--;
+  for(std::size_t i = 1; i < trip_count; i <<= 1)
+    v |= v >> i;
+  v++;
+  return v;
+}
+
+template<class T>
+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<std::size_t, 4>);
+unsigned long select_uint_least(std::integral_constant<std::size_t, 3>);
+unsigned long long select_uint_least(std::integral_constant<std::size_t, 2>);
+template<std::size_t N>
+unsigned long long select_uint_least(std::integral_constant<std::size_t, N>) {
+  static_assert(N < 2, "unsupported type size");
+  return {};
+}
+
+
+template<std::size_t N>
+using select_uint_least_t = decltype(select_uint_least(std::integral_constant<std::size_t, bit_weight(N)>()));
+
+template <typename Iter, typename Compare>
+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 <class T>
+constexpr void cswap(T &a, T &b) {
+  auto tmp = a;
+  a = b;
+  b = tmp;
+}
+
+template <class T, class U>
+constexpr void cswap(std::pair<T, U> & a, std::pair<T, U> & b) {
+  cswap(a.first, b.first);
+  cswap(a.second, b.second);
+}
+
+template <class... Tys, std::size_t... Is>
+constexpr void cswap(std::tuple<Tys...> &a, std::tuple<Tys...> &b, std::index_sequence<Is...>) {
+  using swallow = int[];
+  (void) swallow{(cswap(std::get<Is>(a), std::get<Is>(b)), 0)...};
+}
+
+template <class... Tys>
+constexpr void cswap(std::tuple<Tys...> &a, std::tuple<Tys...> &b) {
+  cswap(a, b, std::make_index_sequence<sizeof...(Tys)>());
+}
+
+template <typename Iterator, class Compare>
+constexpr Iterator partition(Iterator left, Iterator right, Compare const &compare) {
+  auto pivot = left + (right - left) / 2;
+  auto value = *pivot;
+  cswap(*right, *pivot);
+  for (auto it = left; 0 < right - it; ++it) {
+    if (compare(*it, value)) {
+      cswap(*it, *left);
+      left++;
+    }
+  }
+  cswap(*right, *left);
+  return left;
+}
+
+template <typename Iterator, class Compare>
+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 <typename T, std::size_t N, class Compare>
+constexpr bits::carray<T, N> quicksort(bits::carray<T, N> const &array,
+                                     Compare const &compare) {
+  bits::carray<T, N> res = array;
+  quicksort(res.begin(), res.end() - 1, compare);
+  return res;
+}
+
+template <class T, class Compare> struct LowerBound {
+  T const &value_;
+  Compare const &compare_;
+  constexpr LowerBound(T const &value, Compare const &compare)
+      : value_(value), compare_(compare) {}
+
+  template <class ForwardIt>
+  inline constexpr ForwardIt doit_fast(ForwardIt first,
+                                  std::integral_constant<std::size_t, 0>) {
+    return first;
+  }
+
+  template <class ForwardIt, std::size_t N>
+  inline constexpr ForwardIt doit_fast(ForwardIt first,
+                                  std::integral_constant<std::size_t, N>) {
+    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<std::size_t, N / 2>{});
+  }
+
+  template <class ForwardIt, std::size_t N>
+  inline constexpr ForwardIt doitfirst(ForwardIt first, std::integral_constant<std::size_t, N>, std::integral_constant<bool, true>) {
+    return doit_fast(first, std::integral_constant<std::size_t, N>{});
+  }
+
+  template <class ForwardIt, std::size_t N>
+  inline constexpr ForwardIt doitfirst(ForwardIt first, std::integral_constant<std::size_t, N>, std::integral_constant<bool, false>) {
+    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::size_t, next>{}, std::integral_constant<bool, next_highest_power_of_two(next) - 1 == next>{});
+    }
+    else
+      return doit_fast(first, std::integral_constant<std::size_t, next_start>{});
+  }
+
+  template <class ForwardIt>
+  inline constexpr ForwardIt doitfirst(ForwardIt first, std::integral_constant<std::size_t, 1>, std::integral_constant<bool, false>) {
+    return doit_fast(first, std::integral_constant<std::size_t, 1>{});
+  }
+};
+
+template <std::size_t N, class ForwardIt, class T, class Compare>
+constexpr ForwardIt lower_bound(ForwardIt first, const T &value, Compare const &compare) {
+  return LowerBound<T, Compare>{value, compare}.doitfirst(first, std::integral_constant<std::size_t, N>{}, std::integral_constant<bool, next_highest_power_of_two(N) - 1 == N>{});
+}
+
+template <std::size_t N, class Compare, class ForwardIt, class T>
+constexpr bool binary_search(ForwardIt first, const T &value,
+                             Compare const &compare) {
+  ForwardIt where = lower_bound<N>(first, value, compare);
+  return (!(where == first + N) && !(compare(value, *where)));
+}
+
+
+template<class InputIt1, class InputIt2>
+constexpr bool equal(InputIt1 first1, InputIt1 last1, InputIt2 first2)
+{
+  for (; first1 != last1; ++first1, ++first2) {
+    if (!(*first1 == *first2)) {
+      return false;
+    }
+  }
+  return true;
+}
+
+template<class InputIt1, class InputIt2>
+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