1/* 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 // Returns all subsets of a given set (Power Set). 166 PowerSet() Set 167 168 // Returns the Cartesian Product of two sets. 169 CartesianProduct(other Set) Set 170 171 // Returns the members of the set as a slice. 172 ToSlice() []interface{} 173} 174 175// NewSet creates and returns a reference to an empty set. Operations 176// on the resulting set are thread-safe. 177func NewSet(s ...interface{}) Set { 178 set := newThreadSafeSet() 179 for _, item := range s { 180 set.Add(item) 181 } 182 return &set 183} 184 185// NewSetWith creates and returns a new set with the given elements. 186// Operations on the resulting set are thread-safe. 187func NewSetWith(elts ...interface{}) Set { 188 return NewSetFromSlice(elts) 189} 190 191// NewSetFromSlice creates and returns a reference to a set from an 192// existing slice. Operations on the resulting set are thread-safe. 193func NewSetFromSlice(s []interface{}) Set { 194 a := NewSet(s...) 195 return a 196} 197 198// NewThreadUnsafeSet creates and returns a reference to an empty set. 199// Operations on the resulting set are not thread-safe. 200func NewThreadUnsafeSet() Set { 201 set := newThreadUnsafeSet() 202 return &set 203} 204 205// NewThreadUnsafeSetFromSlice creates and returns a reference to a 206// set from an existing slice. Operations on the resulting set are 207// not thread-safe. 208func NewThreadUnsafeSetFromSlice(s []interface{}) Set { 209 a := NewThreadUnsafeSet() 210 for _, item := range s { 211 a.Add(item) 212 } 213 return a 214} 215