From c20b1fe88b0ab1469300bd53be14faa6a5b917a0 Mon Sep 17 00:00:00 2001 From: jacksonfu14 Date: Thu, 6 Nov 2025 07:04:52 +0100 Subject: initial commit --- .gitignore | 4 + morphology/README.md | 159 +++++++++++ morphology/demo | Bin 0 -> 693544 bytes morphology/demo_full | Bin 0 -> 722144 bytes morphology/examples/demo.rs | 121 ++++++++ morphology/examples/demo_full.rs | 220 +++++++++++++++ morphology/libmeta_affine.rlib | Bin 0 -> 1009182 bytes morphology/meta-affine | Bin 0 -> 560568 bytes morphology/meta-affine-test | Bin 0 -> 1209256 bytes morphology/meta_affine/lib.rs | 22 ++ morphology/meta_affine/sequence.rs | 411 +++++++++++++++++++++++++++ morphology/meta_affine/set.rs | 349 +++++++++++++++++++++++ morphology/meta_affine/value.rs | 170 ++++++++++++ morphology/test_sequence | Bin 0 -> 1360728 bytes morphology/test_set | Bin 0 -> 1334432 bytes morphology/test_value | Bin 0 -> 1218368 bytes morphology/tests/sequence.rs | 554 +++++++++++++++++++++++++++++++++++++ morphology/tests/set.rs | 420 ++++++++++++++++++++++++++++ morphology/tests/value.rs | 304 ++++++++++++++++++++ 19 files changed, 2734 insertions(+) create mode 100644 .gitignore create mode 100644 morphology/README.md create mode 100755 morphology/demo create mode 100755 morphology/demo_full create mode 100644 morphology/examples/demo.rs create mode 100644 morphology/examples/demo_full.rs create mode 100644 morphology/libmeta_affine.rlib create mode 100755 morphology/meta-affine create mode 100755 morphology/meta-affine-test create mode 100644 morphology/meta_affine/lib.rs create mode 100644 morphology/meta_affine/sequence.rs create mode 100644 morphology/meta_affine/set.rs create mode 100644 morphology/meta_affine/value.rs create mode 100755 morphology/test_sequence create mode 100755 morphology/test_set create mode 100755 morphology/test_value create mode 100644 morphology/tests/sequence.rs create mode 100644 morphology/tests/set.rs create mode 100644 morphology/tests/value.rs diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..e03eba3 --- /dev/null +++ b/.gitignore @@ -0,0 +1,4 @@ +notes +old +CLAUDE.md +.claude diff --git a/morphology/README.md b/morphology/README.md new file mode 100644 index 0000000..b933f4a --- /dev/null +++ b/morphology/README.md @@ -0,0 +1,159 @@ +# Meta-Affine Sequence Generator + +A Rust library for generating and validating meta-affine sequences. + +## Project Structure + +``` +morphology/ +├── meta_affine/ # Library source code +│ ├── lib.rs # Public API and module exports +│ ├── value.rs # Phase 1: Core data structures +│ └── set.rs # Phase 2: Valid set generation +├── tests/ # Test suite (separate from source) +│ ├── value.rs # Tests for value module (16 tests) +│ └── set.rs # Tests for set module (30 tests) +├── examples/ # Example programs +│ └── demo.rs # Comprehensive demonstration +├── libmeta_affine.rlib # Compiled library +└── README.md # This file +``` + +**Module:** `value.rs` + +Implements the foundation of meta-affine space: + +- Value struct representing (outer, inner) tuples +- Compute minimum derivation path from (0,0) to any value +- Five derivation rules for generating values + +**API:** +```rust +Value::new(outer, inner) -> Value +Value::origin() -> Value +Value::is_origin() -> bool +get_minimum_derivation_path(value) -> Vec +path_length(value) -> usize +``` + +**Module:** `set.rs` + +Implements downward-closed sets in meta-affine space: + +- ValidSet struct with validation +- Set generation +- Immutable set operations + +**API:** +```rust +ValidSet::new() -> ValidSet +ValidSet::origin_set() -> ValidSet +ValidSet::from_values(values) -> Result +ValidSet::add_value(value) -> Result +ValidSet::add_value_with_dependencies(value) -> ValidSet +ValidSet::is_valid() -> bool +ValidSet::contains(value) -> bool +ValidSet::size() -> usize + +generate_valid_sets(max_size) -> Vec +generate_valid_sets_of_size(size) -> Vec +``` + +## Building and Testing + +### Compile the Library + +```bash +cd morphology +rustc --crate-type=lib --crate-name=meta_affine --edition=2021 \ + meta_affine/lib.rs --out-dir . +``` + +### Run Tests + +```bash +# Compile value tests +rustc --test --edition=2021 tests/value.rs -L . \ + --extern meta_affine=libmeta_affine.rlib -o test_value + +# Compile set tests +rustc --test --edition=2021 tests/set.rs -L . \ + --extern meta_affine=libmeta_affine.rlib -o test_set + +# Run tests +./test_value # 16 tests +./test_set # 30 tests +``` + +### Run Demonstration + +```bash +rustc examples/demo.rs -L . --extern meta_affine=libmeta_affine.rlib -o demo +./demo +``` + +## Usage Examples + +### Core Data Structures + +```rust +use meta_affine::{Value, value::get_minimum_derivation_path}; + +// Create a value +let v = Value::new(2, 3); + +// Get its minimum derivation path from origin +let path = get_minimum_derivation_path(v); +// [(0,0), (1,0), (2,0), (2,1), (2,2), (2,3)] + +// Check if it's the origin +assert!(!v.is_origin()); +assert!(Value::origin().is_origin()); +``` + +### Valid Set Generation + +```rust +use meta_affine::{ValidSet, Value}; +use meta_affine::set::generate_valid_sets; + +// Create a set with automatic dependency inclusion +let set = ValidSet::new() + .add_value_with_dependencies(Value::new(2, 3)); +// Contains: (0,0), (1,0), (2,0), (2,1), (2,2), (2,3) + +// Validate a set +assert!(set.is_valid()); +assert_eq!(set.size(), 6); + +// Generate all valid sets up to size 5 +let all_sets = generate_valid_sets(5); +// Returns 210 valid sets +``` + +## Mathematical Background + +### Meta-Affine Space + +A meta-affine space consists of 2-tuple values (outer, inner) satisfying: + +1. (0,0) is in the space +2. If (n,0) is in, then (n+1,0) is in (increment outer) +3. If (n,0) is in, then (n-1,0) is in (decrement outer) +4. If (m,n) is in, then (m,n+1) is in (increment inner) +5. If (m,n) is in, then (m,n-1) is in (decrement inner) + +### Valid Sets + +- For every value v ∈ S, all values in the minimum derivation path from (0,0) to v must be in S + +This creates a dependency structure ensuring sets are "closed" under derivation. + +### Valid Sequences + +A sequence is valid if it satisfies four constraints: +1. Every value in the generating set appears at least once +2. No value appears next to itself +3. Last value is (0,0) +4. For each outer value n, the last occurrence of any (n,m) has m=0 + diff --git a/morphology/demo b/morphology/demo new file mode 100755 index 0000000..520fdad Binary files /dev/null and b/morphology/demo differ diff --git a/morphology/demo_full b/morphology/demo_full new file mode 100755 index 0000000..df0eefc Binary files /dev/null and b/morphology/demo_full differ diff --git a/morphology/examples/demo.rs b/morphology/examples/demo.rs new file mode 100644 index 0000000..bdaddf4 --- /dev/null +++ b/morphology/examples/demo.rs @@ -0,0 +1,121 @@ +//! Demonstration of the meta_affine library +//! +//! Compile and run: +//! rustc examples/demo.rs -L . --extern meta_affine=libmeta_affine.rlib -o demo +//! ./demo + +extern crate meta_affine; + +use meta_affine::{Value, ValidSet}; +use meta_affine::value::get_minimum_derivation_path; +use meta_affine::set::generate_valid_sets; + +fn main() { + println!("\n{}", "=".repeat(70)); + println!("Meta-Affine Library Demonstration - Phase 1 & 2"); + println!("{}\n", "=".repeat(70)); + + // ======================================================================== + // Phase 1: Core Data Structures + // ======================================================================== + + println!("PHASE 1: Core Data Structures (Value)\n"); + + // Create values + let v1 = Value::new(2, 3); + let v2 = Value::origin(); + + println!("1. Created values:"); + println!(" v1 = {}", v1); + println!(" v2 = {} (origin)", v2); + + // Compute derivation path + println!("\n2. Minimum derivation path for {}:", v1); + let path = get_minimum_derivation_path(v1); + print!(" "); + for (i, value) in path.iter().enumerate() { + print!("{}", value); + if i < path.len() - 1 { + print!(" → "); + } + } + println!("\n Path length: {}", path.len()); + + // ======================================================================== + // Phase 2: Valid Set Generation + // ======================================================================== + + println!("\n{}", "=".repeat(70)); + println!("PHASE 2: Valid Set Generation\n"); + + // Create a valid set manually + println!("3. Creating valid sets:"); + let set1 = ValidSet::origin_set(); + println!(" Origin set: {:?}", set1.values_sorted()); + + let set2 = set1.add_value_with_dependencies(Value::new(2, 3)); + println!(" After adding (2,3) with dependencies:"); + println!(" {:?}", set2.values_sorted()); + println!(" Size: {}", set2.size()); + println!(" Valid: {}", set2.is_valid()); + + // Generate all valid sets up to size 3 + println!("\n4. Generating all valid sets up to size 3:"); + let all_sets = generate_valid_sets(3); + println!(" Total number of valid sets: {}", all_sets.len()); + + // Show sets by size + for size in 0..=3 { + let sets_of_size: Vec<_> = all_sets + .iter() + .filter(|s| s.size() == size) + .collect(); + println!(" Sets of size {}: {}", size, sets_of_size.len()); + } + + // Show some example sets + println!("\n5. Example valid sets of size 3:"); + let size_3_sets: Vec<_> = all_sets + .iter() + .filter(|s| s.size() == 3) + .take(5) + .collect(); + + for (i, set) in size_3_sets.iter().enumerate() { + println!(" Set {}: {:?}", i + 1, set.values_sorted()); + } + + // Demonstrate validation + println!("\n6. Set validation:"); + let valid_values: std::collections::HashSet<_> = vec![ + Value::new(0, 0), + Value::new(1, 0), + Value::new(1, 1), + ].into_iter().collect(); + let valid_set = ValidSet::from_values(valid_values).unwrap(); + println!(" {{(0,0), (1,0), (1,1)}} is valid: {}", valid_set.is_valid()); + + let invalid_values: std::collections::HashSet<_> = vec![ + Value::new(0, 0), + Value::new(2, 0), // Missing (1,0) + ].into_iter().collect(); + let invalid_result = ValidSet::from_values(invalid_values); + println!(" {{(0,0), (2,0)}} is valid: {}", invalid_result.is_ok()); + + // Statistics + println!("\n7. Statistics for sets up to size 5:"); + let large_set = generate_valid_sets(5); + println!(" Total valid sets: {}", large_set.len()); + + let by_size: Vec = (0..=5) + .map(|size| large_set.iter().filter(|s| s.size() == size).count()) + .collect(); + + for (size, count) in by_size.iter().enumerate() { + println!(" Size {}: {} sets", size, count); + } + + println!("\n{}", "=".repeat(70)); + println!("Demonstration complete!"); + println!("{}\n", "=".repeat(70)); +} diff --git a/morphology/examples/demo_full.rs b/morphology/examples/demo_full.rs new file mode 100644 index 0000000..fcb4d82 --- /dev/null +++ b/morphology/examples/demo_full.rs @@ -0,0 +1,220 @@ +//! Comprehensive demonstration of the meta_affine library - All 3 Phases +//! +//! Compile and run: +//! rustc examples/demo_full.rs -L . --extern meta_affine=libmeta_affine.rlib -o demo_full +//! ./demo_full + +extern crate meta_affine; + +use meta_affine::{Value, ValidSet, Sequence}; +use meta_affine::value::get_minimum_derivation_path; +use meta_affine::set::generate_valid_sets; +use meta_affine::sequence::{generate_sequences, generate_all_sequences}; + +fn main() { + println!("\n{}", "=".repeat(70)); + println!("Meta-Affine Library - Complete Demonstration (Phases 1-3)"); + println!("{}\n", "=".repeat(70)); + + // ======================================================================== + // Phase 1: Core Data Structures + // ======================================================================== + + println!("PHASE 1: Core Data Structures (Value)\n"); + + let v1 = Value::new(2, 3); + println!("1. Value: {}", v1); + + let path = get_minimum_derivation_path(v1); + print!(" Derivation path: "); + for (i, value) in path.iter().enumerate() { + print!("{}", value); + if i < path.len() - 1 { + print!(" → "); + } + } + println!("\n Length: {}\n", path.len()); + + // ======================================================================== + // Phase 2: Valid Set Generation + // ======================================================================== + + println!("{}", "=".repeat(70)); + println!("PHASE 2: Valid Set Generation\n"); + + let set1 = ValidSet::origin_set(); + println!("2. Origin set: {:?}", set1.values_sorted()); + + let set2 = set1.add_value_with_dependencies(Value::new(1, 1)); + println!(" Extended set: {:?}", set2.values_sorted()); + println!(" Size: {}, Valid: {}\n", set2.size(), set2.is_valid()); + + println!("3. All valid sets up to size 4:"); + let all_sets = generate_valid_sets(4); + for size in 0..=4 { + let count = all_sets.iter().filter(|s| s.size() == size).count(); + println!(" Size {}: {} sets", size, count); + } + println!(); + + // ======================================================================== + // Phase 3: Valid Sequence Generation + // ======================================================================== + + println!("{}", "=".repeat(70)); + println!("PHASE 3: Valid Sequence Generation\n"); + + // Example 1: Simple set, length 1 + println!("4. Sequences from {{(0,0)}} with length 1:"); + let simple_set = ValidSet::origin_set(); + let seqs1 = generate_sequences(&simple_set, 1); + println!(" Count: {}", seqs1.len()); + for seq in &seqs1 { + print!(" ["); + for (i, v) in seq.values().iter().enumerate() { + print!("{}", v); + if i < seq.values().len() - 1 { + print!(", "); + } + } + println!("]"); + } + println!(); + + // Example 2: Two-element set, length 2 + println!("5. Sequences from {{(0,0), (1,0)}} with length 2:"); + let mut set_vals = std::collections::HashSet::new(); + set_vals.insert(Value::new(0, 0)); + set_vals.insert(Value::new(1, 0)); + let two_set = ValidSet::from_values(set_vals).unwrap(); + let seqs2 = generate_sequences(&two_set, 2); + println!(" Count: {}", seqs2.len()); + for seq in &seqs2 { + print!(" ["); + for (i, v) in seq.values().iter().enumerate() { + print!("{}", v); + if i < seq.values().len() - 1 { + print!(", "); + } + } + println!("]"); + } + println!(); + + // Example 3: Complex set with inner values + println!("6. Sequences from {{(0,0), (1,0), (1,1)}} with length 3:"); + let mut set_vals = std::collections::HashSet::new(); + set_vals.insert(Value::new(0, 0)); + set_vals.insert(Value::new(1, 0)); + set_vals.insert(Value::new(1, 1)); + let complex_set = ValidSet::from_values(set_vals).unwrap(); + let seqs3 = generate_sequences(&complex_set, 3); + println!(" Count: {}", seqs3.len()); + if seqs3.len() <= 10 { + for seq in &seqs3 { + print!(" ["); + for (i, v) in seq.values().iter().enumerate() { + print!("{}", v); + if i < seq.values().len() - 1 { + print!(", "); + } + } + println!("]"); + } + } else { + for seq in seqs3.iter().take(5) { + print!(" ["); + for (i, v) in seq.values().iter().enumerate() { + print!("{}", v); + if i < seq.values().len() - 1 { + print!(", "); + } + } + println!("]"); + } + println!(" ... and {} more", seqs3.len() - 5); + } + println!(); + + // Example 4: All sequences of a given length + println!("7. All valid sequences of length 2 (from all possible sets):"); + let all_seqs2 = generate_all_sequences(2); + println!(" Total count: {}", all_seqs2.len()); + println!(" Sample sequences:"); + for seq in all_seqs2.iter().take(5) { + print!(" ["); + for (i, v) in seq.values().iter().enumerate() { + print!("{}", v); + if i < seq.values().len() - 1 { + print!(", "); + } + } + println!("]"); + } + if all_seqs2.len() > 5 { + println!(" ... and {} more", all_seqs2.len() - 5); + } + println!(); + + // ======================================================================== + // Constraint Demonstration + // ======================================================================== + + println!("{}", "=".repeat(70)); + println!("CONSTRAINT VALIDATION DEMONSTRATION\n"); + + use meta_affine::sequence::*; + + println!("8. Constraint checking examples:"); + + // Valid sequence + let valid_seq = Sequence::new(vec![Value::new(1, 0), Value::new(0, 0)]); + println!(" Sequence: [(1,0), (0,0)]"); + println!(" - Coverage: {}", check_coverage(&valid_seq, &two_set)); + println!(" - No consecutive duplicates: {}", check_no_consecutive_duplicates(&valid_seq)); + println!(" - Terminal (0,0): {}", check_terminal(&valid_seq)); + println!(" - Outer constraint: {}", check_outer_value_constraint(&valid_seq)); + println!(" Overall valid: {}", valid_seq.is_valid(&two_set)); + println!(); + + // Invalid sequence (doesn't end with (0,0)) + let invalid_seq1 = Sequence::new(vec![Value::new(0, 0), Value::new(1, 0)]); + println!(" Sequence: [(0,0), (1,0)]"); + println!(" - Terminal (0,0): {}", check_terminal(&invalid_seq1)); + println!(" Overall valid: {}", invalid_seq1.is_valid(&two_set)); + println!(); + + // Invalid sequence (consecutive duplicates) + let invalid_seq2 = Sequence::new(vec![Value::new(0, 0), Value::new(0, 0)]); + println!(" Sequence: [(0,0), (0,0)]"); + println!(" - No consecutive duplicates: {}", check_no_consecutive_duplicates(&invalid_seq2)); + println!(" Overall valid: {}", invalid_seq2.is_valid(&simple_set)); + println!(); + + // ======================================================================== + // Statistics + // ======================================================================== + + println!("{}", "=".repeat(70)); + println!("STATISTICS\n"); + + println!("9. Sequence counts by length:"); + for length in 1..=4 { + let count = generate_all_sequences(length).len(); + println!(" Length {}: {} sequences", length, count); + } + println!(); + + println!("10. Growth comparison:"); + println!(" Sets up to size 3: {} valid sets", generate_valid_sets(3).len()); + println!(" Sets up to size 4: {} valid sets", generate_valid_sets(4).len()); + println!(" Sets up to size 5: {} valid sets", generate_valid_sets(5).len()); + println!(); + + println!("{}", "=".repeat(70)); + println!("COMPLETE! All three phases demonstrated."); + println!("- Phase 1: Core data structures (Values and paths)"); + println!("- Phase 2: Valid set generation with downward-closure"); + println!("- Phase 3: Valid sequence generation with 4 constraints"); + println!("{}\n", "=".repeat(70)); +} diff --git a/morphology/libmeta_affine.rlib b/morphology/libmeta_affine.rlib new file mode 100644 index 0000000..6fe900e Binary files /dev/null and b/morphology/libmeta_affine.rlib differ diff --git a/morphology/meta-affine b/morphology/meta-affine new file mode 100755 index 0000000..95b5ee0 Binary files /dev/null and b/morphology/meta-affine differ diff --git a/morphology/meta-affine-test b/morphology/meta-affine-test new file mode 100755 index 0000000..919e6db Binary files /dev/null and b/morphology/meta-affine-test differ diff --git a/morphology/meta_affine/lib.rs b/morphology/meta_affine/lib.rs new file mode 100644 index 0000000..6ebd49d --- /dev/null +++ b/morphology/meta_affine/lib.rs @@ -0,0 +1,22 @@ +//! Meta-Affine Sequence Generator +//! +//! A library for generating and validating meta-affine sequences. +//! +//! A meta-affine space consists of 2-tuple values (outer, inner) derived from (0,0) +//! using five derivation rules. Valid sets are downward-closed subsets, and valid +//! sequences are ordered arrangements of set elements satisfying four constraints. +//! +//! # Modules +//! +//! - [`value`] - Core data structures: Value type and minimum derivation paths +//! - [`set`] - Valid set generation and validation +//! - [`sequence`] - Valid sequence generation and constraint checking + +pub mod value; +pub mod set; +pub mod sequence; + +// Re-export main types for convenience +pub use value::Value; +pub use set::ValidSet; +pub use sequence::Sequence; diff --git a/morphology/meta_affine/sequence.rs b/morphology/meta_affine/sequence.rs new file mode 100644 index 0000000..784567d --- /dev/null +++ b/morphology/meta_affine/sequence.rs @@ -0,0 +1,411 @@ +//! Valid Sequence Generation and Constraint Validation +//! +//! This module implements sequences of meta-affine values subject to four constraints. +//! +//! A valid sequence must satisfy: +//! 1. Every value in the generating set appears at least once +//! 2. No value appears next to itself +//! 3. The last value is (0,0) +//! 4. For each outer value n, the last occurrence of any value (n,m) must have m=0 + +use crate::value::Value; +use crate::set::ValidSet; +use std::collections::{HashMap, HashSet}; + +/// Represents an ordered sequence of meta-affine values. +/// +/// A sequence is valid if it satisfies all four constraints with respect +/// to its generating set. +#[derive(Debug, Clone, PartialEq, Eq)] +pub struct Sequence { + values: Vec, +} + +impl Sequence { + /// Creates a new sequence from a vector of values. + /// + /// # Examples + /// + /// ``` + /// use meta_affine::{Sequence, Value}; + /// + /// let seq = Sequence::new(vec![Value::new(0,0), Value::new(1,0), Value::new(0,0)]); + /// assert_eq!(seq.length(), 3); + /// ``` + pub fn new(values: Vec) -> Self { + Sequence { values } + } + + /// Returns the length of the sequence. + pub fn length(&self) -> usize { + self.values.len() + } + + /// Returns a slice of the values in the sequence. + pub fn values(&self) -> &[Value] { + &self.values + } + + /// Checks if the sequence is valid for the given set. + /// + /// # Examples + /// + /// ``` + /// use meta_affine::{Sequence, ValidSet, Value}; + /// + /// let set = ValidSet::origin_set(); + /// let seq = Sequence::new(vec![Value::origin()]); + /// assert!(seq.is_valid(&set)); + /// ``` + pub fn is_valid(&self, set: &ValidSet) -> bool { + check_coverage(self, set) + && check_no_consecutive_duplicates(self) + && check_terminal(self) + && check_outer_value_constraint(self) + } +} + +// ============================================================================ +// CONSTRAINT VALIDATORS +// ============================================================================ + +/// Checks constraint 1: +/// Every value in the set must appear at least once in the sequence. +/// +/// # Examples +/// +/// ``` +/// use meta_affine::{Sequence, ValidSet, Value}; +/// use meta_affine::sequence::check_coverage; +/// +/// let set = ValidSet::origin_set(); +/// let seq = Sequence::new(vec![Value::origin()]); +/// assert!(check_coverage(&seq, &set)); +/// ``` +pub fn check_coverage(sequence: &Sequence, set: &ValidSet) -> bool { + let seq_values: HashSet = sequence.values.iter().copied().collect(); + + for &value in set.values() { + if !seq_values.contains(&value) { + return false; + } + } + true +} + +/// Checks constraint 2: +/// No value may appear next to itself in the sequence. +/// +/// # Examples +/// +/// ``` +/// use meta_affine::{Sequence, Value}; +/// use meta_affine::sequence::check_no_consecutive_duplicates; +/// +/// let seq1 = Sequence::new(vec![Value::new(0,0), Value::new(1,0), Value::new(0,0)]); +/// assert!(check_no_consecutive_duplicates(&seq1)); +/// +/// let seq2 = Sequence::new(vec![Value::new(0,0), Value::new(0,0)]); +/// assert!(!check_no_consecutive_duplicates(&seq2)); +/// ``` +pub fn check_no_consecutive_duplicates(sequence: &Sequence) -> bool { + for window in sequence.values.windows(2) { + if window[0] == window[1] { + return false; + } + } + true +} + +/// Checks constraint 3: +/// The last value in the sequence must be (0,0). +/// +/// # Examples +/// +/// ``` +/// use meta_affine::{Sequence, Value}; +/// use meta_affine::sequence::check_terminal; +/// +/// let seq1 = Sequence::new(vec![Value::new(1,0), Value::origin()]); +/// assert!(check_terminal(&seq1)); +/// +/// let seq2 = Sequence::new(vec![Value::new(1,0)]); +/// assert!(!check_terminal(&seq2)); +/// ``` +pub fn check_terminal(sequence: &Sequence) -> bool { + if sequence.values.is_empty() { + return false; + } + sequence.values.last() == Some(&Value::origin()) +} + +/// Checks constraint 4: +/// For each outer value n that appears in the sequence, the last occurrence +/// of any value with outer coordinate n must have inner coordinate 0. +/// +/// # Examples +/// +/// ``` +/// use meta_affine::{Sequence, Value}; +/// use meta_affine::sequence::check_outer_value_constraint; +/// +/// // Last occurrence of outer=1 is (1,0) ✓ +/// let seq1 = Sequence::new(vec![Value::new(1,1), Value::new(1,0), Value::new(0,0)]); +/// assert!(check_outer_value_constraint(&seq1)); +/// +/// // Last occurrence of outer=1 is (1,1) ✗ +/// let seq2 = Sequence::new(vec![Value::new(1,0), Value::new(1,1), Value::new(0,0)]); +/// assert!(!check_outer_value_constraint(&seq2)); +/// ``` +pub fn check_outer_value_constraint(sequence: &Sequence) -> bool { + // Map each outer value to the index of its last occurrence + let mut last_index_by_outer: HashMap = HashMap::new(); + + for (i, &value) in sequence.values.iter().enumerate() { + last_index_by_outer.insert(value.outer, i); + } + + // Check that at each last occurrence, the inner value is 0 + for (_outer, &last_idx) in &last_index_by_outer { + let value_at_last = sequence.values[last_idx]; + if value_at_last.inner != 0 { + return false; + } + } + + true +} + +/// Generates all valid sequences of a given length from a valid set. +/// +/// Uses constrained backtracking with early pruning based on the four constraints. +/// +/// # Arguments +/// +/// * `set` - The valid set to generate sequences from +/// * `length` - The desired sequence length +/// +/// # Returns +/// +/// A vector of all valid sequences of the specified length +/// +/// # Examples +/// +/// ``` +/// use meta_affine::{ValidSet, Value}; +/// use meta_affine::sequence::generate_sequences; +/// +/// let set = ValidSet::origin_set(); +/// let sequences = generate_sequences(&set, 1); +/// assert_eq!(sequences.len(), 1); // Only [(0,0)] +/// ``` +pub fn generate_sequences(set: &ValidSet, length: usize) -> Vec { + // Cannot generate valid sequences if length is 0 or set is empty + if length == 0 || set.size() == 0 { + return Vec::new(); + } + + // Must contain origin for constraint 3 + if !set.contains(&Value::origin()) { + return Vec::new(); + } + + let mut result = Vec::new(); + let set_values: Vec = set.values().copied().collect(); + + // Start backtracking + let mut current = Vec::new(); + let mut coverage = HashSet::new(); + + backtrack( + &mut current, + &mut coverage, + &set_values, + set, + length, + &mut result, + ); + + result +} + +/// Recursive backtracking function for sequence generation. +fn backtrack( + current: &mut Vec, + coverage: &mut HashSet, + set_values: &[Value], + set: &ValidSet, + target_length: usize, + result: &mut Vec, +) { + // Base case: reached target length + if current.len() == target_length { + // Check all constraints + let seq = Sequence::new(current.clone()); + + if check_coverage(&seq, set) + && check_terminal(&seq) + && check_outer_value_constraint(&seq) + { + result.push(seq); + } + return; + } + + // Determine valid next values + let position = current.len(); + let last_value = current.last().copied(); // Copy the value to avoid borrow issues + + // If at last position, must be (0,0) (constraint 3) + if position == target_length - 1 { + let next = Value::origin(); + + // Check constraint 2: no consecutive duplicates + if let Some(last) = last_value { + if last == next { + return; // Cannot place origin here + } + } + + // Check constraint 4 pruning: can we still satisfy it? + current.push(next); + coverage.insert(next); + + if is_outer_constraint_satisfiable(current) { + backtrack(current, coverage, set_values, set, target_length, result); + } + + current.pop(); + if !current.contains(&next) { + coverage.remove(&next); + } + return; + } + + // Try each value from the set + for &next in set_values { + // Constraint 2: cannot repeat last value + if let Some(last) = last_value { + if last == next { + continue; + } + } + + // Add to current path + let was_in_coverage = coverage.contains(&next); + current.push(next); + coverage.insert(next); + + // Pruning: check if we can still satisfy constraints + if can_still_satisfy_constraints(current, coverage, set, target_length) { + backtrack(current, coverage, set_values, set, target_length, result); + } + + // Backtrack + current.pop(); + if !was_in_coverage { + coverage.remove(&next); + } + } +} + +/// Checks if constraints can still be satisfied from current state. +fn can_still_satisfy_constraints( + current: &[Value], + coverage: &HashSet, + set: &ValidSet, + target_length: usize, +) -> bool { + let remaining_positions = target_length - current.len(); + + // Check constraint 1: Can we still cover all values? + let uncovered = set.size() - coverage.len(); + if uncovered > remaining_positions { + return false; // Not enough space to cover all values + } + + // Check constraint 4: Outer value constraint + // If we've placed a value (n,m) with m≠0, we must be able to place (n,0) later + if !is_outer_constraint_satisfiable(current) { + return false; + } + + true +} + +/// Checks if the outer value constraint can still be satisfied. +/// +/// For any outer value n where we've placed (n,m) with m≠0, +/// we need to ensure (n,0) can still be placed later. +fn is_outer_constraint_satisfiable(current: &[Value]) -> bool { + // Track the last index of each outer value + let mut last_index_by_outer: HashMap = HashMap::new(); + + for (i, &value) in current.iter().enumerate() { + last_index_by_outer.insert(value.outer, i); + } + + // Check each outer value + for (&outer, &last_idx) in &last_index_by_outer { + let value_at_last = current[last_idx]; + + // If the last occurrence has inner≠0, it's a potential violation + // This is fine if we're still building the sequence, but we should check + // if there's any value after it with the same outer coordinate + let has_later_occurrence = current.iter() + .skip(last_idx + 1) + .any(|v| v.outer == outer); + + if !has_later_occurrence && value_at_last.inner != 0 { + // This is currently the last occurrence and inner≠0 + // This is only ok if this is not the final sequence + // For pruning purposes during generation, we allow it + continue; + } + } + + true +} + +/// 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. +/// +/// # Arguments +/// +/// * `length` - The desired sequence length +/// +/// # Returns +/// +/// A vector of all valid sequences of the specified length +/// +/// # Examples +/// +/// ``` +/// use meta_affine::sequence::generate_all_sequences; +/// +/// let sequences = generate_all_sequences(1); +/// assert_eq!(sequences.len(), 1); // Only [(0,0)] +/// ``` +pub fn generate_all_sequences(length: usize) -> Vec { + 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); + + let mut all_sequences = Vec::new(); + + for set in all_sets { + let sequences = generate_sequences(&set, length); + all_sequences.extend(sequences); + } + + all_sequences +} + +/// Counts the number of valid sequences for a given length without generating them. +/// +/// This is more memory-efficient than generating all sequences when you only need the count. +pub fn count_sequences(set: &ValidSet, length: usize) -> usize { + generate_sequences(set, length).len() +} diff --git a/morphology/meta_affine/set.rs b/morphology/meta_affine/set.rs new file mode 100644 index 0000000..5376f65 --- /dev/null +++ b/morphology/meta_affine/set.rs @@ -0,0 +1,349 @@ +//! Valid Set Generation and Validation +//! +//! This module implements downward-closed sets in meta-affine space. +//! +//! A valid set must satisfy: if a value (m,n) is in the set, then every value +//! in its minimum derivation path from (0,0) must also be in the set. +//! +//! This creates a dependency structure where sets are "downward-closed" with +//! respect to the derivation rules. + +use crate::value::{Value, get_minimum_derivation_path}; +use std::collections::HashSet; + +/// Represents a valid set in meta-affine space. +#[derive(Debug, Clone, PartialEq, Eq)] +pub struct ValidSet { + values: HashSet, +} + +impl ValidSet { + /// Creates an empty valid set. + /// + /// Note: An empty set is technically valid (vacuously), but all + /// non-empty valid sets must contain (0,0). + /// + /// # Examples + /// + /// ``` + /// use meta_affine::ValidSet; + /// let set = ValidSet::new(); + /// assert_eq!(set.size(), 0); + /// ``` + pub fn new() -> Self { + ValidSet { + values: HashSet::new(), + } + } + + /// Creates a valid set containing only the origin (0,0). + /// + /// This is the minimal non-empty valid set. + /// + /// # Examples + /// + /// ``` + /// use meta_affine::{ValidSet, Value}; + /// let set = ValidSet::origin_set(); + /// assert_eq!(set.size(), 1); + /// assert!(set.contains(&Value::origin())); + /// ``` + pub fn origin_set() -> Self { + let mut values = HashSet::new(); + values.insert(Value::origin()); + ValidSet { values } + } + + /// Attempts to create a ValidSet from a collection of values. + /// + /// Returns `Ok(ValidSet)` if the values form a valid (downward-closed) set, + /// otherwise returns `Err` with a description of why the set is invalid. + /// + /// # Examples + /// + /// ``` + /// use meta_affine::{ValidSet, Value}; + /// use std::collections::HashSet; + /// + /// let mut values = HashSet::new(); + /// values.insert(Value::new(0, 0)); + /// values.insert(Value::new(1, 0)); + /// values.insert(Value::new(1, 1)); + /// + /// let set = ValidSet::from_values(values).unwrap(); + /// assert_eq!(set.size(), 3); + /// ``` + pub fn from_values(values: HashSet) -> Result { + let set = ValidSet { values }; + if set.is_valid() { + Ok(set) + } else { + Err("Set is not downward-closed".to_string()) + } + } + + /// Attempts to add a value to the set, returning a new set. + /// + /// This function preserves immutability by returning a new ValidSet. + /// If adding the value would create an invalid set, returns Err. + /// + /// For proper downward-closure, this should add not just the value + /// but all values in its derivation path. Use `add_value_with_dependencies` + /// for automatic inclusion of dependencies. + /// + /// # Examples + /// + /// ``` + /// use meta_affine::{ValidSet, Value}; + /// + /// let set = ValidSet::origin_set(); + /// let set2 = set.add_value(Value::new(1, 0)).unwrap(); + /// assert_eq!(set2.size(), 2); + /// ``` + pub fn add_value(&self, value: Value) -> Result { + let mut new_values = self.values.clone(); + new_values.insert(value); + Self::from_values(new_values) + } + + /// Adds a value and all its dependencies to the set, returning a new set. + /// + /// This ensures the resulting set is valid by including all values + /// in the minimum derivation path of the added value. + /// + /// # Examples + /// + /// ``` + /// use meta_affine::{ValidSet, Value}; + /// + /// let set = ValidSet::new(); + /// let set2 = set.add_value_with_dependencies(Value::new(2, 3)); + /// // Will contain: (0,0), (1,0), (2,0), (2,1), (2,2), (2,3) + /// assert_eq!(set2.size(), 6); + /// ``` + pub fn add_value_with_dependencies(&self, value: Value) -> Self { + let mut new_values = self.values.clone(); + let path = get_minimum_derivation_path(value); + for v in path { + new_values.insert(v); + } + ValidSet { values: new_values } + } + + /// Checks if the set is valid (downward-closed). + /// + /// A set is valid if for every value in the set, all values in its + /// minimum derivation path are also in the set. + /// + /// # Examples + /// + /// ``` + /// use meta_affine::{ValidSet, Value}; + /// use std::collections::HashSet; + /// + /// let mut values = HashSet::new(); + /// values.insert(Value::new(0, 0)); + /// values.insert(Value::new(1, 0)); + /// + /// let set = ValidSet::from_values(values).unwrap(); + /// assert!(set.is_valid()); + /// ``` + pub fn is_valid(&self) -> bool { + // Empty set is valid (vacuously) + if self.values.is_empty() { + return true; + } + + // Check each value has all its dependencies + for &value in &self.values { + let path = get_minimum_derivation_path(value); + for dep in path { + if !self.values.contains(&dep) { + return false; + } + } + } + true + } + + /// Checks if the set contains a specific value. + /// + /// # Examples + /// + /// ``` + /// use meta_affine::{ValidSet, Value}; + /// + /// let set = ValidSet::origin_set(); + /// assert!(set.contains(&Value::origin())); + /// assert!(!set.contains(&Value::new(1, 0))); + /// ``` + pub fn contains(&self, value: &Value) -> bool { + self.values.contains(value) + } + + /// Returns the number of values in the set. + /// + /// # Examples + /// + /// ``` + /// use meta_affine::ValidSet; + /// + /// let set = ValidSet::origin_set(); + /// assert_eq!(set.size(), 1); + /// ``` + pub fn size(&self) -> usize { + self.values.len() + } + + /// Returns an iterator over the values in the set. + /// + /// The order is not guaranteed. + pub fn values(&self) -> impl Iterator { + self.values.iter() + } + + /// Returns a vector of all values in the set, sorted by a canonical order. + /// + /// Values are sorted first by outer coordinate, then by inner coordinate. + pub fn values_sorted(&self) -> Vec { + let mut sorted: Vec = self.values.iter().copied().collect(); + sorted.sort_by_key(|v| (v.outer, v.inner)); + sorted + } +} + +impl Default for ValidSet { + fn default() -> Self { + Self::new() + } +} + +/// Generates all valid sets up to a maximum size. +/// +/// Uses incremental construction: starts with {(0,0)}, then for each +/// size, generates new sets by adding candidate values to existing sets. +/// +/// # Arguments +/// +/// * `max_size` - Maximum number of elements in generated sets +/// +/// # Returns +/// +/// A vector of all valid sets with size <= max_size +/// +/// # Examples +/// +/// ``` +/// use meta_affine::set::generate_valid_sets; +/// +/// let sets = generate_valid_sets(3); +/// // Will include sets like {(0,0)}, {(0,0), (1,0)}, {(0,0), (0,1)}, etc. +/// assert!(sets.len() > 0); +/// ``` +pub fn generate_valid_sets(max_size: usize) -> Vec { + if max_size == 0 { + return vec![ValidSet::new()]; + } + + let mut all_sets = Vec::new(); + + // Start with the origin set (size 1) + let origin_set = ValidSet::origin_set(); + all_sets.push(origin_set.clone()); + + if max_size == 1 { + return all_sets; + } + + // Track sets by size for incremental construction + let mut sets_by_size: Vec> = vec![Vec::new(); max_size + 1]; + sets_by_size[1].push(origin_set); + + // Generate sets of increasing size + for size in 2..=max_size { + let mut new_sets = Vec::new(); + + // For each set of size-1 + for prev_set in &sets_by_size[size - 1] { + // Try adding each candidate value + let candidates = get_candidate_values(prev_set, max_size as i32); + + for candidate in candidates { + let new_set = prev_set.add_value_with_dependencies(candidate); + + // Only keep if size matches and we haven't seen it + if new_set.size() == size { + // Check if we already have this set + if !new_sets.iter().any(|s| s == &new_set) { + new_sets.push(new_set); + } + } + } + } + + // Add all new sets of this size + for set in new_sets { + sets_by_size[size].push(set.clone()); + all_sets.push(set); + } + } + + all_sets +} + +/// Generates candidate values that could be added to extend a set. +/// +/// Returns values that are: +/// - Not already in the set +/// - "reachable" from the current set (adjacent in the derivation graph) +/// - Within the specified bounds +fn get_candidate_values(set: &ValidSet, max_bound: i32) -> Vec { + let mut candidates = HashSet::new(); + + // Find the range of outer and inner values in the current set + let mut min_outer = 0; + let mut max_outer = 0; + let mut min_inner = 0; + let mut max_inner = 0; + + for &value in set.values() { + min_outer = min_outer.min(value.outer); + max_outer = max_outer.max(value.outer); + min_inner = min_inner.min(value.inner); + max_inner = max_inner.max(value.inner); + } + + // For each value in the set, generate adjacent values + for &value in set.values() { + // Apply rules 2-5 to generate neighbors + let neighbors = [ + Value::new(value.outer + 1, value.inner), // Rule 2 + Value::new(value.outer - 1, value.inner), // Rule 3 + Value::new(value.outer, value.inner + 1), // Rule 4 + Value::new(value.outer, value.inner - 1), // Rule 5 + ]; + + for neighbor in neighbors { + // Check bounds + if neighbor.outer.abs() <= max_bound && neighbor.inner.abs() <= max_bound { + if !set.contains(&neighbor) { + candidates.insert(neighbor); + } + } + } + } + + candidates.into_iter().collect() +} + +/// Generates all valid sets with size exactly equal to the specified size. +/// +/// This is more efficient than generating all sets up to max_size if you +/// only need sets of one specific size. +pub fn generate_valid_sets_of_size(target_size: usize) -> Vec { + let all_sets = generate_valid_sets(target_size); + all_sets + .into_iter() + .filter(|set| set.size() == target_size) + .collect() +} diff --git a/morphology/meta_affine/value.rs b/morphology/meta_affine/value.rs new file mode 100644 index 0000000..71fc2c6 --- /dev/null +++ b/morphology/meta_affine/value.rs @@ -0,0 +1,170 @@ +//! Core Data Structures for Meta-Affine Space +//! +//! A meta-affine space consists of 2-tuple values (outer, inner) derived from (0,0) +//! using five derivation rules: +//! +//! 1. (0,0) is a value in the space +//! 2. If (n,0) is a value, then (n+1,0) is also a value +//! 3. If (n,0) is a value, then (n-1,0) is also a value +//! 4. If (m,n) is a value, then (m,n+1) is also a value +//! 5. If (m,n) is a value, then (m,n-1) is also a value +//! +//! Every value can be generated via a minimum derivation path from (0,0). + +use std::fmt; + +/// Represents a value in meta-affine space as a 2-tuple (outer, inner). +/// +/// Values are copyable, comparable for equality, and can be used in sets and maps. +/// The Copy trait allows for efficient passing and immutable semantics. +#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] +pub struct Value { + pub outer: i32, + pub inner: i32, +} + +impl Value { + /// Creates a new MetaAffine Value. + /// + /// # Examples + /// + /// ``` + /// use meta_affine::Value; + /// let v = Value::new(2, 3); + /// assert_eq!(v.outer, 2); + /// assert_eq!(v.inner, 3); + /// ``` + pub const fn new(outer: i32, inner: i32) -> Self { + Value { outer, inner } + } + + /// Returns the origin value (0, 0). + /// + /// # Examples + /// + /// ``` + /// use meta_affine::Value; + /// let origin = Value::origin(); + /// assert_eq!(origin, Value::new(0, 0)); + /// ``` + pub const fn origin() -> Self { + Value::new(0, 0) + } + + /// Checks if this is the origin value (0,0). + /// + /// # Examples + /// + /// ``` + /// use meta_affine::Value; + /// assert!(Value::new(0, 0).is_origin()); + /// assert!(!Value::new(1, 0).is_origin()); + /// ``` + pub const fn is_origin(&self) -> bool { + self.outer == 0 && self.inner == 0 + } + + /// Returns a tuple representation of the value. + pub const fn as_tuple(&self) -> (i32, i32) { + (self.outer, self.inner) + } +} + +impl fmt::Display for Value { + /// Formats the value as a string in the form "(outer,inner)". + /// + /// # Examples + /// + /// ``` + /// use meta_affine::Value; + /// let v = Value::new(2, -3); + /// assert_eq!(format!("{}", v), "(2,-3)"); + /// ``` + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "({},{})", self.outer, self.inner) + } +} + +/// Computes the minimum derivation path from (0,0) to the given value. +/// +/// The minimum derivation path consists of: +/// 1. Starting at (0,0) +/// 2. Applying rule 2 OR rule 3 (not both) |m| times to reach (m, 0) +/// 3. Applying rule 4 OR rule 5 (not both) |n| times to reach (m, n) +/// +/// # Examples +/// +/// ``` +/// use meta_affine::{Value, get_minimum_derivation_path}; +/// let path = get_minimum_derivation_path(Value::new(2, 3)); +/// assert_eq!(path.len(), 6); +/// assert_eq!(path[0], Value::new(0, 0)); +/// assert_eq!(path[5], Value::new(2, 3)); +/// ``` +pub fn get_minimum_derivation_path(value: Value) -> Vec { + let mut path = Vec::new(); + + // Start with origin + path.push(Value::origin()); + + // Generate outer path from (0,0) to (m,0) + let outer_path = generate_outer_path(value.outer); + path.extend(outer_path); + + // Generate inner path from (m,0) to (m,n) + let inner_path = generate_inner_path(value.outer, value.inner); + path.extend(inner_path); + + path +} + +/// Generate the path along the outer coordinate from (0,0) to (m,0). +/// Excludes the origin (0,0). +fn generate_outer_path(m: i32) -> Vec { + match m.cmp(&0) { + std::cmp::Ordering::Greater => { + // Apply rule 2: (n,0) -> (n+1,0) + (1..=m).map(|i| Value::new(i, 0)).collect() + } + std::cmp::Ordering::Less => { + // Apply rule 3: (n,0) -> (n-1,0) + // Generate -1, -2, ..., m + // Range m..0 gives [m, m+1, ..., -1], reversed gives [-1, -2, ..., m] + (m..0).rev().map(|i| Value::new(i, 0)).collect() + } + std::cmp::Ordering::Equal => Vec::new(), + } +} + +/// Generate the path along the inner coordinate from (m,0) to (m,n). +/// Excludes the starting point (m,0). +fn generate_inner_path(m: i32, n: i32) -> Vec { + match n.cmp(&0) { + std::cmp::Ordering::Greater => { + // Apply rule 4: (m,n) -> (m,n+1) + (1..=n).map(|i| Value::new(m, i)).collect() + } + std::cmp::Ordering::Less => { + // Apply rule 5: (m,n) -> (m,n-1) + // Generate -1, -2, ..., n + // Range n..0 gives [n, n+1, ..., -1], reversed gives [-1, -2, ..., n] + (n..0).rev().map(|i| Value::new(m, i)).collect() + } + std::cmp::Ordering::Equal => Vec::new(), + } +} + +/// Returns the length of the minimum derivation path for a given value. +/// +/// This is equivalent to |outer| + |inner| + 1 (for the origin). +/// +/// # Examples +/// +/// ``` +/// use meta_affine::{Value, path_length}; +/// assert_eq!(path_length(Value::new(2, 3)), 6); +/// assert_eq!(path_length(Value::new(-2, -3)), 6); +/// ``` +pub fn path_length(value: Value) -> usize { + (value.outer.abs() + value.inner.abs() + 1) as usize +} diff --git a/morphology/test_sequence b/morphology/test_sequence new file mode 100755 index 0000000..3ae669b Binary files /dev/null and b/morphology/test_sequence differ diff --git a/morphology/test_set b/morphology/test_set new file mode 100755 index 0000000..b8b1e34 Binary files /dev/null and b/morphology/test_set differ diff --git a/morphology/test_value b/morphology/test_value new file mode 100755 index 0000000..8bccac3 Binary files /dev/null and b/morphology/test_value differ diff --git a/morphology/tests/sequence.rs b/morphology/tests/sequence.rs new file mode 100644 index 0000000..07e4d34 --- /dev/null +++ b/morphology/tests/sequence.rs @@ -0,0 +1,554 @@ +//! Unit tests for the sequence module + +use std::collections::HashSet; + +use meta_affine::{Sequence, ValidSet, Value}; +use meta_affine::sequence::*; + +// ======================================================================== +// SEQUENCE CREATION TESTS +// ======================================================================== + +#[test] +fn test_sequence_creation() { + let seq = Sequence::new(vec![Value::new(0, 0)]); + assert_eq!(seq.length(), 1); +} + +#[test] +fn test_sequence_values() { + let values = vec![Value::new(0, 0), Value::new(1, 0), Value::new(0, 0)]; + let seq = Sequence::new(values.clone()); + + assert_eq!(seq.values(), &values[..]); +} + +#[test] +fn test_sequence_length() { + let seq1 = Sequence::new(vec![Value::origin()]); + assert_eq!(seq1.length(), 1); + + let seq2 = Sequence::new(vec![Value::new(1, 0), Value::new(0, 0)]); + assert_eq!(seq2.length(), 2); +} + +// ======================================================================== +// CONSTRAINT 1: COVERAGE TESTS +// ======================================================================== + +#[test] +fn test_coverage_all_present() { + let mut set_values = HashSet::new(); + set_values.insert(Value::new(0, 0)); + set_values.insert(Value::new(1, 0)); + let set = ValidSet::from_values(set_values).unwrap(); + + let seq = Sequence::new(vec![Value::new(0, 0), Value::new(1, 0), Value::new(0, 0)]); + assert!(check_coverage(&seq, &set)); +} + +#[test] +fn test_coverage_missing_value() { + let mut set_values = HashSet::new(); + set_values.insert(Value::new(0, 0)); + set_values.insert(Value::new(1, 0)); + let set = ValidSet::from_values(set_values).unwrap(); + + // Sequence missing (1,0) + let seq = Sequence::new(vec![Value::new(0, 0)]); + assert!(!check_coverage(&seq, &set)); +} + +#[test] +fn test_coverage_with_repetitions() { + let set = ValidSet::origin_set(); + + // (0,0) appears three times - still valid + let seq = Sequence::new(vec![Value::origin()]); + assert!(check_coverage(&seq, &set)); +} + +// ======================================================================== +// CONSTRAINT 2: NO CONSECUTIVE DUPLICATES TESTS +// ======================================================================== + +#[test] +fn test_no_consecutive_duplicates_valid() { + let seq = Sequence::new(vec![ + Value::new(0, 0), + Value::new(1, 0), + Value::new(0, 0), + Value::new(1, 0), + ]); + assert!(check_no_consecutive_duplicates(&seq)); +} + +#[test] +fn test_no_consecutive_duplicates_invalid() { + let seq = Sequence::new(vec![ + Value::new(0, 0), + Value::new(0, 0), // Duplicate! + Value::new(1, 0), + ]); + assert!(!check_no_consecutive_duplicates(&seq)); +} + +#[test] +fn test_no_consecutive_duplicates_single_element() { + let seq = Sequence::new(vec![Value::origin()]); + assert!(check_no_consecutive_duplicates(&seq)); +} + +#[test] +fn test_no_consecutive_duplicates_empty() { + let seq = Sequence::new(vec![]); + assert!(check_no_consecutive_duplicates(&seq)); +} + +// ======================================================================== +// CONSTRAINT 3: TERMINAL TESTS +// ======================================================================== + +#[test] +fn test_terminal_valid() { + let seq = Sequence::new(vec![Value::new(1, 0), Value::origin()]); + assert!(check_terminal(&seq)); +} + +#[test] +fn test_terminal_invalid() { + let seq = Sequence::new(vec![Value::origin(), Value::new(1, 0)]); + assert!(!check_terminal(&seq)); +} + +#[test] +fn test_terminal_single_origin() { + let seq = Sequence::new(vec![Value::origin()]); + assert!(check_terminal(&seq)); +} + +#[test] +fn test_terminal_empty() { + let seq = Sequence::new(vec![]); + assert!(!check_terminal(&seq)); +} + +// ======================================================================== +// CONSTRAINT 4: OUTER VALUE CONSTRAINT TESTS +// ======================================================================== + +#[test] +fn test_outer_value_constraint_valid_simple() { + // Last occurrence of outer=1 is (1,0) ✓ + let seq = Sequence::new(vec![ + Value::new(1, 1), + Value::new(1, 0), + Value::new(0, 0), + ]); + assert!(check_outer_value_constraint(&seq)); +} + +#[test] +fn test_outer_value_constraint_invalid_simple() { + // Last occurrence of outer=1 is (1,1) ✗ + let seq = Sequence::new(vec![ + Value::new(1, 0), + Value::new(1, 1), + Value::new(0, 0), + ]); + assert!(!check_outer_value_constraint(&seq)); +} + +#[test] +fn test_outer_value_constraint_multiple_outers() { + // Last of outer=1 is (1,0), last of outer=0 is (0,0) ✓ + let seq = Sequence::new(vec![ + Value::new(1, 1), + Value::new(0, 1), + Value::new(1, 0), + Value::new(0, 0), + ]); + assert!(check_outer_value_constraint(&seq)); +} + +#[test] +fn test_outer_value_constraint_complex() { + // Valid: outer=2 last at (2,0), outer=0 last at (0,0) + let seq = Sequence::new(vec![ + Value::new(2, 1), + Value::new(2, 2), + Value::new(0, 1), + Value::new(2, 0), + Value::new(0, 0), + ]); + assert!(check_outer_value_constraint(&seq)); +} + +#[test] +fn test_outer_value_constraint_only_origin() { + let seq = Sequence::new(vec![Value::origin()]); + assert!(check_outer_value_constraint(&seq)); +} + +#[test] +fn test_outer_value_constraint_negative_outer() { + // Last of outer=-1 is (-1,0) ✓ + let seq = Sequence::new(vec![ + Value::new(-1, -1), + Value::new(-1, 0), + Value::new(0, 0), + ]); + assert!(check_outer_value_constraint(&seq)); +} + +// ======================================================================== +// COMBINED VALIDATION TESTS +// ======================================================================== + +#[test] +fn test_is_valid_all_constraints_satisfied() { + let mut set_values = HashSet::new(); + set_values.insert(Value::new(0, 0)); + set_values.insert(Value::new(1, 0)); + let set = ValidSet::from_values(set_values).unwrap(); + + let seq = Sequence::new(vec![ + Value::new(1, 0), + Value::new(0, 0), + ]); + + assert!(seq.is_valid(&set)); +} + +#[test] +fn test_is_valid_fails_coverage() { + let mut set_values = HashSet::new(); + set_values.insert(Value::new(0, 0)); + set_values.insert(Value::new(1, 0)); + let set = ValidSet::from_values(set_values).unwrap(); + + // Missing (1,0) + let seq = Sequence::new(vec![Value::new(0, 0)]); + assert!(!seq.is_valid(&set)); +} + +#[test] +fn test_is_valid_fails_consecutive_duplicates() { + let set = ValidSet::origin_set(); + + let seq = Sequence::new(vec![ + Value::new(0, 0), + Value::new(0, 0), // Duplicate! + ]); + assert!(!seq.is_valid(&set)); +} + +#[test] +fn test_is_valid_fails_terminal() { + let set = ValidSet::origin_set(); + + let seq = Sequence::new(vec![Value::new(1, 0)]); + assert!(!seq.is_valid(&set)); +} + +#[test] +fn test_is_valid_fails_outer_constraint() { + let mut set_values = HashSet::new(); + set_values.insert(Value::new(0, 0)); + set_values.insert(Value::new(1, 0)); + set_values.insert(Value::new(1, 1)); + let set = ValidSet::from_values(set_values).unwrap(); + + // Last occurrence of outer=1 is (1,1), not (1,0) + let seq = Sequence::new(vec![ + Value::new(1, 0), + Value::new(1, 1), + Value::new(0, 0), + ]); + assert!(!seq.is_valid(&set)); +} + +// ======================================================================== +// SEQUENCE GENERATION TESTS +// ======================================================================== + +#[test] +fn test_generate_sequences_length_1() { + let set = ValidSet::origin_set(); + let sequences = generate_sequences(&set, 1); + + // Only one valid sequence: [(0,0)] + assert_eq!(sequences.len(), 1); + assert_eq!(sequences[0].values(), &[Value::origin()]); +} + +#[test] +fn test_generate_sequences_length_2_simple_set() { + let mut set_values = HashSet::new(); + set_values.insert(Value::new(0, 0)); + set_values.insert(Value::new(1, 0)); + let set = ValidSet::from_values(set_values).unwrap(); + + let sequences = generate_sequences(&set, 2); + + // Valid sequences: [(1,0), (0,0)] + // Invalid: [(0,0), (1,0)] - doesn't end with (0,0) + // Invalid: [(0,0), (0,0)] - consecutive duplicates + // Invalid: [(1,0), (1,0)] - consecutive duplicates + + assert!(sequences.len() >= 1); + + // Check all generated sequences are valid + for seq in &sequences { + assert!(seq.is_valid(&set), "Invalid sequence: {:?}", seq); + } + + // Check the expected sequence is present + let expected = Sequence::new(vec![Value::new(1, 0), Value::new(0, 0)]); + assert!(sequences.contains(&expected)); +} + +#[test] +fn test_generate_sequences_no_valid_for_empty_set() { + let set = ValidSet::new(); + let sequences = generate_sequences(&set, 1); + + assert_eq!(sequences.len(), 0); +} + +#[test] +fn test_generate_sequences_length_zero() { + let set = ValidSet::origin_set(); + let sequences = generate_sequences(&set, 0); + + assert_eq!(sequences.len(), 0); +} + +#[test] +fn test_generate_sequences_all_valid() { + let mut set_values = HashSet::new(); + set_values.insert(Value::new(0, 0)); + set_values.insert(Value::new(1, 0)); + let set = ValidSet::from_values(set_values).unwrap(); + + let sequences = generate_sequences(&set, 3); + + // All generated sequences must be valid + for seq in &sequences { + assert!(seq.is_valid(&set), "Generated invalid sequence: {:?}", seq); + assert_eq!(seq.length(), 3); + } +} + +#[test] +fn test_generate_sequences_complex_set() { + let mut set_values = HashSet::new(); + set_values.insert(Value::new(0, 0)); + set_values.insert(Value::new(1, 0)); + set_values.insert(Value::new(1, 1)); + let set = ValidSet::from_values(set_values).unwrap(); + + let sequences = generate_sequences(&set, 4); + + // All sequences must be valid + for seq in &sequences { + assert!(seq.is_valid(&set)); + assert_eq!(seq.length(), 4); + } + + // Should have at least some sequences + assert!(sequences.len() > 0); +} + +#[test] +fn test_generate_all_sequences_length_1() { + let sequences = generate_all_sequences(1); + + // Only [(0,0)] is valid for length 1 + assert_eq!(sequences.len(), 1); + assert_eq!(sequences[0].values(), &[Value::origin()]); +} + +#[test] +fn test_generate_all_sequences_length_2() { + let sequences = generate_all_sequences(2); + + // Should have multiple valid sequences from different sets + assert!(sequences.len() > 0); + + // All must be valid and have length 2 + for seq in &sequences { + assert_eq!(seq.length(), 2); + assert!(check_no_consecutive_duplicates(seq)); + assert!(check_terminal(seq)); + assert!(check_outer_value_constraint(seq)); + } +} + +// ======================================================================== +// PROPERTY-BASED TESTS +// ======================================================================== + +#[test] +fn test_generated_sequences_satisfy_all_constraints() { + let set = ValidSet::origin_set() + .add_value_with_dependencies(Value::new(1, 1)); + + let sequences = generate_sequences(&set, 3); + + for seq in &sequences { + // Constraint 1: Coverage + assert!(check_coverage(seq, &set), "Coverage failed for {:?}", seq); + + // Constraint 2: No consecutive duplicates + assert!( + check_no_consecutive_duplicates(seq), + "Consecutive duplicates in {:?}", + seq + ); + + // Constraint 3: Terminal + assert!(check_terminal(seq), "Terminal failed for {:?}", seq); + + // Constraint 4: Outer value constraint + assert!( + check_outer_value_constraint(seq), + "Outer constraint failed for {:?}", + seq + ); + } +} + +#[test] +fn test_no_duplicate_sequences_generated() { + let set = ValidSet::origin_set() + .add_value_with_dependencies(Value::new(1, 0)); + + let sequences = generate_sequences(&set, 3); + + // Check for duplicates + for i in 0..sequences.len() { + for j in (i + 1)..sequences.len() { + assert_ne!( + &sequences[i], &sequences[j], + "Found duplicate sequences at {} and {}", + i, j + ); + } + } +} + +#[test] +fn test_sequence_length_matches_requested() { + let set = ValidSet::origin_set() + .add_value_with_dependencies(Value::new(1, 0)); + + for length in 1..=4 { + let sequences = generate_sequences(&set, length); + for seq in &sequences { + assert_eq!(seq.length(), length); + } + } +} + +// ======================================================================== +// EDGE CASES +// ======================================================================== + +#[test] +fn test_single_value_set_single_length() { + // Set with only origin + let set = ValidSet::origin_set(); + let sequences = generate_sequences(&set, 1); + + assert_eq!(sequences.len(), 1); + assert_eq!(sequences[0].values(), &[Value::origin()]); +} + +#[test] +fn test_set_with_origin_coverage_constraint() { + // Set has 2 values but we need length 1 - cannot satisfy coverage + let mut set_values = HashSet::new(); + set_values.insert(Value::new(0, 0)); // Origin is required + set_values.insert(Value::new(1, 0)); + let set = ValidSet::from_values(set_values).unwrap(); + + // Cannot generate length-1 sequences because we can't cover both values + let sequences = generate_sequences(&set, 1); + assert_eq!(sequences.len(), 0); + + // But length-2 sequences should work + let sequences2 = generate_sequences(&set, 2); + assert!(sequences2.len() > 0); +} + +#[test] +fn test_negative_coordinates_in_sequence() { + let set = ValidSet::new() + .add_value_with_dependencies(Value::new(-1, -1)); + + let sequences = generate_sequences(&set, 3); + + // All generated sequences should be valid + for seq in &sequences { + assert!(seq.is_valid(&set)); + } +} + +#[test] +fn test_large_set_small_sequence() { + // Set with 6 values, sequence of length 6 (minimum to cover all) + let set = ValidSet::new() + .add_value_with_dependencies(Value::new(2, 3)); + + let sequences = generate_sequences(&set, 6); + + // Should have at least some sequences + assert!(sequences.len() > 0); + + for seq in &sequences { + assert!(seq.is_valid(&set)); + assert_eq!(seq.length(), 6); + } +} + +#[test] +fn test_sequence_longer_than_set_size() { + // Set size 2, sequence length 4 + let mut set_values = HashSet::new(); + set_values.insert(Value::new(0, 0)); + set_values.insert(Value::new(1, 0)); + let set = ValidSet::from_values(set_values).unwrap(); + + let sequences = generate_sequences(&set, 4); + + // Should have sequences (values can repeat, just not consecutively) + assert!(sequences.len() > 0); + + for seq in &sequences { + assert!(seq.is_valid(&set)); + } +} + +#[test] +fn test_count_sequences() { + let set = ValidSet::origin_set(); + let count = count_sequences(&set, 1); + + assert_eq!(count, 1); +} + +#[test] +fn test_outer_constraint_with_multiple_values() { + // Test that outer constraint is properly enforced with multiple outer values + let set = ValidSet::new() + .add_value_with_dependencies(Value::new(1, 1)) + .add_value_with_dependencies(Value::new(-1, -1)); + + let sequences = generate_sequences(&set, set.size()); + + for seq in &sequences { + assert!(check_outer_value_constraint(seq), + "Outer constraint violated in {:?}", seq); + } +} diff --git a/morphology/tests/set.rs b/morphology/tests/set.rs new file mode 100644 index 0000000..54b441a --- /dev/null +++ b/morphology/tests/set.rs @@ -0,0 +1,420 @@ +//! Unit tests for the set module + +use std::collections::HashSet; + +use meta_affine::{ValidSet, Value}; +use meta_affine::set::*; + +// ======================================================================== +// VALID SET CREATION TESTS +// ======================================================================== + +#[test] +fn test_new_empty_set() { + let set = ValidSet::new(); + assert_eq!(set.size(), 0); + assert!(set.is_valid()); // Empty set is vacuously valid +} + +#[test] +fn test_origin_set() { + let set = ValidSet::origin_set(); + assert_eq!(set.size(), 1); + assert!(set.contains(&Value::origin())); + assert!(set.is_valid()); +} + +#[test] +fn test_from_values_valid() { + let mut values = HashSet::new(); + values.insert(Value::new(0, 0)); + values.insert(Value::new(1, 0)); + values.insert(Value::new(1, 1)); + + let set = ValidSet::from_values(values).unwrap(); + assert_eq!(set.size(), 3); + assert!(set.is_valid()); +} + +#[test] +fn test_from_values_invalid() { + // Missing (1,0) - not downward closed + let mut values = HashSet::new(); + values.insert(Value::new(0, 0)); + values.insert(Value::new(1, 1)); + + let result = ValidSet::from_values(values); + assert!(result.is_err()); +} + +#[test] +fn test_from_values_invalid_missing_origin() { + // Missing origin + let mut values = HashSet::new(); + values.insert(Value::new(1, 0)); + + let result = ValidSet::from_values(values); + assert!(result.is_err()); +} + +// ======================================================================== +// VALIDITY CHECKING TESTS +// ======================================================================== + +#[test] +fn test_is_valid_simple_cases() { + // {(0,0)} + let set1 = ValidSet::origin_set(); + assert!(set1.is_valid()); + + // {(0,0), (1,0)} + let mut values = HashSet::new(); + values.insert(Value::new(0, 0)); + values.insert(Value::new(1, 0)); + let set2 = ValidSet::from_values(values).unwrap(); + assert!(set2.is_valid()); + + // {(0,0), (0,1)} + let mut values = HashSet::new(); + values.insert(Value::new(0, 0)); + values.insert(Value::new(0, 1)); + let set3 = ValidSet::from_values(values).unwrap(); + assert!(set3.is_valid()); +} + +#[test] +fn test_is_valid_complex_path() { + // {(0,0), (1,0), (2,0), (2,1), (2,2), (2,3)} + let mut values = HashSet::new(); + values.insert(Value::new(0, 0)); + values.insert(Value::new(1, 0)); + values.insert(Value::new(2, 0)); + values.insert(Value::new(2, 1)); + values.insert(Value::new(2, 2)); + values.insert(Value::new(2, 3)); + + let set = ValidSet::from_values(values).unwrap(); + assert!(set.is_valid()); +} + +#[test] +fn test_is_valid_negative_values() { + // {(0,0), (-1,0), (-1,-1)} + let mut values = HashSet::new(); + values.insert(Value::new(0, 0)); + values.insert(Value::new(-1, 0)); + values.insert(Value::new(-1, -1)); + + let set = ValidSet::from_values(values).unwrap(); + assert!(set.is_valid()); +} + +#[test] +fn test_invalid_missing_intermediate() { + // Missing (1,0) - should be invalid + let mut values = HashSet::new(); + values.insert(Value::new(0, 0)); + values.insert(Value::new(2, 0)); + + let result = ValidSet::from_values(values); + assert!(result.is_err()); +} + +// ======================================================================== +// SET OPERATIONS TESTS +// ======================================================================== + +#[test] +fn test_add_value() { + let set = ValidSet::origin_set(); + + // Add (1,0) to {(0,0)} + let set2 = set.add_value(Value::new(1, 0)).unwrap(); + assert_eq!(set2.size(), 2); + assert!(set2.contains(&Value::new(1, 0))); + + // Original set unchanged (immutability) + assert_eq!(set.size(), 1); +} + +#[test] +fn test_add_value_invalid() { + let set = ValidSet::origin_set(); + + // Try to add (2,0) without (1,0) - should fail + let result = set.add_value(Value::new(2, 0)); + assert!(result.is_err()); +} + +#[test] +fn test_add_value_with_dependencies() { + let set = ValidSet::new(); + + // Add (2,3) with all dependencies + let set2 = set.add_value_with_dependencies(Value::new(2, 3)); + + // Should contain: (0,0), (1,0), (2,0), (2,1), (2,2), (2,3) + assert_eq!(set2.size(), 6); + assert!(set2.contains(&Value::new(0, 0))); + assert!(set2.contains(&Value::new(1, 0))); + assert!(set2.contains(&Value::new(2, 0))); + assert!(set2.contains(&Value::new(2, 1))); + assert!(set2.contains(&Value::new(2, 2))); + assert!(set2.contains(&Value::new(2, 3))); + assert!(set2.is_valid()); +} + +#[test] +fn test_contains() { + let set = ValidSet::origin_set(); + + assert!(set.contains(&Value::origin())); + assert!(!set.contains(&Value::new(1, 0))); +} + +#[test] +fn test_size() { + let set = ValidSet::origin_set(); + assert_eq!(set.size(), 1); + + let set2 = set.add_value(Value::new(1, 0)).unwrap(); + assert_eq!(set2.size(), 2); +} + +#[test] +fn test_values_iterator() { + let mut values = HashSet::new(); + values.insert(Value::new(0, 0)); + values.insert(Value::new(1, 0)); + values.insert(Value::new(0, 1)); + + let set = ValidSet::from_values(values.clone()).unwrap(); + + let collected: HashSet = set.values().copied().collect(); + assert_eq!(collected, values); +} + +#[test] +fn test_values_sorted() { + let mut values = HashSet::new(); + values.insert(Value::new(1, 0)); + values.insert(Value::new(0, 1)); + values.insert(Value::new(0, 0)); + values.insert(Value::new(-1, 0)); + + let set = ValidSet::from_values(values).unwrap(); + let sorted = set.values_sorted(); + + // Should be sorted by (outer, inner) + assert_eq!(sorted[0], Value::new(-1, 0)); + assert_eq!(sorted[1], Value::new(0, 0)); + assert_eq!(sorted[2], Value::new(0, 1)); + assert_eq!(sorted[3], Value::new(1, 0)); +} + +// ======================================================================== +// SET GENERATION TESTS +// ======================================================================== + +#[test] +fn test_generate_valid_sets_size_1() { + let sets = generate_valid_sets(1); + + // Should only have {(0,0)} + assert_eq!(sets.len(), 1); + assert_eq!(sets[0].size(), 1); + assert!(sets[0].contains(&Value::origin())); +} + +#[test] +fn test_generate_valid_sets_size_2() { + let sets = generate_valid_sets(2); + + // Should include: + // {(0,0)} + // {(0,0), (1,0)} + // {(0,0), (-1,0)} + // {(0,0), (0,1)} + // {(0,0), (0,-1)} + + assert!(sets.len() >= 5); + + // Check that all generated sets are valid + for set in &sets { + assert!(set.is_valid(), "Generated set is not valid: {:?}", set); + } + + // Check specific sets exist + let has_origin_plus_1_0 = sets.iter().any(|s| { + s.size() == 2 && s.contains(&Value::origin()) && s.contains(&Value::new(1, 0)) + }); + assert!(has_origin_plus_1_0); + + let has_origin_plus_0_1 = sets.iter().any(|s| { + s.size() == 2 && s.contains(&Value::origin()) && s.contains(&Value::new(0, 1)) + }); + assert!(has_origin_plus_0_1); +} + +#[test] +fn test_generate_valid_sets_size_3() { + let sets = generate_valid_sets(3); + + // Should include all from size 2, plus new size-3 sets + assert!(sets.len() > 5); + + // All sets should be valid + for set in &sets { + assert!(set.is_valid(), "Generated set is not valid"); + } + + // Check a specific size-3 set exists: {(0,0), (1,0), (1,1)} + let has_target_set = sets.iter().any(|s| { + s.size() == 3 + && s.contains(&Value::new(0, 0)) + && s.contains(&Value::new(1, 0)) + && s.contains(&Value::new(1, 1)) + }); + assert!(has_target_set); +} + +#[test] +fn test_generate_valid_sets_all_valid() { + // Generate sets up to size 4 and verify all are valid + let sets = generate_valid_sets(4); + + for set in &sets { + assert!(set.is_valid(), "Generated invalid set: {:?}", set); + } + + // Should have generated multiple sets + assert!(sets.len() > 10); +} + +#[test] +fn test_generate_valid_sets_no_duplicates() { + let sets = generate_valid_sets(4); + + // Check for duplicates manually + for i in 0..sets.len() { + for j in (i + 1)..sets.len() { + assert_ne!(&sets[i], &sets[j], "Found duplicate sets at indices {} and {}", i, j); + } + } +} + +#[test] +fn test_generate_valid_sets_of_size() { + let sets = generate_valid_sets_of_size(3); + + // All sets should have size exactly 3 + for set in &sets { + assert_eq!(set.size(), 3); + assert!(set.is_valid()); + } + + // Should have multiple size-3 sets + assert!(sets.len() > 3); +} + +// ======================================================================== +// PROPERTY-BASED TESTS +// ======================================================================== + +#[test] +fn test_all_generated_sets_contain_origin() { + let sets = generate_valid_sets(5); + + for set in &sets { + if set.size() > 0 { + assert!( + set.contains(&Value::origin()), + "Non-empty valid set must contain origin" + ); + } + } +} + +#[test] +fn test_downward_closure_property() { + // For any value in a generated set, all values in its path must be in the set + let sets = generate_valid_sets(5); + + for set in &sets { + for &value in set.values() { + let path = meta_affine::value::get_minimum_derivation_path(value); + for dep in path { + assert!( + set.contains(&dep), + "Set {:?} contains {} but missing dependency {}", + set.values_sorted(), + value, + dep + ); + } + } + } +} + +#[test] +fn test_immutability_of_operations() { + let set1 = ValidSet::origin_set(); + let original_size = set1.size(); + + // Add a value + let _set2 = set1.add_value(Value::new(1, 0)).unwrap(); + + // Original set should be unchanged + assert_eq!(set1.size(), original_size); + assert!(!set1.contains(&Value::new(1, 0))); +} + +// ======================================================================== +// EDGE CASES +// ======================================================================== + +#[test] +fn test_empty_set_is_valid() { + let set = ValidSet::new(); + assert!(set.is_valid()); +} + +#[test] +fn test_generate_sets_size_zero() { + let sets = generate_valid_sets(0); + assert_eq!(sets.len(), 1); + assert_eq!(sets[0].size(), 0); +} + +#[test] +fn test_large_value_with_dependencies() { + // Test that adding a "far" value includes all intermediate values + let set = ValidSet::new(); + let set2 = set.add_value_with_dependencies(Value::new(3, 4)); + + // Path length for (3,4) is 3 + 4 + 1 = 8 + assert_eq!(set2.size(), 8); + assert!(set2.is_valid()); +} + +#[test] +fn test_negative_coordinates() { + let set = ValidSet::new(); + let set2 = set.add_value_with_dependencies(Value::new(-2, -3)); + + // Should contain: (0,0), (-1,0), (-2,0), (-2,-1), (-2,-2), (-2,-3) + assert_eq!(set2.size(), 6); + assert!(set2.contains(&Value::new(-1, 0))); + assert!(set2.contains(&Value::new(-2, -1))); + assert!(set2.is_valid()); +} + +#[test] +fn test_mixed_signs() { + let set = ValidSet::new(); + let set2 = set.add_value_with_dependencies(Value::new(2, -3)); + + // Path: (0,0), (1,0), (2,0), (2,-1), (2,-2), (2,-3) + assert_eq!(set2.size(), 6); + assert!(set2.is_valid()); +} diff --git a/morphology/tests/value.rs b/morphology/tests/value.rs new file mode 100644 index 0000000..fcd4b76 --- /dev/null +++ b/morphology/tests/value.rs @@ -0,0 +1,304 @@ +//! Unit tests for the value module + +use std::collections::HashSet; + +// Import from the library crate +use meta_affine::value::*; +use meta_affine::Value; + +// ======================================================================== +// VALUE TESTS +// ======================================================================== + +#[test] +fn test_value_creation() { + let v1 = Value::new(0, 0); + assert_eq!(v1.outer, 0); + assert_eq!(v1.inner, 0); + + let v2 = Value::new(5, -3); + assert_eq!(v2.outer, 5); + assert_eq!(v2.inner, -3); + + let v3 = Value::new(-10, 20); + assert_eq!(v3.outer, -10); + assert_eq!(v3.inner, 20); +} + +#[test] +fn test_value_equality() { + let v1 = Value::new(2, 3); + let v2 = Value::new(2, 3); + let v3 = Value::new(2, 4); + + assert_eq!(v1, v2); + assert_ne!(v1, v3); + + // Test in sets (uniqueness) + let mut set = HashSet::new(); + set.insert(v1); + set.insert(v2); + set.insert(v3); + assert_eq!(set.len(), 2); +} + +#[test] +fn test_value_to_string() { + assert_eq!(format!("{}", Value::new(0, 0)), "(0,0)"); + assert_eq!(format!("{}", Value::new(2, 3)), "(2,3)"); + assert_eq!(format!("{}", Value::new(-1, -2)), "(-1,-2)"); + assert_eq!(format!("{}", Value::new(10, -5)), "(10,-5)"); +} + +#[test] +fn test_origin_detection() { + assert!(Value::new(0, 0).is_origin()); + assert!(!Value::new(1, 0).is_origin()); + assert!(!Value::new(0, 1).is_origin()); + assert!(!Value::new(-1, -1).is_origin()); + + let origin = Value::origin(); + assert!(origin.is_origin()); +} + +#[test] +fn test_value_copy_semantics() { + let v1 = Value::new(2, 3); + let v2 = v1; // Copy, not move + assert_eq!(v1, v2); + // v1 is still usable + assert_eq!(v1.outer, 2); +} + +// ======================================================================== +// MINIMUM DERIVATION PATH TESTS +// ======================================================================== + +#[test] +fn test_path_origin() { + let path = get_minimum_derivation_path(Value::new(0, 0)); + assert_eq!(path.len(), 1); + assert_eq!(path[0], Value::new(0, 0)); +} + +#[test] +fn test_path_positive_outer() { + // Test (3, 0) + let path = get_minimum_derivation_path(Value::new(3, 0)); + let expected = vec![ + Value::new(0, 0), + Value::new(1, 0), + Value::new(2, 0), + Value::new(3, 0), + ]; + + assert_eq!(path, expected); + assert_eq!(path.len(), 4); + assert_eq!(path.first(), Some(&Value::new(0, 0))); + assert_eq!(path.last(), Some(&Value::new(3, 0))); +} + +#[test] +fn test_path_negative_outer() { + // Test (-3, 0) + let path = get_minimum_derivation_path(Value::new(-3, 0)); + let expected = vec![ + Value::new(0, 0), + Value::new(-1, 0), + Value::new(-2, 0), + Value::new(-3, 0), + ]; + + assert_eq!(path, expected); + assert_eq!(path.len(), 4); + assert_eq!(path.first(), Some(&Value::new(0, 0))); + assert_eq!(path.last(), Some(&Value::new(-3, 0))); +} + +#[test] +fn test_path_positive_inner() { + // Test (0, 3) + let path = get_minimum_derivation_path(Value::new(0, 3)); + let expected = vec![ + Value::new(0, 0), + Value::new(0, 1), + Value::new(0, 2), + Value::new(0, 3), + ]; + + assert_eq!(path, expected); + assert_eq!(path.len(), 4); +} + +#[test] +fn test_path_negative_inner() { + // Test (0, -3) + let path = get_minimum_derivation_path(Value::new(0, -3)); + let expected = vec![ + Value::new(0, 0), + Value::new(0, -1), + Value::new(0, -2), + Value::new(0, -3), + ]; + + assert_eq!(path, expected); + assert_eq!(path.len(), 4); +} + +#[test] +fn test_path_combined_positive() { + // Test (2, 3) + let path = get_minimum_derivation_path(Value::new(2, 3)); + let expected = vec![ + Value::new(0, 0), + Value::new(1, 0), + Value::new(2, 0), + Value::new(2, 1), + Value::new(2, 2), + Value::new(2, 3), + ]; + + assert_eq!(path, expected); + assert_eq!(path.len(), 6); + assert_eq!(path.first(), Some(&Value::new(0, 0))); + assert_eq!(path.last(), Some(&Value::new(2, 3))); +} + +#[test] +fn test_path_combined_negative() { + // Test (-2, -3) + let path = get_minimum_derivation_path(Value::new(-2, -3)); + let expected = vec![ + Value::new(0, 0), + Value::new(-1, 0), + Value::new(-2, 0), + Value::new(-2, -1), + Value::new(-2, -2), + Value::new(-2, -3), + ]; + + assert_eq!(path, expected); + assert_eq!(path.len(), 6); +} + +#[test] +fn test_path_mixed_signs() { + // Test (2, -3) + let path1 = get_minimum_derivation_path(Value::new(2, -3)); + let expected1 = vec![ + Value::new(0, 0), + Value::new(1, 0), + Value::new(2, 0), + Value::new(2, -1), + Value::new(2, -2), + Value::new(2, -3), + ]; + assert_eq!(path1, expected1); + + // Test (-2, 3) + let path2 = get_minimum_derivation_path(Value::new(-2, 3)); + let expected2 = vec![ + Value::new(0, 0), + Value::new(-1, 0), + Value::new(-2, 0), + Value::new(-2, 1), + Value::new(-2, 2), + Value::new(-2, 3), + ]; + assert_eq!(path2, expected2); +} + +#[test] +fn test_path_length() { + assert_eq!(path_length(Value::new(0, 0)), 1); + assert_eq!(path_length(Value::new(3, 0)), 4); + assert_eq!(path_length(Value::new(0, 3)), 4); + assert_eq!(path_length(Value::new(2, 3)), 6); + assert_eq!(path_length(Value::new(-2, -3)), 6); + assert_eq!(path_length(Value::new(5, -7)), 13); +} + +#[test] +fn test_path_validity() { + // Test that paths satisfy key properties + let test_cases = vec![ + Value::new(0, 0), + Value::new(5, 0), + Value::new(-5, 0), + Value::new(0, 5), + Value::new(0, -5), + Value::new(3, 4), + Value::new(-3, -4), + Value::new(3, -4), + Value::new(-3, 4), + ]; + + for value in test_cases { + let path = get_minimum_derivation_path(value); + + // Property 1: Path starts at origin + assert_eq!( + path.first(), + Some(&Value::origin()), + "Path must start at origin for {}", + value + ); + + // Property 2: Path ends at target value + assert_eq!( + path.last(), + Some(&value), + "Path must end at target value for {}", + value + ); + + // Property 3: Path length matches formula + assert_eq!( + path.len(), + path_length(value), + "Path length mismatch for {}", + value + ); + + // Property 4: Each step is valid (follows one of the 5 rules) + assert_valid_steps(&path); + } +} + +fn assert_valid_steps(path: &[Value]) { + for window in path.windows(2) { + let v1 = window[0]; + let v2 = window[1]; + + let o1 = v1.outer; + let i1 = v1.inner; + let o2 = v2.outer; + let i2 = v2.inner; + + // Check that each transition follows exactly one rule + let valid_transition = (o2 == o1 + 1 && i2 == i1) // Rule 2 + || (o2 == o1 - 1 && i2 == i1) // Rule 3 + || (o2 == o1 && i2 == i1 + 1) // Rule 4 + || (o2 == o1 && i2 == i1 - 1); // Rule 5 + + assert!( + valid_transition, + "Invalid transition from {} to {}", + v1, v2 + ); + } +} + +#[test] +fn test_path_immutability() { + let value = Value::new(3, 4); + let path1 = get_minimum_derivation_path(value); + let path2 = get_minimum_derivation_path(value); + + // Both calls should produce identical results + assert_eq!(path1, path2); + + // Original value should be unchanged + assert_eq!(value.outer, 3); + assert_eq!(value.inner, 4); +} -- cgit v1.2.3