rb_interval_map/
iter.rs

1use std::fmt::Debug;
2
3use crate::index::{IndexType, NodeIndex};
4use crate::interval::Interval;
5use crate::intervalmap::IntervalMap;
6use crate::node::Node;
7
8/// Pushes a link of nodes on the left to stack.
9fn left_link<T, V, Ix>(map_ref: &IntervalMap<T, V, Ix>, mut x: NodeIndex<Ix>) -> Vec<NodeIndex<Ix>>
10where
11    T: Ord,
12    Ix: IndexType,
13{
14    let mut nodes = vec![];
15    while !map_ref.node_ref(x, Node::is_sentinel) {
16        nodes.push(x);
17        x = map_ref.node_ref(x, Node::left);
18    }
19    nodes
20}
21
22/// An iterator over the entries of a `IntervalMap`.
23#[derive(Debug)]
24pub struct Iter<'a, T, V, Ix>
25where
26    T: Ord,
27{
28    /// Reference to the map
29    pub(crate) map_ref: &'a IntervalMap<T, V, Ix>,
30    /// Stack for iteration
31    pub(crate) stack: Vec<NodeIndex<Ix>>,
32}
33
34impl<'a, T, V, Ix> Iter<'a, T, V, Ix>
35where
36    T: Ord,
37    Ix: IndexType,
38{
39    pub fn new(map_ref: &'a IntervalMap<T, V, Ix>) -> Self {
40        Iter {
41            map_ref,
42            stack: left_link(map_ref, map_ref.root),
43        }
44    }
45}
46
47impl<'a, T, V, Ix> Iterator for Iter<'a, T, V, Ix>
48where
49    T: Ord,
50    Ix: IndexType,
51{
52    type Item = (&'a Interval<T>, &'a V);
53
54    #[inline]
55    fn next(&mut self) -> Option<Self::Item> {
56        if self.stack.is_empty() {
57            return None;
58        }
59        let x = self.stack.pop()?;
60        self.stack.extend(left_link(
61            self.map_ref,
62            self.map_ref.node_ref(x, Node::right),
63        ));
64        Some(self.map_ref.node_ref(x, |xn| (xn.interval(), xn.value())))
65    }
66}
67
68/// An into iterator over the entries of a `IntervalMap`.
69#[derive(Debug)]
70pub struct IntoIter<T, V, Ix>
71where
72    T: Ord,
73{
74    interval_map: IntervalMap<T, V, Ix>,
75    /// Stack for iteration
76    pub(crate) stack: Vec<NodeIndex<Ix>>,
77}
78
79impl<T, V, Ix> IntoIter<T, V, Ix>
80where
81    T: Ord,
82    Ix: IndexType,
83{
84    pub fn new(interval_map: IntervalMap<T, V, Ix>) -> Self {
85        let mut temp = IntoIter {
86            interval_map,
87            stack: vec![],
88        };
89        temp.stack = left_link(&temp.interval_map, temp.interval_map.root);
90        temp
91    }
92}
93
94impl<T, V, Ix> Iterator for IntoIter<T, V, Ix>
95where
96    T: Ord,
97    Ix: IndexType,
98{
99    type Item = (Interval<T>, V);
100
101    #[inline]
102    fn next(&mut self) -> Option<Self::Item> {
103        if self.stack.is_empty() {
104            return None;
105        }
106        let x = self.stack.pop()?;
107        self.stack.extend(left_link(
108            &self.interval_map,
109            self.interval_map.node_ref(x, Node::right),
110        ));
111        let res = &mut self.interval_map.nodes[x.index()];
112        Some((res.interval.take().unwrap(), res.value.take().unwrap()))
113    }
114}
115
116/// An unsorted iterator over the entries of a `IntervalMap`.
117#[derive(Debug)]
118pub struct UnsortedIter<'a, T, V, Ix>
119where
120    T: Ord,
121{
122    map_ref: &'a IntervalMap<T, V, Ix>,
123    /// Stack for iteration
124    pub(crate) cur: NodeIndex<Ix>,
125}
126
127impl<'a, T, V, Ix> UnsortedIter<'a, T, V, Ix>
128where
129    T: Ord,
130    Ix: IndexType,
131{
132    pub fn new(map_ref: &'a IntervalMap<T, V, Ix>) -> Self {
133        UnsortedIter {
134            map_ref,
135            cur: NodeIndex::SENTINEL,
136        }
137    }
138}
139
140impl<'a, T, V, Ix> Iterator for UnsortedIter<'a, T, V, Ix>
141where
142    T: Ord,
143    Ix: IndexType,
144{
145    type Item = (&'a Interval<T>, &'a V);
146
147    #[inline]
148    fn next(&mut self) -> Option<Self::Item> {
149        if self.map_ref.is_empty()
150            || self.cur.index() >= self.map_ref.len()
151            || self.cur.index() == <Ix as IndexType>::max().index()
152        {
153            return None;
154        }
155        self.cur = self.cur.inc();
156        Some(
157            self.map_ref
158                .node_ref(self.cur, |xn| (xn.interval(), xn.value())),
159        )
160    }
161}
162
163/// A filter iterator over the entries of a `IntervalMap`.It's equal to `iter().filter()`
164/// but faster than the latter.
165#[derive(Debug)]
166pub struct FilterIter<'a, T, V, Ix>
167where
168    T: Ord,
169{
170    /// Reference to the map
171    pub(crate) map_ref: &'a IntervalMap<T, V, Ix>,
172    /// Stack for iteration
173    pub(crate) stack: Vec<NodeIndex<Ix>>,
174    /// Filter criteria
175    pub(crate) query: &'a Interval<T>,
176}
177
178fn left_link_with_query<T, V, Ix>(
179    map_ref: &IntervalMap<T, V, Ix>,
180    mut x: NodeIndex<Ix>,
181    query: &Interval<T>,
182) -> Vec<NodeIndex<Ix>>
183where
184    T: Ord,
185    Ix: IndexType,
186{
187    let mut stack: Vec<NodeIndex<Ix>> = vec![];
188    if map_ref.max(x).is_some_and(|v| v <= &query.low) {
189        return stack;
190    }
191    while map_ref.node_ref(x, Node::sentinel).is_some() {
192        if map_ref.node_ref(x, Node::interval).low < query.high {
193            stack.push(x);
194        }
195        if map_ref.max(map_ref.node_ref(x, Node::left)) <= Some(&query.low) {
196            break;
197        }
198        x = map_ref.node_ref(x, Node::left);
199    }
200    stack
201}
202
203impl<'a, T, V, Ix> FilterIter<'a, T, V, Ix>
204where
205    T: Ord,
206    Ix: IndexType,
207{
208    pub fn new(map_ref: &'a IntervalMap<T, V, Ix>, query: &'a Interval<T>) -> Self {
209        FilterIter {
210            map_ref,
211            stack: left_link_with_query(map_ref, map_ref.root, query),
212            query,
213        }
214    }
215}
216
217impl<'a, T, V, Ix> Iterator for FilterIter<'a, T, V, Ix>
218where
219    T: Ord,
220    Ix: IndexType,
221{
222    type Item = (&'a Interval<T>, &'a V);
223
224    #[inline]
225    fn next(&mut self) -> Option<Self::Item> {
226        if self.stack.is_empty() {
227            return None;
228        }
229        let mut x = self.stack.pop()?;
230        while !self
231            .map_ref
232            .node_ref(x, Node::interval)
233            .overlaps(self.query)
234        {
235            self.stack.extend(left_link_with_query(
236                self.map_ref,
237                self.map_ref.node_ref(x, Node::right),
238                self.query,
239            ));
240            if self.stack.is_empty() {
241                return None;
242            }
243            x = self.stack.pop()?;
244        }
245        self.stack.extend(left_link_with_query(
246            self.map_ref,
247            self.map_ref.node_ref(x, Node::right),
248            self.query,
249        ));
250        Some(self.map_ref.node_ref(x, |xn| (xn.interval(), xn.value())))
251    }
252}
rb_interval_map/iter.rs

rb_interval_map/
iter.rs
