golang源码阅读之实现set操作

桃扇骨 2022-11-26 08:56 172阅读 0赞

# set.go #

package main
    
    type Set interface {
        
    	// 向集合添加元素。返回是否已添加项。
    	Add(i interface{
        }) bool
    
    	// 返回集合中的元素数
    	Cardinality() int
    
    	// 从集合中移除所有元素，保留空集。
    	Clear()
    
    	// 使用相同的实现返回集合的克隆，复制所有键
    	Clone() Set
    
    	// 返回给定项是否都在集合中。
    	Contains(i ...interface{
        }) bool
    
    	// curr ={1，2，3，4，5}  other ={1，2，3，10}，    curr.Difference(other) = {4, 5}
    	//请注意，Difference的参数必须与方法的接收方的类型相同。否则，panic。。
    	Difference(other Set) Set
    
    	// 确定两个集合是否相等。如果它们具有相同的基数并包含相同的元素，则它们被认为是相等的。元素的添加顺序无关紧要。
    	//请注意，Equal的参数必须与方法的接收方具有相同的类型。否则，panic。
    	Equal(other Set) bool
    
    	// 返回一个新集合，该集合只包含两个集合中存在的元素
    	//请注意，Intersect的参数必须与方法的接收方具有相同的类型。否则，panic。
    	Intersect(other Set) Set
    
    	// 确定此集合中的每个元素是否都在另一个集合中，但这两个集合不相等。
    	//请注意，IsProperSubset的参数必须与方法的接收方具有相同的类型。否则，panic。
    	IsProperSubset(other Set) bool
    
    	// 确定另一个集合中的每个元素是否在此集合中，但两个集合Equal。
    	//请注意，IsProperSuperset的参数必须与方法的接收方具有相同的类型。否则，panic。
    	IsProperSuperset(other Set) bool
    
    	// 确定此集合中的每个元素是否都在另一个集合中。
    	//请注意，IsSubset的参数必须与方法的接收方具有相同的类型。否则，panic。
    	IsSubset(other Set) bool
    
    	//确定另一个集合中的每个元素是否在此集合中。
    	//请注意，IsSuperset的参数必须与方法的接收方具有相同的类型。否则，panic。
    	IsSuperset(other Set) bool
    
    	//迭代元素并对每个元素执行传递的func。如果传递的func返回true，则此时停止迭代。
    	Each(func(interface{
        }) bool)
    
    	// 返回可以range over的元素通道。
    	Iter() <-chan interface{
        }
    
    	//返回一个迭代器对象，您可以使用该对象对集合range over。
    	Iterator() *Iterator
    
    	// 从集合中删除一个元素
    	Remove(i interface{
        })
    
    	// Provides a convenient string representation
    	// of the current state of the set.
    	String() string
    
    	// 返回一个新集合，其中包含此集合或另一个集合中的所有元素，但不在这两个集合中。
    	//请注意，SymmetricDifference的参数必须与方法的接收方具有相同的类型。否则，panic。
    	SymmetricDifference(other Set) Set
    
    	// 并集
    	//
    	//请注意，Union的参数必须与方法的接收方具有相同的类型。否则，panic。
    	Union(other Set) Set
    
    	//Pop从集合中移除任意项, 并返回删除的元素。
    	Pop() interface{
        }
    
    	// 返回给定集（幂集）的所有子集。.
    	PowerSet() Set
    
    	// 返回两个集合的笛卡尔积。
    	// 假设集合A={a, b}，集合B={0, 1, 2}，则两个集合的笛卡尔积为{(a, 0), (a, 1), (a, 2), (b, 0), (b, 1), (b, 2)}。
    	// 类似的例子有，如果A表示某学校学生的集合，B表示该学校所有课程的集合，则A与B的笛卡尔积表示所有可能的选课情况
    	CartesianProduct(other Set) Set
    
    	//将集合的成员作为切片返回。
    	ToSlice() []interface{
        }
    }
    
    func NewSet(s ...interface{
        }) Set  {
        
    	set := newThreadSafeSet()
    
    	for _, item := range s{
        
    		set.Add(item)
    	}
    
    	return &set
    }
    
    func NewSetFromSlice(s []interface{
        }) Set {
        
    	a := NewSet(s...)
    	return a
    }
    
    func NewSetWith(elts ...interface{
        }) Set  {
        
    	return NewSetFromSlice(elts)
    }
    
    func NewThreadUnsafeSet() Set {
        
    	set := newThreadUnsafeSet()
    	return &set
    }
    
    func NewThreadUnsafeSetFromSlice(s []interface{
        }) Set {
        
    	a := NewThreadUnsafeSet()
    	for _, item := range s {
        
    		a.Add(item)
    	}
    	return a
    }

# threadUnsafeSet.go #

package main
    
    import (
    	"bytes"
    	"encoding/json"
    	"fmt"
    	"strings"
    )
    
    type threadUnsafeSet map[interface{
        }]struct{
        }
    
    func newThreadUnsafeSet() threadUnsafeSet {
        
    	return make(threadUnsafeSet)
    }
    
    // 添加元素到set中
    func (set *threadUnsafeSet)Add(i interface{
        }) bool  {
        
    	_, found := (*set)[i]
    	if found {
         //如果已经有了
    		return false // /False if it existed already
    	}
    
    	(*set)[i] = struct{
        }{
        }
    	return true
    }
    
    
    //set 是否包含 i： 只要有一个不在set中就会返回false
    func (set *threadUnsafeSet)Contains(i ... interface{
        }) bool  {
        
    	for _, v := range i{
        
    		if _, ok := (*set)[v]; !ok{
         //只要有一个不存在就返回false
    			return false
    		}
    	}
    	return true
    }
    
    // 删除任意一个成员，并且返回这个成员变量
    func (set *threadUnsafeSet) Pop() interface{
        } {
        
    	for item := range *set {
        
    		delete(*set, item)
    		return item
    	}
    	return nil
    }
    
    // 转为string
    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, ","))
    }
    
    // 转为切片
    func (set *threadUnsafeSet) ToSlice() []interface{
        } {
        
    	keys := make([]interface{
        }, 0, set.Cardinality())
    	for elem := range *set{
        
    		keys = append(keys, elem)
    	}
    	return keys
    }
    
    // 成员个数
    func (set *threadUnsafeSet) Cardinality() int {
        
    	return len(*set)
    }
    
    
    // 清除全部成员
    func (set *threadUnsafeSet) Clear() {
        
    	*set = newThreadUnsafeSet()
    }
    
    
    
    // 开辟一个set，里面克隆了当前set的所有key，并且返回这个set
    func (set *threadUnsafeSet)Clone() Set {
        
    	clonedSet := newThreadUnsafeSet()
    	for _, v := range *set{
        
    		clonedSet[v] = v
    	}
    	return &clonedSet
    }
    
    // 当前set和参数set中的成员变量是否完全一样
    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
    }
    
    // 删除 i成员
    func (set *threadUnsafeSet) Remove(i interface{
        }) {
        
    	delete(*set, i)
    }
    
    // 返回两个set的并集
    // curr = {1, 2, 3}, other = {1, 2, 4, 5}  curr.Union(set) = {1, 2, 3, 4, 5}
    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
    }
    
    
    // curr ={1，2，3，4，5}  other ={1，2，3，10}，    curr.Difference(other) = {4, 5}
    func (set *threadUnsafeSet) Difference(other Set) Set {
        
    	_ = other.(*threadUnsafeSet)
    
    	difference := newThreadUnsafeSet()
    	for elem := range *set {
        
    		if !other.Contains(elem) {
        
    			difference.Add(elem)
    		}
    	}
    	return &difference
    }
    
    // curr ={1，2，3，4，5}  other ={1，2，3，10}，    curr.SymmetricDifference(other) = {4, 5, 10}
    func (set *threadUnsafeSet) SymmetricDifference(other Set) Set {
        
    	_ = other.(*threadUnsafeSet)
    
    	aDiff := set.Difference(other)
    	bDiff := other.Difference(set)
    	return aDiff.Union(bDiff)
    }
    
    
    // set是other的子集但是set的元素小于other
    func (set *threadUnsafeSet) IsProperSuperset(other Set) bool {
        
    	return set.IsSubset(other) && ! set.Equal(other)
    }
    
    
    // curr是不是other的子集
    // curr = {1, 2, 3}; other = {1, 2, 3, 4, 5}.  curr.IsSubset(&other) = 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
    }
    
    
    // curr是不是other的超集
    // curr = {1, 2, 3, 4, 5}; other = {1, 2, 3}.  curr.IsSuperset(&other) = true
    func (set *threadUnsafeSet) IsSuperset(other Set) bool {
        
    	return other.IsSubset(set)
    }
    
    // 求交集
    // curr = {1, 2, 3, 4, 5}; other = {1, 2, 3， 11， 12， 13， 14}.  curr.Intersect(&other) = {1， 2， 3}
    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操作，直到func()返回true或者遍历完成
    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) 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
    }
    
    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
    }
    
    
    
    
    
    
    
    func (set *threadUnsafeSet) PowerSet() Set {
        
    	panic("implement me")
    }
    
    
    func (set *threadUnsafeSet) IsProperSubset(other Set) bool {
        
    	return other.IsProperSubset(set)
    }
    
    
    type OrderedPair struct {
        
    	First interface{
        }
    	Second interface{
        }
    }
    
    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 (pair *OrderedPair) Equal(other OrderedPair) bool {
        
    	if pair.First == other.First &&
    		pair.Second == other.Second {
        
    		return true
    	}
    
    	return false
    }

# threadSafeSet #

package main
    
    import "sync"
    
    type threadSafeSet struct {
        
    	s threadUnsafeSet
    	sync.RWMutex
    }
    
    // 读写锁： 读共享、写独占
    //  写锁锁了， 那么其他线程对锁加读锁/写锁会阻塞
    //  读锁锁了： 其他线程对锁加写锁会阻塞，加读锁会成功
    
    
    // map是非线程安全的 ，所以必修锁
    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
    }