content_tree/
iter.rs

1
2use crate::{NodeLeaf, ContentTraits, TreeMetrics, Cursor, ContentTreeRaw};
3use rle::{Searchable, MergeIter, merge_items};
4
5/// Iterator for all the items inside the entries. Unlike entry iteration we use the offset here.
6#[derive(Debug)]
7pub struct ItemIterator<'a, E: ContentTraits, I: TreeMetrics<E>, const IE: usize, const LE: usize>(pub Cursor<'a, E, I, IE, LE>);
8
9impl<'a, E: ContentTraits + Searchable, I: TreeMetrics<E>, const IE: usize, const LE: usize> Iterator for ItemIterator<'a, E, I, IE, LE> {
10    type Item = E::Item;
11
12    fn next(&mut self) -> Option<Self::Item> {
13        // I'll set idx to an invalid value
14        if self.0.inner.idx == usize::MAX {
15            None
16        } else {
17            let entry = self.0.inner.get_raw_entry();
18            let len = entry.len();
19            let item = entry.at_offset(self.0.inner.offset);
20            self.0.inner.offset += 1;
21
22            if self.0.inner.offset >= len {
23                // Skip to the next entry for the next query.
24                let has_next = self.0.inner.next_entry();
25                if !has_next {
26                    // We're done.
27                    self.0.inner.idx = usize::MAX;
28                }
29            }
30            Some(item)
31        }
32    }
33}
34
35/// Iterator for whole nodes in the tree. This lets you iterate through chunks of items efficiently.
36#[derive(Debug)]
37pub struct NodeIter<'a, E: ContentTraits, I: TreeMetrics<E>, const IE: usize, const LE: usize>(Option<&'a NodeLeaf<E, I, IE, LE>>);
38
39impl<'a, E: ContentTraits, I: TreeMetrics<E>, const IE: usize, const LE: usize> Iterator for NodeIter<'a, E, I, IE, LE> {
40    type Item = &'a NodeLeaf<E, I, IE, LE>;
41
42    fn next(&mut self) -> Option<Self::Item> {
43        if let Some(leaf) = self.0 {
44            let this_ref = self.0;
45            self.0 = leaf.next.map(|ptr| unsafe { ptr.as_ref() });
46            this_ref
47        } else { None }
48    }
49}
50
51impl<E: ContentTraits, I: TreeMetrics<E>, const IE: usize, const LE: usize> ContentTreeRaw<E, I, IE, LE> {
52    /// Iterate through all the items "raw" - which is to say, without merging anything.
53    ///
54    /// This is different from iter() because in some editing situations the tree will not be
55    /// perfectly flattened. That is, it may be possible to merge some items in the tree. This
56    /// iterator method will not merge anything, and instead just iterate through all items as they
57    /// are stored.
58    ///
59    /// Whether specific items are merged or not is an implementation detail, and should not be
60    /// relied upon by your application. If you expect all mergable items to be merged, use iter().
61    pub fn raw_iter(&self) -> Cursor<E, I, IE, LE> { self.cursor_at_start() }
62
63    /// Iterate through all entries in the content tree. This iterator will yield all entries
64    /// merged according to the methods in SplitableSpan.
65    pub fn iter(&self) -> MergeIter<Cursor<E, I, IE, LE>> { merge_items(self.cursor_at_start()) }
66
67    pub fn item_iter(&self) -> ItemIterator<E, I, IE, LE> {
68        ItemIterator(self.raw_iter())
69    }
70
71    pub fn node_iter(&self) -> NodeIter<E, I, IE, LE> {
72        let leaf_ref = self.leaf_at_start();
73        NodeIter(if leaf_ref.num_entries > 0 { Some(leaf_ref) } else { None })
74    }
75}
76
77#[cfg(test)]
78mod test {
79    use crate::ContentTree;
80    use crate::testrange::TestRange;
81
82    #[test]
83    fn node_iter_smoke_test() {
84        let mut tree = ContentTree::new();
85
86        let mut iter = tree.node_iter();
87        assert!(iter.next().is_none());
88
89        tree.push(TestRange { id: 1000, len: 100, is_activated: true });
90
91        let mut iter = tree.node_iter();
92        let first = iter.next().unwrap();
93        assert_eq!(first.num_entries, 1);
94        assert!(iter.next().is_none());
95    }
96}
content_tree/iter.rs

content_tree/
iter.rs
