use crate::{key::Key, map_index::Dir};
use std::ops::Bound;
#[derive(Clone)]
pub struct SegRange<K: Key> {
pub(crate) start: Bound<K>,
pub(crate) end: Bound<K>,
pub(crate) dir: Dir,
pub(crate) since_ms: Option<u64>,
pub(crate) pruning_prefix: Vec<u8>,
pub(crate) empty: bool,
}
impl<K: Key> SegRange<K> {
pub fn all() -> Self {
Self {
start: Bound::Unbounded,
end: Bound::Unbounded,
dir: Dir::Asc,
since_ms: None,
pruning_prefix: Vec::new(),
empty: false,
}
}
pub fn prefix(prefix: &[u8]) -> Self {
let mut query = Self::all();
if prefix.len() > K::zeroed().as_bytes().len() {
query.empty = true;
return query;
}
if prefix.is_empty() {
return query;
}
let mut start = K::zeroed();
start.as_bytes_mut()[..prefix.len()].copy_from_slice(prefix);
query.start = Bound::Included(start);
query.end = crate::scope::key_math::prefix_to_end_bound(prefix);
query.pruning_prefix = prefix.to_vec();
query
}
pub fn range(start: Bound<&K>, end: Bound<&K>) -> Self {
let mut query = Self::all();
query.start = start.map(|k| *k);
query.end = end.map(|k| *k);
if let (Some(a), Some(b)) = (bound_key(&query.start), bound_key(&query.end)) {
query.pruning_prefix = a
.as_bytes()
.iter()
.zip(b.as_bytes())
.take_while(|(a, b)| a == b)
.map(|(a, _)| *a)
.collect();
}
query.normalize();
query
}
pub fn rev(mut self) -> Self {
self.dir = self.dir.flip();
self
}
pub fn written_since(mut self, ms: u64) -> Self {
self.since_ms = Some(ms);
self
}
pub(crate) fn after(mut self, cursor: Option<&K>) -> Self {
if let Some(cursor) = cursor {
match self.dir {
Dir::Asc => {
if bound_key(&self.start).is_none_or(|k| k.as_bytes() <= cursor.as_bytes()) {
self.start = Bound::Excluded(*cursor);
}
}
Dir::Desc => {
if bound_key(&self.end).is_none_or(|k| k.as_bytes() >= cursor.as_bytes()) {
self.end = Bound::Excluded(*cursor);
}
}
}
}
self.normalize();
self
}
fn normalize(&mut self) {
if let (Some(a), Some(b)) = (bound_key(&self.start), bound_key(&self.end)) {
self.empty |= a.as_bytes() > b.as_bytes()
|| (a.as_bytes() == b.as_bytes()
&& (!matches!(self.start, Bound::Included(_))
|| !matches!(self.end, Bound::Included(_))));
}
}
pub(crate) fn contains(&self, key: &[u8]) -> bool {
!self.empty && lower_allows(&self.start, key) && upper_allows(&self.end, key)
}
pub(crate) fn overlaps(&self, min: &[u8], max: &[u8]) -> bool {
!self.empty && lower_allows(&self.start, max) && upper_allows(&self.end, min)
}
}
pub(crate) fn bound_key<K>(b: &Bound<K>) -> Option<&K> {
match b {
Bound::Included(k) | Bound::Excluded(k) => Some(k),
Bound::Unbounded => None,
}
}
fn lower_allows<K: Key>(b: &Bound<K>, k: &[u8]) -> bool {
match b {
Bound::Included(v) => k >= v.as_bytes(),
Bound::Excluded(v) => k > v.as_bytes(),
Bound::Unbounded => true,
}
}
fn upper_allows<K: Key>(b: &Bound<K>, k: &[u8]) -> bool {
match b {
Bound::Included(v) => k <= v.as_bytes(),
Bound::Excluded(v) => k < v.as_bytes(),
Bound::Unbounded => true,
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::seg::testkit::{TestKey, ordered_key};
#[test]
fn empty_inverted_ff_and_cursor_bounds() {
assert!(SegRange::<TestKey>::prefix(&[0; 33]).empty);
assert!(SegRange::<TestKey>::prefix(&[]).contains(&ordered_key(1)));
assert!(SegRange::<TestKey>::prefix(&[255]).contains(&[255; 32]));
assert!(
SegRange::range(
Bound::Included(&ordered_key(2)),
Bound::Included(&ordered_key(1))
)
.empty
);
let query = SegRange::range(
Bound::Included(&ordered_key(1)),
Bound::Included(&ordered_key(3)),
)
.rev()
.written_since(7)
.after(Some(&ordered_key(2)));
assert!(query.contains(&ordered_key(1)));
assert!(!query.contains(&ordered_key(2)));
assert_eq!(query.since_ms, Some(7));
assert_eq!(query.dir, Dir::Desc);
assert!(query.after(Some(&ordered_key(0))).empty);
}
}