bellframe/
block.rs

1//! A representation of a [`Block`] of ringing; i.e. a sort of 'multi-permutation' which takes a
2//! starting [`Row`] and yields a sequence of permuted [`Row`]s.
3
4use std::{
5    fmt::{Debug, Display, Formatter},
6    iter::repeat_with,
7    ops::RangeBounds,
8    slice,
9};
10
11use itertools::Itertools;
12
13use crate::{
14    row::{same_stage_vec, DbgRow},
15    utils, Bell, Row, RowBuf, SameStageVec, Stage,
16};
17
18/// A block of [`Row`], each of which can be given an annotation of any type.  Blocks can start
19/// from any [`Row`], and can be empty.
20///
21/// All blocks must finish with a 'left-over' [`Row`].  This [`Row`] denotes the first [`Row`] of
22/// any block rung **after** this one.  This is not considered part of the `Block`, and
23/// therefore cannot be annotated.  However, it is necessary - for example, if we create a `Block`
24/// for the first lead of Cambridge and Primrose Surprise Minor then they would be identical except
25/// for their 'left-over' row.
26#[derive(Clone, Eq, PartialEq, Hash)]
27pub struct Block<A> {
28    /// The [`Row`]s making up this `Block`.
29    ///
30    /// **Invariant**: `row.len() >= 1`
31    rows: SameStageVec,
32    /// The annotations on each [`Row`] in this `Block`.
33    ///
34    /// **Invariant**: `rows.len() = annots.len() + 1`, because the 'left-over' row cannot be annotated.
35    annots: Vec<A>,
36}
37
38impl<A> Block<A> {
39    //////////////////
40    // CONSTRUCTORS //
41    //////////////////
42
43    /// Parse a multi-line [`str`]ing into an `Block`, where each row is given the annotation
44    /// created by `A::default()`.  Each line in the string is interpreted as a [`Row`], with the
45    /// last row being 'left-over'.  The [`Stage`] is inferred from the first line.
46    pub fn parse(s: &str) -> Result<Self, ParseError>
47    where
48        A: Default,
49    {
50        let rows = SameStageVec::parse(s).map_err(ParseError::Other)?;
51        if rows.is_empty() {
52            // I'm not sure if this branch is even possible, since a zero-line string is
53            // impossible and `SameStageVec` attempts to parse every line as a [`Row`].  But for
54            // safety, it's here anyway
55            Err(ParseError::ZeroLengthBlock)
56        } else {
57            Ok(Self::with_default_annots(rows))
58        }
59    }
60
61    /// Creates a new `Block` from a [`SameStageVec`], where every annotation is
62    /// `A::default()`.
63    ///
64    /// # Panics
65    ///
66    /// This panics if the [`SameStageVec`] provided is empty.
67    pub fn with_default_annots(rows: SameStageVec) -> Self
68    where
69        A: Default,
70    {
71        assert!(!rows.is_empty());
72        Self {
73            annots: repeat_with(A::default).take(rows.len() - 1).collect_vec(),
74            rows,
75        }
76    }
77
78    /// Creates a new [`Block`] with no annotated [`Row`], and a leftover [`Row`] of
79    /// [`RowBuf::rounds`].
80    pub fn empty(stage: Stage) -> Self {
81        Self::with_leftover_row(RowBuf::rounds(stage))
82    }
83
84    /// Creates a new [`Block`] with no annotated [`Row`], and a given leftover [`Row`].
85    pub fn with_leftover_row(leftover_row: RowBuf) -> Self {
86        Self {
87            rows: SameStageVec::from_row_buf(leftover_row),
88            annots: vec![], // No annotations
89        }
90    }
91
92    /// Create an [`Block`] from a [`SameStageVec`] of [`Row`]s, where each annotation is
93    /// generated by calling a closure on its index within this block.  Returns `None` if the
94    /// [`SameStageVec`] contained no [`Row`]s.
95    pub fn with_annots_from_indices(rows: SameStageVec, f: impl FnMut(usize) -> A) -> Option<Self> {
96        let length_of_self = rows.len().checked_sub(1)?;
97        Some(Self {
98            annots: (0..length_of_self).map(f).collect_vec(),
99            rows,
100        })
101    }
102
103    /////////////////
104    // STAGE & LEN //
105    /////////////////
106
107    /// Gets the [`Stage`] of this `Block`.
108    #[inline]
109    pub fn stage(&self) -> Stage {
110        self.rows.stage()
111    }
112
113    /// Gets the effective [`Stage`] of this `Block` - i.e. the smallest [`Stage`] that this
114    /// `Block` can be reduced to without producing invalid [`Row`]s.  See
115    /// [`Row::effective_stage`] for more info and examples.
116    pub fn effective_stage(&self) -> Stage {
117        self.all_rows()
118            .map(Row::effective_stage)
119            .max()
120            // Unwrapping here is safe, because blocks must contain at least one Row
121            .unwrap()
122    }
123
124    /// Shorthand for `self.len() == 0`
125    #[inline]
126    pub fn is_empty(&self) -> bool {
127        self.annots.is_empty()
128    }
129
130    /// Gets the length of this `Block` (excluding the left-over [`Row`]).
131    #[inline]
132    pub fn len(&self) -> usize {
133        self.annots.len()
134    }
135
136    /////////////
137    // GETTERS //
138    /////////////
139
140    /// Gets the [`Row`] at a given index, along with its annotation.
141    #[inline]
142    pub fn get_row(&self, index: usize) -> Option<&Row> {
143        self.rows.get(index)
144    }
145
146    /// Gets an immutable reference to the annotation of the [`Row`] at a given index, if it
147    /// exists.
148    #[inline]
149    pub fn get_annot(&self, index: usize) -> Option<&A> {
150        self.annots.get(index)
151    }
152
153    /// Gets an mutable reference to the annotation of the [`Row`] at a given index, if it
154    /// exists.
155    #[inline]
156    pub fn get_annot_mut(&mut self, index: usize) -> Option<&mut A> {
157        self.annots.get_mut(index)
158    }
159
160    /// Gets the [`Row`] at a given index, along with its annotation.
161    #[inline]
162    pub fn get_annot_row(&self, index: usize) -> Option<(&A, &Row)> {
163        Some((self.get_annot(index)?, self.get_row(index)?))
164    }
165
166    /// Gets the first [`Row`] of this `Block`, which may be leftover.
167    #[inline]
168    pub fn first_row(&self) -> &Row {
169        // This `unwrap` won't panic, because we require an invariant that `self.row_buffer` is
170        // non-empty
171        self.rows.first().unwrap()
172    }
173
174    /// Gets the first [`Row`] of this `Block`, along with its annotation.
175    #[inline]
176    pub fn first_annot_row(&self) -> Option<(&A, &Row)> {
177        self.get_annot_row(0)
178    }
179
180    /// Returns an immutable reference to the 'left-over' [`Row`] of this `Block`.  This [`Row`]
181    /// represents the overall transposition of the `Block`, and should not be used when generating
182    /// rows for truth checking.
183    #[inline]
184    pub fn leftover_row(&self) -> &Row {
185        self.rows.last().unwrap()
186    }
187
188    /// Returns a mutable reference to the 'left-over' [`Row`] of this `Block`.  This [`Row`]
189    /// represents the overall transposition of the `Block`, and should not be used when generating
190    /// rows for truth checking.
191    #[inline]
192    pub fn leftover_row_mut(&mut self) -> &mut Row {
193        self.rows.last_mut().unwrap()
194    }
195
196    //////////////////////////////
197    // ITERATORS / PATH GETTERS //
198    //////////////////////////////
199
200    /// Returns an [`Iterator`] which yields the [`Row`]s which are directly part of this
201    /// `Block`.  This does not include the 'left-over' row; if you want to include the
202    /// left-over [`Row`], use [`Block::all_rows`] instead.
203    #[inline]
204    pub fn rows(&self) -> same_stage_vec::Iter {
205        let mut iter = self.all_rows();
206        iter.next_back(); // Remove the leftover row
207        iter
208    }
209
210    /// Returns an [`Iterator`] which yields all the [`Row`]s, including the leftover [`Row`].
211    #[inline]
212    pub fn all_rows(&self) -> same_stage_vec::Iter {
213        self.rows.iter()
214    }
215
216    /// Returns an [`Iterator`] which yields the annotations of this [`Block`], in
217    /// sequential order.
218    #[inline]
219    pub fn annots(&self) -> std::slice::Iter<A> {
220        self.annots.iter()
221    }
222
223    /// Returns an [`Iterator`] which yields the [`Row`]s which are directly part of this
224    /// `Block`.  This does not include the 'left-over' row; if you want to include the
225    /// left-over [`Row`], use [`Block::all_annot_rows`] instead.
226    #[inline]
227    pub fn annot_rows(&self) -> impl Iterator<Item = (&A, &Row)> + Clone {
228        self.annots().zip_eq(self.rows())
229    }
230
231    /// Returns an [`Iterator`] which yields the [`Row`]s which are directly part of this
232    /// `Block`.  This **does** include the 'left-over' row, which will have an annotation of
233    /// [`None`].
234    #[inline]
235    pub fn all_annot_rows(&self) -> impl Iterator<Item = (Option<&A>, &Row)> + Clone {
236        self.annots()
237            .map(Some)
238            .chain(std::iter::once(None))
239            .zip_eq(self.all_rows())
240    }
241
242    /// Returns the places of a given [`Bell`] in each [`Row`] of this `Block`.  Also returns
243    /// the place of `bell` in the leftover row.
244    pub fn path_of(&self, bell: Bell) -> (Vec<usize>, usize) {
245        let mut full_path = self.full_path_of(bell);
246        let place_in_leftover_row = full_path.pop().unwrap();
247        (full_path, place_in_leftover_row)
248    }
249
250    /// Returns the places of a given [`Bell`] in each [`Row`] of this `Block`, **including**
251    /// the leftover row.
252    pub fn full_path_of(&self, bell: Bell) -> Vec<usize> {
253        self.rows.path_of(bell) // Delegate to `SameStageVec`
254    }
255
256    /// An [`Iterator`] which yields the annotated [`Row`]s of `self` repeated forever.  This
257    /// [`Iterator`] never terminates.
258    ///
259    /// [`RepeatIter`] is an [`Iterator`] which yields [`RowBuf`]s, causing an allocation for each
260    /// call to `next`.  If those allocations are not desired, then use [`RepeatIter::next_into`]
261    /// instead to re-use an existing allocation.
262    pub fn repeat_iter(&self, start_row: RowBuf) -> RepeatIter<A> {
263        RepeatIter::new(start_row, self)
264    }
265
266    /////////////////////////
267    // IN-PLACE OPERATIONS //
268    /////////////////////////
269
270    /// Pre-multiplies every [`Row`] in this `Block` in-place by another [`Row`], whilst preserving
271    /// the annotations.
272    pub fn pre_multiply(&mut self, lhs_row: &Row) {
273        self.rows.pre_multiply(lhs_row) // Delegate to `SameStageVec`
274    }
275
276    /// Extends `self` with the contents of another [`Block`], **pre-multiplying** its [`Row`]s so
277    /// that it starts with `self`'s [`leftover_row`](Self::leftover_row).
278    pub fn extend(&mut self, other: &Self)
279    where
280        A: Clone,
281    {
282        self.extend_range(other, ..)
283    }
284
285    /// Extends `self` with a region of another [`Block`], **pre-multiplying** its [`Row`]s so
286    /// that it starts with `self`'s [`leftover_row`](Self::leftover_row).
287    ///
288    /// # Panics
289    ///
290    /// Panics if `range` explicitly states a bound outside `other.len()`
291    pub fn extend_range(&mut self, other: &Self, range: impl RangeBounds<usize>)
292    where
293        A: Clone,
294    {
295        let range = utils::clamp_range(range, other.len());
296
297        // `transposition` pre-multiplies `other`'s first row to `self`'s leftover row
298        let transposition =
299            Row::solve_xa_equals_b(other.get_row(range.start).unwrap(), self.leftover_row());
300
301        // Add the transposed rows to `self`
302        self.rows.pop(); // If we don't remove the leftover row, then it will get added twice
303        self.rows
304            .extend_range_transposed(&transposition, &other.rows, range.start..range.end + 1);
305
306        // Add the annotations to `self`
307        self.annots.extend_from_slice(&other.annots[range]);
308    }
309
310    /// Extends `self` with a chunk of itself, transposed to start with `self.leftover_row()`.
311    pub fn extend_from_within(&mut self, range: impl RangeBounds<usize> + Debug + Clone)
312    where
313        A: Clone + Debug,
314    {
315        // Clamp open ranges to `0..self.len()`, so our code only has to handle concrete `Range`s
316        let range = utils::clamp_range(range, self.len());
317
318        // Compute the pre-transposition required to make the chunk start at `self.leftover_row`
319        let first_row_of_chunk = self.get_row(range.start).unwrap();
320        // This unwrap is fine because stages must match because both rows were taken from the same
321        // `SameStageVec`
322        let transposition = Row::solve_xa_equals_b(first_row_of_chunk, self.leftover_row());
323
324        // Extend the rows
325        self.rows
326            // The range is offset by 1 to exclude the current `leftover_row` of `self`, but
327            // include the new leftover row
328            .extend_transposed_from_within(range.start + 1..range.end + 1, &transposition);
329        self.annots.extend_from_within(range);
330    }
331
332    ///////////////////////////////////
333    // OPERATIONS WHICH CONSUME SELF //
334    ///////////////////////////////////
335
336    /// Consumes this `Block`, and returns a [`SameStageVec`] containing the same [`Row`]s,
337    /// **including** the left-over row.
338    pub fn into_rows(self) -> SameStageVec {
339        self.rows
340    }
341
342    /// Borrows the [`SameStageVec`] which contains all the [`Row`]s in this `Block`
343    pub fn row_vec(&self) -> &SameStageVec {
344        &self.rows
345    }
346
347    /// Convert this `Block` into another `Block` with identical [`Row`]s, but where each
348    /// annotation is passed through the given function.
349    pub fn map_annots<B>(self, f: impl Fn(A) -> B) -> Block<B> {
350        Block {
351            rows: self.rows, // Don't modify the rows
352            annots: self.annots.into_iter().map(f).collect_vec(),
353        }
354    }
355
356    /// Convert this `Block` into another `Block` with identical [`Row`]s, but where each
357    /// annotation is passed through the given function (along with its index within the
358    /// `Block`).
359    pub fn map_annots_with_index<B>(self, f: impl Fn(usize, A) -> B) -> Block<B> {
360        Block {
361            rows: self.rows, // Don't modify the rows
362            annots: self
363                .annots
364                .into_iter()
365                .enumerate()
366                .map(|(i, annot)| f(i, annot))
367                .collect_vec(),
368        }
369    }
370
371    /// Convert this `Block` into another `Block` with identical [`Row`]s, but where each
372    /// annotation is passed through the given function (along with its index within the
373    /// `Block`).
374    pub fn clone_map_annots_with_index<'s, B>(&'s self, f: impl Fn(usize, &'s A) -> B) -> Block<B> {
375        Block {
376            rows: self.rows.to_owned(), // Don't modify the rows
377            annots: self
378                .annots
379                .iter()
380                .enumerate()
381                .map(|(i, annot)| f(i, annot))
382                .collect_vec(),
383        }
384    }
385
386    /// Splits this `Block` into two separate `Block`s at a specified index.  This is
387    /// defined such the first `Block` has length `index`.  This returns `None` if the second
388    /// `Block` would have negative length.
389    pub fn split(self, index: usize) -> Option<(Self, Self)> {
390        let (first_annots, second_annots) = utils::split_vec(self.annots, index)?;
391        let (mut first_rows, second_rows) = self.rows.split(index)?;
392        // Copy the first row of `second_rows` back into `first_rows` so it becomes the leftover
393        // row of the first block
394        let first_row_of_second = second_rows.first().unwrap(); // Unwrap is safe because
395                                                                // `self.row_buffer.len() > index + 1`
396        first_rows.push(first_row_of_second); // Won't panic because both rows came from `self.row_buffer`
397
398        // Construct the new pair of blocks
399        let first_block = Self {
400            rows: first_rows,
401            annots: first_annots,
402        };
403        let second_block = Self {
404            rows: second_rows,
405            annots: second_annots,
406        };
407        Some((first_block, second_block))
408    }
409}
410
411////////////////
412// FORMATTING //
413////////////////
414
415impl<T> Debug for Block<T>
416where
417    T: Debug,
418{
419    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
420        /// Struct which debug prints as `K: V`
421        struct Pair<K, V>(K, V);
422
423        impl<K, V> Debug for Pair<K, V>
424        where
425            K: Debug,
426            V: Debug,
427        {
428            fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
429                write!(f, "{:?}: {:?}", self.0, self.1)
430            }
431        }
432
433        let mut builder = f.debug_tuple(stringify!(Block));
434        for (annot, row) in self.annot_rows() {
435            // Format all annotated rows as `row: annot`
436            builder.field(&Pair(DbgRow(row), annot));
437        }
438        // Format the leftover row as `row` (since it has no annotation)
439        builder.field(&DbgRow(self.leftover_row()));
440        builder.finish()
441    }
442}
443
444////////////////////////////////////////////////////////////////////////////////////////////////////
445
446/// Iterator used internally by [`RepeatIter`], which yields the (&Row, &annotation) pairs from an
447/// [`Block`].
448type InnerIter<'b, A> =
449    std::iter::Enumerate<itertools::ZipEq<same_stage_vec::Iter<'b>, slice::Iter<'b, A>>>;
450
451/// An [`Iterator`] which yields an [`Block`] forever.  Created with
452/// [`Block::repeat_iter`].
453#[derive(Clone)]
454pub struct RepeatIter<'b, A> {
455    /// Invariant: `self.current_block_head` must have the same [`Stage`] as `self.block`
456    current_block_head: RowBuf,
457    iter: InnerIter<'b, A>,
458    block: &'b Block<A>,
459}
460
461impl<'b, A> RepeatIter<'b, A> {
462    fn new(start_row: RowBuf, block: &'b Block<A>) -> Self {
463        Self {
464            current_block_head: start_row,
465            iter: Self::get_iter(block),
466            block,
467        }
468    }
469
470    /// Same as `self.next` but re-uses an existing allocation.
471    #[must_use]
472    pub fn next_into(&mut self, out: &mut RowBuf) -> Option<(usize, &'b A)> {
473        let (source_idx, (untransposed_row, annot)) = self.next_untransposed_row()?;
474        self.current_block_head.mul_into(untransposed_row, out);
475        Some((source_idx, annot))
476    }
477
478    fn get_iter(block: &'b Block<A>) -> InnerIter<'b, A> {
479        block.rows().zip_eq(block.annots()).enumerate()
480    }
481
482    fn next_untransposed_row(&mut self) -> Option<(usize, (&'b Row, &'b A))> {
483        self.iter.next().or_else(|| {
484            // Apply the block we've just finished to the block head
485            self.current_block_head = self.current_block_head.as_row() * self.block.leftover_row();
486            // Start a new block
487            self.iter = Self::get_iter(self.block);
488            // Get the first row/annot of the next block.  If `self.iter.next()` is None, then the
489            // block must be empty, and `self` should finish immediately
490            self.iter.next()
491        })
492    }
493}
494
495impl<'b, A> Iterator for RepeatIter<'b, A> {
496    type Item = (RowBuf, usize, &'b A);
497
498    fn next(&mut self) -> Option<Self::Item> {
499        let (source_idx, (untransposed_row, annot)) = self.next_untransposed_row()?;
500        let next_row = self.current_block_head.as_row() * untransposed_row;
501        Some((next_row, source_idx, annot))
502    }
503}
504
505////////////////////////////////////////////////////////////////////////////////////////////////////
506
507/// The possible ways that [`Block::parse`] could fail
508#[derive(Debug, Clone)]
509pub enum ParseError {
510    ZeroLengthBlock,
511    Other(same_stage_vec::ParseError),
512}
513
514impl Display for ParseError {
515    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
516        match self {
517            ParseError::ZeroLengthBlock => write!(f, "Blocks must contain at least one row"),
518            ParseError::Other(inner) => write!(f, "{}", inner),
519        }
520    }
521}
522
523impl std::error::Error for ParseError {}