summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorjacksonfu14 <jackson@fashionunited.com>2025-11-09 21:58:46 +0100
committerJackson Moore <jacksonmoore@tuta.io>2025-11-09 21:58:46 +0100
commitcccaa346384c7fed2ebf2524a2a6cca1e1bec577 (patch)
tree2d1d092d24409c5282f2205de88189b1f3d1e7f3
parentda3aa05be9177f10ae311713a99021d76721e426 (diff)
feat: add sequence sorting
-rw-r--r--morphology-cli/src/main.rs4
-rw-r--r--morphology/README.md60
-rw-r--r--morphology/examples/demo_full.rs4
-rw-r--r--morphology/src/lib.rs2
-rw-r--r--morphology/src/sequence.rs248
-rw-r--r--morphology/tests/sequence.rs4
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);