use super::{ByteSlice, Bytes, Map};
use core::{alloc::Allocator, iter::FusedIterator, ops::Bound};
pub struct Range<'a, const K: usize, const V: usize, A: Allocator + Clone, P: Allocator + Clone> {
map: &'a Map<K, V, A, P>,
front: u64,
back: u64,
}
pub struct Entry<'a, const K: usize, const V: usize, A: Allocator + Clone, P: Allocator + Clone> {
map: &'a Map<K, V, A, P>,
id: u64,
}
impl<'a, const K: usize, const V: usize, A: Allocator + Clone, P: Allocator + Clone>
Entry<'a, K, V, A, P>
{
#[must_use]
pub fn key(&self) -> ByteSlice<'a> {
ByteSlice(self.map.key(self.id))
}
#[must_use]
pub fn value_len(&self) -> usize {
self.map.node(self.id).value.length as usize
}
#[must_use]
pub fn value(&self) -> ByteSlice<'a> {
ByteSlice(self.map.value(self.id))
}
}
pub struct Entries<'a, const K: usize, const V: usize, A: Allocator + Clone, P: Allocator + Clone> {
range: Range<'a, K, V, A, P>,
}
impl<'a, const K: usize, const V: usize, A: Allocator + Clone, P: Allocator + Clone>
Range<'a, K, V, A, P>
{
#[must_use]
pub fn entries(self) -> Entries<'a, K, V, A, P> {
Entries { range: self }
}
fn advance(&mut self, forward: bool) -> Option<Entry<'a, K, V, A, P>> {
let id = if forward { self.front } else { self.back };
if id == 0 {
return None;
}
if self.front == self.back {
self.front = 0;
self.back = 0;
} else if forward {
self.front = seek(self.map, Bound::Excluded(self.map.key(id)), true);
} else {
self.back = seek(self.map, Bound::Excluded(self.map.key(id)), false);
}
Some(Entry { map: self.map, id })
}
pub(super) fn new(map: &'a Map<K, V, A, P>, lower: Bound<&[u8]>, upper: Bound<&[u8]>) -> Self {
let front = seek(map, lower, true);
let back = seek(map, upper, false);
let mut range = Self { map, front, back };
if front == 0 || back == 0 || map.key(front) > map.key(back) {
range.front = 0;
range.back = 0;
}
range
}
pub(super) fn prefix(map: &'a Map<K, V, A, P>, prefix: &[u8]) -> Self {
let Ok(mut upper) = Bytes::<K>::new(prefix) else {
return Self {
map,
front: 0,
back: 0,
};
};
for index in (0..prefix.len()).rev() {
if upper.data[index] != 255 {
upper.data[index] += 1;
return Self::new(
map,
Bound::Included(prefix),
Bound::Excluded(&upper.data[..=index]),
);
}
}
Self::new(map, Bound::Included(prefix), Bound::Unbounded)
}
}
fn seek<const K: usize, const V: usize, A: Allocator + Clone, P: Allocator + Clone>(
map: &Map<K, V, A, P>,
bound: Bound<&[u8]>,
forward: bool,
) -> u64 {
let mut id = map.image.root;
let mut candidate = 0;
while id != 0 {
let node = map.node(id);
let qualifies = match bound {
Bound::Unbounded => true,
Bound::Included(key) => {
if forward {
map.key(id) >= key
} else {
map.key(id) <= key
}
}
Bound::Excluded(key) => {
if forward {
map.key(id) > key
} else {
map.key(id) < key
}
}
};
if qualifies {
candidate = id;
id = if forward { node.left } else { node.right };
} else {
id = if forward { node.right } else { node.left };
}
}
candidate
}
impl<'a, const K: usize, const V: usize, A: Allocator + Clone, P: Allocator + Clone> Iterator
for Range<'a, K, V, A, P>
{
type Item = (ByteSlice<'a>, ByteSlice<'a>);
fn next(&mut self) -> Option<Self::Item> {
self.advance(true).map(|entry| (entry.key(), entry.value()))
}
}
impl<const K: usize, const V: usize, A: Allocator + Clone, P: Allocator + Clone> DoubleEndedIterator
for Range<'_, K, V, A, P>
{
fn next_back(&mut self) -> Option<Self::Item> {
self.advance(false)
.map(|entry| (entry.key(), entry.value()))
}
}
impl<const K: usize, const V: usize, A: Allocator + Clone, P: Allocator + Clone> FusedIterator
for Range<'_, K, V, A, P>
{
}
impl<'a, const K: usize, const V: usize, A: Allocator + Clone, P: Allocator + Clone> Iterator
for Entries<'a, K, V, A, P>
{
type Item = Entry<'a, K, V, A, P>;
fn next(&mut self) -> Option<Self::Item> {
self.range.advance(true)
}
}
impl<const K: usize, const V: usize, A: Allocator + Clone, P: Allocator + Clone> DoubleEndedIterator
for Entries<'_, K, V, A, P>
{
fn next_back(&mut self) -> Option<Self::Item> {
self.range.advance(false)
}
}
impl<const K: usize, const V: usize, A: Allocator + Clone, P: Allocator + Clone> FusedIterator
for Entries<'_, K, V, A, P>
{
}