1 extern crate generational_arena; 2 #[macro_use] 3 extern crate quickcheck; 4 5 use generational_arena::Arena; 6 use std::collections::BTreeSet; 7 use std::iter::FromIterator; 8 9 quickcheck! { 10 fn always_contains_inserted_elements(elems: Vec<usize>) -> bool { 11 let mut arena = Arena::new(); 12 let indices: Vec<_> = elems.into_iter().map(|e| arena.insert(e)).collect(); 13 indices.into_iter().all(|i| arena.contains(i)) 14 } 15 } 16 17 quickcheck! { 18 fn never_contains_deleted_elements(elems: Vec<usize>) -> bool { 19 let mut arena = Arena::new(); 20 let indices: Vec<_> = elems.into_iter().map(|e| arena.insert(e)).collect(); 21 for i in indices.iter().cloned() { 22 arena.remove(i).unwrap(); 23 } 24 indices.into_iter().all(|i| !arena.contains(i)) 25 } 26 } 27 28 quickcheck! { 29 fn insert_delete_insert(elems: Vec<usize>) -> bool { 30 let mut arena = Arena::new(); 31 32 let indices: Vec<_> = elems.iter().cloned().map(|e| arena.insert(e)).collect(); 33 for (i, idx) in indices.iter().cloned().enumerate() { 34 if arena.remove(idx).unwrap() != elems[i] { 35 return false; 36 } 37 } 38 39 let new_indices: Vec<_> = elems.iter().cloned().map(|e| arena.insert(e)).collect(); 40 new_indices.into_iter().enumerate().all(|(i, idx)| { 41 !arena.contains(indices[i]) && arena.remove(idx).unwrap() == elems[i] 42 }) 43 } 44 } 45 46 quickcheck! { 47 fn interp(ops: Vec<(bool, usize)>) -> () { 48 let mut arena = Arena::new(); 49 let mut live_indices = vec![]; 50 let mut dead_indices = vec![]; 51 52 for (delete, i) in ops { 53 if delete && !live_indices.is_empty() { 54 let i = i % live_indices.len(); 55 let (idx, expected) = live_indices.remove(i); 56 assert_eq!(arena.remove(idx).unwrap(), expected); 57 dead_indices.push(idx); 58 } else { 59 live_indices.push((arena.insert(i), i)); 60 } 61 62 // All live indices always have the expected value. 63 for (live, expected) in live_indices.iter().cloned() { 64 assert_eq!(*arena.get(live).unwrap(), expected); 65 } 66 67 // All dead indices are never contained in the arena. 68 for dead in dead_indices.iter().cloned() { 69 assert!(!arena.contains(dead)); 70 } 71 } 72 73 // All the remaining values are expected. 74 let remaining: Vec<_> = arena.into_iter().collect(); 75 assert_eq!(remaining.len(), live_indices.len()); 76 for rem in remaining { 77 let i = live_indices.iter().position(|&(_, v)| v == rem).unwrap(); 78 live_indices.remove(i); 79 } 80 } 81 } 82 83 quickcheck! { 84 fn iter(elems: BTreeSet<usize>) -> bool { 85 let arena = Arena::from_iter(elems.clone()); 86 arena.iter().all(|(idx, value)| { 87 elems.contains(value) && arena.get(idx) == Some(value) 88 }) 89 } 90 } 91 92 quickcheck! { 93 fn iter_mut(elems: BTreeSet<usize>) -> bool { 94 let mut arena = Arena::from_iter(elems.clone()); 95 for (_, value) in &mut arena { 96 *value += 1; 97 } 98 arena.iter().all(|(idx, value)| { 99 let orig_value = value - 1; 100 elems.contains(&orig_value) && arena.get(idx) == Some(value) 101 }) 102 } 103 } 104 105 quickcheck! { 106 fn unknown_gen_consistency(values: Vec<(usize, bool)>) -> bool { 107 let mut arena = Arena::new(); 108 109 let inserted_indices: Vec<_> = values.iter().map(|(e, _)| arena.insert(e)).collect(); 110 let unknown_gen_indices: Vec<_> = inserted_indices.iter().map(|idx| idx.into_raw_parts().0).collect(); 111 112 // remove a couple elements at random 113 for (i, arena_index) in inserted_indices.iter().enumerate() { 114 if let Some((_, true)) = values.get(i) { 115 arena.remove(*arena_index); 116 } 117 } 118 119 // check that the results from get_unknown_gen() match get() 120 let first_batch = unknown_gen_indices.iter().enumerate().all(|(i, unknown_gen_idx)| { 121 let shared_check = if let Some((_, idx)) = arena.get_unknown_gen(*unknown_gen_idx) { 122 arena.get(idx).is_some() && inserted_indices[i] == idx 123 } else { 124 true 125 }; 126 let mut_check = if let Some((_, idx)) = arena.get_unknown_gen_mut(*unknown_gen_idx) { 127 arena.get_mut(idx).is_some() && inserted_indices[i] == idx 128 } else { 129 true 130 }; 131 shared_check && mut_check 132 }); 133 if !first_batch { 134 // if the first batch didn't succeed, there is no reason to keep going with the test 135 return false 136 } 137 138 // check that the results from get() match get_unknown_check() 139 inserted_indices.iter().enumerate().all(|(i, idx)| { 140 let shared_check = if let Some(_) = arena.get(*idx) { 141 let internal_index = idx.into_raw_parts().0; 142 arena.get_unknown_gen(internal_index).is_some() && unknown_gen_indices[i] == internal_index 143 } else { 144 true 145 }; 146 let mut_check = if let Some(_) = arena.get_mut(*idx) { 147 let internal_index = idx.into_raw_parts().0; 148 arena.get_unknown_gen_mut(internal_index).is_some() && unknown_gen_indices[i] == internal_index 149 } else { 150 true 151 }; 152 shared_check && mut_check 153 }) 154 } 155 } 156 157 quickcheck! { 158 fn from_iter_into_iter(elems: BTreeSet<usize>) -> bool { 159 let arena = Arena::from_iter(elems.clone()); 160 arena.into_iter().collect::<BTreeSet<_>>() == elems 161 } 162 } 163 164 quickcheck! { 165 fn retain(elems: Vec<bool>) -> () { 166 let mut arena = Arena::new(); 167 let mut live_indices = vec![]; 168 let mut dead_indices = vec![]; 169 170 for elem in elems { 171 let idx = arena.insert(elem); 172 if elem { 173 live_indices.push(idx); 174 } else { 175 dead_indices.push(idx); 176 } 177 } 178 179 arena.retain(|_, &mut b| b); 180 181 for live in live_indices.iter().cloned() { 182 assert!(arena.contains(live)); 183 } 184 185 for dead in dead_indices.iter().cloned() { 186 assert!(!arena.contains(dead)); 187 } 188 189 arena.retain(|_, &mut b| !b); 190 191 for live in live_indices.iter().cloned() { 192 assert!(!arena.contains(live)); 193 } 194 } 195 } 196