sdset/
lib.rs

1//! Operations for already sorted and deduplicated slices.
2//!
3//! This library contains two modules containing types to produce set operations:
4//!   - The [`duo`] module is for types limited to be used with two slices not more not less.
5//!   - The [`multi`] module types can be used to do set operations on multiple slices from zero up to an infinite number.
6//!
7//! The [`duo`] operations are much more performant than [`multi`]
8//! so prefer using [`duo`] when you know that you will need set operations for two slices.
9//!
10//! # Examples
11//!
12//! Using a [`duo`] _union_ set operation on two slices.
13//!
14//! ```
15//! # use sdset::Error;
16//! # fn try_main() -> Result<(), Error> {
17//! use sdset::duo::OpBuilder;
18//! use sdset::{SetOperation, Set, SetBuf};
19//!
20//! let a = Set::new(&[1, 2, 4, 6, 7])?;
21//! let b = Set::new(&[2, 3, 4, 5, 6, 7])?;
22//!
23//! let op = OpBuilder::new(a, b).union();
24//!
25//! let res: SetBuf<i32> = op.into_set_buf();
26//! assert_eq!(&res[..], &[1, 2, 3, 4, 5, 6, 7]);
27//! # Ok(()) }
28//! # try_main().unwrap();
29//! ```
30//!
31//! Using a [`multi`] _intersection_ set operation on three slices.
32//!
33//! ```
34//! # use sdset::Error;
35//! # fn try_main() -> Result<(), Error> {
36//! use sdset::multi::OpBuilder;
37//! use sdset::{SetOperation, Set, SetBuf};
38//!
39//! let a = Set::new(&[1, 2, 4])?;
40//! let b = Set::new(&[2, 3, 4, 5, 7])?;
41//! let c = Set::new(&[2, 4, 6, 7])?;
42//!
43//! let op = OpBuilder::from_vec(vec![a, b, c]).intersection();
44//!
45//! let res: SetBuf<i32> = op.into_set_buf();
46//! assert_eq!(&res[..], &[2, 4]);
47//! # Ok(()) }
48//! # try_main().unwrap();
49//! ```
50
51#![warn(missing_docs)]
52
53#![cfg_attr(feature = "unstable", feature(test))]
54
55#[cfg(feature="serde")]
56extern crate serde;
57
58#[cfg(test)]
59#[macro_use] extern crate quickcheck;
60
61pub mod duo;
62pub mod multi;
63pub mod set;
64mod collection;
65mod two_minimums;
66
67use std::cmp::{self, Ordering};
68pub use crate::set::{Set, SetBuf, Error};
69pub use crate::collection::{Collection, Counter};
70
71/// Exponential searches this sorted slice for a given element.
72///
73/// If the value is found then `Ok` is returned, containing the index of the matching element;
74/// if the value is not found then `Err` is returned, containing the index where a matching element
75/// could be inserted while maintaining sorted order.
76///
77/// # Examples
78///
79/// Looks up a series of four elements. The first is found, with a
80/// uniquely determined position; the second and third are not
81/// found; the fourth could match any position in `[1, 4]`.
82///
83/// ```
84/// use sdset::exponential_search;
85///
86/// let s = &[0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
87///
88/// assert_eq!(exponential_search(s, &13),  Ok(9));
89/// assert_eq!(exponential_search(s, &4),   Err(7));
90/// assert_eq!(exponential_search(s, &100), Err(13));
91/// let r = exponential_search(s, &1);
92/// assert!(match r { Ok(1..=4) => true, _ => false, });
93/// ```
94#[inline]
95pub fn exponential_search<T>(slice: &[T], elem: &T) -> Result<usize, usize>
96where T: Ord
97{
98    exponential_search_by(slice, |x| x.cmp(elem))
99}
100
101/// Binary searches this sorted slice with a comparator function.
102///
103/// The comparator function should implement an order consistent with the sort order of
104/// the underlying slice, returning an order code that indicates whether its argument
105/// is `Less`, `Equal` or `Greater` the desired target.
106///
107/// If the value is found then `Ok` is returned, containing the index of the matching element;
108/// if the value is not found then `Err` is returned, containing the index where a matching element
109/// could be inserted while maintaining sorted order.
110///
111/// # Examples
112///
113/// Looks up a series of four elements. The first is found, with a
114/// uniquely determined position; the second and third are not
115/// found; the fourth could match any position in `[1, 4]`.
116///
117/// ```
118/// use sdset::exponential_search_by;
119///
120/// let s = &[0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
121///
122/// let seek = 13;
123/// assert_eq!(exponential_search_by(s, |probe| probe.cmp(&seek)), Ok(9));
124/// let seek = 4;
125/// assert_eq!(exponential_search_by(s, |probe| probe.cmp(&seek)), Err(7));
126/// let seek = 100;
127/// assert_eq!(exponential_search_by(s, |probe| probe.cmp(&seek)), Err(13));
128/// let seek = 1;
129/// let r = exponential_search_by(s, |probe| probe.cmp(&seek));
130/// assert!(match r { Ok(1..=4) => true, _ => false, });
131/// ```
132#[inline]
133pub fn exponential_search_by<T, F>(slice: &[T], mut f: F) -> Result<usize, usize>
134where F: FnMut(&T) -> Ordering,
135{
136    let mut index = 1;
137    while index < slice.len() && f(&slice[index]) == Ordering::Less {
138        index *= 2;
139    }
140
141    let half_bound = index / 2;
142    let bound = cmp::min(index + 1, slice.len());
143
144    match slice[half_bound..bound].binary_search_by(f) {
145        Ok(pos) => Ok(half_bound + pos),
146        Err(pos) => Err(half_bound + pos),
147    }
148}
149
150/// Binary searches this sorted slice with a key extraction function.
151///
152/// Assumes that the slice is sorted by the key.
153///
154/// If the value is found then `Ok` is returned, containing the index of the matching element;
155/// if the value is not found then `Err` is returned, containing the index where a matching element
156/// could be inserted while maintaining sorted order.
157///
158/// # Examples
159///
160/// Looks up a series of four elements. The first is found, with a
161/// uniquely determined position; the second and third are not
162/// found; the fourth could match any position in `[1, 4]`.
163///
164/// ```
165/// use sdset::exponential_search_by_key;
166///
167/// let s = &[(0, 0), (2, 1), (4, 1), (5, 1), (3, 1),
168///           (1, 2), (2, 3), (4, 5), (5, 8), (3, 13),
169///           (1, 21), (2, 34), (4, 55)];
170///
171/// assert_eq!(exponential_search_by_key(s, &13, |&(a,b)| b),  Ok(9));
172/// assert_eq!(exponential_search_by_key(s, &4, |&(a,b)| b),   Err(7));
173/// assert_eq!(exponential_search_by_key(s, &100, |&(a,b)| b), Err(13));
174/// let r = exponential_search_by_key(s, &1, |&(a,b)| b);
175/// assert!(match r { Ok(1..=4) => true, _ => false, });
176/// ```
177#[inline]
178pub fn exponential_search_by_key<T, B, F>(slice: &[T], b: &B, mut f: F) -> Result<usize, usize>
179where F: FnMut(&T) -> B,
180      B: Ord
181{
182    exponential_search_by(slice, |k| f(k).cmp(b))
183}
184
185#[inline]
186fn exponential_offset_ge<'a, T>(slice: &'a [T], elem: &T) -> &'a [T]
187where T: Ord,
188{
189    exponential_offset_ge_by(slice, |x| x.cmp(elem))
190}
191
192#[inline]
193fn exponential_offset_ge_by<T, F>(slice: &[T], f: F) -> &[T]
194where F: FnMut(&T) -> Ordering,
195{
196    match exponential_search_by(slice, f) {
197        Ok(pos) => &slice[pos..],
198        Err(pos) => &slice[pos..],
199    }
200}
201
202#[inline]
203fn exponential_offset_ge_by_key<'a, T, B, F>(slice: &'a [T], b: &B, mut f: F) -> &'a [T]
204where F: FnMut(&T) -> B,
205      B: Ord,
206{
207    exponential_offset_ge_by(slice, |x| f(x).cmp(b))
208}
209
210/// Represent a type that can produce a set operation on multiple [`Set`]s.
211pub trait SetOperation<T>: Sized {
212    /// Extend a [`Collection`] with the values of the [`Set`]s using this set operation.
213    fn extend_collection<C>(self, output: &mut C) where C: Collection<T>;
214
215    /// Create a [`SetBuf`] using the [`SetOperation::extend_collection`] method.
216    fn into_set_buf(self) -> SetBuf<T> where T: Clone {
217        let mut vec = Vec::new();
218        self.extend_collection(&mut vec);
219        SetBuf::new_unchecked(vec)
220    }
221}
222
223#[cfg(all(feature = "unstable", test))]
224mod bench {
225    mod _btree {
226        mod difference {
227            extern crate test;
228            use self::test::Bencher;
229
230            #[bench]
231            fn two_slices_big(bench: &mut Bencher) {
232                use std::collections::BTreeSet;
233                use std::iter::FromIterator;
234
235                let a: Vec<_> = (0..100).collect();
236                let b: Vec<_> = (1..101).collect();
237
238                let a = BTreeSet::from_iter(a);
239                let b = BTreeSet::from_iter(b);
240
241                bench.iter(|| {
242                    let set: Vec<_> = a.difference(&b).cloned().collect();
243                    test::black_box(|| set);
244                });
245            }
246
247            #[bench]
248            fn two_slices_big2(bench: &mut Bencher) {
249                use std::collections::BTreeSet;
250                use std::iter::FromIterator;
251
252                let a: Vec<_> = (0..100).collect();
253                let b: Vec<_> = (51..151).collect();
254
255                let a = BTreeSet::from_iter(a);
256                let b = BTreeSet::from_iter(b);
257
258                bench.iter(|| {
259                    let set: Vec<_> = a.difference(&b).cloned().collect();
260                    test::black_box(|| set);
261                });
262            }
263
264            #[bench]
265            fn two_slices_big3(bench: &mut Bencher) {
266                use std::collections::BTreeSet;
267                use std::iter::FromIterator;
268
269                let a: Vec<_> = (0..100).collect();
270                let b: Vec<_> = (100..200).collect();
271
272                let a = BTreeSet::from_iter(a);
273                let b = BTreeSet::from_iter(b);
274
275                bench.iter(|| {
276                    let set: Vec<_> = a.difference(&b).cloned().collect();
277                    test::black_box(|| set);
278                });
279            }
280
281            #[bench]
282            fn three_slices_big(bench: &mut Bencher) {
283                use std::collections::BTreeSet;
284                use std::iter::FromIterator;
285
286                let a: Vec<_> = (0..100).collect();
287                let b: Vec<_> = (1..101).collect();
288                let c: Vec<_> = (2..102).collect();
289
290                let a = BTreeSet::from_iter(a);
291                let b = BTreeSet::from_iter(b);
292                let c = BTreeSet::from_iter(c);
293
294                bench.iter(|| {
295                    let ab = &a - &b;
296                    let set: Vec<_> = ab.difference(&c).cloned().collect();
297                    test::black_box(|| set);
298                });
299            }
300
301            #[bench]
302            fn three_slices_big2(bench: &mut Bencher) {
303                use std::collections::BTreeSet;
304                use std::iter::FromIterator;
305
306                let a: Vec<_> = (0..100).collect();
307                let b: Vec<_> = (34..134).collect();
308                let c: Vec<_> = (67..167).collect();
309
310                let a = BTreeSet::from_iter(a);
311                let b = BTreeSet::from_iter(b);
312                let c = BTreeSet::from_iter(c);
313
314                bench.iter(|| {
315                    let ab = &a - &b;
316                    let set: Vec<_> = ab.difference(&c).cloned().collect();
317                    test::black_box(|| set);
318                });
319            }
320
321            #[bench]
322            fn three_slices_big3(bench: &mut Bencher) {
323                use std::collections::BTreeSet;
324                use std::iter::FromIterator;
325
326                let a: Vec<_> = (0..100).collect();
327                let b: Vec<_> = (100..200).collect();
328                let c: Vec<_> = (200..300).collect();
329
330                let a = BTreeSet::from_iter(a);
331                let b = BTreeSet::from_iter(b);
332                let c = BTreeSet::from_iter(c);
333
334                bench.iter(|| {
335                    let ab = &a - &b;
336                    let set: Vec<_> = ab.difference(&c).cloned().collect();
337                    test::black_box(|| set);
338                });
339            }
340        }
341
342        mod intersection {
343            extern crate test;
344            use self::test::Bencher;
345
346            #[bench]
347            fn two_slices_big(bench: &mut Bencher) {
348                use std::collections::BTreeSet;
349                use std::iter::FromIterator;
350
351                let a: Vec<_> = (0..100).collect();
352                let b: Vec<_> = (1..101).collect();
353
354                let a = BTreeSet::from_iter(a);
355                let b = BTreeSet::from_iter(b);
356
357                bench.iter(|| {
358                    let set: Vec<_> = a.intersection(&b).cloned().collect();
359                    test::black_box(|| set);
360                });
361            }
362
363            #[bench]
364            fn two_slices_big2(bench: &mut Bencher) {
365                use std::collections::BTreeSet;
366                use std::iter::FromIterator;
367
368                let a: Vec<_> = (0..100).collect();
369                let b: Vec<_> = (51..151).collect();
370
371                let a = BTreeSet::from_iter(a);
372                let b = BTreeSet::from_iter(b);
373
374                bench.iter(|| {
375                    let set: Vec<_> = a.intersection(&b).cloned().collect();
376                    test::black_box(|| set);
377                });
378            }
379
380            #[bench]
381            fn two_slices_big3(bench: &mut Bencher) {
382                use std::collections::BTreeSet;
383                use std::iter::FromIterator;
384
385                let a: Vec<_> = (0..100).collect();
386                let b: Vec<_> = (100..200).collect();
387
388                let a = BTreeSet::from_iter(a);
389                let b = BTreeSet::from_iter(b);
390
391                bench.iter(|| {
392                    let set: Vec<_> = a.intersection(&b).cloned().collect();
393                    test::black_box(|| set);
394                });
395            }
396
397            #[bench]
398            fn three_slices_big(bench: &mut Bencher) {
399                use std::collections::BTreeSet;
400                use std::iter::FromIterator;
401
402                let a: Vec<_> = (0..100).collect();
403                let b: Vec<_> = (1..101).collect();
404                let c: Vec<_> = (2..102).collect();
405
406                let a = BTreeSet::from_iter(a);
407                let b = BTreeSet::from_iter(b);
408                let c = BTreeSet::from_iter(c);
409
410                bench.iter(|| {
411                    let ab = &a & &b;
412                    let set: Vec<_> = ab.intersection(&c).cloned().collect();
413                    test::black_box(|| set);
414                });
415            }
416
417            #[bench]
418            fn three_slices_big2(bench: &mut Bencher) {
419                use std::collections::BTreeSet;
420                use std::iter::FromIterator;
421
422                let a: Vec<_> = (0..100).collect();
423                let b: Vec<_> = (34..134).collect();
424                let c: Vec<_> = (67..167).collect();
425
426                let a = BTreeSet::from_iter(a);
427                let b = BTreeSet::from_iter(b);
428                let c = BTreeSet::from_iter(c);
429
430                bench.iter(|| {
431                    let ab = &a & &b;
432                    let set: Vec<_> = ab.intersection(&c).cloned().collect();
433                    test::black_box(|| set);
434                });
435            }
436
437            #[bench]
438            fn three_slices_big3(bench: &mut Bencher) {
439                use std::collections::BTreeSet;
440                use std::iter::FromIterator;
441
442                let a: Vec<_> = (0..100).collect();
443                let b: Vec<_> = (100..200).collect();
444                let c: Vec<_> = (200..300).collect();
445
446                let a = BTreeSet::from_iter(a);
447                let b = BTreeSet::from_iter(b);
448                let c = BTreeSet::from_iter(c);
449
450                bench.iter(|| {
451                    let ab = &a & &b;
452                    let set: Vec<_> = ab.intersection(&c).cloned().collect();
453                    test::black_box(|| set);
454                });
455            }
456        }
457
458        mod union {
459            extern crate test;
460            use self::test::Bencher;
461
462            #[bench]
463            fn two_slices_big(bench: &mut Bencher) {
464                use std::collections::BTreeSet;
465                use std::iter::FromIterator;
466
467                let a: Vec<_> = (0..100).collect();
468                let b: Vec<_> = (1..101).collect();
469
470                let a = BTreeSet::from_iter(a);
471                let b = BTreeSet::from_iter(b);
472
473                bench.iter(|| {
474                    let set: Vec<_> = a.union(&b).cloned().collect();
475                    test::black_box(|| set);
476                });
477            }
478
479            #[bench]
480            fn two_slices_big2(bench: &mut Bencher) {
481                use std::collections::BTreeSet;
482                use std::iter::FromIterator;
483
484                let a: Vec<_> = (0..100).collect();
485                let b: Vec<_> = (51..151).collect();
486
487                let a = BTreeSet::from_iter(a);
488                let b = BTreeSet::from_iter(b);
489
490                bench.iter(|| {
491                    let set: Vec<_> = a.union(&b).cloned().collect();
492                    test::black_box(|| set);
493                });
494            }
495
496            #[bench]
497            fn two_slices_big3(bench: &mut Bencher) {
498                use std::collections::BTreeSet;
499                use std::iter::FromIterator;
500
501                let a: Vec<_> = (0..100).collect();
502                let b: Vec<_> = (100..200).collect();
503
504                let a = BTreeSet::from_iter(a);
505                let b = BTreeSet::from_iter(b);
506
507                bench.iter(|| {
508                    let set: Vec<_> = a.union(&b).cloned().collect();
509                    test::black_box(|| set);
510                });
511            }
512
513            #[bench]
514            fn three_slices_big(bench: &mut Bencher) {
515                use std::collections::BTreeSet;
516                use std::iter::FromIterator;
517
518                let a: Vec<_> = (0..100).collect();
519                let b: Vec<_> = (1..101).collect();
520                let c: Vec<_> = (2..102).collect();
521
522                let a = BTreeSet::from_iter(a);
523                let b = BTreeSet::from_iter(b);
524                let c = BTreeSet::from_iter(c);
525
526                bench.iter(|| {
527                    let ab = &a | &b;
528                    let set: Vec<_> = ab.union(&c).cloned().collect();
529                    test::black_box(|| set);
530                });
531            }
532
533            #[bench]
534            fn three_slices_big2(bench: &mut Bencher) {
535                use std::collections::BTreeSet;
536                use std::iter::FromIterator;
537
538                let a: Vec<_> = (0..100).collect();
539                let b: Vec<_> = (34..134).collect();
540                let c: Vec<_> = (67..167).collect();
541
542                let a = BTreeSet::from_iter(a);
543                let b = BTreeSet::from_iter(b);
544                let c = BTreeSet::from_iter(c);
545
546                bench.iter(|| {
547                    let ab = &a | &b;
548                    let set: Vec<_> = ab.union(&c).cloned().collect();
549                    test::black_box(|| set);
550                });
551            }
552
553            #[bench]
554            fn three_slices_big3(bench: &mut Bencher) {
555                use std::collections::BTreeSet;
556                use std::iter::FromIterator;
557
558                let a: Vec<_> = (0..100).collect();
559                let b: Vec<_> = (100..200).collect();
560                let c: Vec<_> = (200..300).collect();
561
562                let a = BTreeSet::from_iter(a);
563                let b = BTreeSet::from_iter(b);
564                let c = BTreeSet::from_iter(c);
565
566                bench.iter(|| {
567                    let ab = &a | &b;
568                    let set: Vec<_> = ab.union(&c).cloned().collect();
569                    test::black_box(|| set);
570                });
571            }
572        }
573
574        mod symmetric_difference {
575            extern crate test;
576            use self::test::Bencher;
577
578            #[bench]
579            fn two_slices_big(bench: &mut Bencher) {
580                use std::collections::BTreeSet;
581                use std::iter::FromIterator;
582
583                let a: Vec<_> = (0..100).collect();
584                let b: Vec<_> = (1..101).collect();
585
586                let a = BTreeSet::from_iter(a);
587                let b = BTreeSet::from_iter(b);
588
589                bench.iter(|| {
590                    let set: Vec<_> = a.symmetric_difference(&b).cloned().collect();
591                    test::black_box(|| set);
592                });
593            }
594
595            #[bench]
596            fn two_slices_big2(bench: &mut Bencher) {
597                use std::collections::BTreeSet;
598                use std::iter::FromIterator;
599
600                let a: Vec<_> = (0..100).collect();
601                let b: Vec<_> = (51..151).collect();
602
603                let a = BTreeSet::from_iter(a);
604                let b = BTreeSet::from_iter(b);
605
606                bench.iter(|| {
607                    let set: Vec<_> = a.symmetric_difference(&b).cloned().collect();
608                    test::black_box(|| set);
609                });
610            }
611
612            #[bench]
613            fn two_slices_big3(bench: &mut Bencher) {
614                use std::collections::BTreeSet;
615                use std::iter::FromIterator;
616
617                let a: Vec<_> = (0..100).collect();
618                let b: Vec<_> = (100..200).collect();
619
620                let a = BTreeSet::from_iter(a);
621                let b = BTreeSet::from_iter(b);
622
623                bench.iter(|| {
624                    let set: Vec<_> = a.symmetric_difference(&b).cloned().collect();
625                    test::black_box(|| set);
626                });
627            }
628
629            #[bench]
630            fn three_slices_big(bench: &mut Bencher) {
631                use std::collections::BTreeSet;
632                use std::iter::FromIterator;
633
634                let a: Vec<_> = (0..100).collect();
635                let b: Vec<_> = (1..101).collect();
636                let c: Vec<_> = (2..102).collect();
637
638                let a = BTreeSet::from_iter(a);
639                let b = BTreeSet::from_iter(b);
640                let c = BTreeSet::from_iter(c);
641
642                bench.iter(|| {
643                    let ab = &a ^ &b;
644                    let set: Vec<_> = ab.symmetric_difference(&c).cloned().collect();
645                    test::black_box(|| set);
646                });
647            }
648
649            #[bench]
650            fn three_slices_big2(bench: &mut Bencher) {
651                use std::collections::BTreeSet;
652                use std::iter::FromIterator;
653
654                let a: Vec<_> = (0..100).collect();
655                let b: Vec<_> = (34..134).collect();
656                let c: Vec<_> = (67..167).collect();
657
658                let a = BTreeSet::from_iter(a);
659                let b = BTreeSet::from_iter(b);
660                let c = BTreeSet::from_iter(c);
661
662                bench.iter(|| {
663                    let ab = &a ^ &b;
664                    let set: Vec<_> = ab.symmetric_difference(&c).cloned().collect();
665                    test::black_box(|| set);
666                });
667            }
668
669            #[bench]
670            fn three_slices_big3(bench: &mut Bencher) {
671                use std::collections::BTreeSet;
672                use std::iter::FromIterator;
673
674                let a: Vec<_> = (0..100).collect();
675                let b: Vec<_> = (100..200).collect();
676                let c: Vec<_> = (200..300).collect();
677
678                let a = BTreeSet::from_iter(a);
679                let b = BTreeSet::from_iter(b);
680                let c = BTreeSet::from_iter(c);
681
682                bench.iter(|| {
683                    let ab = &a ^ &b;
684                    let set: Vec<_> = ab.symmetric_difference(&c).cloned().collect();
685                    test::black_box(|| set);
686                });
687            }
688        }
689    }
690
691    mod _fnv {
692        mod difference {
693            extern crate test;
694            extern crate fnv;
695            use self::test::Bencher;
696
697            #[bench]
698            fn two_slices_big(bench: &mut Bencher) {
699                use self::fnv::FnvHashSet;
700                use std::iter::FromIterator;
701
702                let a: Vec<_> = (0..100).collect();
703                let b: Vec<_> = (1..101).collect();
704
705                let a: FnvHashSet<i32> = FnvHashSet::from_iter(a);
706                let b = FnvHashSet::from_iter(b);
707
708                bench.iter(|| {
709                    let set: Vec<_> = a.difference(&b).cloned().collect();
710                    test::black_box(|| set);
711                });
712            }
713
714            #[bench]
715            fn two_slices_big2(bench: &mut Bencher) {
716                use self::fnv::FnvHashSet;
717                use std::iter::FromIterator;
718
719                let a: Vec<_> = (0..100).collect();
720                let b: Vec<_> = (51..151).collect();
721
722                let a: FnvHashSet<i32> = FnvHashSet::from_iter(a);
723                let b = FnvHashSet::from_iter(b);
724
725                bench.iter(|| {
726                    let set: Vec<_> = a.difference(&b).cloned().collect();
727                    test::black_box(|| set);
728                });
729            }
730
731            #[bench]
732            fn two_slices_big3(bench: &mut Bencher) {
733                use self::fnv::FnvHashSet;
734                use std::iter::FromIterator;
735
736                let a: Vec<_> = (0..100).collect();
737                let b: Vec<_> = (100..200).collect();
738
739                let a: FnvHashSet<i32> = FnvHashSet::from_iter(a);
740                let b = FnvHashSet::from_iter(b);
741
742                bench.iter(|| {
743                    let set: Vec<_> = a.difference(&b).cloned().collect();
744                    test::black_box(|| set);
745                });
746            }
747
748            #[bench]
749            fn three_slices_big(bench: &mut Bencher) {
750                use self::fnv::FnvHashSet;
751                use std::iter::FromIterator;
752
753                let a: Vec<_> = (0..100).collect();
754                let b: Vec<_> = (1..101).collect();
755                let c: Vec<_> = (2..102).collect();
756
757                let a: FnvHashSet<i32> = FnvHashSet::from_iter(a);
758                let b = FnvHashSet::from_iter(b);
759                let c = FnvHashSet::from_iter(c);
760
761                bench.iter(|| {
762                    let ab = &a - &b;
763                    let set: Vec<_> = ab.difference(&c).cloned().collect();
764                    test::black_box(|| set);
765                });
766            }
767
768            #[bench]
769            fn three_slices_big2(bench: &mut Bencher) {
770                use self::fnv::FnvHashSet;
771                use std::iter::FromIterator;
772
773                let a: Vec<_> = (0..100).collect();
774                let b: Vec<_> = (34..134).collect();
775                let c: Vec<_> = (67..167).collect();
776
777                let a: FnvHashSet<i32> = FnvHashSet::from_iter(a);
778                let b = FnvHashSet::from_iter(b);
779                let c = FnvHashSet::from_iter(c);
780
781                bench.iter(|| {
782                    let ab = &a - &b;
783                    let set: Vec<_> = ab.difference(&c).cloned().collect();
784                    test::black_box(|| set);
785                });
786            }
787
788            #[bench]
789            fn three_slices_big3(bench: &mut Bencher) {
790                use self::fnv::FnvHashSet;
791                use std::iter::FromIterator;
792
793                let a: Vec<_> = (0..100).collect();
794                let b: Vec<_> = (100..200).collect();
795                let c: Vec<_> = (200..300).collect();
796
797                let a: FnvHashSet<i32> = FnvHashSet::from_iter(a);
798                let b = FnvHashSet::from_iter(b);
799                let c = FnvHashSet::from_iter(c);
800
801                bench.iter(|| {
802                    let ab = &a - &b;
803                    let set: Vec<_> = ab.difference(&c).cloned().collect();
804                    test::black_box(|| set);
805                });
806            }
807        }
808
809        mod intersection {
810            extern crate test;
811            extern crate fnv;
812            use self::test::Bencher;
813
814            #[bench]
815            fn two_slices_big(bench: &mut Bencher) {
816                use self::fnv::FnvHashSet;
817                use std::iter::FromIterator;
818
819                let a: Vec<_> = (0..100).collect();
820                let b: Vec<_> = (1..101).collect();
821
822                let a: FnvHashSet<i32> = FnvHashSet::from_iter(a);
823                let b = FnvHashSet::from_iter(b);
824
825                bench.iter(|| {
826                    let set: Vec<_> = a.intersection(&b).cloned().collect();
827                    test::black_box(|| set);
828                });
829            }
830
831            #[bench]
832            fn two_slices_big2(bench: &mut Bencher) {
833                use self::fnv::FnvHashSet;
834                use std::iter::FromIterator;
835
836                let a: Vec<_> = (0..100).collect();
837                let b: Vec<_> = (51..151).collect();
838
839                let a: FnvHashSet<i32> = FnvHashSet::from_iter(a);
840                let b = FnvHashSet::from_iter(b);
841
842                bench.iter(|| {
843                    let set: Vec<_> = a.intersection(&b).cloned().collect();
844                    test::black_box(|| set);
845                });
846            }
847
848            #[bench]
849            fn two_slices_big3(bench: &mut Bencher) {
850                use self::fnv::FnvHashSet;
851                use std::iter::FromIterator;
852
853                let a: Vec<_> = (0..100).collect();
854                let b: Vec<_> = (100..200).collect();
855
856                let a: FnvHashSet<i32> = FnvHashSet::from_iter(a);
857                let b = FnvHashSet::from_iter(b);
858
859                bench.iter(|| {
860                    let set: Vec<_> = a.intersection(&b).cloned().collect();
861                    test::black_box(|| set);
862                });
863            }
864
865            #[bench]
866            fn three_slices_big(bench: &mut Bencher) {
867                use self::fnv::FnvHashSet;
868                use std::iter::FromIterator;
869
870                let a: Vec<_> = (0..100).collect();
871                let b: Vec<_> = (1..101).collect();
872                let c: Vec<_> = (2..102).collect();
873
874                let a: FnvHashSet<i32> = FnvHashSet::from_iter(a);
875                let b = FnvHashSet::from_iter(b);
876                let c = FnvHashSet::from_iter(c);
877
878                bench.iter(|| {
879                    let ab = &a & &b;
880                    let set: Vec<_> = ab.intersection(&c).cloned().collect();
881                    test::black_box(|| set);
882                });
883            }
884
885            #[bench]
886            fn three_slices_big2(bench: &mut Bencher) {
887                use self::fnv::FnvHashSet;
888                use std::iter::FromIterator;
889
890                let a: Vec<_> = (0..100).collect();
891                let b: Vec<_> = (34..134).collect();
892                let c: Vec<_> = (67..167).collect();
893
894                let a: FnvHashSet<i32> = FnvHashSet::from_iter(a);
895                let b = FnvHashSet::from_iter(b);
896                let c = FnvHashSet::from_iter(c);
897
898                bench.iter(|| {
899                    let ab = &a & &b;
900                    let set: Vec<_> = ab.intersection(&c).cloned().collect();
901                    test::black_box(|| set);
902                });
903            }
904
905            #[bench]
906            fn three_slices_big3(bench: &mut Bencher) {
907                use self::fnv::FnvHashSet;
908                use std::iter::FromIterator;
909
910                let a: Vec<_> = (0..100).collect();
911                let b: Vec<_> = (100..200).collect();
912                let c: Vec<_> = (200..300).collect();
913
914                let a: FnvHashSet<i32> = FnvHashSet::from_iter(a);
915                let b = FnvHashSet::from_iter(b);
916                let c = FnvHashSet::from_iter(c);
917
918                bench.iter(|| {
919                    let ab = &a & &b;
920                    let set: Vec<_> = ab.intersection(&c).cloned().collect();
921                    test::black_box(|| set);
922                });
923            }
924        }
925
926        mod union {
927            extern crate test;
928            extern crate fnv;
929            use self::test::Bencher;
930
931            #[bench]
932            fn two_slices_big(bench: &mut Bencher) {
933                use self::fnv::FnvHashSet;
934                use std::iter::FromIterator;
935
936                let a: Vec<_> = (0..100).collect();
937                let b: Vec<_> = (1..101).collect();
938
939                let a: FnvHashSet<i32> = FnvHashSet::from_iter(a);
940                let b = FnvHashSet::from_iter(b);
941
942                bench.iter(|| {
943                    let set: Vec<_> = a.union(&b).cloned().collect();
944                    test::black_box(|| set);
945                });
946            }
947
948            #[bench]
949            fn two_slices_big2(bench: &mut Bencher) {
950                use self::fnv::FnvHashSet;
951                use std::iter::FromIterator;
952
953                let a: Vec<_> = (0..100).collect();
954                let b: Vec<_> = (51..151).collect();
955
956                let a: FnvHashSet<i32> = FnvHashSet::from_iter(a);
957                let b = FnvHashSet::from_iter(b);
958
959                bench.iter(|| {
960                    let set: Vec<_> = a.union(&b).cloned().collect();
961                    test::black_box(|| set);
962                });
963            }
964
965            #[bench]
966            fn two_slices_big3(bench: &mut Bencher) {
967                use self::fnv::FnvHashSet;
968                use std::iter::FromIterator;
969
970                let a: Vec<_> = (0..100).collect();
971                let b: Vec<_> = (100..200).collect();
972
973                let a: FnvHashSet<i32> = FnvHashSet::from_iter(a);
974                let b = FnvHashSet::from_iter(b);
975
976                bench.iter(|| {
977                    let set: Vec<_> = a.union(&b).cloned().collect();
978                    test::black_box(|| set);
979                });
980            }
981
982            #[bench]
983            fn three_slices_big(bench: &mut Bencher) {
984                use self::fnv::FnvHashSet;
985                use std::iter::FromIterator;
986
987                let a: Vec<_> = (0..100).collect();
988                let b: Vec<_> = (1..101).collect();
989                let c: Vec<_> = (2..102).collect();
990
991                let a: FnvHashSet<i32> = FnvHashSet::from_iter(a);
992                let b = FnvHashSet::from_iter(b);
993                let c = FnvHashSet::from_iter(c);
994
995                bench.iter(|| {
996                    let ab = &a | &b;
997                    let set: Vec<_> = ab.union(&c).cloned().collect();
998                    test::black_box(|| set);
999                });
1000            }
1001
1002            #[bench]
1003            fn three_slices_big2(bench: &mut Bencher) {
1004                use self::fnv::FnvHashSet;
1005                use std::iter::FromIterator;
1006
1007                let a: Vec<_> = (0..100).collect();
1008                let b: Vec<_> = (34..134).collect();
1009                let c: Vec<_> = (67..167).collect();
1010
1011                let a: FnvHashSet<i32> = FnvHashSet::from_iter(a);
1012                let b = FnvHashSet::from_iter(b);
1013                let c = FnvHashSet::from_iter(c);
1014
1015                bench.iter(|| {
1016                    let ab = &a | &b;
1017                    let set: Vec<_> = ab.union(&c).cloned().collect();
1018                    test::black_box(|| set);
1019                });
1020            }
1021
1022            #[bench]
1023            fn three_slices_big3(bench: &mut Bencher) {
1024                use self::fnv::FnvHashSet;
1025                use std::iter::FromIterator;
1026
1027                let a: Vec<_> = (0..100).collect();
1028                let b: Vec<_> = (100..200).collect();
1029                let c: Vec<_> = (200..300).collect();
1030
1031                let a: FnvHashSet<i32> = FnvHashSet::from_iter(a);
1032                let b = FnvHashSet::from_iter(b);
1033                let c = FnvHashSet::from_iter(c);
1034
1035                bench.iter(|| {
1036                    let ab = &a | &b;
1037                    let set: Vec<_> = ab.union(&c).cloned().collect();
1038                    test::black_box(|| set);
1039                });
1040            }
1041        }
1042
1043        mod symmetric_difference {
1044            extern crate test;
1045            extern crate fnv;
1046            use self::test::Bencher;
1047
1048            #[bench]
1049            fn two_slices_big(bench: &mut Bencher) {
1050                use self::fnv::FnvHashSet;
1051                use std::iter::FromIterator;
1052
1053                let a: Vec<_> = (0..100).collect();
1054                let b: Vec<_> = (1..101).collect();
1055
1056                let a: FnvHashSet<i32> = FnvHashSet::from_iter(a);
1057                let b = FnvHashSet::from_iter(b);
1058
1059                bench.iter(|| {
1060                    let set: Vec<_> = a.symmetric_difference(&b).cloned().collect();
1061                    test::black_box(|| set);
1062                });
1063            }
1064
1065            #[bench]
1066            fn two_slices_big2(bench: &mut Bencher) {
1067                use self::fnv::FnvHashSet;
1068                use std::iter::FromIterator;
1069
1070                let a: Vec<_> = (0..100).collect();
1071                let b: Vec<_> = (51..151).collect();
1072
1073                let a: FnvHashSet<i32> = FnvHashSet::from_iter(a);
1074                let b = FnvHashSet::from_iter(b);
1075
1076                bench.iter(|| {
1077                    let set: Vec<_> = a.symmetric_difference(&b).cloned().collect();
1078                    test::black_box(|| set);
1079                });
1080            }
1081
1082            #[bench]
1083            fn two_slices_big3(bench: &mut Bencher) {
1084                use self::fnv::FnvHashSet;
1085                use std::iter::FromIterator;
1086
1087                let a: Vec<_> = (0..100).collect();
1088                let b: Vec<_> = (100..200).collect();
1089
1090                let a: FnvHashSet<i32> = FnvHashSet::from_iter(a);
1091                let b = FnvHashSet::from_iter(b);
1092
1093                bench.iter(|| {
1094                    let set: Vec<_> = a.symmetric_difference(&b).cloned().collect();
1095                    test::black_box(|| set);
1096                });
1097            }
1098
1099            #[bench]
1100            fn three_slices_big(bench: &mut Bencher) {
1101                use self::fnv::FnvHashSet;
1102                use std::iter::FromIterator;
1103
1104                let a: Vec<_> = (0..100).collect();
1105                let b: Vec<_> = (1..101).collect();
1106                let c: Vec<_> = (2..102).collect();
1107
1108                let a: FnvHashSet<i32> = FnvHashSet::from_iter(a);
1109                let b = FnvHashSet::from_iter(b);
1110                let c = FnvHashSet::from_iter(c);
1111
1112                bench.iter(|| {
1113                    let ab = &a ^ &b;
1114                    let set: Vec<_> = ab.symmetric_difference(&c).cloned().collect();
1115                    test::black_box(|| set);
1116                });
1117            }
1118
1119            #[bench]
1120            fn three_slices_big2(bench: &mut Bencher) {
1121                use self::fnv::FnvHashSet;
1122                use std::iter::FromIterator;
1123
1124                let a: Vec<_> = (0..100).collect();
1125                let b: Vec<_> = (34..134).collect();
1126                let c: Vec<_> = (67..167).collect();
1127
1128                let a: FnvHashSet<i32> = FnvHashSet::from_iter(a);
1129                let b = FnvHashSet::from_iter(b);
1130                let c = FnvHashSet::from_iter(c);
1131
1132                bench.iter(|| {
1133                    let ab = &a ^ &b;
1134                    let set: Vec<_> = ab.symmetric_difference(&c).cloned().collect();
1135                    test::black_box(|| set);
1136                });
1137            }
1138
1139            #[bench]
1140            fn three_slices_big3(bench: &mut Bencher) {
1141                use self::fnv::FnvHashSet;
1142                use std::iter::FromIterator;
1143
1144                let a: Vec<_> = (0..100).collect();
1145                let b: Vec<_> = (100..200).collect();
1146                let c: Vec<_> = (200..300).collect();
1147
1148                let a: FnvHashSet<i32> = FnvHashSet::from_iter(a);
1149                let b = FnvHashSet::from_iter(b);
1150                let c = FnvHashSet::from_iter(c);
1151
1152                bench.iter(|| {
1153                    let ab = &a ^ &b;
1154                    let set: Vec<_> = ab.symmetric_difference(&c).cloned().collect();
1155                    test::black_box(|| set);
1156                });
1157            }
1158        }
1159    }
1160
1161    mod _vec {
1162        mod union {
1163            extern crate test;
1164            use self::test::Bencher;
1165
1166            fn create_vec_set<T: Ord + Clone>(slices: &[&[T]]) -> Vec<T> {
1167                let alloc = slices.iter().map(|v| v.len()).sum();
1168                let mut set = Vec::with_capacity(alloc);
1169                for slice in slices {
1170                    set.extend_from_slice(slice);
1171                }
1172                set.sort_unstable();
1173                set.dedup();
1174                set
1175            }
1176
1177            #[bench]
1178            fn two_slices_big(bench: &mut Bencher) {
1179                let a: Vec<_> = (0..100).collect();
1180                let b: Vec<_> = (1..101).collect();
1181
1182                bench.iter(|| {
1183                    let elements = create_vec_set(&[&a, &b]);
1184                    test::black_box(|| elements.len());
1185                });
1186            }
1187
1188            #[bench]
1189            fn two_slices_big2(bench: &mut Bencher) {
1190                let a: Vec<_> = (0..100).collect();
1191                let b: Vec<_> = (51..151).collect();
1192
1193                bench.iter(|| {
1194                    let elements = create_vec_set(&[&a, &b]);
1195                    test::black_box(|| elements.len());
1196                });
1197            }
1198
1199            #[bench]
1200            fn two_slices_big3(bench: &mut Bencher) {
1201                let a: Vec<_> = (0..100).collect();
1202                let b: Vec<_> = (100..200).collect();
1203
1204                bench.iter(|| {
1205                    let elements = create_vec_set(&[&a, &b]);
1206                    test::black_box(|| elements.len());
1207                });
1208            }
1209
1210            #[bench]
1211            fn three_slices_big(bench: &mut Bencher) {
1212                let a: Vec<_> = (0..100).collect();
1213                let b: Vec<_> = (1..101).collect();
1214                let c: Vec<_> = (2..102).collect();
1215
1216                bench.iter(|| {
1217                    let elements = create_vec_set(&[&a, &b, &c]);
1218                    test::black_box(|| elements.len());
1219                });
1220            }
1221
1222            #[bench]
1223            fn three_slices_big2(bench: &mut Bencher) {
1224                let a: Vec<_> = (0..100).collect();
1225                let b: Vec<_> = (34..134).collect();
1226                let c: Vec<_> = (67..167).collect();
1227
1228                bench.iter(|| {
1229                    let elements = create_vec_set(&[&a, &b, &c]);
1230                    test::black_box(|| elements.len());
1231                });
1232            }
1233
1234            #[bench]
1235            fn three_slices_big3(bench: &mut Bencher) {
1236                let a: Vec<_> = (0..100).collect();
1237                let b: Vec<_> = (100..200).collect();
1238                let c: Vec<_> = (200..300).collect();
1239
1240                bench.iter(|| {
1241                    let elements = create_vec_set(&[&a, &b, &c]);
1242                    test::black_box(|| elements.len());
1243                });
1244            }
1245        }
1246    }
1247}
sdset/lib.rs

sdset/
lib.rs
