extern crate clap;
extern crate rand;

use clap::{Arg, App};
use std::collections::vec_deque::VecDeque;
use std::io::{self, BufRead};
use std::result::Result;

fn some<R: rand::Rng, T: Iterator<Item = Result<String, io::Error>>>(
    r: &mut R,
    n: usize,
    lines: T,
) -> Result<VecDeque<String>, io::Error> {
    let mut result: VecDeque<String> = VecDeque::with_capacity(n);
    fn push(v: &mut VecDeque<String>, n: usize, x: String) {
        v.push_back(x);
        if v.len() > n {
            v.pop_front();
        }
    };

    for (i, line) in lines.enumerate() {
        let line = line?;
        if result.len() < n {
            push(&mut result, n, line);
        } else if r.gen_range(0, i) < n {
            let victim = r.gen_range(0, n);
            result.remove(victim);
            push(&mut result, n, line);

            // Assumption: |result| contains m random elements from the (i-1)
            // first lines.
            //
            // |line| is in result with n/i probability (if expression)
        }
        // An arbitrary line0 occuring before line was in result with
        // probability m/(i-1).
        //
        // P(line0 is still in result) =
        //   m/i * (1 - 1/m) + (1 - m/i) =
        //   m/i - 1/i + 1 - m/i = 1 - 1/i = (i-1) / i
        //
        // The probability that an arbitrary line from the i first lines is in
        // |result| is: m/(i-1) * ((i-1)/i) = m/i. The induction holds.
    }
    return Ok(result);
}

fn main() {
    let matches = App::new("some")
        .version("0.1")
        .author("Kjetil Ørbekk <kj@orbekk.com>")
        .arg(
            Arg::with_name("lines")
                .short("n")
                .value_name("NUM")
                .help("Number of lines to print")
                .takes_value(true),
        )
        .get_matches();
    let num_lines = matches
        .value_of("lines")
        .unwrap_or("10")
        .parse::<usize>()
        .expect("number of lines to print");
    let stdin = io::stdin();
    let lines = some(&mut rand::thread_rng(), num_lines, stdin.lock().lines());
    match lines {
        Ok(lines) => {
            for line in lines {
                println!("{}", line);
            }
        }
        Err(e) => println!("Error: {}", e),
    }
}