summaryrefslogtreecommitdiff
path: root/morphology/meta_affine/sequence.rs
diff options
context:
space:
mode:
Diffstat (limited to 'morphology/meta_affine/sequence.rs')
-rw-r--r--morphology/meta_affine/sequence.rs411
1 files changed, 0 insertions, 411 deletions
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<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()
-}