//! 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}; use rayon::prelude::*; /// 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. /// Sequences are sorted using the precedence orders specified in the options. /// /// # Arguments /// /// * `length` - The desired sequence length /// * `options` - Optional SequenceOptions for sorting. Pass `None` for defaults. /// /// # Returns /// /// A vector of all valid sequences of the specified length, sorted /// /// # Examples /// /// ``` /// use meta_affine::sequence::{generate_all_sequences, SequenceOptions, PrecedenceOrder}; /// /// // Use defaults /// let sequences = generate_all_sequences(1, None); /// assert_eq!(sequences.len(), 1); // Only [(0,0)] /// /// // Specify options /// let opts = SequenceOptions::new() /// .outer_order(PrecedenceOrder::IncreasingNegativeFirst) /// .inner_order(PrecedenceOrder::IncreasingPositiveFirst); /// let sequences = generate_all_sequences(3, opts); /// ``` pub fn generate_all_sequences( length: usize, options: impl Into>, ) -> 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); // Process sets in parallel let mut sequences: Vec = all_sets .par_iter() .flat_map(|set| generate_sequences(set, length)) .collect(); // Sort sequences before returning sort_sequences(&mut sequences, options); 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() } // ============================================================================ // SORTING // ============================================================================ /// Defines the order for precedence lists used in sorting. #[derive(Debug, Clone, Copy)] pub enum PrecedenceOrder { /// [0, -1, 1, -2, 2, -3, 3, ...] IncreasingNegativeFirst, /// [0, 1, -1, 2, -2, 3, -3, ...] IncreasingPositiveFirst, } impl Default for PrecedenceOrder { fn default() -> Self { PrecedenceOrder::IncreasingPositiveFirst } } /// Defines the sorting method for sequences. #[derive(Debug, Clone, Copy, Default)] pub enum SortingMethod { /// Compare position-by-position: outer then inner at each position #[default] DepthFirst, /// Compare all outer values first, then all inner values BreadthFirst, } /// Defines the sorting direction for sequences. #[derive(Debug, Clone, Copy, Default)] pub enum SortingDirection { /// Compare sequences from first to last position #[default] Forward, /// Compare sequences from last to first position Backward, } /// Defines how sequences of different lengths are sorted. #[derive(Debug, Clone, Copy, Default)] pub enum LengthSorting { /// Sequences are grouped by length, shorter sequences first #[default] SegregateLength, /// Sequences of different lengths are sorted together by content InterpolateLength, } /// Configuration options for sequence generation and sorting. /// /// Use the builder pattern to specify only the options you need. /// /// # Examples /// /// ``` /// use meta_affine::sequence::{SequenceOptions, PrecedenceOrder}; /// /// // All defaults /// let opts = SequenceOptions::new(); /// /// // Specify only outer order /// let opts = SequenceOptions::new() /// .outer_order(PrecedenceOrder::IncreasingNegativeFirst); /// /// // Specify both /// let opts = SequenceOptions::new() /// .outer_order(PrecedenceOrder::IncreasingNegativeFirst) /// .inner_order(PrecedenceOrder::IncreasingPositiveFirst); /// ``` #[derive(Debug, Clone, Default)] pub struct SequenceOptions { outer_precedence_order: Option, inner_precedence_order: Option, sorting_method: Option, sorting_direction: Option, length_sorting: Option, } impl SequenceOptions { /// Creates a new SequenceOptions with all defaults. pub fn new() -> Self { Default::default() } /// Sets the precedence order for outer values. pub fn outer_order(mut self, order: PrecedenceOrder) -> Self { self.outer_precedence_order = Some(order); self } /// Sets the precedence order for inner values. pub fn inner_order(mut self, order: PrecedenceOrder) -> Self { self.inner_precedence_order = Some(order); self } /// Sets the sorting method. pub fn sorting_method(mut self, method: SortingMethod) -> Self { self.sorting_method = Some(method); self } /// Sets the sorting direction. pub fn sorting_direction(mut self, direction: SortingDirection) -> Self { self.sorting_direction = Some(direction); self } /// Sets the length sorting mode. pub fn length_sorting(mut self, length_sorting: LengthSorting) -> Self { self.length_sorting = Some(length_sorting); self } /// Gets the outer precedence order, or default if not set. pub(crate) fn get_outer_order(&self) -> PrecedenceOrder { self.outer_precedence_order.unwrap_or_default() } /// Gets the inner precedence order, or default if not set. pub(crate) fn get_inner_order(&self) -> PrecedenceOrder { self.inner_precedence_order.unwrap_or_default() } /// Gets the sorting method, or default if not set. pub(crate) fn get_sorting_method(&self) -> SortingMethod { self.sorting_method.unwrap_or_default() } /// Gets the sorting direction, or default if not set. pub(crate) fn get_sorting_direction(&self) -> SortingDirection { self.sorting_direction.unwrap_or_default() } /// Gets the length sorting mode, or default if not set. pub(crate) fn get_length_sorting(&self) -> LengthSorting { self.length_sorting.unwrap_or_default() } } /// Sorts sequences using specified precedence orders for outer and inner values. /// /// The length parameter for precedence list generation is automatically determined /// as the length of the longest sequence being sorted. /// /// # Arguments /// /// * `sequences` - Mutable slice of sequences to sort /// * `options` - Optional SequenceOptions for sorting. Pass `None` for defaults. /// /// # Examples /// /// ``` /// use meta_affine::{Sequence, Value, sequence::{sort_sequences, SequenceOptions, PrecedenceOrder}}; /// /// let mut sequences = vec![ /// Sequence::new(vec![Value::new(1, 0), Value::new(0, 0)]), /// Sequence::new(vec![Value::new(0, 0), Value::new(1, 0)]), /// ]; /// /// // Use defaults /// sort_sequences(&mut sequences, None); /// /// // Specify options /// let opts = SequenceOptions::new() /// .outer_order(PrecedenceOrder::IncreasingNegativeFirst) /// .inner_order(PrecedenceOrder::IncreasingPositiveFirst); /// sort_sequences(&mut sequences, opts); /// ``` pub fn sort_sequences( sequences: &mut [Sequence], options: impl Into>, ) { if sequences.is_empty() { return; } // Get options or use defaults let opts = options.into().unwrap_or_default(); let outer_order = opts.get_outer_order(); let inner_order = opts.get_inner_order(); let sorting_method = opts.get_sorting_method(); let sorting_direction = opts.get_sorting_direction(); let length_sorting = opts.get_length_sorting(); // Determine the length of the longest sequence let max_length = sequences.iter() .map(|seq| seq.length()) .max() .unwrap_or(0); // Generate precedence lists based on enum values let outer_precedence = generate_precedence_list(outer_order, max_length); let inner_precedence = generate_precedence_list(inner_order, max_length); // Sort using the generated precedence lists sequences.sort_by(|a, b| { compare_sequences_with_precedence(a, b, &outer_precedence, &inner_precedence, sorting_method, sorting_direction, length_sorting) }); } /// Generates precedence list from enum value. fn generate_precedence_list(order: PrecedenceOrder, n: usize) -> Vec { match order { PrecedenceOrder::IncreasingNegativeFirst => increasing_negative_first(n), PrecedenceOrder::IncreasingPositiveFirst => increasing_positive_first(n), } } /// Generates [0, -1, 1, -2, 2, -3, 3, ...] up to ±(n-1). fn increasing_negative_first(n: usize) -> Vec { let max = (n as i32) - 1; std::iter::once(0) .chain((1..=max).flat_map(|i| [-i, i])) .collect() } /// Generates [0, 1, -1, 2, -2, 3, -3, ...] up to ±(n-1). fn increasing_positive_first(n: usize) -> Vec { let max = (n as i32) - 1; std::iter::once(0) .chain((1..=max).flat_map(|i| [i, -i])) .collect() } /// Compares two sequences lexicographically using precedence lists. fn compare_sequences_with_precedence( a: &Sequence, b: &Sequence, outer_precedence: &[i32], inner_precedence: &[i32], sorting_method: SortingMethod, sorting_direction: SortingDirection, length_sorting: LengthSorting, ) -> std::cmp::Ordering { use std::cmp::Ordering; // Handle length-based segregation match length_sorting { LengthSorting::SegregateLength => { let len_cmp = a.values.len().cmp(&b.values.len()); if len_cmp != Ordering::Equal { return len_cmp; // Early return: shorter sequences always come first } // If lengths are equal, fall through to content comparison } LengthSorting::InterpolateLength => { // Do nothing, proceed to normal content comparison } } match sorting_direction { SortingDirection::Forward => { match sorting_method { SortingMethod::DepthFirst => { // Compare position-by-position: outer then inner at each position for (val_a, val_b) in a.values.iter().zip(b.values.iter()) { let cmp = compare_values_with_precedence(val_a, val_b, outer_precedence, inner_precedence); if cmp != Ordering::Equal { return cmp; } } a.values.len().cmp(&b.values.len()) } SortingMethod::BreadthFirst => { // Compare all outer values first, then all inner values // First, compare all outer values position-by-position for (val_a, val_b) in a.values.iter().zip(b.values.iter()) { let outer_cmp = compare_with_precedence(val_a.outer, val_b.outer, outer_precedence); if outer_cmp != Ordering::Equal { return outer_cmp; } } // If all outer values are equal, compare all inner values for (val_a, val_b) in a.values.iter().zip(b.values.iter()) { let inner_cmp = compare_with_precedence(val_a.inner, val_b.inner, inner_precedence); if inner_cmp != Ordering::Equal { return inner_cmp; } } a.values.len().cmp(&b.values.len()) } } } SortingDirection::Backward => { match sorting_method { SortingMethod::DepthFirst => { // Compare position-by-position from last to first for (val_a, val_b) in a.values.iter().rev().zip(b.values.iter().rev()) { let cmp = compare_values_with_precedence(val_a, val_b, outer_precedence, inner_precedence); if cmp != Ordering::Equal { return cmp; } } a.values.len().cmp(&b.values.len()) } SortingMethod::BreadthFirst => { // Compare all outer values from last to first, then all inner values // First, compare all outer values position-by-position (reversed) for (val_a, val_b) in a.values.iter().rev().zip(b.values.iter().rev()) { let outer_cmp = compare_with_precedence(val_a.outer, val_b.outer, outer_precedence); if outer_cmp != Ordering::Equal { return outer_cmp; } } // If all outer values are equal, compare all inner values (reversed) for (val_a, val_b) in a.values.iter().rev().zip(b.values.iter().rev()) { let inner_cmp = compare_with_precedence(val_a.inner, val_b.inner, inner_precedence); if inner_cmp != Ordering::Equal { return inner_cmp; } } a.values.len().cmp(&b.values.len()) } } } } } /// Compares two values using precedence lists (outer first, then inner). fn compare_values_with_precedence( a: &Value, b: &Value, outer_precedence: &[i32], inner_precedence: &[i32], ) -> std::cmp::Ordering { use std::cmp::Ordering; // Compare outer values first let outer_cmp = compare_with_precedence(a.outer, b.outer, outer_precedence); if outer_cmp != Ordering::Equal { return outer_cmp; } // If outer values are equal, compare inner values compare_with_precedence(a.inner, b.inner, inner_precedence) } /// Compares two integers using a precedence list. /// Values not in the list come after listed values and use natural ordering. fn compare_with_precedence(a: i32, b: i32, precedence: &[i32]) -> std::cmp::Ordering { use std::cmp::Ordering; if a == b { return Ordering::Equal; } let pos_a = precedence.iter().position(|&x| x == a); let pos_b = precedence.iter().position(|&x| x == b); match (pos_a, pos_b) { (Some(pa), Some(pb)) => pa.cmp(&pb), (Some(_), None) => Ordering::Less, // a is in list, b is not (None, Some(_)) => Ordering::Greater, // b is in list, a is not (None, None) => a.cmp(&b), // neither in list, use natural ordering } }