From 8a1d977f0c31519437b6226af914cbc0415293f9 Mon Sep 17 00:00:00 2001 From: Chris Mikkelson Date: Sun, 14 Jul 2024 15:31:15 -0500 Subject: [PATCH] Another refactor: back to mtbl C idioms Iter (includes seek + iterator), static entry type, Source, merger, etc. --- src/entry.rs | 25 +++++ src/lib.rs | 10 +- src/merger.rs | 163 +++++++++++++++++++++++++++ src/seekable.rs | 77 ------------- src/seekable/coalesce.rs | 90 --------------- src/seekable/filter_map.rs | 143 ----------------------- src/seekable/merge.rs | 224 ------------------------------------- src/seekable/vec.rs | 51 --------- src/source.rs | 159 ++++++++++++++++++++++++++ 9 files changed, 355 insertions(+), 587 deletions(-) create mode 100644 src/entry.rs create mode 100644 src/merger.rs delete mode 100644 src/seekable.rs delete mode 100644 src/seekable/coalesce.rs delete mode 100644 src/seekable/filter_map.rs delete mode 100644 src/seekable/merge.rs delete mode 100644 src/seekable/vec.rs create mode 100644 src/source.rs diff --git a/src/entry.rs b/src/entry.rs new file mode 100644 index 0000000..4e88f5a --- /dev/null +++ b/src/entry.rs @@ -0,0 +1,25 @@ +use std::sync::Arc; + +#[derive(Debug, Clone)] +pub struct Entry { + pub key: Arc>, + pub value: Arc>, +} + +impl Entry { + pub fn new(key: impl AsRef<[u8]>, value: impl AsRef<[u8]>) -> Self { + Entry { + key: Arc::new(Vec::from(key.as_ref())), + value: Arc::new(Vec::from(value.as_ref())), + } + } + + pub fn replace(&mut self, e: &Entry) { + let key = Arc::make_mut(&mut self.key); + let value = Arc::make_mut(&mut self.value); + key.clear(); + key.extend_from_slice(e.key.as_slice()); + value.clear(); + value.extend_from_slice(e.value.as_slice()); + } +} diff --git a/src/lib.rs b/src/lib.rs index 5335e69..fe36189 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -1,2 +1,8 @@ -pub mod seekable; -pub use seekable::Seekable; +pub mod entry; +use entry::Entry; + +pub mod source; +use source::{Iter, Source}; + +pub mod merger; +//use merger::Merger; diff --git a/src/merger.rs b/src/merger.rs new file mode 100644 index 0000000..e0e34e1 --- /dev/null +++ b/src/merger.rs @@ -0,0 +1,163 @@ +use crate::{Entry, Iter, Source}; +use std::cmp::Ordering; +use std::collections::BinaryHeap; +use std::marker::PhantomData; + +pub struct Merger<'a, S: Source> { + sources: Vec, + _p: PhantomData<&'a u8>, +} + +impl<'a, S, I> From for Merger<'a, S> +where + S: Source, + I: IntoIterator, +{ + fn from(i: I) -> Self { + Merger { + sources: Vec::from_iter(i), + _p: PhantomData, + } + } +} + +struct MergeEntry<'a> { + e: Entry, + it: Box, +} + +impl<'a> PartialEq for MergeEntry<'a> { + fn eq(&self, other: &Self) -> bool { + self.e.key == other.e.key + } +} +impl<'a> Eq for MergeEntry<'a> {} + +impl<'a> PartialOrd for MergeEntry<'a> { + fn partial_cmp(&self, other: &Self) -> Option { + Some(other.e.key.cmp(&self.e.key)) + } +} + +impl<'a> Ord for MergeEntry<'a> { + fn cmp(&self, other: &Self) -> Ordering { + other.e.key.cmp(&self.e.key) + } +} + +struct MergeIter<'a, S: Source> { + sources: &'a [S], + heap: BinaryHeap>, + last_key: Vec, +} + +impl<'a, S: Source> Iterator for MergeIter<'a, S> { + type Item = Entry; + + fn next(&mut self) -> Option { + let cur; + { + let mut next = self.heap.peek_mut()?; + cur = next.e.clone(); + if let Some(e) = next.it.next() { + next.e = e; + self.last_key.clear(); + self.last_key.extend(next.e.key.as_slice()); + return Some(cur); + } + } + self.heap.pop(); + Some(cur) + } +} + +impl<'a, S: Source> Iter for MergeIter<'a, S> { + fn seek(&mut self, key: &[u8]) { + if key > self.last_key.as_slice() { + loop { + match self.heap.peek_mut() { + None => return, + Some(mut head) => { + if head.e.key.as_slice() >= key { + self.last_key.clear(); + self.last_key.extend_from_slice(head.e.key.as_slice()); + return; + } + head.it.seek(key); + if let Some(e) = head.it.next() { + head.e = e; + continue; + } + } + } + self.heap.pop(); + } + } + self.heap = BinaryHeap::from_iter(self.sources.iter().filter_map(|s| { + let mut it = s.iter(); + it.seek(key); + Some(MergeEntry { + e: it.next()?, + it: Box::new(it), + }) + })); + self.last_key.clear(); + self.last_key.extend_from_slice(key); + } +} + +impl<'a, S: Source> Source for Merger<'a, S> { + fn iter(&self) -> impl Iter { + MergeIter { + last_key: Vec::new(), + sources: self.sources.as_slice(), + heap: BinaryHeap::from_iter(self.sources.as_slice().iter().filter_map(|s| { + let mut it = s.iter(); + Some(MergeEntry { + e: it.next()?, + it: Box::new(it), + }) + })), + } + } +} + +#[cfg(test)] +mod test { + use super::Merger; + use crate::source::test::TestSource; + use crate::{Entry, Source}; + + fn tnum(m: u8) -> Vec { + Vec::from_iter((1u8..255).into_iter().filter(|i| i % m == 0)) + } + + fn test_source(m: u8) -> TestSource { + TestSource(Vec::from_iter( + tnum(m).into_iter().map(|n| Entry::new(vec![n], vec![0])), + )) + } + + #[test] + fn test_merge() { + let range = 1..8; + let s = Merger::from(range.clone().into_iter().map(test_source)); + let mut v = Vec::::new(); + for i in range { + v.extend(tnum(i)) + } + v.sort(); + let v2 = Vec::from_iter(s.iter().map(|e| e.key[0])); + assert_eq!(v2, v); + } + + #[test] + fn test_binheap() { + use std::collections::BinaryHeap; + + let v: Vec = vec![1, 8, 2, 9, 4, 7, 3]; + let vs = v.as_slice(); + let h = BinaryHeap::from_iter(vs.into_iter().map(|p| *p)); + assert_ne!(h.into_vec(), v); + } +} diff --git a/src/seekable.rs b/src/seekable.rs deleted file mode 100644 index ffa8161..0000000 --- a/src/seekable.rs +++ /dev/null @@ -1,77 +0,0 @@ -mod coalesce; -mod filter_map; -mod merge; -mod vec; -use coalesce::Coalesce; -use filter_map::FilterMapValue; -use merge::Merger; -pub use vec::SeekableVec; - -pub trait Seekable: Sized { - type Key; - type Value; - - fn next(&mut self) -> Option<(Self::Key, Self::Value)>; - fn seek(&mut self, key: &Self::Key); - - fn filter_mapv(self, func: F) -> FilterMapValue - where - F: FnMut(&Self::Key, Self::Value, &mut Self) -> Option, - { - FilterMapValue { next: self, func } - } - - fn merge(iter: L) -> Merger - where - L: Iterator, - Self::Key: Ord, - { - merge::merge(iter) - } - - fn coalesce(self, cf: F) -> Coalesce - where - F: FnMut(&Self::Key, Self::Value, Self::Value) -> Self::Value, - Self::Key: PartialEq, - { - coalesce::coalesce(self, cf) - } -} - -#[derive(Debug)] -pub struct Iter(T); - -impl Iterator for Iter -where - T: Seekable, -{ - type Item = (T::Key, T::Value); - - fn next(&mut self) -> Option { - self.0.next() - } -} - -#[cfg(test)] -mod test { - use super::{Iter, Seekable}; - - struct Empty; - impl IntoIterator for Empty { - type Item = ((), ()); - type IntoIter = Iter; - fn into_iter(self) -> Iter { - Iter(self) - } - } - - impl Seekable for Empty { - type Value = (); - type Key = (); - - fn next(&mut self) -> Option<((), ())> { - None - } - fn seek(&mut self, _key: &Self::Key) {} - } -} diff --git a/src/seekable/coalesce.rs b/src/seekable/coalesce.rs deleted file mode 100644 index 55c006d..0000000 --- a/src/seekable/coalesce.rs +++ /dev/null @@ -1,90 +0,0 @@ -use crate::seekable::{Iter, Seekable}; -use std::cell::RefCell; - -pub struct Coalesce -where - S: Seekable, - F: FnMut(&S::Key, S::Value, S::Value) -> S::Value, -{ - cur_item: RefCell>, - rest: S, - cfunc: F, -} - -pub fn coalesce(seekable: S, cf: F) -> Coalesce -where - S: Seekable, - F: FnMut(&S::Key, S::Value, S::Value) -> S::Value, -{ - Coalesce { - cur_item: RefCell::new(None), - rest: seekable, - cfunc: cf, - } -} - -impl IntoIterator for Coalesce -where - S: Seekable, - S::Key: PartialEq, - F: FnMut(&S::Key, S::Value, S::Value) -> S::Value, -{ - type Item = (S::Key, S::Value); - type IntoIter = Iter; - fn into_iter(self) -> Iter { - Iter(self) - } -} - -impl Seekable for Coalesce -where - S: Seekable, - S::Key: PartialEq, - F: FnMut(&S::Key, S::Value, S::Value) -> S::Value, -{ - type Key = S::Key; - type Value = S::Value; - - fn next(&mut self) -> Option<(Self::Key, Self::Value)> { - if self.cur_item.borrow().is_none() { - let next = self.rest.next()?; - self.cur_item.replace(Some(next)); - } - while let Some((k, v)) = self.rest.next() { - if let Some((cur_k, cur_v)) = self.cur_item.replace(None) { - if k != cur_k { - self.cur_item.replace(Some((k, v))); - return Some((cur_k, cur_v)); - } - self.cur_item - .replace(Some((k, ((self.cfunc)(&cur_k, cur_v, v))))); - } - } - self.cur_item.replace(None) - } - - fn seek(&mut self, key: &Self::Key) { - self.cur_item.replace(None); - self.rest.seek(key); - } -} - -#[cfg(test)] -mod test { - use crate::seekable::SeekableVec; - use crate::Seekable; - use std::cmp::Ordering; - - #[test] - fn test_coalesce() { - let v = vec![(1, 2), (1, 3), (2, 1), (2, 4)]; - let vc = vec![(1, 2 + 3), (2, 1 + 4)]; - let v: SeekableVec = SeekableVec::from(v.clone()); - assert_eq!( - v.coalesce(|_k, v1, v2| v1 + v2) - .into_iter() - .cmp(vc.into_iter()), - Ordering::Equal - ) - } -} diff --git a/src/seekable/filter_map.rs b/src/seekable/filter_map.rs deleted file mode 100644 index 586868e..0000000 --- a/src/seekable/filter_map.rs +++ /dev/null @@ -1,143 +0,0 @@ -use crate::seekable::{Iter, Seekable}; - -pub struct FilterMapValue -where - S: Seekable, - F: FnMut(&S::Key, S::Value, &mut S) -> Option, -{ - pub(crate) next: S, - pub(crate) func: F, -} - -impl IntoIterator for FilterMapValue -where - S: Seekable, - F: FnMut(&S::Key, S::Value, &mut S) -> Option, -{ - type Item = (S::Key, V); - type IntoIter = Iter; - fn into_iter(self) -> Iter { - Iter(self) - } -} - -impl Seekable for FilterMapValue -where - S: Seekable, - F: FnMut(&S::Key, S::Value, &mut S) -> Option, -{ - type Key = S::Key; - type Value = V; - - fn next(&mut self) -> Option<(S::Key, V)> { - loop { - match self.next.next() { - None => return None, - Some(v) => { - if let Some(i) = (self.func)(&v.0, v.1, &mut self.next) { - return Some((v.0, i)); - } - } - } - } - } - - fn seek(&mut self, key: &S::Key) { - self.next.seek(key) - } -} - -pub struct FilterMapKey -where - S: Seekable, - F: FnMut(&S::Key, &S::Value, &mut S) -> Option, - FS: FnMut(&K, &mut S), -{ - pub(crate) next: S, - pub(crate) func: F, - pub(crate) seekfunc: FS, -} - -impl IntoIterator for FilterMapKey -where - S: Seekable, - F: FnMut(&S::Key, &S::Value, &mut S) -> Option, - FS: FnMut(&K, &mut S), -{ - type Item = (K, S::Value); - type IntoIter = Iter; - fn into_iter(self) -> Self::IntoIter { - Iter(self) - } -} - -impl Seekable for FilterMapKey -where - S: Seekable, - F: FnMut(&S::Key, &S::Value, &mut S) -> Option, - FS: FnMut(&K, &mut S), -{ - type Key = K; - type Value = S::Value; - - fn next(&mut self) -> Option<(Self::Key, Self::Value)> { - loop { - match self.next.next() { - None => return None, - Some((k, v)) => { - if let Some(newk) = (self.func)(&k, &v, &mut self.next) { - return Some((newk, v)); - } - } - } - } - } - fn seek(&mut self, key: &Self::Key) { - (self.seekfunc)(key, &mut self.next); - } -} - -#[cfg(test)] -mod test { - use crate::seekable::SeekableVec; - use crate::Seekable; - use std::cmp::Ordering; - - #[test] - fn test_map() { - let mut v = vec![3i32, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7]; - let sv = SeekableVec::from(v.clone().into_iter().collect::>()); - v.sort(); - assert_eq!( - sv.filter_mapv(|_k, _v, _s| Some("hello")) - .into_iter() - .cmp(v.into_iter().map(|i| (i, "hello"))), - Ordering::Equal - ); - } - - #[test] - fn test_map_filter_seek() { - let v = vec![3i32, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7] - .into_iter() - .map(|i| (i, "foo")) - .collect::>(); - let mut sv = SeekableVec::from(v.clone()).filter_mapv(|k, _v, s| { - if k % 5 == 0 { - return None; - } - if *k == 7 { - s.seek(&8); - return None; - } - Some("bar") - }); - sv.seek(&3); - assert_eq!(sv.next(), Some((3, "bar"))); - assert_eq!(sv.next(), Some((3, "bar"))); - - sv.seek(&5); - assert_eq!(sv.next(), Some((6, "bar"))); - assert_eq!(sv.next(), Some((8, "bar"))) - } -} diff --git a/src/seekable/merge.rs b/src/seekable/merge.rs deleted file mode 100644 index adbcf14..0000000 --- a/src/seekable/merge.rs +++ /dev/null @@ -1,224 +0,0 @@ -use crate::seekable::{Iter, Seekable}; -use std::cell::RefCell; -use std::cmp::Ordering; -use std::collections::BinaryHeap; - -pub struct Merger -where - S: Seekable, - S::Key: Ord, -{ - active: BinaryHeap>, - ended: Vec, -} - -struct MergerEnt -where - S::Key: Ord, -{ - cur_item: RefCell<(S::Key, S::Value)>, - rest: S, -} - -impl Eq for MergerEnt where S::Key: Ord {} -impl PartialEq for MergerEnt -where - S::Key: Ord, -{ - fn eq(&self, other: &Self) -> bool { - let sent = self.cur_item.borrow(); - let oent = other.cur_item.borrow(); - sent.0.eq(&oent.0) - } -} - -// Because std::collections::BinaryHeap implements a max -// heap and we need a min-heap, we reverse the sense of Ord -// for MergerEnt vs. S::Key. We do this instead of using -// std::cmp::Reverse to avoid the additional packing/unpacking -// boilerplate. -impl PartialOrd for MergerEnt -where - S::Key: Ord, -{ - fn partial_cmp(&self, other: &Self) -> Option { - Some(self.cmp(other)) - } -} - -impl Ord for MergerEnt -where - S::Key: Ord, -{ - fn cmp(&self, other: &Self) -> Ordering { - let sent = self.cur_item.borrow(); - let oent = other.cur_item.borrow(); - oent.0.cmp(&sent.0) - } -} - -impl MergerEnt -where - S::Key: Ord, -{ - fn new(mut source: S) -> Option> { - Some(MergerEnt { - cur_item: RefCell::new(source.next()?), - rest: source, - }) - } - - fn replace(&mut self, v: (S::Key, S::Value)) -> (S::Key, S::Value) { - self.cur_item.replace(v) - } -} - -pub fn merge(sources: L) -> Merger -where - L: Iterator, - S: Seekable, - S::Key: Ord, -{ - Merger { - active: BinaryHeap::from( - sources - .into_iter() - .filter_map(|i| MergerEnt::new(i)) - .collect::>>(), - ), - ended: Vec::new(), - } -} - -impl IntoIterator for Merger -where - S::Key: Ord, -{ - type Item = (S::Key, S::Value); - type IntoIter = Iter; - fn into_iter(self) -> Self::IntoIter { - Iter(self) - } -} - -fn heap_reset(m: &mut Merger, key: &S::Key) -where - S::Key: Ord, -{ - let mut active = Vec::>::new(); - let mut ended = Vec::::new(); - while let Some(e) = m.active.pop() { - m.ended.push(e.rest); - } - while let Some(mut s) = m.ended.pop() { - s.seek(key); - if let Some(next_item) = s.next() { - active.push(MergerEnt { - cur_item: RefCell::new(next_item), - rest: s, - }); - } else { - ended.push(s) - } - } - - m.ended = ended; - m.active = BinaryHeap::from(active); -} - -// forward seek within the heap -fn heap_seek(m: &mut Merger, key: &S::Key) -> Option<()> -where - S::Key: Ord, -{ - loop { - let mut head = m.active.peek_mut()?; - if head.cur_item.borrow().0 >= *key { - break; - } - head.rest.seek(key); - if let Some(next) = head.rest.next() { - head.replace(next); - continue; - } - drop(head); // release heap for modification - let head = m.active.pop()?; - m.ended.push(head.rest); - } - None -} - -impl Seekable for Merger -where - S::Key: Ord, -{ - type Key = S::Key; - type Value = S::Value; - - fn next(&mut self) -> Option<(Self::Key, Self::Value)> { - let mut head = self.active.peek_mut()?; - if let Some(next) = head.rest.next() { - return Some(head.replace(next)); - } - drop(head); // release heap for mutation below - let head = self.active.pop()?; - self.ended.push(head.rest); - Some(head.cur_item.into_inner()) - } - - fn seek(&mut self, key: &Self::Key) { - /* seek forward only */ - let head = self.active.peek_mut(); - if head.is_none() { - return; - } - if head.unwrap().cur_item.borrow().0 > *key { - heap_reset(self, key); - return; - } - heap_seek(self, key); - } -} - -#[cfg(test)] -mod test { - use crate::seekable::SeekableVec; - use crate::Seekable; - use std::cmp::Ordering; - - #[test] - fn test_seekablevec() { - let mut v = vec![3, 1, 4, 1, 5, 9]; - let mut sv = SeekableVec::from(v.clone()); - v.sort(); - sv.seek(&3); - assert_eq!( - sv.into_iter() - .map(|e| e.0) - .cmp(v.into_iter().filter(|i| *i >= 3)), - Ordering::Equal - ); - } - - #[test] - fn test_merge_sv() { - let vpi = vec![3, 1, 4, 1, 5, 9]; - let mut ve = vec![2, 7, 1, 8, 2, 8]; - let mut mv = Seekable::merge( - vec![ - SeekableVec::from(vpi.clone()), - SeekableVec::from(ve.clone()), - ] - .into_iter(), - ); - mv.seek(&5); - ve.extend(vpi); - ve.sort(); - assert_eq!( - mv.into_iter() - .map(|e| e.0) - .cmp(ve.into_iter().filter(|i| *i >= 5)), - Ordering::Equal - ); - } -} diff --git a/src/seekable/vec.rs b/src/seekable/vec.rs deleted file mode 100644 index 34409f8..0000000 --- a/src/seekable/vec.rs +++ /dev/null @@ -1,51 +0,0 @@ -use crate::seekable::Iter; -use crate::Seekable; - -#[derive(Debug)] -pub struct SeekableVec { - off: usize, - v: Vec<(K, V)>, -} -impl IntoIterator for SeekableVec { - type Item = (K, V); - type IntoIter = Iter; - fn into_iter(self) -> Iter { - Iter(self) - } -} -impl Seekable for SeekableVec { - type Key = K; - type Value = V; - fn next(&mut self) -> Option<(K, V)> { - if self.off >= self.v.len() { - return None; - } - let v = self.v[self.off].clone(); - self.off += 1; - Some(v) - } - fn seek(&mut self, key: &K) { - self.off = 0; - while self.off < self.v.len() { - if self.v[self.off].0 >= *key { - break; - } - self.off += 1; - } - } -} -impl From> for SeekableVec { - fn from(vec: Vec<(K, V)>) -> SeekableVec { - let mut sv = SeekableVec { off: 0, v: vec }; - sv.v.sort(); - sv - } -} - -impl From> for SeekableVec { - fn from(vec: Vec) -> SeekableVec { - let mut pv = vec.into_iter().map(|k| (k, ())).collect::>(); - pv.sort(); - SeekableVec { off: 0, v: pv } - } -} diff --git a/src/source.rs b/src/source.rs new file mode 100644 index 0000000..42eee8f --- /dev/null +++ b/src/source.rs @@ -0,0 +1,159 @@ +use crate::Entry; +use std::iter::Iterator; + +pub trait Iter: Iterator { + fn seek(&mut self, key: &[u8]); +} + +pub trait Source { + fn iter(&self) -> impl Iter; + + fn get(&self, key: &[u8]) -> impl Iter { + let mut res = RangeIter { + iter: self.iter(), + end: Vec::from(key), + }; + res.seek(key); + res + } + + fn get_prefix(&self, prefix: &[u8]) -> impl Iter { + let mut res = PrefixIter { + iter: self.iter(), + prefix: Vec::from(prefix), + }; + res.seek(prefix); + res + } + + fn get_range(&self, start: &[u8], end: &[u8]) -> impl Iter { + let mut res = RangeIter { + iter: self.iter(), + end: Vec::from(end), + }; + res.seek(start); + res + } +} + +struct PrefixIter { + iter: I, + prefix: Vec, +} + +impl Iterator for PrefixIter { + type Item = Entry; + fn next(&mut self) -> Option { + let item = self.iter.next()?; + if item.key.starts_with(self.prefix.as_slice()) { + Some(item) + } else { + None + } + } +} +impl Iter for PrefixIter { + fn seek(&mut self, key: &[u8]) { + self.iter.seek(key); + } +} + +struct RangeIter { + iter: I, + end: Vec, +} + +impl Iterator for RangeIter { + type Item = Entry; + fn next(&mut self) -> Option { + let item = self.iter.next()?; + if item.key.as_slice() <= self.end.as_slice() { + Some(item) + } else { + None + } + } +} +impl Iter for RangeIter { + fn seek(&mut self, key: &[u8]) { + self.iter.seek(key); + } +} + +#[cfg(test)] +pub mod test { + use super::{Entry, Iter, Source}; + + pub struct TestSource(pub Vec); + + struct TestIter<'a> { + source: &'a TestSource, + off: usize, + } + + impl<'a> Iterator for TestIter<'a> { + type Item = Entry; + + fn next(&mut self) -> Option { + let off = self.off; + if off >= self.source.0.len() { + return None; + } + let item = &self.source.0[off]; + self.off += 1; + Some(item.clone()) + } + } + + impl<'a> Iter for TestIter<'a> { + fn seek(&mut self, key: &[u8]) { + self.off = 0; + while self.off < self.source.0.len() && self.source.0[self.off].key.as_slice() < key { + self.off += 1; + } + } + } + + impl Source for TestSource { + fn iter(&self) -> impl Iter { + TestIter { + source: self, + off: 0, + } + } + } + + fn test_source() -> TestSource { + TestSource(vec![ + Entry::new(vec![0, 0, 0, 0], vec![0]), + Entry::new(vec![0, 0, 0, 1], vec![1]), + Entry::new(vec![0, 0, 1, 0], vec![2]), + Entry::new(vec![0, 1, 0, 0], vec![3]), + Entry::new(vec![1, 0, 0, 0], vec![4]), + ]) + } + + #[test] + fn test_source_iter() { + let s = test_source(); + assert_eq!( + Vec::from_iter(s.iter().map(|e| e.value[0])), + vec![0, 1, 2, 3, 4] + ); + assert_eq!( + Vec::from_iter(s.get(vec![0, 0, 1, 0].as_slice()).map(|e| e.value[0])), + vec![2] + ); + assert_eq!( + Vec::from_iter(s.get_prefix(vec![0, 0].as_slice()).map(|e| e.value[0])), + vec![0, 1, 2] + ); + assert_eq!( + Vec::from_iter( + s.get_range(vec![0, 0, 0, 1].as_slice(), vec![0, 1, 0, 0].as_slice()) + .map(|e| e.value[0]) + ), + vec![1, 2, 3] + ); + } +} -- 2.50.1