Lumiera 0.pre.04
»edit your freedom«
Loading...
Searching...
No Matches
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
42namespace 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*/
function.hpp
Metaprogramming tools for detecting and transforming function types.
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:316
lib
Implementation namespace for support and library code.
Definition common-services.cpp:55
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
lib::binarySearch
auto binarySearch(FUN &&fun, PAR lower, PAR upper, PAR epsilon)
Definition binary-search.hpp:99