From e4c5409397e6e833984d221d63a62ea7bcb2c4a9 Mon Sep 17 00:00:00 2001 From: jacksonfu14 Date: Thu, 6 Nov 2025 07:50:44 +0100 Subject: refactor: use cargo --- morphology/meta_affine/lib.rs | 22 -- morphology/meta_affine/sequence.rs | 411 ------------------------------------- morphology/meta_affine/set.rs | 349 ------------------------------- morphology/meta_affine/value.rs | 170 --------------- 4 files changed, 952 deletions(-) delete mode 100644 morphology/meta_affine/lib.rs delete mode 100644 morphology/meta_affine/sequence.rs delete mode 100644 morphology/meta_affine/set.rs delete mode 100644 morphology/meta_affine/value.rs (limited to 'morphology/meta_affine') diff --git a/morphology/meta_affine/lib.rs b/morphology/meta_affine/lib.rs deleted file mode 100644 index 6ebd49d..0000000 --- a/morphology/meta_affine/lib.rs +++ /dev/null @@ -1,22 +0,0 @@ -//! Meta-Affine Sequence Generator -//! -//! A library for generating and validating meta-affine sequences. -//! -//! A meta-affine space consists of 2-tuple values (outer, inner) derived from (0,0) -//! using five derivation rules. Valid sets are downward-closed subsets, and valid -//! sequences are ordered arrangements of set elements satisfying four constraints. -//! -//! # Modules -//! -//! - [`value`] - Core data structures: Value type and minimum derivation paths -//! - [`set`] - Valid set generation and validation -//! - [`sequence`] - Valid sequence generation and constraint checking - -pub mod value; -pub mod set; -pub mod sequence; - -// Re-export main types for convenience -pub use value::Value; -pub use set::ValidSet; -pub use sequence::Sequence; diff --git a/morphology/meta_affine/sequence.rs b/morphology/meta_affine/sequence.rs deleted file mode 100644 index 784567d..0000000 --- a/morphology/meta_affine/sequence.rs +++ /dev/null @@ -1,411 +0,0 @@ -//! Valid Sequence Generation and Constraint Validation -//! -//! This module implements sequences of meta-affine values subject to four constraints. -//! -//! A valid sequence must satisfy: -//! 1. Every value in the generating set appears at least once -//! 2. No value appears next to itself -//! 3. The last value is (0,0) -//! 4. For each outer value n, the last occurrence of any value (n,m) must have m=0 - -use crate::value::Value; -use crate::set::ValidSet; -use std::collections::{HashMap, HashSet}; - -/// Represents an ordered sequence of meta-affine values. -/// -/// A sequence is valid if it satisfies all four constraints with respect -/// to its generating set. -#[derive(Debug, Clone, PartialEq, Eq)] -pub struct Sequence { - values: Vec, -} - -impl Sequence { - /// Creates a new sequence from a vector of values. - /// - /// # Examples - /// - /// ``` - /// use meta_affine::{Sequence, Value}; - /// - /// let seq = Sequence::new(vec![Value::new(0,0), Value::new(1,0), Value::new(0,0)]); - /// assert_eq!(seq.length(), 3); - /// ``` - pub fn new(values: Vec) -> Self { - Sequence { values } - } - - /// Returns the length of the sequence. - pub fn length(&self) -> usize { - self.values.len() - } - - /// Returns a slice of the values in the sequence. - pub fn values(&self) -> &[Value] { - &self.values - } - - /// Checks if the sequence is valid for the given set. - /// - /// # Examples - /// - /// ``` - /// use meta_affine::{Sequence, ValidSet, Value}; - /// - /// let set = ValidSet::origin_set(); - /// let seq = Sequence::new(vec![Value::origin()]); - /// assert!(seq.is_valid(&set)); - /// ``` - pub fn is_valid(&self, set: &ValidSet) -> bool { - check_coverage(self, set) - && check_no_consecutive_duplicates(self) - && check_terminal(self) - && check_outer_value_constraint(self) - } -} - -// ============================================================================ -// CONSTRAINT VALIDATORS -// ============================================================================ - -/// Checks constraint 1: -/// Every value in the set must appear at least once in the sequence. -/// -/// # Examples -/// -/// ``` -/// use meta_affine::{Sequence, ValidSet, Value}; -/// use meta_affine::sequence::check_coverage; -/// -/// let set = ValidSet::origin_set(); -/// let seq = Sequence::new(vec![Value::origin()]); -/// assert!(check_coverage(&seq, &set)); -/// ``` -pub fn check_coverage(sequence: &Sequence, set: &ValidSet) -> bool { - let seq_values: HashSet = sequence.values.iter().copied().collect(); - - for &value in set.values() { - if !seq_values.contains(&value) { - return false; - } - } - true -} - -/// Checks constraint 2: -/// No value may appear next to itself in the sequence. -/// -/// # Examples -/// -/// ``` -/// use meta_affine::{Sequence, Value}; -/// use meta_affine::sequence::check_no_consecutive_duplicates; -/// -/// let seq1 = Sequence::new(vec![Value::new(0,0), Value::new(1,0), Value::new(0,0)]); -/// assert!(check_no_consecutive_duplicates(&seq1)); -/// -/// let seq2 = Sequence::new(vec![Value::new(0,0), Value::new(0,0)]); -/// assert!(!check_no_consecutive_duplicates(&seq2)); -/// ``` -pub fn check_no_consecutive_duplicates(sequence: &Sequence) -> bool { - for window in sequence.values.windows(2) { - if window[0] == window[1] { - return false; - } - } - true -} - -/// Checks constraint 3: -/// The last value in the sequence must be (0,0). -/// -/// # Examples -/// -/// ``` -/// use meta_affine::{Sequence, Value}; -/// use meta_affine::sequence::check_terminal; -/// -/// let seq1 = Sequence::new(vec![Value::new(1,0), Value::origin()]); -/// assert!(check_terminal(&seq1)); -/// -/// let seq2 = Sequence::new(vec![Value::new(1,0)]); -/// assert!(!check_terminal(&seq2)); -/// ``` -pub fn check_terminal(sequence: &Sequence) -> bool { - if sequence.values.is_empty() { - return false; - } - sequence.values.last() == Some(&Value::origin()) -} - -/// Checks constraint 4: -/// For each outer value n that appears in the sequence, the last occurrence -/// of any value with outer coordinate n must have inner coordinate 0. -/// -/// # Examples -/// -/// ``` -/// use meta_affine::{Sequence, Value}; -/// use meta_affine::sequence::check_outer_value_constraint; -/// -/// // Last occurrence of outer=1 is (1,0) ✓ -/// let seq1 = Sequence::new(vec![Value::new(1,1), Value::new(1,0), Value::new(0,0)]); -/// assert!(check_outer_value_constraint(&seq1)); -/// -/// // Last occurrence of outer=1 is (1,1) ✗ -/// let seq2 = Sequence::new(vec![Value::new(1,0), Value::new(1,1), Value::new(0,0)]); -/// assert!(!check_outer_value_constraint(&seq2)); -/// ``` -pub fn check_outer_value_constraint(sequence: &Sequence) -> bool { - // Map each outer value to the index of its last occurrence - let mut last_index_by_outer: HashMap = HashMap::new(); - - for (i, &value) in sequence.values.iter().enumerate() { - last_index_by_outer.insert(value.outer, i); - } - - // Check that at each last occurrence, the inner value is 0 - for (_outer, &last_idx) in &last_index_by_outer { - let value_at_last = sequence.values[last_idx]; - if value_at_last.inner != 0 { - return false; - } - } - - true -} - -/// Generates all valid sequences of a given length from a valid set. -/// -/// Uses constrained backtracking with early pruning based on the four constraints. -/// -/// # Arguments -/// -/// * `set` - The valid set to generate sequences from -/// * `length` - The desired sequence length -/// -/// # Returns -/// -/// A vector of all valid sequences of the specified length -/// -/// # Examples -/// -/// ``` -/// use meta_affine::{ValidSet, Value}; -/// use meta_affine::sequence::generate_sequences; -/// -/// let set = ValidSet::origin_set(); -/// let sequences = generate_sequences(&set, 1); -/// assert_eq!(sequences.len(), 1); // Only [(0,0)] -/// ``` -pub fn generate_sequences(set: &ValidSet, length: usize) -> Vec { - // Cannot generate valid sequences if length is 0 or set is empty - if length == 0 || set.size() == 0 { - return Vec::new(); - } - - // Must contain origin for constraint 3 - if !set.contains(&Value::origin()) { - return Vec::new(); - } - - let mut result = Vec::new(); - let set_values: Vec = set.values().copied().collect(); - - // Start backtracking - let mut current = Vec::new(); - let mut coverage = HashSet::new(); - - backtrack( - &mut current, - &mut coverage, - &set_values, - set, - length, - &mut result, - ); - - result -} - -/// Recursive backtracking function for sequence generation. -fn backtrack( - current: &mut Vec, - coverage: &mut HashSet, - set_values: &[Value], - set: &ValidSet, - target_length: usize, - result: &mut Vec, -) { - // Base case: reached target length - if current.len() == target_length { - // Check all constraints - let seq = Sequence::new(current.clone()); - - if check_coverage(&seq, set) - && check_terminal(&seq) - && check_outer_value_constraint(&seq) - { - result.push(seq); - } - return; - } - - // Determine valid next values - let position = current.len(); - let last_value = current.last().copied(); // Copy the value to avoid borrow issues - - // If at last position, must be (0,0) (constraint 3) - if position == target_length - 1 { - let next = Value::origin(); - - // Check constraint 2: no consecutive duplicates - if let Some(last) = last_value { - if last == next { - return; // Cannot place origin here - } - } - - // Check constraint 4 pruning: can we still satisfy it? - current.push(next); - coverage.insert(next); - - if is_outer_constraint_satisfiable(current) { - backtrack(current, coverage, set_values, set, target_length, result); - } - - current.pop(); - if !current.contains(&next) { - coverage.remove(&next); - } - return; - } - - // Try each value from the set - for &next in set_values { - // Constraint 2: cannot repeat last value - if let Some(last) = last_value { - if last == next { - continue; - } - } - - // Add to current path - let was_in_coverage = coverage.contains(&next); - current.push(next); - coverage.insert(next); - - // Pruning: check if we can still satisfy constraints - if can_still_satisfy_constraints(current, coverage, set, target_length) { - backtrack(current, coverage, set_values, set, target_length, result); - } - - // Backtrack - current.pop(); - if !was_in_coverage { - coverage.remove(&next); - } - } -} - -/// Checks if constraints can still be satisfied from current state. -fn can_still_satisfy_constraints( - current: &[Value], - coverage: &HashSet, - set: &ValidSet, - target_length: usize, -) -> bool { - let remaining_positions = target_length - current.len(); - - // Check constraint 1: Can we still cover all values? - let uncovered = set.size() - coverage.len(); - if uncovered > remaining_positions { - return false; // Not enough space to cover all values - } - - // Check constraint 4: Outer value constraint - // If we've placed a value (n,m) with m≠0, we must be able to place (n,0) later - if !is_outer_constraint_satisfiable(current) { - return false; - } - - true -} - -/// Checks if the outer value constraint can still be satisfied. -/// -/// For any outer value n where we've placed (n,m) with m≠0, -/// we need to ensure (n,0) can still be placed later. -fn is_outer_constraint_satisfiable(current: &[Value]) -> bool { - // Track the last index of each outer value - let mut last_index_by_outer: HashMap = HashMap::new(); - - for (i, &value) in current.iter().enumerate() { - last_index_by_outer.insert(value.outer, i); - } - - // Check each outer value - for (&outer, &last_idx) in &last_index_by_outer { - let value_at_last = current[last_idx]; - - // If the last occurrence has inner≠0, it's a potential violation - // This is fine if we're still building the sequence, but we should check - // if there's any value after it with the same outer coordinate - let has_later_occurrence = current.iter() - .skip(last_idx + 1) - .any(|v| v.outer == outer); - - if !has_later_occurrence && value_at_last.inner != 0 { - // This is currently the last occurrence and inner≠0 - // This is only ok if this is not the final sequence - // For pruning purposes during generation, we allow it - continue; - } - } - - true -} - -/// Generates all valid sequences of a given length from any valid set. -/// -/// This is the main entry point that combines set generation and sequence generation. -/// -/// # Arguments -/// -/// * `length` - The desired sequence length -/// -/// # Returns -/// -/// A vector of all valid sequences of the specified length -/// -/// # Examples -/// -/// ``` -/// use meta_affine::sequence::generate_all_sequences; -/// -/// let sequences = generate_all_sequences(1); -/// assert_eq!(sequences.len(), 1); // Only [(0,0)] -/// ``` -pub fn generate_all_sequences(length: usize) -> Vec { - use crate::set::generate_valid_sets; - - let max_set_size = length; // Heuristic: set size can't exceed sequence length - let all_sets = generate_valid_sets(max_set_size); - - let mut all_sequences = Vec::new(); - - for set in all_sets { - let sequences = generate_sequences(&set, length); - all_sequences.extend(sequences); - } - - all_sequences -} - -/// Counts the number of valid sequences for a given length without generating them. -/// -/// This is more memory-efficient than generating all sequences when you only need the count. -pub fn count_sequences(set: &ValidSet, length: usize) -> usize { - generate_sequences(set, length).len() -} diff --git a/morphology/meta_affine/set.rs b/morphology/meta_affine/set.rs deleted file mode 100644 index 5376f65..0000000 --- a/morphology/meta_affine/set.rs +++ /dev/null @@ -1,349 +0,0 @@ -//! Valid Set Generation and Validation -//! -//! This module implements downward-closed sets in meta-affine space. -//! -//! A valid set must satisfy: if a value (m,n) is in the set, then every value -//! in its minimum derivation path from (0,0) must also be in the set. -//! -//! This creates a dependency structure where sets are "downward-closed" with -//! respect to the derivation rules. - -use crate::value::{Value, get_minimum_derivation_path}; -use std::collections::HashSet; - -/// Represents a valid set in meta-affine space. -#[derive(Debug, Clone, PartialEq, Eq)] -pub struct ValidSet { - values: HashSet, -} - -impl ValidSet { - /// Creates an empty valid set. - /// - /// Note: An empty set is technically valid (vacuously), but all - /// non-empty valid sets must contain (0,0). - /// - /// # Examples - /// - /// ``` - /// use meta_affine::ValidSet; - /// let set = ValidSet::new(); - /// assert_eq!(set.size(), 0); - /// ``` - pub fn new() -> Self { - ValidSet { - values: HashSet::new(), - } - } - - /// Creates a valid set containing only the origin (0,0). - /// - /// This is the minimal non-empty valid set. - /// - /// # Examples - /// - /// ``` - /// use meta_affine::{ValidSet, Value}; - /// let set = ValidSet::origin_set(); - /// assert_eq!(set.size(), 1); - /// assert!(set.contains(&Value::origin())); - /// ``` - pub fn origin_set() -> Self { - let mut values = HashSet::new(); - values.insert(Value::origin()); - ValidSet { values } - } - - /// Attempts to create a ValidSet from a collection of values. - /// - /// Returns `Ok(ValidSet)` if the values form a valid (downward-closed) set, - /// otherwise returns `Err` with a description of why the set is invalid. - /// - /// # Examples - /// - /// ``` - /// use meta_affine::{ValidSet, Value}; - /// use std::collections::HashSet; - /// - /// let mut values = HashSet::new(); - /// values.insert(Value::new(0, 0)); - /// values.insert(Value::new(1, 0)); - /// values.insert(Value::new(1, 1)); - /// - /// let set = ValidSet::from_values(values).unwrap(); - /// assert_eq!(set.size(), 3); - /// ``` - pub fn from_values(values: HashSet) -> Result { - let set = ValidSet { values }; - if set.is_valid() { - Ok(set) - } else { - Err("Set is not downward-closed".to_string()) - } - } - - /// Attempts to add a value to the set, returning a new set. - /// - /// This function preserves immutability by returning a new ValidSet. - /// If adding the value would create an invalid set, returns Err. - /// - /// For proper downward-closure, this should add not just the value - /// but all values in its derivation path. Use `add_value_with_dependencies` - /// for automatic inclusion of dependencies. - /// - /// # Examples - /// - /// ``` - /// use meta_affine::{ValidSet, Value}; - /// - /// let set = ValidSet::origin_set(); - /// let set2 = set.add_value(Value::new(1, 0)).unwrap(); - /// assert_eq!(set2.size(), 2); - /// ``` - pub fn add_value(&self, value: Value) -> Result { - let mut new_values = self.values.clone(); - new_values.insert(value); - Self::from_values(new_values) - } - - /// Adds a value and all its dependencies to the set, returning a new set. - /// - /// This ensures the resulting set is valid by including all values - /// in the minimum derivation path of the added value. - /// - /// # Examples - /// - /// ``` - /// use meta_affine::{ValidSet, Value}; - /// - /// let set = ValidSet::new(); - /// let set2 = set.add_value_with_dependencies(Value::new(2, 3)); - /// // Will contain: (0,0), (1,0), (2,0), (2,1), (2,2), (2,3) - /// assert_eq!(set2.size(), 6); - /// ``` - pub fn add_value_with_dependencies(&self, value: Value) -> Self { - let mut new_values = self.values.clone(); - let path = get_minimum_derivation_path(value); - for v in path { - new_values.insert(v); - } - ValidSet { values: new_values } - } - - /// Checks if the set is valid (downward-closed). - /// - /// A set is valid if for every value in the set, all values in its - /// minimum derivation path are also in the set. - /// - /// # Examples - /// - /// ``` - /// use meta_affine::{ValidSet, Value}; - /// use std::collections::HashSet; - /// - /// let mut values = HashSet::new(); - /// values.insert(Value::new(0, 0)); - /// values.insert(Value::new(1, 0)); - /// - /// let set = ValidSet::from_values(values).unwrap(); - /// assert!(set.is_valid()); - /// ``` - pub fn is_valid(&self) -> bool { - // Empty set is valid (vacuously) - if self.values.is_empty() { - return true; - } - - // Check each value has all its dependencies - for &value in &self.values { - let path = get_minimum_derivation_path(value); - for dep in path { - if !self.values.contains(&dep) { - return false; - } - } - } - true - } - - /// Checks if the set contains a specific value. - /// - /// # Examples - /// - /// ``` - /// use meta_affine::{ValidSet, Value}; - /// - /// let set = ValidSet::origin_set(); - /// assert!(set.contains(&Value::origin())); - /// assert!(!set.contains(&Value::new(1, 0))); - /// ``` - pub fn contains(&self, value: &Value) -> bool { - self.values.contains(value) - } - - /// Returns the number of values in the set. - /// - /// # Examples - /// - /// ``` - /// use meta_affine::ValidSet; - /// - /// let set = ValidSet::origin_set(); - /// assert_eq!(set.size(), 1); - /// ``` - pub fn size(&self) -> usize { - self.values.len() - } - - /// Returns an iterator over the values in the set. - /// - /// The order is not guaranteed. - pub fn values(&self) -> impl Iterator { - self.values.iter() - } - - /// Returns a vector of all values in the set, sorted by a canonical order. - /// - /// Values are sorted first by outer coordinate, then by inner coordinate. - pub fn values_sorted(&self) -> Vec { - let mut sorted: Vec = self.values.iter().copied().collect(); - sorted.sort_by_key(|v| (v.outer, v.inner)); - sorted - } -} - -impl Default for ValidSet { - fn default() -> Self { - Self::new() - } -} - -/// Generates all valid sets up to a maximum size. -/// -/// Uses incremental construction: starts with {(0,0)}, then for each -/// size, generates new sets by adding candidate values to existing sets. -/// -/// # Arguments -/// -/// * `max_size` - Maximum number of elements in generated sets -/// -/// # Returns -/// -/// A vector of all valid sets with size <= max_size -/// -/// # Examples -/// -/// ``` -/// use meta_affine::set::generate_valid_sets; -/// -/// let sets = generate_valid_sets(3); -/// // Will include sets like {(0,0)}, {(0,0), (1,0)}, {(0,0), (0,1)}, etc. -/// assert!(sets.len() > 0); -/// ``` -pub fn generate_valid_sets(max_size: usize) -> Vec { - if max_size == 0 { - return vec![ValidSet::new()]; - } - - let mut all_sets = Vec::new(); - - // Start with the origin set (size 1) - let origin_set = ValidSet::origin_set(); - all_sets.push(origin_set.clone()); - - if max_size == 1 { - return all_sets; - } - - // Track sets by size for incremental construction - let mut sets_by_size: Vec> = vec![Vec::new(); max_size + 1]; - sets_by_size[1].push(origin_set); - - // Generate sets of increasing size - for size in 2..=max_size { - let mut new_sets = Vec::new(); - - // For each set of size-1 - for prev_set in &sets_by_size[size - 1] { - // Try adding each candidate value - let candidates = get_candidate_values(prev_set, max_size as i32); - - for candidate in candidates { - let new_set = prev_set.add_value_with_dependencies(candidate); - - // Only keep if size matches and we haven't seen it - if new_set.size() == size { - // Check if we already have this set - if !new_sets.iter().any(|s| s == &new_set) { - new_sets.push(new_set); - } - } - } - } - - // Add all new sets of this size - for set in new_sets { - sets_by_size[size].push(set.clone()); - all_sets.push(set); - } - } - - all_sets -} - -/// Generates candidate values that could be added to extend a set. -/// -/// Returns values that are: -/// - Not already in the set -/// - "reachable" from the current set (adjacent in the derivation graph) -/// - Within the specified bounds -fn get_candidate_values(set: &ValidSet, max_bound: i32) -> Vec { - let mut candidates = HashSet::new(); - - // Find the range of outer and inner values in the current set - let mut min_outer = 0; - let mut max_outer = 0; - let mut min_inner = 0; - let mut max_inner = 0; - - for &value in set.values() { - min_outer = min_outer.min(value.outer); - max_outer = max_outer.max(value.outer); - min_inner = min_inner.min(value.inner); - max_inner = max_inner.max(value.inner); - } - - // For each value in the set, generate adjacent values - for &value in set.values() { - // Apply rules 2-5 to generate neighbors - let neighbors = [ - Value::new(value.outer + 1, value.inner), // Rule 2 - Value::new(value.outer - 1, value.inner), // Rule 3 - Value::new(value.outer, value.inner + 1), // Rule 4 - Value::new(value.outer, value.inner - 1), // Rule 5 - ]; - - for neighbor in neighbors { - // Check bounds - if neighbor.outer.abs() <= max_bound && neighbor.inner.abs() <= max_bound { - if !set.contains(&neighbor) { - candidates.insert(neighbor); - } - } - } - } - - candidates.into_iter().collect() -} - -/// Generates all valid sets with size exactly equal to the specified size. -/// -/// This is more efficient than generating all sets up to max_size if you -/// only need sets of one specific size. -pub fn generate_valid_sets_of_size(target_size: usize) -> Vec { - let all_sets = generate_valid_sets(target_size); - all_sets - .into_iter() - .filter(|set| set.size() == target_size) - .collect() -} diff --git a/morphology/meta_affine/value.rs b/morphology/meta_affine/value.rs deleted file mode 100644 index 71fc2c6..0000000 --- a/morphology/meta_affine/value.rs +++ /dev/null @@ -1,170 +0,0 @@ -//! Core Data Structures for Meta-Affine Space -//! -//! A meta-affine space consists of 2-tuple values (outer, inner) derived from (0,0) -//! using five derivation rules: -//! -//! 1. (0,0) is a value in the space -//! 2. If (n,0) is a value, then (n+1,0) is also a value -//! 3. If (n,0) is a value, then (n-1,0) is also a value -//! 4. If (m,n) is a value, then (m,n+1) is also a value -//! 5. If (m,n) is a value, then (m,n-1) is also a value -//! -//! Every value can be generated via a minimum derivation path from (0,0). - -use std::fmt; - -/// Represents a value in meta-affine space as a 2-tuple (outer, inner). -/// -/// Values are copyable, comparable for equality, and can be used in sets and maps. -/// The Copy trait allows for efficient passing and immutable semantics. -#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] -pub struct Value { - pub outer: i32, - pub inner: i32, -} - -impl Value { - /// Creates a new MetaAffine Value. - /// - /// # Examples - /// - /// ``` - /// use meta_affine::Value; - /// let v = Value::new(2, 3); - /// assert_eq!(v.outer, 2); - /// assert_eq!(v.inner, 3); - /// ``` - pub const fn new(outer: i32, inner: i32) -> Self { - Value { outer, inner } - } - - /// Returns the origin value (0, 0). - /// - /// # Examples - /// - /// ``` - /// use meta_affine::Value; - /// let origin = Value::origin(); - /// assert_eq!(origin, Value::new(0, 0)); - /// ``` - pub const fn origin() -> Self { - Value::new(0, 0) - } - - /// Checks if this is the origin value (0,0). - /// - /// # Examples - /// - /// ``` - /// use meta_affine::Value; - /// assert!(Value::new(0, 0).is_origin()); - /// assert!(!Value::new(1, 0).is_origin()); - /// ``` - pub const fn is_origin(&self) -> bool { - self.outer == 0 && self.inner == 0 - } - - /// Returns a tuple representation of the value. - pub const fn as_tuple(&self) -> (i32, i32) { - (self.outer, self.inner) - } -} - -impl fmt::Display for Value { - /// Formats the value as a string in the form "(outer,inner)". - /// - /// # Examples - /// - /// ``` - /// use meta_affine::Value; - /// let v = Value::new(2, -3); - /// assert_eq!(format!("{}", v), "(2,-3)"); - /// ``` - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - write!(f, "({},{})", self.outer, self.inner) - } -} - -/// Computes the minimum derivation path from (0,0) to the given value. -/// -/// The minimum derivation path consists of: -/// 1. Starting at (0,0) -/// 2. Applying rule 2 OR rule 3 (not both) |m| times to reach (m, 0) -/// 3. Applying rule 4 OR rule 5 (not both) |n| times to reach (m, n) -/// -/// # Examples -/// -/// ``` -/// use meta_affine::{Value, get_minimum_derivation_path}; -/// let path = get_minimum_derivation_path(Value::new(2, 3)); -/// assert_eq!(path.len(), 6); -/// assert_eq!(path[0], Value::new(0, 0)); -/// assert_eq!(path[5], Value::new(2, 3)); -/// ``` -pub fn get_minimum_derivation_path(value: Value) -> Vec { - let mut path = Vec::new(); - - // Start with origin - path.push(Value::origin()); - - // Generate outer path from (0,0) to (m,0) - let outer_path = generate_outer_path(value.outer); - path.extend(outer_path); - - // Generate inner path from (m,0) to (m,n) - let inner_path = generate_inner_path(value.outer, value.inner); - path.extend(inner_path); - - path -} - -/// Generate the path along the outer coordinate from (0,0) to (m,0). -/// Excludes the origin (0,0). -fn generate_outer_path(m: i32) -> Vec { - match m.cmp(&0) { - std::cmp::Ordering::Greater => { - // Apply rule 2: (n,0) -> (n+1,0) - (1..=m).map(|i| Value::new(i, 0)).collect() - } - std::cmp::Ordering::Less => { - // Apply rule 3: (n,0) -> (n-1,0) - // Generate -1, -2, ..., m - // Range m..0 gives [m, m+1, ..., -1], reversed gives [-1, -2, ..., m] - (m..0).rev().map(|i| Value::new(i, 0)).collect() - } - std::cmp::Ordering::Equal => Vec::new(), - } -} - -/// Generate the path along the inner coordinate from (m,0) to (m,n). -/// Excludes the starting point (m,0). -fn generate_inner_path(m: i32, n: i32) -> Vec { - match n.cmp(&0) { - std::cmp::Ordering::Greater => { - // Apply rule 4: (m,n) -> (m,n+1) - (1..=n).map(|i| Value::new(m, i)).collect() - } - std::cmp::Ordering::Less => { - // Apply rule 5: (m,n) -> (m,n-1) - // Generate -1, -2, ..., n - // Range n..0 gives [n, n+1, ..., -1], reversed gives [-1, -2, ..., n] - (n..0).rev().map(|i| Value::new(m, i)).collect() - } - std::cmp::Ordering::Equal => Vec::new(), - } -} - -/// Returns the length of the minimum derivation path for a given value. -/// -/// This is equivalent to |outer| + |inner| + 1 (for the origin). -/// -/// # Examples -/// -/// ``` -/// use meta_affine::{Value, path_length}; -/// assert_eq!(path_length(Value::new(2, 3)), 6); -/// assert_eq!(path_length(Value::new(-2, -3)), 6); -/// ``` -pub fn path_length(value: Value) -> usize { - (value.outer.abs() + value.inner.abs() + 1) as usize -} -- cgit v1.2.3