How to implement a simple set data structure in golang

set.go

type Set struct {
	list map[int]struct{} //empty structs occupy 0 memory
}

func (s *Set) Has(v int) bool {
	_, ok := s.list[v]
	return ok
}

func (s *Set) Add(v int) {
	s.list[v] = struct{}{}
}

func (s *Set) Remove(v int) {
	delete(s.list, v)
}

func (s *Set) Clear() {
	s.list = make(map[int]struct{})
}

func (s *Set) Size() int {
	return len(s.list)
}

func NewSet() *Set {
	s := &Set{}
	s.list = make(map[int]struct{})
	return s
}

//optional functionalities

//AddMulti Add multiple values in the set
func (s *Set) AddMulti(list ...int) {
	for _, v := range list {
		s.Add(v)
	}
}

type FilterFunc func(v int) bool

// Filter returns a subset, that contains only the values that satisfies the given predicate P
func (s *Set) Filter(P FilterFunc) *Set {
	res := NewSet()
	for v := range s.list {
		if P(v) == false {
			continue
		}
		res.Add(v)
	}
	return res
}

func (s *Set) Union(s2 *Set) *Set {
	res := NewSet()
	for v := range s.list {
		res.Add(v)
	}

	for v := range s2.list {
		res.Add(v)
	}
	return res
}

func (s *Set) Intersect(s2 *Set) *Set {
	res := NewSet()
	for v := range s.list {
		if s2.Has(v) == false {
			continue
		}
		res.Add(v)
	}
	return res
}

// Difference returns the subset from s, that doesn't exists in s2 (param)
func (s *Set) Difference(s2 *Set) *Set {
	res := NewSet()
	for v := range s.list {
		if s2.Has(v) {
			continue
		}
		res.Add(v)
	}
	return res
}

usage.go

mySet := NewSet()
fmt.Println("has 5", mySet.Has(5)) //false
mySet.Add(5)
fmt.Println("has 5", mySet.Has(5)) //true
mySet.Remove(5)
fmt.Println("has 5", mySet.Has(5)) //false

mySet.AddMulti(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

p := func(v int) bool { return v >= 5 }
subSet := mySet.Filter(p)
fmt.Println("all >= 5", subSet)

Great work! Another option would be to add an alias to the map type as opposed to wrapping it into a struct
type set map[int]struct{}

That way you don't have to do set.list you can jsut use set as the map directly!

Every time I see you can't implement range on a custom type, it makes me sad :(

True, that's why I usually make them aliases. If set is an alias of map we can remove most of the methods as well and use normal delete, len and add operations.

On Wed, Aug 28, 2019, at 21:58, Darrien Glasser wrote: Every time I see you can't implement range on a custom type, it makes me sad :( — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <https://gist.github.com/cb8b9344d9c66571ef331a14eb7a2e80?email_source=notifications&email_token=AAGKUMIOUHID2BAT7KI5W53QG3DHFA5CNFSM4IRQAHOKYY3PNVWWK3TUL52HS4DFVNDWS43UINXW23LFNZ2KUY3PNVWWK3TUL5UWJTQAFXYUS#gistcomment-3010889>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAGKUMPW5BE7BRMTHGSCSJ3QG3DHFANCNFSM4IRQAHOA>.

/*******************************/ ⚛ Bledea-Georgescu Adrian 🖧 Sofware Engineer ✍ https://coder.today 📧 [email protected] 🖥 github.com/bgadrian 💁 linkedin.com/in/bgadrian <https://www.linkedin.com/in/bgadrian/>

I am not clear whether you said you prefer to use the alias, but can't due to limitations. So I am adding my two cents here.

type Set map[int]bool

func (s *Set) Add(val int) {
	(*s)[val] = true
}

(*s)[val] = true

You can use the same Set instead of creating a new Set

Tests

import "testing"

func TestSet_Add(t *testing.T) {
	type args struct {
		val int
	}
	tests := []struct {
		name string
		s    Set
		args args
		wantCount int
	}{
		{name: "AddOne", s: Set{'s': true}, args: args{val: 'p'}, wantCount: 2},
	}
	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			tt.s.Add(tt.args.val)
			if len(tt.s) != tt.wantCount {
				t.Errorf("wanted to have %v, got %v", tt.wantCount, len(tt.s))
			}
		})
	}
}

func (s *Set) iter() []int {
var keys []int
for k, _ := range s.list {
keys = append(keys, k)
}
return keys
}

and
for _, v := range mySet.iter() {
fmt.Println(v)
}

would be a nice addition

Thanks for this. I've modified it to be generic:

package set

type Set[T comparable] struct {
	list map[T]struct{} //empty structs occupy 0 memory
}

func (s *Set[T]) Has(v T) bool {
	_, ok := s.list[v]
	return ok
}

func (s *Set[T]) Add(v T) {
	s.list[v] = struct{}{}
}

func (s *Set[T]) Remove(v T) {
	delete(s.list, v)
}

func (s *Set[T]) Clear() {
	s.list = make(map[T]struct{})
}

func (s *Set[T]) Size() int {
	return len(s.list)
}

func NewSet[T comparable]() *Set[T] {
	s := &Set[T]{}
	s.list = make(map[T]struct{})
	return s
}

// AddMulti Add multiple values in the set
func (s *Set[T]) AddMulti(list ...T) {
	for _, v := range list {
		s.Add(v)
	}
}

type FilterFunc[T comparable] func(v T) bool

// Filter returns a subset, that contains only the values that satisfies the given predicate P
func (s *Set[T]) Filter(P FilterFunc[T]) *Set[T] {
	res := &Set[T]{}
	res.list = make(map[T]struct{})
	for v := range s.list {
		if !P(v) {
			continue
		}
		res.Add(v)
	}
	return res
}

func (s *Set[T]) Union(s2 *Set[T]) *Set[T] {
	res := NewSet[T]()
	for v := range s.list {
		res.Add(v)
	}

	for v := range s2.list {
		res.Add(v)
	}
	return res
}

func (s *Set[T]) Intersect(s2 *Set[T]) *Set[T] {
	res := NewSet[T]()
	for v := range s.list {
		if !s2.Has(v) {
			continue
		}
		res.Add(v)
	}
	return res
}

// Difference returns the subset from s, that doesn't exists in s2 (param)
func (s *Set[T]) Difference(s2 *Set[T]) *Set[T] {
	res := NewSet[T]()
	for v := range s.list {
		if s2.Has(v) {
			continue
		}
		res.Add(v)
	}
	return res
}