sim_lib_pitch_set/
geometry.rs

1//! Pitch-set geometry and graph neighborhoods.
2
3use sim_lib_discrete_graph::{Directedness, Graph, GraphError};
4use sim_lib_discrete_search::SearchControl;
5use sim_lib_pitch_core::PitchClass;
6
7use crate::PitchClassMask;
8
9/// How zero-sized gaps are represented.
10#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
11pub enum ZeroGapPolicy {
12    /// Collapse duplicate pitch classes; zero gaps never appear.
13    CollapseDuplicates,
14    /// Preserve adjacent duplicate pitch classes as explicit zero gaps.
15    PreserveMultiplicity,
16}
17
18/// Directed interval steps between adjacent pitch classes in a cyclic ordering.
19#[derive(Clone, Debug, PartialEq, Eq, Hash)]
20pub struct GapForm {
21    /// Adjacent cyclic semitone gaps. The sum is `12` for duplicate-free
22    /// pitch-class forms and may include zero entries when multiplicity is
23    /// preserved.
24    pub gaps: Vec<u8>,
25    /// The policy used to decide whether adjacent equal pitch classes produce a
26    /// zero gap.
27    pub zero_gap_policy: ZeroGapPolicy,
28}
29
30/// Pairwise directed pitch-class intervals.
31#[derive(Clone, Debug, PartialEq, Eq, Hash)]
32pub struct IntervalForm {
33    /// Ordered pitch-class pairs and directed semitone distances from the first
34    /// pitch class to the second.
35    pub intervals: Vec<(PitchClass, PitchClass, u8)>,
36}
37
38/// Pitch-class universe used by a neighborhood graph.
39#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
40pub struct PitchSetSpace {
41    /// Required set cardinality for every graph node.
42    pub cardinality: u8,
43}
44
45impl PitchSetSpace {
46    /// The complete twelve-class universe at a fixed cardinality.
47    pub fn chromatic(cardinality: u8) -> Self {
48        Self { cardinality }
49    }
50}
51
52/// Allowed move family between pitch-class sets.
53#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
54pub enum PitchSetMovePolicy {
55    /// Any one pitch class may be replaced by any absent pitch class.
56    Jumping,
57    /// A pitch class may move by one semitone into an unoccupied neighbor.
58    NonJumping,
59}
60
61/// Graph builder for pitch-set neighborhoods.
62#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
63pub struct PitchSetNeighborhood {
64    /// Node universe.
65    pub space: PitchSetSpace,
66    /// Edge policy.
67    pub move_policy: PitchSetMovePolicy,
68}
69
70/// Error raised while building a pitch-set graph.
71#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
72pub enum PitchSetGraphError {
73    /// Cardinality must fit the twelve pitch classes.
74    #[error("pitch-set cardinality {0} is outside 0..=12")]
75    InvalidCardinality(u8),
76    /// SearchControl stopped enumeration before the graph was complete.
77    #[error("pitch-set graph enumeration exceeded {limit}: used {used}")]
78    SearchLimit {
79        /// Limit field that stopped the run.
80        limit: &'static str,
81        /// Charged amount at the stop.
82        used: u64,
83    },
84    /// A discrete graph construction error occurred.
85    #[error(transparent)]
86    Graph(#[from] GraphError),
87}
88
89impl PitchClassMask {
90    /// Return adjacent cyclic gaps for this set's pitch classes.
91    ///
92    /// `PitchClassMask` has set identity, so duplicate pitch classes are already
93    /// collapsed and zero gaps are absent. Use [`gap_form_from_pitch_classes`]
94    /// when caller-owned multiplicity must be preserved.
95    pub fn gap_form(self) -> GapForm {
96        gap_form_from_pitch_classes(&self.pitch_classes(), ZeroGapPolicy::CollapseDuplicates)
97    }
98
99    /// Return directed pairwise intervals between all pitch classes in the set.
100    pub fn interval_form(self) -> IntervalForm {
101        interval_form_from_pitch_classes(&self.pitch_classes())
102    }
103}
104
105/// Return adjacent cyclic gaps for caller-owned pitch-class material.
106pub fn gap_form_from_pitch_classes(
107    pitch_classes: &[PitchClass],
108    zero_gap_policy: ZeroGapPolicy,
109) -> GapForm {
110    let mut values: Vec<u8> = pitch_classes
111        .iter()
112        .map(|pitch_class| pitch_class.value())
113        .collect();
114    values.sort_unstable();
115    if matches!(zero_gap_policy, ZeroGapPolicy::CollapseDuplicates) {
116        values.dedup();
117    }
118    let gaps = match values.len() {
119        0 => Vec::new(),
120        1 => vec![0],
121        len => values
122            .iter()
123            .enumerate()
124            .map(|(index, value)| {
125                let next = values[(index + 1) % len];
126                (i16::from(next) - i16::from(*value)).rem_euclid(12) as u8
127            })
128            .collect(),
129    };
130    GapForm {
131        gaps,
132        zero_gap_policy,
133    }
134}
135
136/// Return directed pairwise intervals for caller-owned pitch-class material.
137pub fn interval_form_from_pitch_classes(pitch_classes: &[PitchClass]) -> IntervalForm {
138    let mut values: Vec<PitchClass> = pitch_classes.to_vec();
139    values.sort_by_key(|pitch_class| pitch_class.value());
140    values.dedup();
141    let mut intervals = Vec::new();
142    for (index, from) in values.iter().enumerate() {
143        for to in values.iter().skip(index + 1) {
144            intervals.push((*from, *to, to.value().wrapping_sub(from.value()) % 12));
145        }
146    }
147    IntervalForm { intervals }
148}
149
150impl PitchSetNeighborhood {
151    /// Create a pitch-set neighborhood graph builder.
152    pub fn new(space: PitchSetSpace, move_policy: PitchSetMovePolicy) -> Self {
153        Self { space, move_policy }
154    }
155
156    /// Materialize the neighborhood as an undirected graph.
157    ///
158    /// Open enumeration is charged against `SearchControl::max_work` and
159    /// `SearchControl::max_results`; every accepted node and edge consumes one
160    /// unit of work.
161    pub fn materialize(
162        self,
163        control: SearchControl,
164    ) -> Result<Graph<PitchClassMask, i64>, PitchSetGraphError> {
165        if self.space.cardinality > 12 {
166            return Err(PitchSetGraphError::InvalidCardinality(
167                self.space.cardinality,
168            ));
169        }
170        let nodes = enumerate_masks(self.space.cardinality, &control)?;
171        let mut graph = Graph::with_nodes(nodes, Directedness::Undirected);
172        let mut work = graph.node_count() as u64;
173        for source in 0..graph.nodes.len() {
174            for target in (source + 1)..graph.nodes.len() {
175                if are_neighbors(graph.nodes[source], graph.nodes[target], self.move_policy) {
176                    work = work.checked_add(1).ok_or(PitchSetGraphError::SearchLimit {
177                        limit: "max_work",
178                        used: u64::MAX,
179                    })?;
180                    if let Some(max_work) = control.max_work
181                        && work > max_work
182                    {
183                        return Err(PitchSetGraphError::SearchLimit {
184                            limit: "max_work",
185                            used: work,
186                        });
187                    }
188                    graph.add_edge(source, target, 1)?;
189                }
190            }
191        }
192        Ok(graph)
193    }
194}
195
196fn enumerate_masks(
197    cardinality: u8,
198    control: &SearchControl,
199) -> Result<Vec<PitchClassMask>, PitchSetGraphError> {
200    let mut masks = Vec::new();
201    let mut work = 0u64;
202    for bits in 0u16..=0x0fff {
203        if bits.count_ones() == u32::from(cardinality) {
204            work = work.checked_add(1).ok_or(PitchSetGraphError::SearchLimit {
205                limit: "max_work",
206                used: u64::MAX,
207            })?;
208            if let Some(max_work) = control.max_work
209                && work > max_work
210            {
211                return Err(PitchSetGraphError::SearchLimit {
212                    limit: "max_work",
213                    used: work,
214                });
215            }
216            if let Some(max_results) = control.max_results
217                && masks.len() >= max_results
218            {
219                return Err(PitchSetGraphError::SearchLimit {
220                    limit: "max_results",
221                    used: masks.len() as u64,
222                });
223            }
224            masks.push(PitchClassMask::new(bits).expect("enumeration yields valid mask bits"));
225        }
226    }
227    Ok(masks)
228}
229
230fn are_neighbors(a: PitchClassMask, b: PitchClassMask, policy: PitchSetMovePolicy) -> bool {
231    let removed = a.bits() & !b.bits();
232    let added = b.bits() & !a.bits();
233    if removed.count_ones() != 1 || added.count_ones() != 1 {
234        return false;
235    }
236    match policy {
237        PitchSetMovePolicy::Jumping => true,
238        PitchSetMovePolicy::NonJumping => {
239            let from = removed.trailing_zeros() as i32;
240            let to = added.trailing_zeros() as i32;
241            matches!((to - from).rem_euclid(12), 1 | 11)
242        }
243    }
244}
245
246#[cfg(test)]
247mod tests {
248    use super::*;
249    use sim_lib_discrete_graph::{shortest_path, verify_shortest_paths};
250    use sim_lib_discrete_search::SearchControl;
251
252    fn mask(values: &[PitchClass]) -> PitchClassMask {
253        PitchClassMask::from_pitch_classes(values)
254    }
255
256    #[test]
257    fn gap_forms_make_zero_gap_multiplicity_explicit() {
258        let source = [PitchClass::C, PitchClass::C, PitchClass::E, PitchClass::G];
259
260        assert_eq!(
261            gap_form_from_pitch_classes(&source, ZeroGapPolicy::CollapseDuplicates).gaps,
262            vec![4, 3, 5]
263        );
264        assert_eq!(
265            gap_form_from_pitch_classes(&source, ZeroGapPolicy::PreserveMultiplicity).gaps,
266            vec![0, 4, 3, 5]
267        );
268        assert_eq!(mask(&source).interval_vector().0, [0, 0, 1, 1, 1, 0]);
269    }
270
271    #[test]
272    fn interval_and_gap_forms_are_transposition_invariant() {
273        let source = mask(&[PitchClass::C, PitchClass::DS, PitchClass::FS, PitchClass::A]);
274        let transposed = source.rotate(5);
275
276        assert_eq!(source.gap_form(), transposed.gap_form());
277        assert_eq!(source.interval_vector(), transposed.interval_vector());
278    }
279
280    #[test]
281    fn interval_and_gap_forms_are_inversion_invariant_after_reordering() {
282        let source = mask(&[PitchClass::C, PitchClass::D, PitchClass::F, PitchClass::A]);
283        let inverted = source.invert(PitchClass::C);
284
285        let mut source_gaps = source.gap_form().gaps;
286        let mut inverted_gaps = inverted.gap_form().gaps;
287        source_gaps.sort_unstable();
288        inverted_gaps.sort_unstable();
289        assert_eq!(source_gaps, inverted_gaps);
290        assert_eq!(source.interval_vector(), inverted.interval_vector());
291    }
292
293    #[test]
294    fn jumping_neighborhood_materializes_reversible_graph() {
295        let graph =
296            PitchSetNeighborhood::new(PitchSetSpace::chromatic(2), PitchSetMovePolicy::Jumping)
297                .materialize(SearchControl::default())
298                .unwrap();
299        let start = graph
300            .nodes
301            .iter()
302            .position(|node| *node == mask(&[PitchClass::C, PitchClass::E]))
303            .unwrap();
304        let goal = graph
305            .nodes
306            .iter()
307            .position(|node| *node == mask(&[PitchClass::D, PitchClass::F]))
308            .unwrap();
309
310        let round = shortest_path(&graph, start, goal).unwrap();
311
312        assert_eq!(round.distance, Some(2));
313        verify_shortest_paths(&graph, &round.certificate).unwrap();
314        for edge in &graph.edges {
315            assert!(
316                graph
317                    .neighbors(edge.target)
318                    .unwrap()
319                    .iter()
320                    .any(|neighbor| {
321                        neighbor.node == edge.source && *neighbor.weight == edge.weight
322                    })
323            );
324        }
325    }
326
327    #[test]
328    fn non_jumping_neighborhood_uses_single_step_edges() {
329        let graph =
330            PitchSetNeighborhood::new(PitchSetSpace::chromatic(1), PitchSetMovePolicy::NonJumping)
331                .materialize(SearchControl::default())
332                .unwrap();
333        let start = graph
334            .nodes
335            .iter()
336            .position(|node| node.bits() == 0b1)
337            .unwrap();
338        let goal = graph
339            .nodes
340            .iter()
341            .position(|node| node.bits() == 0b100)
342            .unwrap();
343
344        let trail = shortest_path(&graph, start, goal).unwrap();
345
346        assert_eq!(trail.distance, Some(2));
347        verify_shortest_paths(&graph, &trail.certificate).unwrap();
348    }
349
350    #[test]
351    fn search_control_charges_open_enumeration() {
352        let err =
353            PitchSetNeighborhood::new(PitchSetSpace::chromatic(3), PitchSetMovePolicy::Jumping)
354                .materialize(SearchControl::default().with_max_results(4))
355                .unwrap_err();
356
357        assert_eq!(
358            err,
359            PitchSetGraphError::SearchLimit {
360                limit: "max_results",
361                used: 4,
362            }
363        );
364    }
365}
sim_lib_pitch_set/geometry.rs

sim_lib_pitch_set/
geometry.rs
