#![feature(test)]
extern crate rand;
extern crate test;
extern crate gst;
use std::collections::BTreeMap;
use gst::gst::GstKey;
use gst::rtree::Rect;
use rand::thread_rng;
use rand::distributions::{IndependentSample, Range};
use test::Bencher;


/// A terrible implementation of an R tree to get a baseline idea of the trade offs of more
/// complicated structures vs. smarter lookups.
#[derive(Default)]
pub struct RTreeBad<K: GstKey+Ord, V> {
    root: BTreeMap<K, V>
}

impl<K: GstKey+Ord, V> RTreeBad<K, V> {
    pub fn new() -> Self {
        RTreeBad { root: BTreeMap::new() }
    }

    pub fn insert(&mut self, key: K, val: V) {
        self.root.insert(key, val);
    }

    pub fn get(&self, key: &K) -> Vec<(&K, &V)> {
        let v = self.root.iter().collect::<Vec<_>>();
        v.iter().filter_map(|&(k, v)| {
            if key.consistent(k) { Some((k, v)) } else { None}
        }).collect::<Vec<_>>()
    }
}



#[bench]
fn bench_rtreebad_inserts(b: &mut Bencher) {
    let mut rng = thread_rng();
    let mut rtree = RTreeBad::new();
    let between = Range::new(-100f32, 100f32);
    let vals = (0..100_000).map(|_| {
        let x = between.ind_sample(&mut rng);
        let y = between.ind_sample(&mut rng);
        (x, y)
    }).collect::<Vec<_>>();
    let mut vals_iter = vals.into_iter();
    let word = "Hello".to_string();
    b.iter(|| {
        let (x, y) = vals_iter.next().unwrap();
        rtree.insert(Rect::from_float(x, x, y, y), word.clone());
    });
}

#[bench]
fn bench_rtreebad_lookups(b: &mut Bencher) {
    let mut rng = thread_rng();
    let mut rtree = RTreeBad::new();
    let between = Range::new(-100f32, 100f32);
    (0..100_000).map(|i| {
        let x = between.ind_sample(&mut rng);
        let y = between.ind_sample(&mut rng);
        rtree.insert(Rect::from_float(x, x, y, y), format!("{}", i.to_string()));
    }).collect::<Vec<_>>();

    let vals = (0..10_000).map(|_| {
        let x = between.ind_sample(&mut rng);
        let y = between.ind_sample(&mut rng);
        (x, y)
    }).collect::<Vec<_>>();
    let mut vals_iter = vals.into_iter().cycle();
    b.iter(|| {
        let (x, y) = vals_iter.next().unwrap();
        rtree.get(&Rect::from_float(x-1., x+1., y-1., y+1.));
    });
}