src/librustc_data_structures/sorted_map/tests.rs

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