vortex_array/search_sorted/
primitive.rs1use std::cell::RefCell;
5use std::cmp::Ordering;
6use std::marker::PhantomData;
7
8use vortex_error::VortexResult;
9
10use crate::ArrayRef;
11use crate::ExecutionCtx;
12use crate::RepeatedArrayProbe;
13use crate::arrays::Primitive;
14use crate::arrays::primitive::PrimitiveArrayExt;
15use crate::dtype::NativePType;
16use crate::search_sorted::IndexOrd;
17
18pub struct SearchSortedPrimitiveArray<'a, T> {
28 reader: Reader<'a, T>,
29 len: usize,
30 ctx: RefCell<&'a mut ExecutionCtx>,
31 _ptype: PhantomData<T>,
32}
33
34enum Reader<'a, T> {
36 Values(&'a [T]),
39 Probe(RefCell<RepeatedArrayProbe>),
41}
42
43impl<'a, T: NativePType> SearchSortedPrimitiveArray<'a, T> {
44 pub fn new(array: &'a ArrayRef, ctx: &'a mut ExecutionCtx) -> Self {
47 assert_eq!(
48 array.dtype().as_ptype(),
49 T::PTYPE,
50 "Array PType must match primitive type"
51 );
52 Self {
53 reader: Self::reader(array),
54 len: array.len(),
55 ctx: RefCell::new(ctx),
56 _ptype: PhantomData,
57 }
58 }
59
60 fn reader(array: &'a ArrayRef) -> Reader<'a, T> {
65 if !array.dtype().is_nullable()
66 && let Some(primitive) = array.as_opt::<Primitive>()
67 && primitive.buffer_handle().as_host_opt().is_some()
68 && let Some(values) = primitive.data().as_slice::<T>().get(..array.len())
69 {
70 return Reader::Values(values);
71 }
72 Reader::Probe(RefCell::new(array.repeated_probe()))
73 }
74
75 fn typed_value(&self, idx: usize) -> VortexResult<Option<T>> {
79 let probe = match &self.reader {
80 Reader::Values(values) => return Ok(Some(values[idx])),
81 Reader::Probe(probe) => probe,
82 };
83 Ok(probe
84 .borrow_mut()
85 .execute_scalar(idx, &mut self.ctx.borrow_mut())?
86 .as_primitive()
87 .typed_value::<T>())
88 }
89
90 fn value(&self, idx: usize) -> VortexResult<T> {
92 Ok(self.typed_value(idx)?.unwrap_or_else(|| T::zero()))
93 }
94}
95
96impl<T: NativePType> IndexOrd<T> for SearchSortedPrimitiveArray<'_, T> {
97 fn index_cmp(&self, idx: usize, elem: &T) -> VortexResult<Option<Ordering>> {
98 let value = self.value(idx)?;
99 Ok(Some(value.total_compare(*elem)))
100 }
101
102 fn index_len(&self) -> usize {
103 self.len
104 }
105}
106
107impl<T: NativePType> IndexOrd<Option<T>> for SearchSortedPrimitiveArray<'_, T> {
108 fn index_cmp(&self, idx: usize, elem: &Option<T>) -> VortexResult<Option<Ordering>> {
109 let value = self.typed_value(idx)?;
112
113 Ok(match (value, elem.as_ref()) {
114 (Some(l), Some(r)) => Some(l.total_compare(*r)),
115 (Some(_), None) => Some(Ordering::Greater),
116 (None, Some(_)) => Some(Ordering::Less),
117 (None, None) => Some(Ordering::Equal),
118 })
119 }
120
121 fn index_len(&self) -> usize {
122 self.len
123 }
124}
125
126impl<T: NativePType> IndexOrd<usize> for SearchSortedPrimitiveArray<'_, T> {
127 fn index_cmp(&self, idx: usize, elem: &usize) -> VortexResult<Option<Ordering>> {
128 let value = self.value(idx)?;
129
130 let Some(elem_t) = T::from_usize(*elem) else {
131 return Ok(Some(Ordering::Less));
132 };
133
134 Ok(Some(value.total_compare(elem_t)))
135 }
136
137 fn index_len(&self) -> usize {
138 self.len
139 }
140}
141
142#[cfg(test)]
143mod tests {
144 use std::sync::LazyLock;
145
146 use vortex_buffer::buffer;
147 use vortex_error::VortexResult;
148 use vortex_session::VortexSession;
149
150 use super::Reader;
151 use crate::IntoArray;
152 use crate::arrays::PrimitiveArray;
153 use crate::executor::VortexSessionExecute;
154 use crate::search_sorted::SearchResult;
155 use crate::search_sorted::SearchSorted;
156 use crate::search_sorted::SearchSortedPrimitiveArray;
157 use crate::search_sorted::SearchSortedSide;
158 use crate::validity::Validity;
159
160 static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
161
162 #[test]
163 fn search_sorted_reads_canonical_values_directly() -> VortexResult<()> {
164 let mut ctx = SESSION.create_execution_ctx();
165 let array = PrimitiveArray::new(buffer![1i32, 2, 3, 4], Validity::NonNullable).into_array();
166 let searcher = SearchSortedPrimitiveArray::<i32>::new(&array, &mut ctx);
167 assert!(matches!(searcher.reader, Reader::Values(_)));
168 assert_eq!(
169 searcher.search_sorted(&3i32, SearchSortedSide::Left)?,
170 SearchResult::Found(2)
171 );
172 Ok(())
173 }
174
175 #[test]
176 fn search_sorted_nullable_values_respects_validity() -> VortexResult<()> {
177 let mut ctx = SESSION.create_execution_ctx();
178 let array = PrimitiveArray::new(
179 buffer![99i32, 2, 3, 4],
180 Validity::from_iter([false, true, true, true]),
181 )
182 .into_array();
183 let searcher = SearchSortedPrimitiveArray::<i32>::new(&array, &mut ctx);
184 assert_eq!(
185 searcher.search_sorted(&None::<i32>, SearchSortedSide::Left)?,
186 SearchResult::Found(0)
187 );
188 assert_eq!(
189 searcher.search_sorted(&Some(3i32), SearchSortedSide::Left)?,
190 SearchResult::Found(2)
191 );
192 Ok(())
193 }
194
195 #[test]
196 fn search_sorted_optional_value() -> VortexResult<()> {
197 let array = PrimitiveArray::new(buffer![1i32, 2, 3, 4], Validity::AllValid).into_array();
198 let mut ctx = SESSION.create_execution_ctx();
199 let res = SearchSortedPrimitiveArray::<i32>::new(&array, &mut ctx)
200 .search_sorted(&Some(3i32), SearchSortedSide::Left)?;
201 assert_eq!(res, SearchResult::Found(2));
202 Ok(())
203 }
204
205 #[test]
206 fn search_sorted_optional_value_with_nulls() -> VortexResult<()> {
207 let array =
208 PrimitiveArray::from_option_iter([None, None, Some(2i32), Some(3)]).into_array();
209 let mut ctx = SESSION.create_execution_ctx();
210 let searcher = SearchSortedPrimitiveArray::<i32>::new(&array, &mut ctx);
211 assert_eq!(
212 searcher.search_sorted(&Some(2i32), SearchSortedSide::Left)?,
213 SearchResult::Found(2)
214 );
215 assert_eq!(
216 searcher.search_sorted(&None, SearchSortedSide::Right)?,
217 SearchResult::Found(2)
218 );
219 Ok(())
220 }
221}