sparse_vector/wand/
cursor.rs

1//! Cursors: forward-only readers over a sorted posting list.
2
3use super::{Posting, RecordId, Weight};
4
5/// A forward-only reader over one posting list, sorted by record id.
6///
7/// A cursor is always positioned either *on* an element (the current one,
8/// returned by [`peek`](Self::peek)) or past the end. It only ever moves
9/// forward: [`seek`](Self::seek) with a target at or below the current id
10/// is a no-op that returns the current element, and moving backwards is
11/// never required by the search loop.
12///
13/// Implementations back the cursor with any storage — a `Vec` in RAM, an
14/// mmap'd slice, a decoded block — as long as they honour the ceiling
15/// invariant: [`upper_bound`](Self::upper_bound) is at least the weight of
16/// every element from the current position to the end of the list.
17pub trait PostingCursor {
18    /// The current element, or `None` once the cursor is past the end.
19    fn peek(&self) -> Option<Posting>;
20
21    /// Move to the next element (no-op past the end).
22    fn advance(&mut self);
23
24    /// Move forward to the first element whose id is `>= target` and return
25    /// it. Returns `None` when no such element exists; the cursor is then
26    /// past the end. Never moves backwards.
27    fn seek(&mut self, target: RecordId) -> Option<Posting>;
28
29    /// Number of elements not yet consumed, the current one included.
30    fn remaining(&self) -> usize;
31
32    /// Id of the last element of the whole list (regardless of position);
33    /// `None` for an empty list.
34    fn last_id(&self) -> Option<RecordId>;
35
36    /// Move past the end.
37    fn exhaust(&mut self);
38
39    /// An upper bound on the weights of the elements not yet consumed, the
40    /// current one included. `f32::NEG_INFINITY` once past the end.
41    fn upper_bound(&self) -> Weight {
42        self.peek().map_or(Weight::NEG_INFINITY, |p| p.tail_max)
43    }
44
45    /// A lower bound on the weights of the elements not yet consumed. The
46    /// default is unbounded, which is always correct; storages that track a
47    /// suffix minimum can tighten it so negative query weights prune too.
48    fn lower_bound(&self) -> Weight {
49        Weight::NEG_INFINITY
50    }
51
52    /// Consume every element with id `<= hi`, handing each `(id, weight)` to
53    /// `visit` in id order. Leaves the cursor on the first element above
54    /// `hi` (or past the end).
55    fn drain_through(&mut self, hi: RecordId, mut visit: impl FnMut(RecordId, Weight)) {
56        while let Some(p) = self.peek() {
57            if p.id > hi {
58                break;
59            }
60            visit(p.id, p.weight);
61            self.advance();
62        }
63    }
64
65    /// True once the cursor is past the end.
66    fn is_exhausted(&self) -> bool {
67        self.peek().is_none()
68    }
69}
70
71/// Cursor over a slice of [`Posting`]s sorted by id.
72#[derive(Clone, Debug)]
73pub struct SliceCursor<'a> {
74    items: &'a [Posting],
75    pos: usize,
76}
77
78impl<'a> SliceCursor<'a> {
79    /// Cursor at the start of `items`. The slice must be sorted by id with
80    /// no duplicates and satisfy the ceiling invariant.
81    pub fn new(items: &'a [Posting]) -> Self {
82        debug_assert!(items.windows(2).all(|w| w[0].id < w[1].id));
83        Self { items, pos: 0 }
84    }
85
86    /// Index of the current element within the slice.
87    pub fn position(&self) -> usize {
88        self.pos
89    }
90}
91
92impl PostingCursor for SliceCursor<'_> {
93    #[inline]
94    fn peek(&self) -> Option<Posting> {
95        self.items.get(self.pos).copied()
96    }
97
98    #[inline]
99    fn advance(&mut self) {
100        if self.pos < self.items.len() {
101            self.pos += 1;
102        }
103    }
104
105    fn seek(&mut self, target: RecordId) -> Option<Posting> {
106        let rest = &self.items[self.pos.min(self.items.len())..];
107        // First index in `rest` whose id is >= target.
108        let step = rest.partition_point(|p| p.id < target);
109        self.pos += step;
110        self.peek()
111    }
112
113    #[inline]
114    fn remaining(&self) -> usize {
115        self.items.len().saturating_sub(self.pos)
116    }
117
118    #[inline]
119    fn last_id(&self) -> Option<RecordId> {
120        self.items.last().map(|p| p.id)
121    }
122
123    fn exhaust(&mut self) {
124        self.pos = self.items.len();
125    }
126
127    fn drain_through(&mut self, hi: RecordId, mut visit: impl FnMut(RecordId, Weight)) {
128        let rest = &self.items[self.pos.min(self.items.len())..];
129        let mut taken = 0;
130        for p in rest {
131            if p.id > hi {
132                break;
133            }
134            visit(p.id, p.weight);
135            taken += 1;
136        }
137        self.pos += taken;
138    }
139}
sparse_vector/wand/cursor.rs

sparse_vector/wand/
cursor.rs
