go - 我如何最好地鸭式这个 Go Disjoint Sets 数据结构？

Question

我有一个 DisjointSets 数据结构(从 Cormen 提取)，在 Go 中实现以与 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))
}

我想编写尽可能少的增量代码，以将此结构用于 float64、string 等。我该怎么做？

到目前为止我尝试了什么

我已经阅读了所有关于接口(interface)的内容，但我似乎不明白如何在不必为每种类型编写完整实现的情况下应用它。

Answer 1

您在使用界面时遇到了什么问题？您应该能够轻松地将该代码转换为使用 interface{} 作为元素类型，并让它与任何为其定义了相等性的类型一起工作(可以 work as map keys )。

类似的东西:

• http://play.golang.org/p/uNcYWltd50