//! A crate for matching patterns from a noisy signal against a dictionary of known words from an
//! [alien language][1].
//!
//! [1]: https://code.google.com/codejam/contest/90101/dashboard#s=p0

#![feature(test)]
#![allow(unused_features)]
#![deny(warnings,missing_docs)]

use std::io;

extern crate bit_set;
use bit_set::BitSet;

static ASCII_LOWERCASE: &'static str = "abcdefghijklmnopqrstuvwxyz";

/// Represents an alien language problem set (sample, small, or large).
///
/// # Examples
///
/// ```
/// use std::io::BufReader;
/// use std::fs::File;
/// use std::io::prelude::*;
///
/// use alienlanguage::Problem;
///
/// # fn main() {
/// #     let expected_f = File::open("tests/expected/sample.txt").unwrap();
/// #     let mut expected_lines = BufReader::new(expected_f).lines();
/// #     let mut next_expected_line = || expected_lines.next().unwrap().unwrap();
/// let f = File::open("input/sample.txt").unwrap();
/// let mut lines = BufReader::new(f).lines();
/// let problem = Problem::from_lines(&mut lines);
/// for case in problem {
/// #   assert_eq!(case, next_expected_line());
///     println!("{}", case);
/// }
/// # }
/// ```
pub struct Problem<'a> {
    words: Vec<String>,
    lines: &'a mut Iterator<Item = io::Result<String>>,
    case_number: usize,
}

impl<'a> Problem<'a> {
    /// Constructs a new `Problem` with the specified input lines iterator.
    ///
    /// # Examples
    ///
    /// ```
    /// # use std::io::BufReader;
    /// # use std::fs::File;
    /// # use std::io::prelude::*;
    ///
    /// # use alienlanguage::Problem;
    ///
    /// # fn main() {
    /// #     let expected_f = File::open("tests/expected/sample.txt").unwrap();
    /// #     let mut expected_lines = BufReader::new(expected_f).lines();
    /// #     let mut next_expected_line = || expected_lines.next().unwrap().unwrap();
    /// let f = File::open("input/sample.txt").unwrap();
    /// let mut lines = BufReader::new(f).lines();
    /// let problem = Problem::from_lines(&mut lines);
    /// #     for case in problem {
    /// #         assert_eq!(case, next_expected_line());
    /// #         println!("{}", case);
    /// #     }
    /// # }
    /// ```
    pub fn from_lines(lines: &'a mut Iterator<Item = io::Result<String>>) -> Problem<'a> {
        // The first line of input contains 3 integers, L, D and N separated by a space.
        let mut ldn = [0; 3];
        for (i, j) in lines.next().unwrap().unwrap().split_whitespace().enumerate() {
            ldn[i] = j.parse::<usize>().unwrap();
            assert!(ldn[i] > 0);
        }
        let (l, d, _) = (ldn[0], ldn[1], ldn[2]);

        // D lines follow, each containing one word of length L.
        let mut words: Vec<String> = Vec::with_capacity(d);
        for _ in 0..d {
            let word = lines.next().unwrap().unwrap();
            assert_eq!(word.len(), l);
            words.push(word);
        }
        assert_eq!(words.len(), d);

        Problem {
            words: words,
            lines: lines,
            case_number: 0,
        }
    }

    fn solve(&mut self, pattern: &str) -> String {
        let tokens = tokenize(pattern, self.words[0].len());
        let mut match_count = 0;
        for word in self.words.iter() {
            match_count += is_match(&tokens, &word);
        }
        self.case_number += 1;
        format!("Case #{}: {}", self.case_number, match_count)
    }
}

impl<'a> Iterator for Problem<'a> {
    type Item = String;

    fn next(&mut self) -> Option<String> {
        // A pattern consists of exactly L tokens. Each token is either a single lowercase letter
        // (the scientists are very sure that this is the letter) or a group of unique lowercase
        // letters surrounded by parenthesis ( and ). For example: (ab)d(dc) means the first letter
        // is either a or b, the second letter is definitely d and the last letter is either d or c.
        // Therefore, the pattern (ab)d(dc) can stand for either one of these 4 possibilities: add,
        // adc, bdd, bdc.
        //
        // N test cases then follow, each on its own line and each consisting of a pattern as
        // described above.
        match self.lines.next() {
            Some(pattern) => Some(self.solve(&pattern.unwrap())),
            _ => None,
        }
    }
}

fn tokenize(pattern: &str, l: usize) -> Vec<BitSet> {
    let mut tokens = Vec::with_capacity(l);
    let mut token = BitSet::with_capacity(ASCII_LOWERCASE.len());
    let mut in_parens = false;
    for c in pattern.chars() {
        match c {
            '(' => {
                if in_parens {
                    panic!("got nested '('")
                }
                in_parens = true;
                continue;
            }
            ')' => {
                if !in_parens {
                    panic!("got ')' without preceding '('")
                }
                if token.is_empty() {
                    panic!("empty parens")
                }
                in_parens = false
            }
            _ => {
                match ASCII_LOWERCASE.find(c) {
                    Some(i) => {
                        token.insert(i);
                        if in_parens {
                            continue;
                        }
                    }
                    _ => panic!("illegal character in pattern: {}", c),
                }
            }
        }
        tokens.push(token);
        token = BitSet::with_capacity(ASCII_LOWERCASE.len());
    }
    assert!(tokens.len() <= l);
    tokens
}

fn is_match(tokens: &Vec<BitSet>, word: &str) -> i32 {
    for (i, c) in word.chars().enumerate() {
        match ASCII_LOWERCASE.find(c) {
            Some(j) => {
                if !tokens[i].contains(j) {
                    return 0;
                }
            }
            _ => panic!("illegal char in word: {}", word),
        }
    }
    1
}

#[cfg(test)]
mod tests {

    extern crate test;
    use self::test::Bencher;

    use std::io::BufReader;
    use std::fs::File;
    use std::io::prelude::*;

    use super::{Problem, is_match, tokenize};

    #[test]
    fn it_works() {
        let words = ["abc", "bca", "dac", "dbc", "cba"];
        let patterns = ["(ab)(bc)(ca)", "abc", "(abc)(abc)(abc)", "(zyx)bc"];
        let expected = [2, 1, 3, 0];
        for (i, pattern) in patterns.into_iter().enumerate() {
            let tokens = tokenize(&pattern, words[0].len());
            let mut actual = 0;
            for word in &words {
                actual += is_match(&tokens, word);
            }
            assert_eq!(actual, expected[i]);
        }
    }

    #[bench]
    fn bench(b: &mut Bencher) {
        let f = File::open(format!("input/large.txt")).unwrap();
        let mut lines = BufReader::new(f).lines();
        let mut problem = Problem::from_lines(&mut lines);
        let pattern = ["(hijklmnopqrstuvwxyabcdefg)",
                       "(fghijklmnopqrstuvwxzabcde)",
                       "(vwyzabcdefghijklmnpqrstu)",
                       "(yzacdefghijklmopqrtvw)",
                       "(suvwxyzabcegijlmnopq)",
                       "(bcdefghiklnoqrtuvwxyza)",
                       "(abefghijklmnopqrstvxyz)",
                       "(stuvwxyzacdefghijlmnopr)",
                       "(hijklmnoprtuvwxyzabcdefg)",
                       "(bcdeghijklmnopstuvwxyza)",
                       "(efghijklnopqrtuvwyzabcd)",
                       "(nopqruvwxyzabcdefghijk)",
                       "(uvwxzabcdefghijklmnopqrst)",
                       "(nopqrstuvwxyzabcdefghijklm)",
                       "(hijlmnoprstuvwxzabcdefg)"]
            .join("");
        b.iter(|| problem.solve(&pattern));
    }
}