1 use hashlink::linked_hash_set::{self, LinkedHashSet};
2 use hashlink::DefaultHashBuilder;
3
4 #[allow(dead_code)]
assert_covariance()5 fn assert_covariance() {
6 fn set<'new>(v: LinkedHashSet<&'static str>) -> LinkedHashSet<&'new str> {
7 v
8 }
9
10 fn iter<'a, 'new>(
11 v: linked_hash_set::Iter<'a, &'static str>,
12 ) -> linked_hash_set::Iter<'a, &'new str> {
13 v
14 }
15
16 fn into_iter<'new>(
17 v: linked_hash_set::IntoIter<&'static str>,
18 ) -> linked_hash_set::IntoIter<&'new str> {
19 v
20 }
21
22 fn difference<'a, 'new>(
23 v: linked_hash_set::Difference<'a, &'static str, DefaultHashBuilder>,
24 ) -> linked_hash_set::Difference<'a, &'new str, DefaultHashBuilder> {
25 v
26 }
27
28 fn symmetric_difference<'a, 'new>(
29 v: linked_hash_set::SymmetricDifference<'a, &'static str, DefaultHashBuilder>,
30 ) -> linked_hash_set::SymmetricDifference<'a, &'new str, DefaultHashBuilder> {
31 v
32 }
33
34 fn intersection<'a, 'new>(
35 v: linked_hash_set::Intersection<'a, &'static str, DefaultHashBuilder>,
36 ) -> linked_hash_set::Intersection<'a, &'new str, DefaultHashBuilder> {
37 v
38 }
39
40 fn union<'a, 'new>(
41 v: linked_hash_set::Union<'a, &'static str, DefaultHashBuilder>,
42 ) -> linked_hash_set::Union<'a, &'new str, DefaultHashBuilder> {
43 v
44 }
45
46 fn drain<'new>(
47 d: linked_hash_set::Drain<'static, &'static str>,
48 ) -> linked_hash_set::Drain<'new, &'new str> {
49 d
50 }
51 }
52
53 #[test]
test_zero_capacities()54 fn test_zero_capacities() {
55 type HS = LinkedHashSet<i32>;
56
57 let s = HS::new();
58 assert_eq!(s.capacity(), 0);
59
60 let s = HS::default();
61 assert_eq!(s.capacity(), 0);
62
63 let s = HS::with_hasher(DefaultHashBuilder::default());
64 assert_eq!(s.capacity(), 0);
65
66 let s = HS::with_capacity(0);
67 assert_eq!(s.capacity(), 0);
68
69 let s = HS::with_capacity_and_hasher(0, DefaultHashBuilder::default());
70 assert_eq!(s.capacity(), 0);
71
72 let mut s = HS::new();
73 s.insert(1);
74 s.insert(2);
75 s.remove(&1);
76 s.remove(&2);
77 s.shrink_to_fit();
78 assert_eq!(s.capacity(), 0);
79
80 let mut s = HS::new();
81 s.reserve(0);
82 assert_eq!(s.capacity(), 0);
83 }
84
85 #[test]
test_disjoint()86 fn test_disjoint() {
87 let mut xs = LinkedHashSet::new();
88 let mut ys = LinkedHashSet::new();
89 assert!(xs.is_disjoint(&ys));
90 assert!(ys.is_disjoint(&xs));
91 assert!(xs.insert(5));
92 assert!(ys.insert(11));
93 assert!(xs.is_disjoint(&ys));
94 assert!(ys.is_disjoint(&xs));
95 assert!(xs.insert(7));
96 assert!(xs.insert(19));
97 assert!(xs.insert(4));
98 assert!(ys.insert(2));
99 assert!(ys.insert(-11));
100 assert!(xs.is_disjoint(&ys));
101 assert!(ys.is_disjoint(&xs));
102 assert!(ys.insert(7));
103 assert!(!xs.is_disjoint(&ys));
104 assert!(!ys.is_disjoint(&xs));
105 }
106
107 #[test]
test_subset_and_superset()108 fn test_subset_and_superset() {
109 let mut a = LinkedHashSet::new();
110 assert!(a.insert(0));
111 assert!(a.insert(5));
112 assert!(a.insert(11));
113 assert!(a.insert(7));
114
115 let mut b = LinkedHashSet::new();
116 assert!(b.insert(0));
117 assert!(b.insert(7));
118 assert!(b.insert(19));
119 assert!(b.insert(250));
120 assert!(b.insert(11));
121 assert!(b.insert(200));
122
123 assert!(!a.is_subset(&b));
124 assert!(!a.is_superset(&b));
125 assert!(!b.is_subset(&a));
126 assert!(!b.is_superset(&a));
127
128 assert!(b.insert(5));
129
130 assert!(a.is_subset(&b));
131 assert!(!a.is_superset(&b));
132 assert!(!b.is_subset(&a));
133 assert!(b.is_superset(&a));
134 }
135
136 #[test]
test_iterate()137 fn test_iterate() {
138 let mut a = LinkedHashSet::new();
139 for i in 0..32 {
140 assert!(a.insert(i));
141 }
142 let mut observed: u32 = 0;
143 for k in &a {
144 observed |= 1 << *k;
145 }
146 assert_eq!(observed, 0xFFFF_FFFF);
147 }
148
149 #[test]
test_intersection()150 fn test_intersection() {
151 let mut a = LinkedHashSet::new();
152 let mut b = LinkedHashSet::new();
153
154 assert!(a.insert(11));
155 assert!(a.insert(1));
156 assert!(a.insert(3));
157 assert!(a.insert(77));
158 assert!(a.insert(103));
159 assert!(a.insert(5));
160 assert!(a.insert(-5));
161
162 assert!(b.insert(2));
163 assert!(b.insert(11));
164 assert!(b.insert(77));
165 assert!(b.insert(-9));
166 assert!(b.insert(-42));
167 assert!(b.insert(5));
168 assert!(b.insert(3));
169
170 let mut i = 0;
171 let expected = [3, 5, 11, 77];
172 for x in a.intersection(&b) {
173 assert!(expected.contains(x));
174 i += 1
175 }
176 assert_eq!(i, expected.len());
177 }
178
179 #[test]
test_difference()180 fn test_difference() {
181 let mut a = LinkedHashSet::new();
182 let mut b = LinkedHashSet::new();
183
184 assert!(a.insert(1));
185 assert!(a.insert(3));
186 assert!(a.insert(5));
187 assert!(a.insert(9));
188 assert!(a.insert(11));
189
190 assert!(b.insert(3));
191 assert!(b.insert(9));
192
193 let mut i = 0;
194 let expected = [1, 5, 11];
195 for x in a.difference(&b) {
196 assert!(expected.contains(x));
197 i += 1
198 }
199 assert_eq!(i, expected.len());
200 }
201
202 #[test]
test_symmetric_difference()203 fn test_symmetric_difference() {
204 let mut a = LinkedHashSet::new();
205 let mut b = LinkedHashSet::new();
206
207 assert!(a.insert(1));
208 assert!(a.insert(3));
209 assert!(a.insert(5));
210 assert!(a.insert(9));
211 assert!(a.insert(11));
212
213 assert!(b.insert(-2));
214 assert!(b.insert(3));
215 assert!(b.insert(9));
216 assert!(b.insert(14));
217 assert!(b.insert(22));
218
219 let mut i = 0;
220 let expected = [-2, 1, 5, 11, 14, 22];
221 for x in a.symmetric_difference(&b) {
222 assert!(expected.contains(x));
223 i += 1
224 }
225 assert_eq!(i, expected.len());
226 }
227
228 #[test]
test_union()229 fn test_union() {
230 let mut a = LinkedHashSet::new();
231 let mut b = LinkedHashSet::new();
232
233 assert!(a.insert(1));
234 assert!(a.insert(3));
235 assert!(a.insert(5));
236 assert!(a.insert(9));
237 assert!(a.insert(11));
238 assert!(a.insert(16));
239 assert!(a.insert(19));
240 assert!(a.insert(24));
241
242 assert!(b.insert(-2));
243 assert!(b.insert(1));
244 assert!(b.insert(5));
245 assert!(b.insert(9));
246 assert!(b.insert(13));
247 assert!(b.insert(19));
248
249 let mut i = 0;
250 let expected = [-2, 1, 3, 5, 9, 11, 13, 16, 19, 24];
251 for x in a.union(&b) {
252 assert!(expected.contains(x));
253 i += 1
254 }
255 assert_eq!(i, expected.len());
256 }
257
258 #[test]
test_from_iter()259 fn test_from_iter() {
260 let xs = [1, 2, 3, 4, 5, 6, 7, 8, 9];
261
262 let set: LinkedHashSet<_> = xs.iter().cloned().collect();
263
264 for x in &xs {
265 assert!(set.contains(x));
266 }
267 }
268
269 #[test]
test_move_iter()270 fn test_move_iter() {
271 let hs = {
272 let mut hs = LinkedHashSet::new();
273
274 hs.insert('a');
275 hs.insert('b');
276
277 hs
278 };
279
280 let v = hs.into_iter().collect::<Vec<char>>();
281 assert!(v == ['a', 'b'] || v == ['b', 'a']);
282 }
283
284 #[test]
test_eq()285 fn test_eq() {
286 let mut s1 = LinkedHashSet::new();
287
288 s1.insert(1);
289 s1.insert(2);
290 s1.insert(3);
291
292 let mut s2 = LinkedHashSet::new();
293
294 s2.insert(1);
295 s2.insert(2);
296
297 assert!(s1 != s2);
298
299 s2.insert(3);
300
301 assert_eq!(s1, s2);
302 }
303
304 #[test]
test_show()305 fn test_show() {
306 let mut set = LinkedHashSet::new();
307 let empty = LinkedHashSet::<i32>::new();
308
309 set.insert(1);
310 set.insert(2);
311
312 let set_str = format!("{:?}", set);
313
314 assert!(set_str == "{1, 2}" || set_str == "{2, 1}");
315 assert_eq!(format!("{:?}", empty), "{}");
316 }
317
318 #[test]
test_trivial_drain()319 fn test_trivial_drain() {
320 let mut s = LinkedHashSet::<i32>::new();
321 for _ in s.drain() {}
322 assert!(s.is_empty());
323 drop(s);
324
325 let mut s = LinkedHashSet::<i32>::new();
326 drop(s.drain());
327 assert!(s.is_empty());
328 }
329
330 #[test]
test_drain()331 fn test_drain() {
332 let mut s: LinkedHashSet<_> = (1..100).collect();
333
334 for _ in 0..20 {
335 assert_eq!(s.len(), 99);
336
337 {
338 let mut last_i = 0;
339 let mut d = s.drain();
340 for (i, x) in d.by_ref().take(50).enumerate() {
341 last_i = i;
342 assert!(x != 0);
343 }
344 assert_eq!(last_i, 49);
345 }
346
347 assert_eq!((&s).into_iter().count(), 0);
348
349 s.extend(1..100);
350 }
351 }
352
353 #[test]
test_replace()354 fn test_replace() {
355 use core::hash;
356
357 #[derive(Debug)]
358 struct Foo(&'static str, i32);
359
360 impl PartialEq for Foo {
361 fn eq(&self, other: &Self) -> bool {
362 self.0 == other.0
363 }
364 }
365
366 impl Eq for Foo {}
367
368 impl hash::Hash for Foo {
369 fn hash<H: hash::Hasher>(&self, h: &mut H) {
370 self.0.hash(h);
371 }
372 }
373
374 impl Foo {
375 fn really_eq(&self, other: &Self) -> bool {
376 self.0 == other.0 && self.1 == other.1
377 }
378 }
379
380 let mut s = LinkedHashSet::new();
381 assert_eq!(s.replace(Foo("a", 1)), None);
382 assert_eq!(s.len(), 1);
383 assert_eq!(
384 s.replace(Foo("a", 2)).map(|f| f.really_eq(&Foo("a", 1))),
385 Some(true)
386 );
387 assert_eq!(s.len(), 1);
388
389 let mut it = s.iter();
390 assert_eq!(it.next().map(|f| f.really_eq(&Foo("a", 2))), Some(true));
391 assert_eq!(it.next(), None);
392 }
393
394 #[test]
test_extend_ref()395 fn test_extend_ref() {
396 let mut a = LinkedHashSet::new();
397 a.insert(1);
398
399 a.extend(&[2, 3, 4]);
400
401 assert_eq!(a.len(), 4);
402 assert!(a.contains(&1));
403 assert!(a.contains(&2));
404 assert!(a.contains(&3));
405 assert!(a.contains(&4));
406
407 let mut b = LinkedHashSet::new();
408 b.insert(5);
409 b.insert(6);
410
411 a.extend(&b);
412
413 assert_eq!(a.len(), 6);
414 assert!(a.contains(&1));
415 assert!(a.contains(&2));
416 assert!(a.contains(&3));
417 assert!(a.contains(&4));
418 assert!(a.contains(&5));
419 assert!(a.contains(&6));
420 }
421
422 #[test]
test_retain()423 fn test_retain() {
424 let xs = [1, 2, 3, 4, 5, 6];
425 let mut set: LinkedHashSet<i32> = xs.iter().cloned().collect();
426 set.retain(|&k| k % 2 == 0);
427 assert_eq!(set.len(), 3);
428 assert!(set.contains(&2));
429 assert!(set.contains(&4));
430 assert!(set.contains(&6));
431 }
432
433 #[test]
test_retain_with_order()434 fn test_retain_with_order() {
435 let xs = [1, 2, 3, 4, 5, 6];
436 let mut set: LinkedHashSet<i32> = xs.iter().cloned().collect();
437 let mut vec = Vec::new();
438 set.retain_with_order(|&k| {
439 if k % 2 == 0 {
440 true
441 } else {
442 vec.push(k);
443 false
444 }
445 });
446 assert_eq!(vec![1, 3, 5], vec);
447 }
448
449 #[test]
insert_order()450 fn insert_order() {
451 let mut set = LinkedHashSet::new();
452 set.insert(1);
453 set.insert(2);
454 set.insert(3);
455 set.insert(4);
456 assert_eq!(
457 set.clone().into_iter().collect::<Vec<_>>(),
458 vec![1, 2, 3, 4]
459 );
460 assert_eq!(set.into_iter().collect::<Vec<_>>(), vec![1, 2, 3, 4]);
461 }
462
463 #[test]
front_back()464 fn front_back() {
465 let mut set = LinkedHashSet::new();
466 set.insert(1);
467 set.insert(2);
468 set.insert(3);
469 set.insert(4);
470 assert_eq!(set.front(), Some(&1));
471 assert_eq!(set.back(), Some(&4));
472 assert_eq!(set.pop_back(), Some(4));
473 assert_eq!(set.back(), Some(&3));
474 assert_eq!(set.pop_front(), Some(1));
475 assert_eq!(set.front(), Some(&2));
476 }
477
478 #[test]
double_ended_iter()479 fn double_ended_iter() {
480 let mut set = LinkedHashSet::new();
481 set.insert(1);
482 set.insert(2);
483 set.insert(3);
484 set.insert(4);
485
486 let mut iter = set.iter();
487 assert_eq!(iter.next(), Some(&1));
488 assert_eq!(iter.next(), Some(&2));
489 assert_eq!(iter.next_back(), Some(&4));
490 assert_eq!(iter.next_back(), Some(&3));
491 assert_eq!(iter.next_back(), None);
492 assert_eq!(iter.next(), None);
493 assert_eq!(iter.next_back(), None);
494
495 let mut iter = set.drain();
496 assert_eq!(iter.next(), Some(1));
497 assert_eq!(iter.next(), Some(2));
498 assert_eq!(iter.next_back(), Some(4));
499 assert_eq!(iter.next_back(), Some(3));
500 assert_eq!(iter.next_back(), None);
501 assert_eq!(iter.next(), None);
502 assert_eq!(iter.next_back(), None);
503 drop(iter);
504
505 set.insert(1);
506 set.insert(2);
507 set.insert(3);
508 set.insert(4);
509
510 let mut iter = set.into_iter();
511 assert_eq!(iter.next(), Some(1));
512 assert_eq!(iter.next(), Some(2));
513 assert_eq!(iter.next_back(), Some(4));
514 assert_eq!(iter.next_back(), Some(3));
515 assert_eq!(iter.next_back(), None);
516 assert_eq!(iter.next(), None);
517 assert_eq!(iter.next_back(), None);
518 }
519
520 #[test]
to_back_front_order()521 fn to_back_front_order() {
522 let mut set = LinkedHashSet::new();
523 set.insert(1);
524 set.insert(2);
525 set.insert(3);
526 set.insert(4);
527
528 assert_eq!(set.back().copied(), Some(4));
529 assert_eq!(set.front().copied(), Some(1));
530 set.to_back(&2);
531 assert_eq!(set.back().copied(), Some(2));
532 set.to_front(&3);
533 assert_eq!(set.front().copied(), Some(3));
534 }
535
536 #[test]
test_order_equality()537 fn test_order_equality() {
538 let xs = [1, 2, 3, 4, 5, 6];
539 let mut set1: LinkedHashSet<i32> = xs.iter().copied().collect();
540 let mut set2: LinkedHashSet<i32> = xs.iter().copied().collect();
541
542 assert_eq!(set1, set2);
543
544 set1.to_front(&4);
545 assert_ne!(set1, set2);
546
547 set2.to_front(&4);
548 assert_eq!(set1, set2);
549 }
550