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 let mut old_heights = state.heights.cursor::<Count, ()>();
265 let mut new_heights = old_heights.slice(&Count(old_range.start), Bias::Right, &());
266 old_heights.seek_forward(&Count(old_range.end), Bias::Right, &());
267
268 let old_elements = state.elements.splice(old_range, (0..count).map(|_| None));
269 drop(old_elements);
270
271 new_heights.extend((0..count).map(|_| ElementHeight::Pending), &());
272 new_heights.push_tree(old_heights.suffix(&()), &());
273 drop(old_heights);
274 state.heights = new_heights;
275 }
276
277 pub fn set_scroll_handler(
278 &mut self,
279 handler: impl FnMut(Range<usize>, &mut EventContext) + 'static,
280 ) {
281 self.0.borrow_mut().scroll_handler = Some(Box::new(handler))
282 }
283}
284
285impl StateInner {
286 fn visible_range(&self, height: f32) -> Range<usize> {
287 let mut cursor = self.heights.cursor::<Height, Count>();
288 cursor.seek(&Height(self.scroll_top(height)), Bias::Right, &());
289 let start_ix = cursor.sum_start().0;
290 cursor.seek(&Height(self.scroll_top(height) + height), Bias::Left, &());
291 let end_ix = cursor.sum_start().0;
292 start_ix..self.elements.len().min(end_ix + 1)
293 }
294
295 fn scroll(
296 &mut self,
297 _: Vector2F,
298 mut delta: Vector2F,
299 precise: bool,
300 height: f32,
301 cx: &mut EventContext,
302 ) -> bool {
303 if !precise {
304 delta *= 20.;
305 }
306
307 let delta_y;
308 let seek_bias;
309 match self.orientation {
310 Orientation::Top => {
311 delta_y = delta.y();
312 seek_bias = Bias::Right;
313 }
314 Orientation::Bottom => {
315 delta_y = -delta.y();
316 seek_bias = Bias::Left;
317 }
318 };
319
320 let scroll_max = (self.heights.summary().height - height).max(0.);
321 let new_scroll_top = (self.scroll_top(height) + delta_y).max(0.).min(scroll_max);
322 if self.orientation == Orientation::Bottom && new_scroll_top == scroll_max {
323 self.scroll_top = None;
324 } else {
325 let mut cursor = self.heights.cursor::<Height, Count>();
326 cursor.seek(&Height(new_scroll_top), seek_bias, &());
327 let ix = cursor.sum_start().0;
328 let offset = new_scroll_top - cursor.seek_start().0;
329 self.scroll_top = Some((ix, offset));
330 }
331
332 if self.scroll_handler.is_some() {
333 let range = self.visible_range(height);
334 self.scroll_handler.as_mut().unwrap()(range, cx);
335 }
336 cx.notify();
337
338 true
339 }
340
341 fn scroll_top(&self, height: f32) -> f32 {
342 let scroll_max = (self.heights.summary().height - height).max(0.);
343 if let Some((ix, offset)) = self.scroll_top {
344 let mut cursor = self.heights.cursor::<Count, Height>();
345 cursor.seek(&Count(ix), Bias::Right, &());
346 (cursor.sum_start().0 + offset).min(scroll_max)
347 } else {
348 match self.orientation {
349 Orientation::Top => 0.,
350 Orientation::Bottom => scroll_max,
351 }
352 }
353 }
354}
355
356impl ElementHeight {
357 fn is_pending(&self) -> bool {
358 matches!(self, ElementHeight::Pending)
359 }
360}
361
362impl sum_tree::Item for ElementHeight {
363 type Summary = ElementHeightSummary;
364
365 fn summary(&self) -> Self::Summary {
366 match self {
367 ElementHeight::Pending => ElementHeightSummary {
368 count: 1,
369 pending_count: 1,
370 height: 0.,
371 },
372 ElementHeight::Ready(height) => ElementHeightSummary {
373 count: 1,
374 pending_count: 0,
375 height: *height,
376 },
377 }
378 }
379}
380
381impl sum_tree::Summary for ElementHeightSummary {
382 type Context = ();
383
384 fn add_summary(&mut self, summary: &Self, _: &()) {
385 self.count += summary.count;
386 self.pending_count += summary.pending_count;
387 self.height += summary.height;
388 }
389}
390
391impl<'a> sum_tree::Dimension<'a, ElementHeightSummary> for ElementHeightSummary {
392 fn add_summary(&mut self, summary: &'a ElementHeightSummary, _: &()) {
393 sum_tree::Summary::add_summary(self, summary, &());
394 }
395}
396
397impl<'a> sum_tree::Dimension<'a, ElementHeightSummary> for Count {
398 fn add_summary(&mut self, summary: &'a ElementHeightSummary, _: &()) {
399 self.0 += summary.count;
400 }
401}
402
403impl<'a> sum_tree::SeekDimension<'a, ElementHeightSummary> for Count {
404 fn cmp(&self, other: &Self, _: &()) -> std::cmp::Ordering {
405 self.0.cmp(&other.0)
406 }
407}
408
409impl<'a> sum_tree::Dimension<'a, ElementHeightSummary> for PendingCount {
410 fn add_summary(&mut self, summary: &'a ElementHeightSummary, _: &()) {
411 self.0 += summary.pending_count;
412 }
413}
414
415impl<'a> sum_tree::SeekDimension<'a, ElementHeightSummary> for PendingCount {
416 fn cmp(&self, other: &Self, _: &()) -> std::cmp::Ordering {
417 self.0.cmp(&other.0)
418 }
419}
420
421impl<'a> sum_tree::Dimension<'a, ElementHeightSummary> for Height {
422 fn add_summary(&mut self, summary: &'a ElementHeightSummary, _: &()) {
423 self.0 += summary.height;
424 }
425}
426
427impl<'a> sum_tree::SeekDimension<'a, ElementHeightSummary> for Height {
428 fn cmp(&self, other: &Self, _: &()) -> std::cmp::Ordering {
429 self.0.partial_cmp(&other.0).unwrap()
430 }
431}
432
433#[cfg(test)]
434mod tests {
435 use super::*;
436 use crate::{elements::*, geometry::vector::vec2f, Entity};
437
438 #[crate::test(self)]
439 fn test_layout(cx: &mut crate::MutableAppContext) {
440 let mut presenter = cx.build_presenter(0, 0.);
441
442 let mut elements = vec![20., 30., 10.];
443 let state = ListState::new(elements.len(), Orientation::Top);
444
445 let mut list = List::new(
446 state.clone(),
447 &cx.build_render_context::<TestView>(0, 0, 0., false),
448 |range| elements[range].iter().copied().map(item),
449 )
450 .boxed();
451 let size = list.layout(
452 SizeConstraint::new(vec2f(0., 0.), vec2f(100., 40.)),
453 &mut presenter.build_layout_context(cx),
454 );
455 assert_eq!(size, vec2f(100., 40.));
456 assert_eq!(
457 state.0.borrow().heights.summary(),
458 ElementHeightSummary {
459 count: 3,
460 pending_count: 0,
461 height: 60.
462 }
463 );
464
465 elements.splice(1..2, vec![40., 50.]);
466 elements.push(60.);
467 state.splice(1..2, 2);
468 state.splice(4..4, 1);
469 assert_eq!(
470 state.0.borrow().heights.summary(),
471 ElementHeightSummary {
472 count: 5,
473 pending_count: 3,
474 height: 30.
475 }
476 );
477
478 let mut list = List::new(
479 state.clone(),
480 &cx.build_render_context::<TestView>(0, 0, 0., false),
481 |range| elements[range].iter().copied().map(item),
482 )
483 .boxed();
484 let size = list.layout(
485 SizeConstraint::new(vec2f(0., 0.), vec2f(100., 40.)),
486 &mut presenter.build_layout_context(cx),
487 );
488 assert_eq!(size, vec2f(100., 40.));
489 assert_eq!(
490 state.0.borrow().heights.summary(),
491 ElementHeightSummary {
492 count: 5,
493 pending_count: 0,
494 height: 180.
495 }
496 );
497 }
498
499 fn item(height: f32) -> ElementBox {
500 ConstrainedBox::new(Empty::new().boxed())
501 .with_height(height)
502 .with_width(100.)
503 .boxed()
504 }
505
506 struct TestView;
507
508 impl Entity for TestView {
509 type Event = ();
510 }
511
512 impl View for TestView {
513 fn ui_name() -> &'static str {
514 "TestView"
515 }
516
517 fn render(&mut self, _: &mut RenderContext<'_, Self>) -> ElementBox {
518 unimplemented!()
519 }
520 }
521}