I have a DisjointSets data structure (pulled from Cormen), implemented in Go to work with int64.
type DisjointSets struct {
ranks map[int64]int64
p map[int64]int64
}
// New returns a new DisjointSets
func NewDisjointSets() *DisjointSets {
d := DisjointSets{map[int64]int64{}, map[int64]int64{}}
return &d
}
// MakeSet adds element x to the disjoint sets in its own set
func (d *DisjointSets) MakeSet(x int64) {
d.p[x] = x
d.ranks[x] = 0
}
// Link assigns x to y or vice versa, depending on the rank of each
func (d *DisjointSets) Link(x, y int64) {
if d.ranks[x] > d.ranks[y] {
d.p[y] = x
} else {
d.p[x] = y
if d.ranks[x] == d.ranks[y] {
d.ranks[y] += 1
}
}
}
// FindSet returns the set in which an element x sits
func (d *DisjointSets) FindSet(x int64) int64 {
if x != d.p[x] {
d.p[x] = d.FindSet(d.p[x])
}
return d.p[x]
}
// Union combines two elements x and y into one set.
func (d *DisjointSets) Union(x, y int64) {
d.Link(d.FindSet(x), d.FindSet(y))
}
I'd like to write as little incremental code as possible to use this structure for float64, string, etc. How do I do this?
What I've tried so far
I've read everything I can about Interfaces, but I just don't seem to understand how to apply it without having to write a complete implementation for each type.
What was the issue you stumbled upon when using interfaces? You should be able to easily translate that code to use interface{} as the element types and have it working with any type that has equality defined for it (can work as map keys).
Something along the lines of:
Go does not have templates so I do not think there is an elegant way to do this. You might try changing the class to take interface{} instead of int64.
Looks like you're trying to implement the classical union-find algorithm.
Why can't you keep what you've got, and just layer on top of this a mapping from whatever thing you want (float64, string, etc.) to an int64? Then you don't have to change your original code at all. Think composition.
Concretely, add a map from whatever domain you want, like string:
var m1 map[string]int64
...
m1["hello"] = 0
m2["world"] = 1
and then, whenever you want to figure out what set it belongs to, use m1 to go from strings to its integer representation for the element, and then your original code to find the parent representative.