Lumiera  0.pre.03
»edit your freedom«
binary-search.hpp
Go to the documentation of this file.
1 /*
2  BINARY-SEARCH.hpp - generic search over continuous domain with a probe predicate
3 
4  Copyright (C)
5  2024, Hermann Vosseler <Ichthyostega@web.de>
6 
7   **Lumiera** is free software; you can redistribute it and/or modify it
8   under the terms of the GNU General Public License as published by the
9   Free Software Foundation; either version 2 of the License, or (at your
10   option) any later version. See the file COPYING for further details.
11 
12 */
13 
33 #ifndef LIB_BINARY_SEARCH_H
34 #define LIB_BINARY_SEARCH_H
35 
36 
37 #include "lib/meta/function.hpp"
38 
39 #include <utility>
40 
41 
42 namespace lib {
43 
44  using std::forward;
45 
54  template<class FUN, typename PAR>
55  inline auto
56  binarySearch_inner (FUN&& fun, PAR lower, PAR upper, PAR epsilon)
57  {
58  ASSERT_VALID_SIGNATURE (FUN, bool(PAR) );
59  REQUIRE (lower <= upper);
60  while ((upper-lower) >= epsilon)
61  {
62  PAR div = (lower+upper) / 2;
63  bool hit = fun(div);
64  if (hit)
65  upper = div;
66  else
67  lower = div;
68  }
69  return (lower+upper)/2;
70  }
71 
72 
79  template<class FUN, typename PAR>
80  inline auto
81  binarySearch_upper (FUN&& fun, PAR lower, PAR upper, PAR epsilon)
82  {
83  REQUIRE (lower <= upper);
84  while (true)
85  {
86  bool hit = fun(upper);
87  if (hit) break;
88  // the upper end breaks contract => search above
89  PAR len = (upper-lower);
90  lower = upper - len/10;
91  upper = lower + 14*len/10;
92  }
93  return binarySearch_inner (forward<FUN> (fun), lower,upper,epsilon);
94  }
95 
96 
97  template<class FUN, typename PAR>
98  inline auto
99  binarySearch (FUN&& fun, PAR lower, PAR upper, PAR epsilon)
100  {
101  REQUIRE (lower <= upper);
102  while (true)
103  {
104  bool hit = fun(lower);
105  if (not hit) break;
106  // the lower end breaks contract => search below
107  PAR len = (upper-lower);
108  upper = lower + len/10;
109  lower = upper - 14*len/10;
110  }
111  return binarySearch_upper (forward<FUN> (fun), lower,upper,epsilon);
112  }
113 
114 
115 } // namespace lib
116 #endif /*LIB_BINARY_SEARCH_H*/
ASSERT_VALID_SIGNATURE
#define ASSERT_VALID_SIGNATURE(_FUN_, _SIG_)
Macro for a compile-time check to verify the given generic functors or lambdas expose some expected s...
Definition: function.hpp:247
lib
Implementation namespace for support and library code.
Definition: common-services.cpp:54
function.hpp
Metaprogramming tools for transforming functor types.
lib::binarySearch_upper
auto binarySearch_upper(FUN &&fun, PAR lower, PAR upper, PAR epsilon)
entrance point to binary search to ensure the upper point indeed fulfils the test.
Definition: binary-search.hpp:81
lib::binarySearch_inner
auto binarySearch_inner(FUN &&fun, PAR lower, PAR upper, PAR epsilon)
binary search: actual search loop
Definition: binary-search.hpp:56