#![deny(missing_docs)]
use std::collections::HashMap;
use std::collections::BTreeMap;
pub mod cmp;
pub use cmp::Comparison;
pub use cmp::Condition;
pub use cmp::Value;
pub mod idx;
pub use idx::EqualityIndex;
pub use idx::RangeIndex;
pub use idx::Index;
pub struct Store<T, C = Vec<T>> {
cols: usize,
rowid: usize,
rows: BTreeMap<usize, C>,
indices: HashMap<usize, Index<T>>,
}
pub trait Row<T> {
fn index(&self, column: usize) -> &T;
fn columns(&self) -> usize;
}
impl<T, R> Store<T, R>
where T: Ord + Clone,
R: Row<T>
{
pub fn new(cols: usize) -> Store<T, R> {
Store {
cols: cols,
rowid: 0,
rows: BTreeMap::new(),
indices: HashMap::new(),
}
}
fn using_index<'c, 's: 'c>(&'s self,
conds: &'c [cmp::Condition<'c, T>])
-> Box<Iterator<Item = usize> + 's> {
use EqualityIndex;
let best_idx = conds.iter()
.enumerate()
.filter_map(|(ci, c)| self.indices.get(&c.column).and_then(|idx| Some((ci, idx))))
.filter(|&(ci, _)| {
match conds[ci].cmp {
cmp::Comparison::Equal(cmp::Value::Const(..)) => true,
_ => false,
}
})
.min_by_key(|&(_, idx)| idx.estimate());
best_idx.and_then(|(ci, idx)| match conds[ci].cmp {
cmp::Comparison::Equal(cmp::Value::Const(ref v)) => Some(idx.lookup(v)),
_ => unreachable!(),
})
.unwrap_or_else(|| Box::new(self.rows.keys().map(|k| *k)))
}
pub fn find<'c, 's: 'c>(&'s self,
conds: &'c [cmp::Condition<'c, T>])
-> Box<Iterator<Item = &'s R> + 'c> {
let is_a_match = move |r: &&'s _| conds.iter().all(|c| c.matches(*r));
Box::new(self.using_index(conds)
.map(move |rowi| &self.rows[&rowi])
.filter(is_a_match))
}
pub fn delete(&mut self, conds: &[cmp::Condition<T>]) {
self.delete_filter(conds, |_| true);
}
pub fn delete_filter<F>(&mut self, conds: &[cmp::Condition<T>], mut f: F)
where F: FnMut(&R) -> bool
{
let rowids = self.using_index(conds)
.map(|rowi| (rowi, &self.rows[&rowi]))
.filter(move |&(_, row)| conds.iter().all(|c| c.matches(row)))
.filter(|&(_, row)| f(row))
.map(|(rowid, _)| rowid)
.collect::<Vec<_>>();
let deleted = rowids.into_iter()
.map(|rowid| (rowid, self.rows.remove(&rowid).unwrap()))
.collect::<Vec<_>>();
for (rowid, row) in deleted.into_iter() {
for (col, idx) in self.indices.iter_mut() {
idx.undex(row.index(*col), rowid);
}
}
}
pub fn insert(&mut self, row: R) {
debug_assert_eq!(row.columns(), self.cols);
let rowid = self.rowid;
for (column, idx) in self.indices.iter_mut() {
use EqualityIndex;
idx.index(row.index(*column).clone(), rowid);
}
self.rows.insert(self.rowid, row);
self.rowid += 1;
}
pub fn index<I: Into<Index<T>>>(&mut self, column: usize, indexer: I) {
use EqualityIndex;
let mut idx = indexer.into();
for (rowid, row) in self.rows.iter() {
idx.index(row.index(column).clone(), *rowid);
}
self.indices.insert(column, idx);
}
}
impl<'a, T> Row<T> for &'a [T] {
fn index(&self, i: usize) -> &T {
&self[i]
}
fn columns(&self) -> usize {
self.len()
}
}
impl<T> Row<T> for [T] {
fn index(&self, i: usize) -> &T {
&self[i]
}
fn columns(&self) -> usize {
self.len()
}
}
impl<T> Row<T> for Vec<T> {
fn index(&self, i: usize) -> &T {
&self[i]
}
fn columns(&self) -> usize {
self.len()
}
}
use std::sync;
impl<T> Row<T> for sync::Arc<Vec<T>> {
fn index(&self, i: usize) -> &T {
&self[i]
}
fn columns(&self) -> usize {
self.len()
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn it_works() {
let mut store = Store::new(2);
store.insert(vec!["a1", "a2"]);
store.insert(vec!["b1", "b2"]);
store.insert(vec!["c1", "c2"]);
assert_eq!(store.find(&[]).count(), 3);
}
#[test]
fn it_works_w_non_vec() {
use std::sync;
let mut store = Store::new(2);
store.insert(sync::Arc::new(vec!["a1", "a2"]));
store.insert(sync::Arc::new(vec!["b1", "b2"]));
store.insert(sync::Arc::new(vec!["c1", "c2"]));
assert_eq!(store.find(&[]).count(), 3);
}
#[test]
fn it_works_with_indices() {
let mut store = Store::new(2);
store.index(0, idx::HashIndex::new());
store.insert(vec!["a1", "a2"]);
store.insert(vec!["b1", "b2"]);
store.insert(vec!["c1", "c2"]);
assert_eq!(store.find(&[]).count(), 3);
}
#[test]
fn it_filters() {
let mut store = Store::new(2);
store.insert(vec!["a", "x1"]);
store.insert(vec!["a", "x2"]);
store.insert(vec!["b", "x3"]);
let cmp = [cmp::Condition {
column: 0,
cmp: cmp::Comparison::Equal(cmp::Value::new("a")),
}];
assert_eq!(store.find(&cmp)
.count(),
2);
assert!(store.find(&cmp).all(|r| r[0] == "a"));
}
#[test]
fn it_filters_with_indices() {
let mut store = Store::new(2);
store.index(0, idx::HashIndex::new());
store.insert(vec!["a", "x1"]);
store.insert(vec!["a", "x2"]);
store.insert(vec!["b", "x3"]);
let cmp = [cmp::Condition {
column: 0,
cmp: cmp::Comparison::Equal(cmp::Value::new("a")),
}];
assert_eq!(store.find(&cmp)
.count(),
2);
assert!(store.find(&cmp).all(|r| r[0] == "a"));
}
#[test]
fn it_filters_with_partial_indices() {
let mut store = Store::new(2);
store.index(0, idx::HashIndex::new());
store.insert(vec!["a", "x1"]);
store.insert(vec!["a", "x2"]);
store.insert(vec!["b", "x3"]);
let cmp = [cmp::Condition {
column: 0,
cmp: cmp::Comparison::Equal(cmp::Value::new("a")),
},
cmp::Condition {
column: 1,
cmp: cmp::Comparison::Equal(cmp::Value::new("x2")),
}];
assert_eq!(store.find(&cmp).count(), 1);
assert!(store.find(&cmp).all(|r| r[0] == "a" && r[1] == "x2"));
}
#[test]
fn it_filters_with_late_indices() {
let mut store = Store::new(2);
store.insert(vec!["a", "x1"]);
store.insert(vec!["a", "x2"]);
store.insert(vec!["b", "x3"]);
store.index(0, idx::HashIndex::new());
let cmp = [cmp::Condition {
column: 0,
cmp: cmp::Comparison::Equal(cmp::Value::new("a")),
}];
assert_eq!(store.find(&cmp)
.count(),
2);
assert!(store.find(&cmp).all(|r| r[0] == "a"));
}
#[test]
fn is_send_sync() {
use std::sync;
use std::thread;
let store = sync::Arc::new(Store::<()>::new(0));
thread::spawn(move || { drop(store); })
.join()
.unwrap();
}
#[test]
fn it_deletes() {
let mut store = Store::new(2);
store.insert(vec!["a1", "a2"]);
store.insert(vec!["b1", "b2"]);
store.insert(vec!["c1", "c2"]);
store.delete(&[]);
assert_eq!(store.find(&[]).count(), 0);
}
#[test]
fn filtered_delete() {
let mut store = Store::new(2);
store.insert(vec!["a1", "a2"]);
store.insert(vec!["b1", "b2"]);
store.insert(vec!["c1", "c2"]);
store.delete_filter(&[], |row| row[0] != "b1");
assert_eq!(store.find(&[]).count(), 1);
assert!(store.find(&[]).all(|r| r[0] == "b1"));
}
#[test]
fn it_deletes_with_filters() {
let mut store = Store::new(2);
store.insert(vec!["a", "x1"]);
store.insert(vec!["a", "x2"]);
store.insert(vec!["b", "x3"]);
let cmp = [cmp::Condition {
column: 0,
cmp: cmp::Comparison::Equal(cmp::Value::new("a")),
}];
store.delete(&cmp);
assert_eq!(store.find(&cmp).count(), 0);
assert_eq!(store.find(&[]).count(), 1);
assert!(store.find(&[]).all(|r| r[0] == "b"));
}
#[test]
fn it_deletes_with_indices() {
let mut store = Store::new(2);
store.index(0, idx::HashIndex::new());
store.insert(vec!["a", "x1"]);
store.insert(vec!["a", "x2"]);
store.insert(vec!["b", "x3"]);
let cmp = [cmp::Condition {
column: 0,
cmp: cmp::Comparison::Equal(cmp::Value::new("a")),
}];
store.delete(&cmp);
assert_eq!(store.find(&cmp).count(), 0);
assert_eq!(store.find(&[]).count(), 1);
assert!(store.find(&[]).all(|r| r[0] == "b"));
}
#[test]
fn it_deletes_with_partial_indices() {
let mut store = Store::new(2);
store.index(0, idx::HashIndex::new());
store.insert(vec!["a", "x1"]);
store.insert(vec!["a", "x2"]);
store.insert(vec!["b", "x3"]);
let cmp = [cmp::Condition {
column: 0,
cmp: cmp::Comparison::Equal(cmp::Value::new("a")),
},
cmp::Condition {
column: 1,
cmp: cmp::Comparison::Equal(cmp::Value::new("x2")),
}];
store.delete(&cmp);
assert_eq!(store.find(&cmp).count(), 0);
assert_eq!(store.find(&[]).count(), 2);
assert!(store.find(&[]).any(|r| r[0] == "a" && r[1] == "x1"));
assert!(store.find(&[]).any(|r| r[0] == "b" && r[1] == "x3"));
}
}