Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

proposal: typed unordered set type #22812

Closed
pciet opened this issue Nov 19, 2017 · 1 comment
Closed

proposal: typed unordered set type #22812

pciet opened this issue Nov 19, 2017 · 1 comment

Comments

@pciet
Copy link
Contributor

pciet commented Nov 19, 2017

Using map[type]struct{} is one way to represent a typed unordered set, although the profiling article (https://blog.golang.org/profiling-go-programs) from 2011 indicated that slices can be a more efficient representation. A typed unordered set type could be a useful reference type alongside map and slice and save some effort.

type PointSet set[Point]

func (p PointSet) ChessBoard() Board {
	b := NewBoard()
	for point := range p {
		b[point.Address.Index()] = point
	}
	return b
}

var TestPointSet = PointSet{
	{
		Address: {0, 1},
		Piece: &Piece{
			Kind: Pawn,
			Orientation: White,
		},
	},
	{
		Address: {4, 0},
		Piece: &Piece{
			Kind: King,
			Orientation: White,
		},
	},
	{
		Address: {4, 7},
		Piece: &Piece{
			Kind: King,
			Orientation: Black,
		},
	},
}

func addPawn() {
	TestPointSet = combine(TestPointSet, PointSet{
		{
			Address: {0, 2},
			Piece: &Piece{
				Kind: Pawn,
				Orientation: White,
			},
		},
	})
}

func addSets() {
	TestPointSet = combine(TestPointSet, set0, set1, set2, set3)
}

type Path []Point
type PathSet set[*Path] // slices cannot be compared for equality so use a pointer here
type IntSet set[int]

var TestIntSet = IntSet{0, 1, 2, 2, 3}

func reduceTestIntSet() {
	fmt.Println(TestIntSet)
	fmt.Println(reduce(TestIntSet))
}

> 3 2 1 0 2
> 0 3 2 1

func doesTestIntSetHave4() {
	fmt.Println(has(TestIntSet, 4))
}

> false

var TestIntSet2 = IntSet{3, 2, 1, 2, 0}

func areTestIntSetsEqual() {
	fmt.Println(equal(TestIntSet, TestIntSet2))
}

> true

var TestIntSet3 = IntSet{0, 1, 2, 3}

func testIntSetDifference() {
	newSet := diff(TestIntSet, TestIntSet3)
	fmt.Println(newSet)
}

> 2

This proposal includes the type set representing an unordered set of same-typed items, a simplified range operator for sets (with only one assigned variable), and the related built-in functions add(set, element) set, combine(sets…) set, reduce(set) set, has(set, element) bool, equal(sets…) bool, diff(setA, setB) set, and set.String() string. Other functions may be useful such as count(set, item) uint, but these are the ones I’ve needed so far. append could be overloaded instead of having add, and delete(set, element) set is probably necessary.

For me it would be nice to not have messy statements like paths[&path] = struct{}{} and perhaps there could be some shared performance gain behind the implementation, but writing these set functions as methods on a type (either map or slice) is not a significant effort now. But almost from the start of working with Go I was reaching for an unordered set type.

@gopherbot gopherbot added this to the Proposal milestone Nov 19, 2017
@bradfitz
Copy link
Contributor

Dup of #7088.
But probably also of #15292

@golang golang locked and limited conversation to collaborators Nov 20, 2018
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests

3 participants