create a Set type that extends the two existing Set implementations w…

…ith many new methods (#8) * add a set type that extends existing set types with lots of functionality * slight cleanup Co-authored-by: Dan <dan@null>
zyedidia · Aug 19, 2022 · 38f713d · 38f713d
1 parent ae83fa5
commit 38f713d
Show file tree

Hide file tree

Showing 2 changed files with 303 additions and 0 deletions.
diff --git a/set/set.go b/set/set.go
@@ -0,0 +1,189 @@
+package set
+
+import (
+	"fmt"
+	"sort"
+
+	"github.com/zyedidia/generic"
+	"github.com/zyedidia/generic/hashset"
+	"github.com/zyedidia/generic/mapset"
+)
+
+func NewMapset[K comparable](in ...K) Set[K] {
+	con := func() SetOf[K] { return mapset.New[K]() }
+	set := NewSet(con, in...)
+	return set
+}
+
+func NewHashset[K comparable](cap uint64, equals generic.EqualsFn[K], hash generic.HashFn[K], in ...K) Set[K] {
+	con := func() SetOf[K] { return hashset.New(cap, equals, hash) }
+	set := NewSet(con, in...)
+	return set
+}
+
+func NewSet[K comparable, S func() SetOf[K]](con S, in ...K) Set[K] {
+	set := con()
+	for _, v := range in {
+		set.Put(v)
+	}
+	return Set[K]{
+		new:   con,
+		SetOf: set,
+	}
+}
+
+type SetOf[K comparable] interface {
+	Put(val K)
+	Has(val K) bool
+	Remove(val K)
+	Size() int
+	Each(fn func(key K))
+}
+
+type Set[K comparable] struct {
+	SetOf[K]
+	new func() SetOf[K]
+}
+
+func (s Set[K]) Intersection(others ...SetOf[K]) Set[K] {
+	return s.Clone().InPlaceIntersection(others...)
+}
+func (s Set[K]) Difference(others ...SetOf[K]) Set[K] {
+	return s.Clone().InPlaceDifference(others...)
+}
+func (s Set[K]) Union(others ...SetOf[K]) Set[K] {
+	return s.Clone().InPlaceUnion(others...)
+}
+
+func (s Set[K]) ConstSymmetricDifference(with ...K) Set[K] {
+	return s.SymmetricDifference(NewSet(s.new, with...))
+}
+func (s Set[K]) ConstIntersection(with ...K) Set[K] {
+	return s.Clone().InPlaceIntersection(NewSet(s.new, with...))
+}
+func (s Set[K]) ConstDifference(with ...K) Set[K] {
+	return s.Clone().InPlaceDifference(NewSet(s.new, with...))
+}
+func (s Set[K]) ConstUnion(with ...K) Set[K] {
+	return s.Clone().InPlaceUnion(NewSet(s.new, with...))
+}
+
+func (s Set[K]) Clone() Set[K] {
+	new := NewSet(s.new)
+	s.Each(func(key K) { new.Put(key) })
+	return new
+}
+
+func (s Set[K]) String() string {
+	out := make([]string, 0, s.Size())
+	s.Each(func(key K) { out = append(out, fmt.Sprintf(`%v`, key)) })
+	sort.Strings(out)
+	return fmt.Sprintf("%v", out)
+}
+
+func (s Set[K]) Map() map[K]struct{} {
+	out := make(map[K]struct{}, s.Size())
+	s.Each(func(key K) {
+		out[key] = struct{}{}
+	})
+	return out
+}
+
+func (s Set[K]) SymmetricDifference(others ...SetOf[K]) Set[K] {
+	new := s.Clone()
+	seen := new.Clone()
+	for _, other := range others {
+		other.Each(func(key K) {
+			if seen.Has(key) {
+				new.Remove(key)
+				return
+			}
+			new.Put(key)
+			seen.Put(key)
+		})
+	}
+	return new
+}
+
+func (s Set[K]) InPlaceIntersection(others ...SetOf[K]) Set[K] {
+	for _, other := range others {
+		s.Each(func(key K) {
+			if !other.Has(key) {
+				s.Remove(key)
+			}
+		})
+	}
+	return s
+}
+
+func (s Set[K]) InPlaceDifference(others ...SetOf[K]) Set[K] {
+	for _, other := range others {
+		other.Each(func(key K) {
+			s.Remove(key)
+		})
+	}
+	return s
+}
+
+func (s Set[K]) InPlaceUnion(others ...SetOf[K]) Set[K] {
+	for _, other := range others {
+		other.Each(func(key K) {
+			s.Put(key)
+		})
+	}
+	return s
+}
+
+func (s Set[K]) Keys() []K {
+	out := make([]K, 0, s.Size())
+	s.Each(func(key K) {
+		out = append(out, key)
+	})
+	return out
+}
+
+func (s Set[K]) IsDisjoint(other SetOf[K]) bool {
+	// TODO: maybe optimize?
+	return s.Intersection(other).Size() > 0
+}
+
+func (s Set[K]) IsSubset(of SetOf[K]) bool {
+	subset := true
+	s.Each(func(key K) {
+		if !of.Has(key) {
+			subset = false
+		}
+	})
+	return subset
+}
+
+func (s Set[K]) IsSuperset(of SetOf[K]) bool {
+	superset := true
+	of.Each(func(key K) {
+		if !s.Has(key) {
+			superset = false
+		}
+	})
+	return superset
+}
+
+func (s Set[K]) Equal(to SetOf[K]) bool {
+	if s.Size() != to.Size() {
+		return false
+	}
+	return s.Union(to).Size() == s.Size()
+}
+
+func (s Set[K]) IsProperSubset(to SetOf[K]) bool {
+	if s.Equal(to) {
+		return false
+	}
+	return s.IsSubset(to)
+}
+
+func (s Set[K]) IsProperSuperset(to SetOf[K]) bool {
+	if s.Equal(to) {
+		return false
+	}
+	return s.IsSuperset(to)
+}
diff --git a/set/set_test.go b/set/set_test.go
@@ -0,0 +1,114 @@
+package set
+
+import (
+	"fmt"
+	"sort"
+	"testing"
+
+	"github.com/zyedidia/generic"
+)
+
+func ExampleSet_ConstUnion() {
+	fmt.Print(NewMapset(1, 4, 7).ConstUnion(2, 3, 5, 6))
+	// Output: [1 2 3 4 5 6 7]
+}
+
+func ExampleSet_ConstDifference() {
+	fmt.Print(NewMapset(1.2, 1.8, 2.6, 3.5).ConstDifference(1.2, 2.6))
+	// Output: [1.8 3.5]
+}
+
+func ExampleSet_ConstIntersection() {
+	fmt.Print(NewMapset("a", "b", "c").ConstIntersection("b", "c", "e"))
+	// Output: [b c]
+}
+
+func ExampleSet_ConstSymmetricDifference() {
+	fmt.Print(NewMapset(1, 2, 3).ConstSymmetricDifference(2, 3, 4))
+	// Output: [1 4]
+}
+
+func ExampleSet_SymmetricDifference() {
+	one := NewMapset(2, 3, 4)
+	two := NewMapset(4, 5, 6)
+	fmt.Print(NewMapset(1, 2, 3).SymmetricDifference(one, two))
+	// Output: [1 5 6]
+}
+
+func ExampleSet_Union() {
+	one := NewMapset(2, 3, 4)
+	two := NewMapset(4, 5, 6)
+	fmt.Print(NewMapset(1, 2, 3).Union(one, two))
+	// Output: [1 2 3 4 5 6]
+}
+
+func ExampleSet_InPlaceIntersection() {
+	one := NewMapset(2, 3, 4)
+	two := NewMapset(4, 5, 6)
+	one.InPlaceIntersection(two)
+	fmt.Print(one)
+	// Output: [4]
+}
+
+func ExampleSet_Keys() {
+	keys := NewMapset("one", "two").Keys()
+	sort.Strings(keys)
+	fmt.Println(keys)
+	// Output:
+	// [one two]
+}
+
+func ExampleSet_Intersection() {
+	s := NewMapset(1, 4, 7)
+	o := NewHashset(1, generic.Equals[int], generic.HashInt, 1, 7)
+	inter := s.Intersection(o)
+
+	fmt.Println(inter)
+	fmt.Printf("%T", inter.SetOf) // the same type as the receiver
+	// Output:
+	// [1 7]
+	// mapset.Set[int]
+}
+
+func ExampleSet_Difference() {
+	s := NewHashset(1, generic.Equals[int], generic.HashInt, 3, 4, 5, 6, 7)
+	o := NewMapset(5)
+	diff := s.Difference(o)
+
+	fmt.Println(diff)
+	fmt.Printf("%T", diff.SetOf) // the same type as the receiver
+	// Output:
+	// [3 4 6 7]
+	// *hashset.Set[int]
+}
+
+func TestSetTypes(t *testing.T) {
+	type something struct{ string }
+	set := NewMapset(something{"hello"}, something{"world"})
+	if !set.Has(something{"hello"}) {
+		t.Errorf(`set is missing a value`)
+	}
+	if set.Has(something{"mystery"}) {
+		t.Errorf(`set has an unexpected value`)
+	}
+}
+
+func FuzzDifference(f *testing.F) {
+	f.Fuzz(func(t *testing.T, needle, hay1, hay2 int) {
+		found := needle == hay1 || needle == hay2
+		search := NewMapset(hay1, hay2)
+		initialize := search.Size()
+
+		diff := search.Difference(NewMapset(needle))
+		t.Logf("diff %d,%d - %d: %v", hay1, hay2, needle, diff.Keys())
+		if found != (diff.Size() < initialize) {
+			t.Error("unexpected result from diff")
+		}
+
+		inter := search.Intersection(NewMapset(needle))
+		t.Logf("inter %d,%d + %d: %v", hay1, hay2, needle, diff.Keys())
+		if found == (inter.Size() == 0) {
+			t.Error("unexpected result from inter")
+		}
+	})
+}