sim_lib_music_serial/
order.rs

1//! Validated precedence graph for immutable serial events.
2
3use std::collections::{BTreeMap, BTreeSet};
4
5use crate::{SerialEventId, SerialPlanError};
6
7/// A validated finite precedence DAG over stable event ids.
8#[derive(Clone, Debug, PartialEq, Eq)]
9pub struct PrecedenceGraph<I> {
10    edges: BTreeMap<I, BTreeSet<I>>,
11}
12
13impl<I: Ord> Default for PrecedenceGraph<I> {
14    fn default() -> Self {
15        Self {
16            edges: BTreeMap::new(),
17        }
18    }
19}
20
21impl PrecedenceGraph<SerialEventId> {
22    /// Builds a graph from `before -> after` edges.
23    pub fn try_new(
24        edges: impl IntoIterator<Item = (SerialEventId, SerialEventId)>,
25        known_nodes: &BTreeSet<SerialEventId>,
26    ) -> Result<Self, SerialPlanError> {
27        let mut graph = Self::default();
28        for (before, after) in edges {
29            if !known_nodes.contains(&before) {
30                return Err(SerialPlanError::UnknownPrecedenceNode(before));
31            }
32            if !known_nodes.contains(&after) {
33                return Err(SerialPlanError::UnknownPrecedenceNode(after));
34            }
35            if before == after {
36                return Err(SerialPlanError::SelfPrecedence(before));
37            }
38            graph.edges.entry(before).or_default().insert(after);
39        }
40        graph.validate_acyclic(known_nodes)?;
41        Ok(graph)
42    }
43
44    /// Returns whether one direct precedence edge exists.
45    pub fn contains_edge(&self, before: &SerialEventId, after: &SerialEventId) -> bool {
46        self.edges
47            .get(before)
48            .is_some_and(|targets| targets.contains(after))
49    }
50
51    /// Returns the outgoing precedence targets for one event.
52    pub fn successors(&self, event_id: &SerialEventId) -> Option<&BTreeSet<SerialEventId>> {
53        self.edges.get(event_id)
54    }
55
56    /// Returns every direct precedence edge in canonical order.
57    pub fn edges(&self) -> impl Iterator<Item = (&SerialEventId, &SerialEventId)> {
58        self.edges
59            .iter()
60            .flat_map(|(before, afters)| afters.iter().map(move |after| (before, after)))
61    }
62
63    fn validate_acyclic(
64        &self,
65        known_nodes: &BTreeSet<SerialEventId>,
66    ) -> Result<(), SerialPlanError> {
67        #[derive(Copy, Clone, PartialEq, Eq)]
68        enum Mark {
69            Visiting,
70            Done,
71        }
72
73        fn visit(
74            node: &SerialEventId,
75            graph: &PrecedenceGraph<SerialEventId>,
76            marks: &mut BTreeMap<SerialEventId, Mark>,
77        ) -> Result<(), SerialPlanError> {
78            match marks.get(node) {
79                Some(Mark::Done) => return Ok(()),
80                Some(Mark::Visiting) => return Err(SerialPlanError::PrecedenceCycle(node.clone())),
81                None => {}
82            }
83            marks.insert(node.clone(), Mark::Visiting);
84            if let Some(targets) = graph.edges.get(node) {
85                for target in targets {
86                    visit(target, graph, marks)?;
87                }
88            }
89            marks.insert(node.clone(), Mark::Done);
90            Ok(())
91        }
92
93        let mut marks = BTreeMap::new();
94        for node in known_nodes {
95            visit(node, self, &mut marks)?;
96        }
97        Ok(())
98    }
99}
sim_lib_music_serial/order.rs

sim_lib_music_serial/
order.rs
