1use std::sync::Arc;
2
3use super::{ColumnDef, ColumnFilter, GlobalFilterState, SortCmpFn, SortSpec};
4use serde_json::Value;
5
6use super::memo::Memo;
7
8#[derive(Debug, Clone, PartialEq, Default)]
9pub struct FlatRowOrderDeps {
10 pub items_revision: u64,
11 pub data_len: usize,
12 pub sorting: Vec<SortSpec>,
13 pub column_filters: Vec<ColumnFilter>,
14 pub global_filter: GlobalFilterState,
15}
16
17#[derive(Default)]
18pub struct FlatRowOrderCache {
19 memo: Memo<FlatRowOrderDeps, Arc<[usize]>>,
20 columns_signature: u64,
21}
22
23impl FlatRowOrderCache {
24 pub fn row_order<TData>(
25 &mut self,
26 data: &[TData],
27 columns: &[ColumnDef<TData>],
28 deps: FlatRowOrderDeps,
29 ) -> (&Arc<[usize]>, bool) {
30 let signature = columns_signature(columns);
31 if signature != self.columns_signature {
32 self.columns_signature = signature;
33 self.memo.reset();
34 }
35
36 let sorting = deps.sorting.clone();
37 let column_filters = deps.column_filters.clone();
38 let global_filter = deps.global_filter.clone();
39 self.memo.get_or_compute(deps, || {
40 compute_flat_row_order(data, columns, &sorting, &column_filters, global_filter)
41 })
42 }
43}
44
45pub fn compute_flat_row_order<TData>(
46 data: &[TData],
47 columns: &[ColumnDef<TData>],
48 sorting: &[SortSpec],
49 column_filters: &[ColumnFilter],
50 global_filter: GlobalFilterState,
51) -> Arc<[usize]> {
52 let sorters: Vec<(SortCmpFn<TData>, bool)> = sorting
53 .iter()
54 .filter_map(|spec| {
55 let cmp = columns
56 .iter()
57 .find(|c| c.id.as_ref() == spec.column.as_ref())?
58 .sort_cmp
59 .clone()?;
60 Some((cmp, spec.desc))
61 })
62 .collect();
63
64 let resolved_column_filters: Vec<(super::FilterFn<TData>, Value)> = column_filters
65 .iter()
66 .filter_map(|filter| {
67 let filter_fn = columns
68 .iter()
69 .find(|c| c.id.as_ref() == filter.column.as_ref())?
70 .filter_fn
71 .clone()?;
72 Some((filter_fn, filter.value.clone()))
73 })
74 .collect();
75
76 let global_filter_fns: Vec<super::FilterFn<TData>> = if global_filter.is_some() {
77 columns.iter().filter_map(|c| c.filter_fn.clone()).collect()
78 } else {
79 Vec::new()
80 };
81
82 let mut order: Vec<usize> = (0..data.len())
83 .filter(|&i| {
84 let row = &data[i];
85
86 for (filter_fn, value) in &resolved_column_filters {
87 if !filter_fn(row, value) {
88 return false;
89 }
90 }
91
92 let Some(global_value) = global_filter.as_ref() else {
93 return true;
94 };
95 for filter_fn in &global_filter_fns {
96 if filter_fn(row, global_value) {
97 return true;
98 }
99 }
100 false
101 })
102 .collect();
103 if !sorters.is_empty() {
104 order.sort_by(|&a, &b| {
105 let a_row = &data[a];
106 let b_row = &data[b];
107 for (cmp, desc) in &sorters {
108 let mut ord = cmp(a_row, b_row);
109 if *desc {
110 ord = ord.reverse();
111 }
112 if ord != std::cmp::Ordering::Equal {
113 return ord;
114 }
115 }
116 a.cmp(&b)
117 });
118 }
119
120 Arc::from(order.into_boxed_slice())
121}
122
123fn columns_signature<TData>(columns: &[ColumnDef<TData>]) -> u64 {
124 use std::collections::hash_map::DefaultHasher;
125 use std::hash::{Hash, Hasher};
126
127 let mut hasher = DefaultHasher::new();
128 columns.len().hash(&mut hasher);
129 for col in columns {
130 col.id.as_ref().hash(&mut hasher);
131 col.sort_cmp.is_some().hash(&mut hasher);
132 col.filter_fn.is_some().hash(&mut hasher);
133 }
134 hasher.finish()
135}
136
137#[cfg(test)]
138mod tests {
139 use super::compute_flat_row_order;
140 use crate::table::{ColumnDef, SortSpec};
141 use std::cmp::Ordering;
142 use std::sync::Arc;
143
144 #[derive(Debug)]
145 struct Row {
146 score: i32,
147 name: &'static str,
148 }
149
150 fn col<T: 'static>(id: &str, cmp: fn(&T, &T) -> Ordering) -> ColumnDef<T> {
151 ColumnDef::new(id).sort_by(cmp)
152 }
153
154 #[test]
155 fn flat_row_order_is_stable_without_sorting() {
156 let data = [
157 Row {
158 score: 10,
159 name: "b",
160 },
161 Row {
162 score: 9,
163 name: "a",
164 },
165 ];
166
167 let columns = vec![col::<Row>("score", |a, b| a.score.cmp(&b.score))];
168 let order = compute_flat_row_order(&data, &columns, &[], &[], None);
169 assert_eq!(&*order, &[0, 1]);
170 }
171
172 #[test]
173 fn flat_row_order_sorts_by_single_column() {
174 let data = [
175 Row {
176 score: 10,
177 name: "b",
178 },
179 Row {
180 score: 9,
181 name: "a",
182 },
183 ];
184
185 let columns = vec![col::<Row>("score", |a, b| a.score.cmp(&b.score))];
186 let order = compute_flat_row_order(
187 &data,
188 &columns,
189 &[SortSpec {
190 column: "score".into(),
191 desc: false,
192 }],
193 &[],
194 None,
195 );
196 assert_eq!(&*order, &[1, 0]);
197 }
198
199 #[test]
200 fn flat_row_order_sorts_descending() {
201 let data = [
202 Row {
203 score: 10,
204 name: "a",
205 },
206 Row {
207 score: 10,
208 name: "b",
209 },
210 ];
211
212 let columns = vec![col::<Row>("name", |a, b| a.name.cmp(b.name))];
213 let order = compute_flat_row_order(
214 &data,
215 &columns,
216 &[SortSpec {
217 column: "name".into(),
218 desc: true,
219 }],
220 &[],
221 None,
222 );
223 assert_eq!(&*order, &[1, 0]);
224 }
225
226 #[test]
227 fn flat_row_order_uses_index_tiebreaker() {
228 let data = [
229 Row {
230 score: 10,
231 name: "x",
232 },
233 Row {
234 score: 10,
235 name: "x",
236 },
237 Row {
238 score: 10,
239 name: "x",
240 },
241 ];
242
243 let columns = vec![col::<Row>("score", |a, b| a.score.cmp(&b.score))];
244 let order = compute_flat_row_order(
245 &data,
246 &columns,
247 &[SortSpec {
248 column: "score".into(),
249 desc: false,
250 }],
251 &[],
252 None,
253 );
254 assert_eq!(&*order, &[0, 1, 2]);
255 }
256
257 #[test]
258 fn flat_row_order_filters_before_sorting() {
259 #[derive(Debug)]
260 struct Item {
261 value: i32,
262 kind: Arc<str>,
263 }
264
265 let data = [
266 Item {
267 value: 2,
268 kind: "keep".into(),
269 },
270 Item {
271 value: 1,
272 kind: "drop".into(),
273 },
274 Item {
275 value: 3,
276 kind: "keep".into(),
277 },
278 ];
279
280 let columns = vec![
281 ColumnDef::new("value").sort_by(|a: &Item, b: &Item| a.value.cmp(&b.value)),
282 ColumnDef::new("kind").filter_by(|row: &Item, q| row.kind.as_ref() == q),
283 ];
284
285 let order = compute_flat_row_order(
286 &data,
287 &columns,
288 &[SortSpec {
289 column: "value".into(),
290 desc: false,
291 }],
292 &[crate::table::ColumnFilter {
293 column: "kind".into(),
294 value: serde_json::Value::from("keep"),
295 }],
296 None,
297 );
298
299 assert_eq!(&*order, &[0, 2]);
300 }
301}