summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorjacksonfu14 <jackson@fashionunited.com>2025-11-11 08:02:20 +0100
committerJackson Moore <jacksonmoore@tuta.io>2025-11-11 08:02:20 +0100
commitcf758968d957de0fa2f1bf39a42d633b4fe74616 (patch)
treeb7a8a3d181055422a9de046732d3804786549a24
parent1d0086a3d223f12201b4b1a7832cd283ff384daf (diff)
feat: add backward sorting
-rw-r--r--morphology/README.md12
-rw-r--r--morphology/examples/test_sorting_directions.rs81
-rw-r--r--morphology/src/sequence.rs118
3 files changed, 179 insertions, 32 deletions
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<PrecedenceOrder>,
inner_precedence_order: Option<PrecedenceOrder>,
sorting_method: Option<SortingMethod>,
+ sorting_direction: Option<SortingDirection>,
}
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())
}
}
}