-
Notifications
You must be signed in to change notification settings - Fork 16
/
lazyset.go
107 lines (91 loc) · 2.18 KB
/
lazyset.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
package meerdag
import (
"github.com/Qitmeer/qng/common/hash"
)
//A collection that tries to imitate "lazy" operations
type LazySet struct {
sets []*HashSet
positiveIndices map[int]Empty
}
func (ls *LazySet) update(other *HashSet) {
if other == nil {
return
}
ls.positiveIndices[len(ls.sets)] = Empty{}
ls.sets = append(ls.sets, other)
}
func (ls *LazySet) differenceUpdate(other *HashSet) {
if other == nil {
return
}
ls.sets = append(ls.sets, other)
}
// The set is composed of all self and other elements.
func (ls *LazySet) Union(other *HashSet) *LazySet {
result := ls.Clone()
result.update(other)
return result
}
// A collection consisting of all elements belonging to set self and other.
func (ls *LazySet) Intersection(other *HashSet) *LazySet {
bs := ls.flattenToSet()
if bs == nil || other == nil {
return nil
}
is := bs.Intersection(other)
result := NewLazySet()
result.update(is)
return result
}
// A collection of all elements that belong to self and not to other.
func (ls *LazySet) difference(other *HashSet) *LazySet {
result := ls.Clone()
result.differenceUpdate(other)
return result
}
// Return a new copy
func (ls *LazySet) Clone() *LazySet {
result := NewLazySet()
result.sets = make([]*HashSet, len(ls.sets))
copy(result.sets, ls.sets)
for k := range ls.positiveIndices {
result.positiveIndices[k] = Empty{}
}
return result
}
func (ls *LazySet) flattenToSet() *HashSet {
baseSetIndex := -1
for index := range ls.sets {
if _, ok := ls.positiveIndices[index]; ok {
baseSetIndex = index
}
}
if baseSetIndex < 0 {
return nil
}
baseSet := ls.sets[baseSetIndex].Clone()
lenSets := len(ls.sets)
for index := baseSetIndex + 1; index < lenSets; index++ {
if _, ok := ls.positiveIndices[index]; ok {
baseSet.AddSet(ls.sets[index])
} else {
baseSet.RemoveSet(ls.sets[index])
}
}
return baseSet
}
func (ls *LazySet) Clear() {
ls.sets = []*HashSet{}
ls.positiveIndices = map[int]Empty{}
}
func (ls *LazySet) Add(elem *hash.Hash) {
}
func (ls *LazySet) Remove(elem *hash.Hash) {
}
// Create a new LazySet
func NewLazySet() *LazySet {
return &LazySet{
sets: []*HashSet{},
positiveIndices: map[int]Empty{},
}
}