1mod cursor;
2mod tree_map;
3
4use arrayvec::ArrayVec;
5pub use cursor::{Cursor, FilterCursor, Iter};
6use rayon::prelude::*;
7use std::marker::PhantomData;
8use std::mem;
9use std::{cmp::Ordering, fmt, iter::FromIterator, sync::Arc};
10pub use tree_map::{MapSeekTarget, TreeMap, TreeSet};
11
12#[cfg(test)]
13pub const TREE_BASE: usize = 2;
14#[cfg(not(test))]
15pub const TREE_BASE: usize = 6;
16
17/// An item that can be stored in a [`SumTree`]
18///
19/// Must be summarized by a type that implements [`Summary`]
20pub trait Item: Clone {
21 type Summary: Summary;
22
23 fn summary(&self, cx: &<Self::Summary as Summary>::Context) -> Self::Summary;
24}
25
26/// An [`Item`] whose summary has a specific key that can be used to identify it
27pub trait KeyedItem: Item {
28 type Key: for<'a> Dimension<'a, Self::Summary> + Ord;
29
30 fn key(&self) -> Self::Key;
31}
32
33/// A type that describes the Sum of all [`Item`]s in a subtree of the [`SumTree`]
34///
35/// Each Summary type can have multiple [`Dimension`]s that it measures,
36/// which can be used to navigate the tree
37pub trait Summary: Clone {
38 type Context;
39
40 fn zero(cx: &Self::Context) -> Self;
41 fn add_summary(&mut self, summary: &Self, cx: &Self::Context);
42}
43
44/// Catch-all implementation for when you need something that implements [`Summary`] without a specific type.
45/// We implement it on a &'static, as that avoids blanket impl collisions with `impl<T: Summary> Dimension for T`
46/// (as we also need unit type to be a fill-in dimension)
47impl Summary for &'static () {
48 type Context = ();
49
50 fn zero(_: &()) -> Self {
51 &()
52 }
53
54 fn add_summary(&mut self, _: &Self, _: &()) {}
55}
56
57/// Each [`Summary`] type can have more than one [`Dimension`] type that it measures.
58///
59/// You can use dimensions to seek to a specific location in the [`SumTree`]
60///
61/// # Example:
62/// Zed's rope has a `TextSummary` type that summarizes lines, characters, and bytes.
63/// Each of these are different dimensions we may want to seek to
64pub trait Dimension<'a, S: Summary>: Clone {
65 fn zero(cx: &S::Context) -> Self;
66
67 fn add_summary(&mut self, summary: &'a S, cx: &S::Context);
68
69 fn from_summary(summary: &'a S, cx: &S::Context) -> Self {
70 let mut dimension = Self::zero(cx);
71 dimension.add_summary(summary, cx);
72 dimension
73 }
74}
75
76impl<'a, T: Summary> Dimension<'a, T> for T {
77 fn zero(cx: &T::Context) -> Self {
78 Summary::zero(cx)
79 }
80
81 fn add_summary(&mut self, summary: &'a T, cx: &T::Context) {
82 Summary::add_summary(self, summary, cx);
83 }
84}
85
86pub trait SeekTarget<'a, S: Summary, D: Dimension<'a, S>> {
87 fn cmp(&self, cursor_location: &D, cx: &S::Context) -> Ordering;
88}
89
90impl<'a, S: Summary, D: Dimension<'a, S> + Ord> SeekTarget<'a, S, D> for D {
91 fn cmp(&self, cursor_location: &Self, _: &S::Context) -> Ordering {
92 Ord::cmp(self, cursor_location)
93 }
94}
95
96impl<'a, T: Summary> Dimension<'a, T> for () {
97 fn zero(_: &T::Context) -> Self {}
98
99 fn add_summary(&mut self, _: &'a T, _: &T::Context) {}
100}
101
102#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, PartialOrd, Ord)]
103pub struct Dimensions<D1, D2, D3 = ()>(pub D1, pub D2, pub D3);
104
105impl<'a, T: Summary, D1: Dimension<'a, T>, D2: Dimension<'a, T>, D3: Dimension<'a, T>>
106 Dimension<'a, T> for Dimensions<D1, D2, D3>
107{
108 fn zero(cx: &T::Context) -> Self {
109 Dimensions(D1::zero(cx), D2::zero(cx), D3::zero(cx))
110 }
111
112 fn add_summary(&mut self, summary: &'a T, cx: &T::Context) {
113 self.0.add_summary(summary, cx);
114 self.1.add_summary(summary, cx);
115 self.2.add_summary(summary, cx);
116 }
117}
118
119impl<'a, S, D1, D2, D3> SeekTarget<'a, S, Dimensions<D1, D2, D3>> for D1
120where
121 S: Summary,
122 D1: SeekTarget<'a, S, D1> + Dimension<'a, S>,
123 D2: Dimension<'a, S>,
124 D3: Dimension<'a, S>,
125{
126 fn cmp(&self, cursor_location: &Dimensions<D1, D2, D3>, cx: &S::Context) -> Ordering {
127 self.cmp(&cursor_location.0, cx)
128 }
129}
130
131/// Bias is used to settle ambiguities when determining positions in an ordered sequence.
132///
133/// The primary use case is for text, where Bias influences
134/// which character an offset or anchor is associated with.
135///
136/// # Examples
137/// Given the buffer `AˇBCD`:
138/// - The offset of the cursor is 1
139/// - [Bias::Left] would attach the cursor to the character `A`
140/// - [Bias::Right] would attach the cursor to the character `B`
141///
142/// Given the buffer `A«BCˇ»D`:
143/// - The offset of the cursor is 3, and the selection is from 1 to 3
144/// - The left anchor of the selection has [Bias::Right], attaching it to the character `B`
145/// - The right anchor of the selection has [Bias::Left], attaching it to the character `C`
146///
147/// Given the buffer `{ˇ<...>`, where `<...>` is a folded region:
148/// - The display offset of the cursor is 1, but the offset in the buffer is determined by the bias
149/// - [Bias::Left] would attach the cursor to the character `{`, with a buffer offset of 1
150/// - [Bias::Right] would attach the cursor to the first character of the folded region,
151/// and the buffer offset would be the offset of the first character of the folded region
152#[derive(Copy, Clone, Eq, PartialEq, PartialOrd, Ord, Debug, Hash, Default)]
153pub enum Bias {
154 /// Attach to the character on the left
155 #[default]
156 Left,
157 /// Attach to the character on the right
158 Right,
159}
160
161impl Bias {
162 pub fn invert(self) -> Self {
163 match self {
164 Self::Left => Self::Right,
165 Self::Right => Self::Left,
166 }
167 }
168}
169
170/// A B+ tree in which each leaf node contains `Item`s of type `T` and a `Summary`s for each `Item`.
171/// Each internal node contains a `Summary` of the items in its subtree.
172///
173/// The maximum number of items per node is `TREE_BASE * 2`.
174///
175/// Any [`Dimension`] supported by the [`Summary`] type can be used to seek to a specific location in the tree.
176#[derive(Clone)]
177pub struct SumTree<T: Item>(Arc<Node<T>>);
178
179impl<T> fmt::Debug for SumTree<T>
180where
181 T: fmt::Debug + Item,
182 T::Summary: fmt::Debug,
183{
184 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
185 f.debug_tuple("SumTree").field(&self.0).finish()
186 }
187}
188
189impl<T: Item> SumTree<T> {
190 pub fn new(cx: &<T::Summary as Summary>::Context) -> Self {
191 SumTree(Arc::new(Node::Leaf {
192 summary: <T::Summary as Summary>::zero(cx),
193 items: ArrayVec::new(),
194 item_summaries: ArrayVec::new(),
195 }))
196 }
197
198 /// Useful in cases where the item type has a non-trivial context type, but the zero value of the summary type doesn't depend on that context.
199 pub fn from_summary(summary: T::Summary) -> Self {
200 SumTree(Arc::new(Node::Leaf {
201 summary,
202 items: ArrayVec::new(),
203 item_summaries: ArrayVec::new(),
204 }))
205 }
206
207 pub fn from_item(item: T, cx: &<T::Summary as Summary>::Context) -> Self {
208 let mut tree = Self::new(cx);
209 tree.push(item, cx);
210 tree
211 }
212
213 pub fn from_iter<I: IntoIterator<Item = T>>(
214 iter: I,
215 cx: &<T::Summary as Summary>::Context,
216 ) -> Self {
217 let mut nodes = Vec::new();
218
219 let mut iter = iter.into_iter().fuse().peekable();
220 while iter.peek().is_some() {
221 let items: ArrayVec<T, { 2 * TREE_BASE }> = iter.by_ref().take(2 * TREE_BASE).collect();
222 let item_summaries: ArrayVec<T::Summary, { 2 * TREE_BASE }> =
223 items.iter().map(|item| item.summary(cx)).collect();
224
225 let mut summary = item_summaries[0].clone();
226 for item_summary in &item_summaries[1..] {
227 <T::Summary as Summary>::add_summary(&mut summary, item_summary, cx);
228 }
229
230 nodes.push(Node::Leaf {
231 summary,
232 items,
233 item_summaries,
234 });
235 }
236
237 let mut parent_nodes = Vec::new();
238 let mut height = 0;
239 while nodes.len() > 1 {
240 height += 1;
241 let mut current_parent_node = None;
242 for child_node in nodes.drain(..) {
243 let parent_node = current_parent_node.get_or_insert_with(|| Node::Internal {
244 summary: <T::Summary as Summary>::zero(cx),
245 height,
246 child_summaries: ArrayVec::new(),
247 child_trees: ArrayVec::new(),
248 });
249 let Node::Internal {
250 summary,
251 child_summaries,
252 child_trees,
253 ..
254 } = parent_node
255 else {
256 unreachable!()
257 };
258 let child_summary = child_node.summary();
259 <T::Summary as Summary>::add_summary(summary, child_summary, cx);
260 child_summaries.push(child_summary.clone());
261 child_trees.push(Self(Arc::new(child_node)));
262
263 if child_trees.len() == 2 * TREE_BASE {
264 parent_nodes.extend(current_parent_node.take());
265 }
266 }
267 parent_nodes.extend(current_parent_node.take());
268 mem::swap(&mut nodes, &mut parent_nodes);
269 }
270
271 if nodes.is_empty() {
272 Self::new(cx)
273 } else {
274 debug_assert_eq!(nodes.len(), 1);
275 Self(Arc::new(nodes.pop().unwrap()))
276 }
277 }
278
279 pub fn from_par_iter<I, Iter>(iter: I, cx: &<T::Summary as Summary>::Context) -> Self
280 where
281 I: IntoParallelIterator<Iter = Iter>,
282 Iter: IndexedParallelIterator<Item = T>,
283 T: Send + Sync,
284 T::Summary: Send + Sync,
285 <T::Summary as Summary>::Context: Sync,
286 {
287 let mut nodes = iter
288 .into_par_iter()
289 .chunks(2 * TREE_BASE)
290 .map(|items| {
291 let items: ArrayVec<T, { 2 * TREE_BASE }> = items.into_iter().collect();
292 let item_summaries: ArrayVec<T::Summary, { 2 * TREE_BASE }> =
293 items.iter().map(|item| item.summary(cx)).collect();
294 let mut summary = item_summaries[0].clone();
295 for item_summary in &item_summaries[1..] {
296 <T::Summary as Summary>::add_summary(&mut summary, item_summary, cx);
297 }
298 SumTree(Arc::new(Node::Leaf {
299 summary,
300 items,
301 item_summaries,
302 }))
303 })
304 .collect::<Vec<_>>();
305
306 let mut height = 0;
307 while nodes.len() > 1 {
308 height += 1;
309 nodes = nodes
310 .into_par_iter()
311 .chunks(2 * TREE_BASE)
312 .map(|child_nodes| {
313 let child_trees: ArrayVec<SumTree<T>, { 2 * TREE_BASE }> =
314 child_nodes.into_iter().collect();
315 let child_summaries: ArrayVec<T::Summary, { 2 * TREE_BASE }> = child_trees
316 .iter()
317 .map(|child_tree| child_tree.summary().clone())
318 .collect();
319 let mut summary = child_summaries[0].clone();
320 for child_summary in &child_summaries[1..] {
321 <T::Summary as Summary>::add_summary(&mut summary, child_summary, cx);
322 }
323 SumTree(Arc::new(Node::Internal {
324 height,
325 summary,
326 child_summaries,
327 child_trees,
328 }))
329 })
330 .collect::<Vec<_>>();
331 }
332
333 if nodes.is_empty() {
334 Self::new(cx)
335 } else {
336 debug_assert_eq!(nodes.len(), 1);
337 nodes.pop().unwrap()
338 }
339 }
340
341 #[allow(unused)]
342 pub fn items(&self, cx: &<T::Summary as Summary>::Context) -> Vec<T> {
343 let mut items = Vec::new();
344 let mut cursor = self.cursor::<()>(cx);
345 cursor.next();
346 while let Some(item) = cursor.item() {
347 items.push(item.clone());
348 cursor.next();
349 }
350 items
351 }
352
353 pub fn iter(&self) -> Iter<'_, T> {
354 Iter::new(self)
355 }
356
357 pub fn cursor<'a, S>(&'a self, cx: &'a <T::Summary as Summary>::Context) -> Cursor<'a, T, S>
358 where
359 S: Dimension<'a, T::Summary>,
360 {
361 Cursor::new(self, cx)
362 }
363
364 /// Note: If the summary type requires a non `()` context, then the filter cursor
365 /// that is returned cannot be used with Rust's iterators.
366 pub fn filter<'a, F, U>(
367 &'a self,
368 cx: &'a <T::Summary as Summary>::Context,
369 filter_node: F,
370 ) -> FilterCursor<'a, F, T, U>
371 where
372 F: FnMut(&T::Summary) -> bool,
373 U: Dimension<'a, T::Summary>,
374 {
375 FilterCursor::new(self, cx, filter_node)
376 }
377
378 #[allow(dead_code)]
379 pub fn first(&self) -> Option<&T> {
380 self.leftmost_leaf().0.items().first()
381 }
382
383 pub fn last(&self) -> Option<&T> {
384 self.rightmost_leaf().0.items().last()
385 }
386
387 pub fn update_last(&mut self, f: impl FnOnce(&mut T), cx: &<T::Summary as Summary>::Context) {
388 self.update_last_recursive(f, cx);
389 }
390
391 fn update_last_recursive(
392 &mut self,
393 f: impl FnOnce(&mut T),
394 cx: &<T::Summary as Summary>::Context,
395 ) -> Option<T::Summary> {
396 match Arc::make_mut(&mut self.0) {
397 Node::Internal {
398 summary,
399 child_summaries,
400 child_trees,
401 ..
402 } => {
403 let last_summary = child_summaries.last_mut().unwrap();
404 let last_child = child_trees.last_mut().unwrap();
405 *last_summary = last_child.update_last_recursive(f, cx).unwrap();
406 *summary = sum(child_summaries.iter(), cx);
407 Some(summary.clone())
408 }
409 Node::Leaf {
410 summary,
411 items,
412 item_summaries,
413 } => {
414 if let Some((item, item_summary)) = items.last_mut().zip(item_summaries.last_mut())
415 {
416 (f)(item);
417 *item_summary = item.summary(cx);
418 *summary = sum(item_summaries.iter(), cx);
419 Some(summary.clone())
420 } else {
421 None
422 }
423 }
424 }
425 }
426
427 pub fn extent<'a, D: Dimension<'a, T::Summary>>(
428 &'a self,
429 cx: &<T::Summary as Summary>::Context,
430 ) -> D {
431 let mut extent = D::zero(cx);
432 match self.0.as_ref() {
433 Node::Internal { summary, .. } | Node::Leaf { summary, .. } => {
434 extent.add_summary(summary, cx);
435 }
436 }
437 extent
438 }
439
440 pub fn summary(&self) -> &T::Summary {
441 match self.0.as_ref() {
442 Node::Internal { summary, .. } => summary,
443 Node::Leaf { summary, .. } => summary,
444 }
445 }
446
447 pub fn is_empty(&self) -> bool {
448 match self.0.as_ref() {
449 Node::Internal { .. } => false,
450 Node::Leaf { items, .. } => items.is_empty(),
451 }
452 }
453
454 pub fn extend<I>(&mut self, iter: I, cx: &<T::Summary as Summary>::Context)
455 where
456 I: IntoIterator<Item = T>,
457 {
458 self.append(Self::from_iter(iter, cx), cx);
459 }
460
461 pub fn par_extend<I, Iter>(&mut self, iter: I, cx: &<T::Summary as Summary>::Context)
462 where
463 I: IntoParallelIterator<Iter = Iter>,
464 Iter: IndexedParallelIterator<Item = T>,
465 T: Send + Sync,
466 T::Summary: Send + Sync,
467 <T::Summary as Summary>::Context: Sync,
468 {
469 self.append(Self::from_par_iter(iter, cx), cx);
470 }
471
472 pub fn push(&mut self, item: T, cx: &<T::Summary as Summary>::Context) {
473 let summary = item.summary(cx);
474 self.append(
475 SumTree(Arc::new(Node::Leaf {
476 summary: summary.clone(),
477 items: ArrayVec::from_iter(Some(item)),
478 item_summaries: ArrayVec::from_iter(Some(summary)),
479 })),
480 cx,
481 );
482 }
483
484 pub fn append(&mut self, other: Self, cx: &<T::Summary as Summary>::Context) {
485 if self.is_empty() {
486 *self = other;
487 } else if !other.0.is_leaf() || !other.0.items().is_empty() {
488 if self.0.height() < other.0.height() {
489 for tree in other.0.child_trees() {
490 self.append(tree.clone(), cx);
491 }
492 } else if let Some(split_tree) = self.push_tree_recursive(other, cx) {
493 *self = Self::from_child_trees(self.clone(), split_tree, cx);
494 }
495 }
496 }
497
498 fn push_tree_recursive(
499 &mut self,
500 other: SumTree<T>,
501 cx: &<T::Summary as Summary>::Context,
502 ) -> Option<SumTree<T>> {
503 match Arc::make_mut(&mut self.0) {
504 Node::Internal {
505 height,
506 summary,
507 child_summaries,
508 child_trees,
509 ..
510 } => {
511 let other_node = other.0.clone();
512 <T::Summary as Summary>::add_summary(summary, other_node.summary(), cx);
513
514 let height_delta = *height - other_node.height();
515 let mut summaries_to_append = ArrayVec::<T::Summary, { 2 * TREE_BASE }>::new();
516 let mut trees_to_append = ArrayVec::<SumTree<T>, { 2 * TREE_BASE }>::new();
517 if height_delta == 0 {
518 summaries_to_append.extend(other_node.child_summaries().iter().cloned());
519 trees_to_append.extend(other_node.child_trees().iter().cloned());
520 } else if height_delta == 1 && !other_node.is_underflowing() {
521 summaries_to_append.push(other_node.summary().clone());
522 trees_to_append.push(other)
523 } else {
524 let tree_to_append = child_trees
525 .last_mut()
526 .unwrap()
527 .push_tree_recursive(other, cx);
528 *child_summaries.last_mut().unwrap() =
529 child_trees.last().unwrap().0.summary().clone();
530
531 if let Some(split_tree) = tree_to_append {
532 summaries_to_append.push(split_tree.0.summary().clone());
533 trees_to_append.push(split_tree);
534 }
535 }
536
537 let child_count = child_trees.len() + trees_to_append.len();
538 if child_count > 2 * TREE_BASE {
539 let left_summaries: ArrayVec<_, { 2 * TREE_BASE }>;
540 let right_summaries: ArrayVec<_, { 2 * TREE_BASE }>;
541 let left_trees;
542 let right_trees;
543
544 let midpoint = (child_count + child_count % 2) / 2;
545 {
546 let mut all_summaries = child_summaries
547 .iter()
548 .chain(summaries_to_append.iter())
549 .cloned();
550 left_summaries = all_summaries.by_ref().take(midpoint).collect();
551 right_summaries = all_summaries.collect();
552 let mut all_trees =
553 child_trees.iter().chain(trees_to_append.iter()).cloned();
554 left_trees = all_trees.by_ref().take(midpoint).collect();
555 right_trees = all_trees.collect();
556 }
557 *summary = sum(left_summaries.iter(), cx);
558 *child_summaries = left_summaries;
559 *child_trees = left_trees;
560
561 Some(SumTree(Arc::new(Node::Internal {
562 height: *height,
563 summary: sum(right_summaries.iter(), cx),
564 child_summaries: right_summaries,
565 child_trees: right_trees,
566 })))
567 } else {
568 child_summaries.extend(summaries_to_append);
569 child_trees.extend(trees_to_append);
570 None
571 }
572 }
573 Node::Leaf {
574 summary,
575 items,
576 item_summaries,
577 } => {
578 let other_node = other.0;
579
580 let child_count = items.len() + other_node.items().len();
581 if child_count > 2 * TREE_BASE {
582 let left_items;
583 let right_items;
584 let left_summaries;
585 let right_summaries: ArrayVec<T::Summary, { 2 * TREE_BASE }>;
586
587 let midpoint = (child_count + child_count % 2) / 2;
588 {
589 let mut all_items = items.iter().chain(other_node.items().iter()).cloned();
590 left_items = all_items.by_ref().take(midpoint).collect();
591 right_items = all_items.collect();
592
593 let mut all_summaries = item_summaries
594 .iter()
595 .chain(other_node.child_summaries())
596 .cloned();
597 left_summaries = all_summaries.by_ref().take(midpoint).collect();
598 right_summaries = all_summaries.collect();
599 }
600 *items = left_items;
601 *item_summaries = left_summaries;
602 *summary = sum(item_summaries.iter(), cx);
603 Some(SumTree(Arc::new(Node::Leaf {
604 items: right_items,
605 summary: sum(right_summaries.iter(), cx),
606 item_summaries: right_summaries,
607 })))
608 } else {
609 <T::Summary as Summary>::add_summary(summary, other_node.summary(), cx);
610 items.extend(other_node.items().iter().cloned());
611 item_summaries.extend(other_node.child_summaries().iter().cloned());
612 None
613 }
614 }
615 }
616 }
617
618 fn from_child_trees(
619 left: SumTree<T>,
620 right: SumTree<T>,
621 cx: &<T::Summary as Summary>::Context,
622 ) -> Self {
623 let height = left.0.height() + 1;
624 let mut child_summaries = ArrayVec::new();
625 child_summaries.push(left.0.summary().clone());
626 child_summaries.push(right.0.summary().clone());
627 let mut child_trees = ArrayVec::new();
628 child_trees.push(left);
629 child_trees.push(right);
630 SumTree(Arc::new(Node::Internal {
631 height,
632 summary: sum(child_summaries.iter(), cx),
633 child_summaries,
634 child_trees,
635 }))
636 }
637
638 fn leftmost_leaf(&self) -> &Self {
639 match *self.0 {
640 Node::Leaf { .. } => self,
641 Node::Internal {
642 ref child_trees, ..
643 } => child_trees.first().unwrap().leftmost_leaf(),
644 }
645 }
646
647 fn rightmost_leaf(&self) -> &Self {
648 match *self.0 {
649 Node::Leaf { .. } => self,
650 Node::Internal {
651 ref child_trees, ..
652 } => child_trees.last().unwrap().rightmost_leaf(),
653 }
654 }
655}
656
657impl<T: Item + PartialEq> PartialEq for SumTree<T> {
658 fn eq(&self, other: &Self) -> bool {
659 self.iter().eq(other.iter())
660 }
661}
662
663impl<T: Item + Eq> Eq for SumTree<T> {}
664
665impl<T: KeyedItem> SumTree<T> {
666 pub fn insert_or_replace(
667 &mut self,
668 item: T,
669 cx: &<T::Summary as Summary>::Context,
670 ) -> Option<T> {
671 let mut replaced = None;
672 *self = {
673 let mut cursor = self.cursor::<T::Key>(cx);
674 let mut new_tree = cursor.slice(&item.key(), Bias::Left);
675 if let Some(cursor_item) = cursor.item()
676 && cursor_item.key() == item.key()
677 {
678 replaced = Some(cursor_item.clone());
679 cursor.next();
680 }
681 new_tree.push(item, cx);
682 new_tree.append(cursor.suffix(), cx);
683 new_tree
684 };
685 replaced
686 }
687
688 pub fn remove(&mut self, key: &T::Key, cx: &<T::Summary as Summary>::Context) -> Option<T> {
689 let mut removed = None;
690 *self = {
691 let mut cursor = self.cursor::<T::Key>(cx);
692 let mut new_tree = cursor.slice(key, Bias::Left);
693 if let Some(item) = cursor.item()
694 && item.key() == *key
695 {
696 removed = Some(item.clone());
697 cursor.next();
698 }
699 new_tree.append(cursor.suffix(), cx);
700 new_tree
701 };
702 removed
703 }
704
705 pub fn edit(
706 &mut self,
707 mut edits: Vec<Edit<T>>,
708 cx: &<T::Summary as Summary>::Context,
709 ) -> Vec<T> {
710 if edits.is_empty() {
711 return Vec::new();
712 }
713
714 let mut removed = Vec::new();
715 edits.sort_unstable_by_key(|item| item.key());
716
717 *self = {
718 let mut cursor = self.cursor::<T::Key>(cx);
719 let mut new_tree = SumTree::new(cx);
720 let mut buffered_items = Vec::new();
721
722 cursor.seek(&T::Key::zero(cx), Bias::Left);
723 for edit in edits {
724 let new_key = edit.key();
725 let mut old_item = cursor.item();
726
727 if old_item
728 .as_ref()
729 .is_some_and(|old_item| old_item.key() < new_key)
730 {
731 new_tree.extend(buffered_items.drain(..), cx);
732 let slice = cursor.slice(&new_key, Bias::Left);
733 new_tree.append(slice, cx);
734 old_item = cursor.item();
735 }
736
737 if let Some(old_item) = old_item
738 && old_item.key() == new_key
739 {
740 removed.push(old_item.clone());
741 cursor.next();
742 }
743
744 match edit {
745 Edit::Insert(item) => {
746 buffered_items.push(item);
747 }
748 Edit::Remove(_) => {}
749 }
750 }
751
752 new_tree.extend(buffered_items, cx);
753 new_tree.append(cursor.suffix(), cx);
754 new_tree
755 };
756
757 removed
758 }
759
760 pub fn get<'a>(
761 &'a self,
762 key: &T::Key,
763 cx: &'a <T::Summary as Summary>::Context,
764 ) -> Option<&'a T> {
765 let mut cursor = self.cursor::<T::Key>(cx);
766 if cursor.seek(key, Bias::Left) {
767 cursor.item()
768 } else {
769 None
770 }
771 }
772}
773
774impl<T, S> Default for SumTree<T>
775where
776 T: Item<Summary = S>,
777 S: Summary<Context = ()>,
778{
779 fn default() -> Self {
780 Self::new(&())
781 }
782}
783
784#[derive(Clone)]
785pub enum Node<T: Item> {
786 Internal {
787 height: u8,
788 summary: T::Summary,
789 child_summaries: ArrayVec<T::Summary, { 2 * TREE_BASE }>,
790 child_trees: ArrayVec<SumTree<T>, { 2 * TREE_BASE }>,
791 },
792 Leaf {
793 summary: T::Summary,
794 items: ArrayVec<T, { 2 * TREE_BASE }>,
795 item_summaries: ArrayVec<T::Summary, { 2 * TREE_BASE }>,
796 },
797}
798
799impl<T> fmt::Debug for Node<T>
800where
801 T: Item + fmt::Debug,
802 T::Summary: fmt::Debug,
803{
804 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
805 match self {
806 Node::Internal {
807 height,
808 summary,
809 child_summaries,
810 child_trees,
811 } => f
812 .debug_struct("Internal")
813 .field("height", height)
814 .field("summary", summary)
815 .field("child_summaries", child_summaries)
816 .field("child_trees", child_trees)
817 .finish(),
818 Node::Leaf {
819 summary,
820 items,
821 item_summaries,
822 } => f
823 .debug_struct("Leaf")
824 .field("summary", summary)
825 .field("items", items)
826 .field("item_summaries", item_summaries)
827 .finish(),
828 }
829 }
830}
831
832impl<T: Item> Node<T> {
833 fn is_leaf(&self) -> bool {
834 matches!(self, Node::Leaf { .. })
835 }
836
837 fn height(&self) -> u8 {
838 match self {
839 Node::Internal { height, .. } => *height,
840 Node::Leaf { .. } => 0,
841 }
842 }
843
844 fn summary(&self) -> &T::Summary {
845 match self {
846 Node::Internal { summary, .. } => summary,
847 Node::Leaf { summary, .. } => summary,
848 }
849 }
850
851 fn child_summaries(&self) -> &[T::Summary] {
852 match self {
853 Node::Internal {
854 child_summaries, ..
855 } => child_summaries.as_slice(),
856 Node::Leaf { item_summaries, .. } => item_summaries.as_slice(),
857 }
858 }
859
860 fn child_trees(&self) -> &ArrayVec<SumTree<T>, { 2 * TREE_BASE }> {
861 match self {
862 Node::Internal { child_trees, .. } => child_trees,
863 Node::Leaf { .. } => panic!("Leaf nodes have no child trees"),
864 }
865 }
866
867 fn items(&self) -> &ArrayVec<T, { 2 * TREE_BASE }> {
868 match self {
869 Node::Leaf { items, .. } => items,
870 Node::Internal { .. } => panic!("Internal nodes have no items"),
871 }
872 }
873
874 fn is_underflowing(&self) -> bool {
875 match self {
876 Node::Internal { child_trees, .. } => child_trees.len() < TREE_BASE,
877 Node::Leaf { items, .. } => items.len() < TREE_BASE,
878 }
879 }
880}
881
882#[derive(Debug)]
883pub enum Edit<T: KeyedItem> {
884 Insert(T),
885 Remove(T::Key),
886}
887
888impl<T: KeyedItem> Edit<T> {
889 fn key(&self) -> T::Key {
890 match self {
891 Edit::Insert(item) => item.key(),
892 Edit::Remove(key) => key.clone(),
893 }
894 }
895}
896
897fn sum<'a, T, I>(iter: I, cx: &T::Context) -> T
898where
899 T: 'a + Summary,
900 I: Iterator<Item = &'a T>,
901{
902 let mut sum = T::zero(cx);
903 for value in iter {
904 sum.add_summary(value, cx);
905 }
906 sum
907}
908
909#[cfg(test)]
910mod tests {
911 use super::*;
912 use rand::{distr::StandardUniform, prelude::*};
913 use std::cmp;
914
915 #[ctor::ctor]
916 fn init_logger() {
917 zlog::init_test();
918 }
919
920 #[test]
921 fn test_extend_and_push_tree() {
922 let mut tree1 = SumTree::default();
923 tree1.extend(0..20, &());
924
925 let mut tree2 = SumTree::default();
926 tree2.extend(50..100, &());
927
928 tree1.append(tree2, &());
929 assert_eq!(
930 tree1.items(&()),
931 (0..20).chain(50..100).collect::<Vec<u8>>()
932 );
933 }
934
935 #[test]
936 fn test_random() {
937 let mut starting_seed = 0;
938 if let Ok(value) = std::env::var("SEED") {
939 starting_seed = value.parse().expect("invalid SEED variable");
940 }
941 let mut num_iterations = 100;
942 if let Ok(value) = std::env::var("ITERATIONS") {
943 num_iterations = value.parse().expect("invalid ITERATIONS variable");
944 }
945 let num_operations = std::env::var("OPERATIONS")
946 .map_or(5, |o| o.parse().expect("invalid OPERATIONS variable"));
947
948 for seed in starting_seed..(starting_seed + num_iterations) {
949 eprintln!("seed = {}", seed);
950 let mut rng = StdRng::seed_from_u64(seed);
951
952 let rng = &mut rng;
953 let mut tree = SumTree::<u8>::default();
954 let count = rng.random_range(0..10);
955 if rng.random() {
956 tree.extend(rng.sample_iter(StandardUniform).take(count), &());
957 } else {
958 let items = rng
959 .sample_iter(StandardUniform)
960 .take(count)
961 .collect::<Vec<_>>();
962 tree.par_extend(items, &());
963 }
964
965 for _ in 0..num_operations {
966 let splice_end = rng.random_range(0..tree.extent::<Count>(&()).0 + 1);
967 let splice_start = rng.random_range(0..splice_end + 1);
968 let count = rng.random_range(0..10);
969 let tree_end = tree.extent::<Count>(&());
970 let new_items = rng
971 .sample_iter(StandardUniform)
972 .take(count)
973 .collect::<Vec<u8>>();
974
975 let mut reference_items = tree.items(&());
976 reference_items.splice(splice_start..splice_end, new_items.clone());
977
978 tree = {
979 let mut cursor = tree.cursor::<Count>(&());
980 let mut new_tree = cursor.slice(&Count(splice_start), Bias::Right);
981 if rng.random() {
982 new_tree.extend(new_items, &());
983 } else {
984 new_tree.par_extend(new_items, &());
985 }
986 cursor.seek(&Count(splice_end), Bias::Right);
987 new_tree.append(cursor.slice(&tree_end, Bias::Right), &());
988 new_tree
989 };
990
991 assert_eq!(tree.items(&()), reference_items);
992 assert_eq!(
993 tree.iter().collect::<Vec<_>>(),
994 tree.cursor::<()>(&()).collect::<Vec<_>>()
995 );
996
997 log::info!("tree items: {:?}", tree.items(&()));
998
999 let mut filter_cursor =
1000 tree.filter::<_, Count>(&(), |summary| summary.contains_even);
1001 let expected_filtered_items = tree
1002 .items(&())
1003 .into_iter()
1004 .enumerate()
1005 .filter(|(_, item)| (item & 1) == 0)
1006 .collect::<Vec<_>>();
1007
1008 let mut item_ix = if rng.random() {
1009 filter_cursor.next();
1010 0
1011 } else {
1012 filter_cursor.prev();
1013 expected_filtered_items.len().saturating_sub(1)
1014 };
1015 while item_ix < expected_filtered_items.len() {
1016 log::info!("filter_cursor, item_ix: {}", item_ix);
1017 let actual_item = filter_cursor.item().unwrap();
1018 let (reference_index, reference_item) = expected_filtered_items[item_ix];
1019 assert_eq!(actual_item, &reference_item);
1020 assert_eq!(filter_cursor.start().0, reference_index);
1021 log::info!("next");
1022 filter_cursor.next();
1023 item_ix += 1;
1024
1025 while item_ix > 0 && rng.random_bool(0.2) {
1026 log::info!("prev");
1027 filter_cursor.prev();
1028 item_ix -= 1;
1029
1030 if item_ix == 0 && rng.random_bool(0.2) {
1031 filter_cursor.prev();
1032 assert_eq!(filter_cursor.item(), None);
1033 assert_eq!(filter_cursor.start().0, 0);
1034 filter_cursor.next();
1035 }
1036 }
1037 }
1038 assert_eq!(filter_cursor.item(), None);
1039
1040 let mut before_start = false;
1041 let mut cursor = tree.cursor::<Count>(&());
1042 let start_pos = rng.random_range(0..=reference_items.len());
1043 cursor.seek(&Count(start_pos), Bias::Right);
1044 let mut pos = rng.random_range(start_pos..=reference_items.len());
1045 cursor.seek_forward(&Count(pos), Bias::Right);
1046
1047 for i in 0..10 {
1048 assert_eq!(cursor.start().0, pos);
1049
1050 if pos > 0 {
1051 assert_eq!(cursor.prev_item().unwrap(), &reference_items[pos - 1]);
1052 } else {
1053 assert_eq!(cursor.prev_item(), None);
1054 }
1055
1056 if pos < reference_items.len() && !before_start {
1057 assert_eq!(cursor.item().unwrap(), &reference_items[pos]);
1058 } else {
1059 assert_eq!(cursor.item(), None);
1060 }
1061
1062 if before_start {
1063 assert_eq!(cursor.next_item(), reference_items.first());
1064 } else if pos + 1 < reference_items.len() {
1065 assert_eq!(cursor.next_item().unwrap(), &reference_items[pos + 1]);
1066 } else {
1067 assert_eq!(cursor.next_item(), None);
1068 }
1069
1070 if i < 5 {
1071 cursor.next();
1072 if pos < reference_items.len() {
1073 pos += 1;
1074 before_start = false;
1075 }
1076 } else {
1077 cursor.prev();
1078 if pos == 0 {
1079 before_start = true;
1080 }
1081 pos = pos.saturating_sub(1);
1082 }
1083 }
1084 }
1085
1086 for _ in 0..10 {
1087 let end = rng.random_range(0..tree.extent::<Count>(&()).0 + 1);
1088 let start = rng.random_range(0..end + 1);
1089 let start_bias = if rng.random() {
1090 Bias::Left
1091 } else {
1092 Bias::Right
1093 };
1094 let end_bias = if rng.random() {
1095 Bias::Left
1096 } else {
1097 Bias::Right
1098 };
1099
1100 let mut cursor = tree.cursor::<Count>(&());
1101 cursor.seek(&Count(start), start_bias);
1102 let slice = cursor.slice(&Count(end), end_bias);
1103
1104 cursor.seek(&Count(start), start_bias);
1105 let summary = cursor.summary::<_, Sum>(&Count(end), end_bias);
1106
1107 assert_eq!(summary.0, slice.summary().sum);
1108 }
1109 }
1110 }
1111
1112 #[test]
1113 fn test_cursor() {
1114 // Empty tree
1115 let tree = SumTree::<u8>::default();
1116 let mut cursor = tree.cursor::<IntegersSummary>(&());
1117 assert_eq!(
1118 cursor.slice(&Count(0), Bias::Right).items(&()),
1119 Vec::<u8>::new()
1120 );
1121 assert_eq!(cursor.item(), None);
1122 assert_eq!(cursor.prev_item(), None);
1123 assert_eq!(cursor.next_item(), None);
1124 assert_eq!(cursor.start().sum, 0);
1125 cursor.prev();
1126 assert_eq!(cursor.item(), None);
1127 assert_eq!(cursor.prev_item(), None);
1128 assert_eq!(cursor.next_item(), None);
1129 assert_eq!(cursor.start().sum, 0);
1130 cursor.next();
1131 assert_eq!(cursor.item(), None);
1132 assert_eq!(cursor.prev_item(), None);
1133 assert_eq!(cursor.next_item(), None);
1134 assert_eq!(cursor.start().sum, 0);
1135
1136 // Single-element tree
1137 let mut tree = SumTree::<u8>::default();
1138 tree.extend(vec![1], &());
1139 let mut cursor = tree.cursor::<IntegersSummary>(&());
1140 assert_eq!(
1141 cursor.slice(&Count(0), Bias::Right).items(&()),
1142 Vec::<u8>::new()
1143 );
1144 assert_eq!(cursor.item(), Some(&1));
1145 assert_eq!(cursor.prev_item(), None);
1146 assert_eq!(cursor.next_item(), None);
1147 assert_eq!(cursor.start().sum, 0);
1148
1149 cursor.next();
1150 assert_eq!(cursor.item(), None);
1151 assert_eq!(cursor.prev_item(), Some(&1));
1152 assert_eq!(cursor.next_item(), None);
1153 assert_eq!(cursor.start().sum, 1);
1154
1155 cursor.prev();
1156 assert_eq!(cursor.item(), Some(&1));
1157 assert_eq!(cursor.prev_item(), None);
1158 assert_eq!(cursor.next_item(), None);
1159 assert_eq!(cursor.start().sum, 0);
1160
1161 let mut cursor = tree.cursor::<IntegersSummary>(&());
1162 assert_eq!(cursor.slice(&Count(1), Bias::Right).items(&()), [1]);
1163 assert_eq!(cursor.item(), None);
1164 assert_eq!(cursor.prev_item(), Some(&1));
1165 assert_eq!(cursor.next_item(), None);
1166 assert_eq!(cursor.start().sum, 1);
1167
1168 cursor.seek(&Count(0), Bias::Right);
1169 assert_eq!(
1170 cursor
1171 .slice(&tree.extent::<Count>(&()), Bias::Right)
1172 .items(&()),
1173 [1]
1174 );
1175 assert_eq!(cursor.item(), None);
1176 assert_eq!(cursor.prev_item(), Some(&1));
1177 assert_eq!(cursor.next_item(), None);
1178 assert_eq!(cursor.start().sum, 1);
1179
1180 // Multiple-element tree
1181 let mut tree = SumTree::default();
1182 tree.extend(vec![1, 2, 3, 4, 5, 6], &());
1183 let mut cursor = tree.cursor::<IntegersSummary>(&());
1184
1185 assert_eq!(cursor.slice(&Count(2), Bias::Right).items(&()), [1, 2]);
1186 assert_eq!(cursor.item(), Some(&3));
1187 assert_eq!(cursor.prev_item(), Some(&2));
1188 assert_eq!(cursor.next_item(), Some(&4));
1189 assert_eq!(cursor.start().sum, 3);
1190
1191 cursor.next();
1192 assert_eq!(cursor.item(), Some(&4));
1193 assert_eq!(cursor.prev_item(), Some(&3));
1194 assert_eq!(cursor.next_item(), Some(&5));
1195 assert_eq!(cursor.start().sum, 6);
1196
1197 cursor.next();
1198 assert_eq!(cursor.item(), Some(&5));
1199 assert_eq!(cursor.prev_item(), Some(&4));
1200 assert_eq!(cursor.next_item(), Some(&6));
1201 assert_eq!(cursor.start().sum, 10);
1202
1203 cursor.next();
1204 assert_eq!(cursor.item(), Some(&6));
1205 assert_eq!(cursor.prev_item(), Some(&5));
1206 assert_eq!(cursor.next_item(), None);
1207 assert_eq!(cursor.start().sum, 15);
1208
1209 cursor.next();
1210 cursor.next();
1211 assert_eq!(cursor.item(), None);
1212 assert_eq!(cursor.prev_item(), Some(&6));
1213 assert_eq!(cursor.next_item(), None);
1214 assert_eq!(cursor.start().sum, 21);
1215
1216 cursor.prev();
1217 assert_eq!(cursor.item(), Some(&6));
1218 assert_eq!(cursor.prev_item(), Some(&5));
1219 assert_eq!(cursor.next_item(), None);
1220 assert_eq!(cursor.start().sum, 15);
1221
1222 cursor.prev();
1223 assert_eq!(cursor.item(), Some(&5));
1224 assert_eq!(cursor.prev_item(), Some(&4));
1225 assert_eq!(cursor.next_item(), Some(&6));
1226 assert_eq!(cursor.start().sum, 10);
1227
1228 cursor.prev();
1229 assert_eq!(cursor.item(), Some(&4));
1230 assert_eq!(cursor.prev_item(), Some(&3));
1231 assert_eq!(cursor.next_item(), Some(&5));
1232 assert_eq!(cursor.start().sum, 6);
1233
1234 cursor.prev();
1235 assert_eq!(cursor.item(), Some(&3));
1236 assert_eq!(cursor.prev_item(), Some(&2));
1237 assert_eq!(cursor.next_item(), Some(&4));
1238 assert_eq!(cursor.start().sum, 3);
1239
1240 cursor.prev();
1241 assert_eq!(cursor.item(), Some(&2));
1242 assert_eq!(cursor.prev_item(), Some(&1));
1243 assert_eq!(cursor.next_item(), Some(&3));
1244 assert_eq!(cursor.start().sum, 1);
1245
1246 cursor.prev();
1247 assert_eq!(cursor.item(), Some(&1));
1248 assert_eq!(cursor.prev_item(), None);
1249 assert_eq!(cursor.next_item(), Some(&2));
1250 assert_eq!(cursor.start().sum, 0);
1251
1252 cursor.prev();
1253 assert_eq!(cursor.item(), None);
1254 assert_eq!(cursor.prev_item(), None);
1255 assert_eq!(cursor.next_item(), Some(&1));
1256 assert_eq!(cursor.start().sum, 0);
1257
1258 cursor.next();
1259 assert_eq!(cursor.item(), Some(&1));
1260 assert_eq!(cursor.prev_item(), None);
1261 assert_eq!(cursor.next_item(), Some(&2));
1262 assert_eq!(cursor.start().sum, 0);
1263
1264 let mut cursor = tree.cursor::<IntegersSummary>(&());
1265 assert_eq!(
1266 cursor
1267 .slice(&tree.extent::<Count>(&()), Bias::Right)
1268 .items(&()),
1269 tree.items(&())
1270 );
1271 assert_eq!(cursor.item(), None);
1272 assert_eq!(cursor.prev_item(), Some(&6));
1273 assert_eq!(cursor.next_item(), None);
1274 assert_eq!(cursor.start().sum, 21);
1275
1276 cursor.seek(&Count(3), Bias::Right);
1277 assert_eq!(
1278 cursor
1279 .slice(&tree.extent::<Count>(&()), Bias::Right)
1280 .items(&()),
1281 [4, 5, 6]
1282 );
1283 assert_eq!(cursor.item(), None);
1284 assert_eq!(cursor.prev_item(), Some(&6));
1285 assert_eq!(cursor.next_item(), None);
1286 assert_eq!(cursor.start().sum, 21);
1287
1288 // Seeking can bias left or right
1289 cursor.seek(&Count(1), Bias::Left);
1290 assert_eq!(cursor.item(), Some(&1));
1291 cursor.seek(&Count(1), Bias::Right);
1292 assert_eq!(cursor.item(), Some(&2));
1293
1294 // Slicing without resetting starts from where the cursor is parked at.
1295 cursor.seek(&Count(1), Bias::Right);
1296 assert_eq!(cursor.slice(&Count(3), Bias::Right).items(&()), vec![2, 3]);
1297 assert_eq!(cursor.slice(&Count(6), Bias::Left).items(&()), vec![4, 5]);
1298 assert_eq!(cursor.slice(&Count(6), Bias::Right).items(&()), vec![6]);
1299 }
1300
1301 #[test]
1302 fn test_edit() {
1303 let mut tree = SumTree::<u8>::default();
1304
1305 let removed = tree.edit(vec![Edit::Insert(1), Edit::Insert(2), Edit::Insert(0)], &());
1306 assert_eq!(tree.items(&()), vec![0, 1, 2]);
1307 assert_eq!(removed, Vec::<u8>::new());
1308 assert_eq!(tree.get(&0, &()), Some(&0));
1309 assert_eq!(tree.get(&1, &()), Some(&1));
1310 assert_eq!(tree.get(&2, &()), Some(&2));
1311 assert_eq!(tree.get(&4, &()), None);
1312
1313 let removed = tree.edit(vec![Edit::Insert(2), Edit::Insert(4), Edit::Remove(0)], &());
1314 assert_eq!(tree.items(&()), vec![1, 2, 4]);
1315 assert_eq!(removed, vec![0, 2]);
1316 assert_eq!(tree.get(&0, &()), None);
1317 assert_eq!(tree.get(&1, &()), Some(&1));
1318 assert_eq!(tree.get(&2, &()), Some(&2));
1319 assert_eq!(tree.get(&4, &()), Some(&4));
1320 }
1321
1322 #[test]
1323 fn test_from_iter() {
1324 assert_eq!(
1325 SumTree::from_iter(0..100, &()).items(&()),
1326 (0..100).collect::<Vec<_>>()
1327 );
1328
1329 // Ensure `from_iter` works correctly when the given iterator restarts
1330 // after calling `next` if `None` was already returned.
1331 let mut ix = 0;
1332 let iterator = std::iter::from_fn(|| {
1333 ix = (ix + 1) % 2;
1334 if ix == 1 { Some(1) } else { None }
1335 });
1336 assert_eq!(SumTree::from_iter(iterator, &()).items(&()), vec![1]);
1337 }
1338
1339 #[derive(Clone, Default, Debug)]
1340 pub struct IntegersSummary {
1341 count: usize,
1342 sum: usize,
1343 contains_even: bool,
1344 max: u8,
1345 }
1346
1347 #[derive(Ord, PartialOrd, Default, Eq, PartialEq, Clone, Debug)]
1348 struct Count(usize);
1349
1350 #[derive(Ord, PartialOrd, Default, Eq, PartialEq, Clone, Debug)]
1351 struct Sum(usize);
1352
1353 impl Item for u8 {
1354 type Summary = IntegersSummary;
1355
1356 fn summary(&self, _cx: &()) -> Self::Summary {
1357 IntegersSummary {
1358 count: 1,
1359 sum: *self as usize,
1360 contains_even: (*self & 1) == 0,
1361 max: *self,
1362 }
1363 }
1364 }
1365
1366 impl KeyedItem for u8 {
1367 type Key = u8;
1368
1369 fn key(&self) -> Self::Key {
1370 *self
1371 }
1372 }
1373
1374 impl Summary for IntegersSummary {
1375 type Context = ();
1376
1377 fn zero(_cx: &()) -> Self {
1378 Default::default()
1379 }
1380
1381 fn add_summary(&mut self, other: &Self, _: &()) {
1382 self.count += other.count;
1383 self.sum += other.sum;
1384 self.contains_even |= other.contains_even;
1385 self.max = cmp::max(self.max, other.max);
1386 }
1387 }
1388
1389 impl Dimension<'_, IntegersSummary> for u8 {
1390 fn zero(_cx: &()) -> Self {
1391 Default::default()
1392 }
1393
1394 fn add_summary(&mut self, summary: &IntegersSummary, _: &()) {
1395 *self = summary.max;
1396 }
1397 }
1398
1399 impl Dimension<'_, IntegersSummary> for Count {
1400 fn zero(_cx: &()) -> Self {
1401 Default::default()
1402 }
1403
1404 fn add_summary(&mut self, summary: &IntegersSummary, _: &()) {
1405 self.0 += summary.count;
1406 }
1407 }
1408
1409 impl SeekTarget<'_, IntegersSummary, IntegersSummary> for Count {
1410 fn cmp(&self, cursor_location: &IntegersSummary, _: &()) -> Ordering {
1411 self.0.cmp(&cursor_location.count)
1412 }
1413 }
1414
1415 impl Dimension<'_, IntegersSummary> for Sum {
1416 fn zero(_cx: &()) -> Self {
1417 Default::default()
1418 }
1419
1420 fn add_summary(&mut self, summary: &IntegersSummary, _: &()) {
1421 self.0 += summary.sum;
1422 }
1423 }
1424}