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
|
package share
// Deque is a double-ended queue with an unlimited capacity.
type Deque[T any] struct {
// Sending to PutTail adds an element to the back of the deque
// and never blocks.
PutTail chan<- T
// Sending to PutHead adds an element to the front of the deque
// and never blocks.
PutHead chan<- T
// Receiving from TakeHead removes an element from the front
// of the deque, or, if the queue is empty, blocks until an element
// is enqueued.
TakeHead <-chan T
// Receiving from TakeTail removes an element from the back
// of the deque, or, if the deque is empty, blocks until an element
// is enqueued.
TakeTail <-chan T
}
func NewDeque[T any]() Deque[T] {
putTail, putHead := make(chan T), make(chan T)
takeHead, takeTail := make(chan T), make(chan T)
go run(putTail, putHead, takeHead, takeTail)
return Deque[T]{
PutTail: putTail,
PutHead: putHead,
TakeHead: takeHead,
TakeTail: takeTail,
}
}
func run[T any](putTail, putHead <-chan T, takeHead, takeTail chan<- T) {
defer close(takeTail)
defer close(takeHead)
var buf []T
// While the Put channels are open,
for ok := true; ok; {
if len(buf) > 0 {
buf, ok = putOrTake(putTail, putHead, takeHead, takeTail, buf)
} else {
buf, ok = put(putTail, putHead, buf)
}
}
flush(takeHead, takeTail, buf)
}
func flush[T any](takeHead, takeTail chan<- T, buf []T) {
for len(buf) > 0 {
select {
case takeHead <- buf[0]:
buf = buf[1:]
case takeTail <- buf[len(buf)-1]:
buf = buf[:len(buf)-1]
}
}
}
func putOrTake[T any](putTail, putHead <-chan T, takeHead, takeTail chan<- T, buf []T) ([]T, bool) {
select {
case takeHead <- buf[0]:
buf = buf[1:]
case takeTail <- buf[len(buf)-1]:
buf = buf[:len(buf)-1]
case v, ok := <-putTail:
if !ok {
return buf, false
}
buf = append(buf, v)
case v, ok := <-putHead:
if !ok {
return buf, false
}
buf = append([]T{v}, buf...)
}
return buf, true
}
func put[T any](putTail, putHead <-chan T, buf []T) ([]T, bool) {
var v T
var ok bool
select {
case v, ok = <-putTail:
if ok {
buf = append(buf, v)
}
case v, ok = <-putHead:
if ok {
buf = append([]T{v}, buf...)
}
}
return buf, ok
}
// Close the Put channels of the deque.
// The deque will wait until all elements have been drained through
// either of the Take channels before closing them.
func (dq Deque[T]) Close() {
close(dq.PutTail)
close(dq.PutHead)
}
|