标记并查集

在生产使用中，除了测试两个元素是否在同一个集合中，我们还经常想了解集合的大小或者迭代它。

这些需求可以抽象为可合并的标签。也就是说，集合与标签相关联。当两个集合合并时，它们的标签会合并。

作为典型的并查集使用，但可计数和可迭代

将 () 关联到集合。

use tagged_ufs::*;
use std::collections::BTreeSet;

let mut sets = UnionFindSets::new();
// adds 3 elements
sets.make_set(0, ());
sets.make_set(1, ());
sets.make_set(2, ());
// unites two of them
sets.unite(&0, &1);
// same-set testing
let set_0 = sets.find(&0).unwrap();
let set_1 = sets.find(&1).unwrap();
let set_2 = sets.find(&2).unwrap();
assert_eq!(set_0, set_1);
assert_ne!(set_0, set_2);
assert_ne!(set_1, set_2);
// cardinal querying
assert_eq!(set_0.len(), 2);
assert_eq!(set_2.len(), 1);
// iteration over elements in a set
assert_eq!(set_0.iter().copied().collect::<BTreeSet<_>>(), BTreeSet::from([0, 1]));
assert_eq!(set_2.iter().copied().collect::<BTreeSet<_>>(), BTreeSet::from([2]));
// iteration over sets
assert_eq!(sets.len(), 2);
let trial_sets: BTreeSet<BTreeSet<_>> = sets.iter().map(|xs| {
    xs.iter().copied().collect()
}).collect();
let oracle_sets: BTreeSet<BTreeSet<_>> = [
    BTreeSet::from([0, 1]),
    BTreeSet::from([2]),
].into_iter().collect();
assert_eq!(trial_sets, oracle_sets);

自定义标签

自定义标签类型必须实现[Mergable]。

use tagged_ufs::*;

struct Tag {
    x: usize,
}

impl Mergable for Tag {
    fn merge(&mut self, other: Tag) {
        self.x += other.x;
    }
}

let mut sets = UnionFindSets::new();
sets.make_set(0, Tag { x: 1 });
sets.make_set(1, Tag { x: 2 });
assert_eq!(sets.find(&0).unwrap().tag().x, 1);
assert_eq!(sets.find(&1).unwrap().tag().x, 2);
sets.unite(&0, &1);
assert_eq!(sets.find(&0).unwrap().tag().x, 3);

原始实现（不包含元素迭代）

元素迭代也是通过可合并的标签实现的，例如[IterableTag]。因此，当它成为开销时，可以绕过这一层。

use tagged_ufs::raw::*;
use std::collections::BTreeSet;

let mut sets = UnionFindSets::new();
// adds 3 elements
sets.make_set(0, ());
sets.make_set(1, ());
sets.make_set(2, ());
// unites two of them
sets.unite(&0, &1);
// same-set testing
let set_0 = sets.find(&0).unwrap();
let set_1 = sets.find(&1).unwrap();
let set_2 = sets.find(&2).unwrap();
assert_eq!(set_0, set_1);
assert_ne!(set_0, set_2);
assert_ne!(set_1, set_2);
// cardinal querying
assert_eq!(set_0.len(), 2);
assert_eq!(set_2.len(), 1);
// but iteration over sets is still okey
assert_eq!(sets.len(), 2);
let trial_set_cardinals: BTreeSet<usize> = sets.iter().map(|xs| xs.len()).collect();
assert_eq!(trial_set_cardinals, BTreeSet::from([1, 2]));