bigwise 0.4.0

use Bigwise;
use BitsIter;
use std::fmt::{self, Debug, Formatter};
use std::ops::{BitAnd, BitOr, BitXor, Not, Shl, Shr};
use rand::{Rand, Rng};

/// 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, Hash, Default, Ord, PartialOrd)]
pub struct BwPair<T: Bigwise> {
    left: T,
    right: T,
}

impl <T: Bigwise> Bigwise for BwPair<T> {

    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 rotate_left(self, n: u32) -> Self {
        let n = n % Self::size();
        if n == 0 {
            self
        } else if n < T::size() {
            let p = T::size() - n;
            BwPair {
                left: (self.left << n) | (self.right >> p),
                right: (self.right << n) | (self.left >> p),
            }
        } else if n == T::size() {
            BwPair {
                left: self.right,
                right: self.left,
            }
        } else {
            let p = n - T::size();
            let q = T::size() - p;
            BwPair {
                left: (self.right << p) | (self.left >> q),
                right: (self.left << p) | (self.right >> q),
            }
        }
    }

    fn rotate_right(self, n: u32) -> Self {
        let n = n % Self::size();
        if n == 0 {
            self
        } else if n < T::size() {
            let p = T::size() - n;
            BwPair {
                left: (self.left >> n) | (self.right << p),
                right: (self.right >> n) | (self.left << p),
            }
        } else if n == T::size() {
            BwPair {
                left: self.right,
                right: self.left,
            }
        } else {
            let p = n - T::size();
            let q = T::size() - p;
            BwPair {
                left: (self.right >> p) | (self.left << q),
                right: (self.left >> p) | (self.right << q),
            }
        }
    }
}

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: Bigwise> Debug for BwPair<T> {
    fn fmt(&self, f: &mut Formatter) -> Result<(), fmt::Error> {
        try!(self.left.fmt(f));
        try!(self.right.fmt(f));
        Ok(())
    }
}

impl<T: Bigwise> BitAnd for BwPair<T> {

    type Output = Self;

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

impl<T: Bigwise> BitOr for BwPair<T> {

    type Output = Self;

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

impl<T: Bigwise> BitXor for BwPair<T> {

    type Output = Self;

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

impl<T: Bigwise> Not for BwPair<T> {

    type Output = Self;

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

impl<T: Bigwise> Shl<u32> for BwPair<T> {

    type Output = Self;

    fn shl(self, rhs: u32) -> Self {
        if rhs == 0 {
            self
        } else if rhs < T::size() {
            let p = T::size() - rhs;
            BwPair {
                left: (self.left << rhs) | (self.right >> p),
                right: self.right << rhs,
            }
        } else if rhs == T::size() {
            BwPair {
                left: self.right,
                right: T::empty(),
            }
        } else if rhs < Self::size() {
            let q = rhs - T::size();
            BwPair {
                left: self.right << q,
                right: T::empty(),
            }
        } else {
            BwPair {
                left: T::empty(),
                right: T::empty(),
            }
        }
    }
}

impl<T: Bigwise> Shr<u32> for BwPair<T> {

    type Output = Self;

    fn shr(self, rhs: u32) -> Self {
        if rhs == 0 {
            self
        } else if rhs < T::size() {
            let p = T::size() - rhs;
            BwPair {
                left: self.left >> rhs,
                right: (self.right >> rhs) | (self.left << p),
            }
        } else if rhs == T::size() {
            BwPair {
                left: T::empty(),
                right: self.left,
            }
        } else if rhs < Self::size() {
            let q = rhs - T::size();
            BwPair {
                left: T::empty(),
                right: self.left >> q,
            }
        } else {
            BwPair {
                left: T::empty(),
                right: T::empty(),
            }
        }
    }
}

/// An iterator over the bits.
///
/// Bits are iterated from the least significant one to the most
/// significant one.
///
/// # Examples
///
/// ```
/// use bigwise::{Bigwise, Bw64};
/// let b = Bw64::from_bytes(&[0b11111000]);
/// let mut it = b.into_iter();
/// assert_eq!(Some(false), it.next());
/// assert_eq!(Some(false), it.next());
/// assert_eq!(Some(false), it.next());
/// assert_eq!(Some(true), it.next());
/// assert_eq!(Some(true), it.next());
/// assert_eq!(Some(true), it.next());
/// assert_eq!(Some(true), it.next());
/// assert_eq!(Some(true), it.next());
/// assert_eq!(Some(false), it.next());
/// assert_eq!(Some(false), it.next());
/// assert!(it.take(200).all(|v| v == false));
/// ```
///
impl<T: Bigwise> IntoIterator for BwPair<T> {
    type Item = bool;
    type IntoIter = BitsIter<Self>;

    fn into_iter(self) -> Self::IntoIter {
        BitsIter::new(self)
    }
}