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