summaryrefslogtreecommitdiff
path: root/morphology/meta_affine/set.rs
diff options
context:
space:
mode:
authorjacksonfu14 <jackson@fashionunited.com>2025-11-06 07:50:44 +0100
committerJackson Moore <jacksonmoore@tuta.io>2025-11-06 07:50:44 +0100
commite4c5409397e6e833984d221d63a62ea7bcb2c4a9 (patch)
tree9754d7a8b1a7f6185a0585c7a7a783f24326b2dd /morphology/meta_affine/set.rs
parentc20b1fe88b0ab1469300bd53be14faa6a5b917a0 (diff)
refactor: use cargo
Diffstat (limited to 'morphology/meta_affine/set.rs')
-rw-r--r--morphology/meta_affine/set.rs349
1 files changed, 0 insertions, 349 deletions
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()
-}