1
2 extern crate ordermap;
3 extern crate itertools;
4 #[macro_use]
5 extern crate quickcheck;
6
7 extern crate fnv;
8
9 use ordermap::OrderMap;
10 use itertools::Itertools;
11
12 use quickcheck::Arbitrary;
13 use quickcheck::Gen;
14
15 use fnv::FnvHasher;
16 use std::hash::{BuildHasher, BuildHasherDefault};
17 type FnvBuilder = BuildHasherDefault<FnvHasher>;
18 type OrderMapFnv<K, V> = OrderMap<K, V, FnvBuilder>;
19
20 use std::collections::HashSet;
21 use std::collections::HashMap;
22 use std::iter::FromIterator;
23 use std::hash::Hash;
24 use std::fmt::Debug;
25 use std::ops::Deref;
26 use std::cmp::min;
27
28
29 use ordermap::Entry as OEntry;
30 use std::collections::hash_map::Entry as HEntry;
31
32
set<'a, T: 'a, I>(iter: I) -> HashSet<T> where I: IntoIterator<Item=&'a T>, T: Copy + Hash + Eq33 fn set<'a, T: 'a, I>(iter: I) -> HashSet<T>
34 where I: IntoIterator<Item=&'a T>,
35 T: Copy + Hash + Eq
36 {
37 iter.into_iter().cloned().collect()
38 }
39
ordermap<'a, T: 'a, I>(iter: I) -> OrderMap<T, ()> where I: IntoIterator<Item=&'a T>, T: Copy + Hash + Eq,40 fn ordermap<'a, T: 'a, I>(iter: I) -> OrderMap<T, ()>
41 where I: IntoIterator<Item=&'a T>,
42 T: Copy + Hash + Eq,
43 {
44 OrderMap::from_iter(iter.into_iter().cloned().map(|k| (k, ())))
45 }
46
47 quickcheck! {
48 fn contains(insert: Vec<u32>) -> bool {
49 let mut map = OrderMap::new();
50 for &key in &insert {
51 map.insert(key, ());
52 }
53 insert.iter().all(|&key| map.get(&key).is_some())
54 }
55
56 fn contains_not(insert: Vec<u8>, not: Vec<u8>) -> bool {
57 let mut map = OrderMap::new();
58 for &key in &insert {
59 map.insert(key, ());
60 }
61 let nots = &set(¬) - &set(&insert);
62 nots.iter().all(|&key| map.get(&key).is_none())
63 }
64
65 fn insert_remove(insert: Vec<u8>, remove: Vec<u8>) -> bool {
66 let mut map = OrderMap::new();
67 for &key in &insert {
68 map.insert(key, ());
69 }
70 for &key in &remove {
71 map.swap_remove(&key);
72 }
73 let elements = &set(&insert) - &set(&remove);
74 map.len() == elements.len() && map.iter().count() == elements.len() &&
75 elements.iter().all(|k| map.get(k).is_some())
76 }
77
78 fn insertion_order(insert: Vec<u32>) -> bool {
79 let mut map = OrderMap::new();
80 for &key in &insert {
81 map.insert(key, ());
82 }
83 itertools::assert_equal(insert.iter().unique(), map.keys());
84 true
85 }
86
87 fn pop(insert: Vec<u8>) -> bool {
88 let mut map = OrderMap::new();
89 for &key in &insert {
90 map.insert(key, ());
91 }
92 let mut pops = Vec::new();
93 while let Some((key, _v)) = map.pop() {
94 pops.push(key);
95 }
96 pops.reverse();
97
98 itertools::assert_equal(insert.iter().unique(), &pops);
99 true
100 }
101
102 fn with_cap(cap: usize) -> bool {
103 let map: OrderMap<u8, u8> = OrderMap::with_capacity(cap);
104 println!("wish: {}, got: {} (diff: {})", cap, map.capacity(), map.capacity() as isize - cap as isize);
105 map.capacity() >= cap
106 }
107
108 fn drain(insert: Vec<u8>) -> bool {
109 let mut map = OrderMap::new();
110 for &key in &insert {
111 map.insert(key, ());
112 }
113 let mut clone = map.clone();
114 let drained = clone.drain(..);
115 for (key, _) in drained {
116 map.remove(&key);
117 }
118 map.is_empty()
119 }
120 }
121
122 use Op::*;
123 #[derive(Copy, Clone, Debug)]
124 enum Op<K, V> {
125 Add(K, V),
126 Remove(K),
127 AddEntry(K, V),
128 RemoveEntry(K),
129 }
130
131 impl<K, V> Arbitrary for Op<K, V>
132 where K: Arbitrary,
133 V: Arbitrary,
134 {
arbitrary<G: Gen>(g: &mut G) -> Self135 fn arbitrary<G: Gen>(g: &mut G) -> Self {
136 match g.gen::<u32>() % 4 {
137 0 => Add(K::arbitrary(g), V::arbitrary(g)),
138 1 => AddEntry(K::arbitrary(g), V::arbitrary(g)),
139 2 => Remove(K::arbitrary(g)),
140 _ => RemoveEntry(K::arbitrary(g)),
141 }
142 }
143 }
144
do_ops<K, V, S>(ops: &[Op<K, V>], a: &mut OrderMap<K, V, S>, b: &mut HashMap<K, V>) where K: Hash + Eq + Clone, V: Clone, S: BuildHasher,145 fn do_ops<K, V, S>(ops: &[Op<K, V>], a: &mut OrderMap<K, V, S>, b: &mut HashMap<K, V>)
146 where K: Hash + Eq + Clone,
147 V: Clone,
148 S: BuildHasher,
149 {
150 for op in ops {
151 match *op {
152 Add(ref k, ref v) => {
153 a.insert(k.clone(), v.clone());
154 b.insert(k.clone(), v.clone());
155 }
156 AddEntry(ref k, ref v) => {
157 a.entry(k.clone()).or_insert(v.clone());
158 b.entry(k.clone()).or_insert(v.clone());
159 }
160 Remove(ref k) => {
161 a.swap_remove(k);
162 b.remove(k);
163 }
164 RemoveEntry(ref k) => {
165 match a.entry(k.clone()) {
166 OEntry::Occupied(ent) => { ent.remove_entry(); },
167 _ => { }
168 }
169 match b.entry(k.clone()) {
170 HEntry::Occupied(ent) => { ent.remove_entry(); },
171 _ => { }
172 }
173 }
174 }
175 //println!("{:?}", a);
176 }
177 }
178
assert_maps_equivalent<K, V>(a: &OrderMap<K, V>, b: &HashMap<K, V>) -> bool where K: Hash + Eq + Debug, V: Eq + Debug,179 fn assert_maps_equivalent<K, V>(a: &OrderMap<K, V>, b: &HashMap<K, V>) -> bool
180 where K: Hash + Eq + Debug,
181 V: Eq + Debug,
182 {
183 assert_eq!(a.len(), b.len());
184 assert_eq!(a.iter().next().is_some(), b.iter().next().is_some());
185 for key in a.keys() {
186 assert!(b.contains_key(key), "b does not contain {:?}", key);
187 }
188 for key in b.keys() {
189 assert!(a.get(key).is_some(), "a does not contain {:?}", key);
190 }
191 for key in a.keys() {
192 assert_eq!(a[key], b[key]);
193 }
194 true
195 }
196
197 quickcheck! {
198 fn operations_i8(ops: Large<Vec<Op<i8, i8>>>) -> bool {
199 let mut map = OrderMap::new();
200 let mut reference = HashMap::new();
201 do_ops(&ops, &mut map, &mut reference);
202 assert_maps_equivalent(&map, &reference)
203 }
204
205 fn operations_string(ops: Vec<Op<Alpha, i8>>) -> bool {
206 let mut map = OrderMap::new();
207 let mut reference = HashMap::new();
208 do_ops(&ops, &mut map, &mut reference);
209 assert_maps_equivalent(&map, &reference)
210 }
211
212 fn keys_values(ops: Large<Vec<Op<i8, i8>>>) -> bool {
213 let mut map = OrderMap::new();
214 let mut reference = HashMap::new();
215 do_ops(&ops, &mut map, &mut reference);
216 let mut visit = OrderMap::new();
217 for (k, v) in map.keys().zip(map.values()) {
218 assert_eq!(&map[k], v);
219 assert!(!visit.contains_key(k));
220 visit.insert(*k, *v);
221 }
222 assert_eq!(visit.len(), reference.len());
223 true
224 }
225
226 fn keys_values_mut(ops: Large<Vec<Op<i8, i8>>>) -> bool {
227 let mut map = OrderMap::new();
228 let mut reference = HashMap::new();
229 do_ops(&ops, &mut map, &mut reference);
230 let mut visit = OrderMap::new();
231 let keys = Vec::from_iter(map.keys().cloned());
232 for (k, v) in keys.iter().zip(map.values_mut()) {
233 assert_eq!(&reference[k], v);
234 assert!(!visit.contains_key(k));
235 visit.insert(*k, *v);
236 }
237 assert_eq!(visit.len(), reference.len());
238 true
239 }
240
241 fn equality(ops1: Vec<Op<i8, i8>>, removes: Vec<usize>) -> bool {
242 let mut map = OrderMap::new();
243 let mut reference = HashMap::new();
244 do_ops(&ops1, &mut map, &mut reference);
245 let mut ops2 = ops1.clone();
246 for &r in &removes {
247 if !ops2.is_empty() {
248 let i = r % ops2.len();
249 ops2.remove(i);
250 }
251 }
252 let mut map2 = OrderMapFnv::default();
253 let mut reference2 = HashMap::new();
254 do_ops(&ops2, &mut map2, &mut reference2);
255 assert_eq!(map == map2, reference == reference2);
256 true
257 }
258
259 fn retain_ordered(keys: Large<Vec<i8>>, remove: Large<Vec<i8>>) -> () {
260 let mut map = ordermap(keys.iter());
261 let initial_map = map.clone(); // deduplicated in-order input
262 let remove_map = ordermap(remove.iter());
263 let keys_s = set(keys.iter());
264 let remove_s = set(remove.iter());
265 let answer = &keys_s - &remove_s;
266 map.retain(|k, _| !remove_map.contains_key(k));
267
268 // check the values
269 assert_eq!(map.len(), answer.len());
270 for key in &answer {
271 assert!(map.contains_key(key));
272 }
273 // check the order
274 itertools::assert_equal(map.keys(), initial_map.keys().filter(|&k| !remove_map.contains_key(k)));
275 }
276
277 fn sort_1(keyvals: Large<Vec<(i8, i8)>>) -> () {
278 let mut map: OrderMap<_, _> = OrderMap::from_iter(keyvals.to_vec());
279 let mut answer = keyvals.0;
280 answer.sort_by_key(|t| t.0);
281
282 // reverse dedup: Because OrderMap::from_iter keeps the last value for
283 // identical keys
284 answer.reverse();
285 answer.dedup_by_key(|t| t.0);
286 answer.reverse();
287
288 map.sort_by(|k1, _, k2, _| Ord::cmp(k1, k2));
289
290 // check it contains all the values it should
291 for &(key, val) in &answer {
292 assert_eq!(map[&key], val);
293 }
294
295 // check the order
296
297 let mapv = Vec::from_iter(map);
298 assert_eq!(answer, mapv);
299
300 }
301
302 fn sort_2(keyvals: Large<Vec<(i8, i8)>>) -> () {
303 let mut map: OrderMap<_, _> = OrderMap::from_iter(keyvals.to_vec());
304 map.sort_by(|_, v1, _, v2| Ord::cmp(v1, v2));
305 assert_sorted_by_key(map, |t| t.1);
306 }
307 }
308
assert_sorted_by_key<I, Key, X>(iterable: I, key: Key) where I: IntoIterator, I::Item: Ord + Clone + Debug, Key: Fn(&I::Item) -> X, X: Ord,309 fn assert_sorted_by_key<I, Key, X>(iterable: I, key: Key)
310 where I: IntoIterator,
311 I::Item: Ord + Clone + Debug,
312 Key: Fn(&I::Item) -> X,
313 X: Ord,
314 {
315 let input = Vec::from_iter(iterable);
316 let mut sorted = input.clone();
317 sorted.sort_by_key(key);
318 assert_eq!(input, sorted);
319 }
320
321 #[derive(Clone, Debug, Hash, PartialEq, Eq)]
322 struct Alpha(String);
323
324 impl Deref for Alpha {
325 type Target = String;
deref(&self) -> &String326 fn deref(&self) -> &String { &self.0 }
327 }
328
329 const ALPHABET: &'static [u8] = b"abcdefghijklmnopqrstuvwxyz";
330
331 impl Arbitrary for Alpha {
arbitrary<G: Gen>(g: &mut G) -> Self332 fn arbitrary<G: Gen>(g: &mut G) -> Self {
333 let len = g.next_u32() % g.size() as u32;
334 let len = min(len, 16);
335 Alpha((0..len).map(|_| {
336 ALPHABET[g.next_u32() as usize % ALPHABET.len()] as char
337 }).collect())
338 }
339
shrink(&self) -> Box<Iterator<Item=Self>>340 fn shrink(&self) -> Box<Iterator<Item=Self>> {
341 Box::new((**self).shrink().map(Alpha))
342 }
343 }
344
345 /// quickcheck Arbitrary adaptor -- make a larger vec
346 #[derive(Clone, Debug)]
347 struct Large<T>(T);
348
349 impl<T> Deref for Large<T> {
350 type Target = T;
deref(&self) -> &T351 fn deref(&self) -> &T { &self.0 }
352 }
353
354 impl<T> Arbitrary for Large<Vec<T>>
355 where T: Arbitrary
356 {
arbitrary<G: Gen>(g: &mut G) -> Self357 fn arbitrary<G: Gen>(g: &mut G) -> Self {
358 let len = g.next_u32() % (g.size() * 10) as u32;
359 Large((0..len).map(|_| T::arbitrary(g)).collect())
360 }
361
shrink(&self) -> Box<Iterator<Item=Self>>362 fn shrink(&self) -> Box<Iterator<Item=Self>> {
363 Box::new((**self).shrink().map(Large))
364 }
365 }
366