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