Problem: You want to create a set data structure.
Solution: Wrap a struct around a map. Create set functions on the struct.
A set is an unordered data structure that has only unique elements. It implements the mathematical concept of a finite set and the operations around it. The basic functions associated with sets include:
Add
• Add a new element to the set.
Remove
• Remove an existing element from the set.
IsEmpty
• Check if the set is empty.
Size
• Get the size of the set.
Has
• Check if an element is a member of a given set.
Union
• Given two or more sets, the union of the sets is the set that consists of elements that are in any of those sets.
Intersection
• Given two or more sets, the intersection of sets is the set that consists of elements that are in all the sets.
Difference
• Given two sets A and B, the difference A – B consists of elements that are in set A but not set B.
IsSubset
• Given two sets A and B, check if every element in set B is in set A.
type Set struct { elements map [ any ] bool }
Map keys are unordered and are also unique so it’s no surprise that you implement Set with a map. In this implementation, the key is the element in the set, while you don’t care about the value at all.
However, because you’re using a map to represent a set, you need to use a separate function to create a new set. This is because maps need to be initialized before they can be used:
func NewSet () Set { return Set { elements : make ( map [ any ] bool )} }
func ( s * Set ) Add ( el any ) { s . elements [ el ] = false } func ( s * Set ) Remove ( el any ) { delete ( s . elements , el ) } func ( s * Set ) IsEmpty () bool { return s . Size () == 0 } func ( s * Set ) Size () int { return len ( s . elements ) } func ( s * Set ) List () ( list [] any ) { for k := range s . elements { list = append ( list , k ) } return } func ( s Set ) Has ( el any ) ( ok bool ) { _ , ok = s . elements [ el ] return } func ( s * Set ) Copy () ( u Set ) { u = NewSet () for k := range s . elements { u . Add ( k ) } return } func Union ( sets ... Set ) ( u Set ) { u = sets [ 0 ]. Copy () for _ , set := range sets [ 1 : len ( sets )] { for k := range set . elements { u . Add ( k ) } } return } func Intersect ( sets ... Set ) ( i Set ) { i = sets [ 0 ]. Copy () for k := range i . elements { for _ , set := range sets [ 1 : len ( sets )] { if ! set . Has ( k ) { i . Remove ( k ) } } } return } func ( s Set ) Difference ( t Set ) Set { for k := range t . elements { if s . Has ( k ) { delete ( s . elements , k ) } } return s } func ( s Set ) IsSubset ( t Set ) bool { for k := range s . elements { if ! t . Has ( k ) { return false } } return true }