detray/utils/find_bound.hpp

0001 // This file is part of the ACTS project.
0002 //
0003 // Copyright (C) 2016 CERN for the benefit of the ACTS project
0004 //
0005 // This Source Code Form is subject to the terms of the Mozilla Public
0006 // License, v. 2.0. If a copy of the MPL was not distributed with this
0007 // file, You can obtain one at https://mozilla.org/MPL/2.0/.
0008
0009 #pragma once
0010
0011 // Project include(s).
0012 #include "detray/definitions/detail/qualifiers.hpp"
0013 #include "detray/utils/ranges.hpp"
0014
0015 // System include(s).
0016 #include <iterator>
0017
0018 namespace detray::detail {
0019
0020 /// Implementation of @c upper_bound
0021 /// @see
0022 /// https://github.com/gcc-mirror/gcc/blob/8f87b3c5ecd47f6ac0d7407ae5d436a12fb169dd/libstdc%2B%2B-v3/include/bits/stl_algo.h
0023 template <std::forward_iterator iterator_t, typename T>
0024 DETRAY_HOST_DEVICE constexpr iterator_t upper_bound(iterator_t first,
0025                                                     iterator_t last,
0026                                                     const T& value) {
0027   using difference_t = std::iter_difference_t<iterator_t>;
0028
0029   difference_t len{detray::ranges::distance(first, last)};
0030
0031   // binary search
0032   while (len > 0) {
0033     difference_t half{len >> 1};
0034     iterator_t middle{first};
0035     detray::ranges::advance(middle, half);
0036     if (value < *middle) {
0037       len = half;
0038     } else {
0039       first = middle;
0040       ++first;
0041       len -= half + 1;
0042     }
0043   }
0044   return first;
0045 }
0046
0047 /// Implementation of @c lower_bound
0048 /// @see
0049 /// https://github.com/gcc-mirror/gcc/blob/8f87b3c5ecd47f6ac0d7407ae5d436a12fb169dd/libstdc%2B%2B-v3/include/bits/stl_algobase.h
0050 template <std::forward_iterator iterator_t, typename T>
0051 DETRAY_HOST_DEVICE constexpr iterator_t lower_bound(iterator_t first,
0052                                                     iterator_t last,
0053                                                     const T& value) {
0054   using difference_t = std::iter_difference_t<iterator_t>;
0055
0056   difference_t len{detray::ranges::distance(first, last)};
0057
0058   // binary search
0059   while (len > 0) {
0060     difference_t half{len >> 1};
0061     iterator_t middle{first};
0062     detray::ranges::advance(middle, half);
0063     if (*middle < value) {
0064       first = middle;
0065       ++first;
0066       len -= half + 1;
0067     } else {
0068       len = half;
0069     }
0070   }
0071   return first;
0072 }
0073
0074 }  // namespace detray::detail