-
Notifications
You must be signed in to change notification settings - Fork 661
/
bag.go
156 lines (131 loc) · 3.35 KB
/
bag.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
// (c) 2019-2020, Ava Labs, Inc. All rights reserved.
// See the file LICENSE for licensing terms.
package ids
import (
"fmt"
"strings"
)
const (
minBagSize = 16
)
// Bag is a multiset of IDs.
//
// A bag has the ability to split and filter on it's bits for ease of use for
// binary voting.
type Bag struct {
counts map[ID]int
size int
mode ID
modeFreq int
threshold int
metThreshold Set
}
func (b *Bag) init() {
if b.counts == nil {
b.counts = make(map[ID]int, minBagSize)
}
}
// SetThreshold sets the number of times an ID must be added to be contained in
// the threshold set.
func (b *Bag) SetThreshold(threshold int) {
if b.threshold == threshold {
return
}
b.threshold = threshold
b.metThreshold.Clear()
for vote, count := range b.counts {
if count >= threshold {
b.metThreshold.Add(vote)
}
}
}
// Add increases the number of times each id has been seen by one.
func (b *Bag) Add(ids ...ID) {
for _, id := range ids {
b.AddCount(id, 1)
}
}
// AddCount increases the nubmer of times the id has been seen by count.
//
// count must be >= 0
func (b *Bag) AddCount(id ID, count int) {
if count <= 0 {
return
}
b.init()
totalCount := b.counts[id] + count
b.counts[id] = totalCount
b.size += count
if totalCount > b.modeFreq {
b.mode = id
b.modeFreq = totalCount
}
if totalCount >= b.threshold {
b.metThreshold.Add(id)
}
}
// Count returns the number of times the id has been added.
func (b *Bag) Count(id ID) int {
return b.counts[id]
}
// Len returns the number of times an id has been added.
func (b *Bag) Len() int { return b.size }
// List returns a list of all ids that have been added.
func (b *Bag) List() []ID {
idList := make([]ID, len(b.counts))
i := 0
for id := range b.counts {
idList[i] = id
i++
}
return idList
}
// Equals returns true if the bags contain the same elements
func (b *Bag) Equals(oIDs Bag) bool {
if b.Len() != oIDs.Len() {
return false
}
for key, value := range b.counts {
if value != oIDs.counts[key] {
return false
}
}
return true
}
// Mode returns the id that has been seen the most and the number of times it
// has been seen. Ties are broken by the first id to be seen the reported number
// of times.
func (b *Bag) Mode() (ID, int) { return b.mode, b.modeFreq }
// Threshold returns the ids that have been seen at least threshold times.
func (b *Bag) Threshold() Set { return b.metThreshold }
// Filter returns the bag of ids with the same counts as this bag, except all
// the ids in the returned bag must have the same bits in the range [start, end)
// as id.
func (b *Bag) Filter(start, end int, id ID) Bag {
newBag := Bag{}
for vote, count := range b.counts {
if EqualSubset(start, end, id, vote) {
newBag.AddCount(vote, count)
}
}
return newBag
}
// Split returns the bags of ids with the same counts a this bag, except all ids
// in the 0th index have a 0 at bit [index], and all ids in the 1st index have a
// 1 at bit [index].
func (b *Bag) Split(index uint) [2]Bag {
splitVotes := [2]Bag{}
for vote, count := range b.counts {
bit := vote.Bit(index)
splitVotes[bit].AddCount(vote, count)
}
return splitVotes
}
func (b *Bag) String() string {
sb := strings.Builder{}
sb.WriteString(fmt.Sprintf("Bag: (Size = %d)", b.Len()))
for id, count := range b.counts {
sb.WriteString(fmt.Sprintf("\n ID[%s]: Count = %d", id, count))
}
return sb.String()
}