[dependencies.bit-vec]
version = "0.6.1"
default-features = false

[features]
default = ["std"]
std = ["bit-vec/std"]

pub struct BitSet<B = u32> {
    bit_vec: BitVec<B>,
}

        // Apply values found in other
        for (i, w) in other_words {
            let old = self_bit_vec.storage()[i];
            let new = f(old, w);
            unsafe {
                self_bit_vec.storage_mut()[i] = new;
            }
        }
    }

    #[inline]
    pub fn shrink_to_fit(&mut self) {
        let bit_vec = &mut self.bit_vec;
        // Obtain original length
        let old_len = bit_vec.storage().len();
        // Obtain coarse trailing zero length
        let n = bit_vec
            .storage()
            .iter()
            .rev()
            .take_while(|&&n| n == B::zero())
            .count();
        // Truncate away all empty trailing blocks, then shrink_to_fit
        let trunc_len = old_len - n;
        unsafe {
            bit_vec.storage_mut().truncate(trunc_len);
            bit_vec.set_len(trunc_len * B::bits());
            bit_vec.shrink_to_fit();
        }
    }

impl<'a, T, B: BitBlock> Iterator for BlockIter<T, B>
where
    T: Iterator<Item = B>,
{
    type Item = usize;

    fn next(&mut self) -> Option<usize> {
        while self.head == B::zero() {
            match self.tail.next() {
                Some(w) => self.head = w,
                None => return None,
            }
            self.head_offset += B::bits();
        }

        // from the current block, isolate the
        // LSB and subtract 1, producing k:
        // a block with a number of set bits
        // equal to the index of the LSB
        let k = (self.head & (!self.head + B::one())) - B::one();
        // update block, removing the LSB
        self.head = self.head & (self.head - B::one());
        // return offset + (index of LSB)
        Some(self.head_offset + (B::count_ones(k) as usize))
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        match self.tail.size_hint() {
            (_, Some(h)) => (0, Some(1 + h * B::bits())),
            _ => (0, None),
        }
    }
}

/// Computes how many blocks are needed to store that many bits
fn blocks_for_bits<B: BitBlock>(bits: usize) -> usize {
    // If we want 17 bits, dividing by 32 will produce 0. So we add 1 to make sure we
    // reserve enough. But if we want exactly a multiple of 32, this will actually allocate
    // one too many. So we need to check if that's the case. We can do that by computing if
    // bitwise AND by `32 - 1` is 0. But LLVM should be able to optimize the semantically
    // superior modulo operator on a power of two to this.
    //
    // Note that we can technically avoid this branch with the expression
    // `(nbits + BITS - 1) / 32::BITS`, but if nbits is almost usize::MAX this will overflow.
    if bits % B::bits() == 0 {
        bits / B::bits()
    } else {
        bits / B::bits() + 1
    }
}

#![no_std]
#![cfg_attr(all(test, feature = "nightly"), feature(test))]
extern crate bit_vec;
#[cfg(all(test, feature = "nightly"))]
extern crate rand;
#[cfg(all(test, feature = "nightly"))]
extern crate test;

#[cfg(test)]
#[macro_use]
extern crate std;

use bit_vec::{BitBlock, BitVec, Blocks};
use core::cmp;
use core::cmp::Ordering;
use core::fmt;
use core::hash;
use core::iter::{self, Chain, Enumerate, FromIterator, Repeat, Skip, Take};

#[cfg(test)]
mod tests {
    use super::BitSet;
    use bit_vec::BitVec;
    use std::cmp::Ordering::{Equal, Greater, Less};
    use std::vec::Vec;

    #[test]
    fn test_bit_set_show() {
        let mut s = BitSet::new();
        s.insert(1);
        s.insert(10);
        s.insert(50);
        s.insert(2);
        assert_eq!("{1, 2, 10, 50}", format!("{:?}", s));
    }

    #[test]
    fn test_bit_set_from_usizes() {
        let usizes = vec![0, 2, 2, 3];
        let a: BitSet = usizes.into_iter().collect();
        let mut b = BitSet::new();
        b.insert(0);
        b.insert(2);
        b.insert(3);
        assert_eq!(a, b);
    }

    #[test]
    fn test_bit_set_iterator() {
        let usizes = vec![0, 2, 2, 3];
        let bit_vec: BitSet = usizes.into_iter().collect();

        let idxs: Vec<_> = bit_vec.iter().collect();
        assert_eq!(idxs, [0, 2, 3]);

        let long: BitSet = (0..10000).filter(|&n| n % 2 == 0).collect();
        let real: Vec<_> = (0..10000 / 2).map(|x| x * 2).collect();

        let idxs: Vec<_> = long.iter().collect();
        assert_eq!(idxs, real);
    }

    #[test]
    fn test_bit_set_frombit_vec_init() {
        let bools = [true, false];
        let lengths = [10, 64, 100];
        for &b in &bools {
            for &l in &lengths {
                let bitset = BitSet::from_bit_vec(BitVec::from_elem(l, b));
                assert_eq!(bitset.contains(1), b);
                assert_eq!(bitset.contains(l - 1), b);
                assert!(!bitset.contains(l));
            }
        }
    }

    #[test]
    fn test_bit_vec_masking() {
        let b = BitVec::from_elem(140, true);
        let mut bs = BitSet::from_bit_vec(b);
        assert!(bs.contains(139));
        assert!(!bs.contains(140));
        assert!(bs.insert(150));
        assert!(!bs.contains(140));
        assert!(!bs.contains(149));
        assert!(bs.contains(150));
        assert!(!bs.contains(151));
    }

    #[test]
    fn test_bit_set_basic() {
        let mut b = BitSet::new();
        assert!(b.insert(3));
        assert!(!b.insert(3));
        assert!(b.contains(3));
        assert!(b.insert(4));
        assert!(!b.insert(4));
        assert!(b.contains(3));
        assert!(b.insert(400));
        assert!(!b.insert(400));
        assert!(b.contains(400));
        assert_eq!(b.len(), 3);
    }

    #[test]
    fn test_bit_set_intersection() {
        let mut a = BitSet::new();
        let mut b = BitSet::new();

        assert!(a.insert(11));
        assert!(a.insert(1));
        assert!(a.insert(3));
        assert!(a.insert(77));
        assert!(a.insert(103));
        assert!(a.insert(5));

        assert!(b.insert(2));
        assert!(b.insert(11));
        assert!(b.insert(77));
        assert!(b.insert(5));
        assert!(b.insert(3));

        let expected = [3, 5, 11, 77];
        let actual: Vec<_> = a.intersection(&b).collect();
        assert_eq!(actual, expected);
    }

    #[test]
    fn test_bit_set_difference() {
        let mut a = BitSet::new();
        let mut b = BitSet::new();

        assert!(a.insert(1));
        assert!(a.insert(3));
        assert!(a.insert(5));
        assert!(a.insert(200));
        assert!(a.insert(500));

        assert!(b.insert(3));
        assert!(b.insert(200));

        let expected = [1, 5, 500];
        let actual: Vec<_> = a.difference(&b).collect();
        assert_eq!(actual, expected);
    }

    #[test]
    fn test_bit_set_symmetric_difference() {
        let mut a = BitSet::new();
        let mut b = BitSet::new();

        assert!(a.insert(1));
        assert!(a.insert(3));
        assert!(a.insert(5));
        assert!(a.insert(9));
        assert!(a.insert(11));

        assert!(b.insert(3));
        assert!(b.insert(9));
        assert!(b.insert(14));
        assert!(b.insert(220));

        let expected = [1, 5, 11, 14, 220];
        let actual: Vec<_> = a.symmetric_difference(&b).collect();
        assert_eq!(actual, expected);
    }

    #[test]
    fn test_bit_set_union() {
        let mut a = BitSet::new();
        let mut b = BitSet::new();
        assert!(a.insert(1));
        assert!(a.insert(3));
        assert!(a.insert(5));
        assert!(a.insert(9));
        assert!(a.insert(11));
        assert!(a.insert(160));
        assert!(a.insert(19));
        assert!(a.insert(24));
        assert!(a.insert(200));

        assert!(b.insert(1));
        assert!(b.insert(5));
        assert!(b.insert(9));
        assert!(b.insert(13));
        assert!(b.insert(19));

        let expected = [1, 3, 5, 9, 11, 13, 19, 24, 160, 200];
        let actual: Vec<_> = a.union(&b).collect();
        assert_eq!(actual, expected);
    }

    #[test]
    fn test_bit_set_subset() {
        let mut set1 = BitSet::new();
        let mut set2 = BitSet::new();

        assert!(set1.is_subset(&set2)); //  {}  {}
        set2.insert(100);
        assert!(set1.is_subset(&set2)); //  {}  { 1 }
        set2.insert(200);
        assert!(set1.is_subset(&set2)); //  {}  { 1, 2 }
        set1.insert(200);
        assert!(set1.is_subset(&set2)); //  { 2 }  { 1, 2 }
        set1.insert(300);
        assert!(!set1.is_subset(&set2)); // { 2, 3 }  { 1, 2 }
        set2.insert(300);
        assert!(set1.is_subset(&set2)); // { 2, 3 }  { 1, 2, 3 }
        set2.insert(400);
        assert!(set1.is_subset(&set2)); // { 2, 3 }  { 1, 2, 3, 4 }
        set2.remove(100);
        assert!(set1.is_subset(&set2)); // { 2, 3 }  { 2, 3, 4 }
        set2.remove(300);
        assert!(!set1.is_subset(&set2)); // { 2, 3 }  { 2, 4 }
        set1.remove(300);
        assert!(set1.is_subset(&set2)); // { 2 }  { 2, 4 }
    }

    #[test]
    fn test_bit_set_is_disjoint() {
        let a = BitSet::from_bytes(&[0b10100010]);
        let b = BitSet::from_bytes(&[0b01000000]);
        let c = BitSet::new();
        let d = BitSet::from_bytes(&[0b00110000]);

        assert!(!a.is_disjoint(&d));
        assert!(!d.is_disjoint(&a));

        assert!(a.is_disjoint(&b));
        assert!(a.is_disjoint(&c));
        assert!(b.is_disjoint(&a));
        assert!(b.is_disjoint(&c));
        assert!(c.is_disjoint(&a));
        assert!(c.is_disjoint(&b));
    }

    #[test]
    fn test_bit_set_union_with() {
        //a should grow to include larger elements
        let mut a = BitSet::new();
        a.insert(0);
        let mut b = BitSet::new();
        b.insert(5);
        let expected = BitSet::from_bytes(&[0b10000100]);
        a.union_with(&b);
        assert_eq!(a, expected);

        // Standard
        let mut a = BitSet::from_bytes(&[0b10100010]);
        let mut b = BitSet::from_bytes(&[0b01100010]);
        let c = a.clone();
        a.union_with(&b);
        b.union_with(&c);
        assert_eq!(a.len(), 4);
        assert_eq!(b.len(), 4);
    }

    #[test]
    fn test_bit_set_intersect_with() {
        // Explicitly 0'ed bits
        let mut a = BitSet::from_bytes(&[0b10100010]);
        let mut b = BitSet::from_bytes(&[0b00000000]);
        let c = a.clone();
        a.intersect_with(&b);
        b.intersect_with(&c);
        assert!(a.is_empty());
        assert!(b.is_empty());

        // Uninitialized bits should behave like 0's
        let mut a = BitSet::from_bytes(&[0b10100010]);
        let mut b = BitSet::new();
        let c = a.clone();
        a.intersect_with(&b);
        b.intersect_with(&c);
        assert!(a.is_empty());
        assert!(b.is_empty());

        // Standard
        let mut a = BitSet::from_bytes(&[0b10100010]);
        let mut b = BitSet::from_bytes(&[0b01100010]);
        let c = a.clone();
        a.intersect_with(&b);
        b.intersect_with(&c);
        assert_eq!(a.len(), 2);
        assert_eq!(b.len(), 2);
    }

    #[test]
    fn test_bit_set_difference_with() {
        // Explicitly 0'ed bits
        let mut a = BitSet::from_bytes(&[0b00000000]);
        let b = BitSet::from_bytes(&[0b10100010]);
        a.difference_with(&b);
        assert!(a.is_empty());

        // Uninitialized bits should behave like 0's
        let mut a = BitSet::new();
        let b = BitSet::from_bytes(&[0b11111111]);
        a.difference_with(&b);
        assert!(a.is_empty());

        // Standard
        let mut a = BitSet::from_bytes(&[0b10100010]);
        let mut b = BitSet::from_bytes(&[0b01100010]);
        let c = a.clone();
        a.difference_with(&b);
        b.difference_with(&c);
        assert_eq!(a.len(), 1);
        assert_eq!(b.len(), 1);
    }

    #[test]
    fn test_bit_set_symmetric_difference_with() {
        //a should grow to include larger elements
        let mut a = BitSet::new();
        a.insert(0);
        a.insert(1);
        let mut b = BitSet::new();
        b.insert(1);
        b.insert(5);
        let expected = BitSet::from_bytes(&[0b10000100]);
        a.symmetric_difference_with(&b);
        assert_eq!(a, expected);

        let mut a = BitSet::from_bytes(&[0b10100010]);
        let b = BitSet::new();
        let c = a.clone();
        a.symmetric_difference_with(&b);
        assert_eq!(a, c);

        // Standard
        let mut a = BitSet::from_bytes(&[0b11100010]);
        let mut b = BitSet::from_bytes(&[0b01101010]);
        let c = a.clone();
        a.symmetric_difference_with(&b);
        b.symmetric_difference_with(&c);
        assert_eq!(a.len(), 2);
        assert_eq!(b.len(), 2);
    }

    #[test]
    fn test_bit_set_eq() {
        let a = BitSet::from_bytes(&[0b10100010]);
        let b = BitSet::from_bytes(&[0b00000000]);
        let c = BitSet::new();

        assert!(a == a);
        assert!(a != b);
        assert!(a != c);
        assert!(b == b);
        assert!(b == c);
        assert!(c == c);
    }

    #[test]
    fn test_bit_set_cmp() {
        let a = BitSet::from_bytes(&[0b10100010]);
        let b = BitSet::from_bytes(&[0b00000000]);
        let c = BitSet::new();

        assert_eq!(a.cmp(&b), Greater);
        assert_eq!(a.cmp(&c), Greater);
        assert_eq!(b.cmp(&a), Less);
        assert_eq!(b.cmp(&c), Equal);
        assert_eq!(c.cmp(&a), Less);
        assert_eq!(c.cmp(&b), Equal);
    }

    #[test]
    fn test_bit_set_shrink_to_fit_new() {
        // There was a strange bug where we refused to truncate to 0
        // and this would end up actually growing the array in a way
        // that (safely corrupted the state).
        let mut a = BitSet::new();
        assert_eq!(a.len(), 0);
        assert_eq!(a.capacity(), 0);
        a.shrink_to_fit();
        assert_eq!(a.len(), 0);
        assert_eq!(a.capacity(), 0);
        assert!(!a.contains(1));
        a.insert(3);
        assert!(a.contains(3));
        assert_eq!(a.len(), 1);
        assert!(a.capacity() > 0);
        a.shrink_to_fit();
        assert!(a.contains(3));
        assert_eq!(a.len(), 1);
        assert!(a.capacity() > 0);
    }

    #[test]
    fn test_bit_set_shrink_to_fit() {
        let mut a = BitSet::new();
        assert_eq!(a.len(), 0);
        assert_eq!(a.capacity(), 0);
        a.insert(259);
        a.insert(98);
        a.insert(3);
        assert_eq!(a.len(), 3);
        assert!(a.capacity() > 0);
        assert!(!a.contains(1));
        assert!(a.contains(259));
        assert!(a.contains(98));
        assert!(a.contains(3));

        a.shrink_to_fit();
        assert!(!a.contains(1));
        assert!(a.contains(259));
        assert!(a.contains(98));
        assert!(a.contains(3));
        assert_eq!(a.len(), 3);
        assert!(a.capacity() > 0);

        let old_cap = a.capacity();
        assert!(a.remove(259));
        a.shrink_to_fit();
        assert!(a.capacity() < old_cap, "{} {}", a.capacity(), old_cap);
        assert!(!a.contains(1));
        assert!(!a.contains(259));
        assert!(a.contains(98));
        assert!(a.contains(3));
        assert_eq!(a.len(), 2);

        let old_cap2 = a.capacity();
        a.clear();
        assert_eq!(a.capacity(), old_cap2);
        assert_eq!(a.len(), 0);
        assert!(!a.contains(1));
        assert!(!a.contains(259));
        assert!(!a.contains(98));
        assert!(!a.contains(3));

        a.insert(512);
        assert!(a.capacity() > 0);
        assert_eq!(a.len(), 1);
        assert!(a.contains(512));
        assert!(!a.contains(1));
        assert!(!a.contains(259));
        assert!(!a.contains(98));
        assert!(!a.contains(3));

        a.remove(512);
        a.shrink_to_fit();
        assert_eq!(a.capacity(), 0);
        assert_eq!(a.len(), 0);
        assert!(!a.contains(512));
        assert!(!a.contains(1));
        assert!(!a.contains(259));
        assert!(!a.contains(98));
        assert!(!a.contains(3));
        assert!(!a.contains(0));
    }

    #[test]
    fn test_bit_vec_remove() {
        let mut a = BitSet::new();

        assert!(a.insert(1));
        assert!(a.remove(1));

        assert!(a.insert(100));
        assert!(a.remove(100));

        assert!(a.insert(1000));
        assert!(a.remove(1000));
        a.shrink_to_fit();
    }

    /// Returns the number of set bits in this set.
    #[inline]
    pub fn len(&self) -> usize {
        self.bit_vec
            .blocks()
            .fold(0, |acc, n| acc + n.count_ones() as usize)
    }

    /// Returns whether there are no bits set in this set
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.bit_vec.none()
    }

    /// Clears all bits in this set
    #[inline]
    pub fn clear(&mut self) {
        self.bit_vec.clear();
    }

    /// Returns `true` if this set contains the specified integer.
    #[inline]
    pub fn contains(&self, value: usize) -> bool {
        let bit_vec = &self.bit_vec;
        value < bit_vec.len() && bit_vec[value]
    }

    /// Returns `true` if the set has no elements in common with `other`.
    /// This is equivalent to checking for an empty intersection.
    #[inline]
    pub fn is_disjoint(&self, other: &Self) -> bool {
        self.intersection(other).next().is_none()
    }

    /// Returns `true` if the set is a subset of another.
    #[inline]
    pub fn is_subset(&self, other: &Self) -> bool {
        let self_bit_vec = &self.bit_vec;
        let other_bit_vec = &other.bit_vec;
        let other_blocks = blocks_for_bits::<B>(other_bit_vec.len());

        // Check that `self` intersect `other` is self
        self_bit_vec.blocks().zip(other_bit_vec.blocks()).all(|(w1, w2)| w1 & w2 == w1) &&
        // Make sure if `self` has any more blocks than `other`, they're all 0
        self_bit_vec.blocks().skip(other_blocks).all(|w| w == B::zero())
    }

    /// Returns `true` if the set is a superset of another.
    #[inline]
    pub fn is_superset(&self, other: &Self) -> bool {
        other.is_subset(self)
    }

    /// Adds a value to the set. Returns `true` if the value was not already
    /// present in the set.
    pub fn insert(&mut self, value: usize) -> bool {
        if self.contains(value) {
            return false;
        }

        // Ensure we have enough space to hold the new element
        let len = self.bit_vec.len();
        if value >= len {
            self.bit_vec.grow(value - len + 1, false)
        }

        self.bit_vec.set(value, true);
        true
    }

    /// Removes a value from the set. Returns `true` if the value was
    /// present in the set.
    pub fn remove(&mut self, value: usize) -> bool {
        if !self.contains(value) {
            return false;
        }

        self.bit_vec.set(value, false);

        true
    }