-
Notifications
You must be signed in to change notification settings - Fork 661
/
unique_bag.go
102 lines (82 loc) · 1.75 KB
/
unique_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
// (c) 2019-2020, Ava Labs, Inc. All rights reserved.
// See the file LICENSE for licensing terms.
package ids
import (
"fmt"
"strings"
)
const (
minUniqueBagSize = 16
)
// UniqueBag ...
type UniqueBag map[ID]BitSet
func (b *UniqueBag) init() {
if *b == nil {
*b = make(map[ID]BitSet, minUniqueBagSize)
}
}
// Add ...
func (b *UniqueBag) Add(setID uint, idSet ...ID) {
bs := BitSet(0)
bs.Add(setID)
for _, id := range idSet {
b.UnionSet(id, bs)
}
}
// UnionSet ...
func (b *UniqueBag) UnionSet(id ID, set BitSet) {
b.init()
previousSet := (*b)[id]
previousSet.Union(set)
(*b)[id] = previousSet
}
// DifferenceSet ...
func (b *UniqueBag) DifferenceSet(id ID, set BitSet) {
b.init()
previousSet := (*b)[id]
previousSet.Difference(set)
(*b)[id] = previousSet
}
// Difference ...
func (b *UniqueBag) Difference(diff *UniqueBag) {
b.init()
for id, previousSet := range *b {
if previousSetDiff, exists := (*diff)[id]; exists {
previousSet.Difference(previousSetDiff)
}
(*b)[id] = previousSet
}
}
// GetSet ...
func (b *UniqueBag) GetSet(id ID) BitSet { return (*b)[id] }
// RemoveSet ...
func (b *UniqueBag) RemoveSet(id ID) { delete(*b, id) }
// List ...
func (b *UniqueBag) List() []ID {
idList := make([]ID, len(*b))
i := 0
for id := range *b {
idList[i] = id
i++
}
return idList
}
// Bag ...
func (b *UniqueBag) Bag(alpha int) Bag {
bag := Bag{
counts: make(map[ID]int, len(*b)),
}
bag.SetThreshold(alpha)
for id, bs := range *b {
bag.AddCount(id, bs.Len())
}
return bag
}
func (b *UniqueBag) String() string {
sb := strings.Builder{}
sb.WriteString(fmt.Sprintf("UniqueBag: (Size = %d)", len(*b)))
for id, set := range *b {
sb.WriteString(fmt.Sprintf("\n ID[%s]: Members = %s", id, set))
}
return sb.String()
}