summaryrefslogtreecommitdiff
path: root/morphology/src/sequence.rs
diff options
context:
space:
mode:
Diffstat (limited to 'morphology/src/sequence.rs')
-rw-r--r--morphology/src/sequence.rs411
1 files changed, 411 insertions, 0 deletions
diff --git a/morphology/src/sequence.rs b/morphology/src/sequence.rs
new file mode 100644
index 0000000..784567d
--- /dev/null
+++ b/morphology/src/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()
+}