From e4c5409397e6e833984d221d63a62ea7bcb2c4a9 Mon Sep 17 00:00:00 2001 From: jacksonfu14 Date: Thu, 6 Nov 2025 07:50:44 +0100 Subject: refactor: use cargo --- morphology/Cargo.toml | 19 ++ morphology/demo | Bin 693544 -> 0 bytes morphology/demo_full | Bin 722144 -> 0 bytes morphology/libmeta_affine.rlib | Bin 1009182 -> 0 bytes morphology/meta-affine | Bin 560568 -> 0 bytes morphology/meta-affine-test | Bin 1209256 -> 0 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/src/lib.rs | 22 ++ morphology/src/sequence.rs | 411 +++++++++++++++++++++++++++++++++++++ morphology/src/set.rs | 349 +++++++++++++++++++++++++++++++ morphology/src/value.rs | 170 +++++++++++++++ morphology/test_sequence | Bin 1360728 -> 0 bytes morphology/test_set | Bin 1334432 -> 0 bytes morphology/test_value | Bin 1218368 -> 0 bytes 17 files changed, 971 insertions(+), 952 deletions(-) create mode 100644 morphology/Cargo.toml delete mode 100755 morphology/demo delete mode 100755 morphology/demo_full delete mode 100644 morphology/libmeta_affine.rlib delete mode 100755 morphology/meta-affine delete mode 100755 morphology/meta-affine-test delete mode 100644 morphology/meta_affine/lib.rs delete mode 100644 morphology/meta_affine/sequence.rs delete mode 100644 morphology/meta_affine/set.rs delete mode 100644 morphology/meta_affine/value.rs create mode 100644 morphology/src/lib.rs create mode 100644 morphology/src/sequence.rs create mode 100644 morphology/src/set.rs create mode 100644 morphology/src/value.rs delete mode 100755 morphology/test_sequence delete mode 100755 morphology/test_set delete mode 100755 morphology/test_value (limited to 'morphology') diff --git a/morphology/Cargo.toml b/morphology/Cargo.toml new file mode 100644 index 0000000..fcbf7fc --- /dev/null +++ b/morphology/Cargo.toml @@ -0,0 +1,19 @@ +[package] +name = "meta_affine" +version = "0.1.0" +edition = "2021" +authors = ["Your Name "] + +[lib] +name = "meta_affine" +path = "src/lib.rs" + +[dependencies] + +[[example]] +name = "demo" +path = "examples/demo.rs" + +[[example]] +name = "demo_full" +path = "examples/demo_full.rs" diff --git a/morphology/demo b/morphology/demo deleted file mode 100755 index 520fdad..0000000 Binary files a/morphology/demo and /dev/null differ diff --git a/morphology/demo_full b/morphology/demo_full deleted file mode 100755 index df0eefc..0000000 Binary files a/morphology/demo_full and /dev/null differ diff --git a/morphology/libmeta_affine.rlib b/morphology/libmeta_affine.rlib deleted file mode 100644 index 6fe900e..0000000 Binary files a/morphology/libmeta_affine.rlib and /dev/null differ diff --git a/morphology/meta-affine b/morphology/meta-affine deleted file mode 100755 index 95b5ee0..0000000 Binary files a/morphology/meta-affine and /dev/null differ diff --git a/morphology/meta-affine-test b/morphology/meta-affine-test deleted file mode 100755 index 919e6db..0000000 Binary files a/morphology/meta-affine-test and /dev/null differ diff --git a/morphology/meta_affine/lib.rs b/morphology/meta_affine/lib.rs deleted file mode 100644 index 6ebd49d..0000000 --- a/morphology/meta_affine/lib.rs +++ /dev/null @@ -1,22 +0,0 @@ -//! 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 deleted file mode 100644 index 784567d..0000000 --- a/morphology/meta_affine/sequence.rs +++ /dev/null @@ -1,411 +0,0 @@ -//! 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 deleted file mode 100644 index 5376f65..0000000 --- a/morphology/meta_affine/set.rs +++ /dev/null @@ -1,349 +0,0 @@ -//! 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 deleted file mode 100644 index 71fc2c6..0000000 --- a/morphology/meta_affine/value.rs +++ /dev/null @@ -1,170 +0,0 @@ -//! 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/src/lib.rs b/morphology/src/lib.rs new file mode 100644 index 0000000..de6a3e4 --- /dev/null +++ b/morphology/src/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 and functions for convenience +pub use value::{Value, get_minimum_derivation_path, path_length}; +pub use set::ValidSet; +pub use sequence::Sequence; diff --git a/morphology/src/sequence.rs b/morphology/src/sequence.rs new file mode 100644 index 0000000..784567d --- /dev/null +++ b/morphology/src/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/src/set.rs b/morphology/src/set.rs new file mode 100644 index 0000000..5376f65 --- /dev/null +++ b/morphology/src/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/src/value.rs b/morphology/src/value.rs new file mode 100644 index 0000000..71fc2c6 --- /dev/null +++ b/morphology/src/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 deleted file mode 100755 index 3ae669b..0000000 Binary files a/morphology/test_sequence and /dev/null differ diff --git a/morphology/test_set b/morphology/test_set deleted file mode 100755 index b8b1e34..0000000 Binary files a/morphology/test_set and /dev/null differ diff --git a/morphology/test_value b/morphology/test_value deleted file mode 100755 index 8bccac3..0000000 Binary files a/morphology/test_value and /dev/null differ -- cgit v1.2.3