compiler/rustc_data_structures/src/sorted_map/tests.rs

   1 use super::{SortedIndexMultiMap, SortedMap};
   2
   3 #[test]
   4 fn test_sorted_index_multi_map() {
   5     let entries: Vec<_> = vec![(2, 0), (1, 0), (2, 1), (3, 0), (2, 2)];
   6     let set: SortedIndexMultiMap<usize, _, _> = entries.iter().copied().collect();
   7
   8     // Insertion order is preserved.
   9     assert!(entries.iter().map(|(ref k, ref v)| (k, v)).eq(set.iter()));
  10
  11     // Indexing
  12     for (i, expect) in entries.iter().enumerate() {
  13         assert_eq!(set[i], expect.1);
  14     }
  15
  16     // `get_by_key` works.
  17     assert_eq!(set.get_by_key(&3).copied().collect::<Vec<_>>(), vec![0]);
  18     assert!(set.get_by_key(&4).next().is_none());
  19
  20     // `get_by_key` returns items in insertion order.
  21     let twos: Vec<_> = set.get_by_key_enumerated(&2).collect();
  22     let idxs: Vec<usize> = twos.iter().map(|(i, _)| *i).collect();
  23     let values: Vec<usize> = twos.iter().map(|(_, &v)| v).collect();
  24
  25     assert_eq!(idxs, vec![0, 2, 4]);
  26     assert_eq!(values, vec![0, 1, 2]);
  27 }
  28
  29 #[test]
  30 fn test_insert_and_iter() {
  31     let mut map = SortedMap::new();
  32     let mut expected = Vec::new();
  33
  34     for x in 0..100 {
  35         assert_eq!(map.iter().cloned().collect::<Vec<_>>(), expected);
  36
  37         let x = 1000 - x * 2;
  38         map.insert(x, x);
  39         expected.insert(0, (x, x));
  40     }
  41 }
  42
  43 #[test]
  44 fn test_get_and_index() {
  45     let mut map = SortedMap::new();
  46     let mut expected = Vec::new();
  47
  48     for x in 0..100 {
  49         let x = 1000 - x;
  50         if x & 1 == 0 {
  51             map.insert(x, x);
  52         }
  53         expected.push(x);
  54     }
  55
  56     for mut x in expected {
  57         if x & 1 == 0 {
  58             assert_eq!(map.get(&x), Some(&x));
  59             assert_eq!(map.get_mut(&x), Some(&mut x));
  60             assert_eq!(map[&x], x);
  61             assert_eq!(&mut map[&x], &mut x);
  62         } else {
  63             assert_eq!(map.get(&x), None);
  64             assert_eq!(map.get_mut(&x), None);
  65         }
  66     }
  67 }
  68
  69 #[test]
  70 fn test_range() {
  71     let mut map = SortedMap::new();
  72     map.insert(1, 1);
  73     map.insert(3, 3);
  74     map.insert(6, 6);
  75     map.insert(9, 9);
  76
  77     let keys = |s: &[(_, _)]| s.into_iter().map(|e| e.0).collect::<Vec<u32>>();
  78
  79     for start in 0..11 {
  80         for end in 0..11 {
  81             if end < start {
  82                 continue;
  83             }
  84
  85             let mut expected = vec![1, 3, 6, 9];
  86             expected.retain(|&x| x >= start && x < end);
  87
  88             assert_eq!(keys(map.range(start..end)), expected, "range = {}..{}", start, end);
  89         }
  90     }
  91 }
  92
  93 #[test]
  94 fn test_offset_keys() {
  95     let mut map = SortedMap::new();
  96     map.insert(1, 1);
  97     map.insert(3, 3);
  98     map.insert(6, 6);
  99
 100     map.offset_keys(|k| *k += 1);
 101
 102     let mut expected = SortedMap::new();
 103     expected.insert(2, 1);
 104     expected.insert(4, 3);
 105     expected.insert(7, 6);
 106
 107     assert_eq!(map, expected);
 108 }
 109
 110 fn keys(s: SortedMap<u32, u32>) -> Vec<u32> {
 111     s.into_iter().map(|(k, _)| k).collect::<Vec<u32>>()
 112 }
 113
 114 fn elements(s: SortedMap<u32, u32>) -> Vec<(u32, u32)> {
 115     s.into_iter().collect::<Vec<(u32, u32)>>()
 116 }
 117
 118 #[test]
 119 fn test_remove_range() {
 120     let mut map = SortedMap::new();
 121     map.insert(1, 1);
 122     map.insert(3, 3);
 123     map.insert(6, 6);
 124     map.insert(9, 9);
 125
 126     for start in 0..11 {
 127         for end in 0..11 {
 128             if end < start {
 129                 continue;
 130             }
 131
 132             let mut expected = vec![1, 3, 6, 9];
 133             expected.retain(|&x| x < start || x >= end);
 134
 135             let mut map = map.clone();
 136             map.remove_range(start..end);
 137
 138             assert_eq!(keys(map), expected, "range = {}..{}", start, end);
 139         }
 140     }
 141 }
 142
 143 #[test]
 144 fn test_remove() {
 145     let mut map = SortedMap::new();
 146     let mut expected = Vec::new();
 147
 148     for x in 0..10 {
 149         map.insert(x, x);
 150         expected.push((x, x));
 151     }
 152
 153     for x in 0..10 {
 154         let mut map = map.clone();
 155         let mut expected = expected.clone();
 156
 157         assert_eq!(map.remove(&x), Some(x));
 158         expected.remove(x as usize);
 159
 160         assert_eq!(map.iter().cloned().collect::<Vec<_>>(), expected);
 161     }
 162 }
 163
 164 #[test]
 165 fn test_insert_presorted_non_overlapping() {
 166     let mut map = SortedMap::new();
 167     map.insert(2, 0);
 168     map.insert(8, 0);
 169
 170     map.insert_presorted(vec![(3, 0), (7, 0)]);
 171
 172     let expected = vec![2, 3, 7, 8];
 173     assert_eq!(keys(map), expected);
 174 }
 175
 176 #[test]
 177 fn test_insert_presorted_first_elem_equal() {
 178     let mut map = SortedMap::new();
 179     map.insert(2, 2);
 180     map.insert(8, 8);
 181
 182     map.insert_presorted(vec![(2, 0), (7, 7)]);
 183
 184     let expected = vec![(2, 0), (7, 7), (8, 8)];
 185     assert_eq!(elements(map), expected);
 186 }
 187
 188 #[test]
 189 fn test_insert_presorted_last_elem_equal() {
 190     let mut map = SortedMap::new();
 191     map.insert(2, 2);
 192     map.insert(8, 8);
 193
 194     map.insert_presorted(vec![(3, 3), (8, 0)]);
 195
 196     let expected = vec![(2, 2), (3, 3), (8, 0)];
 197     assert_eq!(elements(map), expected);
 198 }
 199
 200 #[test]
 201 fn test_insert_presorted_shuffle() {
 202     let mut map = SortedMap::new();
 203     map.insert(2, 2);
 204     map.insert(7, 7);
 205
 206     map.insert_presorted(vec![(1, 1), (3, 3), (8, 8)]);
 207
 208     let expected = vec![(1, 1), (2, 2), (3, 3), (7, 7), (8, 8)];
 209     assert_eq!(elements(map), expected);
 210 }
 211
 212 #[test]
 213 fn test_insert_presorted_at_end() {
 214     let mut map = SortedMap::new();
 215     map.insert(1, 1);
 216     map.insert(2, 2);
 217
 218     map.insert_presorted(vec![(3, 3), (8, 8)]);
 219
 220     let expected = vec![(1, 1), (2, 2), (3, 3), (8, 8)];
 221     assert_eq!(elements(map), expected);
 222 }