#![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;
#[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.));
});
}