diff options
| author | jacksonfu14 <jackson@fashionunited.com> | 2025-11-06 07:04:52 +0100 |
|---|---|---|
| committer | Jackson Moore <jacksonmoore@tuta.io> | 2025-11-06 07:04:52 +0100 |
| commit | c20b1fe88b0ab1469300bd53be14faa6a5b917a0 (patch) | |
| tree | 9e41975e6f6852146216a05ba4cef09436688aa2 /morphology/meta_affine | |
initial commit
Diffstat (limited to 'morphology/meta_affine')
| -rw-r--r-- | morphology/meta_affine/lib.rs | 22 | ||||
| -rw-r--r-- | morphology/meta_affine/sequence.rs | 411 | ||||
| -rw-r--r-- | morphology/meta_affine/set.rs | 349 | ||||
| -rw-r--r-- | morphology/meta_affine/value.rs | 170 |
4 files changed, 952 insertions, 0 deletions
diff --git a/morphology/meta_affine/lib.rs b/morphology/meta_affine/lib.rs new file mode 100644 index 0000000..6ebd49d --- /dev/null +++ b/morphology/meta_affine/lib.rs @@ -0,0 +1,22 @@ +//! 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 new file mode 100644 index 0000000..784567d --- /dev/null +++ b/morphology/meta_affine/sequence.rs @@ -0,0 +1,411 @@ +//! 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<Value>, +} + +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<Value>) -> 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<Value> = 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<i32, usize> = 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<Sequence> { + // 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<Value> = 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<Value>, + coverage: &mut HashSet<Value>, + set_values: &[Value], + set: &ValidSet, + target_length: usize, + result: &mut Vec<Sequence>, +) { + // 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<Value>, + 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<i32, usize> = 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<Sequence> { + 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 new file mode 100644 index 0000000..5376f65 --- /dev/null +++ b/morphology/meta_affine/set.rs @@ -0,0 +1,349 @@ +//! 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<Value>, +} + +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<Value>) -> Result<Self, String> { + 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<Self, String> { + 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<Item = &Value> { + 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<Value> { + let mut sorted: Vec<Value> = 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<ValidSet> { + 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<ValidSet>> = 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<Value> { + 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<ValidSet> { + 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 new file mode 100644 index 0000000..71fc2c6 --- /dev/null +++ b/morphology/meta_affine/value.rs @@ -0,0 +1,170 @@ +//! 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<Value> { + 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<Value> { + 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<Value> { + 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 +} |