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/src/sequence.rs | 68 ++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 59 insertions(+), 9 deletions(-) (limited to 'morphology/src/sequence.rs') 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