diff options
| author | jacksonfu14 <jackson@fashionunited.com> | 2025-11-09 21:58:46 +0100 |
|---|---|---|
| committer | Jackson Moore <jacksonmoore@tuta.io> | 2025-11-09 21:58:46 +0100 |
| commit | cccaa346384c7fed2ebf2524a2a6cca1e1bec577 (patch) | |
| tree | 2d1d092d24409c5282f2205de88189b1f3d1e7f3 /morphology/src/sequence.rs | |
| parent | da3aa05be9177f10ae311713a99021d76721e426 (diff) | |
feat: add sequence sorting
Diffstat (limited to 'morphology/src/sequence.rs')
| -rw-r--r-- | morphology/src/sequence.rs | 248 |
1 files changed, 242 insertions, 6 deletions
diff --git a/morphology/src/sequence.rs b/morphology/src/sequence.rs index 2203e83..9b5e8f6 100644 --- a/morphology/src/sequence.rs +++ b/morphology/src/sequence.rs @@ -371,34 +371,51 @@ fn is_outer_constraint_satisfiable(current: &[Value]) -> bool { /// 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 +/// A vector of all valid sequences of the specified length, sorted /// /// # Examples /// /// ``` -/// use meta_affine::sequence::generate_all_sequences; +/// use meta_affine::sequence::{generate_all_sequences, SequenceOptions, PrecedenceOrder}; /// -/// let sequences = generate_all_sequences(1); +/// // 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) -> Vec<Sequence> { +pub fn generate_all_sequences( + length: usize, + options: impl Into<Option<SequenceOptions>>, +) -> 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); // Process sets in parallel - all_sets + let mut sequences: Vec<Sequence> = all_sets .par_iter() .flat_map(|set| generate_sequences(set, length)) - .collect() + .collect(); + + // Sort sequences before returning + sort_sequences(&mut sequences, options); + + sequences } /// Counts the number of valid sequences for a given length without generating them. @@ -407,3 +424,222 @@ pub fn generate_all_sequences(length: usize) -> Vec<Sequence> { 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 + } +} + +/// 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<PrecedenceOrder>, + inner_precedence_order: Option<PrecedenceOrder>, +} + +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 + } + + /// 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() + } +} + +/// 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<Option<SequenceOptions>>, +) { + 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(); + + // 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) + }); +} + +/// Generates precedence list from enum value. +fn generate_precedence_list(order: PrecedenceOrder, n: usize) -> Vec<i32> { + 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<i32> { + 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<i32> { + 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], +) -> std::cmp::Ordering { + use std::cmp::Ordering; + + // Compare each position until a difference is found + 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; + } + } + + // Shorter sequence comes first if all compared values are equal + 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 + } +} |