convenient_skiplist/
iter.rs

1use crate::{Node, NodeValue, RangeHint, SkipList};
2use core::ops::{Bound, RangeBounds};
3use std::hint::unreachable_unchecked;
4
5pub(crate) struct VerticalIter<T> {
6    curr_node: Option<*mut Node<T>>,
7}
8
9impl<T> VerticalIter<T> {
10    pub(crate) fn new(curr_node: *mut Node<T>) -> Self {
11        Self {
12            curr_node: Some(curr_node),
13        }
14    }
15}
16
17impl<T> Iterator for VerticalIter<T> {
18    type Item = *mut Node<T>;
19    fn next(&mut self) -> Option<Self::Item> {
20        let next = self
21            .curr_node
22            .and_then(|n| unsafe { (*n).down })
23            .map(|p| p.as_ptr());
24
25        std::mem::replace(&mut self.curr_node, next)
26    }
27}
28
29/// Iterator to grab all values from the right of `curr_node`
30pub(crate) struct NodeRightIter<T> {
31    curr_node: *mut Node<T>,
32}
33
34impl<T> NodeRightIter<T> {
35    pub(crate) fn new(curr_node: *mut Node<T>) -> Self {
36        Self { curr_node }
37    }
38}
39
40impl<T: Clone> Iterator for NodeRightIter<T> {
41    type Item = T;
42
43    #[inline]
44    fn next(&mut self) -> Option<Self::Item> {
45        unsafe {
46            let next = (*self.curr_node).right?.as_ptr();
47            let ret = std::mem::replace(&mut self.curr_node, next);
48            Some((*ret).value.get_value().clone())
49        }
50    }
51}
52
53/// Struct to keep track of things for IntoIterator
54/// *Warning*: As all nodes are heap allocated, we have
55/// to clone them to produce type T.
56pub struct IntoIter<T> {
57    _skiplist: SkipList<T>,
58    curr_node: *mut Node<T>,
59    finished: bool,
60    total_len: usize,
61}
62
63impl<T: Clone> Iterator for IntoIter<T> {
64    type Item = T;
65
66    #[inline]
67    fn next(&mut self) -> Option<Self::Item> {
68        if self.finished {
69            return None;
70        }
71        unsafe {
72            match (*self.curr_node).right {
73                Some(right) => {
74                    self.curr_node = right.as_ptr();
75                    Some((*self.curr_node).value.get_value().clone())
76                }
77                None => {
78                    self.finished = true;
79                    Some((*self.curr_node).value.get_value().clone())
80                }
81            }
82        }
83    }
84
85    #[inline]
86    fn size_hint(&self) -> (usize, Option<usize>) {
87        (self.total_len, Some(self.total_len))
88    }
89}
90
91impl<T: PartialOrd + Clone> IntoIterator for SkipList<T> {
92    type Item = T;
93    type IntoIter = IntoIter<T>;
94
95    fn into_iter(self) -> Self::IntoIter {
96        IntoIter {
97            total_len: self.len,
98            curr_node: self.top_left.as_ptr(),
99            _skiplist: self,
100            finished: false,
101        }
102    }
103}
104
105// TODO: Drain
106// pub struct Drain<T> {
107//     curr_node: *mut Node<T>,
108//     finished: bool,
109// }
110
111// impl<T: Clone> Iterator for Drain<T> {
112//     type Item = T;
113//     fn next(&mut self) -> Option<Self::Item> {
114//         if self.finished {
115//             return None;
116//         }
117//         unsafe {
118//             match (*self.curr_node).right {
119//                 Some(right) => {
120//                     let ret = std::mem::replace(&mut self.curr_node, right.as_ptr());
121//                     let ret = Box::from_raw(ret);
122//                     return Some(ret.value.get_value().clone());
123//                 }
124//                 None => {
125//                     self.finished = true;
126//                     return Some(Box::from_raw(self.curr_node).value.get_value().clone());
127//                 }
128//             };
129//         };
130//     }
131// }
132
133/// IterAll is a iterator struct to iterate over the entire
134/// linked list.
135///
136/// You should use the method `iter_all` on [SkipList](convenient-skiplist::SkipList)
137pub struct IterAll<'a, T> {
138    curr_node: &'a Node<T>,
139    at_bottom: bool,
140    finished: bool,
141    total_len: usize,
142}
143
144impl<'a, T> IterAll<'a, T> {
145    #[inline]
146    pub(crate) fn new(curr_node: &'a Node<T>, total_len: usize) -> Self {
147        Self {
148            curr_node,
149            at_bottom: false,
150            finished: false,
151            total_len,
152        }
153    }
154}
155
156impl<'a, T: PartialOrd> Iterator for IterAll<'a, T> {
157    type Item = &'a T;
158    #[inline]
159    fn next(&mut self) -> Option<Self::Item> {
160        if self.finished {
161            return None;
162        }
163        // step 1: Hit the bottom
164        if !self.at_bottom {
165            unsafe {
166                while let Some(down) = self.curr_node.down.as_ref() {
167                    self.curr_node = down.as_ref();
168                }
169            }
170            // step 2: Go one to the right
171            unsafe {
172                self.curr_node = self.curr_node.right.unwrap().as_ptr().as_ref().unwrap();
173            }
174            self.at_bottom = true;
175        }
176        unsafe {
177            match self.curr_node.value {
178                NodeValue::NegInf => {
179                    self.curr_node = self.curr_node.right.unwrap().as_ptr().as_ref().unwrap();
180                }
181                NodeValue::PosInf => return None,
182                NodeValue::Value(..) => {}
183            };
184            if self.curr_node.right.unwrap().as_ref().value == NodeValue::PosInf {
185                self.finished = true;
186                Some(self.curr_node.value.get_value())
187            } else {
188                let next = self.curr_node.right.unwrap().as_ptr().as_ref().unwrap();
189                let to_ret = std::mem::replace(&mut self.curr_node, next);
190                Some(to_ret.value.get_value())
191            }
192        }
193    }
194
195    #[inline]
196    fn size_hint(&self) -> (usize, Option<usize>) {
197        (self.total_len, Some(self.total_len))
198    }
199}
200
201pub struct SkipListIndexRange<'a, R: RangeBounds<usize>, T> {
202    range: R,
203    curr_node: *const Node<T>,
204    curr_index: usize,
205    phantom: std::marker::PhantomData<&'a T>,
206}
207
208impl<'a, R: RangeBounds<usize>, T> SkipListIndexRange<'a, R, T> {
209    pub(crate) fn new(curr_node: *const Node<T>, range: R) -> Self {
210        let mut curr_node = curr_node;
211        // Find closest starting node
212        let mut curr_index = 0;
213        let mut curr_node = match range.start_bound() {
214            Bound::Unbounded => {
215                while let Some(down) = unsafe { (*curr_node).down } {
216                    curr_node = down.as_ptr();
217                }
218                // Advance once to the right from neginf
219                unsafe { (*curr_node).right.unwrap().as_ptr() }
220            }
221            bound => loop {
222                unsafe {
223                    match ((*curr_node).right, (*curr_node).down) {
224                        (Some(right), Some(down)) => {
225                            let idx = match bound {
226                                Bound::Included(&idx) => {
227                                    let idx = idx + 1;
228                                    if curr_index == idx {
229                                        break curr_node;
230                                    }
231                                    idx
232                                }
233                                Bound::Excluded(&idx) => {
234                                    let idx = idx + 1;
235                                    if curr_index == idx {
236                                        break right.as_ptr();
237                                    }
238                                    idx
239                                }
240                                _ => unreachable_unchecked(),
241                            };
242                            let width = (*curr_node).width;
243                            if curr_index + width <= idx {
244                                curr_node = right.as_ptr() as *const _;
245                                curr_index += width;
246                            } else {
247                                curr_node = down.as_ptr();
248                            }
249                        }
250                        (Some(right), None) => {
251                            match bound {
252                                Bound::Included(&idx) => {
253                                    if curr_index == idx + 1 {
254                                        break curr_node;
255                                    }
256                                }
257                                Bound::Excluded(&idx) => {
258                                    if curr_index == idx + 1 {
259                                        break right.as_ptr();
260                                    }
261                                }
262                                _ => unreachable_unchecked(),
263                            };
264                            curr_node = right.as_ptr();
265                            curr_index += (*curr_node).width;
266                        }
267                        (None, None) => {
268                            break curr_node;
269                        }
270                        _ => unreachable!("264"),
271                    }
272                }
273            },
274        };
275        // Make sure we reach the bottom
276        while let Some(down) = unsafe { (*curr_node).down } {
277            curr_node = down.as_ptr();
278        }
279        Self {
280            range,
281            curr_node,
282            curr_index: curr_index.saturating_sub(1),
283            phantom: std::marker::PhantomData::default(),
284        }
285    }
286}
287
288macro_rules! get_value_and_advance {
289    ($curr:expr, $right:expr) => {{
290        Some(
291            (*std::mem::replace($curr, $right.as_ptr()))
292                .value
293                .get_value(),
294        )
295    }};
296}
297
298impl<'a, T, R: RangeBounds<usize>> Iterator for SkipListIndexRange<'a, R, T> {
299    type Item = &'a T;
300    fn next(&mut self) -> Option<Self::Item> {
301        unsafe {
302            debug_assert!((*self.curr_node).down.is_none());
303            let right = (*self.curr_node).right?;
304            match self.range.end_bound() {
305                Bound::Unbounded => get_value_and_advance!(&mut self.curr_node, right),
306                Bound::Included(&idx) => {
307                    if self.curr_index > idx {
308                        return None;
309                    }
310                    self.curr_index += 1;
311                    get_value_and_advance!(&mut self.curr_node, right)
312                }
313                Bound::Excluded(&idx) => {
314                    if self.curr_index == idx {
315                        return None;
316                    }
317                    self.curr_index += 1;
318                    get_value_and_advance!(&mut self.curr_node, right)
319                }
320            }
321        }
322    }
323}
324
325pub struct SkipListRange<'a, T> {
326    curr_node: &'a Node<T>,
327    start: &'a T,
328    end: &'a T,
329    at_bottom: bool,
330}
331
332impl<'a, T> SkipListRange<'a, T> {
333    pub(crate) fn new(curr_node: &'a Node<T>, start: &'a T, end: &'a T) -> Self {
334        Self {
335            curr_node,
336            start,
337            end,
338            at_bottom: false,
339        }
340    }
341}
342
343impl<'a, T: PartialOrd> Iterator for SkipListRange<'a, T> {
344    type Item = &'a T;
345    #[inline]
346    fn next(&mut self) -> Option<Self::Item> {
347        // Step 1: Find the first node >= self.start
348        while !self.at_bottom {
349            match (self.curr_node.right, self.curr_node.down) {
350                (Some(right), Some(down)) => unsafe {
351                    if &right.as_ref().value < self.start {
352                        self.curr_node = right.as_ptr().as_ref().unwrap();
353                    } else {
354                        self.curr_node = down.as_ptr().as_ref().unwrap();
355                    }
356                },
357                (Some(right), None) => unsafe {
358                    if &right.as_ref().value < self.start {
359                        self.curr_node = right.as_ptr().as_ref().unwrap();
360                    } else {
361                        self.at_bottom = true;
362                        self.curr_node = self.curr_node.right.unwrap().as_ptr().as_ref().unwrap();
363                        break;
364                    }
365                },
366                _ => unreachable!(),
367            }
368        }
369        // Verify that we are, indeed, at the bottom
370        debug_assert!(self.curr_node.down.is_none());
371        if &self.curr_node.value <= self.end {
372            unsafe {
373                let ret_val = &self.curr_node.value;
374                let next = self.curr_node.right.unwrap().as_ptr().as_ref().unwrap();
375                self.curr_node = next;
376                return Some(ret_val.get_value());
377            }
378        }
379        None
380    }
381}
382
383#[derive(Clone)]
384pub(crate) struct NodeWidth<T> {
385    pub curr_node: *mut Node<T>,
386    /// The total width traveled so _far_ in the iterator.
387    /// The last iteration is guaranteed to be the true width from
388    /// negative infinity to the element.
389    pub curr_width: usize,
390}
391
392impl<T> NodeWidth<T> {
393    pub(crate) fn new(curr_node: *mut Node<T>, curr_width: usize) -> Self {
394        Self {
395            curr_node,
396            curr_width,
397        }
398    }
399}
400
401pub(crate) struct LeftBiasIterWidth<'a, T> {
402    curr_node: *mut Node<T>,
403    total_width: usize,
404    item: &'a T,
405    finished: bool,
406}
407
408impl<'a, T> LeftBiasIterWidth<'a, T> {
409    pub(crate) fn new(curr_node: *mut Node<T>, item: &'a T) -> Self {
410        Self {
411            curr_node,
412            item,
413            finished: false,
414            total_width: 0,
415        }
416    }
417}
418
419impl<'a, T: PartialOrd> Iterator for LeftBiasIterWidth<'a, T> {
420    type Item = NodeWidth<T>;
421    #[inline]
422    fn next(&mut self) -> Option<Self::Item> {
423        if self.finished {
424            return None;
425        }
426        unsafe {
427            loop {
428                match ((*self.curr_node).right, (*self.curr_node).down) {
429                    // We're somewhere in the middle of the skiplist
430                    (Some(right), Some(down)) => {
431                        // The node our right is smaller than `item`, so let's advance forward.
432                        if &right.as_ref().value < self.item {
433                            self.total_width += (*self.curr_node).width;
434                            self.curr_node = right.as_ptr();
435                        } else {
436                            // The node to our right is the first seen that's larger than `item`,
437                            // So we yield it and head down.
438                            let ret_node = std::mem::replace(&mut self.curr_node, down.as_ptr());
439                            return Some(NodeWidth::new(ret_node, self.total_width));
440                        }
441                    }
442                    // We're at the bottom of the skiplist
443                    (Some(right), None) => {
444                        // We're at the bottom row, and the item to our right >= `self.item`.
445                        // This is exactly the same as a linked list -- we don't want to continue further.
446                        if &right.as_ref().value >= self.item {
447                            self.finished = true;
448                            return Some(NodeWidth::new(self.curr_node, self.total_width));
449                        } else {
450                            // The node to our right is _smaller_ than us, so continue forward.
451                            self.curr_node = right.as_ptr();
452                            self.total_width += 1;
453                        }
454                    }
455                    // If we've upheld invariants correctly, there's always a right when iterating
456                    // Otherwise, some element was larger than NodeValue::PosInf.
457                    _ => unreachable!(),
458                }
459            }
460        }
461    }
462}
463/// Left-biased iteration towards `item`.
464///
465/// Guaranteed to return an iterator of items directly left of `item`,
466/// or where `item` should be in the skiplist.
467pub(crate) struct LeftBiasIter<'a, T> {
468    curr_node: *mut Node<T>,
469    item: &'a T,
470    finished: bool,
471}
472
473impl<'a, T> LeftBiasIter<'a, T> {
474    pub(crate) fn new(curr_node: *mut Node<T>, item: &'a T) -> Self {
475        Self {
476            curr_node,
477            item,
478            finished: false,
479        }
480    }
481}
482
483impl<'a, T: PartialOrd> Iterator for LeftBiasIter<'a, T> {
484    type Item = *mut Node<T>;
485    #[inline]
486    fn next(&mut self) -> Option<Self::Item> {
487        if self.finished {
488            return None;
489        }
490        unsafe {
491            loop {
492                match ((*self.curr_node).right, (*self.curr_node).down) {
493                    // We're somewhere in the middle of the skiplist, so if `self.item` is larger than our right,
494                    (Some(right), Some(down)) => {
495                        // The node our right is smaller than `item`, so let's advance forward.
496                        if &right.as_ref().value < self.item {
497                            self.curr_node = right.as_ptr();
498                        } else {
499                            // The node to our right is the first seen that's larger than `item`,
500                            // So we yield it and head down.
501                            return Some(std::mem::replace(&mut self.curr_node, down.as_ptr()));
502                        }
503                    }
504                    // We're at the bottom of the skiplist
505                    (Some(right), None) => {
506                        // We're at the bottom row, and the item to our right >= `self.item`.
507                        // This is exactly the same as a linked list -- we don't want to continue further.
508                        if &right.as_ref().value >= self.item {
509                            self.finished = true;
510                            return Some(self.curr_node);
511                        } else {
512                            // The node to our right is _smaller_ than us, so continue forward.
513                            self.curr_node = right.as_ptr();
514                        }
515                    }
516                    // If we've upheld invariants correctly, there's always a right when iterating
517                    // Otherwise, some element was larger than NodeValue::PosInf.
518                    _ => unreachable!(),
519                }
520            }
521        }
522    }
523}
524
525pub struct IterRangeWith<'a, T, F>
526where
527    T: PartialOrd,
528    F: Fn(&'a T) -> RangeHint,
529{
530    inclusive_fn: F,
531    curr_node: &'a Node<T>,
532    at_bottom: bool,
533}
534
535impl<'a, T, F> IterRangeWith<'a, T, F>
536where
537    T: PartialOrd,
538    F: Fn(&T) -> RangeHint,
539{
540    #[inline]
541    pub(crate) fn new(curr_node: &'a Node<T>, inclusive_fn: F) -> Self {
542        Self {
543            inclusive_fn,
544            curr_node,
545            at_bottom: false,
546        }
547    }
548
549    // Is `item` smaller than our range?
550    #[inline]
551    fn item_smaller_than_range(&self, item: &NodeValue<T>) -> bool {
552        match item {
553            NodeValue::NegInf => true,
554            NodeValue::PosInf => false,
555            NodeValue::Value(v) => {
556                if let RangeHint::SmallerThanRange = (self.inclusive_fn)(v) {
557                    true
558                } else {
559                    false
560                }
561            }
562        }
563    }
564
565    // Is `item` in our range?
566    #[inline]
567    fn item_in_range(&self, item: &NodeValue<T>) -> bool {
568        match item {
569            NodeValue::NegInf => false,
570            NodeValue::PosInf => false,
571            NodeValue::Value(v) => {
572                if let RangeHint::InRange = (self.inclusive_fn)(v) {
573                    true
574                } else {
575                    false
576                }
577            }
578        }
579    }
580}
581
582impl<'a, T, F> Iterator for IterRangeWith<'a, T, F>
583where
584    T: PartialOrd,
585    F: Fn(&T) -> RangeHint,
586{
587    type Item = &'a T;
588    #[inline]
589    fn next(&mut self) -> Option<Self::Item> {
590        // Step 1: Find the *largest* element smaller than our range.
591        // This process is _very_ similar to LeftBiasIter, where
592        // we search for the element immediately left of the desired one.
593        while !self.at_bottom {
594            match (self.curr_node.right, self.curr_node.down) {
595                // We're in the middle of the skiplist somewhere
596                (Some(right), Some(down)) => unsafe {
597                    // The item to our right is _smaller_ than our range,
598                    // so we get to skip right.
599                    if self.item_smaller_than_range(&right.as_ref().value) {
600                        self.curr_node = right.as_ptr().as_ref().unwrap();
601                    } else {
602                        // The item is in our range, or larger, so we need to go down.
603                        self.curr_node = down.as_ptr().as_ref().unwrap();
604                    }
605                },
606                // We're at the bottom of the skiplist
607                (Some(right), None) => unsafe {
608                    // The item immediately to our right is _smaller_ than the range,
609                    // so advance right.
610                    if self.item_smaller_than_range(&right.as_ref().value) {
611                        self.curr_node = right.as_ptr().as_ref().unwrap();
612                    } else {
613                        // The element to our right is in the range, or larger!
614                        self.at_bottom = true;
615                        // We're exactly ONE step away from the first item in the range,
616                        // so advance one to the right
617                        self.curr_node = self.curr_node.right.unwrap().as_ptr().as_ref().unwrap();
618                        break;
619                    }
620                },
621                _ => unreachable!(),
622            }
623        }
624        // Verify that we are, indeed, at the bottom
625        debug_assert!(self.curr_node.down.is_none());
626        if self.item_in_range(&self.curr_node.value) {
627            unsafe {
628                let ret_val = &self.curr_node.value;
629                let next = self.curr_node.right.unwrap().as_ptr().as_ref().unwrap();
630                self.curr_node = next;
631                return Some(ret_val.get_value());
632            }
633        }
634        None
635    }
636}
637
638#[cfg(test)]
639mod tests {
640    use crate::RangeHint;
641    use crate::SkipList;
642
643    #[test]
644    fn test_iterall() {
645        let mut sk = SkipList::new();
646        let expected: Vec<usize> = (0..10).collect();
647        for e in &expected {
648            sk.insert(*e);
649        }
650        let foo: Vec<_> = sk.iter_all().cloned().collect();
651        for i in 0..expected.len() {
652            assert_eq!(expected[i], foo[i]);
653        }
654        let mut second = foo.clone();
655        second.sort();
656        assert_eq!(foo, second)
657    }
658
659    #[test]
660    fn test_empty() {
661        let sk = SkipList::<usize>::new();
662        let foo: Vec<_> = sk.iter_all().cloned().collect();
663        assert!(foo.is_empty());
664    }
665
666    // MIRI: This test takes forever.
667    #[test]
668    fn test_range() {
669        let mut sk = SkipList::new();
670        for i in 0..500 {
671            sk.insert(i);
672        }
673        let expected: Vec<usize> = (50..=100).collect();
674        let got: Vec<usize> = sk.range(&50, &100).cloned().collect();
675        assert_eq!(expected, got);
676    }
677
678    #[test]
679    fn test_range_empty() {
680        let sk = SkipList::new();
681        let expected: Vec<usize> = Vec::new();
682        let got: Vec<usize> = sk.range(&50, &100).cloned().collect();
683        assert_eq!(expected, got);
684    }
685
686    #[test]
687    fn test_range_outside() {
688        let mut sk = SkipList::new();
689        for i in 20..30 {
690            sk.insert(i);
691        }
692        let expected: Vec<usize> = Vec::new();
693        let less: Vec<usize> = sk.range(&0, &19).cloned().collect();
694        let more: Vec<usize> = sk.range(&30, &32).cloned().collect();
695        assert_eq!(expected, less);
696        assert_eq!(expected, more);
697    }
698
699    #[test]
700    fn test_inclusion_fn_range_with() {
701        use crate::iter::IterRangeWith;
702        use crate::{Node, NodeValue};
703        let n = Node {
704            right: None,
705            down: None,
706            value: NodeValue::Value(3),
707            width: 1,
708        };
709        let srw = IterRangeWith::new(&n, |&i| {
710            if i < 2 {
711                RangeHint::SmallerThanRange
712            } else if i > 4 {
713                RangeHint::LargerThanRange
714            } else {
715                RangeHint::InRange
716            }
717        });
718        assert!(srw.item_smaller_than_range(&NodeValue::Value(1)) == true);
719        assert!(srw.item_smaller_than_range(&NodeValue::Value(2)) == false);
720        assert!(srw.item_smaller_than_range(&NodeValue::Value(4)) == false);
721        assert!(srw.item_smaller_than_range(&NodeValue::Value(5)) == false);
722        assert!(srw.item_smaller_than_range(&NodeValue::NegInf) == true);
723        assert!(srw.item_smaller_than_range(&NodeValue::PosInf) == false);
724
725        assert!(srw.item_in_range(&NodeValue::Value(1)) == false);
726        assert!(srw.item_in_range(&NodeValue::Value(2)) == true);
727        assert!(srw.item_in_range(&NodeValue::Value(3)) == true);
728        assert!(srw.item_in_range(&NodeValue::Value(4)) == true);
729        assert!(srw.item_in_range(&NodeValue::Value(5)) == false);
730        assert!(srw.item_in_range(&NodeValue::PosInf) == false);
731        assert!(srw.item_in_range(&NodeValue::NegInf) == false);
732    }
733
734    #[test]
735    fn test_index_range() {
736        use std::ops::RangeBounds;
737        fn sk_range<R: RangeBounds<usize>>(range: R) -> Vec<usize> {
738            let sk = SkipList::from(0..20);
739            sk.index_range(range).cloned().collect()
740        }
741
742        fn vec_range<R: RangeBounds<usize>>(range: R) -> Vec<usize> {
743            let mut vec: Vec<_> = (0..20).collect();
744            vec.drain(range).collect()
745        }
746
747        fn test_against<R: RangeBounds<usize> + Clone + std::fmt::Debug>(range: R) {
748            assert_eq!(
749                sk_range(range.clone()),
750                vec_range(range.clone()),
751                "\nRange that caused the failure: {:?}",
752                range
753            );
754        }
755
756        test_against(..);
757        test_against(4..10);
758        test_against(0..20);
759        test_against(20..20);
760        test_against(..20);
761        test_against(10..);
762        test_against(20..);
763        test_against(1..1);
764        test_against(1..=1);
765        test_against(3..=8);
766        test_against(..=8);
767    }
768
769    #[test]
770    fn test_range_with() {
771        use crate::iter::RangeHint;
772        let mut sk = SkipList::<usize>::new();
773        let expected = &[0, 1, 2, 3, 4, 5];
774        for e in expected {
775            sk.insert(*e);
776        }
777        let f: Vec<_> = sk
778            .range_with(|&i| {
779                if i < 2 {
780                    RangeHint::SmallerThanRange
781                } else if i > 4 {
782                    RangeHint::LargerThanRange
783                } else {
784                    RangeHint::InRange
785                }
786            })
787            .cloned()
788            .collect();
789        assert_eq!(f, vec![2, 3, 4]);
790    }
791
792    #[test]
793    fn test_range_with_empty() {
794        use crate::iter::RangeHint;
795        let sk = SkipList::<usize>::new();
796        let f: Vec<_> = sk
797            .range_with(|&i| {
798                if i < 2 {
799                    RangeHint::SmallerThanRange
800                } else if i > 4 {
801                    RangeHint::LargerThanRange
802                } else {
803                    RangeHint::InRange
804                }
805            })
806            .cloned()
807            .collect();
808        let expected: Vec<usize> = vec![];
809        assert_eq!(f, expected);
810    }
811
812    #[test]
813    fn test_range_with_all() {
814        use crate::iter::RangeHint;
815        let mut sk = SkipList::<usize>::new();
816        let expected = &[0, 1, 2, 3, 4, 5];
817        for e in expected {
818            sk.insert(*e);
819        }
820        let f: Vec<_> = sk.range_with(|&_i| RangeHint::InRange).cloned().collect();
821        assert_eq!(f, expected.to_vec());
822    }
823
824    #[test]
825    fn test_range_with_none() {
826        use crate::iter::RangeHint;
827        let mut sk = SkipList::<usize>::new();
828        let expected = &[0, 1, 2, 3, 4, 5];
829        for e in expected {
830            sk.insert(*e);
831        }
832        let f: Vec<_> = sk
833            .range_with(|&_i| RangeHint::SmallerThanRange)
834            .cloned()
835            .collect();
836        // compiler bug? Should not need to specify type
837        let expected: Vec<usize> = Vec::new();
838        assert_eq!(f, expected);
839        let f: Vec<_> = sk
840            .range_with(|&_i| RangeHint::LargerThanRange)
841            .cloned()
842            .collect();
843        assert_eq!(f, expected);
844    }
845
846    // You should run this test with miri
847    #[test]
848    fn test_range_pathological_no_panic() {
849        use crate::RangeHint;
850        use rand;
851        use rand::prelude::*;
852        let mut sk = SkipList::<usize>::new();
853        let expected = &[0, 1, 2, 3, 4, 5];
854        for e in expected {
855            sk.insert(*e);
856        }
857        let _f: Vec<_> = sk
858            .range_with(|&_i| {
859                let mut thrng = rand::thread_rng();
860                let r: f32 = thrng.gen();
861                if 0.0 < r && r < 0.33 {
862                    RangeHint::SmallerThanRange
863                } else if r < 0.66 {
864                    RangeHint::InRange
865                } else {
866                    RangeHint::LargerThanRange
867                }
868            })
869            .cloned()
870            .collect();
871    }
872}
convenient_skiplist/iter.rs

convenient_skiplist/
iter.rs
