grove 0.2.0

A segment tree library enabling generic user-defined queries and actions on segments of your data.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

//! A convenience struct that represents a specific segment of a tree.

use super::*;
use crate::*;
use std::marker::PhantomData;

/// Returns a value representing a specific subsegment of the tree. This gives a nicer
/// Interface for tree operations: `tree.slice(3..50).act(action)` instead of
/// `tree.act_segment(3..50, action)`.
///
/// It allows to query the tree for a summary or to apply an action,
/// and other useful operations, with a nicer interface.
///
/// This struct essentially just forwards calls, mostly to the methods in the traits in [`crate::trees`].
pub struct Slice<'a, D, T, L> {
    phantom: PhantomData<D>,
    tree: &'a mut T,
    locator: L,
}

impl<'a, D: Data, T: SomeTree<D>, L: Locator<D>> Slice<'a, D, T, L>
where
    for<'b> &'b mut T: SomeTreeRef<D>,
{
    /// Creates a new slice that represents the locator's segment in the tree.
    pub fn new(tree: &'a mut T, locator: L) -> Self {
        Slice {
            phantom: PhantomData,
            tree,
            locator,
        }
    }

    /// Compute the summary of this subsegment.
    pub fn summary(&mut self) -> D::Summary
    {
        self.tree.segment_summary(self.locator.clone())
    }

    /// Apply an action on this subsegment.
    pub fn act(&mut self, action: D::Action) {
        self.tree.act_segment(action, self.locator.clone());
    }

    /// Finds any node in the current subsegment.
    /// If there isn't any, it finds the empty location where that node would be instead.
    /// Returns a walker at the wanted position.
    pub fn search(self) -> <&'a mut T as SomeTreeRef<D>>::Walker {
        self.tree.search(self.locator)
    }

    /// Iterating on values.
    /// This iterator assumes you won't change the values using interior mutability. If you change the values,
    /// The tree summaries will behave incorrectly.
    ///
    /// The iterator receives a `&mut self` argument instead of a `&self` argument.
    /// Because of the way the trees work, immutable iterators can't be written without either mutable access
    /// to the tree, or assuming that the values are `Clone`.
    ///
    /// On the other hand, mutable iterators can't be written because the values of the nodes must be rebuilt,
    /// but they can only be rebuilt after the iterator exits. (This is because rust iterators can't be streaming iterators).
    /// If you want a mutable iterator, use a walker instead.
    pub fn iter(self) -> basic_tree::iterators::IterLocator<'a, D, L, T::TreeData> {
        self.tree.iter_locator(self.locator)
    }
}

impl<'a, D: Data, T: SomeTree<D>, L: Locator<D>> Slice<'a, D, T, L>
where
    for<'b> &'b mut T: ModifiableTreeRef<D>,
{
    /// Assumes that the this subsegment is empty.
    /// Inserts the value into the tree into the position of this empty subsegment.
    /// If the current subsegment is not empty, returns [`None`].
    pub fn insert(&mut self, value: D::Value) -> Option<()> {
        let mut walker = self.tree.search(self.locator.clone());
        walker.insert(value)
    }

    /// Removes any value from this subsegment from tree, and returns it.
    /// If this subsegment is empty, returns [`None`].
    pub fn delete(&mut self) -> Option<D::Value> {
        let mut walker = self.tree.search(self.locator.clone());
        walker.delete()
    }
}

impl<'a, D: Data, T: SomeTree<D>, L: Locator<D>> Slice<'a, D, T, L>
where
    for<'b> &'b mut T: SplittableTreeRef<D>,
{
    /// Assumes that the this subsegment is empty.
    /// Split out everything to the right of this subsegment, if it is an empty subsegment.
    /// Otherwise returns [`None`].
    pub fn split_right(
        &mut self,
    ) -> Option<<<&mut T as SplittableTreeRef<D>>::SplittableWalker as SplittableWalker<D>>::T>
    {
        let mut walker = self.tree.search(self.locator.clone());
        walker.split_right()
    }

    /// Assumes that the this subsegment is empty.
    /// Split out everything to the left of the this subsegment, if it is an empty subsegment.
    /// Otherwise returns [`None`].
    pub fn split_left(
        &mut self,
    ) -> Option<<<&mut T as SplittableTreeRef<D>>::SplittableWalker as SplittableWalker<D>>::T>
    {
        let mut walker = self.tree.search(self.locator.clone());
        walker.split_left()
    }
}