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/sequence.rs | |
initial commit
Diffstat (limited to 'morphology/meta_affine/sequence.rs')
| -rw-r--r-- | morphology/meta_affine/sequence.rs | 411 |
1 files changed, 411 insertions, 0 deletions
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() +} |