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