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

golang练手小项目系列(6)-使用map实现set问题描述go没有提供set数据结构,请用map实现set要点需要支持方法:Add添加元素Remove删除元素Cardinality获取Set长度Clear清空SetContains检测元素是否在Set中Pop()随机删除一个元素并返回被删除的元素ToSlice()[]interface{}转换成slice返回拓展Clone复制SetDi…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

问题描述

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
}

Jetbrains全家桶1年46,售后保障稳定

源码来自:https://github.com/deckarep/golang-set

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/223043.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 【js】Input事件

    【js】Input事件InputEvent常用事件触发的先后顺序如下:1keydown2keypress3textInput4input5keyupkeydown,keyup1全部浏览器支持2当用户按下/释放键盘上的任意键时触发3event.keyCode,返回键盘上按键对应的特定键码(兼容性:分号在Firefox,Opera上返回的是ASC

  • 计算机网络重点回顾

    计算机网络一.计算机网络概述计算机网络的概念:(*)1.计算机网络的定义:​ 计算机网络是指将地理位置不同的具有独立功能的多台计算机及其外部设备,通过通信线路链接起来,在网络操作系统,网络管理软件及网络通信协议的管理和协调下,实现资源共享和信息传递的计算机系统。2.计算机网络的组成:终端系统/资源子网:提供共享的软件资源和硬件资源通信子网:提供信息交换的网络结点和通信线路。3.计算机网络的类型:按照拓朴分类:星型结构树形结构总线型结构环形结构网状结构按照范围分

  • v3S驱动gt911触摸「建议收藏」

    v3S驱动gt911触摸「建议收藏」文章目录一、修改设备树二、编写驱动三、运行测试四、编译进内核1.拷贝文件2.修改对应的Makefile3.编译运行4.测试1.注释掉坐标信息五、移植tslib1.buildroot配置tslib2.配置tslib3.测试一、修改设备树在sun8i-v3s-licheepi-zero-dock.dts中添加pio节点(其实经过测试不添加也是可以的,后面会说)&pio{ /*按键*/ key_pins:key_pins@0{ pins=”PG2″;

  • sparkSQL实例_flink sql

    sparkSQL实例_flink sql记一次SparkSqlETL过程需求:1)input:json日志2)ETL:根据IP解析出省份,城市3)stat:地区分布指标计算,满足条件的才算,满足条件的赋值为1,不满足的赋值为0(如下图)将统计结果写入MySQL中。(就比如说这个广告请求要满足requestmode=1和processnode=3这两个条件)valspark=SparkSessi…

    2022年10月29日
  • Ubuntu18.04 安装 Idea 2018.2 Ultimate[通俗易懂]

    Ubuntu18.04 安装 Idea 2018.2 Ultimate[通俗易懂]Ubuntu18.04Idea

  • pycharm怎么配置python环境anaconda_pycharm环境变量配置Anaconda

    pycharm怎么配置python环境anaconda_pycharm环境变量配置AnacondaPyCharm是一款很好用很流行的python编辑器。Anaconda是专注于数据分析的Python发行版本,包含了conda、Python等190多个科学包及其依赖项。Anaconda通过管理工具包、开发环境、Python版本,大大简化了你的工作流程。不仅可以方便地安装、更新、卸载工具包,而且安装时能自动安装相应的依赖包,同时还能使用不同的虚拟环境隔离不同要求的项目。anaconda自带集成开发…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号