golang练手小项目系列(6)-使用map实现set

问题描述

go没有提供set数据结构,请用map实现set

要点

需要支持方法:

• Add 添加元素
• Remove 删除元素
• Cardinality 获取 Set 长度
• Clear 清空 Set
• Contains 检测元素是否在 Set 中
• Pop() 随机删除一个元素并返回被删除的元素
• ToSlice() []interface{} 转换成slice返回

拓展

• Clone 复制 Set
• Difference(other Set) Set 返回和另一个Set的差集
• Equal(other Set) bool 判断和另一个Set是否相等
• Intersect(other Set) Set 返回和另一个Set的交集
• SymmetricDifference(other Set) Set 返回不在交集中的元素的集合
• Union(other Set) Set 返回并集
• 实现一个线程安全的版本

实现

//set.go
// Package mapset implements a simple and generic set collection.
// Items stored within it are unordered and unique. It supports
// typical set operations: membership testing, intersection, union,
// difference, symmetric difference and cloning.
//
// Package mapset provides two implementations of the Set
// interface. The default implementation is safe for concurrent
// access, but a non-thread-safe implementation is also provided for
// programs that can benefit from the slight speed improvement and
// that can enforce mutual exclusion through other means.
package mapset
// Set is the primary interface provided by the mapset package. It
// represents an unordered set of data and a large number of
// operations that can be applied to that set.
type Set interface {
 // Adds an element to the set. Returns whether
 // the item was added.
 Add(i interface{}) bool
 // Returns the number of elements in the set.
 Cardinality() int
 // Removes all elements from the set, leaving
 // the empty set.
 Clear()
 // Returns a clone of the set using the same
 // implementation, duplicating all keys.
 Clone() Set
 // Returns whether the given items
 // are all in the set.
 Contains(i ...interface{}) bool
 // Returns the difference between this set
 // and other. The returned set will contain
 // all elements of this set that are not also
 // elements of other.
 //
 // Note that the argument to Difference
 // must be of the same type as the receiver
 // of the method. Otherwise, Difference will
 // panic.
 Difference(other Set) Set
 // Determines if two sets are equal to each
 // other. If they have the same cardinality
 // and contain the same elements, they are
 // considered equal. The order in which
 // the elements were added is irrelevant.
 //
 // Note that the argument to Equal must be
 // of the same type as the receiver of the
 // method. Otherwise, Equal will panic.
 Equal(other Set) bool
 // Returns a new set containing only the elements
 // that exist only in both sets.
 //
 // Note that the argument to Intersect
 // must be of the same type as the receiver
 // of the method. Otherwise, Intersect will
 // panic.
 Intersect(other Set) Set
 // Determines if every element in this set is in
 // the other set but the two sets are not equal.
 //
 // Note that the argument to IsProperSubset
 // must be of the same type as the receiver
 // of the method. Otherwise, IsProperSubset
 // will panic.
 IsProperSubset(other Set) bool
 // Determines if every element in the other set
 // is in this set but the two sets are not
 // equal.
 //
 // Note that the argument to IsSuperset
 // must be of the same type as the receiver
 // of the method. Otherwise, IsSuperset will
 // panic.
 IsProperSuperset(other Set) bool
 // Determines if every element in this set is in
 // the other set.
 //
 // Note that the argument to IsSubset
 // must be of the same type as the receiver
 // of the method. Otherwise, IsSubset will
 // panic.
 IsSubset(other Set) bool
 // Determines if every element in the other set
 // is in this set.
 //
 // Note that the argument to IsSuperset
 // must be of the same type as the receiver
 // of the method. Otherwise, IsSuperset will
 // panic.
 IsSuperset(other Set) bool
 // Iterates over elements and executes the passed func against each element.
 // If passed func returns true, stop iteration at the time.
 Each(func(interface{}) bool)
 // Returns a channel of elements that you can
 // range over.
 Iter() <-chan interface{}
 // Returns an Iterator object that you can
 // use to range over the set.
 Iterator() *Iterator
 // Remove a single element from the set.
 Remove(i interface{})
 // Provides a convenient string representation
 // of the current state of the set.
 String() string
 // Returns a new set with all elements which are
 // in either this set or the other set but not in both.
 //
 // Note that the argument to SymmetricDifference
 // must be of the same type as the receiver
 // of the method. Otherwise, SymmetricDifference
 // will panic.
 SymmetricDifference(other Set) Set
 // Returns a new set with all elements in both sets.
 //
 // Note that the argument to Union must be of the
 // same type as the receiver of the method.
 // Otherwise, IsSuperset will panic.
 Union(other Set) Set
 // Pop removes and returns an arbitrary item from the set.
 Pop() interface{}
 // Returns all subsets of a given set (Power Set).
 PowerSet() Set
 // Returns the Cartesian Product of two sets.
 CartesianProduct(other Set) Set
 // Returns the members of the set as a slice.
 ToSlice() []interface{}
}
// NewSet creates and returns a reference to an empty set. Operations
// on the resulting set are thread-safe.
func NewSet(s ...interface{}) Set {
 set := newThreadSafeSet()
 for _, item := range s {
 set.Add(item)
 }
 return &set
}
// NewSetWith creates and returns a new set with the given elements.
// Operations on the resulting set are thread-safe.
func NewSetWith(elts ...interface{}) Set {
 return NewSetFromSlice(elts)
}
// NewSetFromSlice creates and returns a reference to a set from an
// existing slice. Operations on the resulting set are thread-safe.
func NewSetFromSlice(s []interface{}) Set {
 a := NewSet(s...)
 return a
}
// NewThreadUnsafeSet creates and returns a reference to an empty set.
// Operations on the resulting set are not thread-safe.
func NewThreadUnsafeSet() Set {
 set := newThreadUnsafeSet()
 return &set
}
// NewThreadUnsafeSetFromSlice creates and returns a reference to a
// set from an existing slice. Operations on the resulting set are
// not thread-safe.
func NewThreadUnsafeSetFromSlice(s []interface{}) Set {
 a := NewThreadUnsafeSet()
 for _, item := range s {
 a.Add(item)
 }
 return a
}
// iterator.go
package mapset
// Iterator defines an iterator over a Set, its C channel can be used to range over the Set's
// elements.
type Iterator struct {
 C <-chan interface{}
 stop chan struct{}
}
// Stop stops the Iterator, no further elements will be received on C, C will be closed.
func (i *Iterator) Stop() {
 // Allows for Stop() to be called multiple times
 // (close() panics when called on already closed channel)
 defer func() {
 recover()
 }()
 close(i.stop)
 // Exhaust any remaining elements.
 for range i.C {
 }
}
// newIterator returns a new Iterator instance together with its item and stop channels.
func newIterator() (*Iterator, chan<- interface{}, <-chan struct{}) {
 itemChan := make(chan interface{})
 stopChan := make(chan struct{})
 return &Iterator{
 C: itemChan,
 stop: stopChan,
 }, itemChan, stopChan
}
// threadunsafe.go
package mapset
import (
 "bytes"
 "encoding/json"
 "fmt"
 "reflect"
 "strings"
)
type threadUnsafeSet map[interface{}]struct{}
// An OrderedPair represents a 2-tuple of values.
type OrderedPair struct {
 First interface{}
 Second interface{}
}
func newThreadUnsafeSet() threadUnsafeSet {
 return make(threadUnsafeSet)
}
// Equal says whether two 2-tuples contain the same values in the same order.
func (pair *OrderedPair) Equal(other OrderedPair) bool {
 if pair.First == other.First &&
 pair.Second == other.Second {
 return true
 }
 return false
}
func (set *threadUnsafeSet) Add(i interface{}) bool {
 _, found := (*set)[i]
 if found {
 return false //False if it existed already
 }
 (*set)[i] = struct{}{}
 return true
}
func (set *threadUnsafeSet) Contains(i ...interface{}) bool {
 for _, val := range i {
 if _, ok := (*set)[val]; !ok {
 return false
 }
 }
 return true
}
func (set *threadUnsafeSet) IsSubset(other Set) bool {
 _ = other.(*threadUnsafeSet)
 if set.Cardinality() > other.Cardinality() {
 return false
 }
 for elem := range *set {
 if !other.Contains(elem) {
 return false
 }
 }
 return true
}
func (set *threadUnsafeSet) IsProperSubset(other Set) bool {
 return set.IsSubset(other) && !set.Equal(other)
}
func (set *threadUnsafeSet) IsSuperset(other Set) bool {
 return other.IsSubset(set)
}
func (set *threadUnsafeSet) IsProperSuperset(other Set) bool {
 return set.IsSuperset(other) && !set.Equal(other)
}
func (set *threadUnsafeSet) Union(other Set) Set {
 o := other.(*threadUnsafeSet)
 unionedSet := newThreadUnsafeSet()
 for elem := range *set {
 unionedSet.Add(elem)
 }
 for elem := range *o {
 unionedSet.Add(elem)
 }
 return &unionedSet
}
func (set *threadUnsafeSet) Intersect(other Set) Set {
 o := other.(*threadUnsafeSet)
 intersection := newThreadUnsafeSet()
 // loop over smaller set
 if set.Cardinality() < other.Cardinality() {
 for elem := range *set {
 if other.Contains(elem) {
 intersection.Add(elem)
 }
 }
 } else {
 for elem := range *o {
 if set.Contains(elem) {
 intersection.Add(elem)
 }
 }
 }
 return &intersection
}
func (set *threadUnsafeSet) Difference(other Set) Set {
 _ = other.(*threadUnsafeSet)
 difference := newThreadUnsafeSet()
 for elem := range *set {
 if !other.Contains(elem) {
 difference.Add(elem)
 }
 }
 return &difference
}
func (set *threadUnsafeSet) SymmetricDifference(other Set) Set {
 _ = other.(*threadUnsafeSet)
 aDiff := set.Difference(other)
 bDiff := other.Difference(set)
 return aDiff.Union(bDiff)
}
func (set *threadUnsafeSet) Clear() {
 *set = newThreadUnsafeSet()
}
func (set *threadUnsafeSet) Remove(i interface{}) {
 delete(*set, i)
}
func (set *threadUnsafeSet) Cardinality() int {
 return len(*set)
}
func (set *threadUnsafeSet) Each(cb func(interface{}) bool) {
 for elem := range *set {
 if cb(elem) {
 break
 }
 }
}
func (set *threadUnsafeSet) Iter() <-chan interface{} {
 ch := make(chan interface{})
 go func() {
 for elem := range *set {
 ch <- elem
 }
 close(ch)
 }()
 return ch
}
func (set *threadUnsafeSet) Iterator() *Iterator {
 iterator, ch, stopCh := newIterator()
 go func() {
 L:
 for elem := range *set {
 select {
 case <-stopCh:
 break L
 case ch <- elem:
 }
 }
 close(ch)
 }()
 return iterator
}
func (set *threadUnsafeSet) Equal(other Set) bool {
 _ = other.(*threadUnsafeSet)
 if set.Cardinality() != other.Cardinality() {
 return false
 }
 for elem := range *set {
 if !other.Contains(elem) {
 return false
 }
 }
 return true
}
func (set *threadUnsafeSet) Clone() Set {
 clonedSet := newThreadUnsafeSet()
 for elem := range *set {
 clonedSet.Add(elem)
 }
 return &clonedSet
}
func (set *threadUnsafeSet) String() string {
 items := make([]string, 0, len(*set))
 for elem := range *set {
 items = append(items, fmt.Sprintf("%v", elem))
 }
 return fmt.Sprintf("Set{%s}", strings.Join(items, ", "))
}
// String outputs a 2-tuple in the form "(A, B)".
func (pair OrderedPair) String() string {
 return fmt.Sprintf("(%v, %v)", pair.First, pair.Second)
}
func (set *threadUnsafeSet) Pop() interface{} {
 for item := range *set {
 delete(*set, item)
 return item
 }
 return nil
}
func (set *threadUnsafeSet) PowerSet() Set {
 powSet := NewThreadUnsafeSet()
 nullset := newThreadUnsafeSet()
 powSet.Add(&nullset)
 for es := range *set {
 u := newThreadUnsafeSet()
 j := powSet.Iter()
 for er := range j {
 p := newThreadUnsafeSet()
 if reflect.TypeOf(er).Name() == "" {
 k := er.(*threadUnsafeSet)
 for ek := range *(k) {
 p.Add(ek)
 }
 } else {
 p.Add(er)
 }
 p.Add(es)
 u.Add(&p)
 }
 powSet = powSet.Union(&u)
 }
 return powSet
}
func (set *threadUnsafeSet) CartesianProduct(other Set) Set {
 o := other.(*threadUnsafeSet)
 cartProduct := NewThreadUnsafeSet()
 for i := range *set {
 for j := range *o {
 elem := OrderedPair{First: i, Second: j}
 cartProduct.Add(elem)
 }
 }
 return cartProduct
}
func (set *threadUnsafeSet) ToSlice() []interface{} {
 keys := make([]interface{}, 0, set.Cardinality())
 for elem := range *set {
 keys = append(keys, elem)
 }
 return keys
}
// MarshalJSON creates a JSON array from the set, it marshals all elements
func (set *threadUnsafeSet) MarshalJSON() ([]byte, error) {
 items := make([]string, 0, set.Cardinality())
 for elem := range *set {
 b, err := json.Marshal(elem)
 if err != nil {
 return nil, err
 }
 items = append(items, string(b))
 }
 return []byte(fmt.Sprintf("[%s]", strings.Join(items, ","))), nil
}
// UnmarshalJSON recreates a set from a JSON array, it only decodes
// primitive types. Numbers are decoded as json.Number.
func (set *threadUnsafeSet) UnmarshalJSON(b []byte) error {
 var i []interface{}
 d := json.NewDecoder(bytes.NewReader(b))
 d.UseNumber()
 err := d.Decode(&i)
 if err != nil {
 return err
 }
 for _, v := range i {
 switch t := v.(type) {
 case []interface{}, map[string]interface{}:
 continue
 default:
 set.Add(t)
 }
 }
 return nil
}
// threadsafe.go
package mapset
import "sync"
type threadSafeSet struct {
 s threadUnsafeSet
 sync.RWMutex
}
func newThreadSafeSet() threadSafeSet {
 return threadSafeSet{s: newThreadUnsafeSet()}
}
func (set *threadSafeSet) Add(i interface{}) bool {
 set.Lock()
 ret := set.s.Add(i)
 set.Unlock()
 return ret
}
func (set *threadSafeSet) Contains(i ...interface{}) bool {
 set.RLock()
 ret := set.s.Contains(i...)
 set.RUnlock()
 return ret
}
func (set *threadSafeSet) IsSubset(other Set) bool {
 o := other.(*threadSafeSet)
 set.RLock()
 o.RLock()
 ret := set.s.IsSubset(&o.s)
 set.RUnlock()
 o.RUnlock()
 return ret
}
func (set *threadSafeSet) IsProperSubset(other Set) bool {
 o := other.(*threadSafeSet)
 set.RLock()
 defer set.RUnlock()
 o.RLock()
 defer o.RUnlock()
 return set.s.IsProperSubset(&o.s)
}
func (set *threadSafeSet) IsSuperset(other Set) bool {
 return other.IsSubset(set)
}
func (set *threadSafeSet) IsProperSuperset(other Set) bool {
 return other.IsProperSubset(set)
}
func (set *threadSafeSet) Union(other Set) Set {
 o := other.(*threadSafeSet)
 set.RLock()
 o.RLock()
 unsafeUnion := set.s.Union(&o.s).(*threadUnsafeSet)
 ret := &threadSafeSet{s: *unsafeUnion}
 set.RUnlock()
 o.RUnlock()
 return ret
}
func (set *threadSafeSet) Intersect(other Set) Set {
 o := other.(*threadSafeSet)
 set.RLock()
 o.RLock()
 unsafeIntersection := set.s.Intersect(&o.s).(*threadUnsafeSet)
 ret := &threadSafeSet{s: *unsafeIntersection}
 set.RUnlock()
 o.RUnlock()
 return ret
}
func (set *threadSafeSet) Difference(other Set) Set {
 o := other.(*threadSafeSet)
 set.RLock()
 o.RLock()
 unsafeDifference := set.s.Difference(&o.s).(*threadUnsafeSet)
 ret := &threadSafeSet{s: *unsafeDifference}
 set.RUnlock()
 o.RUnlock()
 return ret
}
func (set *threadSafeSet) SymmetricDifference(other Set) Set {
 o := other.(*threadSafeSet)
 set.RLock()
 o.RLock()
 unsafeDifference := set.s.SymmetricDifference(&o.s).(*threadUnsafeSet)
 ret := &threadSafeSet{s: *unsafeDifference}
 set.RUnlock()
 o.RUnlock()
 return ret
}
func (set *threadSafeSet) Clear() {
 set.Lock()
 set.s = newThreadUnsafeSet()
 set.Unlock()
}
func (set *threadSafeSet) Remove(i interface{}) {
 set.Lock()
 delete(set.s, i)
 set.Unlock()
}
func (set *threadSafeSet) Cardinality() int {
 set.RLock()
 defer set.RUnlock()
 return len(set.s)
}
func (set *threadSafeSet) Each(cb func(interface{}) bool) {
 set.RLock()
 for elem := range set.s {
 if cb(elem) {
 break
 }
 }
 set.RUnlock()
}
func (set *threadSafeSet) Iter() <-chan interface{} {
 ch := make(chan interface{})
 go func() {
 set.RLock()
 for elem := range set.s {
 ch <- elem
 }
 close(ch)
 set.RUnlock()
 }()
 return ch
}
func (set *threadSafeSet) Iterator() *Iterator {
 iterator, ch, stopCh := newIterator()
 go func() {
 set.RLock()
 L:
 for elem := range set.s {
 select {
 case <-stopCh:
 break L
 case ch <- elem:
 }
 }
 close(ch)
 set.RUnlock()
 }()
 return iterator
}
func (set *threadSafeSet) Equal(other Set) bool {
 o := other.(*threadSafeSet)
 set.RLock()
 o.RLock()
 ret := set.s.Equal(&o.s)
 set.RUnlock()
 o.RUnlock()
 return ret
}
func (set *threadSafeSet) Clone() Set {
 set.RLock()
 unsafeClone := set.s.Clone().(*threadUnsafeSet)
 ret := &threadSafeSet{s: *unsafeClone}
 set.RUnlock()
 return ret
}
func (set *threadSafeSet) String() string {
 set.RLock()
 ret := set.s.String()
 set.RUnlock()
 return ret
}
func (set *threadSafeSet) PowerSet() Set {
 set.RLock()
 unsafePowerSet := set.s.PowerSet().(*threadUnsafeSet)
 set.RUnlock()
 ret := &threadSafeSet{s: newThreadUnsafeSet()}
 for subset := range unsafePowerSet.Iter() {
 unsafeSubset := subset.(*threadUnsafeSet)
 ret.Add(&threadSafeSet{s: *unsafeSubset})
 }
 return ret
}
func (set *threadSafeSet) Pop() interface{} {
 set.Lock()
 defer set.Unlock()
 return set.s.Pop()
}
func (set *threadSafeSet) CartesianProduct(other Set) Set {
 o := other.(*threadSafeSet)
 set.RLock()
 o.RLock()
 unsafeCartProduct := set.s.CartesianProduct(&o.s).(*threadUnsafeSet)
 ret := &threadSafeSet{s: *unsafeCartProduct}
 set.RUnlock()
 o.RUnlock()
 return ret
}
func (set *threadSafeSet) ToSlice() []interface{} {
 keys := make([]interface{}, 0, set.Cardinality())
 set.RLock()
 for elem := range set.s {
 keys = append(keys, elem)
 }
 set.RUnlock()
 return keys
}
func (set *threadSafeSet) MarshalJSON() ([]byte, error) {
 set.RLock()
 b, err := set.s.MarshalJSON()
 set.RUnlock()
 return b, err
}
func (set *threadSafeSet) UnmarshalJSON(p []byte) error {
 set.RLock()
 err := set.s.UnmarshalJSON(p)
 set.RUnlock()
 return err
}

图片描述

源码来自:https://github.com/deckarep/g...

本文来自:Segmentfault

感谢作者:李说的对

查看原文:golang练手小项目系列(6)-使用map实现set

• 编辑
• 预览