sorted_list/
lib.rs

1#![deny(missing_docs)]
2#![deny(missing_debug_implementations)]
3#![deny(unused_imports)]
4
5#![cfg_attr(feature = "nightly", feature(collections_range))]
6
7//! Simple sorted list collection like the one found in the .NET collections library.
8
9use std::fmt;
10
11#[cfg(feature = "nightly")]
12use std::collections::Bound::*;
13
14#[cfg(feature = "nightly")]
15use std::collections::range::RangeArgument;
16
17/// `SortedList` stores multiple `(K, V)` tuples ordered by K, then in the order of insertion for `V`.
18/// Implmented using two `Vec` this should be fast for in-order inserts and quite bad in the
19/// worst-case of reverse insertion order.
20///
21/// # Example
22///
23/// ```
24/// use sorted_list::SortedList;
25///
26/// let mut list: SortedList<u32, u8> = SortedList::new();
27/// list.insert(0, 0);
28/// list.insert(1, 1);
29/// list.insert(0, 2);
30///
31/// assert_eq!(
32///     list.iter().collect::<Vec<_>>(),
33///     vec![(&0, &0), (&0, &2), (&1, &1)]);
34/// ```
35pub struct SortedList<K: Ord, V: PartialEq> {
36    keys: Vec<K>,
37    values: Vec<V>,
38}
39
40impl<K: Ord, V: PartialEq> SortedList<K, V> {
41    /// Creates a new as small as possible `SortedList`
42    pub fn new() -> Self {
43        SortedList { keys: Vec::new(), values: Vec::new() }
44    }
45
46    /// Returns the number of tuples
47    pub fn len(&self) -> usize {
48        self.keys.len()
49    }
50
51    /// Returns `true` if the `(key, value)` did not exist in the sorted list before and it exists now,
52    /// `false` otherwise.
53    pub fn insert(&mut self, key: K, value: V) -> bool {
54        match self.keys.binary_search(&key) {
55            Ok(found_at) => {
56                let insertion_position = self.find_insertion_positition(found_at, &key, &value);
57
58                if let Some(insertion_position) = insertion_position {
59                    insertion_position.insert(key, value, &mut self.keys, &mut self.values);
60                    true
61                } else {
62                    false
63                }
64            },
65            Err(insert_at) => {
66                self.keys.insert(insert_at, key);
67                self.values.insert(insert_at, value);
68
69                true
70            }
71        }
72    }
73
74    /// Returns the values of a specific key as a slice
75    pub fn values_of(& self, key: &K) -> &[V] {
76        let first = self.find_first_position(key).ok();
77        match first {
78            Some(first) => {
79                let last = self.find_last_position(key).unwrap();
80                &self.values[first..last]
81            },
82            None => {
83                &self.values[0..0]
84            }
85        }
86    }
87
88    fn find_insertion_positition(&self, from: usize, key: &K, value: &V) -> Option<InsertionPosition> {
89        let mut keys = self.keys.iter().skip(from);
90        let mut values = self.values.iter().skip(from);
91
92        let mut index: usize = from;
93
94        loop {
95            index += 1;
96
97            match (keys.next(), values.next()) {
98                (Some(other_key), Some(other_value)) => {
99                    if key == other_key {
100                        if value == other_value {
101                            // found it already
102                            return None;
103                        }
104                    } else {
105                        // we ran past the matching keys, insert before
106                        return Some(InsertionPosition::Before(index));
107                    }
108                },
109                (None, None) => {
110                    return Some(InsertionPosition::Last);
111                }
112                (_, _) => unreachable!(),
113            };
114        }
115    }
116
117    /// Iterate all stored tuples, keys in order, values in insertion order
118    pub fn iter(&self) -> Tuples<K, V> {
119        Tuples {
120            keys: &self.keys,
121            values: &self.values,
122            low: 0,
123            high: self.len(),
124        }
125    }
126
127    /// Iterate over all keys, can contain duplicates
128    pub fn keys(&self) -> ::std::slice::Iter<K> {
129        self.keys.iter()
130    }
131
132    /// Iterate over all values
133    pub fn values(&self) -> ::std::slice::Iter<V> {
134        self.values.iter()
135    }
136
137    /// Returns the first (in insertion order) value of `key`
138    pub fn first_value_of(&self, key: &K) -> Option<&V> {
139        self.find_first_position(key).ok().map(|idx| &self.values[idx])
140    }
141
142    /// Returns the last (in insertion order) value of `key`
143    pub fn last_value_of(&self, key: &K) -> Option<&V> {
144        self.find_last_position(key).ok().map(|idx| &self.values[idx - 1])
145    }
146
147    fn find_first_position(&self, key: &K) -> Result<usize, usize> {
148        match self.keys.binary_search(key) {
149            Ok(mut pos) => {
150                while pos > 0 && key == &self.keys[pos] { pos -= 1; }
151
152                if pos == 0 {
153                    if key == &self.keys[0] {
154                        Ok(0)
155                    } else {
156                        Ok(1)
157                    }
158                } else {
159                    Ok(pos + 1)
160                }
161            },
162            Err(pos) => Err(pos),
163        }
164    }
165
166    fn find_last_position(&self, key: &K) -> Result<usize, usize> {
167        match self.keys.binary_search(key) {
168            Ok(mut pos) => {
169                while pos < self.keys.len() && key == &self.keys[pos] { pos += 1; }
170
171                if pos == self.keys.len() {
172                    // this is off by one ...
173                    Ok(pos)
174                } else {
175                    Ok(pos)
176                }
177            },
178            Err(pos) => Err(pos),
179        }
180    }
181}
182
183impl<K: Ord + Clone, V: PartialEq + Clone> Clone for SortedList<K, V> {
184    fn clone(&self) -> Self {
185        SortedList {
186            keys: self.keys.clone(),
187            values: self.values.clone(),
188        }
189    }
190}
191
192trait ResultExt<A> {
193    fn either(self) -> A;
194}
195
196impl<A> ResultExt<A> for Result<A, A> {
197    fn either(self) -> A {
198        match self {
199            Ok(x) => x,
200            Err(x) => x,
201        }
202    }
203}
204
205#[cfg(feature = "nightly")]
206impl<K: Ord + PartialEq, V: PartialEq> SortedList<K, V> {
207    /// Returns an iterator over the specified range of tuples
208    pub fn range<R>(&self, range: R) -> Tuples<K, V> where R: RangeArgument<K>, {
209        let start = match range.start() {
210            Included(key) => self.find_first_position(key).either().into(),
211            Excluded(key) => self.find_last_position(key).either().into(),
212            Unbounded => Some(0)
213        };
214
215        let end = match range.end() {
216            Included(key) => self.find_last_position(key).either(),
217            Excluded(key) => self.find_first_position(key).either(),
218            Unbounded => self.len(),
219        };
220
221        let skip = start.unwrap_or(self.keys.len());
222        let take = if end <= skip { 0 } else { end };
223
224        Tuples { keys: &self.keys, values: &self.values, low: skip, high: take }
225    }
226}
227
228impl<K: Ord, V: PartialEq> IntoIterator for SortedList<K, V> {
229    type Item = (K, V);
230    type IntoIter = IntoTuples<K, V>;
231
232    fn into_iter(self) -> Self::IntoIter {
233        IntoTuples {
234            keys: self.keys.into_iter(),
235            values: self.values.into_iter(),
236        }
237    }
238}
239
240/// IntoIterator version of `Tuples`
241pub struct IntoTuples<K, V> {
242    keys: ::std::vec::IntoIter<K>,
243    values: ::std::vec::IntoIter<V>,
244}
245
246impl<K, V> fmt::Debug for IntoTuples<K, V> {
247    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
248        write!(fmt, "IntoTuples {{ remaining: {} }}", self.keys.size_hint().0)
249    }
250}
251
252impl<K, V> Iterator for IntoTuples<K, V> {
253    type Item = (K, V);
254
255    fn next(&mut self) -> Option<Self::Item> {
256        match (self.keys.next(), self.values.next()) {
257            (Some(k), Some(v)) => (k, v).into(),
258            (None, None) => None,
259            _ => unreachable!()
260        }
261    }
262
263    fn size_hint(&self) -> (usize, Option<usize>) {
264        self.keys.size_hint()
265    }
266}
267
268impl<K, V> DoubleEndedIterator for IntoTuples<K, V> {
269    fn next_back(&mut self) -> Option<(K, V)> {
270        match (self.keys.next_back(), self.values.next_back()) {
271            (Some(k), Some(v)) => (k, v).into(),
272            (None, None) => None,
273            _ => unreachable!()
274        }
275    }
276}
277
278impl<K, V> ExactSizeIterator for IntoTuples<K, V> {}
279
280impl<K: Clone + Ord, V: PartialEq> Extend<(K, V)> for SortedList<K, V> {
281    fn extend<T>(&mut self, iter: T) where T: IntoIterator<Item = (K, V)> {
282        let mut temp = iter.into_iter().collect::<Vec<_>>();
283        temp.sort_by_key(|&(ref k, _)| k.clone());
284
285        for (k, v) in temp {
286            self.insert(k, v);
287        }
288    }
289}
290
291impl<K: Ord + fmt::Debug, V: PartialEq + fmt::Debug> fmt::Debug for SortedList<K, V> {
292    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
293        write!(fmt, "SortedList {{ {:?} }}", &self.iter())
294    }
295}
296
297/// Helper value for knowning where to insert the value
298enum InsertionPosition {
299    Before(usize),
300    Last
301}
302
303impl InsertionPosition {
304    fn insert<K, V>(self, key: K, value: V, keys: &mut Vec<K>, values: &mut Vec<V>) {
305        match self {
306            InsertionPosition::Before(index) => {
307                keys.insert(index - 1, key);
308                values.insert(index - 1, value);
309
310                assert_eq!(keys.len(), values.len());
311            },
312            InsertionPosition::Last => {
313                keys.push(key);
314                values.push(value);
315
316                assert_eq!(keys.len(), values.len());
317            }
318        }
319    }
320}
321
322/// Iterator over tuples stored in `SortedList`
323pub struct Tuples<'a, K: 'a, V: 'a> {
324    keys: &'a Vec<K>,
325    values: &'a Vec<V>,
326    low: usize,
327    high: usize,
328}
329
330impl<'a, K, V> Iterator for Tuples<'a, K, V> {
331    type Item = (&'a K, &'a V);
332
333    fn next(&mut self) -> Option<Self::Item> {
334        if self.low < self.high {
335            let low = self.low;
336            self.low += 1;
337            Some((&self.keys[low], &self.values[low]))
338        } else {
339            None
340        }
341    }
342
343    fn size_hint(&self) -> (usize, Option<usize>) {
344        let len = self.high - self.low;
345        (len, Some(len))
346    }
347}
348
349impl<'a, K, V> DoubleEndedIterator for Tuples<'a, K, V> {
350    fn next_back(&mut self) -> Option<Self::Item> {
351        if self.high > self.low {
352            self.high -= 1;
353            let high = self.high;
354            Some((&self.keys[high], &self.values[high]))
355        } else {
356            None
357        }
358    }
359}
360
361impl<'a, K, V> Clone for Tuples<'a, K, V> {
362    fn clone(&self) -> Self {
363        Tuples {
364            keys: self.keys.clone(),
365            values: self.values.clone(),
366            low: self.low,
367            high: self.high,
368        }
369    }
370}
371
372impl<'a, K: Ord + fmt::Debug, V: PartialEq + fmt::Debug> fmt::Debug for Tuples<'a, K, V> {
373    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
374        let remaining = self.size_hint().0;
375        let mut clone = self.clone();
376        let mut idx = 0;
377        write!(fmt, "[")?;
378        while let Some(tuple) = clone.next() {
379            if idx == remaining - 1 {
380                write!(fmt, "{:?}", tuple)?;
381            } else {
382                write!(fmt, "{:?}, ", tuple)?;
383            }
384            idx += 1;
385        }
386        write!(fmt, "]")
387    }
388}
389
390impl<'a, K, V> ExactSizeIterator for Tuples<'a, K, V> {}
391
392#[cfg(test)]
393mod tests {
394    use std::fmt::Debug;
395    use super::SortedList;
396
397    /// Extension trait with asserting methods
398    trait SortedListExt<K, V> {
399        fn insert_only_new(&mut self, key: K, value: V);
400    }
401
402    impl<K: Debug + Clone + Ord, V: Debug + Clone + PartialEq> SortedListExt<K, V> for SortedList<K, V> {
403        fn insert_only_new(&mut self, key: K, value: V) {
404            let cloned_key = key.clone();
405            let cloned_value = value.clone();
406
407            assert!(self.insert(key, value), "pair existed already: ({:?}, {:?})", cloned_key, cloned_value);
408        }
409    }
410
411    #[test]
412    fn insert_in_order_and_iterate() {
413        let mut list = SortedList::new();
414        list.insert_only_new(0u32, 0u8);
415        list.insert_only_new(1u32, 4u8);
416
417        let mut iter = list.iter();
418
419        assert_eq!(iter.next(), Some((&0, &0)));
420        assert_eq!(iter.next(), Some((&1, &4)));
421        assert_eq!(iter.next(), None);
422    }
423
424    #[test]
425    fn insert_out_of_order_and_iterate() {
426        let mut list = SortedList::new();
427        list.insert_only_new(1u32, 4u8);
428        list.insert_only_new(0u32, 0u8);
429
430        let mut iter = list.iter();
431
432        assert_eq!(iter.next(), Some((&0, &0)));
433        assert_eq!(iter.next(), Some((&1, &4)));
434        assert_eq!(iter.next(), None);
435    }
436
437    #[test]
438    fn insert_duplicate() {
439        let mut list = SortedList::new();
440        assert!(list.insert(1u32, 4u8));
441        assert!(!list.insert(1u32, 4u8));
442    }
443
444    #[test]
445    fn insert_multiple_in_order() {
446        let mut list = SortedList::new();
447        list.insert_only_new(0u32, 0u8);
448        list.insert_only_new(0u32, 1u8);
449        list.insert_only_new(0u32, 2u8);
450        list.insert_only_new(0u32, 3u8);
451
452        let mut iter = list.iter();
453        assert_eq!(iter.next(), Some((&0, &0)));
454        assert_eq!(iter.next(), Some((&0, &1)));
455        assert_eq!(iter.next(), Some((&0, &2)));
456        assert_eq!(iter.next(), Some((&0, &3)));
457        assert_eq!(iter.next(), None);
458    }
459
460    #[test]
461    fn multiple_values_are_iterated_in_insertion_order() {
462        let mut list = SortedList::new();
463        list.insert_only_new(0u32, 3u8);
464        list.insert_only_new(0u32, 2u8);
465        list.insert_only_new(0u32, 1u8);
466        list.insert_only_new(0u32, 0u8);
467
468        let mut iter = list.iter();
469        assert_eq!(iter.next(), Some((&0, &3)));
470        assert_eq!(iter.next(), Some((&0, &2)));
471        assert_eq!(iter.next(), Some((&0, &1)));
472        assert_eq!(iter.next(), Some((&0, &0)));
473        assert_eq!(iter.next(), None);
474    }
475
476    #[test]
477    fn iterate_over_mixed_in_order() {
478        let mut list = SortedList::new();
479        list.insert_only_new(0u32, 0u8);
480        list.insert_only_new(0u32, 1u8);
481        list.insert_only_new(0u32, 2u8);
482        list.insert_only_new(0u32, 3u8);
483        list.insert_only_new(1u32, 4u8);
484        list.insert_only_new(2u32, 5u8);
485        list.insert_only_new(2u32, 6u8);
486        list.insert_only_new(3u32, 7u8);
487
488        let mut iter = list.iter();
489        assert_eq!(iter.next(), Some((&0, &0)));
490        assert_eq!(iter.next(), Some((&0, &1)));
491        assert_eq!(iter.next(), Some((&0, &2)));
492        assert_eq!(iter.next(), Some((&0, &3)));
493        assert_eq!(iter.next(), Some((&1, &4)));
494        assert_eq!(iter.next(), Some((&2, &5)));
495        assert_eq!(iter.next(), Some((&2, &6)));
496        assert_eq!(iter.next(), Some((&3, &7)));
497        assert_eq!(iter.next(), None);
498    }
499
500    #[test]
501    fn iterate_over_mixed_out_of_order() {
502        let mut list = SortedList::new();
503        list.insert_only_new(3u32, 7u8);
504        list.insert_only_new(0u32, 0u8);
505        list.insert_only_new(1u32, 4u8);
506        list.insert_only_new(0u32, 1u8);
507
508        println!("{:?}", list);
509
510        let mut iter = list.iter();
511        assert_eq!(iter.next(), Some((&0, &0)));
512        assert_eq!(iter.next(), Some((&0, &1)));
513        assert_eq!(iter.next(), Some((&1, &4)));
514        assert_eq!(iter.next(), Some((&3, &7)));
515        assert_eq!(iter.next(), None);
516    }
517
518    #[test]
519    fn empty_values_of() {
520        let list: SortedList<u32, u8> = SortedList::new();
521        assert_eq!(list.values_of(&0).iter().next(), None);
522    }
523
524    #[test]
525    fn iterate_values_of() {
526        let mut list = SortedList::new();
527        list.insert_only_new(1u32, 4u8);
528        list.insert_only_new(0u32, 0u8);
529        list.insert_only_new(0u32, 1u8);
530        list.insert_only_new(2u32, 5u8);
531        list.insert_only_new(0u32, 2u8);
532        list.insert_only_new(3u32, 7u8);
533        list.insert_only_new(0u32, 3u8);
534        list.insert_only_new(2u32, 6u8);
535
536        let mut values_of = list.values_of(&0).iter();
537        assert_eq!(values_of.next(), Some(&0));
538        assert_eq!(values_of.next(), Some(&1));
539        assert_eq!(values_of.next(), Some(&2));
540        assert_eq!(values_of.next(), Some(&3));
541        assert_eq!(values_of.next(), None);
542
543        let mut values_of = list.values_of(&1).iter();
544        assert_eq!(values_of.next(), Some(&4));
545        assert_eq!(values_of.next(), None);
546
547        let mut values_of = list.values_of(&2).iter();
548        assert_eq!(values_of.next(), Some(&5));
549        assert_eq!(values_of.next(), Some(&6));
550        assert_eq!(values_of.next(), None);
551
552        let mut values_of = list.values_of(&3).iter();
553        assert_eq!(values_of.next(), Some(&7));
554        assert_eq!(values_of.next(), None);
555    }
556
557    #[test]
558    fn extend_worst_case() {
559        use std::time::Instant;
560
561        /// 1000, 100 => 4.08s (3.76s release) originally
562        /// 1000, 100 for copy types: 0.66s (0.23s release)
563        let max_key = 1000;
564        let max_val = 100;
565        let mut input = Vec::with_capacity(max_key * max_val);
566        for key in 0..max_key {
567            for val in 0..max_val {
568                input.push((max_key - key, val));
569            }
570        }
571
572        let began = Instant::now();
573
574        let mut slist = SortedList::new();
575        slist.extend(input);
576
577        let elapsed = began.elapsed();
578        println!("elapsed: {}.{:09}s", elapsed.as_secs(), elapsed.subsec_nanos());
579    }
580
581    fn to_vec<'a, A: 'a + Copy, B: 'a + Copy, I: Iterator<Item=(&'a A, &'a B)>>(it: I) -> Vec<(A, B)> {
582        it.map(|(a, b)| (*a, *b)).collect()
583    }
584
585    #[cfg(feature = "nightly")]
586    #[test]
587    fn range() {
588        use std::collections::Bound::*;
589
590        let mut list: SortedList<u32, u8> = SortedList::new();
591        list.insert_only_new(1, 4);
592        list.insert_only_new(0, 0);
593        list.insert_only_new(0, 1);
594        list.insert_only_new(2, 5);
595        list.insert_only_new(0, 2);
596        list.insert_only_new(3, 7);
597        list.insert_only_new(0, 3);
598        list.insert_only_new(2, 6);
599        list.insert_only_new(4, 8);
600        list.insert_only_new(6, 9);
601        list.insert_only_new(6, 10);
602        list.insert_only_new(9, 11);
603
604        assert_eq!(
605            to_vec(list.range((Unbounded, Included(2)))),
606            vec![(0, 0), (0, 1), (0, 2), (0, 3), (1, 4), (2, 5), (2, 6)]);
607
608        assert_eq!(
609            to_vec(list.range((Unbounded, Excluded(2)))),
610            vec![(0, 0), (0, 1), (0, 2), (0, 3), (1, 4)]);
611
612        assert_eq!(
613            to_vec(list.range((Included(0), Excluded(2)))),
614            vec![(0, 0), (0, 1), (0, 2), (0, 3), (1, 4)]);
615
616        assert_eq!(
617            to_vec(list.range((Included(1), Excluded(2)))),
618            vec![(1, 4)]);
619
620        assert_eq!(
621            to_vec(list.range((Included(2), Excluded(2)))),
622            vec![]);
623
624        assert_eq!(
625            to_vec(list.range((Included(2), Included(2)))),
626            vec![(2, 5), (2, 6)]);
627
628        assert_eq!(
629            to_vec(list.range((Included(2), Excluded(3)))),
630            vec![(2, 5), (2, 6)]);
631
632        assert_eq!(
633            to_vec(list.range((Included(2), Included(3)))),
634            vec![(2, 5), (2, 6), (3, 7)]);
635
636        assert_eq!(
637            to_vec(list.range((Included(2), Unbounded))),
638            vec![(2, 5), (2, 6), (3, 7), (4, 8), (6, 9), (6, 10), (9, 11)]);
639
640        assert_eq!(
641            to_vec(list.range((Excluded(1), Unbounded))),
642            vec![(2, 5), (2, 6), (3, 7), (4, 8), (6, 9), (6, 10), (9, 11)]);
643
644        assert_eq!(
645            to_vec(list.range((Excluded(0), Unbounded))),
646            vec![(1, 4), (2, 5), (2, 6), (3, 7), (4, 8), (6, 9), (6, 10), (9, 11)]);
647
648        assert_eq!(
649            to_vec(list.range((Excluded(4), Unbounded))),
650            vec![(6, 9), (6, 10), (9, 11)]);
651
652        assert_eq!(
653            to_vec(list.range((Included(5), Unbounded))),
654            vec![(6, 9), (6, 10), (9, 11)]);
655
656        assert_eq!(
657            to_vec(list.range((Excluded(5), Unbounded))),
658            vec![(6, 9), (6, 10), (9, 11)]);
659
660        assert_eq!(
661            to_vec(list.range((Excluded(6), Unbounded))),
662            vec![(9, 11)]);
663
664        assert_eq!(
665            to_vec(list.range((Excluded(6), Excluded(7)))),
666            vec![]);
667
668        assert_eq!(
669            to_vec(list.range((Excluded(6), Included(8)))),
670            vec![]);
671
672        assert_eq!(
673            to_vec(list.range((Excluded(6), Excluded(9)))),
674            vec![]);
675
676        assert_eq!(
677            to_vec(list.range((Excluded(6), Included(9)))),
678            vec![(9, 11)]);
679
680        assert_eq!(
681            to_vec(list.range((Excluded(7), Included(9)))),
682            vec![(9, 11)]);
683
684        assert_eq!(
685            to_vec(list.range((Included(7), Included(9)))),
686            vec![(9, 11)]);
687
688        assert_eq!(
689            to_vec(list.range((Excluded(8), Included(9)))),
690            vec![(9, 11)]);
691
692        assert_eq!(
693            to_vec(list.range((Included(8), Included(9)))),
694            vec![(9, 11)]);
695
696        assert_eq!(
697            to_vec(list.range(..)),
698            to_vec(list.iter()));
699    }
700
701    #[test]
702    fn first_value_of() {
703        let mut list: SortedList<u32, u8> = SortedList::new();
704        list.insert_only_new(1, 3);
705        list.insert_only_new(0, 0);
706        list.insert_only_new(0, 1);
707        list.insert_only_new(2, 4);
708        list.insert_only_new(0, 2);
709        list.insert_only_new(3, 6);
710        list.insert_only_new(2, 5);
711
712        assert_eq!(list.first_value_of(&0), Some(&0));
713        assert_eq!(list.first_value_of(&1), Some(&3));
714        assert_eq!(list.first_value_of(&2), Some(&4));
715        assert_eq!(list.first_value_of(&3), Some(&6));
716    }
717
718    #[test]
719    fn last_value_of() {
720        let mut list: SortedList<u32, u8> = SortedList::new();
721        list.insert_only_new(1, 3);
722        list.insert_only_new(0, 0);
723        list.insert_only_new(0, 1);
724        list.insert_only_new(2, 4);
725        list.insert_only_new(0, 2);
726        list.insert_only_new(3, 6);
727        list.insert_only_new(2, 5);
728
729        assert_eq!(list.last_value_of(&0), Some(&2));
730        assert_eq!(list.last_value_of(&1), Some(&3));
731        assert_eq!(list.last_value_of(&2), Some(&5));
732        assert_eq!(list.last_value_of(&3), Some(&6));
733    }
734
735    #[test]
736    fn double_ended_iter_empty() {
737        let list: SortedList<u32, u8> = SortedList::new();
738        assert_eq!(list.iter().next_back(), None);
739    }
740
741    #[test]
742    fn double_ended_iter_single() {
743        let mut list: SortedList<u32, u8> = SortedList::new();
744
745        list.insert_only_new(1, 3);
746
747        let mut iter = list.iter();
748        assert_eq!(iter.next_back(), Some((&1, &3)));
749        assert_eq!(iter.next_back(), None);
750    }
751
752    #[test]
753    fn double_ended_iter_multiple() {
754        let mut list: SortedList<u32, u8> = SortedList::new();
755
756        list.insert_only_new(1, 3);
757        list.insert_only_new(0, 0);
758        list.insert_only_new(0, 1);
759        list.insert_only_new(2, 4);
760        list.insert_only_new(0, 2);
761        list.insert_only_new(3, 6);
762        list.insert_only_new(2, 5);
763
764        assert_eq!(
765            to_vec(list.iter().rev()),
766            vec![(3, 6), (2, 5), (2, 4), (1, 3), (0, 2), (0, 1), (0, 0)]);
767    }
768
769    #[test]
770    fn double_ended_iter_zig_zag() {
771        let mut list: SortedList<u32, u8> = SortedList::new();
772
773        list.insert_only_new(1, 3);
774        list.insert_only_new(0, 0);
775        list.insert_only_new(0, 1);
776        list.insert_only_new(2, 4);
777        list.insert_only_new(0, 2);
778        list.insert_only_new(3, 6);
779        list.insert_only_new(2, 5);
780
781        let mut iter = list.iter();
782        assert_eq!(iter.next(), (&0, &0).into());
783        assert_eq!(iter.next_back(), (&3, &6).into());
784
785        assert_eq!(iter.next(), (&0, &1).into());
786        assert_eq!(iter.next_back(), (&2, &5).into());
787
788        assert_eq!(iter.next(), (&0, &2).into());
789        assert_eq!(iter.next_back(), (&2, &4).into());
790
791        assert_eq!(iter.next(), (&1, &3).into());
792        assert_eq!(iter.next_back(), None);
793        assert_eq!(iter.next(), None);
794    }
795
796    #[test]
797    fn double_ended_iter_zag_zig() {
798        let mut list: SortedList<u32, u8> = SortedList::new();
799
800        list.insert_only_new(1, 3);
801        list.insert_only_new(0, 0);
802        list.insert_only_new(0, 1);
803        list.insert_only_new(2, 4);
804        list.insert_only_new(0, 2);
805        list.insert_only_new(3, 6);
806        list.insert_only_new(2, 5);
807
808        let mut iter = list.iter();
809        assert_eq!(iter.next_back(), (&3, &6).into());
810        assert_eq!(iter.next(), (&0, &0).into());
811
812        assert_eq!(iter.next_back(), (&2, &5).into());
813        assert_eq!(iter.next(), (&0, &1).into());
814
815        assert_eq!(iter.next_back(), (&2, &4).into());
816        assert_eq!(iter.next(), (&0, &2).into());
817
818        assert_eq!(iter.next_back(), (&1, &3).into());
819        assert_eq!(iter.next(), None);
820        assert_eq!(iter.next(), None);
821    }
822
823    #[test]
824    fn into_iter() {
825        let mut list: SortedList<u32, u8> = SortedList::new();
826
827        list.insert_only_new(1, 3);
828        list.insert_only_new(0, 0);
829        list.insert_only_new(0, 1);
830        list.insert_only_new(2, 4);
831        list.insert_only_new(0, 2);
832        list.insert_only_new(3, 6);
833        list.insert_only_new(2, 5);
834
835        assert_eq!(
836            list.clone().into_iter().collect::<Vec<_>>(),
837            to_vec(list.iter()));
838    }
839}
sorted_list/lib.rs

sorted_list/
lib.rs
