blob: 29eb2e5a22470be90c2ac61e66733f8e2b85b38e [file] [log] [blame]
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -07001/*
2Open Source Initiative OSI - The MIT License (MIT):Licensing
3
4The MIT License (MIT)
5Copyright (c) 2013 Ralph Caraveo (deckarep@gmail.com)
6
7Permission is hereby granted, free of charge, to any person obtaining a copy of
8this software and associated documentation files (the "Software"), to deal in
9the Software without restriction, including without limitation the rights to
10use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
11of the Software, and to permit persons to whom the Software is furnished to do
12so, subject to the following conditions:
13
14The above copyright notice and this permission notice shall be included in all
15copies or substantial portions of the Software.
16
17THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
23SOFTWARE.
24*/
25
26// Package mapset implements a simple and generic set collection.
27// Items stored within it are unordered and unique. It supports
28// typical set operations: membership testing, intersection, union,
29// difference, symmetric difference and cloning.
30//
31// Package mapset provides two implementations of the Set
32// interface. The default implementation is safe for concurrent
33// access, but a non-thread-safe implementation is also provided for
34// programs that can benefit from the slight speed improvement and
35// that can enforce mutual exclusion through other means.
36package mapset
37
38// Set is the primary interface provided by the mapset package. It
39// represents an unordered set of data and a large number of
40// operations that can be applied to that set.
41type Set interface {
42 // Adds an element to the set. Returns whether
43 // the item was added.
44 Add(i interface{}) bool
45
46 // Returns the number of elements in the set.
47 Cardinality() int
48
49 // Removes all elements from the set, leaving
50 // the empty set.
51 Clear()
52
53 // Returns a clone of the set using the same
54 // implementation, duplicating all keys.
55 Clone() Set
56
57 // Returns whether the given items
58 // are all in the set.
59 Contains(i ...interface{}) bool
60
61 // Returns the difference between this set
62 // and other. The returned set will contain
63 // all elements of this set that are not also
64 // elements of other.
65 //
66 // Note that the argument to Difference
67 // must be of the same type as the receiver
68 // of the method. Otherwise, Difference will
69 // panic.
70 Difference(other Set) Set
71
72 // Determines if two sets are equal to each
73 // other. If they have the same cardinality
74 // and contain the same elements, they are
75 // considered equal. The order in which
76 // the elements were added is irrelevant.
77 //
78 // Note that the argument to Equal must be
79 // of the same type as the receiver of the
80 // method. Otherwise, Equal will panic.
81 Equal(other Set) bool
82
83 // Returns a new set containing only the elements
84 // that exist only in both sets.
85 //
86 // Note that the argument to Intersect
87 // must be of the same type as the receiver
88 // of the method. Otherwise, Intersect will
89 // panic.
90 Intersect(other Set) Set
91
92 // Determines if every element in this set is in
93 // the other set but the two sets are not equal.
94 //
95 // Note that the argument to IsProperSubset
96 // must be of the same type as the receiver
97 // of the method. Otherwise, IsProperSubset
98 // will panic.
99 IsProperSubset(other Set) bool
100
101 // Determines if every element in the other set
102 // is in this set but the two sets are not
103 // equal.
104 //
105 // Note that the argument to IsSuperset
106 // must be of the same type as the receiver
107 // of the method. Otherwise, IsSuperset will
108 // panic.
109 IsProperSuperset(other Set) bool
110
111 // Determines if every element in this set is in
112 // the other set.
113 //
114 // Note that the argument to IsSubset
115 // must be of the same type as the receiver
116 // of the method. Otherwise, IsSubset will
117 // panic.
118 IsSubset(other Set) bool
119
120 // Determines if every element in the other set
121 // is in this set.
122 //
123 // Note that the argument to IsSuperset
124 // must be of the same type as the receiver
125 // of the method. Otherwise, IsSuperset will
126 // panic.
127 IsSuperset(other Set) bool
128
129 // Iterates over elements and executes the passed func against each element.
130 // If passed func returns true, stop iteration at the time.
131 Each(func(interface{}) bool)
132
133 // Returns a channel of elements that you can
134 // range over.
135 Iter() <-chan interface{}
136
137 // Returns an Iterator object that you can
138 // use to range over the set.
139 Iterator() *Iterator
140
141 // Remove a single element from the set.
142 Remove(i interface{})
143
144 // Provides a convenient string representation
145 // of the current state of the set.
146 String() string
147
148 // Returns a new set with all elements which are
149 // in either this set or the other set but not in both.
150 //
151 // Note that the argument to SymmetricDifference
152 // must be of the same type as the receiver
153 // of the method. Otherwise, SymmetricDifference
154 // will panic.
155 SymmetricDifference(other Set) Set
156
157 // Returns a new set with all elements in both sets.
158 //
159 // Note that the argument to Union must be of the
160
161 // same type as the receiver of the method.
162 // Otherwise, IsSuperset will panic.
163 Union(other Set) Set
164
165 // Pop removes and returns an arbitrary item from the set.
166 Pop() interface{}
167
168 // Returns all subsets of a given set (Power Set).
169 PowerSet() Set
170
171 // Returns the Cartesian Product of two sets.
172 CartesianProduct(other Set) Set
173
174 // Returns the members of the set as a slice.
175 ToSlice() []interface{}
176}
177
178// NewSet creates and returns a reference to an empty set. Operations
179// on the resulting set are thread-safe.
180func NewSet(s ...interface{}) Set {
181 set := newThreadSafeSet()
182 for _, item := range s {
183 set.Add(item)
184 }
185 return &set
186}
187
188// NewSetWith creates and returns a new set with the given elements.
189// Operations on the resulting set are thread-safe.
190func NewSetWith(elts ...interface{}) Set {
191 return NewSetFromSlice(elts)
192}
193
194// NewSetFromSlice creates and returns a reference to a set from an
195// existing slice. Operations on the resulting set are thread-safe.
196func NewSetFromSlice(s []interface{}) Set {
197 a := NewSet(s...)
198 return a
199}
200
201// NewThreadUnsafeSet creates and returns a reference to an empty set.
202// Operations on the resulting set are not thread-safe.
203func NewThreadUnsafeSet() Set {
204 set := newThreadUnsafeSet()
205 return &set
206}
207
208// NewThreadUnsafeSetFromSlice creates and returns a reference to a
209// set from an existing slice. Operations on the resulting set are
210// not thread-safe.
211func NewThreadUnsafeSetFromSlice(s []interface{}) Set {
212 a := NewThreadUnsafeSet()
213 for _, item := range s {
214 a.Add(item)
215 }
216 return a
217}