-
Notifications
You must be signed in to change notification settings - Fork 0
/
iter.go
239 lines (214 loc) · 7.02 KB
/
iter.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
// Package giter implements lazy, type-safe iterators in Go.
//
// Iterators are implemented via a struct Iterator, which exposes a channel that emits the
// iterator's values.
//
// Make creates Iterators via a provided implementation function that produces the iterator's
// values.
//
// These iterators can be effectively created and used with just these two elements; however, many
// common use-cases are supported by more convenient functions that produce iterators from different
// values, transform the contents of iterators to produce new iterators, compose multiple iterators
// into a single iterator, or produce a non-iterator value from an iterator.
package giter
// An Iterator that produces 0 or more values
//
// To consume the iterator, range-loop over the Each channel.
//
// An iterator must be closed, otherwise any resources held by the iterator's producer will not be
// released. It may be closed repeatedly without ill effect.
//
// Note that all functions receiving an Iterator in this package take responsibility for closing the
// iterators they receive.
//
// Thus a trivial iterator use that consumes all elements and discards them might look like:
//
// iter := ...
// defer iter.Close()
// for _ := range iter.Each {
// }
//
// Higher-level interfaces on Iterator consumption are expected to manage closing the Iterator when
// appropriate; callers that simply pass an Iterator into an Iterator consumer should not be
// required to manually call Close.
type Iterator[T any] struct {
Each <-chan T
// stopChan is used to coordinate stopping of the Each producer goroutine: Close() sends
// a message on the channel, which the Each producer takes to mean it should stop producing
// and exit.
stopChan chan<- interface{}
}
// Close stops production to Each and releases goroutines and any other resources held for producing
// to this Iterator.
func (iter *Iterator[T]) Close() {
select {
case iter.stopChan <- nil:
default:
}
}
// Make creates an Iterator via a given function that produces values.
//
// This is the most basic interface to creating Iterators. There are many functions already provided
// in this package that create iterators from various common inputs that may preclude the need to
// use this function.
//
// The function receives a function that is given two channels: one to which the function must
// produce the values of the iterator, and the other which signals that no more values should be
// produced and the implementation should return.
//
// The resulting iterator will produce values in the order that they are produced by the passed
// implementation function, in the order they were produced in.
func Make[T any](impl func(values chan<- T, stop <-chan interface{})) (i Iterator[T]) {
values := make(chan T)
stopChan := make(chan interface{})
go func() {
impl(values, stopChan)
close(values)
}()
return Iterator[T]{
Each: values,
stopChan: stopChan,
}
}
// Slice creates an iterator that emits the values of a given slice.
//
// Modification of the provided slice can impact the values produced, so caution is advised.
//
// The given slice will be held until all values are consumed or the iterator is closed.
func Slice[T any](xs []T) (i Iterator[T]) {
return Make(
func(values chan<- T, stopChan <-chan interface{}) {
for _, x := range xs {
select {
case values <- x:
case <-stopChan:
return
}
}
})
}
// SliceReversed creates an interator that emits the values of a given slice in reverse.
//
// Same caveats apply as in Slice.
func SliceReversed[T any](xs []T) (i Iterator[T]) {
return Make(
func(values chan<- T, stopChan <-chan interface{}) {
for i, _ := range xs {
select {
case values <- xs[len(xs)-i-1]:
case <-stopChan:
return
}
}
})
}
// NeverShrink can be used to indicate to ConsumeSlice to never shrink the slice it's consuming.
func NeverShrink(_, _ int) bool { return false }
// ConsumeSlice produces an iterator emitting the values of a slice, consuming the values of the
// slice as they are emitted.
//
// Values in the source slice are overwritten with zero when they are emitted, so any pointers
// within are released.
//
// The slice can be optionally shrunk (a smaller slice is allocated, the remaining elements are
// copied into it and the old, larger slice is released) if the source slice itself needs to be
// released before all values are emitted. shrink receives the current len (remaining) and cap of
// the slice and can return true to trigger shrinking.
//
// A convenience shrink indicator function NeverShrink is provided to disable shrinking.
func ConsumeSlice[T any](shrink func(l, c int) bool, xs []T) (i Iterator[T]) {
return Make(
func(values chan<- T, stopChan <-chan interface{}) {
var zero T
defer clear(&xs)
READ_XS:
for {
for i, x := range xs {
xs[i] = zero // zero out any pointers
select {
case values <- x:
case <-stopChan:
return
}
// don't bother making an slice of cap 0 in the last
// iteration.
if i < len(xs)-1 && shrink(len(xs)-i-1, cap(xs)) {
xs = xs[i+1:]
prime := make([]T, len(xs))
copy(prime, xs)
clear(&xs)
xs = prime
// need to restart range so that we release xs and
// our indexing makes sense.
continue READ_XS
}
}
// we made it to the end of the range, thus we consumed everything.
break
}
})
}
// MapKeys returns an iterator that emits the keys of a given map.
func MapKeys[K comparable, V any](m map[K]V) (i Iterator[K]) {
return Make(
func(keys chan<- K, stopChan <-chan interface{}) {
for k, _ := range m {
select {
case keys <- k:
case <-stopChan:
return
}
}
})
}
// MapValues returns an Iterator that emits the values of a given map.
func MapValues[K comparable, V any](m map[K]V) (i Iterator[V]) {
return Make(
func(values chan<- V, stopChan <-chan interface{}) {
for _, v := range m {
select {
case values <- v:
case <-stopChan:
return
}
}
})
}
// KVPair holds the individual key-value pairs that represent a map.
//
// They can be generated from a given map with MapPairs, or a map can be created from them via
// Collect and MapCollector, or ToMap.
type KVPair[K comparable, V any] struct {
Key K
Value V
}
// MapPairs returns an Iterator emitting the key-value pairs contained in a map.
//
// Modifying the passed map before the Iterator is closed may cause unpredictable results.
func MapPairs[K comparable, V any](m map[K]V) (i Iterator[KVPair[K, V]]) {
return Make(
func(keys chan<- KVPair[K, V], stopChan <-chan interface{}) {
LOOP:
for k, v := range m {
select {
case keys <- KVPair[K, V]{k, v}:
case <-stopChan:
break LOOP
}
}
})
}
// One returns an Iterator emitting a single value.
//
// Particularly useful for calling a function that receives an Iterator and one only wants to pass
// a single value.
func One[V any](x V) Iterator[V] {
return Make(
func(values chan<- V, stopChan <-chan interface{}) {
select {
case values <- x:
case <-stopChan:
return
}
})
}