Skip to main content

sum_tree/
sum_tree.rs

1mod cursor;
2#[cfg(any(test, feature = "test-support"))]
3pub mod property_test;
4mod tree_map;
5
6pub use cursor::{Cursor, FilterCursor, Iter};
7use heapless::Vec as ArrayVec;
8#[cfg(any(test, feature = "rayon"))]
9use rayon::iter::{IndexedParallelIterator, IntoParallelIterator, ParallelIterator as _};
10use std::marker::PhantomData;
11use std::mem;
12use std::{cmp::Ordering, fmt, iter::FromIterator, sync::Arc};
13pub use tree_map::{MapSeekTarget, TreeMap, TreeSet};
14use ztracing::instrument;
15
16#[cfg(test)]
17pub const TREE_BASE: usize = 2;
18#[cfg(not(test))]
19pub const TREE_BASE: usize = 6;
20
21// Helper for when we cannot use ArrayVec::<T>::push().unwrap() as T doesn't impl Debug
22trait CapacityResultExt {
23    fn unwrap_oob(self);
24}
25
26impl<T> CapacityResultExt for Result<(), T> {
27    fn unwrap_oob(self) {
28        self.unwrap_or_else(|_| panic!("item should fit into fixed size ArrayVec"))
29    }
30}
31
32/// An item that can be stored in a [`SumTree`]
33///
34/// Must be summarized by a type that implements [`Summary`]
35pub trait Item: Clone {
36    type Summary: Summary;
37
38    fn summary(&self, cx: <Self::Summary as Summary>::Context<'_>) -> Self::Summary;
39}
40
41/// An [`Item`] whose summary has a specific key that can be used to identify it
42pub trait KeyedItem: Item {
43    type Key: for<'a> Dimension<'a, Self::Summary> + Ord;
44
45    fn key(&self) -> Self::Key;
46}
47
48/// A type that describes the Sum of all [`Item`]s in a subtree of the [`SumTree`]
49///
50/// Each Summary type can have multiple [`Dimension`]s that it measures,
51/// which can be used to navigate the tree
52pub trait Summary: Clone {
53    type Context<'a>: Copy;
54    fn zero<'a>(cx: Self::Context<'a>) -> Self;
55    fn add_summary<'a>(&mut self, summary: &Self, cx: Self::Context<'a>);
56}
57
58pub trait ContextLessSummary: Clone {
59    fn zero() -> Self;
60    fn add_summary(&mut self, summary: &Self);
61}
62
63impl<T: ContextLessSummary> Summary for T {
64    type Context<'a> = ();
65
66    fn zero<'a>((): ()) -> Self {
67        T::zero()
68    }
69
70    fn add_summary<'a>(&mut self, summary: &Self, (): ()) {
71        T::add_summary(self, summary)
72    }
73}
74
75#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
76pub struct NoSummary;
77
78/// Catch-all implementation for when you need something that implements [`Summary`] without a specific type.
79/// We implement it on a `NoSummary` instead of re-using `()`, as that avoids blanket impl collisions with `impl<T: Summary> Dimension for T`
80/// (as we also need unit type to be a fill-in dimension)
81impl ContextLessSummary for NoSummary {
82    fn zero() -> Self {
83        NoSummary
84    }
85
86    fn add_summary(&mut self, _: &Self) {}
87}
88
89/// Each [`Summary`] type can have more than one [`Dimension`] type that it measures.
90///
91/// You can use dimensions to seek to a specific location in the [`SumTree`]
92///
93/// # Example:
94/// Zed's rope has a `TextSummary` type that summarizes lines, characters, and bytes.
95/// Each of these are different dimensions we may want to seek to
96pub trait Dimension<'a, S: Summary>: Clone {
97    fn zero(cx: S::Context<'_>) -> Self;
98
99    fn add_summary(&mut self, summary: &'a S, cx: S::Context<'_>);
100    #[must_use]
101    fn with_added_summary(mut self, summary: &'a S, cx: S::Context<'_>) -> Self {
102        self.add_summary(summary, cx);
103        self
104    }
105
106    fn from_summary(summary: &'a S, cx: S::Context<'_>) -> Self {
107        let mut dimension = Self::zero(cx);
108        dimension.add_summary(summary, cx);
109        dimension
110    }
111}
112
113impl<'a, T: Summary> Dimension<'a, T> for T {
114    fn zero(cx: T::Context<'_>) -> Self {
115        Summary::zero(cx)
116    }
117
118    fn add_summary(&mut self, summary: &'a T, cx: T::Context<'_>) {
119        Summary::add_summary(self, summary, cx);
120    }
121}
122
123pub trait SeekTarget<'a, S: Summary, D: Dimension<'a, S>> {
124    fn cmp(&self, cursor_location: &D, cx: S::Context<'_>) -> Ordering;
125}
126
127impl<'a, S: Summary, D: Dimension<'a, S> + Ord> SeekTarget<'a, S, D> for D {
128    fn cmp(&self, cursor_location: &Self, _: S::Context<'_>) -> Ordering {
129        Ord::cmp(self, cursor_location)
130    }
131}
132
133impl<'a, T: Summary> Dimension<'a, T> for () {
134    fn zero(_: T::Context<'_>) -> Self {}
135
136    fn add_summary(&mut self, _: &'a T, _: T::Context<'_>) {}
137}
138
139#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, PartialOrd, Ord)]
140pub struct Dimensions<D1, D2, D3 = ()>(pub D1, pub D2, pub D3);
141
142impl<'a, T: Summary, D1: Dimension<'a, T>, D2: Dimension<'a, T>, D3: Dimension<'a, T>>
143    Dimension<'a, T> for Dimensions<D1, D2, D3>
144{
145    fn zero(cx: T::Context<'_>) -> Self {
146        Dimensions(D1::zero(cx), D2::zero(cx), D3::zero(cx))
147    }
148
149    fn add_summary(&mut self, summary: &'a T, cx: T::Context<'_>) {
150        self.0.add_summary(summary, cx);
151        self.1.add_summary(summary, cx);
152        self.2.add_summary(summary, cx);
153    }
154}
155
156impl<'a, S, D1, D2, D3> SeekTarget<'a, S, Dimensions<D1, D2, D3>> for D1
157where
158    S: Summary,
159    D1: SeekTarget<'a, S, D1> + Dimension<'a, S>,
160    D2: Dimension<'a, S>,
161    D3: Dimension<'a, S>,
162{
163    fn cmp(&self, cursor_location: &Dimensions<D1, D2, D3>, cx: S::Context<'_>) -> Ordering {
164        self.cmp(&cursor_location.0, cx)
165    }
166}
167
168/// Bias is used to settle ambiguities when determining positions in an ordered sequence.
169///
170/// The primary use case is for text, where Bias influences
171/// which character an offset or anchor is associated with.
172///
173/// # Examples
174/// Given the buffer `AˇBCD`:
175/// - The offset of the cursor is 1
176/// - [Bias::Left] would attach the cursor to the character `A`
177/// - [Bias::Right] would attach the cursor to the character `B`
178///
179/// Given the buffer `A«BCˇ»D`:
180/// - The offset of the cursor is 3, and the selection is from 1 to 3
181/// - The left anchor of the selection has [Bias::Right], attaching it to the character `B`
182/// - The right anchor of the selection has [Bias::Left], attaching it to the character `C`
183///
184/// Given the buffer `{ˇ<...>`, where `<...>` is a folded region:
185/// - The display offset of the cursor is 1, but the offset in the buffer is determined by the bias
186/// - [Bias::Left] would attach the cursor to the character `{`, with a buffer offset of 1
187/// - [Bias::Right] would attach the cursor to the first character of the folded region,
188///   and the buffer offset would be the offset of the first character of the folded region
189#[derive(Copy, Clone, Eq, PartialEq, PartialOrd, Ord, Debug, Hash, Default)]
190pub enum Bias {
191    /// Attach to the character on the left
192    #[default]
193    Left,
194    /// Attach to the character on the right
195    Right,
196}
197
198impl Bias {
199    pub fn invert(self) -> Self {
200        match self {
201            Self::Left => Self::Right,
202            Self::Right => Self::Left,
203        }
204    }
205}
206
207/// A B+ tree in which each leaf node contains `Item`s of type `T` and a `Summary`s for each `Item`.
208/// Each internal node contains a `Summary` of the items in its subtree.
209///
210/// The maximum number of items per node is `TREE_BASE * 2`.
211///
212/// Any [`Dimension`] supported by the [`Summary`] type can be used to seek to a specific location in the tree.
213#[derive(Clone)]
214pub struct SumTree<T: Item>(Arc<Node<T>>);
215
216impl<T> fmt::Debug for SumTree<T>
217where
218    T: fmt::Debug + Item,
219    T::Summary: fmt::Debug,
220{
221    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
222        f.debug_tuple("SumTree").field(&self.0).finish()
223    }
224}
225
226impl<T: Item> SumTree<T> {
227    pub fn new(cx: <T::Summary as Summary>::Context<'_>) -> Self {
228        SumTree(Arc::new(Node::Leaf {
229            summary: <T::Summary as Summary>::zero(cx),
230            items: ArrayVec::new(),
231            item_summaries: ArrayVec::new(),
232        }))
233    }
234
235    /// 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.
236    pub fn from_summary(summary: T::Summary) -> Self {
237        SumTree(Arc::new(Node::Leaf {
238            summary,
239            items: ArrayVec::new(),
240            item_summaries: ArrayVec::new(),
241        }))
242    }
243
244    pub fn from_item(item: T, cx: <T::Summary as Summary>::Context<'_>) -> Self {
245        let mut tree = Self::new(cx);
246        tree.push(item, cx);
247        tree
248    }
249
250    pub fn from_iter<I: IntoIterator<Item = T>>(
251        iter: I,
252        cx: <T::Summary as Summary>::Context<'_>,
253    ) -> Self {
254        let mut nodes = Vec::new();
255
256        let mut iter = iter.into_iter().fuse().peekable();
257        while iter.peek().is_some() {
258            let items: ArrayVec<T, { 2 * TREE_BASE }, u8> =
259                iter.by_ref().take(2 * TREE_BASE).collect();
260            let item_summaries: ArrayVec<T::Summary, { 2 * TREE_BASE }, u8> =
261                items.iter().map(|item| item.summary(cx)).collect();
262
263            let mut summary = item_summaries[0].clone();
264            for item_summary in &item_summaries[1..] {
265                <T::Summary as Summary>::add_summary(&mut summary, item_summary, cx);
266            }
267
268            nodes.push(SumTree(Arc::new(Node::Leaf {
269                summary,
270                items,
271                item_summaries,
272            })));
273        }
274
275        let mut parent_nodes = Vec::new();
276        let mut height = 0;
277        while nodes.len() > 1 {
278            height += 1;
279            let mut current_parent_node = None;
280            for child_node in nodes.drain(..) {
281                let parent_node = current_parent_node.get_or_insert_with(|| {
282                    SumTree(Arc::new(Node::Internal {
283                        summary: <T::Summary as Summary>::zero(cx),
284                        height,
285                        child_summaries: ArrayVec::new(),
286                        child_trees: ArrayVec::new(),
287                    }))
288                });
289                let Node::Internal {
290                    summary,
291                    child_summaries,
292                    child_trees,
293                    ..
294                } = Arc::get_mut(&mut parent_node.0).unwrap()
295                else {
296                    unreachable!()
297                };
298                let child_summary = child_node.summary();
299                <T::Summary as Summary>::add_summary(summary, child_summary, cx);
300                child_summaries.push(child_summary.clone()).unwrap_oob();
301                child_trees.push(child_node.clone()).unwrap_oob();
302
303                if child_trees.len() == 2 * TREE_BASE {
304                    parent_nodes.extend(current_parent_node.take());
305                }
306            }
307            parent_nodes.extend(current_parent_node.take());
308            mem::swap(&mut nodes, &mut parent_nodes);
309        }
310
311        if nodes.is_empty() {
312            Self::new(cx)
313        } else {
314            debug_assert_eq!(nodes.len(), 1);
315            nodes.pop().unwrap()
316        }
317    }
318
319    #[cfg(any(test, feature = "rayon"))]
320    pub fn from_par_iter<I, Iter>(iter: I, cx: <T::Summary as Summary>::Context<'_>) -> Self
321    where
322        I: IntoParallelIterator<Iter = Iter>,
323        Iter: IndexedParallelIterator<Item = T>,
324        T: Send + Sync,
325        T::Summary: Send + Sync,
326        for<'a> <T::Summary as Summary>::Context<'a>: Sync,
327    {
328        let mut nodes = iter
329            .into_par_iter()
330            .chunks(2 * TREE_BASE)
331            .map(|items| {
332                let items: ArrayVec<T, { 2 * TREE_BASE }, u8> = items.into_iter().collect();
333                let item_summaries: ArrayVec<T::Summary, { 2 * TREE_BASE }, u8> =
334                    items.iter().map(|item| item.summary(cx)).collect();
335                let mut summary = item_summaries[0].clone();
336                for item_summary in &item_summaries[1..] {
337                    <T::Summary as Summary>::add_summary(&mut summary, item_summary, cx);
338                }
339                SumTree(Arc::new(Node::Leaf {
340                    summary,
341                    items,
342                    item_summaries,
343                }))
344            })
345            .collect::<Vec<_>>();
346
347        let mut height = 0;
348        while nodes.len() > 1 {
349            height += 1;
350            nodes = nodes
351                .into_par_iter()
352                .chunks(2 * TREE_BASE)
353                .map(|child_nodes| {
354                    let child_trees: ArrayVec<SumTree<T>, { 2 * TREE_BASE }, u8> =
355                        child_nodes.into_iter().collect();
356                    let child_summaries: ArrayVec<T::Summary, { 2 * TREE_BASE }, u8> = child_trees
357                        .iter()
358                        .map(|child_tree| child_tree.summary().clone())
359                        .collect();
360                    let mut summary = child_summaries[0].clone();
361                    for child_summary in &child_summaries[1..] {
362                        <T::Summary as Summary>::add_summary(&mut summary, child_summary, cx);
363                    }
364                    SumTree(Arc::new(Node::Internal {
365                        height,
366                        summary,
367                        child_summaries,
368                        child_trees,
369                    }))
370                })
371                .collect::<Vec<_>>();
372        }
373
374        if nodes.is_empty() {
375            Self::new(cx)
376        } else {
377            debug_assert_eq!(nodes.len(), 1);
378            nodes.pop().unwrap()
379        }
380    }
381
382    #[allow(unused)]
383    pub fn items<'a>(&'a self, cx: <T::Summary as Summary>::Context<'a>) -> Vec<T> {
384        let mut items = Vec::new();
385        let mut cursor = self.cursor::<()>(cx);
386        cursor.next();
387        while let Some(item) = cursor.item() {
388            items.push(item.clone());
389            cursor.next();
390        }
391        items
392    }
393
394    pub fn iter(&self) -> Iter<'_, T> {
395        Iter::new(self)
396    }
397
398    /// A more efficient version of `Cursor::new()` + `Cursor::seek()` + `Cursor::item()`.
399    ///
400    /// Only returns the item that exactly has the target match.
401    #[instrument(skip_all)]
402    pub fn find_exact<'a, 'slf, D, Target>(
403        &'slf self,
404        cx: <T::Summary as Summary>::Context<'a>,
405        target: &Target,
406        bias: Bias,
407    ) -> (D, D, Option<&'slf T>)
408    where
409        D: Dimension<'slf, T::Summary>,
410        Target: SeekTarget<'slf, T::Summary, D>,
411    {
412        let tree_end = D::zero(cx).with_added_summary(self.summary(), cx);
413        let comparison = target.cmp(&tree_end, cx);
414        if comparison == Ordering::Greater || (comparison == Ordering::Equal && bias == Bias::Right)
415        {
416            return (tree_end.clone(), tree_end, None);
417        }
418
419        let mut pos = D::zero(cx);
420        return match Self::find_iterate::<_, _, true>(cx, target, bias, &mut pos, self) {
421            Some((item, end)) => (pos, end, Some(item)),
422            None => (pos.clone(), pos, None),
423        };
424    }
425
426    /// A more efficient version of `Cursor::new()` + `Cursor::seek()` + `Cursor::item()`
427    #[instrument(skip_all)]
428    pub fn find<'a, 'slf, D, Target>(
429        &'slf self,
430        cx: <T::Summary as Summary>::Context<'a>,
431        target: &Target,
432        bias: Bias,
433    ) -> (D, D, Option<&'slf T>)
434    where
435        D: Dimension<'slf, T::Summary>,
436        Target: SeekTarget<'slf, T::Summary, D>,
437    {
438        let tree_end = D::zero(cx).with_added_summary(self.summary(), cx);
439        let comparison = target.cmp(&tree_end, cx);
440        if comparison == Ordering::Greater || (comparison == Ordering::Equal && bias == Bias::Right)
441        {
442            return (tree_end.clone(), tree_end, None);
443        }
444
445        let mut pos = D::zero(cx);
446        return match Self::find_iterate::<_, _, false>(cx, target, bias, &mut pos, self) {
447            Some((item, end)) => (pos, end, Some(item)),
448            None => (pos.clone(), pos, None),
449        };
450    }
451
452    fn find_iterate<'tree, 'a, D, Target, const EXACT: bool>(
453        cx: <T::Summary as Summary>::Context<'a>,
454        target: &Target,
455        bias: Bias,
456        position: &mut D,
457        mut this: &'tree SumTree<T>,
458    ) -> Option<(&'tree T, D)>
459    where
460        D: Dimension<'tree, T::Summary>,
461        Target: SeekTarget<'tree, T::Summary, D>,
462    {
463        'iterate: loop {
464            match &*this.0 {
465                Node::Internal {
466                    child_summaries,
467                    child_trees,
468                    ..
469                } => {
470                    for (child_tree, child_summary) in child_trees.iter().zip(child_summaries) {
471                        let child_end = position.clone().with_added_summary(child_summary, cx);
472
473                        let comparison = target.cmp(&child_end, cx);
474                        let target_in_child = comparison == Ordering::Less
475                            || (comparison == Ordering::Equal && bias == Bias::Left);
476                        if target_in_child {
477                            this = child_tree;
478                            continue 'iterate;
479                        }
480                        *position = child_end;
481                    }
482                }
483                Node::Leaf {
484                    items,
485                    item_summaries,
486                    ..
487                } => {
488                    for (item, item_summary) in items.iter().zip(item_summaries) {
489                        let mut child_end = position.clone();
490                        child_end.add_summary(item_summary, cx);
491
492                        let comparison = target.cmp(&child_end, cx);
493                        let entry_found = if EXACT {
494                            comparison == Ordering::Equal
495                        } else {
496                            comparison == Ordering::Less
497                                || (comparison == Ordering::Equal && bias == Bias::Left)
498                        };
499                        if entry_found {
500                            return Some((item, child_end));
501                        }
502
503                        *position = child_end;
504                    }
505                }
506            }
507            return None;
508        }
509    }
510
511    /// A more efficient version of `Cursor::new()` + `Cursor::seek()` + `Cursor::item()`
512    #[instrument(skip_all)]
513    pub fn find_with_prev<'a, 'slf, D, Target>(
514        &'slf self,
515        cx: <T::Summary as Summary>::Context<'a>,
516        target: &Target,
517        bias: Bias,
518    ) -> (D, D, Option<(Option<&'slf T>, &'slf T)>)
519    where
520        D: Dimension<'slf, T::Summary>,
521        Target: SeekTarget<'slf, T::Summary, D>,
522    {
523        let tree_end = D::zero(cx).with_added_summary(self.summary(), cx);
524        let comparison = target.cmp(&tree_end, cx);
525        if comparison == Ordering::Greater || (comparison == Ordering::Equal && bias == Bias::Right)
526        {
527            return (tree_end.clone(), tree_end, None);
528        }
529
530        let mut pos = D::zero(cx);
531        return match Self::find_with_prev_iterate::<_, _, false>(cx, target, bias, &mut pos, self) {
532            Some((prev, item, end)) => (pos, end, Some((prev, item))),
533            None => (pos.clone(), pos, None),
534        };
535    }
536
537    fn find_with_prev_iterate<'tree, 'a, D, Target, const EXACT: bool>(
538        cx: <T::Summary as Summary>::Context<'a>,
539        target: &Target,
540        bias: Bias,
541        position: &mut D,
542        mut this: &'tree SumTree<T>,
543    ) -> Option<(Option<&'tree T>, &'tree T, D)>
544    where
545        D: Dimension<'tree, T::Summary>,
546        Target: SeekTarget<'tree, T::Summary, D>,
547    {
548        let mut prev = None;
549        'iterate: loop {
550            match &*this.0 {
551                Node::Internal {
552                    child_summaries,
553                    child_trees,
554                    ..
555                } => {
556                    for (child_tree, child_summary) in child_trees.iter().zip(child_summaries) {
557                        let child_end = position.clone().with_added_summary(child_summary, cx);
558
559                        let comparison = target.cmp(&child_end, cx);
560                        let target_in_child = comparison == Ordering::Less
561                            || (comparison == Ordering::Equal && bias == Bias::Left);
562                        if target_in_child {
563                            this = child_tree;
564                            continue 'iterate;
565                        }
566                        prev = child_tree.last();
567                        *position = child_end;
568                    }
569                }
570                Node::Leaf {
571                    items,
572                    item_summaries,
573                    ..
574                } => {
575                    for (item, item_summary) in items.iter().zip(item_summaries) {
576                        let mut child_end = position.clone();
577                        child_end.add_summary(item_summary, cx);
578
579                        let comparison = target.cmp(&child_end, cx);
580                        let entry_found = if EXACT {
581                            comparison == Ordering::Equal
582                        } else {
583                            comparison == Ordering::Less
584                                || (comparison == Ordering::Equal && bias == Bias::Left)
585                        };
586                        if entry_found {
587                            return Some((prev, item, child_end));
588                        }
589
590                        prev = Some(item);
591                        *position = child_end;
592                    }
593                }
594            }
595            return None;
596        }
597    }
598
599    pub fn cursor<'a, 'b, D>(
600        &'a self,
601        cx: <T::Summary as Summary>::Context<'b>,
602    ) -> Cursor<'a, 'b, T, D>
603    where
604        D: Dimension<'a, T::Summary>,
605    {
606        Cursor::new(self, cx)
607    }
608
609    /// Note: If the summary type requires a non `()` context, then the filter cursor
610    /// that is returned cannot be used with Rust's iterators.
611    pub fn filter<'a, 'b, F, U>(
612        &'a self,
613        cx: <T::Summary as Summary>::Context<'b>,
614        filter_node: F,
615    ) -> FilterCursor<'a, 'b, F, T, U>
616    where
617        F: FnMut(&T::Summary) -> bool,
618        U: Dimension<'a, T::Summary>,
619    {
620        FilterCursor::new(self, cx, filter_node)
621    }
622
623    #[allow(dead_code)]
624    pub fn first(&self) -> Option<&T> {
625        self.leftmost_leaf().0.items().first()
626    }
627
628    pub fn last(&self) -> Option<&T> {
629        self.rightmost_leaf().0.items().last()
630    }
631
632    pub fn last_summary(&self) -> Option<&T::Summary> {
633        self.rightmost_leaf().0.child_summaries().last()
634    }
635
636    pub fn update_last(
637        &mut self,
638        f: impl FnOnce(&mut T),
639        cx: <T::Summary as Summary>::Context<'_>,
640    ) {
641        self.update_last_recursive(f, cx);
642    }
643
644    fn update_last_recursive(
645        &mut self,
646        f: impl FnOnce(&mut T),
647        cx: <T::Summary as Summary>::Context<'_>,
648    ) -> Option<T::Summary> {
649        match Arc::make_mut(&mut self.0) {
650            Node::Internal {
651                summary,
652                child_summaries,
653                child_trees,
654                ..
655            } => {
656                let last_summary = child_summaries.last_mut().unwrap();
657                let last_child = child_trees.last_mut().unwrap();
658                *last_summary = last_child.update_last_recursive(f, cx).unwrap();
659                *summary = sum(child_summaries.iter(), cx);
660                Some(summary.clone())
661            }
662            Node::Leaf {
663                summary,
664                items,
665                item_summaries,
666            } => {
667                if let Some((item, item_summary)) = items.last_mut().zip(item_summaries.last_mut())
668                {
669                    (f)(item);
670                    *item_summary = item.summary(cx);
671                    *summary = sum(item_summaries.iter(), cx);
672                    Some(summary.clone())
673                } else {
674                    None
675                }
676            }
677        }
678    }
679
680    pub fn update_first(
681        &mut self,
682        f: impl FnOnce(&mut T),
683        cx: <T::Summary as Summary>::Context<'_>,
684    ) {
685        self.update_first_recursive(f, cx);
686    }
687
688    fn update_first_recursive(
689        &mut self,
690        f: impl FnOnce(&mut T),
691        cx: <T::Summary as Summary>::Context<'_>,
692    ) -> Option<T::Summary> {
693        match Arc::make_mut(&mut self.0) {
694            Node::Internal {
695                summary,
696                child_summaries,
697                child_trees,
698                ..
699            } => {
700                let first_summary = child_summaries.first_mut().unwrap();
701                let first_child = child_trees.first_mut().unwrap();
702                *first_summary = first_child.update_first_recursive(f, cx).unwrap();
703                *summary = sum(child_summaries.iter(), cx);
704                Some(summary.clone())
705            }
706            Node::Leaf {
707                summary,
708                items,
709                item_summaries,
710            } => {
711                if let Some((item, item_summary)) =
712                    items.first_mut().zip(item_summaries.first_mut())
713                {
714                    (f)(item);
715                    *item_summary = item.summary(cx);
716                    *summary = sum(item_summaries.iter(), cx);
717                    Some(summary.clone())
718                } else {
719                    None
720                }
721            }
722        }
723    }
724
725    pub fn extent<'a, D: Dimension<'a, T::Summary>>(
726        &'a self,
727        cx: <T::Summary as Summary>::Context<'_>,
728    ) -> D {
729        let mut extent = D::zero(cx);
730        match self.0.as_ref() {
731            Node::Internal { summary, .. } | Node::Leaf { summary, .. } => {
732                extent.add_summary(summary, cx);
733            }
734        }
735        extent
736    }
737
738    pub fn summary(&self) -> &T::Summary {
739        match self.0.as_ref() {
740            Node::Internal { summary, .. } => summary,
741            Node::Leaf { summary, .. } => summary,
742        }
743    }
744
745    pub fn is_empty(&self) -> bool {
746        match self.0.as_ref() {
747            Node::Internal { .. } => false,
748            Node::Leaf { items, .. } => items.is_empty(),
749        }
750    }
751
752    pub fn extend<I>(&mut self, iter: I, cx: <T::Summary as Summary>::Context<'_>)
753    where
754        I: IntoIterator<Item = T>,
755    {
756        self.append(Self::from_iter(iter, cx), cx);
757    }
758
759    #[cfg(any(test, feature = "rayon"))]
760    pub fn par_extend<I, Iter>(&mut self, iter: I, cx: <T::Summary as Summary>::Context<'_>)
761    where
762        I: IntoParallelIterator<Iter = Iter>,
763        Iter: IndexedParallelIterator<Item = T>,
764        T: Send + Sync,
765        T::Summary: Send + Sync,
766        for<'a> <T::Summary as Summary>::Context<'a>: Sync,
767    {
768        self.append(Self::from_par_iter(iter, cx), cx);
769    }
770
771    pub fn push(&mut self, item: T, cx: <T::Summary as Summary>::Context<'_>) {
772        let summary = item.summary(cx);
773        self.append(
774            SumTree(Arc::new(Node::Leaf {
775                summary: summary.clone(),
776                items: ArrayVec::from_iter(Some(item)),
777                item_summaries: ArrayVec::from_iter(Some(summary)),
778            })),
779            cx,
780        );
781    }
782
783    pub fn append(&mut self, mut other: Self, cx: <T::Summary as Summary>::Context<'_>) {
784        if self.is_empty() {
785            *self = other;
786        } else if !other.0.is_leaf() || !other.0.items().is_empty() {
787            if self.0.height() < other.0.height() {
788                if let Some(tree) = Self::append_large(self.clone(), &mut other, cx) {
789                    *self = Self::from_child_trees(tree, other, cx);
790                } else {
791                    *self = other;
792                }
793            } else if let Some(split_tree) = self.push_tree_recursive(other, cx) {
794                *self = Self::from_child_trees(self.clone(), split_tree, cx);
795            }
796        }
797    }
798
799    fn push_tree_recursive(
800        &mut self,
801        other: SumTree<T>,
802        cx: <T::Summary as Summary>::Context<'_>,
803    ) -> Option<SumTree<T>> {
804        match Arc::make_mut(&mut self.0) {
805            Node::Internal {
806                height,
807                summary,
808                child_summaries,
809                child_trees,
810                ..
811            } => {
812                let other_node = other.0.clone();
813                <T::Summary as Summary>::add_summary(summary, other_node.summary(), cx);
814
815                let height_delta = *height - other_node.height();
816                let mut summaries_to_append = ArrayVec::<T::Summary, { 2 * TREE_BASE }, u8>::new();
817                let mut trees_to_append = ArrayVec::<SumTree<T>, { 2 * TREE_BASE }, u8>::new();
818                if height_delta == 0 {
819                    summaries_to_append.extend(other_node.child_summaries().iter().cloned());
820                    trees_to_append.extend(other_node.child_trees().iter().cloned());
821                } else if height_delta == 1 && !other_node.is_underflowing() {
822                    summaries_to_append
823                        .push(other_node.summary().clone())
824                        .unwrap_oob();
825                    trees_to_append.push(other).unwrap_oob();
826                } else {
827                    let tree_to_append = child_trees
828                        .last_mut()
829                        .unwrap()
830                        .push_tree_recursive(other, cx);
831                    *child_summaries.last_mut().unwrap() =
832                        child_trees.last().unwrap().0.summary().clone();
833
834                    if let Some(split_tree) = tree_to_append {
835                        summaries_to_append
836                            .push(split_tree.0.summary().clone())
837                            .unwrap_oob();
838                        trees_to_append.push(split_tree).unwrap_oob();
839                    }
840                }
841
842                let child_count = child_trees.len() + trees_to_append.len();
843                if child_count > 2 * TREE_BASE {
844                    let left_summaries: ArrayVec<_, { 2 * TREE_BASE }, u8>;
845                    let right_summaries: ArrayVec<_, { 2 * TREE_BASE }, u8>;
846                    let left_trees;
847                    let right_trees;
848
849                    let midpoint = (child_count + child_count % 2) / 2;
850                    {
851                        let mut all_summaries = child_summaries
852                            .iter()
853                            .chain(summaries_to_append.iter())
854                            .cloned();
855                        left_summaries = all_summaries.by_ref().take(midpoint).collect();
856                        right_summaries = all_summaries.collect();
857                        let mut all_trees =
858                            child_trees.iter().chain(trees_to_append.iter()).cloned();
859                        left_trees = all_trees.by_ref().take(midpoint).collect();
860                        right_trees = all_trees.collect();
861                    }
862                    *summary = sum(left_summaries.iter(), cx);
863                    *child_summaries = left_summaries;
864                    *child_trees = left_trees;
865
866                    Some(SumTree(Arc::new(Node::Internal {
867                        height: *height,
868                        summary: sum(right_summaries.iter(), cx),
869                        child_summaries: right_summaries,
870                        child_trees: right_trees,
871                    })))
872                } else {
873                    child_summaries.extend(summaries_to_append);
874                    child_trees.extend(trees_to_append);
875                    None
876                }
877            }
878            Node::Leaf {
879                summary,
880                items,
881                item_summaries,
882            } => {
883                let other_node = other.0;
884
885                let child_count = items.len() + other_node.items().len();
886                if child_count > 2 * TREE_BASE {
887                    let left_items;
888                    let right_items;
889                    let left_summaries;
890                    let right_summaries: ArrayVec<T::Summary, { 2 * TREE_BASE }, u8>;
891
892                    let midpoint = (child_count + child_count % 2) / 2;
893                    {
894                        let mut all_items = items.iter().chain(other_node.items().iter()).cloned();
895                        left_items = all_items.by_ref().take(midpoint).collect();
896                        right_items = all_items.collect();
897
898                        let mut all_summaries = item_summaries
899                            .iter()
900                            .chain(other_node.child_summaries())
901                            .cloned();
902                        left_summaries = all_summaries.by_ref().take(midpoint).collect();
903                        right_summaries = all_summaries.collect();
904                    }
905                    *items = left_items;
906                    *item_summaries = left_summaries;
907                    *summary = sum(item_summaries.iter(), cx);
908                    Some(SumTree(Arc::new(Node::Leaf {
909                        items: right_items,
910                        summary: sum(right_summaries.iter(), cx),
911                        item_summaries: right_summaries,
912                    })))
913                } else {
914                    <T::Summary as Summary>::add_summary(summary, other_node.summary(), cx);
915                    items.extend(other_node.items().iter().cloned());
916                    item_summaries.extend(other_node.child_summaries().iter().cloned());
917                    None
918                }
919            }
920        }
921    }
922
923    // appends the `large` tree to a `small` tree, assumes small.height() <= large.height()
924    fn append_large(
925        small: Self,
926        large: &mut Self,
927        cx: <T::Summary as Summary>::Context<'_>,
928    ) -> Option<Self> {
929        if small.0.height() == large.0.height() {
930            if !small.0.is_underflowing() {
931                Some(small)
932            } else {
933                Self::merge_into_right(small, large, cx)
934            }
935        } else {
936            debug_assert!(small.0.height() < large.0.height());
937            let Node::Internal {
938                height,
939                summary,
940                child_summaries,
941                child_trees,
942            } = Arc::make_mut(&mut large.0)
943            else {
944                unreachable!();
945            };
946            let mut full_summary = small.summary().clone();
947            Summary::add_summary(&mut full_summary, summary, cx);
948            *summary = full_summary;
949
950            let first = child_trees.first_mut().unwrap();
951            let res = Self::append_large(small, first, cx);
952            *child_summaries.first_mut().unwrap() = first.summary().clone();
953            if let Some(tree) = res {
954                if child_trees.len() < 2 * TREE_BASE {
955                    child_summaries
956                        .insert(0, tree.summary().clone())
957                        .unwrap_oob();
958                    child_trees.insert(0, tree).unwrap_oob();
959                    None
960                } else {
961                    let new_child_summaries = {
962                        let mut res = ArrayVec::from_iter([tree.summary().clone()]);
963                        res.extend(child_summaries.drain(..TREE_BASE));
964                        res
965                    };
966                    let tree = SumTree(Arc::new(Node::Internal {
967                        height: *height,
968                        summary: sum(new_child_summaries.iter(), cx),
969                        child_summaries: new_child_summaries,
970                        child_trees: {
971                            let mut res = ArrayVec::from_iter([tree]);
972                            res.extend(child_trees.drain(..TREE_BASE));
973                            res
974                        },
975                    }));
976
977                    *summary = sum(child_summaries.iter(), cx);
978                    Some(tree)
979                }
980            } else {
981                None
982            }
983        }
984    }
985
986    // Merge two nodes into `large`.
987    //
988    // `large` will contain the contents of `small` followed by its own data.
989    // If the combined data exceed the node capacity, returns a new node that
990    // holds the first half of the merged items and `large` is left with the
991    // second half
992    //
993    // The nodes must be on the same height
994    // It only makes sense to call this when `small` is underflowing
995    fn merge_into_right(
996        small: Self,
997        large: &mut Self,
998        cx: <<T as Item>::Summary as Summary>::Context<'_>,
999    ) -> Option<SumTree<T>> {
1000        debug_assert_eq!(small.0.height(), large.0.height());
1001        match (small.0.as_ref(), Arc::make_mut(&mut large.0)) {
1002            (
1003                Node::Internal {
1004                    summary: small_summary,
1005                    child_summaries: small_child_summaries,
1006                    child_trees: small_child_trees,
1007                    ..
1008                },
1009                Node::Internal {
1010                    summary,
1011                    child_summaries,
1012                    child_trees,
1013                    height,
1014                },
1015            ) => {
1016                let total_child_count = child_trees.len() + small_child_trees.len();
1017                if total_child_count <= 2 * TREE_BASE {
1018                    let mut all_trees = small_child_trees.clone();
1019                    all_trees.extend(child_trees.drain(..));
1020                    *child_trees = all_trees;
1021
1022                    let mut all_summaries = small_child_summaries.clone();
1023                    all_summaries.extend(child_summaries.drain(..));
1024                    *child_summaries = all_summaries;
1025
1026                    let mut full_summary = small_summary.clone();
1027                    Summary::add_summary(&mut full_summary, summary, cx);
1028                    *summary = full_summary;
1029                    None
1030                } else {
1031                    let midpoint = total_child_count.div_ceil(2);
1032                    let mut all_trees = small_child_trees.iter().chain(child_trees.iter()).cloned();
1033                    let left_trees = all_trees.by_ref().take(midpoint).collect();
1034                    *child_trees = all_trees.collect();
1035
1036                    let mut all_summaries = small_child_summaries
1037                        .iter()
1038                        .chain(child_summaries.iter())
1039                        .cloned();
1040                    let left_summaries: ArrayVec<_, { 2 * TREE_BASE }, u8> =
1041                        all_summaries.by_ref().take(midpoint).collect();
1042                    *child_summaries = all_summaries.collect();
1043
1044                    *summary = sum(child_summaries.iter(), cx);
1045                    Some(SumTree(Arc::new(Node::Internal {
1046                        height: *height,
1047                        summary: sum(left_summaries.iter(), cx),
1048                        child_summaries: left_summaries,
1049                        child_trees: left_trees,
1050                    })))
1051                }
1052            }
1053            (
1054                Node::Leaf {
1055                    summary: small_summary,
1056                    items: small_items,
1057                    item_summaries: small_item_summaries,
1058                },
1059                Node::Leaf {
1060                    summary,
1061                    items,
1062                    item_summaries,
1063                },
1064            ) => {
1065                let total_child_count = small_items.len() + items.len();
1066                if total_child_count <= 2 * TREE_BASE {
1067                    let mut all_items = small_items.clone();
1068                    all_items.extend(items.drain(..));
1069                    *items = all_items;
1070
1071                    let mut all_summaries = small_item_summaries.clone();
1072                    all_summaries.extend(item_summaries.drain(..));
1073                    *item_summaries = all_summaries;
1074
1075                    let mut full_summary = small_summary.clone();
1076                    Summary::add_summary(&mut full_summary, summary, cx);
1077                    *summary = full_summary;
1078                    None
1079                } else {
1080                    let midpoint = total_child_count.div_ceil(2);
1081                    let mut all_items = small_items.iter().chain(items.iter()).cloned();
1082                    let left_items = all_items.by_ref().take(midpoint).collect();
1083                    *items = all_items.collect();
1084
1085                    let mut all_summaries = small_item_summaries
1086                        .iter()
1087                        .chain(item_summaries.iter())
1088                        .cloned();
1089                    let left_summaries: ArrayVec<_, { 2 * TREE_BASE }, u8> =
1090                        all_summaries.by_ref().take(midpoint).collect();
1091                    *item_summaries = all_summaries.collect();
1092
1093                    *summary = sum(item_summaries.iter(), cx);
1094                    Some(SumTree(Arc::new(Node::Leaf {
1095                        items: left_items,
1096                        summary: sum(left_summaries.iter(), cx),
1097                        item_summaries: left_summaries,
1098                    })))
1099                }
1100            }
1101            _ => unreachable!(),
1102        }
1103    }
1104
1105    fn from_child_trees(
1106        left: SumTree<T>,
1107        right: SumTree<T>,
1108        cx: <T::Summary as Summary>::Context<'_>,
1109    ) -> Self {
1110        let height = left.0.height() + 1;
1111        let mut child_summaries = ArrayVec::new();
1112        child_summaries.push(left.0.summary().clone()).unwrap_oob();
1113        child_summaries.push(right.0.summary().clone()).unwrap_oob();
1114        let mut child_trees = ArrayVec::new();
1115        child_trees.push(left).unwrap_oob();
1116        child_trees.push(right).unwrap_oob();
1117        SumTree(Arc::new(Node::Internal {
1118            height,
1119            summary: sum(child_summaries.iter(), cx),
1120            child_summaries,
1121            child_trees,
1122        }))
1123    }
1124
1125    fn leftmost_leaf(&self) -> &Self {
1126        match *self.0 {
1127            Node::Leaf { .. } => self,
1128            Node::Internal {
1129                ref child_trees, ..
1130            } => child_trees.first().unwrap().leftmost_leaf(),
1131        }
1132    }
1133
1134    fn rightmost_leaf(&self) -> &Self {
1135        match *self.0 {
1136            Node::Leaf { .. } => self,
1137            Node::Internal {
1138                ref child_trees, ..
1139            } => child_trees.last().unwrap().rightmost_leaf(),
1140        }
1141    }
1142}
1143
1144impl<T: Item + PartialEq> PartialEq for SumTree<T> {
1145    fn eq(&self, other: &Self) -> bool {
1146        self.iter().eq(other.iter())
1147    }
1148}
1149
1150impl<T: Item + Eq> Eq for SumTree<T> {}
1151
1152impl<T: KeyedItem> SumTree<T> {
1153    pub fn insert_or_replace<'a, 'b>(
1154        &'a mut self,
1155        item: T,
1156        cx: <T::Summary as Summary>::Context<'b>,
1157    ) -> Option<T> {
1158        let mut replaced = None;
1159        {
1160            let mut cursor = self.cursor::<T::Key>(cx);
1161            let mut new_tree = cursor.slice(&item.key(), Bias::Left);
1162            if let Some(cursor_item) = cursor.item()
1163                && cursor_item.key() == item.key()
1164            {
1165                replaced = Some(cursor_item.clone());
1166                cursor.next();
1167            }
1168            new_tree.push(item, cx);
1169            new_tree.append(cursor.suffix(), cx);
1170            drop(cursor);
1171            *self = new_tree
1172        };
1173        replaced
1174    }
1175
1176    pub fn remove(&mut self, key: &T::Key, cx: <T::Summary as Summary>::Context<'_>) -> Option<T> {
1177        let mut removed = None;
1178        *self = {
1179            let mut cursor = self.cursor::<T::Key>(cx);
1180            let mut new_tree = cursor.slice(key, Bias::Left);
1181            if let Some(item) = cursor.item()
1182                && item.key() == *key
1183            {
1184                removed = Some(item.clone());
1185                cursor.next();
1186            }
1187            new_tree.append(cursor.suffix(), cx);
1188            new_tree
1189        };
1190        removed
1191    }
1192
1193    pub fn edit(
1194        &mut self,
1195        mut edits: Vec<Edit<T>>,
1196        cx: <T::Summary as Summary>::Context<'_>,
1197    ) -> Vec<T> {
1198        if edits.is_empty() {
1199            return Vec::new();
1200        }
1201
1202        let mut removed = Vec::new();
1203        edits.sort_unstable_by_key(|item| item.key());
1204
1205        *self = {
1206            let mut cursor = self.cursor::<T::Key>(cx);
1207            let mut new_tree = SumTree::new(cx);
1208            let mut buffered_items = Vec::new();
1209
1210            cursor.seek(&T::Key::zero(cx), Bias::Left);
1211            for edit in edits {
1212                let new_key = edit.key();
1213                let mut old_item = cursor.item();
1214
1215                if old_item
1216                    .as_ref()
1217                    .is_some_and(|old_item| old_item.key() < new_key)
1218                {
1219                    new_tree.extend(buffered_items.drain(..), cx);
1220                    let slice = cursor.slice(&new_key, Bias::Left);
1221                    new_tree.append(slice, cx);
1222                    old_item = cursor.item();
1223                }
1224
1225                if let Some(old_item) = old_item
1226                    && old_item.key() == new_key
1227                {
1228                    removed.push(old_item.clone());
1229                    cursor.next();
1230                }
1231
1232                match edit {
1233                    Edit::Insert(item) => {
1234                        buffered_items.push(item);
1235                    }
1236                    Edit::Remove(_) => {}
1237                }
1238            }
1239
1240            new_tree.extend(buffered_items, cx);
1241            new_tree.append(cursor.suffix(), cx);
1242            new_tree
1243        };
1244
1245        removed
1246    }
1247
1248    pub fn get<'a>(
1249        &'a self,
1250        key: &T::Key,
1251        cx: <T::Summary as Summary>::Context<'a>,
1252    ) -> Option<&'a T> {
1253        if let (_, _, Some(item)) = self.find_exact::<T::Key, _>(cx, key, Bias::Left) {
1254            Some(item)
1255        } else {
1256            None
1257        }
1258    }
1259}
1260
1261impl<T, S> Default for SumTree<T>
1262where
1263    T: Item<Summary = S>,
1264    S: for<'a> Summary<Context<'a> = ()>,
1265{
1266    fn default() -> Self {
1267        Self::new(())
1268    }
1269}
1270
1271#[derive(Clone)]
1272pub enum Node<T: Item> {
1273    Internal {
1274        height: u8,
1275        summary: T::Summary,
1276        child_summaries: ArrayVec<T::Summary, { 2 * TREE_BASE }, u8>,
1277        child_trees: ArrayVec<SumTree<T>, { 2 * TREE_BASE }, u8>,
1278    },
1279    Leaf {
1280        summary: T::Summary,
1281        items: ArrayVec<T, { 2 * TREE_BASE }, u8>,
1282        item_summaries: ArrayVec<T::Summary, { 2 * TREE_BASE }, u8>,
1283    },
1284}
1285
1286impl<T> fmt::Debug for Node<T>
1287where
1288    T: Item + fmt::Debug,
1289    T::Summary: fmt::Debug,
1290{
1291    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1292        match self {
1293            Node::Internal {
1294                height,
1295                summary,
1296                child_summaries,
1297                child_trees,
1298            } => f
1299                .debug_struct("Internal")
1300                .field("height", height)
1301                .field("summary", summary)
1302                .field("child_summaries", child_summaries)
1303                .field("child_trees", child_trees)
1304                .finish(),
1305            Node::Leaf {
1306                summary,
1307                items,
1308                item_summaries,
1309            } => f
1310                .debug_struct("Leaf")
1311                .field("summary", summary)
1312                .field("items", items)
1313                .field("item_summaries", item_summaries)
1314                .finish(),
1315        }
1316    }
1317}
1318
1319impl<T: Item> Node<T> {
1320    fn is_leaf(&self) -> bool {
1321        matches!(self, Node::Leaf { .. })
1322    }
1323
1324    fn height(&self) -> u8 {
1325        match self {
1326            Node::Internal { height, .. } => *height,
1327            Node::Leaf { .. } => 0,
1328        }
1329    }
1330
1331    fn summary(&self) -> &T::Summary {
1332        match self {
1333            Node::Internal { summary, .. } => summary,
1334            Node::Leaf { summary, .. } => summary,
1335        }
1336    }
1337
1338    fn child_summaries(&self) -> &[T::Summary] {
1339        match self {
1340            Node::Internal {
1341                child_summaries, ..
1342            } => child_summaries.as_slice(),
1343            Node::Leaf { item_summaries, .. } => item_summaries.as_slice(),
1344        }
1345    }
1346
1347    fn child_trees(&self) -> &ArrayVec<SumTree<T>, { 2 * TREE_BASE }, u8> {
1348        match self {
1349            Node::Internal { child_trees, .. } => child_trees,
1350            Node::Leaf { .. } => panic!("Leaf nodes have no child trees"),
1351        }
1352    }
1353
1354    fn items(&self) -> &ArrayVec<T, { 2 * TREE_BASE }, u8> {
1355        match self {
1356            Node::Leaf { items, .. } => items,
1357            Node::Internal { .. } => panic!("Internal nodes have no items"),
1358        }
1359    }
1360
1361    fn is_underflowing(&self) -> bool {
1362        match self {
1363            Node::Internal { child_trees, .. } => child_trees.len() < TREE_BASE,
1364            Node::Leaf { items, .. } => items.len() < TREE_BASE,
1365        }
1366    }
1367}
1368
1369#[derive(Debug)]
1370pub enum Edit<T: KeyedItem> {
1371    Insert(T),
1372    Remove(T::Key),
1373}
1374
1375impl<T: KeyedItem> Edit<T> {
1376    fn key(&self) -> T::Key {
1377        match self {
1378            Edit::Insert(item) => item.key(),
1379            Edit::Remove(key) => key.clone(),
1380        }
1381    }
1382}
1383
1384fn sum<'a, T, I>(iter: I, cx: T::Context<'_>) -> T
1385where
1386    T: 'a + Summary,
1387    I: Iterator<Item = &'a T>,
1388{
1389    let mut sum = T::zero(cx);
1390    for value in iter {
1391        sum.add_summary(value, cx);
1392    }
1393    sum
1394}
1395
1396#[cfg(test)]
1397mod tests {
1398    use super::*;
1399    use rand::{distr::StandardUniform, prelude::*};
1400    use std::cmp;
1401
1402    #[ctor::ctor(unsafe)]
1403    fn init_logger() {
1404        zlog::init_test();
1405    }
1406
1407    #[test]
1408    fn test_extend_and_push_tree() {
1409        let mut tree1 = SumTree::default();
1410        tree1.extend(0..20, ());
1411
1412        let mut tree2 = SumTree::default();
1413        tree2.extend(50..100, ());
1414
1415        tree1.append(tree2, ());
1416        assert_eq!(tree1.items(()), (0..20).chain(50..100).collect::<Vec<u8>>());
1417    }
1418
1419    #[test]
1420    fn test_random() {
1421        let mut starting_seed = 0;
1422        if let Ok(value) = std::env::var("SEED") {
1423            starting_seed = value.parse().expect("invalid SEED variable");
1424        }
1425        let mut num_iterations = 100;
1426        if let Ok(value) = std::env::var("ITERATIONS") {
1427            num_iterations = value.parse().expect("invalid ITERATIONS variable");
1428        }
1429        let num_operations = std::env::var("OPERATIONS")
1430            .map_or(5, |o| o.parse().expect("invalid OPERATIONS variable"));
1431
1432        for seed in starting_seed..(starting_seed + num_iterations) {
1433            eprintln!("seed = {}", seed);
1434            let mut rng = StdRng::seed_from_u64(seed);
1435
1436            let rng = &mut rng;
1437            let mut tree = SumTree::<u8>::default();
1438            let count = rng.random_range(0..10);
1439            if rng.random() {
1440                tree.extend(rng.sample_iter(StandardUniform).take(count), ());
1441            } else {
1442                let items = rng
1443                    .sample_iter(StandardUniform)
1444                    .take(count)
1445                    .collect::<Vec<_>>();
1446                tree.par_extend(items, ());
1447            }
1448
1449            for _ in 0..num_operations {
1450                let splice_end = rng.random_range(0..tree.extent::<Count>(()).0 + 1);
1451                let splice_start = rng.random_range(0..splice_end + 1);
1452                let count = rng.random_range(0..10);
1453                let tree_end = tree.extent::<Count>(());
1454                let new_items = rng
1455                    .sample_iter(StandardUniform)
1456                    .take(count)
1457                    .collect::<Vec<u8>>();
1458
1459                let mut reference_items = tree.items(());
1460                reference_items.splice(splice_start..splice_end, new_items.clone());
1461
1462                tree = {
1463                    let mut cursor = tree.cursor::<Count>(());
1464                    let mut new_tree = cursor.slice(&Count(splice_start), Bias::Right);
1465                    if rng.random() {
1466                        new_tree.extend(new_items, ());
1467                    } else {
1468                        new_tree.par_extend(new_items, ());
1469                    }
1470                    cursor.seek(&Count(splice_end), Bias::Right);
1471                    new_tree.append(cursor.slice(&tree_end, Bias::Right), ());
1472                    new_tree
1473                };
1474
1475                assert_eq!(tree.items(()), reference_items);
1476                assert_eq!(
1477                    tree.iter().collect::<Vec<_>>(),
1478                    tree.cursor::<()>(()).collect::<Vec<_>>()
1479                );
1480
1481                log::info!("tree items: {:?}", tree.items(()));
1482
1483                let mut filter_cursor =
1484                    tree.filter::<_, Count>((), |summary| summary.contains_even);
1485                let expected_filtered_items = tree
1486                    .items(())
1487                    .into_iter()
1488                    .enumerate()
1489                    .filter(|(_, item)| (item & 1) == 0)
1490                    .collect::<Vec<_>>();
1491
1492                let mut item_ix = if rng.random() {
1493                    filter_cursor.next();
1494                    0
1495                } else {
1496                    filter_cursor.prev();
1497                    expected_filtered_items.len().saturating_sub(1)
1498                };
1499                while item_ix < expected_filtered_items.len() {
1500                    log::info!("filter_cursor, item_ix: {}", item_ix);
1501                    let actual_item = filter_cursor.item().unwrap();
1502                    let (reference_index, reference_item) = expected_filtered_items[item_ix];
1503                    assert_eq!(actual_item, &reference_item);
1504                    assert_eq!(filter_cursor.start().0, reference_index);
1505                    log::info!("next");
1506                    filter_cursor.next();
1507                    item_ix += 1;
1508
1509                    while item_ix > 0 && rng.random_bool(0.2) {
1510                        log::info!("prev");
1511                        filter_cursor.prev();
1512                        item_ix -= 1;
1513
1514                        if item_ix == 0 && rng.random_bool(0.2) {
1515                            filter_cursor.prev();
1516                            assert_eq!(filter_cursor.item(), None);
1517                            assert_eq!(filter_cursor.start().0, 0);
1518                            filter_cursor.next();
1519                        }
1520                    }
1521                }
1522                assert_eq!(filter_cursor.item(), None);
1523
1524                let mut before_start = false;
1525                let mut cursor = tree.cursor::<Count>(());
1526                let start_pos = rng.random_range(0..=reference_items.len());
1527                cursor.seek(&Count(start_pos), Bias::Right);
1528                let mut pos = rng.random_range(start_pos..=reference_items.len());
1529                cursor.seek_forward(&Count(pos), Bias::Right);
1530
1531                for i in 0..10 {
1532                    assert_eq!(cursor.start().0, pos);
1533
1534                    if pos > 0 {
1535                        assert_eq!(cursor.prev_item().unwrap(), &reference_items[pos - 1]);
1536                    } else {
1537                        assert_eq!(cursor.prev_item(), None);
1538                    }
1539
1540                    if pos < reference_items.len() && !before_start {
1541                        assert_eq!(cursor.item().unwrap(), &reference_items[pos]);
1542                    } else {
1543                        assert_eq!(cursor.item(), None);
1544                    }
1545
1546                    if before_start {
1547                        assert_eq!(cursor.next_item(), reference_items.first());
1548                    } else if pos + 1 < reference_items.len() {
1549                        assert_eq!(cursor.next_item().unwrap(), &reference_items[pos + 1]);
1550                    } else {
1551                        assert_eq!(cursor.next_item(), None);
1552                    }
1553
1554                    if i < 5 {
1555                        cursor.next();
1556                        if pos < reference_items.len() {
1557                            pos += 1;
1558                            before_start = false;
1559                        }
1560                    } else {
1561                        cursor.prev();
1562                        if pos == 0 {
1563                            before_start = true;
1564                        }
1565                        pos = pos.saturating_sub(1);
1566                    }
1567                }
1568            }
1569
1570            for _ in 0..10 {
1571                let end = rng.random_range(0..tree.extent::<Count>(()).0 + 1);
1572                let start = rng.random_range(0..end + 1);
1573                let start_bias = if rng.random() {
1574                    Bias::Left
1575                } else {
1576                    Bias::Right
1577                };
1578                let end_bias = if rng.random() {
1579                    Bias::Left
1580                } else {
1581                    Bias::Right
1582                };
1583
1584                let mut cursor = tree.cursor::<Count>(());
1585                cursor.seek(&Count(start), start_bias);
1586                let slice = cursor.slice(&Count(end), end_bias);
1587
1588                cursor.seek(&Count(start), start_bias);
1589                let summary = cursor.summary::<_, Sum>(&Count(end), end_bias);
1590
1591                assert_eq!(summary.0, slice.summary().sum);
1592            }
1593        }
1594    }
1595
1596    #[test]
1597    fn test_cursor() {
1598        // Empty tree
1599        let tree = SumTree::<u8>::default();
1600        let mut cursor = tree.cursor::<IntegersSummary>(());
1601        assert_eq!(
1602            cursor.slice(&Count(0), Bias::Right).items(()),
1603            Vec::<u8>::new()
1604        );
1605        assert_eq!(cursor.item(), None);
1606        assert_eq!(cursor.prev_item(), None);
1607        assert_eq!(cursor.next_item(), None);
1608        assert_eq!(cursor.start().sum, 0);
1609        cursor.prev();
1610        assert_eq!(cursor.item(), None);
1611        assert_eq!(cursor.prev_item(), None);
1612        assert_eq!(cursor.next_item(), None);
1613        assert_eq!(cursor.start().sum, 0);
1614        cursor.next();
1615        assert_eq!(cursor.item(), None);
1616        assert_eq!(cursor.prev_item(), None);
1617        assert_eq!(cursor.next_item(), None);
1618        assert_eq!(cursor.start().sum, 0);
1619
1620        // Single-element tree
1621        let mut tree = SumTree::<u8>::default();
1622        tree.extend(vec![1], ());
1623        let mut cursor = tree.cursor::<IntegersSummary>(());
1624        assert_eq!(
1625            cursor.slice(&Count(0), Bias::Right).items(()),
1626            Vec::<u8>::new()
1627        );
1628        assert_eq!(cursor.item(), Some(&1));
1629        assert_eq!(cursor.prev_item(), None);
1630        assert_eq!(cursor.next_item(), None);
1631        assert_eq!(cursor.start().sum, 0);
1632
1633        cursor.next();
1634        assert_eq!(cursor.item(), None);
1635        assert_eq!(cursor.prev_item(), Some(&1));
1636        assert_eq!(cursor.next_item(), None);
1637        assert_eq!(cursor.start().sum, 1);
1638
1639        cursor.prev();
1640        assert_eq!(cursor.item(), Some(&1));
1641        assert_eq!(cursor.prev_item(), None);
1642        assert_eq!(cursor.next_item(), None);
1643        assert_eq!(cursor.start().sum, 0);
1644
1645        let mut cursor = tree.cursor::<IntegersSummary>(());
1646        assert_eq!(cursor.slice(&Count(1), Bias::Right).items(()), [1]);
1647        assert_eq!(cursor.item(), None);
1648        assert_eq!(cursor.prev_item(), Some(&1));
1649        assert_eq!(cursor.next_item(), None);
1650        assert_eq!(cursor.start().sum, 1);
1651
1652        cursor.seek(&Count(0), Bias::Right);
1653        assert_eq!(
1654            cursor
1655                .slice(&tree.extent::<Count>(()), Bias::Right)
1656                .items(()),
1657            [1]
1658        );
1659        assert_eq!(cursor.item(), None);
1660        assert_eq!(cursor.prev_item(), Some(&1));
1661        assert_eq!(cursor.next_item(), None);
1662        assert_eq!(cursor.start().sum, 1);
1663
1664        // Multiple-element tree
1665        let mut tree = SumTree::default();
1666        tree.extend(vec![1, 2, 3, 4, 5, 6], ());
1667        let mut cursor = tree.cursor::<IntegersSummary>(());
1668
1669        assert_eq!(cursor.slice(&Count(2), Bias::Right).items(()), [1, 2]);
1670        assert_eq!(cursor.item(), Some(&3));
1671        assert_eq!(cursor.prev_item(), Some(&2));
1672        assert_eq!(cursor.next_item(), Some(&4));
1673        assert_eq!(cursor.start().sum, 3);
1674
1675        cursor.next();
1676        assert_eq!(cursor.item(), Some(&4));
1677        assert_eq!(cursor.prev_item(), Some(&3));
1678        assert_eq!(cursor.next_item(), Some(&5));
1679        assert_eq!(cursor.start().sum, 6);
1680
1681        cursor.next();
1682        assert_eq!(cursor.item(), Some(&5));
1683        assert_eq!(cursor.prev_item(), Some(&4));
1684        assert_eq!(cursor.next_item(), Some(&6));
1685        assert_eq!(cursor.start().sum, 10);
1686
1687        cursor.next();
1688        assert_eq!(cursor.item(), Some(&6));
1689        assert_eq!(cursor.prev_item(), Some(&5));
1690        assert_eq!(cursor.next_item(), None);
1691        assert_eq!(cursor.start().sum, 15);
1692
1693        cursor.next();
1694        cursor.next();
1695        assert_eq!(cursor.item(), None);
1696        assert_eq!(cursor.prev_item(), Some(&6));
1697        assert_eq!(cursor.next_item(), None);
1698        assert_eq!(cursor.start().sum, 21);
1699
1700        cursor.prev();
1701        assert_eq!(cursor.item(), Some(&6));
1702        assert_eq!(cursor.prev_item(), Some(&5));
1703        assert_eq!(cursor.next_item(), None);
1704        assert_eq!(cursor.start().sum, 15);
1705
1706        cursor.prev();
1707        assert_eq!(cursor.item(), Some(&5));
1708        assert_eq!(cursor.prev_item(), Some(&4));
1709        assert_eq!(cursor.next_item(), Some(&6));
1710        assert_eq!(cursor.start().sum, 10);
1711
1712        cursor.prev();
1713        assert_eq!(cursor.item(), Some(&4));
1714        assert_eq!(cursor.prev_item(), Some(&3));
1715        assert_eq!(cursor.next_item(), Some(&5));
1716        assert_eq!(cursor.start().sum, 6);
1717
1718        cursor.prev();
1719        assert_eq!(cursor.item(), Some(&3));
1720        assert_eq!(cursor.prev_item(), Some(&2));
1721        assert_eq!(cursor.next_item(), Some(&4));
1722        assert_eq!(cursor.start().sum, 3);
1723
1724        cursor.prev();
1725        assert_eq!(cursor.item(), Some(&2));
1726        assert_eq!(cursor.prev_item(), Some(&1));
1727        assert_eq!(cursor.next_item(), Some(&3));
1728        assert_eq!(cursor.start().sum, 1);
1729
1730        cursor.prev();
1731        assert_eq!(cursor.item(), Some(&1));
1732        assert_eq!(cursor.prev_item(), None);
1733        assert_eq!(cursor.next_item(), Some(&2));
1734        assert_eq!(cursor.start().sum, 0);
1735
1736        cursor.prev();
1737        assert_eq!(cursor.item(), None);
1738        assert_eq!(cursor.prev_item(), None);
1739        assert_eq!(cursor.next_item(), Some(&1));
1740        assert_eq!(cursor.start().sum, 0);
1741
1742        cursor.next();
1743        assert_eq!(cursor.item(), Some(&1));
1744        assert_eq!(cursor.prev_item(), None);
1745        assert_eq!(cursor.next_item(), Some(&2));
1746        assert_eq!(cursor.start().sum, 0);
1747
1748        let mut cursor = tree.cursor::<IntegersSummary>(());
1749        assert_eq!(
1750            cursor
1751                .slice(&tree.extent::<Count>(()), Bias::Right)
1752                .items(()),
1753            tree.items(())
1754        );
1755        assert_eq!(cursor.item(), None);
1756        assert_eq!(cursor.prev_item(), Some(&6));
1757        assert_eq!(cursor.next_item(), None);
1758        assert_eq!(cursor.start().sum, 21);
1759
1760        cursor.seek(&Count(3), Bias::Right);
1761        assert_eq!(
1762            cursor
1763                .slice(&tree.extent::<Count>(()), Bias::Right)
1764                .items(()),
1765            [4, 5, 6]
1766        );
1767        assert_eq!(cursor.item(), None);
1768        assert_eq!(cursor.prev_item(), Some(&6));
1769        assert_eq!(cursor.next_item(), None);
1770        assert_eq!(cursor.start().sum, 21);
1771
1772        // Seeking can bias left or right
1773        cursor.seek(&Count(1), Bias::Left);
1774        assert_eq!(cursor.item(), Some(&1));
1775        cursor.seek(&Count(1), Bias::Right);
1776        assert_eq!(cursor.item(), Some(&2));
1777
1778        // Slicing without resetting starts from where the cursor is parked at.
1779        cursor.seek(&Count(1), Bias::Right);
1780        assert_eq!(cursor.slice(&Count(3), Bias::Right).items(()), vec![2, 3]);
1781        assert_eq!(cursor.slice(&Count(6), Bias::Left).items(()), vec![4, 5]);
1782        assert_eq!(cursor.slice(&Count(6), Bias::Right).items(()), vec![6]);
1783    }
1784
1785    #[test]
1786    fn test_edit() {
1787        let mut tree = SumTree::<u8>::default();
1788
1789        let removed = tree.edit(vec![Edit::Insert(1), Edit::Insert(2), Edit::Insert(0)], ());
1790        assert_eq!(tree.items(()), vec![0, 1, 2]);
1791        assert_eq!(removed, Vec::<u8>::new());
1792        assert_eq!(tree.get(&0, ()), Some(&0));
1793        assert_eq!(tree.get(&1, ()), Some(&1));
1794        assert_eq!(tree.get(&2, ()), Some(&2));
1795        assert_eq!(tree.get(&4, ()), None);
1796
1797        let removed = tree.edit(vec![Edit::Insert(2), Edit::Insert(4), Edit::Remove(0)], ());
1798        assert_eq!(tree.items(()), vec![1, 2, 4]);
1799        assert_eq!(removed, vec![0, 2]);
1800        assert_eq!(tree.get(&0, ()), None);
1801        assert_eq!(tree.get(&1, ()), Some(&1));
1802        assert_eq!(tree.get(&2, ()), Some(&2));
1803        assert_eq!(tree.get(&4, ()), Some(&4));
1804    }
1805
1806    #[test]
1807    fn test_from_iter() {
1808        assert_eq!(
1809            SumTree::from_iter(0..100, ()).items(()),
1810            (0..100).collect::<Vec<_>>()
1811        );
1812
1813        // Ensure `from_iter` works correctly when the given iterator restarts
1814        // after calling `next` if `None` was already returned.
1815        let mut ix = 0;
1816        let iterator = std::iter::from_fn(|| {
1817            ix = (ix + 1) % 2;
1818            if ix == 1 { Some(1) } else { None }
1819        });
1820        assert_eq!(SumTree::from_iter(iterator, ()).items(()), vec![1]);
1821    }
1822
1823    #[derive(Clone, Default, Debug)]
1824    pub struct IntegersSummary {
1825        count: usize,
1826        sum: usize,
1827        contains_even: bool,
1828        max: u8,
1829    }
1830
1831    #[derive(Ord, PartialOrd, Default, Eq, PartialEq, Clone, Debug)]
1832    struct Count(usize);
1833
1834    #[derive(Ord, PartialOrd, Default, Eq, PartialEq, Clone, Debug)]
1835    struct Sum(usize);
1836
1837    impl Item for u8 {
1838        type Summary = IntegersSummary;
1839
1840        fn summary(&self, _cx: ()) -> Self::Summary {
1841            IntegersSummary {
1842                count: 1,
1843                sum: *self as usize,
1844                contains_even: (*self & 1) == 0,
1845                max: *self,
1846            }
1847        }
1848    }
1849
1850    impl KeyedItem for u8 {
1851        type Key = u8;
1852
1853        fn key(&self) -> Self::Key {
1854            *self
1855        }
1856    }
1857
1858    impl ContextLessSummary for IntegersSummary {
1859        fn zero() -> Self {
1860            Default::default()
1861        }
1862
1863        fn add_summary(&mut self, other: &Self) {
1864            self.count += other.count;
1865            self.sum += other.sum;
1866            self.contains_even |= other.contains_even;
1867            self.max = cmp::max(self.max, other.max);
1868        }
1869    }
1870
1871    impl Dimension<'_, IntegersSummary> for u8 {
1872        fn zero(_cx: ()) -> Self {
1873            Default::default()
1874        }
1875
1876        fn add_summary(&mut self, summary: &IntegersSummary, _: ()) {
1877            *self = summary.max;
1878        }
1879    }
1880
1881    impl Dimension<'_, IntegersSummary> for Count {
1882        fn zero(_cx: ()) -> Self {
1883            Default::default()
1884        }
1885
1886        fn add_summary(&mut self, summary: &IntegersSummary, _: ()) {
1887            self.0 += summary.count;
1888        }
1889    }
1890
1891    impl SeekTarget<'_, IntegersSummary, IntegersSummary> for Count {
1892        fn cmp(&self, cursor_location: &IntegersSummary, _: ()) -> Ordering {
1893            self.0.cmp(&cursor_location.count)
1894        }
1895    }
1896
1897    impl Dimension<'_, IntegersSummary> for Sum {
1898        fn zero(_cx: ()) -> Self {
1899            Default::default()
1900        }
1901
1902        fn add_summary(&mut self, summary: &IntegersSummary, _: ()) {
1903            self.0 += summary.sum;
1904        }
1905    }
1906}