sim-lib-music-serial 0.1.1

Immutable serial plans with stable row and event identity, explicit provenance, and validated partial temporal order.
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
97
98
99

//! Validated precedence graph for immutable serial events.

use std::collections::{BTreeMap, BTreeSet};

use crate::{SerialEventId, SerialPlanError};

/// A validated finite precedence DAG over stable event ids.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct PrecedenceGraph<I> {
    edges: BTreeMap<I, BTreeSet<I>>,
}

impl<I: Ord> Default for PrecedenceGraph<I> {
    fn default() -> Self {
        Self {
            edges: BTreeMap::new(),
        }
    }
}

impl PrecedenceGraph<SerialEventId> {
    /// Builds a graph from `before -> after` edges.
    pub fn try_new(
        edges: impl IntoIterator<Item = (SerialEventId, SerialEventId)>,
        known_nodes: &BTreeSet<SerialEventId>,
    ) -> Result<Self, SerialPlanError> {
        let mut graph = Self::default();
        for (before, after) in edges {
            if !known_nodes.contains(&before) {
                return Err(SerialPlanError::UnknownPrecedenceNode(before));
            }
            if !known_nodes.contains(&after) {
                return Err(SerialPlanError::UnknownPrecedenceNode(after));
            }
            if before == after {
                return Err(SerialPlanError::SelfPrecedence(before));
            }
            graph.edges.entry(before).or_default().insert(after);
        }
        graph.validate_acyclic(known_nodes)?;
        Ok(graph)
    }

    /// Returns whether one direct precedence edge exists.
    pub fn contains_edge(&self, before: &SerialEventId, after: &SerialEventId) -> bool {
        self.edges
            .get(before)
            .is_some_and(|targets| targets.contains(after))
    }

    /// Returns the outgoing precedence targets for one event.
    pub fn successors(&self, event_id: &SerialEventId) -> Option<&BTreeSet<SerialEventId>> {
        self.edges.get(event_id)
    }

    /// Returns every direct precedence edge in canonical order.
    pub fn edges(&self) -> impl Iterator<Item = (&SerialEventId, &SerialEventId)> {
        self.edges
            .iter()
            .flat_map(|(before, afters)| afters.iter().map(move |after| (before, after)))
    }

    fn validate_acyclic(
        &self,
        known_nodes: &BTreeSet<SerialEventId>,
    ) -> Result<(), SerialPlanError> {
        #[derive(Copy, Clone, PartialEq, Eq)]
        enum Mark {
            Visiting,
            Done,
        }

        fn visit(
            node: &SerialEventId,
            graph: &PrecedenceGraph<SerialEventId>,
            marks: &mut BTreeMap<SerialEventId, Mark>,
        ) -> Result<(), SerialPlanError> {
            match marks.get(node) {
                Some(Mark::Done) => return Ok(()),
                Some(Mark::Visiting) => return Err(SerialPlanError::PrecedenceCycle(node.clone())),
                None => {}
            }
            marks.insert(node.clone(), Mark::Visiting);
            if let Some(targets) = graph.edges.get(node) {
                for target in targets {
                    visit(target, graph, marks)?;
                }
            }
            marks.insert(node.clone(), Mark::Done);
            Ok(())
        }

        let mut marks = BTreeMap::new();
        for node in known_nodes {
            visit(node, self, &mut marks)?;
        }
        Ok(())
    }
}