1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
|
//! 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;
/// Represents a valid set in meta-affine space.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ValidSet {
values: HashSet<Value>,
}
impl Hash for ValidSet {
fn hash<H: Hasher>(&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<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 = HashSet::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 (HashSet automatically deduplicates)
if new_set.size() == size {
new_sets.insert(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()
}
|