-
Notifications
You must be signed in to change notification settings - Fork 0
/
set.go
148 lines (131 loc) · 2.51 KB
/
set.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
// Idea taken from here: https://bitfieldconsulting.com/golang/generic-set
package set
type void struct{}
type set[T comparable] struct {
hashTable map[T]void
len int
}
//
// This constructor function never returns a nil pointer.
// If the set is initialized with no item(s), pointer to
// an empty/null set is returned.
//
func New[T comparable](items ...T) *set[T] {
s := set[T]{
hashTable: map[T]void{},
len: 0,
}
for _, item := range items {
if _, exist := s.hashTable[item]; !exist {
s.hashTable[item] = void{}
s.len++
}
}
return &s
}
func (s *set[T]) Len() int {
return s.len
}
func (s *set[T]) IsEmpty() bool {
return s.Len() == 0
}
//
// Identical to `set.IsEmpty()` method
//
func (s *set[T]) IsNull() bool {
return s.Len() == 0
}
func (s *set[T]) Contains(item T) bool {
_, exist := s.hashTable[item]
return exist
}
func (s *set[T]) Add(items ...T) {
for _, item := range items {
if !s.Contains(item) {
s.hashTable[item] = void{}
s.len++
}
}
}
func (s *set[T]) Remove(item T) {
if s.Contains(item) {
delete(s.hashTable, item)
s.len--
}
}
func (s *set[T]) Members() []T {
var members []T
for item := range s.hashTable {
members = append(members, item)
}
return members
}
func (s *set[T]) Union(s2 set[T]) *set[T] {
result := s
result.Add(s2.Members()...)
return result
}
func (s *set[T]) Intersection(s2 set[T]) *set[T] {
result := New[T]()
for item := range s.hashTable {
if s2.Contains(item) {
result.Add(item)
}
}
return result
}
func (s *set[T]) Difference(s2 set[T]) *set[T] {
result := s
for item := range s2.hashTable {
if result.Contains(item) {
result.Remove(item)
}
}
return result
}
//
// Checks if two sets are equal or not.
//
func (s *set[T]) IsEqual(s2 set[T]) bool {
if s.Len() != s2.Len() {
return false
}
for item := range s.hashTable {
if !s2.Contains(item) {
return false
}
}
return true
}
//
// Checks whether the set "s" and "s2" are disjoint or not.
//
func (s *set[T]) IsDisjoint(s2 set[T]) bool {
if s.IsEmpty() && s2.IsEmpty() {
return false
}
for item := range s.hashTable {
if s2.Contains(item) {
return false
}
}
return true
}
//
// Whether the set "s" is a subset of the set "s2". "proper" param
// indicates if the subset is proper or not.
//
func (s *set[T]) IsSubsetOf(s2 set[T], proper bool) bool {
if s.Len() > s2.Len() {
return false
}
if proper && s.Len() == s2.Len() {
return false
}
for item := range s.hashTable {
if !s2.Contains(item) {
return false
}
}
return true
}