-
Notifications
You must be signed in to change notification settings - Fork 0
/
slice.go
259 lines (231 loc) · 6.39 KB
/
slice.go
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
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
package slice
import (
"reflect"
"sort"
"sync"
"github.com/adamcolton/luce/math/ints"
"github.com/adamcolton/luce/util/liter"
)
// Slice is a wrapper that provides helper methods
type Slice[T any] []T
// New is syntactic sugar to infer the type
func New[T any](s []T) Slice[T] {
return s
}
// Make a slice with the specified length and capacity. If capacity is set to
// 0, then ln will be used for capacity as well.
func Make[T any](ln, cp int) Slice[T] {
if cp == 0 {
cp = ln
}
return make(Slice[T], ln, cp)
}
// Clone a slice.
func (s Slice[T]) Clone() Slice[T] {
out := make([]T, len(s))
copy(out, s)
return out
}
// Swaps two values in the slice.
func (s Slice[T]) Swap(i, j int) {
s[i], s[j] = s[j], s[i]
}
// Len creates a strongly typed version of builtin len for slices.
func Len[T any](s []T) int {
return len(s)
}
// AppendNotZero will append any values from ts that are not the zero
// value for the type. Particularly useful for appending not nil values.
func (s Slice[T]) AppendNotZero(ts ...T) []T {
for _, t := range ts {
v := reflect.ValueOf(t)
if v.Kind() != reflect.Invalid && !v.IsZero() {
s = append(s, t)
}
}
return s
}
func (s Slice[T]) Iter() liter.Wrapper[T] {
return NewIter(s)
}
func (s Slice[T]) IterFactory() (i liter.Iter[T], t T, done bool) {
i = NewIter(s)
t, done = i.Cur()
return
}
// ForAll runs a Go routine for each element in s, passing it into fn. A
// WaitGroup is returned that will finish when all Go routines return.
func (s Slice[T]) ForAll(fn func(idx int, t T)) *sync.WaitGroup {
var wg sync.WaitGroup
wg.Add(len(s))
wrap := func(idx int, t T) {
fn(idx, t)
wg.Add(-1)
}
for i, t := range s {
go wrap(i, t)
}
return &wg
}
// Remove values at given indicies by swapping them with values from the end
// and truncating the slice. Values less than zero or greater than the length
// of the list are ignored. Note that idxs is reordered so if that is a slice
// passed in and the order is important, pass in a copy.
func (s Slice[T]) Remove(idxs ...int) Slice[T] {
sort.Sort(sort.Reverse(sort.IntSlice(idxs)))
ln := len(s)
prev := ln
// Depending on variations in the implementation there are two things that
// can make this behave in unintended ways. Duplicate values cause a double
// swap. And it could be possible for a value near the end of the list to
// removed, but then swapped with a value earlier in the list, reintroducing
// it. Also, negative values are not allowed.
//
// To avoid both, idxs is sorted in descending order and prev tracks the
// the last value. The "idx < prev" comparison guarentees both that there
// are no duplicates and that idx is less than the length of the list.
for _, idx := range idxs {
if idx >= 0 && idx < prev {
ln--
s.Swap(idx, ln)
prev = idx
}
}
return s[:ln]
}
// RemoveOrdered preserves the order of the slice while removing the values
// at the given indexes.
func (s Slice[T]) RemoveOrdered(idxs ...int) Slice[T] {
sort.Ints(idxs)
ln := len(idxs)
start := 0
var pIdx int
for {
if start >= ln {
return s
}
pIdx = idxs[start]
start++
if pIdx >= 0 {
break
}
}
ln = len(s)
d := 0
for _, idx := range idxs[start:] {
if idx >= ln {
break
}
if idx < 0 || idx == pIdx {
continue
}
copy(s[pIdx-d:], s[pIdx+1:idx])
d++
pIdx = idx
}
copy(s[pIdx-d:], s[pIdx+1:ln])
return s[:ln-d-1]
}
func (s Slice[T]) Buffer() Buffer[T] {
return Buffer[T](s)
}
// Pop returns the last element of the slice and the slice resized to remove
// that element. If the size of the slice is zero, the zero value for the type
// is returned.
func (s Slice[T]) Pop() (T, Slice[T]) {
ln := len(s)
if ln == 0 {
var t T
return t, s
}
ln--
return s[ln], s[:ln]
}
// Shift returns the first element of the slice and the slice resized to remove
// that element. If the size of the slice is zero, the zero value for the type
// is returned.
func (s Slice[T]) Shift() (T, Slice[T]) {
ln := len(s)
if ln == 0 {
var t T
return t, s
}
return s[0], s[1:ln]
}
// CheckCapacity ensures that Slice s has capacity c. If not, a new slice is
// created with capacity c and the slice is copied.
func (s Slice[T]) CheckCapacity(c int) Slice[T] {
if cap(s) >= c {
return s
}
out := make(Slice[T], len(s), c)
copy(out, s)
return out
}
// Search wraps sort.Search
func (s Slice[T]) Search(fn func(T) bool) int {
return sort.Search(len(s), func(idx int) bool {
return fn(s[idx])
})
}
// IdxCheck returns false if idx is out of the range of s.
func (s Slice[T]) IdxCheck(idx int) bool {
return idx >= 0 && idx < len(s)
}
// Idx provides a relative index to the slice. So a value of -1 will return
// the last index. The bool indicates if the index is in range.
func (s Slice[T]) Idx(idx int) (int, bool) {
return ints.Idx(idx, len(s))
}
// Sort wraps slice.Sort. Sorts the Slice in place. The slice is also returned
// for chaining.
func (s Slice[T]) Sort(less Less[T]) Slice[T] {
return less.Sort(s)
}
// Transform one slice to another. The transformation function's second return
// is a bool indicating if the returned value should be included in the result.
// The returned Slice is sized exactly to the output.
func Transform[In, Out any](in liter.Iter[In], fn func(In, int) (Out, bool)) Slice[Out] {
return transform(in, fn)
}
// Transform one slice to another. The transformation function's second return
// is a bool indicating if the returned value should be included in the result.
// The returned Slice is sized exactly to the output.
func TransformSlice[In, Out any](in []In, fn func(In, int) (Out, bool)) Slice[Out] {
return transform(NewIter(in), fn)
}
func transform[In, Out any](in liter.Iter[In], fn func(In, int) (Out, bool)) (out Slice[Out]) {
i, done := in.Cur()
if done {
return
}
if o, include := fn(i, in.Idx()); include {
out = transformRecurse(1, in, fn)
out[0] = o
} else {
out = transformRecurse(0, in, fn)
}
return
}
func transformRecurse[In, Out any](size int, in liter.Iter[In], fn func(In, int) (Out, bool)) Slice[Out] {
for i, done := in.Next(); !done; i, done = in.Next() {
o, include := fn(i, in.Idx())
if include {
out := transformRecurse(size+1, in, fn)
out[size] = o
return out
}
}
if size == 0 {
return nil
}
return make([]Out, size)
}
// AtIdx returns the value at idx. Fulfills list.List.
func (s Slice[T]) AtIdx(idx int) T {
return s[idx]
}
// Len returns the length of the slice. Fulfills list.List.
func (s Slice[T]) Len() int {
return len(s)
}