//! Bitwise operations on fixed-size, arbitrary big buffer of bytes.
//!
//! The primitive types `u8`, `u16`, `u32` and `u64` are very useful types,
//! when one needs to perform boolean algebra on many bits at once (bitwise
//! operations).
//!
//! This crate complements these primitive types, with subsequent power-of-two
//! sizes: `Bw128`, `Bw256`, etc. These types are all `Copy` (that is, they can
//! be trivially copied as raw memory), and their size is really the size given
//! by their names (`Bw256` takes 256 bits). You may be quickly limited by
//! Rust's default stack size if you store these types directly on the stack.
//! Don't forget to box your values if you want them to live on the heap!
//!
//! If the types provided are not enough, you can easily define your own by
//! creating an alias to a `BwPair<X>`. Only power-of-two sizes are supported.

extern crate rand;

#[cfg(test)]
extern crate quickcheck;

pub mod bigwise {

    use rand::{Rand, Rng};
    use std::fmt::{self, Debug, Formatter};

    /// A type that supports bitwise operations.
    ///
    /// An impl of this trait must declare the number of bits it woks with,
    /// using the `size` method.
    ///
    /// Note that bitwise operations can be applied only between operands of
    /// the exact same type, and not two different types that both implement
    /// `Bigwise`.
    ///
    pub trait Bigwise : Rand + Debug + Eq {

        /// Number of bits stored.
        fn size() -> u32;

        /// A value with all bits set to 0.
        fn empty() -> Self;

        /// A value with all bits set to 1.
        fn full() -> Self;

        /// Creates a value based on raw data.
        ///
        /// The LSB (least significant bit) of the last element of the slice
        /// will become the LSB of the created value.
        ///
        /// If `byte` contains less bits than the type allows, then the MSB
        /// (most significant bits) of the created value will be set to 0. If
        /// `byte` contains more bits than the type allows, then only the last
        /// n elements of the slice will be used to set the content of the
        /// created value (with `n` = `size` / 8).
        ///
        fn from_bytes(byte: &[u8]) -> Self;

        /// The content of the value as raw bytes.
        ///
        /// The MSB (most significant bit) of the first u8 is the MSB of the
        /// value. The LSB (least significant bit) of the last u8 is the LSB of
        /// the value.
        ///
        fn to_bytes(&self) -> Vec<u8>;

        /// The boolean value of the given bit.
        ///
        /// Bits are indexed from the least significant (index 0) to the most
        /// significant.
        ///
        /// if `i` is outside the capacity of this type, the returned value is
        /// always false (as if the value had an infinite amout of 0 before
        /// the most significant bit).
        ///
        fn get(&self, i: u32) -> bool;

        /// Assigns a boolean value to a given bit.
        ///
        /// Bits are indexed from the least significant (index 0) to the most
        /// significant.
        ///
        /// # Panics
        ///
        /// Panics if `i` >= `size`.
        ///
        fn set(&mut self, i: u32, v: bool);

        /// An iterator over the bits.
        ///
        /// Bits are iterated from the least significant one to the most
        /// significant one.
        ///
        fn iter(&self) -> BitsIter<Self>;

        /// Shifts all the bits `n` positions to the left.
        ///
        /// The bits that are inserted on the LSB (least significant bit) side
        /// are all zeroes.
        ///
        /// If `n` >= `size`, the result will contain only zeroes.
        ///
        fn shift_left(&self, n: u32) -> Self;

        /// Shifts all the bits `n` positions to the right.
        ///
        /// The bits that are inserted on the MSB (most significant bit) side
        /// are all zeroes.
        ///
        /// If `n` >= `size`, the result will contain only zeroes.
        ///
        fn shift_right(&self, n: u32) -> Self;

        /// Bitwise OR operation
        fn or(&self, rhs: &Self) -> Self;

        /// Bitwise AND operation
        fn and(&self, rhs: &Self) -> Self;

        /// Bitwise XOR operation
        fn xor(&self, rhs: &Self) -> Self;

        /// Bitwise NOT operation
        fn not(&self) -> Self;

        /// Rotates all the bits `n` positions to the left.
        ///
        /// The bits that are lost on the MSB (most significant bit) side are
        /// re-inserted on the LSB (least significant bit) side.
        ///
        fn rotate_left(&self, n: u32) -> Self;

        /// Rotates all the bits `n` positions to the right.
        ///
        /// The bits that are lost on the LSB (least significant bit) side are
        /// re-inserted on the MSB (most significant bit) side.
        ///
        fn rotate_right(&self, n: u32) -> Self;
    }

    /// An iterator over the bits.
    ///
    /// Bits are iterated from the least significant one to the most
    /// significant one.
    ///
    pub struct BitsIter<'a, T: Bigwise + 'a> {
        bw: &'a T,
        idx: u32,
    }

    impl<'a, T: Bigwise> Iterator for BitsIter<'a, T> {
        type Item = bool;

        fn next(&mut self) -> Option<Self::Item> {
            if self.idx < T::size() {
                let res = Some(self.bw.get(self.idx));
                self.idx += 1;
                res
            } else {
                None
            }
        }
    }

    /// A `Bigwise` type composed of 64 bits.
    ///
    /// Wraps a `u64`
    ///
    #[derive(Copy, Clone, Eq, PartialEq)]
    pub struct Bw64(u64);

    impl Bigwise for Bw64 {

        fn size() -> u32 {
            64
        }

        fn empty() -> Self {
            Bw64(0)
        }

        fn full() -> Self {
            Bw64(!0)
        }

        fn from_bytes(bytes: &[u8]) -> Self {
            let mut val = 0u64;
            for (i, &b) in bytes.iter().rev().take(8).enumerate() {
                val |= (b as u64) << (8*i);
            }
            Bw64(val)
        }

        fn to_bytes(&self) -> Vec<u8> {
            let nb_bytes = (Self::size() / 8) as usize;
            let mut res = Vec::with_capacity(nb_bytes);
            for i in (0..nb_bytes).rev() {
                res.push(((self.0 >> (8*i)) & 0xFF) as u8);
            }
            res
        }

        fn get(&self, i: u32) -> bool {
            if i >= Self::size() {
                false
            } else {
                (self.0 >> i) & 1 > 0
            }
        }

        fn set(&mut self, i: u32, v: bool) {
            if i >= Self::size() {
                panic!("index overflow");
            }
            if v {
                self.0 |= 1 << i;
            } else {
                self.0 &= !(1 << i);
            }
        }

        fn iter(&self) -> BitsIter<Self> {
            BitsIter {bw: self, idx: 0}
        }

        fn shift_left(&self, n: u32) -> Self {
            if n >= Self::size() {
                Self::empty()
            } else {
                Bw64(self.0 << n)
            }
        }

        fn shift_right(&self, n: u32) -> Self {
            if n >= Self::size() {
                Self::empty()
            } else {
                Bw64(self.0 >> n)
            }
        }

        fn or(&self, rhs: &Self) -> Self {
            Bw64(self.0 | rhs.0)
        }

        fn and(&self, rhs: &Self) -> Self {
            Bw64(self.0 & rhs.0)
        }

        fn xor(&self, rhs: &Self) -> Self {
            Bw64(self.0 ^ rhs.0)
        }

        fn not(&self) -> Self {
            Bw64(!self.0)
        }

        fn rotate_left(&self, n: u32) -> Self {
            Bw64(self.0.rotate_left(n))
        }

        fn rotate_right(&self, n: u32) -> Self {
            Bw64(self.0.rotate_right(n))
        }
    }

    impl Rand for Bw64 {
        fn rand<R: Rng>(rng: &mut R) -> Self {
            Bw64(rng.next_u64())
        }
    }

    /// The sequence of zeroes and ones, the MSB (most significant bit)
    /// appearing on the left.
    ///
    impl Debug for Bw64 {
        fn fmt(&self, f: &mut Formatter) -> Result<(), fmt::Error> {
            let bytes = self.to_bytes();
            for b in bytes {
                try!(f.write_str(&format!("{:08b}", b)));
            }
            Ok(())
        }
    }

    /// Combines two `Bigwise` to form a bigger one.
    ///
    /// This is the mechanism that allows us to build any power-of-two sized
    /// Bigwise.
    ///
    #[derive(Copy, Clone, Eq, PartialEq)]
    pub struct BwPair<T> where T: Bigwise {
        left: T,
        right: T,
    }

    /// A `Bigwise` type composed of 128 bits.
    pub type Bw128 = BwPair<Bw64>;

    /// A `Bigwise` type composed of 256 bits.
    pub type Bw256 = BwPair<Bw128>;

    /// A `Bigwise` type composed of 512 bits.
    pub type Bw512 = BwPair<Bw256>;

    /// A `Bigwise` type composed of 1024 bits.
    pub type Bw1k = BwPair<Bw512>;

    /// A `Bigwise` type composed of 2.048 bits.
    pub type Bw2k = BwPair<Bw1k>;

    /// A `Bigwise` type composed of 4.096 bits.
    pub type Bw4k = BwPair<Bw2k>;

    /// A `Bigwise` type composed of 8.192 bits.
    pub type Bw8k = BwPair<Bw4k>;

    /// A `Bigwise` type composed of 16.384 bits.
    pub type Bw16k = BwPair<Bw8k>;

    /// A `Bigwise` type composed of 32.768 bits.
    pub type Bw32k = BwPair<Bw16k>;

    /// A `Bigwise` type composed of 65.536 bits.
    pub type Bw64k = BwPair<Bw32k>;

    /// A `Bigwise` type composed of 131.072 bits.
    pub type Bw128k = BwPair<Bw64k>;

    /// A `Bigwise` type composed of 262.144 bits.
    pub type Bw256k = BwPair<Bw128k>;

    /// A `Bigwise` type composed of 524.288 bits.
    pub type Bw512k = BwPair<Bw256k>;

    /// A `Bigwise` type composed of 1.048.576 bits.
    pub type Bw1M = BwPair<Bw512k>;

    impl <T> Bigwise for BwPair<T> where T: Bigwise + Copy {

        fn size() -> u32 {
            2 * T::size()
        }

        fn empty() -> Self {
            BwPair {
                left: T::empty(),
                right: T::empty(),
            }
        }

        fn full() -> Self {
            BwPair {
                left: T::full(),
                right: T::full(),
            }
        }

        fn from_bytes(bytes: &[u8]) -> Self {
            use std::cmp::min;

            let half_bytes = (T::size() / 8) as usize;
            let x1 = bytes.len() - min(bytes.len(), 2 * half_bytes);
            let x2 = bytes.len() - min(bytes.len(), half_bytes);
            BwPair {
                left: if x2 > x1 { T::from_bytes(&bytes[x1..x2]) } else { T::empty() },
                right: T::from_bytes(&bytes[x2..]),
            }
        }

        fn to_bytes(&self) -> Vec<u8> {
            let nb_bytes = (Self::size() / 8) as usize;
            let mut res = Vec::with_capacity(nb_bytes);
            res.extend(&mut self.left.to_bytes().into_iter());
            res.extend(&mut self.right.to_bytes().into_iter());
            res
        }

        fn get(&self, i: u32) -> bool {
            if i >= Self::size() {
                false
            } else if i >= T::size() {
                self.left.get(i - T::size())
            } else {
                self.right.get(i)
            }
        }

        fn set(&mut self, i: u32, v: bool) {
            if i >= Self::size() {
                panic!("index overflowed");
            } else if i >= T::size() {
                self.left.set(i - T::size(), v)
            } else {
                self.right.set(i, v)
            }
        }

        fn iter(&self) -> BitsIter<Self> {
            BitsIter {bw: self, idx: 0}
        }

        fn shift_left(&self, n: u32) -> Self {
            if n == 0 {
                *self
            } else if n < T::size() {
                BwPair {
                    left: self.left.shift_left(n).or(&self.right.shift_right(T::size()-n)),
                    right: self.right.shift_left(n),
                }
            } else if n == T::size() {
                BwPair {
                    left: self.right,
                    right: T::empty(),
                }
            } else if n < Self::size() {
                BwPair {
                    left: self.right.shift_left(n-T::size()),
                    right: T::empty(),
                }
            } else {
                BwPair {
                    left: T::empty(),
                    right: T::empty(),
                }
            }
        }

        fn shift_right(&self, n: u32) -> Self {
            if n == 0 {
                *self
            } else if n < T::size() {
                BwPair {
                    left: self.left.shift_right(n),
                    right: self.right.shift_right(n).or(&self.left.shift_left(T::size()-n)),
                }
            } else if n == T::size() {
                BwPair {
                    left: T::empty(),
                    right: self.left,
                }
            } else if n < Self::size() {
                BwPair {
                    left: T::empty(),
                    right: self.left.shift_right(n-T::size()),
                }
            } else {
                BwPair {
                    left: T::empty(),
                    right: T::empty(),
                }
            }
        }

        fn or(&self, rhs: &Self) -> Self {
            BwPair {
                left: self.left.or(&rhs.left),
                right: self.right.or(&rhs.right),
            }
        }

        fn and(&self, rhs: &Self) -> Self {
            BwPair {
                left: self.left.and(&rhs.left),
                right: self.right.and(&rhs.right),
            }
        }

        fn xor(&self, rhs: &Self) -> Self {
            BwPair {
                left: self.left.xor(&rhs.left),
                right: self.right.xor(&rhs.right),
            }
        }

        fn not(&self) -> Self {
            BwPair {
                left: self.left.not(),
                right: self.right.not(),
            }
        }

        fn rotate_left(&self, n: u32) -> Self {
            let n = n % Self::size();
            if n == 0 {
                *self
            } else if n < T::size() {
                BwPair {
                    left: self.left.shift_left(n).or(&self.right.shift_right(T::size()-n)),
                    right: self.right.shift_left(n).or(&self.left.shift_right(T::size()-n)),
                }
            } else if n == T::size() {
                BwPair {
                    left: self.right,
                    right: self.left,
                }
            } else {
                BwPair {
                    left: self.right.shift_left(n-T::size()).or(&self.left.shift_right(T::size()-n)),
                    right: self.left.shift_right(n-T::size()).or(&self.right.shift_left(T::size()-n)),
                }
            }
        }

        fn rotate_right(&self, n: u32) -> Self {
            let n = n % Self::size();
            if n == 0 {
                *self
            } else if n < T::size() {
                BwPair {
                    left: self.right.shift_right(n).or(&self.left.shift_left(T::size()-n)),
                    right: self.left.shift_right(n).or(&self.right.shift_left(T::size()-n)),
                }
            } else if n == T::size() {
                BwPair {
                    left: self.right,
                    right: self.left,
                }
            } else {
                BwPair {
                    left: self.left.shift_right(n-T::size()).or(&self.right.shift_left(T::size()-n)),
                    right: self.right.shift_left(n-T::size()).or(&self.left.shift_right(T::size()-n)),
                }
            }
        }
    }

    impl <T> Rand for BwPair<T> where T: Bigwise {
        fn rand<R: Rng>(rng: &mut R) -> Self {
            BwPair {
                left: T::rand(rng),
                right: T::rand(rng),
            }
        }
    }

    /// The sequence of zeroes and ones, the MSB (most significant bit)
    /// appearing on the left.
    ///
    impl <T> Debug for BwPair<T> where T: Bigwise {
        fn fmt(&self, f: &mut Formatter) -> Result<(), fmt::Error> {
            try!(self.left.fmt(f));
            try!(self.right.fmt(f));
            Ok(())
        }
    }

    #[cfg(test)]
    mod tests {

        use bigwise::{Bigwise, BwPair, Bw64, Bw128, Bw256};
        use quickcheck::{Arbitrary, Gen, quickcheck, TestResult};

        impl Arbitrary for Bw64 {
            fn arbitrary<G: Gen>(g: &mut G) -> Self {
                g.gen()
            }
        }

        impl <T> Arbitrary for BwPair<T> where T: Bigwise + Send + 'static + Clone {
            fn arbitrary<G: Gen>(g: &mut G) -> Self {
                g.gen()
            }
        }

        fn generic_empty<T>() where T: Bigwise {
            let x = T::empty();
            for i in 0..T::size() {
                assert!(x.get(i) == false);
            }
        }

        #[test] fn bw64_empty() { generic_empty::<Bw64>(); }
        #[test] fn bw128_empty() { generic_empty::<Bw128>(); }
        #[test] fn bw256_empty() { generic_empty::<Bw256>(); }

        fn generic_full<T>() where T: Bigwise {
            let x = T::full();
            for i in 0..T::size() {
                assert!(x.get(i) == true);
            }
        }

        #[test] fn bw64_full() { generic_full::<Bw64>(); }
        #[test] fn bw128_full() { generic_full::<Bw128>(); }
        #[test] fn bw256_full() { generic_full::<Bw256>(); }

        fn generic_set_get<T>() where T: Bigwise {
            for i in 0..T::size() {
                let mut x = T::empty();
                assert!(x.get(i) == false);
                x.set(i, true);
                assert!(x.get(i) == true);
                x.set(i, false);
                assert!(x.get(i) == false);
            }
        }

        #[test] fn bw64_set_get() { generic_set_get::<Bw64>(); }
        #[test] fn bw128_set_get() { generic_set_get::<Bw128>(); }
        #[test] fn bw256_set_get() { generic_set_get::<Bw256>(); }

        fn prop_to_bytes_from_bytes<T>(x: T) -> bool where T: Bigwise {
            x == T::from_bytes(&x.to_bytes())
        }

        #[test] fn bw64_to_bytes_from_bytes() { quickcheck(prop_to_bytes_from_bytes::<Bw64> as fn(Bw64) -> bool); }
        #[test] fn bw128_to_bytes_from_bytes() { quickcheck(prop_to_bytes_from_bytes::<Bw128> as fn(Bw128) -> bool); }
        #[test] fn bw256_to_bytes_from_bytes() { quickcheck(prop_to_bytes_from_bytes::<Bw256> as fn(Bw256) -> bool); }

        fn generic_from_empty_bytes<T>() where T: Bigwise {
            assert!(T::from_bytes(&[]) == T::empty());
        }

        #[test] fn bw64_from_empty_bytes() { generic_from_empty_bytes::<Bw64>(); }
        #[test] fn bw128_from_empty_bytes() { generic_from_empty_bytes::<Bw128>(); }
        #[test] fn bw256_from_empty_bytes() { generic_from_empty_bytes::<Bw256>(); }

        fn generic_from_one_byte<T>() where T: Bigwise {
            let len = (T::size() / 8) as usize;
            let x = T::from_bytes(&[0xFF]).to_bytes();
            assert!(x.len() == len);
            assert!(x.iter().take(len-1).all(|&v| v == 0));
            assert!(x.last() == Some(&0xFF));
        }

        #[test] fn bw64_from_one_byte() { generic_from_one_byte::<Bw64>(); }
        #[test] fn bw128_from_one_byte() { generic_from_one_byte::<Bw128>(); }
        #[test] fn bw256_from_one_byte() { generic_from_one_byte::<Bw256>(); }

        fn generic_iter_empty<T>() where T: Bigwise {
            use std::iter::repeat;
            let v1 : Vec<_> = T::empty().iter().collect();
            let v2 : Vec<_> = repeat(false).take(T::size() as usize).collect();
            assert!(v1 == v2);
            assert!(v1.len() == T::size() as usize);
        }

        #[test] fn bw64_iter_empty() { generic_iter_empty::<Bw64>(); }
        #[test] fn bw128_iter_empty() { generic_iter_empty::<Bw128>(); }
        #[test] fn bw256_iter_empty() { generic_iter_empty::<Bw256>(); }

        fn generic_iter_full<T>() where T: Bigwise {
            use std::iter::repeat;
            let v1 : Vec<_> = T::full().iter().collect();
            let v2 : Vec<_> = repeat(true).take(T::size() as usize).collect();
            assert!(v1 == v2);
            assert!(v1.len() == T::size() as usize);
        }

        #[test] fn bw64_iter_full() { generic_iter_full::<Bw64>(); }
        #[test] fn bw128_iter_full() { generic_iter_full::<Bw128>(); }
        #[test] fn bw256_iter_full() { generic_iter_full::<Bw256>(); }

        fn prop_iter_get<T>(x: T) -> bool where T: Bigwise {
            x.iter().enumerate().all(|(i, b)| x.get(i as u32) == b)
        }

        #[test] fn bw64_iter_get() { quickcheck(prop_iter_get::<Bw64> as fn(Bw64) -> bool); }
        #[test] fn bw128_iter_get() { quickcheck(prop_iter_get::<Bw128> as fn(Bw128) -> bool); }
        #[test] fn bw256_iter_get() { quickcheck(prop_iter_get::<Bw256> as fn(Bw256) -> bool); }

        fn prop_shift_left<T>((original, n) : (T, u32)) -> TestResult where T: Bigwise {
            if n >= T::size() {
                return TestResult::discard();
            }
            let shifted = original.shift_left(n);
            let v_original : Vec<_> = original.iter().take((T::size()-n) as usize).collect();
            let v_shifted : Vec<_> = shifted.iter().skip(n as usize).collect();
            TestResult::from_bool(v_original == v_shifted)
        }

        #[test] fn bw64_shift_left() { quickcheck(prop_shift_left::<Bw64> as fn((Bw64, u32)) -> TestResult); }
        #[test] fn bw128_shift_left() { quickcheck(prop_shift_left::<Bw128> as fn((Bw128, u32)) -> TestResult); }
        #[test] fn bw256_shift_left() { quickcheck(prop_shift_left::<Bw256> as fn((Bw256, u32)) -> TestResult); }

        fn prop_shift_right<T>((original, n) : (T, u32)) -> TestResult where T: Bigwise {
            if n >= T::size() {
                return TestResult::discard();
            }
            let shifted = original.shift_right(n);
            let v_original : Vec<_> = original.iter().skip(n as usize).collect();
            let v_shifted : Vec<_> = shifted.iter().take((T::size()-n) as usize).collect();
            TestResult::from_bool(v_original == v_shifted)
        }

        #[test] fn bw64_shift_right() { quickcheck(prop_shift_right::<Bw64> as fn((Bw64, u32)) -> TestResult); }
        #[test] fn bw128_shift_right() { quickcheck(prop_shift_right::<Bw128> as fn((Bw128, u32)) -> TestResult); }
        #[test] fn bw256_shift_right() { quickcheck(prop_shift_right::<Bw256> as fn((Bw256, u32)) -> TestResult); }

        fn prop_or<T>(xx: (T, T)) -> bool where T: Bigwise {
            let res = xx.0.or(&xx.1);
            xx.0.iter().zip(xx.1.iter())
                .map(|(x1,x2)| x1 | x2)
                .zip(res.iter())
                .all(|(expected, observed)| expected == observed)
        }

        #[test] fn bw64_or() { quickcheck(prop_or::<Bw64> as fn((Bw64, Bw64)) -> bool); }
        #[test] fn bw128_or() { quickcheck(prop_or::<Bw128> as fn((Bw128, Bw128)) -> bool); }
        #[test] fn bw256_or() { quickcheck(prop_or::<Bw256> as fn((Bw256, Bw256)) -> bool); }
    }
}