ic_stable_structures/btreemap/
iter.rs

1use super::{
2    node::{Node, NodeType},
3    BTreeMap,
4};
5use crate::{types::NULL, Address, Memory, Storable};
6use std::borrow::Cow;
7use std::ops::{Bound, RangeBounds};
8use std::rc::Rc;
9
10/// An indicator of the current position in the map.
11pub(crate) enum Cursor<K: Storable + Ord + Clone> {
12    Address(Address),
13    Node { node: Rc<Node<K>>, next: Index },
14}
15
16/// An index into a node's child or entry.
17pub(crate) enum Index {
18    Child(usize),
19    Entry(usize),
20}
21
22/// An iterator over the entries of a [`BTreeMap`].
23#[must_use = "iterators are lazy and do nothing unless consumed"]
24pub(crate) struct IterInternal<'a, K, V, M>
25where
26    K: Storable + Ord + Clone,
27    V: Storable,
28    M: Memory,
29{
30    // A reference to the map being iterated on.
31    map: &'a BTreeMap<K, V, M>,
32
33    // Flags indicating if the cursors have been initialized yet. These are needed to distinguish
34    // between the case where the iteration hasn't started yet and the case where the iteration has
35    // finished (in both cases the cursors will be empty).
36    forward_cursors_initialized: bool,
37    backward_cursors_initialized: bool,
38
39    // Stacks of cursors indicating the current iteration positions in the tree.
40    forward_cursors: Vec<Cursor<K>>,
41    backward_cursors: Vec<Cursor<K>>,
42
43    // The range of keys we want to traverse.
44    range: (Bound<K>, Bound<K>),
45}
46
47impl<'a, K, V, M> IterInternal<'a, K, V, M>
48where
49    K: Storable + Ord + Clone,
50    V: Storable,
51    M: Memory,
52{
53    pub(crate) fn new(map: &'a BTreeMap<K, V, M>) -> Self {
54        Self {
55            map,
56            forward_cursors_initialized: false,
57            backward_cursors_initialized: false,
58            forward_cursors: vec![],
59            backward_cursors: vec![],
60            range: (Bound::Unbounded, Bound::Unbounded),
61        }
62    }
63
64    /// Returns an empty iterator.
65    pub(crate) fn null(map: &'a BTreeMap<K, V, M>) -> Self {
66        Self {
67            map,
68            forward_cursors_initialized: true,
69            backward_cursors_initialized: true,
70            forward_cursors: vec![],
71            backward_cursors: vec![],
72            range: (Bound::Unbounded, Bound::Unbounded),
73        }
74    }
75
76    pub(crate) fn new_in_range(map: &'a BTreeMap<K, V, M>, range: (Bound<K>, Bound<K>)) -> Self {
77        Self {
78            map,
79            forward_cursors_initialized: false,
80            backward_cursors_initialized: false,
81            forward_cursors: vec![],
82            backward_cursors: vec![],
83            range,
84        }
85    }
86
87    fn initialize_forward_cursors(&mut self) {
88        debug_assert!(!self.forward_cursors_initialized);
89
90        match self.range.start_bound() {
91            Bound::Unbounded => {
92                self.forward_cursors
93                    .push(Cursor::Address(self.map.root_addr));
94            }
95            Bound::Included(key) | Bound::Excluded(key) => {
96                let mut node = self.map.load_node(self.map.root_addr);
97                loop {
98                    match node.search(key, self.map.memory()) {
99                        Ok(idx) => {
100                            if let Bound::Included(_) = self.range.start_bound() {
101                                // We found the key exactly matching the left bound.
102                                // Here is where we'll start the iteration.
103                                self.forward_cursors.push(Cursor::Node {
104                                    node: Rc::new(node),
105                                    next: Index::Entry(idx),
106                                });
107                                break;
108                            } else {
109                                // We found the key that we must
110                                // exclude.  We add its right neighbor
111                                // to the stack and start iterating
112                                // from its right child.
113                                let right_child = match node.node_type() {
114                                    NodeType::Internal => Some(node.child(idx + 1)),
115                                    NodeType::Leaf => None,
116                                };
117
118                                if idx + 1 < node.entries_len()
119                                    && self.range.contains(node.key(idx + 1, self.map.memory()))
120                                {
121                                    self.forward_cursors.push(Cursor::Node {
122                                        node: Rc::new(node),
123                                        next: Index::Entry(idx + 1),
124                                    });
125                                }
126                                if let Some(right_child) = right_child {
127                                    self.forward_cursors.push(Cursor::Address(right_child));
128                                }
129                                break;
130                            }
131                        }
132                        Err(idx) => {
133                            // The `idx` variable points to the first
134                            // key that is greater than the left
135                            // bound.
136                            //
137                            // If the index points to a valid node, we
138                            // will visit its left subtree and then
139                            // return to this key.
140                            //
141                            // If the index points at the end of
142                            // array, we'll continue with the right
143                            // child of the last key.
144
145                            // Load the left child of the node to visit if it exists.
146                            // This is done first to avoid cloning the node.
147                            let child = match node.node_type() {
148                                NodeType::Internal => {
149                                    // Note that loading a child node cannot fail since
150                                    // len(children) = len(entries) + 1
151                                    Some(self.map.load_node(node.child(idx)))
152                                }
153                                NodeType::Leaf => None,
154                            };
155
156                            if idx < node.entries_len()
157                                && self.range.contains(node.key(idx, self.map.memory()))
158                            {
159                                self.forward_cursors.push(Cursor::Node {
160                                    node: Rc::new(node),
161                                    next: Index::Entry(idx),
162                                });
163                            }
164
165                            match child {
166                                None => {
167                                    // Leaf node. Return an iterator with the found cursors.
168                                    break;
169                                }
170                                Some(child) => {
171                                    // Iterate over the child node.
172                                    node = child;
173                                }
174                            }
175                        }
176                    }
177                }
178            }
179        }
180        self.forward_cursors_initialized = true;
181    }
182
183    fn initialize_backward_cursors(&mut self) {
184        debug_assert!(!self.backward_cursors_initialized);
185
186        match self.range.end_bound() {
187            Bound::Unbounded => {
188                self.backward_cursors
189                    .push(Cursor::Address(self.map.root_addr));
190            }
191            Bound::Included(key) | Bound::Excluded(key) => {
192                let mut node = self.map.load_node(self.map.root_addr);
193                loop {
194                    match node.search(key, self.map.memory()) {
195                        Ok(idx) => {
196                            if let Bound::Included(_) = self.range.end_bound() {
197                                // We found the key exactly matching the right bound.
198                                // Here is where we'll start the iteration.
199                                self.backward_cursors.push(Cursor::Node {
200                                    node: Rc::new(node),
201                                    next: Index::Entry(idx),
202                                });
203                                break;
204                            } else {
205                                // We found the key that we must
206                                // exclude. We add its left neighbor
207                                // to the stack and start iterating
208                                // from its left child.
209                                let left_child = match node.node_type() {
210                                    NodeType::Internal => Some(node.child(idx)),
211                                    NodeType::Leaf => None,
212                                };
213
214                                if idx > 0
215                                    && self.range.contains(node.key(idx - 1, self.map.memory()))
216                                {
217                                    self.backward_cursors.push(Cursor::Node {
218                                        node: Rc::new(node),
219                                        next: Index::Entry(idx - 1),
220                                    });
221                                }
222                                if let Some(left_child) = left_child {
223                                    self.backward_cursors.push(Cursor::Address(left_child));
224                                }
225                                break;
226                            }
227                        }
228                        Err(idx) => {
229                            // The `idx` variable points to the first
230                            // key that is greater than the right
231                            // bound.
232                            //
233                            // If the index points to a valid node, we
234                            // will visit its left subtree.
235                            //
236                            // If the index points at the end of
237                            // array, we'll continue with the right
238                            // child of the last key.
239
240                            // Load the left child of the node to visit if it exists.
241                            // This is done first to avoid cloning the node.
242                            let child = match node.node_type() {
243                                NodeType::Internal => {
244                                    // Note that loading a child node cannot fail since
245                                    // len(children) = len(entries) + 1
246                                    Some(self.map.load_node(node.child(idx)))
247                                }
248                                NodeType::Leaf => None,
249                            };
250
251                            if idx > 0 && self.range.contains(node.key(idx - 1, self.map.memory()))
252                            {
253                                self.backward_cursors.push(Cursor::Node {
254                                    node: Rc::new(node),
255                                    next: Index::Entry(idx - 1),
256                                });
257                            }
258
259                            match child {
260                                None => {
261                                    // Leaf node. Return an iterator with the found cursors.
262                                    break;
263                                }
264                                Some(child) => {
265                                    // Iterate over the child node.
266                                    node = child;
267                                }
268                            }
269                        }
270                    }
271                }
272            }
273        }
274        self.backward_cursors_initialized = true;
275    }
276
277    // Iterates to find the next element in the requested range.
278    // If it exists, `map` is applied to that element and the result is returned.
279    fn next_map<T, F: Fn(&Rc<Node<K>>, usize) -> T>(&mut self, map: F) -> Option<T> {
280        if !self.forward_cursors_initialized {
281            self.initialize_forward_cursors();
282        }
283
284        // If the cursors are empty. Iteration is complete.
285        match self.forward_cursors.pop()? {
286            Cursor::Address(address) => {
287                if address != NULL {
288                    // Load the node at the given address, and add it to the cursors.
289                    let node = self.map.load_node(address);
290                    self.forward_cursors.push(Cursor::Node {
291                        next: match node.node_type() {
292                            // Iterate on internal nodes starting from the first child.
293                            NodeType::Internal => Index::Child(0),
294                            // Iterate on leaf nodes starting from the first entry.
295                            NodeType::Leaf => Index::Entry(0),
296                        },
297                        node: Rc::new(node),
298                    });
299                }
300                self.next_map(map)
301            }
302
303            Cursor::Node {
304                node,
305                next: Index::Child(child_idx),
306            } => {
307                let child_address = node.child(child_idx);
308
309                if child_idx < node.entries_len() {
310                    // After iterating on the child, iterate on the next _entry_ in this node.
311                    // The entry immediately after the child has the same index as the child's.
312                    self.forward_cursors.push(Cursor::Node {
313                        node,
314                        next: Index::Entry(child_idx),
315                    });
316                }
317
318                // Add the child to the top of the cursors to be iterated on first.
319                self.forward_cursors.push(Cursor::Address(child_address));
320
321                self.next_map(map)
322            }
323
324            Cursor::Node {
325                node,
326                next: Index::Entry(entry_idx),
327            } => {
328                // If the key does not belong to the range, iteration stops.
329                if !self.range.contains(node.key(entry_idx, self.map.memory())) {
330                    // Clear all cursors to avoid needless work in subsequent calls.
331                    self.forward_cursors = vec![];
332                    self.backward_cursors = vec![];
333                    return None;
334                }
335
336                let res = map(&node, entry_idx);
337                self.range.0 = Bound::Excluded(node.key(entry_idx, self.map.memory()).clone());
338
339                let next = match node.node_type() {
340                    // If this is an internal node, add the next child to the cursors.
341                    NodeType::Internal => Index::Child(entry_idx + 1),
342                    // If this is a leaf node, and it contains another entry, add the
343                    // next entry to the cursors.
344                    NodeType::Leaf if entry_idx + 1 < node.entries_len() => {
345                        Index::Entry(entry_idx + 1)
346                    }
347                    _ => return Some(res),
348                };
349
350                // Add to the cursors the next element to be traversed.
351                self.forward_cursors.push(Cursor::Node { next, node });
352                Some(res)
353            }
354        }
355    }
356
357    // Iterates to find the next back element in the requested range.
358    // If it exists, `map` is applied to that element and the result is returned.
359    fn next_back_map<T, F: Fn(&Rc<Node<K>>, usize) -> T>(&mut self, map: F) -> Option<T> {
360        if !self.backward_cursors_initialized {
361            self.initialize_backward_cursors();
362        }
363
364        // If the cursors are empty. Iteration is complete.
365        match self.backward_cursors.pop()? {
366            Cursor::Address(address) => {
367                if address != NULL {
368                    // Load the node at the given address, and add it to the cursors.
369                    let node = self.map.load_node(address);
370                    if let Some(next) = match node.node_type() {
371                        // Iterate on internal nodes starting from the last child.
372                        NodeType::Internal if node.children_len() > 0 => {
373                            Some(Index::Child(node.children_len() - 1))
374                        }
375                        // Iterate on leaf nodes starting from the last entry.
376                        NodeType::Leaf if node.entries_len() > 0 => {
377                            Some(Index::Entry(node.entries_len() - 1))
378                        }
379                        _ => None,
380                    } {
381                        self.backward_cursors.push(Cursor::Node {
382                            next,
383                            node: Rc::new(node),
384                        });
385                    }
386                }
387                self.next_back_map(map)
388            }
389
390            Cursor::Node {
391                node,
392                next: Index::Child(child_idx),
393            } => {
394                let child_address = node.child(child_idx);
395
396                if 0 < child_idx {
397                    // After iterating on the child, iterate on the previous _entry_ in this node.
398                    self.backward_cursors.push(Cursor::Node {
399                        node,
400                        next: Index::Entry(child_idx - 1),
401                    });
402                }
403
404                // Add the child to the top of the cursors to be iterated on first.
405                self.backward_cursors.push(Cursor::Address(child_address));
406
407                self.next_back_map(map)
408            }
409
410            Cursor::Node {
411                node,
412                next: Index::Entry(entry_idx),
413            } => {
414                // If the key does not belong to the range, iteration stops.
415                if !self.range.contains(node.key(entry_idx, self.map.memory())) {
416                    // Clear all cursors to avoid needless work in subsequent calls.
417                    self.forward_cursors = vec![];
418                    self.backward_cursors = vec![];
419                    return None;
420                }
421
422                let res = map(&node, entry_idx);
423                self.range.1 = Bound::Excluded(node.key(entry_idx, self.map.memory()).clone());
424
425                if let Some(next) = match node.node_type() {
426                    // If this is an internal node, add the previous child to the cursors.
427                    NodeType::Internal => Some(Index::Child(entry_idx)),
428                    // If this is a leaf node, add the previous entry to the cursors.
429                    NodeType::Leaf if entry_idx > 0 => Some(Index::Entry(entry_idx - 1)),
430                    _ => None,
431                } {
432                    // Add to the cursors the next element to be traversed.
433                    self.backward_cursors.push(Cursor::Node { next, node });
434                }
435
436                Some(res)
437            }
438        }
439    }
440
441    fn count(&mut self) -> usize {
442        let mut cnt = 0;
443        while self.next_map(|_, _| ()).is_some() {
444            cnt += 1;
445        }
446        cnt
447    }
448}
449
450/// A lazily evaluated key-value entry from a `BTreeMap` iterator.
451///
452/// This struct defers deserialization and cloning of the key and value
453/// until they are explicitly accessed, improving performance.
454pub struct LazyEntry<'a, K, V, M>
455where
456    K: Storable + Ord + Clone,
457    V: Storable,
458    M: Memory,
459{
460    node: Rc<Node<K>>,
461    entry_idx: usize,
462    map: &'a BTreeMap<K, V, M>,
463}
464
465impl<K, V, M> LazyEntry<'_, K, V, M>
466where
467    K: Storable + Ord + Clone,
468    V: Storable,
469    M: Memory,
470{
471    /// Returns a reference to the key.
472    pub fn key(&self) -> &K {
473        self.node.key(self.entry_idx, self.map.memory())
474    }
475
476    /// Returns the value by deserializing it.
477    pub fn value(&self) -> V {
478        let encoded_value = self.node.value(self.entry_idx, self.map.memory());
479        V::from_bytes(Cow::Borrowed(encoded_value))
480    }
481
482    /// Converts the entry into an owned (K, V) pair.
483    pub fn into_pair(self) -> (K, V) {
484        (self.key().clone(), self.value())
485    }
486}
487
488pub struct Iter<'a, K, V, M>(IterInternal<'a, K, V, M>)
489where
490    K: Storable + Ord + Clone,
491    V: Storable,
492    M: Memory;
493
494impl<'a, K, V, M> Iterator for Iter<'a, K, V, M>
495where
496    K: Storable + Ord + Clone,
497    V: Storable,
498    M: Memory,
499{
500    type Item = LazyEntry<'a, K, V, M>;
501
502    fn next(&mut self) -> Option<Self::Item> {
503        self.0.next_map(|node, entry_idx| LazyEntry {
504            node: node.clone(),
505            entry_idx,
506            map: self.0.map,
507        })
508    }
509
510    fn count(mut self) -> usize
511    where
512        Self: Sized,
513    {
514        self.0.count()
515    }
516}
517
518impl<K, V, M> DoubleEndedIterator for Iter<'_, K, V, M>
519where
520    K: Storable + Ord + Clone,
521    V: Storable,
522    M: Memory,
523{
524    fn next_back(&mut self) -> Option<Self::Item> {
525        self.0.next_back_map(|node, entry_idx| LazyEntry {
526            node: node.clone(),
527            entry_idx,
528            map: self.0.map,
529        })
530    }
531}
532
533pub struct KeysIter<'a, K, V, M>(IterInternal<'a, K, V, M>)
534where
535    K: Storable + Ord + Clone,
536    V: Storable,
537    M: Memory;
538
539impl<K, V, M> Iterator for KeysIter<'_, K, V, M>
540where
541    K: Storable + Ord + Clone,
542    V: Storable,
543    M: Memory,
544{
545    type Item = K;
546
547    fn next(&mut self) -> Option<Self::Item> {
548        self.0
549            .next_map(|node, entry_idx| node.key(entry_idx, self.0.map.memory()).clone())
550    }
551
552    fn count(mut self) -> usize
553    where
554        Self: Sized,
555    {
556        self.0.count()
557    }
558}
559
560impl<K, V, M> DoubleEndedIterator for KeysIter<'_, K, V, M>
561where
562    K: Storable + Ord + Clone,
563    V: Storable,
564    M: Memory,
565{
566    fn next_back(&mut self) -> Option<Self::Item> {
567        self.0
568            .next_back_map(|node, entry_idx| node.key(entry_idx, self.0.map.memory()).clone())
569    }
570}
571
572pub struct ValuesIter<'a, K, V, M>(IterInternal<'a, K, V, M>)
573where
574    K: Storable + Ord + Clone,
575    V: Storable,
576    M: Memory;
577
578impl<K, V, M> Iterator for ValuesIter<'_, K, V, M>
579where
580    K: Storable + Ord + Clone,
581    V: Storable,
582    M: Memory,
583{
584    type Item = V;
585
586    fn next(&mut self) -> Option<Self::Item> {
587        self.0.next_map(|node, entry_idx| {
588            let encoded_value = node.value(entry_idx, self.0.map.memory());
589            V::from_bytes(Cow::Borrowed(encoded_value))
590        })
591    }
592
593    fn count(mut self) -> usize
594    where
595        Self: Sized,
596    {
597        self.0.count()
598    }
599}
600
601impl<K, V, M> DoubleEndedIterator for ValuesIter<'_, K, V, M>
602where
603    K: Storable + Ord + Clone,
604    V: Storable,
605    M: Memory,
606{
607    fn next_back(&mut self) -> Option<Self::Item> {
608        self.0.next_back_map(|node, entry_idx| {
609            let encoded_value = node.value(entry_idx, self.0.map.memory());
610            V::from_bytes(Cow::Borrowed(encoded_value))
611        })
612    }
613}
614
615impl<'a, K, V, M> From<IterInternal<'a, K, V, M>> for Iter<'a, K, V, M>
616where
617    K: Storable + Ord + Clone,
618    V: Storable,
619    M: Memory,
620{
621    fn from(value: IterInternal<'a, K, V, M>) -> Self {
622        Iter(value)
623    }
624}
625
626impl<'a, K, V, M> From<IterInternal<'a, K, V, M>> for KeysIter<'a, K, V, M>
627where
628    K: Storable + Ord + Clone,
629    V: Storable,
630    M: Memory,
631{
632    fn from(value: IterInternal<'a, K, V, M>) -> Self {
633        KeysIter(value)
634    }
635}
636
637impl<'a, K, V, M> From<IterInternal<'a, K, V, M>> for ValuesIter<'a, K, V, M>
638where
639    K: Storable + Ord + Clone,
640    V: Storable,
641    M: Memory,
642{
643    fn from(value: IterInternal<'a, K, V, M>) -> Self {
644        ValuesIter(value)
645    }
646}
647
648#[cfg(test)]
649mod test {
650    use super::*;
651    use std::cell::RefCell;
652    use std::rc::Rc;
653
654    fn make_memory() -> Rc<RefCell<Vec<u8>>> {
655        Rc::new(RefCell::new(Vec::new()))
656    }
657
658    #[test]
659    fn iterate_leaf() {
660        let mem = make_memory();
661        let mut btree = BTreeMap::new(mem);
662
663        for i in 0..10u8 {
664            btree.insert(i, i + 1);
665        }
666
667        let mut i = 0;
668        for entry in btree.iter() {
669            assert_eq!(*entry.key(), i);
670            assert_eq!(entry.value(), i + 1);
671            i += 1;
672        }
673
674        assert_eq!(i, 10u8);
675    }
676
677    #[test]
678    fn iterate_children() {
679        let mem = make_memory();
680        let mut btree = BTreeMap::new(mem);
681
682        // Insert the elements in reverse order.
683        for i in (0..100u64).rev() {
684            btree.insert(i, i + 1);
685        }
686
687        // Iteration should be in ascending order.
688        let mut i = 0;
689        for entry in btree.iter() {
690            assert_eq!(*entry.key(), i);
691            assert_eq!(entry.value(), i + 1);
692            i += 1;
693        }
694
695        assert_eq!(i, 100);
696    }
697
698    #[test]
699    fn iterate_range() {
700        let mem = make_memory();
701        let mut btree = BTreeMap::new(mem);
702
703        // Insert the elements in reverse order.
704        for i in (0..100u64).rev() {
705            btree.insert(i, i + 1);
706        }
707
708        // Iteration should be in ascending order.
709        let mut i = 10;
710        for entry in btree.range(10..90) {
711            assert_eq!(*entry.key(), i);
712            assert_eq!(entry.value(), i + 1);
713            i += 1;
714        }
715
716        assert_eq!(i, 90);
717    }
718
719    #[test]
720    fn iterate_reverse() {
721        let mem = make_memory();
722        let mut btree = BTreeMap::new(mem);
723
724        // Insert the elements in reverse order.
725        for i in (0..100u64).rev() {
726            btree.insert(i, i + 1);
727        }
728
729        // Iteration should be in descending order.
730        let mut i = 100;
731        for entry in btree.iter().rev() {
732            i -= 1;
733            assert_eq!(*entry.key(), i);
734            assert_eq!(entry.value(), i + 1);
735        }
736
737        assert_eq!(i, 0);
738    }
739
740    #[test]
741    fn iterate_range_reverse() {
742        let mem = make_memory();
743        let mut btree = BTreeMap::new(mem);
744
745        // Insert the elements in reverse order.
746        for i in (0..100u64).rev() {
747            btree.insert(i, i + 1);
748        }
749
750        // Iteration should be in descending order.
751        let mut i = 80;
752        for entry in btree.range(20..80).rev() {
753            i -= 1;
754            assert_eq!(*entry.key(), i);
755            assert_eq!(entry.value(), i + 1);
756        }
757
758        assert_eq!(i, 20);
759    }
760
761    #[test]
762    fn iterate_from_both_ends() {
763        let mem = make_memory();
764        let mut btree = BTreeMap::new(mem);
765
766        // Insert the elements in reverse order.
767        for i in (0..100u64).rev() {
768            btree.insert(i, i + 1);
769        }
770
771        let mut iter = btree.iter();
772
773        for i in 0..50 {
774            let entry = iter.next().unwrap();
775            assert_eq!(*entry.key(), i);
776            assert_eq!(entry.value(), i + 1);
777
778            let entry = iter.next_back().unwrap();
779            assert_eq!(*entry.key(), 99 - i);
780            assert_eq!(entry.value(), 100 - i);
781        }
782
783        assert!(iter.next().is_none());
784        assert!(iter.next_back().is_none());
785    }
786
787    #[test]
788    fn iterate_range_from_both_ends() {
789        let mem = make_memory();
790        let mut btree = BTreeMap::new(mem);
791
792        // Insert the elements in reverse order.
793        for i in (0..100u64).rev() {
794            btree.insert(i, i + 1);
795        }
796
797        let mut iter = btree.range(30..70);
798
799        for i in 0..20 {
800            let entry = iter.next().unwrap();
801            assert_eq!(*entry.key(), 30 + i);
802            assert_eq!(entry.value(), 31 + i);
803
804            let entry = iter.next_back().unwrap();
805            assert_eq!(*entry.key(), 69 - i);
806            assert_eq!(entry.value(), 70 - i);
807        }
808
809        assert!(iter.next().is_none());
810        assert!(iter.next_back().is_none());
811    }
812
813    #[test]
814    fn keys_from_both_ends() {
815        let mem = make_memory();
816        let mut btree = BTreeMap::new(mem);
817
818        // Insert the elements in reverse order.
819        for i in (0..100u64).rev() {
820            btree.insert(i, i + 1);
821        }
822
823        let mut iter = btree.keys();
824
825        for i in 0..50 {
826            let key = iter.next().unwrap();
827            assert_eq!(key, i);
828
829            let key = iter.next_back().unwrap();
830            assert_eq!(key, 99 - i);
831        }
832
833        assert!(iter.next().is_none());
834        assert!(iter.next_back().is_none());
835    }
836
837    #[test]
838    fn keys_range_from_both_ends() {
839        let mem = make_memory();
840        let mut btree = BTreeMap::new(mem);
841
842        // Insert the elements in reverse order.
843        for i in (0..100u64).rev() {
844            btree.insert(i, i + 1);
845        }
846
847        let mut iter = btree.keys_range(30..70);
848
849        for i in 0..20 {
850            let key = iter.next().unwrap();
851            assert_eq!(key, 30 + i);
852
853            let key = iter.next_back().unwrap();
854            assert_eq!(key, 69 - i);
855        }
856
857        assert!(iter.next().is_none());
858        assert!(iter.next_back().is_none());
859    }
860
861    #[test]
862    fn values_from_both_ends() {
863        let mem = make_memory();
864        let mut btree = BTreeMap::new(mem);
865
866        // Insert the elements in reverse order.
867        for i in (0..100u64).rev() {
868            btree.insert(i, i + 1);
869        }
870
871        let mut iter = btree.values();
872
873        for i in 0..50 {
874            let value = iter.next().unwrap();
875            assert_eq!(value, i + 1);
876
877            let value = iter.next_back().unwrap();
878            assert_eq!(value, 100 - i);
879        }
880
881        assert!(iter.next().is_none());
882        assert!(iter.next_back().is_none());
883    }
884
885    #[test]
886    fn values_range_from_both_ends() {
887        let mem = make_memory();
888        let mut btree = BTreeMap::new(mem);
889
890        // Insert the elements in reverse order.
891        for i in (0..100u64).rev() {
892            btree.insert(i, i + 1);
893        }
894
895        let mut iter = btree.values_range(30..70);
896
897        for i in 0..20 {
898            let value = iter.next().unwrap();
899            assert_eq!(value, 31 + i);
900
901            let value = iter.next_back().unwrap();
902            assert_eq!(value, 70 - i);
903        }
904
905        assert!(iter.next().is_none());
906        assert!(iter.next_back().is_none());
907    }
908}
ic_stable_structures/btreemap/iter.rs

ic_stable_structures/btreemap/
iter.rs
