cadmpeg-codec-step 0.6.3

Read and write ISO 10303-21 STEP Part 21 files for AP203, AP214, and AP242.
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

// SPDX-License-Identifier: Apache-2.0
//! Connected wire carriers, using vertex identities rather than coordinates.

use crate::writer::Ref;
use cadmpeg_ir::topology::Edge;
use std::collections::HashMap;

pub(super) fn connected_components(edges: &[(Ref, &Edge)]) -> Vec<Vec<Ref>> {
    fn root(parents: &mut [usize], mut index: usize) -> usize {
        while parents[index] != index {
            parents[index] = parents[parents[index]];
            index = parents[index];
        }
        index
    }
    let mut parents = (0..edges.len()).collect::<Vec<_>>();
    let mut ranks = vec![0u8; edges.len()];
    let mut vertices = HashMap::new();
    for (index, (_, edge)) in edges.iter().enumerate() {
        for vertex in [&edge.start, &edge.end] {
            if let Some(&previous) = vertices.get(vertex) {
                let left = root(&mut parents, index);
                let right = root(&mut parents, previous);
                if left != right {
                    match ranks[left].cmp(&ranks[right]) {
                        std::cmp::Ordering::Less => parents[left] = right,
                        std::cmp::Ordering::Greater => parents[right] = left,
                        std::cmp::Ordering::Equal => {
                            parents[right] = left;
                            ranks[left] += 1;
                        }
                    }
                }
            } else {
                vertices.insert(vertex, index);
            }
        }
    }
    let mut groups = HashMap::new();
    let mut components = Vec::<Vec<Ref>>::new();
    for (index, (emitted, _)) in edges.iter().enumerate() {
        let group = *groups.entry(root(&mut parents, index)).or_insert_with(|| {
            components.push(Vec::new());
            components.len() - 1
        });
        components[group].push(*emitted);
    }
    components
}

#[cfg(test)]
mod tests {
    use super::connected_components;
    use crate::writer::Ref;
    use cadmpeg_ir::{
        ids::{EdgeId, VertexId},
        topology::Edge,
    };

    #[test]
    fn components_follow_topological_vertices_including_bridges_branches_and_cycles() {
        let carrier = cadmpeg_ir::examples::unit_cube().expect("cube").model.edges[0]
            .carrier
            .clone();
        let edge = |id: usize, start: usize, end: usize| Edge {
            id: EdgeId::mint(format!("test:model:edge#{id}")).expect("edge id"),
            carrier: carrier.clone(),
            start: VertexId::mint(format!("test:model:vertex#{start}")).expect("vertex id"),
            end: VertexId::mint(format!("test:model:vertex#{end}")).expect("vertex id"),
            tolerance: None,
        };
        let edges = [
            edge(1, 1, 2),
            edge(2, 3, 4),
            edge(3, 2, 3),
            edge(4, 4, 1),
            edge(5, 2, 5),
            edge(6, 6, 7),
            edge(7, 7, 7),
        ];
        let emitted = edges
            .iter()
            .enumerate()
            .map(|(i, edge)| (Ref(cadmpeg_core::decode::u64_from_index(i) + 1), edge))
            .collect::<Vec<_>>();
        assert_eq!(
            connected_components(&emitted),
            vec![
                vec![Ref(1), Ref(2), Ref(3), Ref(4), Ref(5)],
                vec![Ref(6), Ref(7)]
            ]
        );
        assert!(connected_components(&[]).is_empty());
    }
}