Go语言泛型化不相交集数据结构：使用interface{}实现类型无关操作

package disjointsets

type DisjointSets struct {
    ranks map[int64]int64 // 存储每个集合代表的秩
    p     map[int64]int64 // 存储每个元素的父节点
}

// NewDisjointSets 返回一个新的DisjointSets实例
func NewDisjointSets() *DisjointSets {
    d := DisjointSets{map[int64]int64{}, map[int64]int64{}}
    return &d
}

// MakeSet 将元素x添加到不相交集中，作为其自身所在集合的代表
func (d *DisjointSets) MakeSet(x int64) {
    d.p[x] = x
    d.ranks[x] = 0
}

// Link 根据秩合并两个代表元素x和y所在的集合
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 查找元素x所属集合的代表元素，并进行路径压缩
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 合并元素x和y所在的两个集合
func (d *DisjointSets) Union(x, y int64) {
    d.Link(d.FindSet(x), d.FindSet(y))
}

package disjointsets

// DisjointSets 泛型不相交集数据结构
type DisjointSets struct {
    ranks map[interface{}]int64   // 存储每个集合代表的秩，键为任意类型
    p     map[interface{}]interface{} // 存储每个元素的父节点，键和值都为任意类型
}

// NewDisjointSets 返回一个新的泛型DisjointSets实例
func NewDisjointSets() *DisjointSets {
    d := DisjointSets{
        ranks: make(map[interface{}]int64),
        p:     make(map[interface{}]interface{}),
    }
    return &d
}

// MakeSet 将元素x添加到不相交集中，作为其自身所在集合的代表
// x可以是任何可作为map键的类型
func (d *DisjointSets) MakeSet(x interface{}) {
    // 检查元素是否已存在，避免重复初始化
    if _, exists := d.p[x]; !exists {
        d.p[x] = x
        d.ranks[x] = 0
    }
}

// Link 根据秩合并两个代表元素x和y所在的集合
// x和y必须是已通过MakeSet添加的元素，且为同一类型
func (d *DisjointSets) Link(x, y interface{}) {
    // 注意：这里的x和y已经是FindSet后的代表元素
    // 它们应该在ranks中存在
    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 查找元素x所属集合的代表元素，并进行路径压缩
// x可以是任何可作为map键的类型
func (d *DisjointSets) FindSet(x interface{}) interface{} {
    // 如果x不是其自身的父节点，则进行路径压缩
    if x != d.p[x] {
        d.p[x] = d.FindSet(d.p[x])
    }
    return d.p[x]
}

// Union 合并元素x和y所在的两个集合
// x和y可以是任何可作为map键的类型
func (d *DisjointSets) Union(x, y interface{}) {
    // 在合并之前，确保x和y都已经通过MakeSet添加
    // 否则FindSet可能会失败
    d.Link(d.FindSet(x), d.FindSet(y))
}

package main

import (
    "fmt"
    "disjointsets" // 假设上述代码在disjointsets包中
)

func main() {
    ds := disjointsets.NewDisjointSets()

    // 使用int类型
    fmt.Println("--- 使用 int 类型 ---")
    ds.MakeSet(1)
    ds.MakeSet(2)
    ds.MakeSet(3)
    ds.MakeSet(4)

    ds.Union(1, 2)
    ds.Union(3, 4)
    ds.Union(2, 3)

    fmt.Printf("FindSet(1): %v\n", ds.FindSet(1)) // 预期：与2,3,4相同
    fmt.Printf("FindSet(4): %v\n", ds.FindSet(4)) // 预期：与1,2,3相同
    fmt.Println("1和4是否在同一集合:", ds.FindSet(1) == ds.FindSet(4)) // true

    // 使用string类型
    fmt.Println("\n--- 使用 string 类型 ---")
    ds2 := disjointsets.NewDisjointSets()
    ds2.MakeSet("apple")
    ds2.MakeSet("banana")
    ds2.MakeSet("cherry")
    ds2.MakeSet("date")

    ds2.Union("apple", "banana")
    ds2.Union("cherry", "date")
    ds2.Union("banana", "cherry")

    fmt.Printf("FindSet(\"apple\"): %v\n", ds2.FindSet("apple"))
    fmt.Printf("FindSet(\"date\"): %v\n", ds2.FindSet("date"))
    fmt.Println("apple和date是否在同一集合:", ds2.FindSet("apple") == ds2.FindSet("date")) // true

    // 使用float64类型
    fmt.Println("\n--- 使用 float64 类型 ---")
    ds3 := disjointsets.NewDisjointSets()
    ds3.MakeSet(1.1)
    ds3.MakeSet(2.2)
    ds3.MakeSet(3.3)

    ds3.Union(1.1, 2.2)

    fmt.Printf("FindSet(1.1): %v\n", ds3.FindSet(1.1))
    fmt.Printf("FindSet(3.3): %v\n", ds3.FindSet(3.3))
    fmt.Println("1.1和3.3是否在同一集合:", ds3.FindSet(1.1) == ds3.FindSet(3.3)) // false
}