summaryrefslogtreecommitdiff
path: root/morphology
diff options
context:
space:
mode:
Diffstat (limited to 'morphology')
-rw-r--r--morphology/README.md32
-rw-r--r--morphology/examples/test_sorting_methods.rs60
-rw-r--r--morphology/src/sequence.rs68
3 files changed, 134 insertions, 26 deletions
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<PrecedenceOrder>,
inner_precedence_order: Option<PrecedenceOrder>,
+ sorting_method: Option<SortingMethod>,
}
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).