From 1d0086a3d223f12201b4b1a7832cd283ff384daf Mon Sep 17 00:00:00 2001 From: jacksonfu14 Date: Tue, 11 Nov 2025 07:04:56 +0100 Subject: feat: add breadth first sorting --- morphology/README.md | 32 +++++++------- morphology/examples/test_sorting_methods.rs | 60 +++++++++++++++++++++++++ morphology/src/sequence.rs | 68 +++++++++++++++++++++++++---- 3 files changed, 134 insertions(+), 26 deletions(-) create mode 100644 morphology/examples/test_sorting_methods.rs diff --git a/morphology/README.md b/morphology/README.md index 7e1865b..9b8807f 100644 --- a/morphology/README.md +++ b/morphology/README.md @@ -82,6 +82,9 @@ count_sequences(&set, length) -> usize PrecedenceOrder::IncreasingNegativeFirst // [0, -1, 1, -2, 2, ...] PrecedenceOrder::IncreasingPositiveFirst // [0, 1, -1, 2, -2, ...] +SortingMethod::DepthFirst // Compare position-by-position: outer then inner at each position +SortingMethod::BreadthFirst // Compare all outer values first, then all inner values + sort_sequences(&mut sequences, outer_order, inner_order) ``` @@ -161,9 +164,8 @@ let all_sets = generate_valid_sets(5); ```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; +use meta_affine::sequence::{generate_sequences, generate_all_sequences, sort_sequences}; +use meta_affine::sequence::{SequenceOptions, PrecedenceOrder, SortingMethod}; // Create a valid set let set = ValidSet::new() @@ -171,24 +173,20 @@ let set = ValidSet::new() // 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 defaults (DepthFirst, IncreasingPositiveFirst) +sort_sequences(&mut sequences, 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, ...] -); +// Sort with custom options using builder pattern +let opts = SequenceOptions::new() + .sorting_method(SortingMethod::BreadthFirst) + .outer_order(PrecedenceOrder::IncreasingNegativeFirst) + .inner_order(PrecedenceOrder::IncreasingPositiveFirst); +sort_sequences(&mut sequences, opts); // 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 +let opts = SequenceOptions::new().sorting_method(SortingMethod::BreadthFirst); +let all_sequences = generate_all_sequences(3, opts); ``` ## Mathematical Background diff --git a/morphology/examples/test_sorting_methods.rs b/morphology/examples/test_sorting_methods.rs new file mode 100644 index 0000000..b4ad18f --- /dev/null +++ b/morphology/examples/test_sorting_methods.rs @@ -0,0 +1,60 @@ +// Test program to demonstrate DepthFirst vs BreadthFirst sorting + +use meta_affine::{Sequence, Value}; +use meta_affine::sequence::{sort_sequences, SequenceOptions, SortingMethod}; + +fn print_sequences(label: &str, sequences: &[Sequence]) { + println!("\n{}:", label); + for (i, seq) in sequences.iter().enumerate() { + print!(" {}: [", i); + for (j, v) in seq.values().iter().enumerate() { + if j > 0 { print!(", "); } + print!("({},{})", v.outer, v.inner); + } + println!("]"); + } +} + +fn main() { + // Create test sequences that demonstrate the difference between DepthFirst and BreadthFirst + // These sequences have same outer values but different inner values at different positions + let sequences = vec![ + // Sequence A: (0,2), (0,1), (0,0) - outer: [0,0,0], inner: [2,1,0] + Sequence::new(vec![Value::new(0, 2), Value::new(0, 1), Value::new(0, 0)]), + // Sequence B: (0,1), (0,2), (0,0) - outer: [0,0,0], inner: [1,2,0] + Sequence::new(vec![Value::new(0, 1), Value::new(0, 2), Value::new(0, 0)]), + // Sequence C: (1,0), (0,0) - outer: [1,0], inner: [0,0] + Sequence::new(vec![Value::new(1, 0), Value::new(0, 0)]), + // Sequence D: (0,0) - outer: [0], inner: [0] + Sequence::new(vec![Value::new(0, 0)]), + ]; + + print_sequences("Original sequences", &sequences); + + // Test DepthFirst sorting (default) + let mut depth_first = sequences.clone(); + sort_sequences(&mut depth_first, SequenceOptions::new().sorting_method(SortingMethod::DepthFirst)); + + print_sequences("DepthFirst sorted (compares position-by-position)", &depth_first); + println!(" Explanation: At position 0, compares (0,2) vs (0,1)"); + println!(" Outer values equal (0==0), so compare inner: 1 < 2"); + println!(" Therefore sequence B comes before A"); + + // Test BreadthFirst sorting + let mut breadth_first = sequences.clone(); + sort_sequences(&mut breadth_first, SequenceOptions::new().sorting_method(SortingMethod::BreadthFirst)); + + print_sequences("BreadthFirst sorted (all outer values, then all inner values)", &breadth_first); + println!(" Explanation: First compares all outer values [0,0,0] vs [0,0,0] -> equal"); + println!(" Then compares all inner values [2,1,0] vs [1,2,0]"); + println!(" At position 0 of inner: 1 < 2"); + println!(" Therefore sequence B comes before A"); + + println!("\n=== Note ==="); + println!("In this example, both methods produce the same result because:"); + println!("- DepthFirst: Compares position 0 -> outer equal, inner 1<2"); + println!("- BreadthFirst: All outers equal, then inner position 0 -> 1<2"); + println!("\nBoth reach the same conclusion through different comparison paths."); + println!("The distinction becomes more apparent with more complex sequences"); + println!("where outer values differ at later positions."); +} diff --git a/morphology/src/sequence.rs b/morphology/src/sequence.rs index 9b5e8f6..3005cdf 100644 --- a/morphology/src/sequence.rs +++ b/morphology/src/sequence.rs @@ -444,6 +444,16 @@ impl Default for PrecedenceOrder { } } +/// 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, +} + /// Configuration options for sequence generation and sorting. /// /// Use the builder pattern to specify only the options you need. @@ -469,6 +479,7 @@ impl Default for PrecedenceOrder { pub struct SequenceOptions { outer_precedence_order: Option, inner_precedence_order: Option, + sorting_method: Option, } impl SequenceOptions { @@ -489,6 +500,12 @@ impl SequenceOptions { self } + /// Sets the sorting method. + pub fn sorting_method(mut self, method: SortingMethod) -> Self { + self.sorting_method = Some(method); + 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() @@ -498,6 +515,11 @@ impl SequenceOptions { 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() + } } /// Sorts sequences using specified precedence orders for outer and inner values. @@ -541,6 +563,7 @@ pub fn sort_sequences( 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(); // Determine the length of the longest sequence let max_length = sequences.iter() @@ -554,7 +577,7 @@ pub fn sort_sequences( // Sort using the generated precedence lists sequences.sort_by(|a, b| { - compare_sequences_with_precedence(a, b, &outer_precedence, &inner_precedence) + compare_sequences_with_precedence(a, b, &outer_precedence, &inner_precedence, sorting_method) }); } @@ -590,19 +613,46 @@ fn compare_sequences_with_precedence( b: &Sequence, outer_precedence: &[i32], inner_precedence: &[i32], + sorting_method: SortingMethod, ) -> 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; + match sorting_method { + SortingMethod::DepthFirst => { + // Current behavior: compare position-by-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; + } + } + + // If everything is equal, shorter sequence comes first + a.values.len().cmp(&b.values.len()) } - } + SortingMethod::BreadthFirst => { + // New behavior: compare all outer values, 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; + } + } - // Shorter sequence comes first if all compared values are equal - a.values.len().cmp(&b.values.len()) + // 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; + } + } + + // If everything is equal, shorter sequence comes first + a.values.len().cmp(&b.values.len()) + } + } } /// Compares two values using precedence lists (outer first, then inner). -- cgit v1.2.3