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 {}