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

use std::collections::HashSet;

use choice::PatternElemChoice;
use meta::MetaAnalyzer;
use pattern::{CustomPatternElem, Pattern, PatternElem};
use stepper::Stepper;

/// Identifies patterns that describe a given sequence.
pub struct Analyzer {
    choices: Vec<PatternElemChoice>,
    meta: bool,
}

impl Analyzer {
    /// Creates a new Analyzer from a slice of integers.
    pub fn from_slice(seq: &[i32]) -> Self {
        Self::with_custom_patterns(seq, Vec::new())
    }

    /// Same as `from_slice`, but also finds meta-patterns.
    pub fn with_meta(seq: &[i32]) -> Self {
        Self::with_options(seq, true, Vec::new())
    }

    /// Same as `from_slice`, but allows custom patterns elements to be specified.
    pub fn with_custom_patterns(seq: &[i32], pats: Vec<CustomPatternElem>) -> Self {
        Self::with_options(seq, false, pats)
    }

    /// Creates a new Analyzer, specifying custom pattern elements and whether meta-patterns
    /// should be found.
    pub fn with_options(seq: &[i32], meta: bool, pats: Vec<CustomPatternElem>) -> Self {
        Analyzer {
            meta: meta,
            choices: (0..seq.len() - 1).map(|i|
                         PatternElemChoice::from_i32_pair(seq[i], seq[i + 1], pats.clone())
                     ).collect()
        }
    }

    /// Attempts to find exactly one pattern of `n` operations that described the given sequence.
    pub fn find_any_pattern_of_length(&self, n: usize) -> Option<Pattern> {
        // TODO: Short-circuit finding one pattern instead of all of them
        self.find_patterns_of_length(n).pop()
    }

    /// Attempts to find exactly one pattern of maximum size `max` (in terms of number of
    /// operations) that describes the given sequence. It returns the smallest such pattern it can
    /// find .
    pub fn find_any_pattern(&self, max: usize) -> Option<Pattern> {
        for i in 1..max + 1 {
            let mut vec = self.find_patterns_of_length(i);

            // TODO: Short-circuit finding one pattern instead of all of them
            if !vec.is_empty() {
                return vec.pop();
            }
        }

        return None;
    }

    /// Finds all patterns with `n` operations that describe the given sequence.
    pub fn find_patterns_of_length(&self, range: usize) -> Vec<Pattern> {
        let mut pats = vec![Pattern::empty()];

        for i in 0..range {
            let choices: Vec<_> = step!(i => self.len(); range).map(|i| self.choices[i].clone()).collect();

            let meta_patterns = if self.meta {
                self.find_meta_patterns(i, range)
            } else {
                Vec::new()
            };

            let mut new = Vec::new();

            for pat in pats.iter_mut() {
                let mut new_pats = Self::intersection(&choices[..]);
                new_pats.extend(meta_patterns.clone());
                new.extend(pat.extend_each(new_pats.into_iter()).into_iter());
            }

            pats = new;

            // Makes results deterministic, which is helpful.
            pats.sort();
        }

        pats
    }

    /// Finds patterns of maximum size `max` (in terms of number of operations) that describe the
    /// given sequence. It will return all such patterns that are of minimal size (i.e. if a
    /// sequence can be described by a pattern of two operations, it will return all such patterns,
    /// but none of size three or greater).
    pub fn find_patterns(&self, max: usize) -> Vec<Pattern> {
        for i in 1..max + 1 {
            let vec = self.find_patterns_of_length(i);

            if !vec.is_empty() {
                return vec;
            }
        }

        return Vec::new();
    }

    #[inline]
    fn len(&self) -> usize {
        self.choices.len()
    }

    fn intersection(slice: &[PatternElemChoice]) -> HashSet<PatternElem> {
        let base = match slice.first() {
            Some(&PatternElemChoice(ref choices)) => choices.clone(),
            None => return HashSet::new()
        };

        slice.into_iter().fold(base, |set, choice| set.intersection(&choice.0).cloned().collect())
    }

    fn find_meta_patterns(&self, offset: usize, range: usize) -> Vec<PatternElem> {
        let choices: Vec<_> = step!(offset => self.len(); range).map(|i| self.choices[i].clone()).collect();
        let meta_analyzer = MetaAnalyzer::new(choices);

        meta_analyzer.find_patterns().into_iter().map(|pat| PatternElem::Meta(pat)).collect()
    }
}