//! 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; use std::hash::{Hash, Hasher}; use std::collections::hash_map::DefaultHasher; use rayon::prelude::*; /// Represents a valid set in meta-affine space. #[derive(Debug, Clone, PartialEq, Eq)] pub struct ValidSet { values: HashSet, } impl Hash for ValidSet { fn hash(&self, state: &mut H) { // Hash using XOR of individual value hashes (commutative, O(n)) // This avoids sorting while ensuring equal sets produce equal hashes let combined_hash = self.values.iter() .map(|v| { let mut hasher = DefaultHasher::new(); v.hash(&mut hasher); hasher.finish() }) .fold(0u64, |acc, h| acc ^ h); // Hash both the XOR result and size to avoid collisions combined_hash.hash(state); self.values.len().hash(state); } } 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 { // Process sets in parallel let new_sets_vec: Vec = sets_by_size[size - 1] .par_iter() .flat_map(|prev_set| { let candidates = get_candidate_values(prev_set, max_size as i32); candidates.into_iter().filter_map(|candidate| { let new_set = prev_set.add_value_with_dependencies(candidate); if new_set.size() == size { Some(new_set) } else { None } }).collect::>() }) .collect(); // Deduplicate using HashSet let new_sets: HashSet = new_sets_vec.into_iter().collect(); // 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() }