Code for billiard scales: Difference between revisions

← Older edit Newer edit →

VisualWikitext

@@ Line 531: / Line 531: @@
 use crate::helpers::gcd;
 use crate::plane_geometry::{ConvexPolygon, Line, Point, PointLineConfiguration, Slope};
-use crate::words::{Letter, least_mode};
+pub type Letter = usize;
 // ERRORS
@@ Line 563: / Line 564: @@
 impl std::error::Error for BadBilliardState {}
+/// Rotate a scale word left by `degree` positions (change mode).
+///
+/// # Examples
+///
+/// ```
+/// use ternary::words::rotate;
+///
+/// let lydian = vec![0, 0, 0, 1, 0, 0, 1];
+/// let mixolydian = rotate(&lydian, 1);  // Rotate left by 1
+/// assert_eq!(mixolydian, vec![0, 0, 1, 0, 0, 1, 0]);
+/// ```
+pub fn rotate<T: std::clone::Clone>(slice: &[T], degree: usize) -> Vec<T> {
+    let degree = degree % slice.len();
+    if degree == 0 {
+        slice.to_vec()
+    } else {
+        [&slice[degree..slice.len()], &slice[0..degree]].concat()
+    }
+}
+/// The lexicographically least mode of a word (where the letters are in their usual order).
+///
+/// # Examples
+///
+/// ```
+/// use ternary::words::least_mode;
+///
+/// let ionian = vec![0, 0, 1, 0, 0, 0, 1]; // LLsLLLs
+/// let lydian = vec![0, 0, 0, 1, 0, 0, 1]; // LLLsLLs (lexicographically least mode of diatonic)
+/// assert_eq!(least_mode(&ionian), lydian)
+/// ```
+pub fn least_mode(scale: &[Letter]) -> Vec<Letter> {
+    rotate(scale, booth(scale))
+}
+/// The rotation required from the current word to the
+/// lexicographically least mode of a word.
+/// Booth's algorithm requires at most 3*n* comparisons and *n* storage locations where *n* is the input word's length.
+/// See Booth, K. S. (1980). Lexicographically least circular substrings.
+/// Information Processing Letters, 10(4-5), 240–242. doi:10.1016/0020-0190(80)90149-0
+pub fn booth(scale: &[Letter]) -> usize {
+    let scale_len = scale.len();
+    // `failure_func` is the failure function of the least rotation; `usize::MAX` is used as a null value.
+    // null indicates that the failure function does not point backwards in the string.
+    // `usize::MAX` will behave the same way as -1 does, assuming wrapping unsigned addition
+    let mut failure_func = vec![usize::MAX; 2 * scale_len];
+    let mut least_rotation: usize = 0;
+    // `scan_pos` loops over `scale` twice.
+    for scan_pos in 1..2 * scale_len {
+        let mut match_len = failure_func[scan_pos - least_rotation - 1];
+        while match_len != usize::MAX
+            && scale[scan_pos % scale_len]
+                != scale[least_rotation.wrapping_add(match_len).wrapping_add(1) % scale_len]
+        {
+            // (1) If the scan_pos-th letter is less than s[(least_rotation + match_len + 1) % scale_len] then change least_rotation to scan_pos - match_len - 1,
+            // in effect left-shifting the failure function and the input string.
+            // This appropriately compensates for the new, shorter least substring.
+            if scale[scan_pos % scale_len]
+                < scale[least_rotation.wrapping_add(match_len).wrapping_add(1) % scale_len]
+            {
+                least_rotation = scan_pos.wrapping_sub(match_len).wrapping_sub(1);
+            }
+            match_len = failure_func[match_len];
+        }
+        if match_len == usize::MAX
+            && scale[scan_pos % scale_len]
+                != scale[least_rotation.wrapping_add(match_len).wrapping_add(1) % scale_len]
+        {
+            // See note (1) above.
+            if scale[scan_pos % scale_len]
+                < scale[least_rotation.wrapping_add(match_len).wrapping_add(1) % scale_len]
+            {
+                least_rotation = scan_pos;
+            }
+            failure_func[scan_pos - least_rotation] = usize::MAX;
+        } else {
+            failure_func[scan_pos - least_rotation] = match_len.wrapping_add(1);
+        }
+        // The induction hypothesis is that
+        // at this point `failure_func[0..scan_pos - least_rotation]` is the failure function of `s[least_rotation..(least_rotation+scan_pos)%scale_len]`,
+        // and `least_rotation` is the lexicographically least subword of the letters scanned so far.
+    }
+    least_rotation
+}
 fn projected_constraint_planes(a: u32, b: u32, c: u32) -> (Vec<Line>, Vec<Line>, Vec<Line>) {
@@ Line 823: / Line 909: @@
 }
 </syntaxhighlight>
 === lib.rs ===
 <syntaxhighlight lang="rs">use std::collections::BTreeSet;