Dwi Wahyudi

Senior Software Engineer (Ruby, Golang, Java)

In this post, let’s talk about using Go 1.18 generics feature to create a set data structure.

Overview

Set is just a list but with unique members/elements, which means we would’nt find any duplicate in it.

Before Go 1.18, without generics, we need to create different sets of methods for each data type. Set methods for string, set methods for int64, set methods for float64, and so on.

With generics now, it’s very simple, because we can parameterized the type.

Set Type Declaration

First, we’re going to declare the Set data type, here we create comparable. Let’s make a new package set.

package set

type set[T comparable] map[T]bool

Here we’re using map data type for storing our set members. Rather than slice, map is better since it is more performant when searching for the element.

What’s this comparable? It’s predeclared identifier.

tl;dr Any data type that can operate on comparison operators (==, !=, <, >, etc) will work just fine. Structs comparison will compare all fields of it.

Set Initializer

Now, let’s setup our set initializer function, we want to receive any comparable type, so here we go.

func New[T comparable]() set[T] {
	return make(set[T])
}

This method will return an empty map with specified data type.

Add Method

Now let’s create Add method for that Set type.

func (s set[T]) Add(values ...T) {
	for _, value := range values {
		s[value] = true
	}
}

Map data type will keep its key uniqueness. So adding duplicate data will ignore the duplicates.

IsMember Method

After Add method above, we would like to create a method to check whether a value is member of the set.

func (s set[T]) IsMember(value T) bool {
	_, ok := s[value]
	return ok
}

Delete Method

Delete method will remove a member from the set, return false if such member doesn’t exist.

func (s set[T]) Delete(value T) bool {
	if s.IsMember(value) {
		delete(s, value)
		return true
	} else {
		return false
	}
}

Len Method

This method can be used to check the length of the set.

func (s set[T]) Len() int {
	return len(s)
}

Members Method

And finally Members method will return all of set’s members.


func (s set[T]) Members() []T {
	members := make([]T, 0)
	for member := range s {
		members = append(members, member)
	}

	return members
}

Testing The Set Method

Let’s now make a unit test for that code, but in order to test a set of structs, let’s create a new package entity.

package entity

type Song struct {
	Title       string
	Artist      string
	ReleaseYear int16
}

And here’s the test functions:

package set_test

import (
	"go-test-set/entity"
	"go-test-set/set"
	"testing"

	"github.com/stretchr/testify/assert"
)

func TestInteger(t *testing.T) {
	intSet := set.New[int]()
	intSet.Add(4, 6, 10, 12, 18, 12)
	intSet.Delete(10)

	assert.Equal(t, intSet.Len(), 4)
	assert.True(t, intSet.IsMember(4))
	assert.ElementsMatch(t, intSet.Members(), []int{4, 6, 12, 18})
}

func TestString(t *testing.T) {
	stringSet := set.New[string]()
	stringSet.Add("burger", "softdrink", "pizza", "soto", "burger", "rendang")
	stringSet.Delete("ice cream")

	assert.Equal(t, stringSet.Len(), 5)
	assert.False(t, stringSet.IsMember("kebab"))
	assert.ElementsMatch(t, stringSet.Members(), []string{"burger", "softdrink", "pizza", "soto", "rendang"})
}

func TestStruct(t *testing.T) {
	songSet := set.New[entity.Song]()
	songSet.Add(entity.Song{Title: "Stayin' Alive", Artist: "Bee Gees", ReleaseYear: 1979})
	songSet.Add(entity.Song{Title: "Dancing Queen", Artist: "ABBA", ReleaseYear: 1976})
	songSet.Add(entity.Song{Title: "Blitzkrieg Bop", Artist: "Ramones", ReleaseYear: 1976})
	songSet.Add(entity.Song{Title: "Dancing Queen", Artist: "ABBA", ReleaseYear: 1976}) // will be ignored

	assert.Equal(t, songSet.Len(), 3)
	assert.True(t, songSet.IsMember(entity.Song{Title: "Blitzkrieg Bop", Artist: "Ramones", ReleaseYear: 1976}))
	assert.ElementsMatch(t, songSet.Members(), []entity.Song{
		{Title: "Stayin' Alive", Artist: "Bee Gees", ReleaseYear: 1979},
		{Title: "Dancing Queen", Artist: "ABBA", ReleaseYear: 1976},
		{Title: "Blitzkrieg Bop", Artist: "Ramones", ReleaseYear: 1976},
	})
}

With this unit test, we can verify that the set methods above with generics can receive any comparable data type (including struct which will be compared field by field).

comparable in Go has limitations, it’s not interface, we cannot implement it, so we can’t compare by specific field. If we want to sort a slice of structs based on a specific field, for now sort package is the way to go, https://pkg.go.dev/sort.