1 use hashbrown::hash_map::DefaultHashBuilder;
2 use hashlink::linked_hash_set::{self, LinkedHashSet};
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 for _ in &s {
348 panic!("s should be empty!");
349 }
350
351 s.extend(1..100);
352 }
353 }
354
355 #[test]
test_replace()356 fn test_replace() {
357 use core::hash;
358
359 #[derive(Debug)]
360 struct Foo(&'static str, i32);
361
362 impl PartialEq for Foo {
363 fn eq(&self, other: &Self) -> bool {
364 self.0 == other.0
365 }
366 }
367
368 impl Eq for Foo {}
369
370 impl hash::Hash for Foo {
371 fn hash<H: hash::Hasher>(&self, h: &mut H) {
372 self.0.hash(h);
373 }
374 }
375
376 let mut s = LinkedHashSet::new();
377 assert_eq!(s.replace(Foo("a", 1)), None);
378 assert_eq!(s.len(), 1);
379 assert_eq!(s.replace(Foo("a", 2)), Some(Foo("a", 1)));
380 assert_eq!(s.len(), 1);
381
382 let mut it = s.iter();
383 assert_eq!(it.next(), Some(&Foo("a", 2)));
384 assert_eq!(it.next(), None);
385 }
386
387 #[test]
test_extend_ref()388 fn test_extend_ref() {
389 let mut a = LinkedHashSet::new();
390 a.insert(1);
391
392 a.extend(&[2, 3, 4]);
393
394 assert_eq!(a.len(), 4);
395 assert!(a.contains(&1));
396 assert!(a.contains(&2));
397 assert!(a.contains(&3));
398 assert!(a.contains(&4));
399
400 let mut b = LinkedHashSet::new();
401 b.insert(5);
402 b.insert(6);
403
404 a.extend(&b);
405
406 assert_eq!(a.len(), 6);
407 assert!(a.contains(&1));
408 assert!(a.contains(&2));
409 assert!(a.contains(&3));
410 assert!(a.contains(&4));
411 assert!(a.contains(&5));
412 assert!(a.contains(&6));
413 }
414
415 #[test]
test_retain()416 fn test_retain() {
417 let xs = [1, 2, 3, 4, 5, 6];
418 let mut set: LinkedHashSet<i32> = xs.iter().cloned().collect();
419 set.retain(|&k| k % 2 == 0);
420 assert_eq!(set.len(), 3);
421 assert!(set.contains(&2));
422 assert!(set.contains(&4));
423 assert!(set.contains(&6));
424 }
425
426 #[test]
test_retain_with_order()427 fn test_retain_with_order() {
428 let xs = [1, 2, 3, 4, 5, 6];
429 let mut set: LinkedHashSet<i32> = xs.iter().cloned().collect();
430 let mut vec = Vec::new();
431 set.retain_with_order(|&k| {
432 if k % 2 == 0 {
433 true
434 } else {
435 vec.push(k);
436 false
437 }
438 });
439 assert_eq!(vec![1, 3, 5], vec);
440 }
441
442 #[test]
insert_order()443 fn insert_order() {
444 let mut set = LinkedHashSet::new();
445 set.insert(1);
446 set.insert(2);
447 set.insert(3);
448 set.insert(4);
449 assert_eq!(
450 set.clone().into_iter().collect::<Vec<_>>(),
451 vec![1, 2, 3, 4]
452 );
453 assert_eq!(set.into_iter().collect::<Vec<_>>(), vec![1, 2, 3, 4]);
454 }
455
456 #[test]
front_back()457 fn front_back() {
458 let mut set = LinkedHashSet::new();
459 set.insert(1);
460 set.insert(2);
461 set.insert(3);
462 set.insert(4);
463 assert_eq!(set.front(), Some(&1));
464 assert_eq!(set.back(), Some(&4));
465 assert_eq!(set.pop_back(), Some(4));
466 assert_eq!(set.back(), Some(&3));
467 assert_eq!(set.pop_front(), Some(1));
468 assert_eq!(set.front(), Some(&2));
469 }
470
471 #[test]
double_ended_iter()472 fn double_ended_iter() {
473 let mut set = LinkedHashSet::new();
474 set.insert(1);
475 set.insert(2);
476 set.insert(3);
477 set.insert(4);
478
479 let mut iter = set.iter();
480 assert_eq!(iter.next(), Some(&1));
481 assert_eq!(iter.next(), Some(&2));
482 assert_eq!(iter.next_back(), Some(&4));
483 assert_eq!(iter.next_back(), Some(&3));
484 assert_eq!(iter.next_back(), None);
485 assert_eq!(iter.next(), None);
486 assert_eq!(iter.next_back(), None);
487 drop(iter);
488
489 let mut iter = set.drain();
490 assert_eq!(iter.next(), Some(1));
491 assert_eq!(iter.next(), Some(2));
492 assert_eq!(iter.next_back(), Some(4));
493 assert_eq!(iter.next_back(), Some(3));
494 assert_eq!(iter.next_back(), None);
495 assert_eq!(iter.next(), None);
496 assert_eq!(iter.next_back(), None);
497 drop(iter);
498
499 set.insert(1);
500 set.insert(2);
501 set.insert(3);
502 set.insert(4);
503
504 let mut iter = set.into_iter();
505 assert_eq!(iter.next(), Some(1));
506 assert_eq!(iter.next(), Some(2));
507 assert_eq!(iter.next_back(), Some(4));
508 assert_eq!(iter.next_back(), Some(3));
509 assert_eq!(iter.next_back(), None);
510 assert_eq!(iter.next(), None);
511 assert_eq!(iter.next_back(), None);
512 }
513
514 #[test]
to_back_front_order()515 fn to_back_front_order() {
516 let mut set = LinkedHashSet::new();
517 set.insert(1);
518 set.insert(2);
519 set.insert(3);
520 set.insert(4);
521
522 assert_eq!(set.back().copied(), Some(4));
523 assert_eq!(set.front().copied(), Some(1));
524 set.to_back(&2);
525 assert_eq!(set.back().copied(), Some(2));
526 set.to_front(&3);
527 assert_eq!(set.front().copied(), Some(3));
528 }
529
530 #[test]
test_order_equality()531 fn test_order_equality() {
532 let xs = [1, 2, 3, 4, 5, 6];
533 let mut set1: LinkedHashSet<i32> = xs.iter().copied().collect();
534 let mut set2: LinkedHashSet<i32> = xs.iter().copied().collect();
535
536 assert_eq!(set1, set2);
537
538 set1.to_front(&4);
539 assert_ne!(set1, set2);
540
541 set2.to_front(&4);
542 assert_eq!(set1, set2);
543 }
544