From c20b1fe88b0ab1469300bd53be14faa6a5b917a0 Mon Sep 17 00:00:00 2001 From: jacksonfu14 Date: Thu, 6 Nov 2025 07:04:52 +0100 Subject: initial commit --- morphology/meta_affine/set.rs | 349 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 349 insertions(+) create mode 100644 morphology/meta_affine/set.rs (limited to 'morphology/meta_affine/set.rs') 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() +} -- cgit v1.2.3