-
Notifications
You must be signed in to change notification settings - Fork 0
/
kcomb.go
106 lines (87 loc) · 1.88 KB
/
kcomb.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
package kcomb
// Datum represents a single value within a set.
type Datum struct {
Value interface{}
}
// Set represents a column (or set) of data of a similar kind.
type Set []Datum
// Combine will generate every distinct permutation of values within a
// collection of sets.
//
// Example:
// argument: [ [ apple, orange ], [ celery, broccoli ] ]
// output: => [
// [ apple, celery ],
// [ apple, broccoli ],
// [ orange, celery ],
// [ orange, broccoli ]
// ]
func Combine(columns []Set) []Set {
n := len(columns)
sliceSize := 100
idx := 0
indices := make([]int, n)
combset := make([]Set, sliceSize)
for {
comb := make(Set, n)
for i := 0; i < n; i++ {
comb[i] = columns[i][indices[i]]
}
c := cap(combset)
if idx > c-1 {
newCombset := make([]Set, c*2)
copy(newCombset, combset)
combset = newCombset
}
combset[idx] = comb
idx++
next := n - 1
for next >= 0 && (indices[next]+1 >= len(columns[next])) {
next--
}
if next < 0 {
return combset[0:idx]
}
indices[next]++
for i := next + 1; i < n; i++ {
indices[i] = 0
}
}
}
// CombineGenerator implements the same algorithm as Combine, except returns a stream to be
// used in a pipeline. See demo for usage.
func CombineGenerator(
done <-chan struct{},
columns []Set,
) <-chan Set {
stream := make(chan Set, 1)
n := len(columns)
indices := make([]int, n)
go func() {
defer close(stream)
for {
select {
case <-done:
return
default:
comb := make(Set, n)
for i := 0; i < n; i++ {
comb[i] = columns[i][indices[i]]
}
stream <- comb
next := n - 1
for next >= 0 && (indices[next]+1 >= len(columns[next])) {
next--
}
if next < 0 {
return
}
indices[next]++
for i := next + 1; i < n; i++ {
indices[i] = 0
}
}
}
}()
return stream
}