summaryrefslogtreecommitdiff
path: root/morphology/meta_affine
diff options
context:
space:
mode:
Diffstat (limited to 'morphology/meta_affine')
-rw-r--r--morphology/meta_affine/lib.rs22
-rw-r--r--morphology/meta_affine/sequence.rs411
-rw-r--r--morphology/meta_affine/set.rs349
-rw-r--r--morphology/meta_affine/value.rs170
4 files changed, 0 insertions, 952 deletions
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<Value>,
-}
-
-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<Value>) -> 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<Value> = 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<i32, usize> = 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<Sequence> {
- // 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<Value> = 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<Value>,
- coverage: &mut HashSet<Value>,
- set_values: &[Value],
- set: &ValidSet,
- target_length: usize,
- result: &mut Vec<Sequence>,
-) {
- // 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<Value>,
- 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<i32, usize> = 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<Sequence> {
- use crate::set::generate_valid_sets;
-
- let max_set_size = length; // Heuristic: set size can't exceed sequence length
- let all_sets = generate_valid_sets(max_set_size);
-
- 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<Value>,
-}
-
-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<Value>) -> Result<Self, String> {
- 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<Self, String> {
- 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<Item = &Value> {
- 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<Value> {
- let mut sorted: Vec<Value> = 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<ValidSet> {
- 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<ValidSet>> = 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<Value> {
- 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<ValidSet> {
- 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<Value> {
- 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<Value> {
- 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<Value> {
- 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
-}