bitarray_set/
lib.rs

1// Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
2// file at the top-level directory of this distribution and at
3// http://rust-lang.org/COPYRIGHT.
4//
5// Copyright 2016 The bit-set-array developers.
6//
7// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
8// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
9// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
10// option. This file may not be copied, modified, or distributed
11// except according to those terms.
12
13//! An implementation of a set using a bit array as an underlying
14//! representation for holding unsigned numerical elements.
15//!
16//! It should also be noted that the amount of storage necessary for holding a
17//! set of objects is proportional to the maximum of the objects when viewed
18//! as a `usize`.
19//!
20//! # Examples
21//!
22//! ```
23//! extern crate typenum;
24//! # extern crate bitarray_set;
25//! use typenum::{Unsigned, U8};
26//! use bitarray_set::BitArraySet;
27//!
28//! # fn main() {
29//! // It's a regular set
30//! let mut s = BitArraySet::<u32, U8>::new();
31//! s.insert(0);
32//! s.insert(3);
33//! s.insert(7);
34//!
35//! s.remove(7);
36//!
37//! if !s.contains(7) {
38//!     println!("There is no 7");
39//! }
40//!
41//! // Can initialize from a `BitArray`
42//! let other = BitArraySet::<u32, U8>::from_bytes(&[0b11010000]);
43//!
44//! s.union_with(&other);
45//!
46//! // Print 0, 1, 3 in some order
47//! for x in s.iter() {
48//!     println!("{}", x);
49//! }
50//!
51//! // Can convert back to a `BitArray`
52//! let bv = s.into_bit_array();
53//! assert!(bv[3]);
54//! # }
55//! ```
56
57#![cfg_attr(all(test, feature = "nightly"), feature(test))]
58#[cfg(all(test, feature = "nightly"))] extern crate test;
59#[cfg(all(test, feature = "nightly"))] extern crate rand;
60extern crate bit_vec;
61extern crate bit_array;
62extern crate typenum;
63extern crate generic_array;
64
65use bit_vec::BitBlock;
66use bit_array::{BitsIn, BitArray, Blocks};
67use std::cmp::Ordering;
68use std::cmp;
69use std::fmt;
70use std::hash;
71use std::ops::*;
72use std::iter::{self, Chain, Enumerate, FromIterator, Repeat, Skip, Take};
73use typenum::{Unsigned, NonZero};
74
75type MatchWords<'a, B> = Chain<Enumerate<Blocks<'a, B>>, Skip<Take<Enumerate<Repeat<B>>>>>;
76
77// Take two BitArray's, and return iterators of their words, where the shorter one
78// has been padded with 0's
79fn match_words<'a, 'b, B: BitsIn + BitBlock + Default, NBits: Unsigned + NonZero>(a: &'a BitArray<B, NBits>, b: &'b BitArray<B, NBits>)
80    -> (MatchWords<'a, B>, MatchWords<'b, B>)
81    where NBits: Add<<B as BitsIn>::Output>,
82    <NBits as Add<<B as BitsIn>::Output>>::Output: Sub<typenum::B1>,
83    <<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output: Div<<B as BitsIn>::Output>,
84    <<<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output as Div<<B as BitsIn>::Output>>::Output: generic_array::ArrayLength<B>
85{
86    let a_len = a.len();
87    let b_len = b.len();
88
89    // have to uselessly pretend to pad the longer one for type matching
90    if a_len < b_len {
91        (a.blocks().enumerate().chain(iter::repeat(B::zero()).enumerate().take(b_len).skip(a_len)),
92         b.blocks().enumerate().chain(iter::repeat(B::zero()).enumerate().take(0).skip(0)))
93    } else {
94        (a.blocks().enumerate().chain(iter::repeat(B::zero()).enumerate().take(0).skip(0)),
95         b.blocks().enumerate().chain(iter::repeat(B::zero()).enumerate().take(a_len).skip(b_len)))
96    }
97}
98
99pub struct BitArraySet<B: BitsIn, NBits: Unsigned + NonZero> 
100    where NBits: Add<<B as BitsIn>::Output>,
101    <NBits as Add<<B as BitsIn>::Output>>::Output: Sub<typenum::B1>,
102    <<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output: Div<<B as BitsIn>::Output>,
103    <<<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output as Div<<B as BitsIn>::Output>>::Output: generic_array::ArrayLength<B>
104{
105    bit_array: BitArray<B, NBits>,
106}
107
108impl<B: BitsIn + BitBlock + Default, NBits: Unsigned + NonZero>  Clone for BitArraySet<B, NBits> 
109    where NBits: Add<<B as BitsIn>::Output>,
110    <NBits as Add<<B as BitsIn>::Output>>::Output: Sub<typenum::B1>,
111    <<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output: Div<<B as BitsIn>::Output>,
112    <<<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output as Div<<B as BitsIn>::Output>>::Output: generic_array::ArrayLength<B>
113{
114    fn clone(&self) -> Self {
115        BitArraySet {
116            bit_array: self.bit_array.clone(),
117        }
118    }
119
120    fn clone_from(&mut self, other: &Self) {
121        self.bit_array.clone_from(&other.bit_array);
122    }
123}
124
125impl<B: BitsIn + BitBlock + Default, NBits: Unsigned + NonZero> Default for BitArraySet<B, NBits> 
126    where NBits: Add<<B as BitsIn>::Output>,
127    <NBits as Add<<B as BitsIn>::Output>>::Output: Sub<typenum::B1>,
128    <<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output: Div<<B as BitsIn>::Output>,
129    <<<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output as Div<<B as BitsIn>::Output>>::Output: generic_array::ArrayLength<B>
130 {
131    #[inline]
132    fn default() -> Self { BitArraySet { bit_array: Default::default() } }
133}
134
135impl<B: BitsIn + BitBlock + Default, NBits: Unsigned + NonZero> FromIterator<usize> for BitArraySet<B, NBits> 
136    where NBits: Add<<B as BitsIn>::Output>,
137    <NBits as Add<<B as BitsIn>::Output>>::Output: Sub<typenum::B1>,
138    <<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output: Div<<B as BitsIn>::Output>,
139    <<<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output as Div<<B as BitsIn>::Output>>::Output: generic_array::ArrayLength<B>
140{
141    fn from_iter<I: IntoIterator<Item = usize>>(iter: I) -> Self {
142        let mut ret = Self::default();
143        ret.extend(iter);
144        ret
145    }
146}
147
148impl<B: BitsIn + BitBlock + Default + BitAnd + BitOr, NBits: Unsigned + NonZero> Extend<usize> for BitArraySet<B, NBits> 
149    where NBits: Add<<B as BitsIn>::Output>,
150    <NBits as Add<<B as BitsIn>::Output>>::Output: Sub<typenum::B1>,
151    <<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output: Div<<B as BitsIn>::Output>,
152    <<<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output as Div<<B as BitsIn>::Output>>::Output: generic_array::ArrayLength<B>
153{
154    #[inline]
155    fn extend<I: IntoIterator<Item = usize>>(&mut self, iter: I) {
156        for i in iter {
157            self.insert(i);
158        }
159    }
160}
161
162impl<B: BitsIn + BitBlock + Default, NBits: Unsigned + NonZero> PartialOrd for BitArraySet<B, NBits> 
163    where NBits: Add<<B as BitsIn>::Output>,
164    <NBits as Add<<B as BitsIn>::Output>>::Output: Sub<typenum::B1>,
165    <<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output: Div<<B as BitsIn>::Output>,
166    <<<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output as Div<<B as BitsIn>::Output>>::Output: generic_array::ArrayLength<B>
167{
168    #[inline]
169    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
170        self.iter().partial_cmp(other)
171    }
172}
173
174impl<B: BitsIn + BitBlock + Default, NBits: Unsigned + NonZero> Ord for BitArraySet<B, NBits> 
175    where NBits: Add<<B as BitsIn>::Output>,
176    <NBits as Add<<B as BitsIn>::Output>>::Output: Sub<typenum::B1>,
177    <<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output: Div<<B as BitsIn>::Output>,
178    <<<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output as Div<<B as BitsIn>::Output>>::Output: generic_array::ArrayLength<B>
179{
180    #[inline]
181    fn cmp(&self, other: &Self) -> Ordering {
182        self.iter().cmp(other)
183    }
184}
185
186impl<B: BitsIn + BitBlock + Default, NBits: Unsigned + NonZero> PartialEq for BitArraySet<B, NBits> 
187    where NBits: Add<<B as BitsIn>::Output>,
188    <NBits as Add<<B as BitsIn>::Output>>::Output: Sub<typenum::B1>,
189    <<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output: Div<<B as BitsIn>::Output>,
190    <<<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output as Div<<B as BitsIn>::Output>>::Output: generic_array::ArrayLength<B>
191{
192    #[inline]
193    fn eq(&self, other: &Self) -> bool {
194        self.iter().eq(other)
195    }
196}
197
198impl<B: BitsIn + BitBlock + Default, NBits: Unsigned + NonZero> Eq for BitArraySet<B, NBits> 
199    where NBits: Add<<B as BitsIn>::Output>,
200    <NBits as Add<<B as BitsIn>::Output>>::Output: Sub<typenum::B1>,
201    <<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output: Div<<B as BitsIn>::Output>,
202    <<<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output as Div<<B as BitsIn>::Output>>::Output: generic_array::ArrayLength<B>
203{}
204
205impl<B: BitsIn + BitBlock + Default, NBits: Unsigned + NonZero> BitArraySet<B, NBits> 
206    where NBits: Add<<B as BitsIn>::Output>,
207    <NBits as Add<<B as BitsIn>::Output>>::Output: Sub<typenum::B1>,
208    <<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output: Div<<B as BitsIn>::Output>,
209    <<<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output as Div<<B as BitsIn>::Output>>::Output: generic_array::ArrayLength<B>
210{
211
212    /// Creates a new empty `BitArraySet`.
213    ///
214    /// # Examples
215    ///
216    /// ```
217    /// extern crate typenum;
218    /// # extern crate bitarray_set;
219    /// use typenum::{Unsigned, U8};
220    /// use bitarray_set::BitArraySet;
221    ///
222    /// # fn main() {
223    /// let mut s = BitArraySet::<u32, U8>::new();
224    /// # }
225    /// ```
226    #[inline]
227    pub fn new() -> Self {
228        Self::default()
229    }
230
231    /// Creates a new `BitArraySet` from the given bit array.
232    ///
233    /// # Examples
234    ///
235    /// ```
236    /// extern crate typenum;
237    /// extern crate bit_array;
238    /// extern crate bitarray_set;
239    /// use typenum::{Unsigned, U8};
240    /// use bit_array::BitArray;
241    /// use bitarray_set::BitArraySet;
242    ///
243    /// fn main() {
244    ///     let bv = BitArray::<u32, U8>::from_bytes(&[0b01100000]);
245    ///     let s = BitArraySet::from_bit_array(bv);
246    ///
247    ///     // Print 1, 2 in arbitrary order
248    ///     for x in s.iter() {
249    ///         println!("{}", x);
250    ///     }
251    /// }
252    /// ```
253    #[inline]
254    pub fn from_bit_array(bit_array: BitArray<B, NBits>) -> Self {
255        BitArraySet { bit_array: bit_array }
256    }
257
258    pub fn from_bytes(bytes: &[u8]) -> Self {
259        BitArraySet { bit_array: BitArray::from_bytes(bytes) }
260    }
261
262    /// Consumes this set to return the underlying bit array.
263    ///
264    /// # Examples
265    ///
266    /// ```
267    /// extern crate typenum;
268    /// # extern crate bitarray_set;
269    /// use typenum::{Unsigned, U8};
270    /// use bitarray_set::BitArraySet;
271    ///
272    /// # fn main() {
273    /// let mut s = BitArraySet::<u32, U8>::new();
274    /// s.insert(0);
275    /// s.insert(3);
276    ///
277    /// let bv = s.into_bit_array();
278    /// assert!(bv[0]);
279    /// assert!(bv[3]);
280    /// # }
281    /// ```
282    #[inline]
283    pub fn into_bit_array(self) -> BitArray<B, NBits> {
284        self.bit_array
285    }
286
287    /// Returns a reference to the underlying bit array.
288    ///
289    /// # Examples
290    ///
291    /// ```
292    /// extern crate typenum;
293    /// # extern crate bitarray_set;
294    /// use typenum::{Unsigned, U8};
295    /// use bitarray_set::BitArraySet;
296    ///
297    /// # fn main() {
298    /// let mut s = BitArraySet::<u32, U8>::new();
299    /// s.insert(0);
300    ///
301    /// let bv = s.get_ref();
302    /// assert_eq!(bv[0], true);
303    /// # }
304    /// ```
305    #[inline]
306    pub fn get_ref(&self) -> &BitArray<B, NBits> {
307        &self.bit_array
308    }
309
310    #[inline]
311    fn other_op<F>(&mut self, other: &Self, mut f: F) where F: FnMut(B, B) -> B {
312        // Unwrap BitArrays
313        let self_bit_array = &mut self.bit_array;
314        let other_bit_array = &other.bit_array;
315
316        // virtually pad other with 0's for equal lengths
317        let other_words = {
318            let (_, result) = match_words(self_bit_array, other_bit_array);
319            result
320        };
321
322        // Apply values found in other
323        for (i, w) in other_words {
324            let old = self_bit_array.storage()[i];
325            let new = f(old, w);
326            unsafe {
327                self_bit_array.storage_mut()[i] = new;
328            }
329        }
330    }
331
332    /// Iterator over each usize stored in the `BitArraySet`.
333    ///
334    /// # Examples
335    ///
336    /// ```
337    /// extern crate typenum;
338    /// # extern crate bitarray_set;
339    /// use typenum::{Unsigned, U8};
340    /// use bitarray_set::BitArraySet;
341    ///
342    /// # fn main() {
343    /// let s = BitArraySet::<u32, U8>::from_bytes(&[0b01001010]);
344    ///
345    /// // Print 1, 4, 6 in arbitrary order
346    /// for x in s.iter() {
347    ///     println!("{}", x);
348    /// }
349    /// # }
350    /// ```
351    #[inline]
352    pub fn iter(&self) -> Iter<B> {
353        Iter(BlockIter::from_blocks(self.bit_array.blocks()))
354    }
355
356    /// Iterator over each usize stored in `self` union `other`.
357    /// See [union_with](#method.union_with) for an efficient in-place version.
358    ///
359    /// # Examples
360    ///
361    /// ```
362    /// extern crate typenum;
363    /// # extern crate bitarray_set;
364    /// use typenum::{Unsigned, U8};
365    /// use bitarray_set::BitArraySet;
366    ///
367    /// # fn main() {
368    /// let a = BitArraySet::<u32, U8>::from_bytes(&[0b01101000]);
369    /// let b = BitArraySet::<u32, U8>::from_bytes(&[0b10100000]);
370    ///
371    /// // Print 0, 1, 2, 4 in arbitrary order
372    /// for x in a.union(&b) {
373    ///     println!("{}", x);
374    /// }
375    /// # }
376    /// ```
377    #[inline]
378    pub fn union<'a>(&'a self, other: &'a Self) -> Union<'a, B> {
379        fn or<B: BitBlock>(w1: B, w2: B) -> B { w1 | w2 }
380
381        Union(BlockIter::from_blocks(TwoBitPositions {
382            set: self.bit_array.blocks(),
383            other: other.bit_array.blocks(),
384            merge: or,
385        }))
386    }
387
388    /// Iterator over each usize stored in `self` intersect `other`.
389    /// See [intersect_with](#method.intersect_with) for an efficient in-place version.
390    ///
391    /// # Examples
392    ///
393    /// ```
394    /// extern crate typenum;
395    /// # extern crate bitarray_set;
396    /// use typenum::{Unsigned, U8};
397    /// use bitarray_set::BitArraySet;
398    ///
399    /// # fn main() {
400    /// let a = BitArraySet::<u32, U8>::from_bytes(&[0b01101000]);
401    /// let b = BitArraySet::<u32, U8>::from_bytes(&[0b10100000]);
402    ///
403    /// // Print 2
404    /// for x in a.intersection(&b) {
405    ///     println!("{}", x);
406    /// }
407    /// # }
408    /// ```
409    #[inline]
410    pub fn intersection<'a>(&'a self, other: &'a Self) -> Intersection<'a, B> {
411        fn bitand<B: BitBlock>(w1: B, w2: B) -> B { w1 & w2 }
412        let min = cmp::min(self.bit_array.len(), other.bit_array.len());
413
414        Intersection(BlockIter::from_blocks(TwoBitPositions {
415            set: self.bit_array.blocks(),
416            other: other.bit_array.blocks(),
417            merge: bitand,
418        }).take(min))
419    }
420
421    /// Iterator over each usize stored in the `self` setminus `other`.
422    /// See [difference_with](#method.difference_with) for an efficient in-place version.
423    ///
424    /// # Examples
425    ///
426    /// ```
427    /// extern crate typenum;
428    /// # extern crate bitarray_set;
429    /// use typenum::{Unsigned, U8};
430    /// use bitarray_set::BitArraySet;
431    ///
432    /// # fn main() {
433    /// let a = BitArraySet::<u32, U8>::from_bytes(&[0b01101000]);
434    /// let b = BitArraySet::<u32, U8>::from_bytes(&[0b10100000]);
435    ///
436    /// // Print 1, 4 in arbitrary order
437    /// for x in a.difference(&b) {
438    ///     println!("{}", x);
439    /// }
440    ///
441    /// // Note that difference is not symmetric,
442    /// // and `b - a` means something else.
443    /// // This prints 0
444    /// for x in b.difference(&a) {
445    ///     println!("{}", x);
446    /// }
447    /// # }
448    /// ```
449    #[inline]
450    pub fn difference<'a>(&'a self, other: &'a Self) -> Difference<'a, B> {
451        fn diff<B: BitBlock>(w1: B, w2: B) -> <B as std::ops::BitAnd>::Output { w1 & !w2 }
452
453        Difference(BlockIter::from_blocks(TwoBitPositions {
454            set: self.bit_array.blocks(),
455            other: other.bit_array.blocks(),
456            merge: diff,
457        }))
458    }
459
460    /// Iterator over each usize stored in the symmetric difference of `self` and `other`.
461    /// See [symmetric_difference_with](#method.symmetric_difference_with) for
462    /// an efficient in-place version.
463    ///
464    /// # Examples
465    ///
466    /// ```
467    /// extern crate typenum;
468    /// # extern crate bitarray_set;
469    /// use typenum::{Unsigned, U8};
470    /// use bitarray_set::BitArraySet;
471    ///
472    /// # fn main() {
473    /// let a = BitArraySet::<u32, U8>::from_bytes(&[0b01101000]);
474    /// let b = BitArraySet::<u32, U8>::from_bytes(&[0b10100000]);
475    ///
476    /// // Print 0, 1, 4 in arbitrary order
477    /// for x in a.symmetric_difference(&b) {
478    ///     println!("{}", x);
479    /// }
480    /// # }
481    /// ```
482    #[inline]
483    pub fn symmetric_difference<'a>(&'a self, other: &'a Self) -> SymmetricDifference<'a, B> {
484        fn bitxor<B: BitBlock>(w1: B, w2: B) -> B { w1 ^ w2 }
485
486        SymmetricDifference(BlockIter::from_blocks(TwoBitPositions {
487            set: self.bit_array.blocks(),
488            other: other.bit_array.blocks(),
489            merge: bitxor,
490        }))
491    }
492
493    /// Unions in-place with the specified other bit array.
494    ///
495    /// # Examples
496    ///
497    /// ```
498    /// extern crate typenum;
499    /// # extern crate bitarray_set;
500    /// use typenum::{Unsigned, U8};
501    /// use bitarray_set::BitArraySet;
502    ///
503    /// # fn main() {
504    /// let a   = 0b01101000;
505    /// let b   = 0b10100000;
506    /// let res = 0b11101000;
507    ///
508    /// let mut a = BitArraySet::<u32, U8>::from_bytes(&[a]);
509    /// let b = BitArraySet::<u32, U8>::from_bytes(&[b]);
510    /// let res = BitArraySet::<u32, U8>::from_bytes(&[res]);
511    ///
512    /// a.union_with(&b);
513    /// assert_eq!(a, res);
514    /// # }
515    /// ```
516    #[inline]
517    pub fn union_with(&mut self, other: &Self) {
518        self.other_op(other, |w1, w2| w1 | w2);
519    }
520
521    /// Intersects in-place with the specified other bit array.
522    ///
523    /// # Examples
524    ///
525    /// ```
526    /// extern crate typenum;
527    /// # extern crate bitarray_set;
528    /// use typenum::{Unsigned, U8};
529    /// use bitarray_set::BitArraySet;
530    ///
531    /// # fn main() {
532    /// let a   = 0b01101000;
533    /// let b   = 0b10100000;
534    /// let res = 0b00100000;
535    ///
536    /// let mut a = BitArraySet::<u32, U8>::from_bytes(&[a]);
537    /// let b = BitArraySet::<u32, U8>::from_bytes(&[b]);
538    /// let res = BitArraySet::<u32, U8>::from_bytes(&[res]);
539    ///
540    /// a.intersect_with(&b);
541    /// assert_eq!(a, res);
542    /// # }
543    /// ```
544    #[inline]
545    pub fn intersect_with(&mut self, other: &Self) {
546        self.other_op(other, |w1, w2| w1 & w2);
547    }
548
549    /// Makes this bit array the difference with the specified other bit array
550    /// in-place.
551    ///
552    /// # Examples
553    ///
554    /// ```
555    /// extern crate typenum;
556    /// # extern crate bitarray_set;
557    /// use typenum::{Unsigned, U8};
558    /// use bitarray_set::BitArraySet;
559    ///
560    /// # fn main() {
561    /// let a   = 0b01101000;
562    /// let b   = 0b10100000;
563    /// let a_b = 0b01001000; // a - b
564    /// let b_a = 0b10000000; // b - a
565    ///
566    /// let mut bva = BitArraySet::<u32, U8>::from_bytes(&[a]);
567    /// let bvb = BitArraySet::<u32, U8>::from_bytes(&[b]);
568    /// let bva_b = BitArraySet::<u32, U8>::from_bytes(&[a_b]);
569    /// let bvb_a = BitArraySet::<u32, U8>::from_bytes(&[b_a]);
570    ///
571    /// bva.difference_with(&bvb);
572    /// assert_eq!(bva, bva_b);
573    ///
574    /// let bva = BitArraySet::<u32, U8>::from_bytes(&[a]);
575    /// let mut bvb = BitArraySet::<u32, U8>::from_bytes(&[b]);
576    ///
577    /// bvb.difference_with(&bva);
578    /// assert_eq!(bvb, bvb_a);
579    /// # }
580    /// ```
581    #[inline]
582    pub fn difference_with(&mut self, other: &Self) {
583        self.other_op(other, |w1, w2| w1 & !w2);
584    }
585
586    /// Makes this bit array the symmetric difference with the specified other
587    /// bit array in-place.
588    ///
589    /// # Examples
590    ///
591    /// ```
592    /// extern crate typenum;
593    /// # extern crate bitarray_set;
594    /// use typenum::{Unsigned, U8};
595    /// use bitarray_set::BitArraySet;
596    ///
597    /// # fn main() {
598    /// let a   = 0b01101000;
599    /// let b   = 0b10100000;
600    /// let res = 0b11001000;
601    ///
602    /// let mut a = BitArraySet::<u32, U8>::from_bytes(&[a]);
603    /// let b = BitArraySet::<u32, U8>::from_bytes(&[b]);
604    /// let res = BitArraySet::<u32, U8>::from_bytes(&[res]);
605    ///
606    /// a.symmetric_difference_with(&b);
607    /// assert_eq!(a, res);
608    /// # }
609    /// ```
610    #[inline]
611    pub fn symmetric_difference_with(&mut self, other: &Self) {
612        self.other_op(other, |w1, w2| w1 ^ w2);
613    }
614
615    /// Returns the number of set bits in this set.
616    #[inline]
617    pub fn len(&self) -> usize  {
618        self.bit_array.blocks().fold(0, |acc, n| acc + n.count_ones() as usize)
619    }
620
621    /// Returns whether there are no bits set in this set
622    #[inline]
623    pub fn is_empty(&self) -> bool {
624        self.bit_array.none()
625    }
626
627    /// Clears all bits in this set
628    #[inline]
629    pub fn clear(&mut self) {
630        self.bit_array.clear();
631    }
632
633    /// Returns `true` if this set contains the specified integer.
634    #[inline]
635    pub fn contains(&self, value: usize) -> bool {
636        let bit_array = &self.bit_array;
637        value < bit_array.len() && bit_array[value]
638    }
639
640    /// Returns `true` if the set has no elements in common with `other`.
641    /// This is equivalent to checking for an empty intersection.
642    #[inline]
643    pub fn is_disjoint(&self, other: &Self) -> bool {
644        self.intersection(other).next().is_none()
645    }
646
647    /// Returns `true` if the set is a subset of another.
648    #[inline]
649    pub fn is_subset(&self, other: &Self) -> bool {
650        let self_bit_array = &self.bit_array;
651        let other_bit_array = &other.bit_array;
652
653        // Check that `self` intersect `other` is self
654        self_bit_array.blocks().zip(other_bit_array.blocks()).all(|(w1, w2)| w1 & w2 == w1)
655    }
656
657    /// Returns `true` if the set is a superset of another.
658    #[inline]
659    pub fn is_superset(&self, other: &Self) -> bool {
660        other.is_subset(self)
661    }
662
663    /// Adds a value to the set. Returns `true` if the value was not already
664    /// present in the set.
665    pub fn insert(&mut self, value: usize) -> bool {
666        assert!(value <= NBits::to_usize(), "BitArraySet can only handle {:?} entries. Insert to {:?} requested.", NBits::to_usize(), value);
667        if self.contains(value) {
668            return false;
669        }
670
671        self.bit_array.set(value, true);
672        return true;
673    }
674
675    /// Removes a value from the set. Returns `true` if the value was
676    /// present in the set.
677    pub fn remove(&mut self, value: usize) -> bool {
678        if !self.contains(value) {
679            return false;
680        }
681
682        self.bit_array.set(value, false);
683
684        return true;
685    }
686}
687
688impl<B: BitsIn + BitBlock + Default, NBits: Unsigned + NonZero> fmt::Debug for BitArraySet<B, NBits> 
689    where NBits: Add<<B as BitsIn>::Output>,
690    <NBits as Add<<B as BitsIn>::Output>>::Output: Sub<typenum::B1>,
691    <<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output: Div<<B as BitsIn>::Output>,
692    <<<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output as Div<<B as BitsIn>::Output>>::Output: generic_array::ArrayLength<B>
693{
694    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
695        fmt.debug_set().entries(self).finish()
696    }
697}
698
699impl<B: BitsIn + BitBlock + Default, NBits: Unsigned + NonZero> hash::Hash for BitArraySet<B, NBits> 
700    where NBits: Add<<B as BitsIn>::Output>,
701    <NBits as Add<<B as BitsIn>::Output>>::Output: Sub<typenum::B1>,
702    <<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output: Div<<B as BitsIn>::Output>,
703    <<<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output as Div<<B as BitsIn>::Output>>::Output: generic_array::ArrayLength<B>
704{
705    fn hash<H: hash::Hasher>(&self, state: &mut H) {
706        for pos in self {
707            pos.hash(state);
708        }
709    }
710}
711
712#[derive(Clone)]
713struct BlockIter<T, B> {
714    head: B,
715    head_offset: usize,
716    tail: T,
717}
718
719impl<T, B: BitBlock> BlockIter<T, B> where T: Iterator<Item=B> {
720    fn from_blocks(mut blocks: T) -> BlockIter<T, B> {
721        let h = blocks.next().unwrap_or(B::zero());
722        BlockIter {tail: blocks, head: h, head_offset: 0}
723    }
724}
725
726/// An iterator combining two `BitArraySet` iterators.
727#[derive(Clone)]
728struct TwoBitPositions<'a, B: 'a> {
729    set: Blocks<'a, B>,
730    other: Blocks<'a, B>,
731    merge: fn(B, B) -> B,
732}
733
734/// An iterator for `BitArraySet`.
735#[derive(Clone)]
736pub struct Iter<'a, B: 'a>(BlockIter<Blocks<'a, B>, B>);
737#[derive(Clone)]
738pub struct Union<'a, B: 'a>(BlockIter<TwoBitPositions<'a, B>, B>);
739#[derive(Clone)]
740pub struct Intersection<'a, B: 'a>(Take<BlockIter<TwoBitPositions<'a, B>, B>>);
741#[derive(Clone)]
742pub struct Difference<'a, B: 'a>(BlockIter<TwoBitPositions<'a, B>, B>);
743#[derive(Clone)]
744pub struct SymmetricDifference<'a, B: 'a>(BlockIter<TwoBitPositions<'a, B>, B>);
745
746impl<'a, T, B: BitBlock> Iterator for BlockIter<T, B> where T: Iterator<Item=B> {
747    type Item = usize;
748
749    fn next(&mut self) -> Option<usize> {
750        while self.head == B::zero() {
751            match self.tail.next() {
752                Some(w) => self.head = w,
753                None => return None
754            }
755            self.head_offset += B::bits();
756        }
757
758        // from the current block, isolate the
759        // LSB and subtract 1, producing k:
760        // a block with a number of set bits
761        // equal to the index of the LSB
762        let k = (self.head & (!self.head + B::one())) - B::one();
763        // update block, removing the LSB
764        self.head = self.head & (self.head - B::one());
765        // return offset + (index of LSB)
766        Some(self.head_offset + (B::count_ones(k) as usize))
767    }
768
769    #[inline]
770    fn size_hint(&self) -> (usize, Option<usize>) {
771        match self.tail.size_hint() {
772            (_, Some(h)) => (0, Some(1 + h * B::bits())),
773            _ => (0, None)
774        }
775    }
776}
777
778impl<'a, B: BitBlock> Iterator for TwoBitPositions<'a, B> {
779    type Item = B;
780
781    fn next(&mut self) -> Option<B> {
782        match (self.set.next(), self.other.next()) {
783            (Some(a), Some(b)) => Some((self.merge)(a, b)),
784            (Some(a), None) => Some((self.merge)(a, B::zero())),
785            (None, Some(b)) => Some((self.merge)(B::zero(), b)),
786            _ => return None
787        }
788    }
789
790    #[inline]
791    fn size_hint(&self) -> (usize, Option<usize>) {
792        let (a, au) = self.set.size_hint();
793        let (b, bu) = self.other.size_hint();
794
795        let upper = match (au, bu) {
796            (Some(au), Some(bu)) => Some(cmp::max(au, bu)),
797            _ => None
798        };
799
800        (cmp::max(a, b), upper)
801    }
802}
803
804impl<'a, B: BitBlock> Iterator for Iter<'a, B> {
805    type Item = usize;
806
807    #[inline] fn next(&mut self) -> Option<usize> { self.0.next() }
808    #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
809}
810
811impl<'a, B: BitBlock> Iterator for Union<'a, B> {
812    type Item = usize;
813
814    #[inline] fn next(&mut self) -> Option<usize> { self.0.next() }
815    #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
816}
817
818impl<'a, B: BitBlock> Iterator for Intersection<'a, B> {
819    type Item = usize;
820
821    #[inline] fn next(&mut self) -> Option<usize> { self.0.next() }
822    #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
823}
824
825impl<'a, B: BitBlock> Iterator for Difference<'a, B> {
826    type Item = usize;
827
828    #[inline] fn next(&mut self) -> Option<usize> { self.0.next() }
829    #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
830}
831
832impl<'a, B: BitBlock> Iterator for SymmetricDifference<'a, B> {
833    type Item = usize;
834
835    #[inline] fn next(&mut self) -> Option<usize> { self.0.next() }
836    #[inline] fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
837}
838
839impl<'a, B: BitsIn + BitBlock + Default, NBits: Unsigned + NonZero> IntoIterator for &'a BitArraySet<B, NBits> 
840    where NBits: Add<<B as BitsIn>::Output>,
841    <NBits as Add<<B as BitsIn>::Output>>::Output: Sub<typenum::B1>,
842    <<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output: Div<<B as BitsIn>::Output>,
843    <<<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output as Div<<B as BitsIn>::Output>>::Output: generic_array::ArrayLength<B>
844{
845    type Item = usize;
846    type IntoIter = Iter<'a, B>;
847
848    fn into_iter(self) -> Iter<'a, B> {
849        self.iter()
850    }
851}
852
853impl<B: BitsIn + BitBlock + Default, NBits: Unsigned + NonZero> Not for BitArraySet<B, NBits>
854    where NBits: Add<<B as BitsIn>::Output>,
855          <NBits as Add<<B as BitsIn>::Output>>::Output: Sub<typenum::B1>,
856          <<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output: Div<<B as BitsIn>::Output>,
857          <<<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output as Div<<B as BitsIn>::Output>>::Output: generic_array::ArrayLength<B>
858{
859    type Output = BitArraySet<B, NBits>;
860
861    fn not(self) -> Self::Output {
862        let mut not = self.clone();
863        not.bit_array.negate();
864        not
865    }
866}
867
868impl<B: BitsIn + BitBlock + Default, NBits: Unsigned + NonZero> BitAnd for BitArraySet<B, NBits>
869    where NBits: Add<<B as BitsIn>::Output>,
870          <NBits as Add<<B as BitsIn>::Output>>::Output: Sub<typenum::B1>,
871          <<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output: Div<<B as BitsIn>::Output>,
872          <<<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output as Div<<B as BitsIn>::Output>>::Output: generic_array::ArrayLength<B>
873{
874    type Output = BitArraySet<B, NBits>;
875
876    fn bitand(self, rhs: Self) -> Self::Output {
877        let mut and = self.clone();
878        and.intersect_with(&rhs);
879        and
880    }
881
882}
883
884impl<B: BitsIn + BitBlock + Default, NBits: Unsigned + NonZero> BitAndAssign for BitArraySet<B, NBits>
885    where NBits: Add<<B as BitsIn>::Output>,
886          <NBits as Add<<B as BitsIn>::Output>>::Output: Sub<typenum::B1>,
887          <<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output: Div<<B as BitsIn>::Output>,
888          <<<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output as Div<<B as BitsIn>::Output>>::Output: generic_array::ArrayLength<B>
889{
890    fn bitand_assign(&mut self, rhs: Self) {
891        self.intersect_with(&rhs);
892    }
893
894}
895
896impl<B: BitsIn + BitBlock + Default, NBits: Unsigned + NonZero> BitOr for BitArraySet<B, NBits>
897    where NBits: Add<<B as BitsIn>::Output>,
898          <NBits as Add<<B as BitsIn>::Output>>::Output: Sub<typenum::B1>,
899          <<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output: Div<<B as BitsIn>::Output>,
900          <<<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output as Div<<B as BitsIn>::Output>>::Output: generic_array::ArrayLength<B>
901{
902    type Output = BitArraySet<B, NBits>;
903
904    fn bitor(self, rhs: Self) -> Self::Output {
905        let mut or = self.clone();
906        or.union_with(&rhs);
907        or
908    }
909
910}
911
912impl<B: BitsIn + BitBlock + Default, NBits: Unsigned + NonZero> BitOrAssign for BitArraySet<B, NBits>
913    where NBits: Add<<B as BitsIn>::Output>,
914          <NBits as Add<<B as BitsIn>::Output>>::Output: Sub<typenum::B1>,
915          <<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output: Div<<B as BitsIn>::Output>,
916          <<<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output as Div<<B as BitsIn>::Output>>::Output: generic_array::ArrayLength<B>
917{
918    fn bitor_assign(&mut self, rhs: Self) {
919        self.union_with(&rhs);
920    }
921
922}
923
924impl<B: BitsIn + BitBlock + Default, NBits: Unsigned + NonZero> BitXor for BitArraySet<B, NBits>
925    where NBits: Add<<B as BitsIn>::Output>,
926          <NBits as Add<<B as BitsIn>::Output>>::Output: Sub<typenum::B1>,
927          <<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output: Div<<B as BitsIn>::Output>,
928          <<<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output as Div<<B as BitsIn>::Output>>::Output: generic_array::ArrayLength<B>
929{
930    type Output = BitArraySet<B, NBits>;
931
932    fn bitxor(self, rhs: Self) -> Self::Output {
933        let mut xor = self.clone();
934        xor.symmetric_difference_with(&rhs);
935        xor
936    }
937
938}
939
940impl<B: BitsIn + BitBlock + Default, NBits: Unsigned + NonZero> BitXorAssign for BitArraySet<B, NBits>
941    where NBits: Add<<B as BitsIn>::Output>,
942          <NBits as Add<<B as BitsIn>::Output>>::Output: Sub<typenum::B1>,
943          <<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output: Div<<B as BitsIn>::Output>,
944          <<<NBits as Add<<B as BitsIn>::Output>>::Output as Sub<typenum::B1>>::Output as Div<<B as BitsIn>::Output>>::Output: generic_array::ArrayLength<B>
945{
946    fn bitxor_assign(&mut self, rhs: Self) {
947        self.symmetric_difference_with(&rhs);
948    }
949
950}
951
952#[cfg(test)]
953mod tests {
954    use std::cmp::Ordering::{Equal, Greater, Less};
955    use super::BitArraySet;
956    use bit_array::BitArray;
957    use typenum::{U4, U8, U10, U51, U64, U100, U104, U152, U201, U221, U401, U501, U1001};
958
959    #[test]
960    fn test_bit_set_show() {
961        let mut s = BitArraySet::<u32, U51>::new();
962        s.insert(1);
963        s.insert(10);
964        s.insert(50);
965        s.insert(2);
966        assert_eq!("{1, 2, 10, 50}", format!("{:?}", s));
967    }
968
969    #[test]
970    fn test_bit_set_from_usizes() {
971        let usizes = vec![0, 2, 2, 3];
972        let a: BitArraySet<u32, U4> = usizes.into_iter().collect();
973        let mut b = BitArraySet::new();
974        b.insert(0);
975        b.insert(2);
976        b.insert(3);
977        assert_eq!(a, b);
978    }
979
980    #[test]
981    fn test_bit_set_iterator() {
982        let usizes = vec![0, 2, 2, 3];
983        let bit_array: BitArraySet<u32, U4> = usizes.into_iter().collect();
984
985        let idxs: Vec<_> = bit_array.iter().collect();
986        assert_eq!(idxs, [0, 2, 3]);
987
988        let long: BitArraySet<u32, U1001> = (0..1000).filter(|&n| n % 2 == 0).collect();
989        let real: Vec<_> = (0..1000/2).map(|x| x*2).collect();
990
991        let idxs: Vec<_> = long.iter().collect();
992        assert_eq!(idxs, real);
993    }
994
995    #[test]
996    fn test_bit_set_frombit_array_init() {
997        let bools = [true, false];
998        for &b in &bools {
999            let bitset_10 = BitArraySet::from_bit_array(BitArray::<u32, U10>::from_elem(b));
1000            let bitset_64 = BitArraySet::from_bit_array(BitArray::<u32, U64>::from_elem(b));
1001            let bitset_100 = BitArraySet::from_bit_array(BitArray::<u32, U100>::from_elem(b));
1002
1003            assert_eq!(bitset_10.contains(1), b);
1004            assert_eq!(bitset_10.contains((9)), b);
1005            assert!(!bitset_10.contains(10));
1006
1007            assert_eq!(bitset_64.contains(1), b);
1008            assert_eq!(bitset_64.contains((63)), b);
1009            assert!(!bitset_64.contains(64));
1010
1011            assert_eq!(bitset_100.contains(1), b);
1012            assert_eq!(bitset_100.contains((99)), b);
1013            assert!(!bitset_100.contains(100));
1014        }
1015    }
1016
1017    #[test]
1018    fn test_bit_array_masking() {
1019        let b: BitArray<u32, U152> = BitArray::from_elem(true);
1020        let mut bs = BitArraySet::from_bit_array(b);
1021        bs.remove(140);
1022        bs.remove(149);
1023        bs.remove(150);
1024        bs.remove(151);
1025        assert!(bs.contains(139));
1026        assert!(!bs.contains(140));
1027        assert!(bs.insert(150));
1028        assert!(!bs.contains(140));
1029        assert!(!bs.contains(149));
1030        assert!(bs.contains(150));
1031        assert!(!bs.contains(151));
1032    }
1033
1034    #[test]
1035    fn test_bit_set_basic() {
1036        let mut b = BitArraySet::<u32, U401>::new();
1037        assert!(b.insert(3));
1038        assert!(!b.insert(3));
1039        assert!(b.contains(3));
1040        assert!(b.insert(4));
1041        assert!(!b.insert(4));
1042        assert!(b.contains(3));
1043        assert!(b.insert(400));
1044        assert!(!b.insert(400));
1045        assert!(b.contains(400));
1046        assert_eq!(b.len(), 3);
1047    }
1048
1049    #[test]
1050    fn test_bit_set_intersection() {
1051        let mut a = BitArraySet::<u32, U104>::new();
1052        let mut b = BitArraySet::<u32, U104>::new();
1053
1054        assert!(a.insert(11));
1055        assert!(a.insert(1));
1056        assert!(a.insert(3));
1057        assert!(a.insert(77));
1058        assert!(a.insert(103));
1059        assert!(a.insert(5));
1060
1061        assert!(b.insert(2));
1062        assert!(b.insert(11));
1063        assert!(b.insert(77));
1064        assert!(b.insert(5));
1065        assert!(b.insert(3));
1066
1067        let expected = [3, 5, 11, 77];
1068        let actual: Vec<_> = a.intersection(&b).collect();
1069        assert_eq!(actual, expected);
1070    }
1071
1072    #[test]
1073    fn test_bit_set_difference() {
1074        let mut a = BitArraySet::<u32, U501>::new();
1075        let mut b = BitArraySet::<u32, U501>::new();
1076
1077        assert!(a.insert(1));
1078        assert!(a.insert(3));
1079        assert!(a.insert(5));
1080        assert!(a.insert(200));
1081        assert!(a.insert(500));
1082
1083        assert!(b.insert(3));
1084        assert!(b.insert(200));
1085
1086        let expected = [1, 5, 500];
1087        let actual: Vec<_> = a.difference(&b).collect();
1088        assert_eq!(actual, expected);
1089    }
1090
1091    #[test]
1092    fn test_bit_set_symmetric_difference() {
1093        let mut a = BitArraySet::<u32, U221>::new();
1094        let mut b = BitArraySet::<u32, U221>::new();
1095
1096        assert!(a.insert(1));
1097        assert!(a.insert(3));
1098        assert!(a.insert(5));
1099        assert!(a.insert(9));
1100        assert!(a.insert(11));
1101
1102        assert!(b.insert(3));
1103        assert!(b.insert(9));
1104        assert!(b.insert(14));
1105        assert!(b.insert(220));
1106
1107        let expected = [1, 5, 11, 14, 220];
1108        let actual: Vec<_> = a.symmetric_difference(&b).collect();
1109        assert_eq!(actual, expected);
1110    }
1111
1112    #[test]
1113    fn test_bit_set_union() {
1114        let mut a = BitArraySet::<u32, U201>::new();
1115        let mut b = BitArraySet::<u32, U201>::new();
1116        assert!(a.insert(1));
1117        assert!(a.insert(3));
1118        assert!(a.insert(5));
1119        assert!(a.insert(9));
1120        assert!(a.insert(11));
1121        assert!(a.insert(160));
1122        assert!(a.insert(19));
1123        assert!(a.insert(24));
1124        assert!(a.insert(200));
1125
1126        assert!(b.insert(1));
1127        assert!(b.insert(5));
1128        assert!(b.insert(9));
1129        assert!(b.insert(13));
1130        assert!(b.insert(19));
1131
1132        let expected = [1, 3, 5, 9, 11, 13, 19, 24, 160, 200];
1133        let actual: Vec<_> = a.union(&b).collect();
1134        assert_eq!(actual, expected);
1135    }
1136
1137    #[test]
1138    fn test_bit_set_subset() {
1139        let mut set1 = BitArraySet::<u32, U401>::new();
1140        let mut set2 = BitArraySet::<u32, U401>::new();
1141
1142        assert!(set1.is_subset(&set2)); //  {}  {}
1143        set2.insert(100);
1144        assert!(set1.is_subset(&set2)); //  {}  { 1 }
1145        set2.insert(200);
1146        assert!(set1.is_subset(&set2)); //  {}  { 1, 2 }
1147        set1.insert(200);
1148        assert!(set1.is_subset(&set2)); //  { 2 }  { 1, 2 }
1149        set1.insert(300);
1150        assert!(!set1.is_subset(&set2)); // { 2, 3 }  { 1, 2 }
1151        set2.insert(300);
1152        assert!(set1.is_subset(&set2)); // { 2, 3 }  { 1, 2, 3 }
1153        set2.insert(400);
1154        assert!(set1.is_subset(&set2)); // { 2, 3 }  { 1, 2, 3, 4 }
1155        set2.remove(100);
1156        assert!(set1.is_subset(&set2)); // { 2, 3 }  { 2, 3, 4 }
1157        set2.remove(300);
1158        assert!(!set1.is_subset(&set2)); // { 2, 3 }  { 2, 4 }
1159        set1.remove(300);
1160        assert!(set1.is_subset(&set2)); // { 2 }  { 2, 4 }
1161    }
1162
1163    #[test]
1164    fn test_bit_set_is_disjoint() {
1165        let a = BitArraySet::<u32, U8>::from_bytes(&[0b10100010]);
1166        let b = BitArraySet::<u32, U8>::from_bytes(&[0b01000000]);
1167        let c = BitArraySet::<u32, U8>::new();
1168        let d = BitArraySet::<u32, U8>::from_bytes(&[0b00110000]);
1169
1170        assert!(!a.is_disjoint(&d));
1171        assert!(!d.is_disjoint(&a));
1172
1173        assert!(a.is_disjoint(&b));
1174        assert!(a.is_disjoint(&c));
1175        assert!(b.is_disjoint(&a));
1176        assert!(b.is_disjoint(&c));
1177        assert!(c.is_disjoint(&a));
1178        assert!(c.is_disjoint(&b));
1179    }
1180
1181    #[test]
1182    fn test_bit_set_union_with() {
1183        //a should grow to include larger elements
1184        let mut a = BitArraySet::<u32, U8>::new();
1185        a.insert(0);
1186        let mut b = BitArraySet::<u32, U8>::new();
1187        b.insert(5);
1188        let expected = BitArraySet::<u32, U8>::from_bytes(&[0b10000100]);
1189        a.union_with(&b);
1190        assert_eq!(a, expected);
1191
1192        // Standard
1193        let mut a = BitArraySet::<u32, U8>::from_bytes(&[0b10100010]);
1194        let mut b = BitArraySet::<u32, U8>::from_bytes(&[0b01100010]);
1195        let c = a.clone();
1196        a.union_with(&b);
1197        b.union_with(&c);
1198        assert_eq!(a.len(), 4);
1199        assert_eq!(b.len(), 4);
1200    }
1201
1202    #[test]
1203    fn test_bit_set_intersect_with() {
1204        // Explicitly 0'ed bits
1205        let mut a = BitArraySet::<u32, U8>::from_bytes(&[0b10100010]);
1206        let mut b = BitArraySet::<u32, U8>::from_bytes(&[0b00000000]);
1207        let c = a.clone();
1208        a.intersect_with(&b);
1209        b.intersect_with(&c);
1210        assert!(a.is_empty());
1211        assert!(b.is_empty());
1212
1213        // Uninitialized bits should behave like 0's
1214        let mut a = BitArraySet::<u32, U8>::from_bytes(&[0b10100010]);
1215        let mut b = BitArraySet::<u32, U8>::new();
1216        let c = a.clone();
1217        a.intersect_with(&b);
1218        b.intersect_with(&c);
1219        assert!(a.is_empty());
1220        assert!(b.is_empty());
1221
1222        // Standard
1223        let mut a = BitArraySet::<u32, U8>::from_bytes(&[0b10100010]);
1224        let mut b = BitArraySet::<u32, U8>::from_bytes(&[0b01100010]);
1225        let c = a.clone();
1226        a.intersect_with(&b);
1227        b.intersect_with(&c);
1228        assert_eq!(a.len(), 2);
1229        assert_eq!(b.len(), 2);
1230    }
1231
1232    #[test]
1233    fn test_bit_set_difference_with() {
1234        // Explicitly 0'ed bits
1235        let mut a = BitArraySet::<u32, U8>::from_bytes(&[0b00000000]);
1236        let b = BitArraySet::<u32, U8>::from_bytes(&[0b10100010]);
1237        a.difference_with(&b);
1238        assert!(a.is_empty());
1239
1240        // Uninitialized bits should behave like 0's
1241        let mut a = BitArraySet::<u32, U8>::new();
1242        let b = BitArraySet::<u32, U8>::from_bytes(&[0b11111111]);
1243        a.difference_with(&b);
1244        assert!(a.is_empty());
1245
1246        // Standard
1247        let mut a = BitArraySet::<u32, U8>::from_bytes(&[0b10100010]);
1248        let mut b = BitArraySet::<u32, U8>::from_bytes(&[0b01100010]);
1249        let c = a.clone();
1250        a.difference_with(&b);
1251        b.difference_with(&c);
1252        assert_eq!(a.len(), 1);
1253        assert_eq!(b.len(), 1);
1254    }
1255
1256    #[test]
1257    fn test_bit_set_symmetric_difference_with() {
1258        //a should grow to include larger elements
1259        let mut a = BitArraySet::<u32, U8>::new();
1260        a.insert(0);
1261        a.insert(1);
1262        let mut b = BitArraySet::<u32, U8>::new();
1263        b.insert(1);
1264        b.insert(5);
1265        let expected = BitArraySet::<u32, U8>::from_bytes(&[0b10000100]);
1266        a.symmetric_difference_with(&b);
1267        assert_eq!(a, expected);
1268
1269        let mut a = BitArraySet::<u32, U8>::from_bytes(&[0b10100010]);
1270        let b = BitArraySet::<u32, U8>::new();
1271        let c = a.clone();
1272        a.symmetric_difference_with(&b);
1273        assert_eq!(a, c);
1274
1275        // Standard
1276        let mut a = BitArraySet::<u32, U8>::from_bytes(&[0b11100010]);
1277        let mut b = BitArraySet::<u32, U8>::from_bytes(&[0b01101010]);
1278        let c = a.clone();
1279        a.symmetric_difference_with(&b);
1280        b.symmetric_difference_with(&c);
1281        assert_eq!(a.len(), 2);
1282        assert_eq!(b.len(), 2);
1283    }
1284
1285    #[test]
1286    fn test_bit_set_eq() {
1287        let a = BitArraySet::<u32, U8>::from_bytes(&[0b10100010]);
1288        let b = BitArraySet::<u32, U8>::from_bytes(&[0b00000000]);
1289        let c = BitArraySet::<u32, U8>::new();
1290
1291        assert!(a == a);
1292        assert!(a != b);
1293        assert!(a != c);
1294        assert!(b == b);
1295        assert!(b == c);
1296        assert!(c == c);
1297    }
1298
1299    #[test]
1300    fn test_bit_set_cmp() {
1301        let a = BitArraySet::<u32, U8>::from_bytes(&[0b10100010]);
1302        let b = BitArraySet::<u32, U8>::from_bytes(&[0b00000000]);
1303        let c = BitArraySet::<u32, U8>::new();
1304
1305        assert_eq!(a.cmp(&b), Greater);
1306        assert_eq!(a.cmp(&c), Greater);
1307        assert_eq!(b.cmp(&a), Less);
1308        assert_eq!(b.cmp(&c), Equal);
1309        assert_eq!(c.cmp(&a), Less);
1310        assert_eq!(c.cmp(&b), Equal);
1311    }
1312
1313    #[test]
1314    fn test_bit_array_remove() {
1315        let mut a = BitArraySet::<u32, U1001>::new();
1316
1317        assert!(a.insert(1));
1318        assert!(a.remove(1));
1319
1320        assert!(a.insert(100));
1321        assert!(a.remove(100));
1322
1323        assert!(a.insert(1000));
1324        assert!(a.remove(1000));
1325    }
1326
1327    #[test]
1328    fn test_bit_array_clone() {
1329        let mut a = BitArraySet::<u32, U1001>::new();
1330
1331        assert!(a.insert(1));
1332        assert!(a.insert(100));
1333        assert!(a.insert(1000));
1334
1335        let mut b = a.clone();
1336
1337        assert!(a == b);
1338
1339        assert!(b.remove(1));
1340        assert!(a.contains(1));
1341
1342        assert!(a.remove(1000));
1343        assert!(b.contains(1000));
1344    }
1345
1346/*
1347    #[test]
1348    fn test_bit_set_append() {
1349        let mut a = BitArraySet::new();
1350        a.insert(2);
1351        a.insert(6);
1352
1353        let mut b = BitArraySet::new();
1354        b.insert(1);
1355        b.insert(3);
1356        b.insert(6);
1357
1358        a.append(&mut b);
1359
1360        assert_eq!(a.len(), 4);
1361        assert_eq!(b.len(), 0);
1362        assert!(b.capacity() >= 6);
1363
1364        assert_eq!(a, BitArraySet::from_bytes(&[0b01110010]));
1365    }
1366
1367    #[test]
1368    fn test_bit_set_split_off() {
1369        // Split at 0
1370        let mut a = BitArraySet::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
1371                                         0b00110011, 0b01101011, 0b10101101]);
1372
1373        let b = a.split_off(0);
1374
1375        assert_eq!(a.len(), 0);
1376        assert_eq!(b.len(), 21);
1377
1378        assert_eq!(b, BitArraySet::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
1379                                           0b00110011, 0b01101011, 0b10101101]);
1380
1381        // Split behind last element
1382        let mut a = BitArraySet::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
1383                                         0b00110011, 0b01101011, 0b10101101]);
1384
1385        let b = a.split_off(50);
1386
1387        assert_eq!(a.len(), 21);
1388        assert_eq!(b.len(), 0);
1389
1390        assert_eq!(a, BitArraySet::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
1391                                           0b00110011, 0b01101011, 0b10101101]));
1392
1393        // Split at arbitrary element
1394        let mut a = BitArraySet::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
1395                                         0b00110011, 0b01101011, 0b10101101]);
1396
1397        let b = a.split_off(34);
1398
1399        assert_eq!(a.len(), 12);
1400        assert_eq!(b.len(), 9);
1401
1402        assert_eq!(a, BitArraySet::from_bytes(&[0b10100000, 0b00010010, 0b10010010,
1403                                           0b00110011, 0b01000000]));
1404        assert_eq!(b, BitArraySet::from_bytes(&[0, 0, 0, 0,
1405                                           0b00101011, 0b10101101]));
1406    }
1407*/
1408}
1409
1410#[cfg(all(test, feature = "nightly"))]
1411mod bench {
1412    use super::BitArraySet;
1413    use bit_array::BitArray;
1414    use rand::{Rng, thread_rng, ThreadRng};
1415    use typenum::*;
1416
1417    use test::{Bencher, black_box};
1418
1419    //const BENCH_BITS: usize = 1 << 14;
1420    const BITS: usize = 32;
1421
1422    fn rng() -> ThreadRng {
1423        thread_rng()
1424    }
1425
1426    #[bench]
1427    fn bench_bit_arrayset_small(b: &mut Bencher) {
1428        let mut r = rng();
1429        let mut bit_arrayset = BitArraySet::<u32, U32>::new();
1430        b.iter(|| {
1431            for _ in 0..100 {
1432                bit_arrayset.insert((r.next_u32() as usize) % BITS);
1433            }
1434            black_box(&bit_arrayset);
1435        });
1436    }
1437
1438    #[bench]
1439    fn bench_bit_arrayset_big(b: &mut Bencher) {
1440        let mut r = rng();
1441        let mut bit_arrayset = BitArraySet::<u32, U16384>::new();
1442        b.iter(|| {
1443            for _ in 0..100 {
1444                bit_arrayset.insert((r.next_u32() as usize) % U16384::to_usize());
1445            }
1446            black_box(&bit_arrayset);
1447        });
1448    }
1449
1450    #[bench]
1451    fn bench_bit_arrayset_iter(b: &mut Bencher) {
1452        let bit_arrayset = BitArraySet::from_bit_array(BitArray::<u32, U32>::from_fn(
1453                                              |idx| {idx % 3 == 0}));
1454        b.iter(|| {
1455            let mut sum = 0;
1456            for idx in &bit_arrayset {
1457                sum += idx as usize;
1458            }
1459            sum
1460        })
1461    }
1462}
bitarray_set/lib.rs

bitarray_set/
lib.rs
