music21/alpha/analysis/
search.rs

1//! Runs of notes climbing or falling through a scale: music21's
2//! `alpha.analysis.search`.
3//!
4//! ```
5//! use music21::alpha::analysis::search::{ScaleRunOptions, find_consecutive_scale};
6//! use music21::scale::{Scale, ScaleType};
7//! use music21::tinynotation::from_tiny_notation;
8//! use music21::Pitch;
9//!
10//! let line = from_tiny_notation("4/4 a4 b c'# d' e' f'#")?.flatten();
11//! let a_major = Scale::new(ScaleType::Major, Pitch::from_name("A4")?);
12//! let runs = find_consecutive_scale(&line, &a_major, &ScaleRunOptions::default())?;
13//! assert_eq!(runs.len(), 1);
14//! assert_eq!(runs[0].elements.len(), 6);
15//! # Ok::<(), music21::Error>(())
16//! ```
17
18use std::collections::BTreeSet;
19
20use crate::error::{Error, Result};
21use crate::pitch::Pitch;
22use crate::scale::{DegreeComparison, Scale};
23use crate::stream::{Stream, StreamElement};
24
25/// Which way a run goes through the scale.
26#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
27#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
28pub enum RunDirection {
29    /// Up the scale.
30    Ascending,
31    /// Down the scale.
32    Descending,
33}
34
35/// What two pitches must share to count as the same: music21's
36/// `comparisonAttribute`.
37#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Default)]
38#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
39pub enum PitchAttribute {
40    /// The name, octave aside: `name`.
41    #[default]
42    Name,
43    /// The name and the octave: `nameWithOctave`.
44    NameWithOctave,
45    /// The pitch class: `pitchClass`.
46    PitchClass,
47    /// The letter: `step`.
48    Step,
49}
50
51impl PitchAttribute {
52    fn key(self, pitch: &Pitch) -> String {
53        match self {
54            Self::Name => pitch.name(),
55            Self::NameWithOctave => pitch.name_with_octave(),
56            Self::PitchClass => pitch.pitch_class().number().to_string(),
57            Self::Step => pitch.step().as_char().to_string(),
58        }
59    }
60
61    /// How a scale degree is found under this comparison. music21 looks a
62    /// pitch up among the scale's pitches realized about it, octave and
63    /// all, so a name with its octave finds the degree its name does.
64    fn degree_comparison(self) -> DegreeComparison {
65        match self {
66            Self::Name | Self::NameWithOctave => DegreeComparison::Name,
67            Self::PitchClass => DegreeComparison::PitchClass,
68            Self::Step => DegreeComparison::Step,
69        }
70    }
71}
72
73/// music21's keyword arguments to `findConsecutiveScale`.
74#[derive(Clone, Debug, PartialEq, Eq)]
75#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
76#[non_exhaustive]
77pub struct ScaleRunOptions {
78    /// How many different degrees a run must reach: `degreesRequired`.
79    pub degrees_required: usize,
80    /// How many degrees each step of a run moves: `stepSize`.
81    pub step_size: usize,
82    /// What a pitch and a scale pitch must share: `comparisonAttribute`.
83    pub comparison: PitchAttribute,
84    /// Whether a degree repeated keeps a run going: `repeatsAllowed`.
85    pub repeats_allowed: bool,
86}
87
88impl Default for ScaleRunOptions {
89    fn default() -> Self {
90        Self {
91            degrees_required: 5,
92            step_size: 1,
93            comparison: PitchAttribute::Name,
94            repeats_allowed: true,
95        }
96    }
97}
98
99/// A run found: the notes in it, by their place among the stream's own
100/// elements, and the way it goes, where it has gone one.
101#[derive(Clone, Debug, PartialEq, Eq)]
102#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
103pub struct ScaleRun {
104    /// The places of the notes in the stream's own elements, in order.
105    pub elements: Vec<usize>,
106    /// Which way the run went.
107    pub direction: Option<RunDirection>,
108}
109
110/// The degree a pitch stands on, read in a direction, or both where none
111/// is said: music21's `getScaleDegreeFromPitch`.
112fn degree(
113    scale: &Scale,
114    pitch: &Pitch,
115    direction: Option<RunDirection>,
116    comparison: PitchAttribute,
117) -> Result<Option<usize>> {
118    let comparison = comparison.degree_comparison();
119    match direction {
120        Some(RunDirection::Ascending) => scale.degree_of_by(pitch, comparison),
121        Some(RunDirection::Descending) => scale.descending().degree_of_by(pitch, comparison),
122        None => match scale.degree_of_by(pitch, comparison)? {
123            Some(found) => Ok(Some(found)),
124            None => scale.descending().degree_of_by(pitch, comparison),
125        },
126    }
127}
128
129/// Whether `other` is the pitch `steps` degrees from `origin` in a
130/// direction: music21's `isNext`, which is false where there is no other
131/// pitch and refuses where no direction is said.
132fn is_next(
133    scale: &Scale,
134    other: Option<&Pitch>,
135    origin: &Pitch,
136    direction: Option<RunDirection>,
137    steps: usize,
138    comparison: PitchAttribute,
139) -> Result<bool> {
140    let Some(other) = other else {
141        return Ok(false);
142    };
143    let next = match direction {
144        Some(RunDirection::Ascending) => scale.next_pitch_beside(origin, steps as _, true)?,
145        Some(RunDirection::Descending) => scale.descending().next_pitch_beside(
146            origin,
147            -(steps as crate::defaults::IntegerType),
148            false,
149        )?,
150        None => {
151            return Err(Error::Scale(
152                "cannot match direction specification: None".to_string(),
153            ));
154        }
155    };
156    Ok(comparison.key(&next) == comparison.key(other))
157}
158
159/// Every run of notes in a stream going one way through a scale, a degree
160/// at a time, that reaches at least as many different degrees as asked:
161/// music21's `findConsecutiveScale`.
162///
163/// The stream's own notes are read in order, its chords, rests and
164/// streams passed over -- so a rest never breaks a run, whatever
165/// music21's `restsAllowed` says, since it never reads one. A run is
166/// greedy: it goes on as long as the next note continues it. A note off
167/// the scale ends a run; a note on it that does not continue the run ends
168/// it and starts the next.
169///
170/// # Errors
171///
172/// A scale its pitches cannot be read in, or a run asked for of fewer than
173/// two degrees, which music21 cannot tell the way of.
174pub fn find_consecutive_scale(
175    source: &Stream,
176    scale: &Scale,
177    options: &ScaleRunOptions,
178) -> Result<Vec<ScaleRun>> {
179    let notes: Vec<(usize, Pitch)> = source
180        .events()
181        .iter()
182        .enumerate()
183        .filter_map(|(place, event)| match event.element() {
184            StreamElement::Note(note) => Some((place, note.pitch().clone())),
185            _ => None,
186        })
187        .collect();
188    let mut order: Vec<usize> = (0..notes.len()).collect();
189    order.sort_by(|&left, &right| {
190        source.events()[notes[left].0]
191            .offset()
192            .total_cmp(&source.events()[notes[right].0].offset())
193    });
194    let notes: Vec<(usize, Pitch)> = order
195        .into_iter()
196        .map(|index| notes[index].clone())
197        .collect();
198
199    let comparison = options.comparison;
200    let step = options.step_size;
201    let mut degree_last: Option<usize> = None;
202    let mut pitch_last: Option<Pitch> = None;
203    let mut direction_last: Option<RunDirection> = None;
204    let mut degrees: BTreeSet<usize> = BTreeSet::new();
205    let mut elements: Vec<usize> = Vec::new();
206    let mut clear = false;
207    let mut clear_keeping_last = false;
208    let mut runs = Vec::new();
209
210    for (index, (place, pitch)) in notes.iter().enumerate() {
211        let next = notes.get(index + 1).map(|(_, next)| next);
212        let found_degree = degree(scale, pitch, direction_last, comparison)?;
213        match found_degree {
214            None => clear = true,
215            Some(found) => {
216                let collect = match (degree_last, &pitch_last) {
217                    (None, _) | (_, None) => true,
218                    (Some(last), _) if options.repeats_allowed && last == found => true,
219                    (Some(_), Some(previous)) => {
220                        if matches!(direction_last, None | Some(RunDirection::Ascending))
221                            && is_next(
222                                scale,
223                                Some(pitch),
224                                previous,
225                                Some(RunDirection::Ascending),
226                                step,
227                                comparison,
228                            )?
229                        {
230                            direction_last = Some(RunDirection::Ascending);
231                            true
232                        } else if matches!(direction_last, None | Some(RunDirection::Descending))
233                            && is_next(
234                                scale,
235                                Some(pitch),
236                                previous,
237                                Some(RunDirection::Descending),
238                                step,
239                                comparison,
240                            )?
241                        {
242                            direction_last = Some(RunDirection::Descending);
243                            true
244                        } else {
245                            clear_keeping_last = true;
246                            false
247                        }
248                    }
249                };
250                if collect {
251                    degrees.insert(found);
252                    elements.push(*place);
253                }
254            }
255        }
256        degree_last = found_degree;
257        pitch_last = Some(pitch.clone());
258
259        if degrees.len() >= options.degrees_required
260            && !is_next(scale, next, pitch, direction_last, 1, comparison)?
261        {
262            runs.push(ScaleRun {
263                elements: elements.clone(),
264                direction: direction_last,
265            });
266            if !clear && !clear_keeping_last {
267                let continues = is_next(
268                    scale,
269                    next,
270                    pitch,
271                    Some(RunDirection::Descending),
272                    step,
273                    comparison,
274                )? || is_next(
275                    scale,
276                    next,
277                    pitch,
278                    Some(RunDirection::Ascending),
279                    step,
280                    comparison,
281                )?;
282                if continues {
283                    clear_keeping_last = true;
284                } else {
285                    clear = true;
286                }
287            }
288        }
289        if clear {
290            degree_last = None;
291            direction_last = None;
292            degrees.clear();
293            elements.clear();
294            clear = false;
295        }
296        if clear_keeping_last {
297            direction_last = None;
298            degrees.clear();
299            // music21 keeps the degree the note was last found on, which
300            // is nothing where it is off the scale.
301            if let Some(found) = found_degree {
302                degrees.insert(found);
303            }
304            elements = vec![*place];
305            clear_keeping_last = false;
306        }
307    }
308    Ok(runs)
309}
310
311#[cfg(test)]
312mod tests {
313    use super::*;
314    use crate::note::Note;
315    use crate::scale::ScaleType;
316
317    fn line(names: &[&str]) -> Stream {
318        let mut stream = Stream::new();
319        for name in names {
320            stream.push(Note::from_name(name).unwrap());
321        }
322        stream
323    }
324
325    fn runs(names: &[&str], required: usize, comparison: PitchAttribute) -> Vec<(usize, String)> {
326        let source = line(names);
327        let a_major = Scale::new(ScaleType::Major, Pitch::from_name("A4").unwrap());
328        let options = ScaleRunOptions {
329            degrees_required: required,
330            comparison,
331            ..ScaleRunOptions::default()
332        };
333        find_consecutive_scale(&source, &a_major, &options)
334            .unwrap()
335            .into_iter()
336            .map(|run| {
337                let StreamElement::Note(first) = source.events()[run.elements[0]].element() else {
338                    unreachable!("a run holds notes")
339                };
340                (run.elements.len(), first.pitch().name_with_octave())
341            })
342            .collect()
343    }
344
345    /// music21's testFindConsecutiveScaleA.
346    #[test]
347    fn runs_are_found_as_music21_finds_them() {
348        use PitchAttribute::{Name, NameWithOctave};
349        let scale = ["a4", "b4", "c#4", "d4", "e4", "f#4", "g#4", "a4"];
350        assert_eq!(runs(&scale, 4, Name).len(), 1);
351        assert_eq!(runs(&scale, 4, Name)[0].0, 8);
352        assert_eq!(runs(&scale, 4, NameWithOctave)[0].0, 6);
353        let twice = ["a4", "b4", "c#5", "d5", "e5", "a4", "b4", "c#5", "d5", "e5"];
354        assert_eq!(
355            runs(&twice, 4, NameWithOctave)
356                .iter()
357                .map(|r| r.0)
358                .collect::<Vec<_>>(),
359            [5, 5]
360        );
361        let shifted = [
362            "a4", "b8", "c#3", "d3", "e4", "a4", "b9", "c#2", "d4", "e12",
363        ];
364        assert_eq!(
365            runs(&shifted, 4, Name)
366                .iter()
367                .map(|r| r.0)
368                .collect::<Vec<_>>(),
369            [5, 5]
370        );
371        let thrice = [
372            "a4", "b4", "c#5", "d-3", "a4", "b4", "c#5", "d-3", "a4", "b4", "c#5", "d-3",
373        ];
374        assert!(runs(&thrice, 4, NameWithOctave).is_empty());
375        assert_eq!(
376            runs(&thrice, 3, NameWithOctave)
377                .iter()
378                .map(|r| r.0)
379                .collect::<Vec<_>>(),
380            [3, 3, 3]
381        );
382
383        let up = ["c#5", "d3", "e4", "f#4", "g#4"];
384        let down = ["g#4", "f#4", "e4", "d3", "c#5"];
385        let turning: Vec<&str> = [up, down, up, down, down].concat();
386        assert!(runs(&turning, 5, NameWithOctave).is_empty());
387        let found = runs(&turning, 5, Name);
388        assert_eq!(
389            found.iter().map(|r| r.1.as_str()).collect::<Vec<_>>(),
390            ["C#5", "G#4", "C#5", "G#4", "G#4"]
391        );
392        assert!(found.iter().all(|run| run.0 == 5));
393
394        let mingled: Vec<&str> = [
395            &up[..],
396            &down,
397            &["g2", "e#7"],
398            &up,
399            &["a-2"],
400            &down,
401            &["a", "b"],
402            &down,
403        ]
404        .concat();
405        assert!(runs(&mingled, 5, NameWithOctave).is_empty());
406        let found = runs(&mingled, 5, Name);
407        assert_eq!(
408            found.iter().map(|r| r.1.as_str()).collect::<Vec<_>>(),
409            ["C#5", "G#4", "C#5", "G#4", "G#4"]
410        );
411    }
412}
music21/alpha/analysis/search.rs

music21/alpha/analysis/
search.rs
