1use crate::{
2 geometry::{
3 rect::RectF,
4 vector::{vec2f, Vector2F},
5 },
6 json::json,
7 sum_tree::{self, Bias, SumTree},
8 DebugContext, Element, ElementBox, ElementRc, Event, EventContext, LayoutContext, PaintContext,
9 RenderContext, SizeConstraint, View,
10};
11use std::{cell::RefCell, ops::Range, rc::Rc};
12
13pub struct List {
14 state: ListState,
15}
16
17#[derive(Clone)]
18pub struct ListState(Rc<RefCell<StateInner>>);
19
20#[derive(Eq, PartialEq)]
21pub enum Orientation {
22 Top,
23 Bottom,
24}
25
26struct StateInner {
27 last_layout_width: Option<f32>,
28 elements: Vec<Option<ElementRc>>,
29 heights: SumTree<ElementHeight>,
30 scroll_position: f32,
31 orientation: Orientation,
32}
33
34#[derive(Clone, Debug)]
35enum ElementHeight {
36 Pending,
37 Ready(f32),
38}
39
40#[derive(Clone, Debug, Default, PartialEq)]
41struct ElementHeightSummary {
42 count: usize,
43 pending_count: usize,
44 height: f32,
45}
46
47#[derive(Clone, Debug, Default)]
48struct Count(usize);
49
50#[derive(Clone, Debug, Default)]
51struct PendingCount(usize);
52
53#[derive(Clone, Debug, Default)]
54struct Height(f32);
55
56impl List {
57 pub fn new<F, I, V>(state: ListState, cx: &RenderContext<V>, build_items: F) -> Self
58 where
59 F: Fn(Range<usize>) -> I,
60 I: IntoIterator<Item = ElementBox>,
61 V: View,
62 {
63 {
64 let state = &mut *state.0.borrow_mut();
65 if cx.refreshing {
66 let elements = (build_items)(0..state.elements.len());
67 state.last_layout_width = None;
68 state.elements.clear();
69 state
70 .elements
71 .extend(elements.into_iter().map(|e| Some(e.into())));
72 state.heights = SumTree::new();
73 state.heights.extend(
74 (0..state.elements.len()).map(|_| ElementHeight::Pending),
75 &(),
76 );
77 } else {
78 let mut cursor = state.heights.cursor::<PendingCount, Count>();
79 cursor.seek(&PendingCount(1), sum_tree::Bias::Left, &());
80
81 while cursor.item().is_some() {
82 let start_ix = cursor.sum_start().0;
83 while cursor.item().map_or(false, |h| h.is_pending()) {
84 cursor.next(&());
85 }
86 let end_ix = cursor.sum_start().0;
87 if end_ix > start_ix {
88 state.elements.splice(
89 start_ix..end_ix,
90 (build_items)(start_ix..end_ix)
91 .into_iter()
92 .map(|e| Some(e.into())),
93 );
94 }
95
96 cursor.seek(&PendingCount(cursor.seek_start().0 + 1), Bias::Left, &());
97 }
98 }
99 }
100
101 Self { state }
102 }
103}
104
105impl Element for List {
106 type LayoutState = Vec<ElementRc>;
107
108 type PaintState = ();
109
110 fn layout(
111 &mut self,
112 constraint: SizeConstraint,
113 cx: &mut LayoutContext,
114 ) -> (Vector2F, Self::LayoutState) {
115 let state = &mut *self.state.0.borrow_mut();
116 let mut item_constraint = constraint;
117 item_constraint.min.set_y(0.);
118 item_constraint.max.set_y(f32::INFINITY);
119
120 let size = constraint.max;
121
122 let visible_top = state.scroll_top(size.y());
123 let visible_bottom = visible_top + size.y();
124
125 if state.last_layout_width == Some(constraint.max.x()) {
126 let mut old_heights = state.heights.cursor::<PendingCount, ElementHeightSummary>();
127 let mut new_heights = old_heights.slice(&PendingCount(1), sum_tree::Bias::Left, &());
128
129 while let Some(height) = old_heights.item() {
130 if height.is_pending() {
131 let element = &mut state.elements[old_heights.sum_start().count];
132 let element_size = element.as_mut().unwrap().layout(item_constraint, cx);
133 new_heights.push(ElementHeight::Ready(element_size.y()), &());
134
135 // Adjust scroll position to keep visible elements stable
136 match state.orientation {
137 Orientation::Top => {
138 if new_heights.summary().height < visible_top {
139 state.scroll_position += element_size.y();
140 }
141 }
142 Orientation::Bottom => {
143 if new_heights.summary().height - element_size.y() > visible_bottom {
144 state.scroll_position += element_size.y();
145 }
146 }
147 }
148
149 old_heights.next(&());
150 } else {
151 new_heights.push_tree(
152 old_heights.slice(
153 &PendingCount(old_heights.sum_start().pending_count + 1),
154 Bias::Left,
155 &(),
156 ),
157 &(),
158 );
159 }
160 }
161
162 drop(old_heights);
163 state.heights = new_heights;
164 } else {
165 state.heights = SumTree::new();
166 for element in &mut state.elements {
167 let element = element.as_mut().unwrap();
168 let size = element.layout(item_constraint, cx);
169 state.heights.push(ElementHeight::Ready(size.y()), &());
170 }
171 state.last_layout_width = Some(constraint.max.x());
172 }
173
174 let visible_elements = state.elements[state.visible_range(size.y())]
175 .iter()
176 .map(|e| e.clone().unwrap())
177 .collect();
178 (size, visible_elements)
179 }
180
181 fn paint(
182 &mut self,
183 bounds: RectF,
184 visible_elements: &mut Self::LayoutState,
185 cx: &mut PaintContext,
186 ) {
187 cx.scene.push_layer(Some(bounds));
188 let state = &mut *self.state.0.borrow_mut();
189 let visible_range = state.visible_range(bounds.height());
190
191 let mut item_top = {
192 let mut cursor = state.heights.cursor::<Count, Height>();
193 cursor.seek(&Count(visible_range.start), Bias::Right, &());
194 cursor.sum_start().0
195 };
196 if state.orientation == Orientation::Bottom
197 && bounds.height() > state.heights.summary().height
198 {
199 item_top += bounds.height() - state.heights.summary().height;
200 }
201 let scroll_top = state.scroll_top(bounds.height());
202
203 for element in visible_elements {
204 let origin = bounds.origin() + vec2f(0., item_top - scroll_top);
205 element.paint(origin, cx);
206 item_top += element.size().y();
207 }
208 cx.scene.pop_layer();
209 }
210
211 fn dispatch_event(
212 &mut self,
213 event: &Event,
214 bounds: RectF,
215 visible_elements: &mut Self::LayoutState,
216 _: &mut (),
217 cx: &mut EventContext,
218 ) -> bool {
219 let mut handled = false;
220
221 let mut state = self.state.0.borrow_mut();
222 for element in visible_elements {
223 handled = element.dispatch_event(event, cx) || handled;
224 }
225
226 match event {
227 Event::ScrollWheel {
228 position,
229 delta,
230 precise,
231 } => {
232 if bounds.contains_point(*position) {
233 if state.scroll(*position, *delta, *precise, bounds.height(), cx) {
234 handled = true;
235 }
236 }
237 }
238 _ => {}
239 }
240
241 handled
242 }
243
244 fn debug(
245 &self,
246 bounds: RectF,
247 visible_elements: &Self::LayoutState,
248 _: &(),
249 cx: &DebugContext,
250 ) -> serde_json::Value {
251 let state = self.state.0.borrow_mut();
252 let visible_range = state.visible_range(bounds.height());
253 let visible_elements = visible_elements
254 .iter()
255 .map(|e| e.debug(cx))
256 .collect::<Vec<_>>();
257 json!({
258 "visible_range": visible_range,
259 "visible_elements": visible_elements,
260 "scroll_position": state.scroll_position,
261 })
262 }
263}
264
265impl ListState {
266 pub fn new(element_count: usize, orientation: Orientation) -> Self {
267 let mut heights = SumTree::new();
268 heights.extend((0..element_count).map(|_| ElementHeight::Pending), &());
269 Self(Rc::new(RefCell::new(StateInner {
270 last_layout_width: None,
271 elements: (0..element_count).map(|_| None).collect(),
272 heights,
273 scroll_position: 0.,
274 orientation,
275 })))
276 }
277
278 pub fn splice(&self, old_range: Range<usize>, count: usize) {
279 let state = &mut *self.0.borrow_mut();
280
281 let mut old_heights = state.heights.cursor::<Count, ()>();
282 let mut new_heights = old_heights.slice(&Count(old_range.start), Bias::Right, &());
283 old_heights.seek_forward(&Count(old_range.end), Bias::Right, &());
284
285 let old_elements = state.elements.splice(old_range, (0..count).map(|_| None));
286 drop(old_elements);
287
288 new_heights.extend((0..count).map(|_| ElementHeight::Pending), &());
289 new_heights.push_tree(old_heights.suffix(&()), &());
290 drop(old_heights);
291 state.heights = new_heights;
292 }
293}
294
295impl StateInner {
296 fn visible_range(&self, height: f32) -> Range<usize> {
297 let mut cursor = self.heights.cursor::<Height, Count>();
298 cursor.seek(&Height(self.scroll_top(height)), Bias::Right, &());
299 let start_ix = cursor.sum_start().0;
300 cursor.seek(&Height(self.scroll_top(height) + height), Bias::Left, &());
301 let end_ix = cursor.sum_start().0;
302 start_ix..self.elements.len().min(end_ix + 1)
303 }
304
305 fn scroll(
306 &mut self,
307 _: Vector2F,
308 delta: Vector2F,
309 precise: bool,
310 height: f32,
311 cx: &mut EventContext,
312 ) -> bool {
313 if !precise {
314 todo!("still need to handle non-precise scroll events from a mouse wheel");
315 }
316
317 let scroll_max = (self.heights.summary().height - height).max(0.);
318 let delta_y = match self.orientation {
319 Orientation::Top => -delta.y(),
320 Orientation::Bottom => delta.y(),
321 };
322 self.scroll_position = (self.scroll_position + delta_y).max(0.).min(scroll_max);
323 cx.notify();
324
325 true
326 }
327
328 fn scroll_top(&self, height: f32) -> f32 {
329 match self.orientation {
330 Orientation::Top => self.scroll_position,
331 Orientation::Bottom => {
332 (self.heights.summary().height - height - self.scroll_position).max(0.)
333 }
334 }
335 }
336}
337
338impl ElementHeight {
339 fn is_pending(&self) -> bool {
340 matches!(self, ElementHeight::Pending)
341 }
342}
343
344impl sum_tree::Item for ElementHeight {
345 type Summary = ElementHeightSummary;
346
347 fn summary(&self) -> Self::Summary {
348 match self {
349 ElementHeight::Pending => ElementHeightSummary {
350 count: 1,
351 pending_count: 1,
352 height: 0.,
353 },
354 ElementHeight::Ready(height) => ElementHeightSummary {
355 count: 1,
356 pending_count: 0,
357 height: *height,
358 },
359 }
360 }
361}
362
363impl sum_tree::Summary for ElementHeightSummary {
364 type Context = ();
365
366 fn add_summary(&mut self, summary: &Self, _: &()) {
367 self.count += summary.count;
368 self.pending_count += summary.pending_count;
369 self.height += summary.height;
370 }
371}
372
373impl<'a> sum_tree::Dimension<'a, ElementHeightSummary> for ElementHeightSummary {
374 fn add_summary(&mut self, summary: &'a ElementHeightSummary, _: &()) {
375 sum_tree::Summary::add_summary(self, summary, &());
376 }
377}
378
379impl<'a> sum_tree::Dimension<'a, ElementHeightSummary> for Count {
380 fn add_summary(&mut self, summary: &'a ElementHeightSummary, _: &()) {
381 self.0 += summary.count;
382 }
383}
384
385impl<'a> sum_tree::SeekDimension<'a, ElementHeightSummary> for Count {
386 fn cmp(&self, other: &Self, _: &()) -> std::cmp::Ordering {
387 self.0.cmp(&other.0)
388 }
389}
390
391impl<'a> sum_tree::Dimension<'a, ElementHeightSummary> for PendingCount {
392 fn add_summary(&mut self, summary: &'a ElementHeightSummary, _: &()) {
393 self.0 += summary.pending_count;
394 }
395}
396
397impl<'a> sum_tree::SeekDimension<'a, ElementHeightSummary> for PendingCount {
398 fn cmp(&self, other: &Self, _: &()) -> std::cmp::Ordering {
399 self.0.cmp(&other.0)
400 }
401}
402
403impl<'a> sum_tree::Dimension<'a, ElementHeightSummary> for Height {
404 fn add_summary(&mut self, summary: &'a ElementHeightSummary, _: &()) {
405 self.0 += summary.height;
406 }
407}
408
409impl<'a> sum_tree::SeekDimension<'a, ElementHeightSummary> for Height {
410 fn cmp(&self, other: &Self, _: &()) -> std::cmp::Ordering {
411 self.0.partial_cmp(&other.0).unwrap()
412 }
413}
414
415#[cfg(test)]
416mod tests {
417 use super::*;
418 use crate::{elements::*, geometry::vector::vec2f, Entity};
419
420 #[crate::test(self)]
421 fn test_layout(cx: &mut crate::MutableAppContext) {
422 let mut presenter = cx.build_presenter(0, 0.);
423
424 let mut elements = vec![20., 30., 10.];
425 let state = ListState::new(elements.len(), Orientation::Top);
426
427 let mut list = List::new(
428 state.clone(),
429 &cx.render_cx::<TestView>(0, 0, 0., false),
430 |range| elements[range].iter().copied().map(item),
431 )
432 .boxed();
433 let size = list.layout(
434 SizeConstraint::new(vec2f(0., 0.), vec2f(100., 40.)),
435 &mut presenter.layout_cx(cx),
436 );
437 assert_eq!(size, vec2f(100., 40.));
438 assert_eq!(
439 state.0.borrow().heights.summary(),
440 ElementHeightSummary {
441 count: 3,
442 pending_count: 0,
443 height: 60.
444 }
445 );
446
447 elements.splice(1..2, vec![40., 50.]);
448 elements.push(60.);
449 state.splice(1..2, 2);
450 state.splice(4..4, 1);
451 assert_eq!(
452 state.0.borrow().heights.summary(),
453 ElementHeightSummary {
454 count: 5,
455 pending_count: 3,
456 height: 30.
457 }
458 );
459
460 let mut list = List::new(
461 state.clone(),
462 &cx.render_cx::<TestView>(0, 0, 0., false),
463 |range| elements[range].iter().copied().map(item),
464 )
465 .boxed();
466 let size = list.layout(
467 SizeConstraint::new(vec2f(0., 0.), vec2f(100., 40.)),
468 &mut presenter.layout_cx(cx),
469 );
470 assert_eq!(size, vec2f(100., 40.));
471 assert_eq!(
472 state.0.borrow().heights.summary(),
473 ElementHeightSummary {
474 count: 5,
475 pending_count: 0,
476 height: 180.
477 }
478 );
479 }
480
481 fn item(height: f32) -> ElementBox {
482 ConstrainedBox::new(Empty::new().boxed())
483 .with_height(height)
484 .with_width(100.)
485 .boxed()
486 }
487
488 struct TestView;
489
490 impl Entity for TestView {
491 type Event = ();
492 }
493
494 impl View for TestView {
495 fn ui_name() -> &'static str {
496 "TestView"
497 }
498
499 fn render(&self, _: &mut RenderContext<'_, Self>) -> ElementBox {
500 unimplemented!()
501 }
502 }
503}