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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
|
// Copyright (C) 2022 Luke Shumaker <lukeshu@lukeshu.com>
//
// SPDX-License-Identifier: GPL-2.0-or-later
package slices
import (
"sort"
"golang.org/x/exp/constraints"
)
func Contains[T comparable](needle T, haystack []T) bool {
for _, straw := range haystack {
if needle == straw {
return true
}
}
return false
}
func RemoveAll[T comparable](haystack []T, needle T) []T {
for i, straw := range haystack {
if needle == straw {
return append(
haystack[:i],
RemoveAll(haystack[i+1:], needle)...)
}
}
return haystack
}
func RemoveAllFunc[T any](haystack []T, f func(T) bool) []T {
for i, straw := range haystack {
if f(straw) {
return append(
haystack[:i],
RemoveAllFunc(haystack[i+1:], f)...)
}
}
return haystack
}
func Reverse[T any](slice []T) {
for i := 0; i < len(slice)/2; i++ {
j := (len(slice) - 1) - i
slice[i], slice[j] = slice[j], slice[i]
}
}
func Max[T constraints.Ordered](a T, rest ...T) T {
ret := a
for _, b := range rest {
if b > a {
ret = b
}
}
return ret
}
func Min[T constraints.Ordered](a T, rest ...T) T {
ret := a
for _, b := range rest {
if b < a {
ret = b
}
}
return ret
}
func Sort[T constraints.Ordered](slice []T) {
sort.Slice(slice, func(i, j int) bool {
return slice[i] < slice[j]
})
}
// returns (a+b)/2, but avoids overflow
func avg(a, b int) int {
return int(uint(a+b) >> 1)
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
// Search the slice for a value for which `fn(slice[i]) = 0`.
//
// : + + + 0 0 0 - - -
// : ^ ^ ^
// : any of
//
// You can conceptualize `fn` as subtraction:
//
// func(straw T) int {
// return needle - straw
// }
func Search[T any](slice []T, fn func(T) int) (int, bool) {
beg, end := 0, len(slice)
for beg < end {
midpoint := avg(beg, end)
direction := fn(slice[midpoint])
switch {
case direction < 0:
end = midpoint
case direction > 0:
beg = midpoint + 1
case direction == 0:
return midpoint, true
}
}
return 0, false
}
// Search the slice for the left-most value for which `fn(slice[i]) = 0`.
//
// : + + + 0 0 0 - - -
// : ^
//
// You can conceptualize `fn` as subtraction:
//
// func(straw T) int {
// return needle - straw
// }
func SearchLowest[T any](slice []T, fn func(T) int) (int, bool) {
lastBad, firstGood, firstBad := -1, len(slice), len(slice)
for lastBad+1 < min(firstGood, firstBad) {
midpoint := avg(lastBad, min(firstGood, firstBad))
direction := fn(slice[midpoint])
switch {
case direction < 0:
firstBad = midpoint
case direction > 0:
lastBad = midpoint
default:
firstGood = midpoint
}
}
if firstGood == len(slice) {
return 0, false
}
return firstGood, true
}
// Search the slice for the right-most value for which `fn(slice[i]) = 0`.
//
// : + + + 0 0 0 - - -
// : ^
//
// You can conceptualize `fn` as subtraction:
//
// func(straw T) int {
// return needle - straw
// }
func SearchHighest[T any](slice []T, fn func(T) int) (int, bool) {
lastBad, lastGood, firstBad := -1, -1, len(slice)
for max(lastBad, lastGood)+1 < firstBad {
midpoint := avg(max(lastBad, lastGood), firstBad)
direction := fn(slice[midpoint])
switch {
case direction < 0:
firstBad = midpoint
case direction > 0:
lastBad = midpoint
default:
lastGood = midpoint
}
}
if lastGood < 0 {
return 0, false
}
return lastGood, true
}
|
