git.seregonwar.com

crates/strato-ui-core/src/linear_index.rs

StratoSDK / crates / strato-ui-core / src / linear_index.rs

1	use std::marker::PhantomData;
2	use std::ops::AddAssign;
3
4	#[derive(Clone, Copy, Debug, PartialEq, Eq)]
5	pub enum SeekBias {
6	Left,
7	Right,
8	}
9
10	pub trait Item {
11	type Summary: Clone + Default;
12
13	fn summary(&self) -> Self::Summary;
14	}
15
16	pub trait Dimension<'a, Summary> {
17	fn add_summary(&mut self, summary: &'a Summary);
18	}
19
20	impl<'a, Summary> Dimension<'a, Summary> for () {
21	fn add_summary(&mut self, _summary: &'a Summary) {}
22	}
23
24	#[derive(Clone, Debug)]
25	pub struct SumTree<T: Item + Clone> {
26	items: Vec<T>,
27	}
28
29	impl<T: Item + Clone> SumTree<T> {
30	pub fn new() -> Self {
31	Self { items: Vec::new() }
32	}
33
34	pub fn push(&mut self, item: T) {
35	self.items.push(item);
36	}
37
38	pub fn push_tree(&mut self, mut tree: Self) {
39	self.items.append(&mut tree.items);
40	}
41
42	pub fn extend<I>(&mut self, items: I)
43	where
44	I: IntoIterator<Item = T>,
45	{
46	self.items.extend(items);
47	}
48
49	pub fn summary(&self) -> T::Summary
50	where
51	for<'a> T::Summary: AddAssign<&'a T::Summary>,
52	{
53	summarize::<T>(&self.items)
54	}
55
56	pub fn cursor<SeekDimension, StartDimension>(&self) -> Cursor<T, SeekDimension, StartDimension>
57	where
58	StartDimension: Default,
59	{
60	Cursor {
61	items: self.items.clone(),
62	position: 0,
63	start: StartDimension::default(),
64	_seek_dimension: PhantomData,
65	}
66	}
67	}
68
69	impl<T: Item + Clone> Default for SumTree<T> {
70	fn default() -> Self {
71	Self::new()
72	}
73	}
74
75	pub struct Cursor<T, SeekDimension, StartDimension>
76	where
77	T: Item + Clone,
78	{
79	items: Vec<T>,
80	position: usize,
81	start: StartDimension,
82	_seek_dimension: PhantomData<SeekDimension>,
83	}
84
85	impl<T, SeekDimension, StartDimension> Cursor<T, SeekDimension, StartDimension>
86	where
87	T: Item + Clone,
88	StartDimension: Clone + Default,
89	for<'a> StartDimension: Dimension<'a, T::Summary>,
90	{
91	pub fn seek(&mut self, target: &SeekDimension, bias: SeekBias)
92	where
93	SeekDimension: Clone + Default + PartialOrd,
94	for<'a> SeekDimension: Dimension<'a, T::Summary>,
95	{
96	let (position, start) =
97	seek_position::<T, SeekDimension, StartDimension>(&self.items, target, bias);
98	self.position = position;
99	self.start = start;
100	}
101
102	pub fn start(&self) -> &StartDimension {
103	&self.start
104	}
105
106	pub fn item(&self) -> Option<&T> {
107	self.items.get(self.position)
108	}
109
110	pub fn next(&mut self) {
111	if let Some(item) = self.items.get(self.position) {
112	self.start.add_summary(&item.summary());
113	self.position += 1;
114	}
115	}
116
117	pub fn slice(&mut self, target: &SeekDimension, bias: SeekBias) -> SumTree<T>
118	where
119	SeekDimension: Clone + Default + PartialOrd,
120	for<'a> SeekDimension: Dimension<'a, T::Summary>,
121	{
122	self.seek(target, bias);
123	SumTree {
124	items: self.items[..self.position].to_vec(),
125	}
126	}
127
128	pub fn suffix(&self) -> SumTree<T> {
129	SumTree {
130	items: self.items[self.position..].to_vec(),
131	}
132	}
133
134	pub fn enumerate(&self) -> impl Iterator<Item = (usize, T)> + '_ {
135	self.items[self.position..].iter().cloned().enumerate()
136	}
137	}
138
139	fn summarize<T>(items: &[T]) -> T::Summary
140	where
141	T: Item + Clone,
142	for<'a> T::Summary: AddAssign<&'a T::Summary>,
143	{
144	let mut summary = T::Summary::default();
145	for item in items {
146	summary += &item.summary();
147	}
148	summary
149	}
150
151	fn seek_position<T, SeekDimension, StartDimension>(
152	items: &[T],
153	target: &SeekDimension,
154	bias: SeekBias,
155	) -> (usize, StartDimension)
156	where
157	T: Item + Clone,
158	SeekDimension: Clone + Default + PartialOrd,
159	StartDimension: Clone + Default,
160	for<'a> SeekDimension: Dimension<'a, T::Summary>,
161	for<'a> StartDimension: Dimension<'a, T::Summary>,
162	{
163	let mut seek_dimension = SeekDimension::default();
164	let mut start_dimension = StartDimension::default();
165
166	for (index, item) in items.iter().enumerate() {
167	let summary = item.summary();
168	let mut next_seek_dimension = seek_dimension.clone();
169	next_seek_dimension.add_summary(&summary);
170
171	let found = match bias {
172	SeekBias::Left => next_seek_dimension >= *target,
173	SeekBias::Right => next_seek_dimension > *target,
174	};
175
176	if found {
177	return (index, start_dimension);
178	}
179
180	seek_dimension = next_seek_dimension;
181	start_dimension.add_summary(&summary);
182	}
183
184	(items.len(), start_dimension)
185	}
186

Seregon/StratoSDK