diff options
| -rw-r--r-- | morphology-cli/src/main.rs | 4 | ||||
| -rw-r--r-- | morphology/README.md | 60 | ||||
| -rw-r--r-- | morphology/examples/demo_full.rs | 4 | ||||
| -rw-r--r-- | morphology/src/lib.rs | 2 | ||||
| -rw-r--r-- | morphology/src/sequence.rs | 248 | ||||
| -rw-r--r-- | morphology/tests/sequence.rs | 4 |
6 files changed, 309 insertions, 13 deletions
diff --git a/morphology-cli/src/main.rs b/morphology-cli/src/main.rs index 290a97d..4d183ae 100644 --- a/morphology-cli/src/main.rs +++ b/morphology-cli/src/main.rs @@ -54,8 +54,8 @@ fn main() { println!("Generating all valid meta-affine sequences of length {}...\n", length); - // Generate all sequences - let sequences = generate_all_sequences(length); + // Generate all sequences with default options + let sequences = generate_all_sequences(length, None); // Choose delimiters based on output format let (open, close) = if pretty { ("", "") } else { ("[", "]") }; diff --git a/morphology/README.md b/morphology/README.md index b933f4a..7e1865b 100644 --- a/morphology/README.md +++ b/morphology/README.md @@ -59,6 +59,32 @@ generate_valid_sets(max_size) -> Vec<ValidSet> generate_valid_sets_of_size(size) -> Vec<ValidSet> ``` +**Module:** `sequence.rs` + +Implements sequence generation and sorting: + +- Sequence struct containing ordered values +- Sequence generation from valid sets +- Sorting with customizable precedence + +**API:** +```rust +Sequence::new(values) -> Sequence +Sequence::length() -> usize +Sequence::values() -> &[Value] +Sequence::is_valid(&set) -> bool + +generate_sequences(&set, length) -> Vec<Sequence> +generate_all_sequences(length) -> Vec<Sequence> +count_sequences(&set, length) -> usize + +// Sorting +PrecedenceOrder::IncreasingNegativeFirst // [0, -1, 1, -2, 2, ...] +PrecedenceOrder::IncreasingPositiveFirst // [0, 1, -1, 2, -2, ...] + +sort_sequences(&mut sequences, outer_order, inner_order) +``` + ## Building and Testing ### Compile the Library @@ -131,6 +157,40 @@ let all_sets = generate_valid_sets(5); // Returns 210 valid sets ``` +### Sequence Generation and Sorting + +```rust +use meta_affine::{ValidSet, Value, Sequence}; +use meta_affine::sequence::generate_sequences; +use meta_affine::{generate_all_sequences, sort_sequences, PrecedenceOrder}; +use std::collections::HashMap; + +// Create a valid set +let set = ValidSet::new() + .add_value_with_dependencies(Value::new(1, 0)); + +// Generate all valid sequences of length 3 from this set +let mut sequences = generate_sequences(&set, 3); +// Returns sequences like [(0,0), (1,0), (0,0)] and [(1,0), (0,0), (1,0)] + +// Sort sequences with default precedence (IncreasingPositiveFirst for both) +sort_sequences(&mut sequences, None, None); + +// Sort with custom precedence orders +sort_sequences( + &mut sequences, + Some(PrecedenceOrder::IncreasingNegativeFirst), // outer: [0, -1, 1, -2, 2, ...] + Some(PrecedenceOrder::IncreasingPositiveFirst), // inner: [0, 1, -1, 2, -2, ...] +); + +// Generate all sequences from all valid sets with sorting options +let mut options = HashMap::new(); +options.insert("outerPrecedenceOrder".to_string(), PrecedenceOrder::IncreasingNegativeFirst); +options.insert("innerPrecedenceOrder".to_string(), PrecedenceOrder::IncreasingPositiveFirst); +let all_sequences = generate_all_sequences(3, options); +// Returns all valid sequences of length 3, sorted by the specified precedence +``` + ## Mathematical Background ### Meta-Affine Space diff --git a/morphology/examples/demo_full.rs b/morphology/examples/demo_full.rs index fcb4d82..9122f11 100644 --- a/morphology/examples/demo_full.rs +++ b/morphology/examples/demo_full.rs @@ -138,7 +138,7 @@ fn main() { // Example 4: All sequences of a given length println!("7. All valid sequences of length 2 (from all possible sets):"); - let all_seqs2 = generate_all_sequences(2); + let all_seqs2 = generate_all_sequences(2, None); println!(" Total count: {}", all_seqs2.len()); println!(" Sample sequences:"); for seq in all_seqs2.iter().take(5) { @@ -200,7 +200,7 @@ fn main() { println!("9. Sequence counts by length:"); for length in 1..=4 { - let count = generate_all_sequences(length).len(); + let count = generate_all_sequences(length, None).len(); println!(" Length {}: {} sequences", length, count); } println!(); diff --git a/morphology/src/lib.rs b/morphology/src/lib.rs index de6a3e4..fdb788b 100644 --- a/morphology/src/lib.rs +++ b/morphology/src/lib.rs @@ -19,4 +19,4 @@ pub mod sequence; // Re-export main types and functions for convenience pub use value::{Value, get_minimum_derivation_path, path_length}; pub use set::ValidSet; -pub use sequence::Sequence; +pub use sequence::{Sequence, PrecedenceOrder, SequenceOptions, sort_sequences, generate_all_sequences}; 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 + } +} diff --git a/morphology/tests/sequence.rs b/morphology/tests/sequence.rs index 07e4d34..4b52c57 100644 --- a/morphology/tests/sequence.rs +++ b/morphology/tests/sequence.rs @@ -362,7 +362,7 @@ fn test_generate_sequences_complex_set() { #[test] fn test_generate_all_sequences_length_1() { - let sequences = generate_all_sequences(1); + let sequences = generate_all_sequences(1, None); // Only [(0,0)] is valid for length 1 assert_eq!(sequences.len(), 1); @@ -371,7 +371,7 @@ fn test_generate_all_sequences_length_1() { #[test] fn test_generate_all_sequences_length_2() { - let sequences = generate_all_sequences(2); + let sequences = generate_all_sequences(2, None); // Should have multiple valid sequences from different sets assert!(sequences.len() > 0); |