From cf758968d957de0fa2f1bf39a42d633b4fe74616 Mon Sep 17 00:00:00 2001 From: jacksonfu14 Date: Tue, 11 Nov 2025 08:02:20 +0100 Subject: feat: add backward sorting --- morphology/README.md | 12 ++- morphology/examples/test_sorting_directions.rs | 81 +++++++++++++++++ morphology/src/sequence.rs | 118 +++++++++++++++++++------ 3 files changed, 179 insertions(+), 32 deletions(-) create mode 100644 morphology/examples/test_sorting_directions.rs diff --git a/morphology/README.md b/morphology/README.md index 9b8807f..dee8c3e 100644 --- a/morphology/README.md +++ b/morphology/README.md @@ -85,6 +85,9 @@ 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 +SortingDirection::Forward // Compare sequences from first to last position +SortingDirection::Backward // Compare sequences from last to first position + sort_sequences(&mut sequences, outer_order, inner_order) ``` @@ -165,7 +168,7 @@ let all_sets = generate_valid_sets(5); ```rust use meta_affine::{ValidSet, Value, Sequence}; use meta_affine::sequence::{generate_sequences, generate_all_sequences, sort_sequences}; -use meta_affine::sequence::{SequenceOptions, PrecedenceOrder, SortingMethod}; +use meta_affine::sequence::{SequenceOptions, PrecedenceOrder, SortingMethod, SortingDirection}; // Create a valid set let set = ValidSet::new() @@ -174,18 +177,21 @@ let set = ValidSet::new() // Generate all valid sequences of length 3 from this set let mut sequences = generate_sequences(&set, 3); -// Sort with defaults (DepthFirst, IncreasingPositiveFirst) +// Sort with defaults (Forward, DepthFirst, IncreasingPositiveFirst) sort_sequences(&mut sequences, None); // Sort with custom options using builder pattern let opts = SequenceOptions::new() + .sorting_direction(SortingDirection::Backward) .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 opts = SequenceOptions::new().sorting_method(SortingMethod::BreadthFirst); +let opts = SequenceOptions::new() + .sorting_method(SortingMethod::BreadthFirst) + .sorting_direction(SortingDirection::Backward); let all_sequences = generate_all_sequences(3, opts); ``` diff --git a/morphology/examples/test_sorting_directions.rs b/morphology/examples/test_sorting_directions.rs new file mode 100644 index 0000000..30ea280 --- /dev/null +++ b/morphology/examples/test_sorting_directions.rs @@ -0,0 +1,81 @@ +// Test program to demonstrate Forward vs Backward sorting directions + +use meta_affine::{Sequence, Value}; +use meta_affine::sequence::{sort_sequences, SequenceOptions, SortingMethod, SortingDirection}; + +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 where Forward and Backward will produce different results + let sequences = vec![ + // Sequence A: (1,0), (0,1), (0,0) - differs at position 0 + Sequence::new(vec![Value::new(1, 0), Value::new(0, 1), Value::new(0, 0)]), + // Sequence B: (0,1), (1,0), (0,0) - differs at position 0 + Sequence::new(vec![Value::new(0, 1), Value::new(1, 0), Value::new(0, 0)]), + // Sequence C: (0,0) + Sequence::new(vec![Value::new(0, 0)]), + ]; + + print_sequences("Original sequences", &sequences); + + // Test Forward DepthFirst (default) + let mut forward_depth = sequences.clone(); + let opts = SequenceOptions::new() + .sorting_method(SortingMethod::DepthFirst) + .sorting_direction(SortingDirection::Forward); + sort_sequences(&mut forward_depth, opts); + + print_sequences("Forward DepthFirst (compares from first position)", &forward_depth); + println!(" Explanation: At position 0, compares (1,0) vs (0,1)"); + println!(" Outer values: 0 < 1, so B comes before A"); + + // Test Backward DepthFirst + let mut backward_depth = sequences.clone(); + let opts = SequenceOptions::new() + .sorting_method(SortingMethod::DepthFirst) + .sorting_direction(SortingDirection::Backward); + sort_sequences(&mut backward_depth, opts); + + print_sequences("Backward DepthFirst (compares from last position)", &backward_depth); + println!(" Explanation: Starting from last position (both end with (0,0))"); + println!(" Position -2 (second to last): compares (0,1) vs (1,0)"); + println!(" Outer values: 0 < 1, so A comes before B"); + + // Test Forward BreadthFirst + let mut forward_breadth = sequences.clone(); + let opts = SequenceOptions::new() + .sorting_method(SortingMethod::BreadthFirst) + .sorting_direction(SortingDirection::Forward); + sort_sequences(&mut forward_breadth, opts); + + print_sequences("Forward BreadthFirst", &forward_breadth); + println!(" Explanation: Compare all outer values [1,0,0] vs [0,1,0]"); + println!(" At position 0: 0 < 1, so B comes before A"); + + // Test Backward BreadthFirst + let mut backward_breadth = sequences.clone(); + let opts = SequenceOptions::new() + .sorting_method(SortingMethod::BreadthFirst) + .sorting_direction(SortingDirection::Backward); + sort_sequences(&mut backward_breadth, opts); + + print_sequences("Backward BreadthFirst", &backward_breadth); + println!(" Explanation: Compare all outer values reversed [0,0,1] vs [0,1,0]"); + println!(" At position 0 (from end): both are 0"); + println!(" At position 1 (from end): 0 < 1, so A comes before B"); + + println!("\n=== Summary ==="); + println!("Forward: Compares sequences starting from the first position"); + println!("Backward: Compares sequences starting from the last position"); + println!("This can produce different orderings depending on where differences occur."); +} diff --git a/morphology/src/sequence.rs b/morphology/src/sequence.rs index 3005cdf..bb93418 100644 --- a/morphology/src/sequence.rs +++ b/morphology/src/sequence.rs @@ -454,6 +454,16 @@ pub enum SortingMethod { 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, +} + /// Configuration options for sequence generation and sorting. /// /// Use the builder pattern to specify only the options you need. @@ -480,6 +490,7 @@ pub struct SequenceOptions { outer_precedence_order: Option, inner_precedence_order: Option, sorting_method: Option, + sorting_direction: Option, } impl SequenceOptions { @@ -506,6 +517,12 @@ impl SequenceOptions { self } + /// Sets the sorting direction. + pub fn sorting_direction(mut self, direction: SortingDirection) -> Self { + self.sorting_direction = Some(direction); + 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() @@ -520,6 +537,11 @@ impl SequenceOptions { 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() + } } /// Sorts sequences using specified precedence orders for outer and inner values. @@ -564,6 +586,7 @@ pub fn sort_sequences( 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(); // Determine the length of the longest sequence let max_length = sequences.iter() @@ -577,7 +600,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, sorting_method) + compare_sequences_with_precedence(a, b, &outer_precedence, &inner_precedence, sorting_method, sorting_direction) }); } @@ -614,43 +637,80 @@ fn compare_sequences_with_precedence( outer_precedence: &[i32], inner_precedence: &[i32], sorting_method: SortingMethod, + sorting_direction: SortingDirection, ) -> std::cmp::Ordering { use std::cmp::Ordering; - 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; + 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()) } } - - // 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; + 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()) } - } - - // 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; + 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()) } } - - // If everything is equal, shorter sequence comes first - a.values.len().cmp(&b.values.len()) } } } -- cgit v1.2.3