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) Lumiera.org
5  2024, Hermann Vosseler <Ichthyostega@web.de>
6 
7  This program is free software; you can redistribute it and/or
8  modify it under the terms of the GNU General Public License as
9  published by the Free Software Foundation; either version 2 of
10  the License, or (at your option) any later version.
11 
12  This program is distributed in the hope that it will be useful,
13  but WITHOUT ANY WARRANTY; without even the implied warranty of
14  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  GNU General Public License for more details.
16 
17  You should have received a copy of the GNU General Public License
18  along with this program; if not, write to the Free Software
19  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
20 
21 */
22 
42 #ifndef LIB_BINARY_SEARCH_H
43 #define LIB_BINARY_SEARCH_H
44 
45 
46 #include "lib/meta/function.hpp"
47 
48 #include <utility>
49 
50 
51 namespace lib {
52 
53  using std::forward;
54 
63  template<class FUN, typename PAR>
64  inline auto
65  binarySearch_inner (FUN&& fun, PAR lower, PAR upper, PAR epsilon)
66  {
67  ASSERT_VALID_SIGNATURE (FUN, bool(PAR) );
68  REQUIRE (lower <= upper);
69  while ((upper-lower) >= epsilon)
70  {
71  PAR div = (lower+upper) / 2;
72  bool hit = fun(div);
73  if (hit)
74  upper = div;
75  else
76  lower = div;
77  }
78  return (lower+upper)/2;
79  }
80 
81 
88  template<class FUN, typename PAR>
89  inline auto
90  binarySearch_upper (FUN&& fun, PAR lower, PAR upper, PAR epsilon)
91  {
92  REQUIRE (lower <= upper);
93  while (true)
94  {
95  bool hit = fun(upper);
96  if (hit) break;
97  // the upper end breaks contract => search above
98  PAR len = (upper-lower);
99  lower = upper - len/10;
100  upper = lower + 14*len/10;
101  }
102  return binarySearch_inner (forward<FUN> (fun), lower,upper,epsilon);
103  }
104 
105 
106  template<class FUN, typename PAR>
107  inline auto
108  binarySearch (FUN&& fun, PAR lower, PAR upper, PAR epsilon)
109  {
110  REQUIRE (lower <= upper);
111  while (true)
112  {
113  bool hit = fun(lower);
114  if (not hit) break;
115  // the lower end breaks contract => search below
116  PAR len = (upper-lower);
117  upper = lower + len/10;
118  lower = upper - 14*len/10;
119  }
120  return binarySearch_upper (forward<FUN> (fun), lower,upper,epsilon);
121  }
122 
123 
124 } // namespace lib
125 #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:256
lib
Implementation namespace for support and library code.
Definition: common-services.cpp:63
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:90
lib::binarySearch_inner
auto binarySearch_inner(FUN &&fun, PAR lower, PAR upper, PAR epsilon)
binary search: actual search loop
Definition: binary-search.hpp:65