summaryrefslogtreecommitdiff
path: root/morphology/src/sequence.rs
blob: 2203e834bea0666e16c20649985c06b8585e3e79 (plain)
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
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
//! 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};
use rayon::prelude::*;

/// 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);

    // Process sets in parallel
    all_sets
        .par_iter()
        .flat_map(|set| generate_sequences(set, length))
        .collect()
}

/// 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()
}