aptera-data/fbisect.py at main · bennetyee/aptera-data · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#!/usr/bin/python3

# Binary search: similar idea as the bisect module, except that we are
# doing bisection using an univariate monotonically non-decreasing (or
# non-increasing) function from integers to integers.

from typing import Callable

# range R = \left\[x0,x1\right\]

# Henceforth until otherwise indicated,
# f is monotonically non-decreasing; i.e.,
#   \forall x_1, x_2 \in R:  x_1 < x_2 \rightarrow f(x_1) \le f(x_2)

# returns x \in R such that f(x) \ge ythreshold
#   \wedge \forall x' \in R: f(x') \ge ythreshold \rightarrow x \le x'
def find_first_ge(f: Callable[[int], int],
                  ythreshold: int,
                  x0: int,
                  x1: int) -> int:
    assert x0 <= x1, f'find_first_ge: {x0}>{x1}: empty range'  # non-empty range
    assert f(x1) >= ythreshold, f'find_first_ge: f({x1})={f(x1)} < {ythreshold}: right end of range below threshold'
    if f(x0) >= ythreshold:
        return x0
    # f(x0) < ythreshold
    return find_first_ge_intern(f, ythreshold, x0, x1)

def find_first_ge_intern(f: Callable[[int], int],
                         ythreshold: int,
                         x0: int,
                         x1: int) -> int:

    if x0 + 1 == x1:
        return x1
    xmid = (x0 + x1) // 2  # python, no overflow
    if f(xmid) >= ythreshold:
        return find_first_ge_intern(f, ythreshold, x0, xmid)

    # f(xmid) < ythreshold
    return find_first_ge_intern(f, ythreshold, xmid, x1)

# returns x \in R such that f(x) \le ythreshold
#   \wedge \forall x' \in R: f(x') \le ythreshold \rightarrow x' \le x
def find_last_le(f: Callable[[int], int],
                 ythreshold: int,
                 x0: int,
                 x1: int) -> int:
    assert x0 <= x1, f'find_last_le: {x0}>{x1}: empty range'  # non-empty range
    assert f(x0) <= ythreshold, f'find_last_le: f({x0})={f(x0)}>{ythreshold}: left end of range above threshold'
    if f(x1) <= ythreshold:
        return x1
    # f(x1) > ythreshold
    return find_last_le_intern(f, ythreshold, x0, x1)

def find_last_le_intern(f: Callable[[int], int],
                        ythreshold: int,
                        x0: int,
                        x1: int) -> int:
    if x0 + 1 == x1:
        return x0
    xmid = (x0 + x1) // 2  # python, no overflow
    if f(xmid) <= ythreshold:
        return find_last_le_intern(f, ythreshold, xmid, x1)

    # f(xmid) > ythreshold
    return find_last_le_intern(f, ythreshold, x0, xmid)

# Henceforth until otherwise indicated,
# f is monotonically nonincreasing, i.e.,
#   \forall x_1, x_2 \in R:  x_1 < x_2 \rightarrow f(x_1) \ge f(x_2)

# returns x \in R such that f(x) \le ythreshold
#   \wedge \forall x' \in R: f(x') \le ythreshold \rightarrow x \le x'
def find_first_le(f: Callable[[int], int],
                  ythreshold: int,
                  x0: int,
                  x1: int) -> int:
    assert x0 <= x1, f'find_first_le: {x0}>{x1}: empty range'  # non-empty range
    assert f(x1) <= ythreshold, f'find_first_le: f({x1})={f(x1)}>{ythreshold}: right end of range above threshold'
    if f(x0) <= ythreshold:
        return x0
    # f(x0) > ythreshold
    return find_first_le_intern(f, ythreshold, x0, x1)

def find_first_le_intern(f: Callable[[int], int],
                         ythreshold: int,
                         x0: int,
                         x1: int) -> int:

    if x0 + 1 == x1:
        return x1
    xmid = (x0 + x1) // 2  # python, no overflow
    if f(xmid) <= ythreshold:
        return find_first_le_intern(f, ythreshold, x0, xmid)

    # f(xmid) > ythreshold
    return find_first_le_intern(f, ythreshold, xmid, x1)

# returns x \in R such that f(x) \ge ythreshold
#   \wedge \forall x' \in R: f(x') \ge ythreshold \rightarrow x' \le x
def find_last_ge(f: Callable[[int], int],
                 ythreshold: int,
                 x0: int,
                 x1: int) -> int:
    assert x0 <= x1, f'find_last_ge: {x0}>{x1}: empty range'  # non-empty range
    assert f(x0) >= ythreshold, f'find_last_ge: f({x0})={f(x0)}<{ythreshold}: left end of range below threshold'
    if f(x1) >= ythreshold:
        return x1
    # f(x1) < ythreshold
    return find_last_ge_intern(f, ythreshold, x0, x1)

def find_last_ge_intern(f: Callable[[int], int],
                        ythreshold: int,
                        x0: int,
                        x1: int) -> int:
    if x0 + 1 == x1:
        return x0
    xmid = (x0 + x1) // 2  # python, no overflow
    if f(xmid) >= ythreshold:
        return find_last_ge_intern(f, ythreshold, xmid, x1)

    # f(xmid) < ythreshold
    return find_last_ge_intern(f, ythreshold, x0, xmid)