summaryrefslogtreecommitdiff
path: root/morphology/src/sequence.rs
diff options
context:
space:
mode:
Diffstat (limited to 'morphology/src/sequence.rs')
-rw-r--r--morphology/src/sequence.rs248
1 files changed, 242 insertions, 6 deletions
diff --git a/morphology/src/sequence.rs b/morphology/src/sequence.rs
index 2203e83..9b5e8f6 100644
--- a/morphology/src/sequence.rs
+++ b/morphology/src/sequence.rs
@@ -371,34 +371,51 @@ fn is_outer_constraint_satisfiable(current: &[Value]) -> bool {
/// Generates all valid sequences of a given length from any valid set.
///
/// This is the main entry point that combines set generation and sequence generation.
+/// Sequences are sorted using the precedence orders specified in the options.
///
/// # Arguments
///
/// * `length` - The desired sequence length
+/// * `options` - Optional SequenceOptions for sorting. Pass `None` for defaults.
///
/// # Returns
///
-/// A vector of all valid sequences of the specified length
+/// A vector of all valid sequences of the specified length, sorted
///
/// # Examples
///
/// ```
-/// use meta_affine::sequence::generate_all_sequences;
+/// use meta_affine::sequence::{generate_all_sequences, SequenceOptions, PrecedenceOrder};
///
-/// let sequences = generate_all_sequences(1);
+/// // Use defaults
+/// let sequences = generate_all_sequences(1, None);
/// assert_eq!(sequences.len(), 1); // Only [(0,0)]
+///
+/// // Specify options
+/// let opts = SequenceOptions::new()
+/// .outer_order(PrecedenceOrder::IncreasingNegativeFirst)
+/// .inner_order(PrecedenceOrder::IncreasingPositiveFirst);
+/// let sequences = generate_all_sequences(3, opts);
/// ```
-pub fn generate_all_sequences(length: usize) -> Vec<Sequence> {
+pub fn generate_all_sequences(
+ length: usize,
+ options: impl Into<Option<SequenceOptions>>,
+) -> Vec<Sequence> {
use crate::set::generate_valid_sets;
let max_set_size = length; // Heuristic: set size can't exceed sequence length
let all_sets = generate_valid_sets(max_set_size);
// Process sets in parallel
- all_sets
+ let mut sequences: Vec<Sequence> = all_sets
.par_iter()
.flat_map(|set| generate_sequences(set, length))
- .collect()
+ .collect();
+
+ // Sort sequences before returning
+ sort_sequences(&mut sequences, options);
+
+ sequences
}
/// Counts the number of valid sequences for a given length without generating them.
@@ -407,3 +424,222 @@ pub fn generate_all_sequences(length: usize) -> Vec<Sequence> {
pub fn count_sequences(set: &ValidSet, length: usize) -> usize {
generate_sequences(set, length).len()
}
+
+// ============================================================================
+// SORTING
+// ============================================================================
+
+/// Defines the order for precedence lists used in sorting.
+#[derive(Debug, Clone, Copy)]
+pub enum PrecedenceOrder {
+ /// [0, -1, 1, -2, 2, -3, 3, ...]
+ IncreasingNegativeFirst,
+ /// [0, 1, -1, 2, -2, 3, -3, ...]
+ IncreasingPositiveFirst,
+}
+
+impl Default for PrecedenceOrder {
+ fn default() -> Self {
+ PrecedenceOrder::IncreasingPositiveFirst
+ }
+}
+
+/// Configuration options for sequence generation and sorting.
+///
+/// Use the builder pattern to specify only the options you need.
+///
+/// # Examples
+///
+/// ```
+/// use meta_affine::sequence::{SequenceOptions, PrecedenceOrder};
+///
+/// // All defaults
+/// let opts = SequenceOptions::new();
+///
+/// // Specify only outer order
+/// let opts = SequenceOptions::new()
+/// .outer_order(PrecedenceOrder::IncreasingNegativeFirst);
+///
+/// // Specify both
+/// let opts = SequenceOptions::new()
+/// .outer_order(PrecedenceOrder::IncreasingNegativeFirst)
+/// .inner_order(PrecedenceOrder::IncreasingPositiveFirst);
+/// ```
+#[derive(Debug, Clone, Default)]
+pub struct SequenceOptions {
+ outer_precedence_order: Option<PrecedenceOrder>,
+ inner_precedence_order: Option<PrecedenceOrder>,
+}
+
+impl SequenceOptions {
+ /// Creates a new SequenceOptions with all defaults.
+ pub fn new() -> Self {
+ Default::default()
+ }
+
+ /// Sets the precedence order for outer values.
+ pub fn outer_order(mut self, order: PrecedenceOrder) -> Self {
+ self.outer_precedence_order = Some(order);
+ self
+ }
+
+ /// Sets the precedence order for inner values.
+ pub fn inner_order(mut self, order: PrecedenceOrder) -> Self {
+ self.inner_precedence_order = Some(order);
+ 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()
+ }
+
+ /// Gets the inner precedence order, or default if not set.
+ pub(crate) fn get_inner_order(&self) -> PrecedenceOrder {
+ self.inner_precedence_order.unwrap_or_default()
+ }
+}
+
+/// Sorts sequences using specified precedence orders for outer and inner values.
+///
+/// The length parameter for precedence list generation is automatically determined
+/// as the length of the longest sequence being sorted.
+///
+/// # Arguments
+///
+/// * `sequences` - Mutable slice of sequences to sort
+/// * `options` - Optional SequenceOptions for sorting. Pass `None` for defaults.
+///
+/// # Examples
+///
+/// ```
+/// use meta_affine::{Sequence, Value, sequence::{sort_sequences, SequenceOptions, PrecedenceOrder}};
+///
+/// let mut sequences = vec![
+/// Sequence::new(vec![Value::new(1, 0), Value::new(0, 0)]),
+/// Sequence::new(vec![Value::new(0, 0), Value::new(1, 0)]),
+/// ];
+///
+/// // Use defaults
+/// sort_sequences(&mut sequences, None);
+///
+/// // Specify options
+/// let opts = SequenceOptions::new()
+/// .outer_order(PrecedenceOrder::IncreasingNegativeFirst)
+/// .inner_order(PrecedenceOrder::IncreasingPositiveFirst);
+/// sort_sequences(&mut sequences, opts);
+/// ```
+pub fn sort_sequences(
+ sequences: &mut [Sequence],
+ options: impl Into<Option<SequenceOptions>>,
+) {
+ if sequences.is_empty() {
+ return;
+ }
+
+ // Get options or use defaults
+ let opts = options.into().unwrap_or_default();
+ let outer_order = opts.get_outer_order();
+ let inner_order = opts.get_inner_order();
+
+ // Determine the length of the longest sequence
+ let max_length = sequences.iter()
+ .map(|seq| seq.length())
+ .max()
+ .unwrap_or(0);
+
+ // Generate precedence lists based on enum values
+ let outer_precedence = generate_precedence_list(outer_order, max_length);
+ let inner_precedence = generate_precedence_list(inner_order, max_length);
+
+ // Sort using the generated precedence lists
+ sequences.sort_by(|a, b| {
+ compare_sequences_with_precedence(a, b, &outer_precedence, &inner_precedence)
+ });
+}
+
+/// Generates precedence list from enum value.
+fn generate_precedence_list(order: PrecedenceOrder, n: usize) -> Vec<i32> {
+ match order {
+ PrecedenceOrder::IncreasingNegativeFirst => increasing_negative_first(n),
+ PrecedenceOrder::IncreasingPositiveFirst => increasing_positive_first(n),
+ }
+}
+
+/// Generates [0, -1, 1, -2, 2, -3, 3, ...] up to ±(n-1).
+fn increasing_negative_first(n: usize) -> Vec<i32> {
+ let max = (n as i32) - 1;
+
+ std::iter::once(0)
+ .chain((1..=max).flat_map(|i| [-i, i]))
+ .collect()
+}
+
+/// Generates [0, 1, -1, 2, -2, 3, -3, ...] up to ±(n-1).
+fn increasing_positive_first(n: usize) -> Vec<i32> {
+ let max = (n as i32) - 1;
+
+ std::iter::once(0)
+ .chain((1..=max).flat_map(|i| [i, -i]))
+ .collect()
+}
+
+/// Compares two sequences lexicographically using precedence lists.
+fn compare_sequences_with_precedence(
+ a: &Sequence,
+ b: &Sequence,
+ outer_precedence: &[i32],
+ inner_precedence: &[i32],
+) -> 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;
+ }
+ }
+
+ // Shorter sequence comes first if all compared values are equal
+ a.values.len().cmp(&b.values.len())
+}
+
+/// Compares two values using precedence lists (outer first, then inner).
+fn compare_values_with_precedence(
+ a: &Value,
+ b: &Value,
+ outer_precedence: &[i32],
+ inner_precedence: &[i32],
+) -> std::cmp::Ordering {
+ use std::cmp::Ordering;
+
+ // Compare outer values first
+ let outer_cmp = compare_with_precedence(a.outer, b.outer, outer_precedence);
+ if outer_cmp != Ordering::Equal {
+ return outer_cmp;
+ }
+
+ // If outer values are equal, compare inner values
+ compare_with_precedence(a.inner, b.inner, inner_precedence)
+}
+
+/// Compares two integers using a precedence list.
+/// Values not in the list come after listed values and use natural ordering.
+fn compare_with_precedence(a: i32, b: i32, precedence: &[i32]) -> std::cmp::Ordering {
+ use std::cmp::Ordering;
+
+ if a == b {
+ return Ordering::Equal;
+ }
+
+ let pos_a = precedence.iter().position(|&x| x == a);
+ let pos_b = precedence.iter().position(|&x| x == b);
+
+ match (pos_a, pos_b) {
+ (Some(pa), Some(pb)) => pa.cmp(&pb),
+ (Some(_), None) => Ordering::Less, // a is in list, b is not
+ (None, Some(_)) => Ordering::Greater, // b is in list, a is not
+ (None, None) => a.cmp(&b), // neither in list, use natural ordering
+ }
+}