libpitust 0.1.2

libpitust implements random utility functions I tend to use a lot
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

//! module `dsu` implements the Disjoint Set Union data structure.
//!
//! See https://cp-algorithms.com/data_structures/disjoint_set_union.html

use std::hash::Hash;

use crate::{
    index::{intern::InternMap, vec::IndexVec},
    index_type,
};

index_type!(DSUNode);

#[derive(Default, Clone)]
struct DSUBase {
    nodes: IndexVec<DSUNode, DSUNode>,
    weights: IndexVec<DSUNode, u32>,
}
impl DSUBase {
    fn new() -> DSUBase {
        DSUBase {
            nodes: IndexVec::new(),
            weights: IndexVec::new(),
        }
    }
    fn track_new_node(&mut self, node: DSUNode) {
        let node2 = self.nodes.push(node);
        debug_assert!(node == node2);

        self.weights.push(1);
    }
    fn find(&mut self, node: DSUNode) -> DSUNode {
        let mut cur = node;
        loop {
            let next = self.nodes[cur];
            if cur == next {
                self.nodes[node] = cur;
                return cur;
            }
            cur = next;
        }
    }
    fn union(&mut self, n1: DSUNode, n2: DSUNode) {
        let n1 = self.find(n1);
        let n2 = self.find(n2);
        if n1 == n2 {
            return;
        }

        let parent;
        let child;
        if self.weights[n1] < self.weights[n2] {
            child = n1;
            parent = n2;
        } else {
            child = n2;
            parent = n1;
        }
        self.nodes[child] = parent;
        self.weights[parent] += self.weights[child];
    }
}

pub struct DSU<Node: Copy + Eq + Hash> {
    nodes: InternMap<DSUNode, Node>,
    dsu: DSUBase,
}
impl<Node: Copy + Eq + Hash> DSU<Node> {
    pub fn new() -> DSU<Node> {
        DSU {
            nodes: InternMap::new(),
            dsu: DSUBase::new(),
        }
    }
    fn node_to_id(&mut self, node: Node) -> DSUNode {
        let w = self.nodes.watermark();
        let id = self.nodes.push(&node);
        if w != self.nodes.watermark() {
            self.dsu.track_new_node(id);
        }
        id
    }
    pub fn find(&mut self, node: Node) -> Node {
        if let Some(node) = self.nodes.try_push(&node) {
            let node = self.dsu.find(node);
            self.nodes[node]
        } else {
            node
        }
    }
    pub fn union(&mut self, a: Node, b: Node) {
        let a = self.node_to_id(a);
        let b = self.node_to_id(b);
        self.dsu.union(a, b);
    }
}