queriable_storage/lib.rs
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217
//! # queriable_storage
//!
//! `queriable_storage` is a create that provides the [QueriableDataStore](QueriableDataStore) that can be queried by multiple filters.
//! # Examples
//! ```
//! use queriable_storage::QueriableDataStore;
//! struct Person {
//! first_name: &'static str,
//! last_name: &'static str,
//! age: u32,
//! }
//! let persons:Vec<Person> = vec![/* ...*/];
//! let storage: QueriableDataStore<Person> = persons.into();
//! let first_name_index = storage.get_index(|v| v.first_name);
//! let last_name_index = storage.get_index(|v| v.last_name);
//! let age_index = storage.get_index(|v| v.age);
//! let filtered: Vec<&Person> = storage
//! .filter(
//! (first_name_index.filter_eq("Isaiah") & last_name_index.filter_eq("Mccarthy"))
//! | (age_index.filter_lt(30) | age_index.filter_gte(60)),
//! )
//! .collect();
//! ```
use std::{
collections::BTreeMap,
ops::{BitAnd, BitOr, Bound::*, RangeBounds},
};
use iter_set::{intersection, union};
///Data structure that can be queried by multiple filters.
///Its not allowed to modify data after the generation of the data store.
pub struct QueriableDataStore<T> {
items: Vec<T>,
}
impl<T> QueriableDataStore<T> {
///Get all entries of the [DataStore](QueriableDataStore) that match the filter.
pub fn filter(&self, filter: DataFilter) -> impl Iterator<Item = &T> {
filter.indices.into_iter().map(move |v| &self.items[v])
}
///Get a new [Index](SortedIndex) for the [DataStore](QueriableDataStore) for the provided key.
pub fn get_index<F, U>(&self, index_provider: F) -> SortedIndex<U>
where
F: Fn(&T) -> U,
U: Ord,
{
SortedIndex::new(self, index_provider)
}
///Iterate over all items in the [DataStore](QueriableDataStore).
pub fn items(&self) -> impl Iterator<Item = &T> {
self.items.iter()
}
}
impl<T> From<Vec<T>> for QueriableDataStore<T> {
fn from(items: Vec<T>) -> Self {
Self { items }
}
}
///Index of a [DataStore](QueriableDataStore).
#[derive(Clone, Eq, PartialEq)]
pub struct SortedIndex<T> {
pairs: BTreeMap<T, Vec<usize>>,
}
impl<T> SortedIndex<T>
where
T: Ord,
{
///Creates a new [Index](SortedIndex) from a [DataStore](QueriableDataStore) for the index provided by the index_provider function.
pub fn new<F, U>(data_store: &QueriableDataStore<U>, index_provider: F) -> Self
where
F: Fn(&U) -> T,
{
let mut pairs: BTreeMap<T, Vec<usize>> = BTreeMap::new();
for (index, item) in data_store.items().enumerate() {
let key = index_provider(item);
pairs.entry(key).or_insert_with(|| vec![]).push(index);
}
Self { pairs }
}
///Get a new [DataFilter](DataFilter) for all items in the given range.
pub fn filter_range<R>(&self, range: R) -> DataFilter
where
R: RangeBounds<T>,
{
let filtered = self
.pairs
.range(range)
.into_iter()
.flat_map(|(_, indices)| indices.iter().cloned());
DataFilter::from_unsorted(filtered)
}
///Get a new [DataFilter](DataFilter) for all items between the given values (including lower and upper value).
pub fn filter_between(&self, lower_inclusive: T, upper_inclusive: T) -> DataFilter {
self.filter_range((Included(lower_inclusive), Included(upper_inclusive)))
}
///Get a new [DataFilter](DataFilter) for all items that are equivalent to the given value.
pub fn filter_eq(&self, value: T) -> DataFilter {
if let Some(keys) = self.pairs.get(&value) {
DataFilter::from_unsorted(keys.iter().cloned())
} else {
DataFilter::default()
}
}
///Get a new [DataFilter](DataFilter) for all items that are greater than the given value.
pub fn filter_gt(&self, lower_limit: T) -> DataFilter {
self.filter_range((Excluded(lower_limit), Unbounded))
}
///Get a new [DataFilter](DataFilter) for all items that are greater than ore equal to the given value.
pub fn filter_gte(&self, lower_limit: T) -> DataFilter {
self.filter_range((Included(lower_limit), Unbounded))
}
///Get a new [DataFilter](DataFilter) for all items that are less than the given value.
pub fn filter_lt(&self, upper_limit: T) -> DataFilter {
self.filter_range((Unbounded, Excluded(upper_limit)))
}
///Get a new [DataFilter](DataFilter) for all items that are less than ore equal to the given value.
pub fn filter_lte(&self, upper_limit: T) -> DataFilter {
self.filter_range((Unbounded, Included(upper_limit)))
}
///Get the first element in the index
pub fn first(&self) -> DataFilter {
DataFilter::from_unsorted(
self.pairs
.iter()
.flat_map(|v| v.1.iter())
.cloned()
.nth(0)
.into_iter(),
)
}
///Get the first n elements of the index (less if the amount of items is smaller then n)
pub fn first_n(&self, n: usize) -> DataFilter {
DataFilter::from_unsorted(self.pairs.iter().flat_map(|v| v.1.iter()).cloned().take(n))
}
///Get the last element in the index
pub fn last(&self) -> DataFilter {
DataFilter::from_unsorted(
self.pairs
.iter()
.rev()
.flat_map(|v| v.1.iter())
.cloned()
.nth(0)
.into_iter(),
)
}
///Get the last n elements of the index (less if the amount of items is smaller then n)
pub fn last_n(&self, n: usize) -> DataFilter {
DataFilter::from_unsorted(
self.pairs
.iter()
.rev()
.flat_map(|v| v.1.iter())
.cloned()
.take(n),
)
}
}
///Contains all items that match a given filter.
///Can be combined with the bitwise logical operators (& |).
#[derive(Default)]
pub struct DataFilter {
indices: Vec<usize>,
}
impl DataFilter {
///Creates a [DataFilter](DataFilter) from an unsorted list of indices.
fn from_unsorted<T>(unsorted_indices: T) -> Self
where
T: Iterator<Item = usize>,
{
let mut indices: Vec<usize> = unsorted_indices.collect();
indices.sort();
Self { indices }
}
}
impl BitAnd for DataFilter {
type Output = DataFilter;
fn bitand(self, other: DataFilter) -> Self::Output {
Self {
indices: intersection(self.indices, other.indices).collect(),
}
}
}
impl BitOr for DataFilter {
type Output = DataFilter;
fn bitor(self, other: DataFilter) -> Self::Output {
Self {
indices: union(self.indices, other.indices).collect(),
}
}
}