vortex_scan/
strict_sorted_buffer.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4//! Defines a [`Buffer`] wrapper whose values are known to be strictly sorted.
5
6use std::ops::Deref;
7
8use vortex_buffer::Buffer;
9use vortex_error::VortexResult;
10use vortex_error::vortex_bail;
11
12/// A buffer whose values are known to be strictly sorted in ascending order.
13///
14/// Dereferences to the inner [`Buffer`], which in turn dereferences to a slice.
15#[derive(Clone, Debug)]
16pub struct StrictSortedBuffer<T> {
17    buffer: Buffer<T>,
18}
19
20impl<T> StrictSortedBuffer<T> {
21    /// Create a new buffer without checking that the values are strictly increasing.
22    ///
23    /// # Safety
24    ///
25    /// The values must be strictly increasing. Callers of [`StrictSortedBuffer`] rely on this
26    /// invariant, for example to binary search the buffer.
27    pub unsafe fn new_unchecked(buffer: Buffer<T>) -> Self {
28        Self { buffer }
29    }
30
31    /// Return the sorted buffer.
32    pub fn into_inner(self) -> Buffer<T> {
33        self.buffer
34    }
35}
36
37impl<T: Ord> StrictSortedBuffer<T> {
38    /// Create a new buffer, failing if the values are not strictly increasing.
39    pub fn try_new(buffer: Buffer<T>) -> VortexResult<Self> {
40        for (idx, window) in buffer.windows(2).enumerate() {
41            if window[0] >= window[1] {
42                vortex_bail!(
43                    "buffer values must be strictly increasing at positions {} and {}",
44                    idx,
45                    idx + 1
46                );
47            }
48        }
49        Ok(Self { buffer })
50    }
51}
52
53impl<T> Default for StrictSortedBuffer<T> {
54    fn default() -> Self {
55        Self {
56            buffer: Buffer::default(),
57        }
58    }
59}
60
61impl<T> Deref for StrictSortedBuffer<T> {
62    type Target = Buffer<T>;
63
64    fn deref(&self) -> &Self::Target {
65        &self.buffer
66    }
67}
68
69#[cfg(test)]
70mod tests {
71    use vortex_buffer::Buffer;
72
73    use super::StrictSortedBuffer;
74
75    #[test]
76    fn rejects_unsorted_values() {
77        let err = StrictSortedBuffer::try_new(Buffer::from_iter([3, 1])).unwrap_err();
78        assert!(err.to_string().contains("strictly increasing"));
79    }
80
81    #[test]
82    fn rejects_duplicate_values() {
83        let err = StrictSortedBuffer::try_new(Buffer::from_iter([1, 1])).unwrap_err();
84        assert!(err.to_string().contains("strictly increasing"));
85    }
86}
vortex_scan/strict_sorted_buffer.rs

vortex_scan/
strict_sorted_buffer.rs
