set

Educating myself about making generic sets in go. Attempting to match the python set API. For version 1.0, all methods are written in more or less the naive way. Elements of a set must be comparable. Comparable is an interface that is implemented by all comparable types (booleans, numbers, strings, pointers, channels, arrays of comparable types, structs whose fields are all comparable types).

The top level module, set, uses go's built in map to store the items of the set as keys, and an empty struct as the value. The sub-module bitset uses uint64s as the underlying container of bits, and it keeps track of which continuous set of 64 integers that uint64 represents with a key telling if it is positive, and how many multiples of 64 it is along the numberline.

API

package main

import (
	"fmt"

	"github.com/natemcintosh/set"
)

func main() {
	// The input slice (notice the duplicates)
	raw_data_1 := []int{1, 2, 1, 4, 5, 6, 6, 6, 7}
	// Create the Set
	s1 := set.NewSet(raw_data_1)
	// See that duplicate values no longer exist
	fmt.Println(s1)
	// {5, 6, 7, 1, 2, 4}

	// Check if an item exists in the set
	if s1.Contains(10) {
		fmt.Println("10 is in the set")
	} else {
		fmt.Println("10 is not in the set")
		// 10 is not in the set
	}

	// How many items are in the set?
	fmt.Printf("The set has %v items\n", s1.Len())
	// The set has 6 items

	// Is the set empty?
	fmt.Printf("The set is empty: %t\n", s1.IsEmpty())
	// The set is empty: false

	// Add new items to the set
	s1.Add(3)
	s1.Add(10)
	s1.Add(1) // Does nothing since 1 already exists in the set

	// Remove items, and return an error if it doesn't exist
	err := s1.Remove(100)
	if err != nil {
		fmt.Println("The set did not have the item 100. Failed to remove it from the set.")
		// The set did not have the item 100. Failed to remove it from the set.
	}

	// Discard items, and don't worry about if it exists in the set or not
	s1.Discard(1)
	fmt.Printf("The set contains 1: %t\n", s1.Contains(1))
	// The set contains 1: false

	// Pop a random item from the set. Get an error if the set is empty
	item, err := s1.Pop()
	if err != nil {
		fmt.Printf("The set was empty")
	}
	fmt.Printf("The item popped from the set was: %v\n", item)
	// The item popped from the set was: 10

	// Clear all items from the set
	s1.Clear()
	fmt.Printf("The set is empty: %t\n", s1.IsEmpty())
	// The set is empty: true

	// Create a new set with capacity for 50 numbers. Useful if we know that this will
	// be filled up with at least that many items in the future.
	// Also note that we can pass in a type that has a slice as the underlying type.
	type some_floats []float64
	var numbers some_floats = []float64{1.0, 2.0, 3.14, 4.95}
	s2 := set.NewSetWithCapacity(numbers, 50)

	// Create a deep copy of s2
	s3 := s2.Copy()

	// Make `s3` a little different than `s2`
	s3.Discard(1.0)
	s3.Discard(2.0)
	s3.Add(5.67)
	s3.Add(-100.21)

	// Are the two sets equal?
	fmt.Printf("s2 equals s3?: %t\n", s2.Equals(s3))
	// s2 equals s3?: false

	// Note that we cannot compare two sets of different types
	// s1.Equals(s2)
	// Compile error:
	// cannot use s2 (variable of type set.Set[float64]) as type set.Set[int] in argument to s1.Equals

	// What's the union of the two sets
	union := s2.Union(s3)
	fmt.Printf("Created a new set (deep copy), containing: %v\n", union)
	// Created a new set (deep copy), containing: {3.14, 5.67, -100.21, 1, 2, 4.95}

	// Union, but update the set in place. This will be faster as it doesn't create a copy
	s2.UnionInPlace(s3)
	fmt.Printf("s2 has become: %v\n", s2)
	// s2 has become: {1, 2, 5.67, -100.21, 4.95, 3.14}

	// Recreate original `s2`
	s2 = set.NewSet(numbers)

	// What is the intersection of the two sets?
	intersection := s2.Intersection(s3)
	fmt.Printf("s2 intersection with s3 = %v\n", intersection)
	// s2 intersection with s3 = {4.95, 3.14}

	// IntersectionInPlace will update a set in place. Faster than Intersection
	s2.IntersectionInPlace(s3)
	fmt.Printf("s2 has become: %v\n", s2)
	// s2 has become: {3.14, 4.95}

	// Recreate original `s2`
	s2 = set.NewSet(numbers)

	s4 := set.NewSet([]float64{-10, -9})
	// Are the two sets disjoint? As in, are there no elements common to both?
	fmt.Printf("s2 has no common elements with s4? %t\n", s2.IsDisjoint(s4))
	// s2 has no common elements with s4? true

	s3 = s2.Copy()
	// Is `s3` a subset of `s2`?
	fmt.Printf("s3 is a subset of s2? %t\n", s3.IsSubsetOf(s2))
	// s3 is a subset of s2? true

	// Proper subset
	fmt.Printf("s3 is a proper subset of s2? %t\n", s3.IsProperSubsetOf(s2))
	// s3 is a proper subset of s2? false

	s3.Add(23.45)
	// Is `s3` a super set of `s2`
	fmt.Printf("s3 is a super set of s2? %t\n", s3.IsSuperSetOf(s2))
	// s3 is a super set of s2? true

	// Proper superset
	fmt.Printf("s3 is a proper super set of s2? %t\n", s3.IsProperSuperSetOf(s2))
	// s3 is a proper super set of s2? true

	// What is the difference of two sets
	taking_science := set.NewSet([]string{"Larry", "Curly", "Moe", "Shemp"})
	taking_math := set.NewSet([]string{"Curly", "Shemp", "Albert"})
	not_taking_math := taking_science.Difference(taking_math)
	fmt.Printf("The following students take science but not math: %v\n", not_taking_math)
	// The following students take science but not math: {Larry, Moe}

	// DifferenceInPlace is faster, but alters the original
	taking_science.DifferenceInPlace(taking_math)
	fmt.Printf("taking_science is now: %v\n", taking_science)
	// taking_science is now: {Larry, Moe}

	// Reset `taking_science`
	taking_science = set.NewSet([]string{"Larry", "Curly", "Moe", "Shemp"})

	// What is the symmetric difference? I.e. not in the intersection of the two
	sym_diff := taking_science.SymmetricDifference(taking_math)
	fmt.Printf("The following students are taking science or math, but not both: %v\n", sym_diff)
	// The following students are taking science or math, but not both: {Larry, Moe, Albert}

	// Once again, the in place version is faster, but alters the original
	taking_science.SymmetricDifferenceInPlace(taking_math)
	fmt.Printf("taking_science has become %v\n", taking_science)
	// taking_science has become {Larry, Moe, Albert}
}