use std::fmt::{self, Debug, Write};
use std::marker::PhantomData;
use std::{mem, slice};

#[cfg(test)]
mod tests;

mod hybrid;
pub mod matrix;
mod sparse;

pub use hybrid::{HybridBitSet, HybridIter};
pub use matrix::{BitMatrix, GrowableSparseBitMatrix, SparseBitMatrix};
pub use sparse::SparseBitSet;
use sparse::SPARSE_MAX;

pub type Word = u64;
pub const WORD_BYTES: usize = mem::size_of::<Word>();
pub const WORD_BITS: usize = WORD_BYTES * 8;

/// A fixed-size bitset type with a dense representation.
///
/// NOTE: Use [`GrowableBitSet`] if you need support for resizing after creation.
///
/// `T` is an index type, typically a newtyped `usize` wrapper, but it can also
/// just be `usize`.
///
/// All operations that involve an element will panic if the element is equal
/// to or greater than the domain size. All operations that involve two bitsets
/// will panic if the bitsets have differing domain sizes.
///
#[derive(PartialEq, Eq)]
pub struct BitSet<T> {
    domain_size: usize,
    words: Vec<Word>,
    marker: PhantomData<T>,
}

impl<T> Default for BitSet<T> {
    fn default() -> Self {
        Self { domain_size: 0, words: Vec::new(), marker: PhantomData }
    }
}

impl<T> BitSet<T> {
    /// Gets the domain size.
    pub fn domain_size(&self) -> usize {
        self.domain_size
    }
}

impl<T: From<usize> + Into<usize> + Copy + PartialEq + Debug> BitSet<T> {
    /// Creates a new, empty bitset with a given `domain_size`.
    #[inline]
    pub fn new_empty(domain_size: usize) -> BitSet<T> {
        let num_words = num_words(domain_size);
        BitSet { domain_size, words: vec![0; num_words], marker: PhantomData }
    }

    /// Creates a new, filled bitset with a given `domain_size`.
    #[inline]
    pub fn new_filled(domain_size: usize) -> BitSet<T> {
        let num_words = num_words(domain_size);
        let mut result = BitSet { domain_size, words: vec![!0; num_words], marker: PhantomData };
        result.clear_excess_bits();
        result
    }

    /// Clear all elements.
    #[inline]
    pub fn clear(&mut self) {
        for word in &mut self.words {
            *word = 0;
        }
    }

    /// Clear excess bits in the final word.
    fn clear_excess_bits(&mut self) {
        let num_bits_in_final_word = self.domain_size % WORD_BITS;
        if num_bits_in_final_word > 0 {
            let mask = (1 << num_bits_in_final_word) - 1;
            let final_word_idx = self.words.len() - 1;
            self.words[final_word_idx] &= mask;
        }
    }

    pub fn copy_from(&mut self, other: &Self) {
        self.words.copy_from_slice(&other.words)
    }

    pub fn copy_from_hybrid<const CLEAR: bool>(&mut self, other: &HybridBitSet<T>) {
        match other {
            HybridBitSet::Sparse(src) => {
                if CLEAR {
                    self.clear()
                }
                for i in src.iter() {
                    self.insert(*i);
                }
            }
            HybridBitSet::Dense(other) => self.copy_from(other),
        }
    }

    /// Count the number of set bits in the set.
    pub fn count(&self) -> usize {
        self.words.iter().map(|e| e.count_ones() as usize).sum()
    }

    /// Returns `true` if `self` contains `elem`.
    #[inline]
    pub fn contains(&self, elem: T) -> bool {
        let (word_index, mask) = word_index_and_mask(elem);
        (self.words[word_index] & mask) != 0
    }

    /// Is `self` is a (non-strict) superset of `other`?
    #[inline]
    pub fn superset(&self, other: &BitSet<T>) -> bool {
        self.words.iter().zip(&other.words).all(|(a, b)| (a & b) == *b)
    }

    /// Is the set empty?
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.words.iter().all(|a| *a == 0)
    }

    /// Insert `elem`. Returns whether the set has changed.
    #[inline]
    pub fn insert(&mut self, elem: T) -> bool {
        let (word_index, mask) = word_index_and_mask(elem);
        let word_ref = &mut self.words[word_index];
        let word = *word_ref;
        let new_word = word | mask;
        *word_ref = new_word;
        new_word != word
    }

    /// Sets all bits to true.
    pub fn insert_all(&mut self) {
        for word in &mut self.words {
            *word = !0;
        }
        self.clear_excess_bits();
    }

    pub fn inverse(&mut self) {
        for word in &mut self.words {
            *word = !*word;
        }
        self.clear_excess_bits();
    }

    /// Returns `true` if the set has changed.
    #[inline]
    pub fn remove(&mut self, elem: T) -> bool {
        let (word_index, mask) = word_index_and_mask(elem);
        let word_ref = &mut self.words[word_index];
        let word = *word_ref;
        let new_word = word & !mask;
        *word_ref = new_word;
        new_word != word
    }

    /// Sets `self = self | other` and returns `true` if `self` changed
    /// (i.e., if new bits were added).
    pub fn union(&mut self, other: &impl UnionIntoBitSet<T>) -> bool {
        other.union_into(self)
    }

    /// Sets `self = self - other` and returns `true` if `self` changed.
    /// (i.e., if any bits were removed).
    pub fn subtract(&mut self, other: &impl SubtractFromBitSet<T>) -> bool {
        other.subtract_from(self)
    }

    /// Sets `self = self & other` and return `true` if `self` changed.
    /// (i.e., if any bits were removed).
    pub fn intersect(&mut self, other: &BitSet<T>) -> bool {
        bitwise(&mut self.words, &other.words, |a, b| a & b)
    }

    /// Gets a slice of the underlying words.
    pub fn words(&self) -> &[Word] {
        &self.words
    }

    /// Iterates over the indices of set bits in a sorted order.
    #[inline]
    pub fn iter(&self) -> BitIter<'_, T> {
        BitIter::new(&self.words)
    }

    /// Duplicates the set as a hybrid set.
    pub fn to_hybrid(&self) -> HybridBitSet<T> {
        // Note: we currently don't bother trying to make a Sparse set.
        if self.count() <= SPARSE_MAX {
            let mut res = SparseBitSet::new_empty();
            for val in self.iter() {
                res.insert(val);
            }
            HybridBitSet::Sparse(res)
        } else {
            HybridBitSet::Dense(self.to_owned())
        }
    }

    /// Set `self = self | other`. In contrast to `union` returns `true` if the set contains at
    /// least one bit that is not in `other` (i.e. `other` is not a superset of `self`).
    ///
    /// This is an optimization for union of a hybrid bitset.
    fn reverse_union_sparse(&mut self, sparse: &SparseBitSet<T>) -> bool {
        self.clear_excess_bits();

        let mut not_already = false;
        // Index of the current word not yet merged.
        let mut current_index = 0;
        // Mask of bits that came from the sparse set in the current word.
        let mut new_bit_mask = 0;
        for (word_index, mask) in sparse.iter().map(|x| word_index_and_mask(*x)) {
            // Next bit is in a word not inspected yet.
            if word_index > current_index {
                self.words[current_index] |= new_bit_mask;
                // Were there any bits in the old word that did not occur in the sparse set?
                not_already |= (self.words[current_index] ^ new_bit_mask) != 0;
                // Check all words we skipped for any set bit.
                not_already |= self.words[current_index + 1..word_index].iter().any(|&x| x != 0);
                // Update next word.
                current_index = word_index;
                // Reset bit mask, no bits have been merged yet.
                new_bit_mask = 0;
            }
            // Add bit and mark it as coming from the sparse set.
            // self.words[word_index] |= mask;
            new_bit_mask |= mask;
        }
        self.words[current_index] |= new_bit_mask;
        // Any bits in the last inspected word that were not in the sparse set?
        not_already |= (self.words[current_index] ^ new_bit_mask) != 0;
        // Any bits in the tail? Note `clear_excess_bits` before.
        not_already |= self.words[current_index + 1..].iter().any(|&x| x != 0);

        not_already
    }

    /// Ensure that the set can hold at least `min_domain_size` elements.
    pub fn ensure(&mut self, min_domain_size: usize) {
        if self.domain_size < min_domain_size {
            self.domain_size = min_domain_size;
        } else {
            return;
        }

        let min_num_words = num_words(min_domain_size);
        if self.words.len() < min_num_words {
            self.words.resize(min_num_words, 0)
        }
    }

    pub fn set_size_enable(&mut self, domain_size: usize) {
        self.domain_size = domain_size;
        let num_words = num_words(domain_size);
        self.words.resize(num_words, u64::MAX);
        self.insert_all();
    }
}

impl<T> Extend<T> for BitSet<T>
where
    T: From<usize> + Into<usize> + Copy + PartialEq + Debug,
{
    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        for x in iter {
            self.insert(x);
        }
    }
}

/// This is implemented by all the bitsets so that BitSet::union() can be
/// passed any type of bitset.
pub trait UnionIntoBitSet<T>
where
    T: From<usize> + Into<usize> + Copy + PartialEq + Debug,
{
    // Performs `other = other | self`.
    fn union_into(&self, other: &mut BitSet<T>) -> bool;
}

/// This is implemented by all the bitsets so that BitSet::subtract() can be
/// passed any type of bitset.
pub trait SubtractFromBitSet<T>
where
    T: From<usize> + Into<usize> + Copy + PartialEq + Debug,
{
    // Performs `other = other - self`.
    fn subtract_from(&self, other: &mut BitSet<T>) -> bool;
}

/// This is implemented by all the bitsets so that BitSet::union() can be
/// passed any type of bitset.
pub trait UnionIntoHybridBitSet<T>
where
    T: From<usize> + Into<usize> + Copy + PartialEq + Debug,
{
    // Performs `other = other | self`.
    fn union_into(&self, other: &mut HybridBitSet<T>, domain_size: usize) -> bool;
}

pub trait FullBitSetOperations<T>:
    SubtractFromHybridBitSet<T> + UnionIntoHybridBitSet<T> + SubtractFromBitSet<T> + UnionIntoBitSet<T>
where
    T: From<usize> + Into<usize> + Copy + PartialEq + Debug,
{
}

impl<T, Set> FullBitSetOperations<T> for Set
where
    Set: SubtractFromHybridBitSet<T>
        + UnionIntoHybridBitSet<T>
        + SubtractFromBitSet<T>
        + UnionIntoBitSet<T>,
    T: From<usize> + Into<usize> + Copy + PartialEq + Debug,
{
}

/// This is implemented by all the bitsets so that BitSet::subtract() can be
/// passed any type of bitset.
pub trait SubtractFromHybridBitSet<T>
where
    T: From<usize> + Into<usize> + Copy + PartialEq + Debug,
{
    // Performs `other = other - self`.
    fn subtract_from_h(&self, other: &mut HybridBitSet<T>) -> bool;
}

impl<T> UnionIntoBitSet<T> for BitSet<T>
where
    T: From<usize> + Into<usize> + Copy + PartialEq + Debug,
{
    fn union_into(&self, other: &mut BitSet<T>) -> bool {
        bitwise(&mut other.words, &self.words, |a, b| a | b)
    }
}

impl<T> SubtractFromBitSet<T> for BitSet<T>
where
    T: From<usize> + Into<usize> + Copy + PartialEq + Debug,
{
    fn subtract_from(&self, other: &mut BitSet<T>) -> bool {
        bitwise(&mut other.words, &self.words, |a, b| a & !b)
    }
}

impl<T> Clone for BitSet<T> {
    fn clone(&self) -> Self {
        BitSet { domain_size: self.domain_size, words: self.words.clone(), marker: PhantomData }
    }

    fn clone_from(&mut self, from: &Self) {
        if self.domain_size != from.domain_size {
            self.words.resize(from.domain_size, 0);
            self.domain_size = from.domain_size;
        }

        self.words.copy_from_slice(&from.words);
    }
}

impl<T> fmt::Debug for BitSet<T>
where
    T: From<usize> + Into<usize> + Copy + PartialEq + Debug + Debug,
{
    fn fmt(&self, w: &mut fmt::Formatter<'_>) -> fmt::Result {
        w.debug_list().entries(self.iter()).finish()
    }
}

impl<T> ToString for BitSet<T>
where
    T: From<usize> + Into<usize> + Copy + PartialEq + Debug,
{
    fn to_string(&self) -> String {
        let mut result = String::new();
        let mut sep = '[';

        // Note: this is a little endian printout of bytes.

        // i tracks how many bits we have printed so far.
        let mut i = 0;
        for word in &self.words {
            let mut word = *word;
            for _ in 0..WORD_BYTES {
                // for each byte in `word`:
                let remain = self.domain_size - i;
                // If less than a byte remains, then mask just that many bits.
                let mask = if remain <= 8 { (1 << remain) - 1 } else { 0xFF };
                assert!(mask <= 0xFF);
                let byte = word & mask;

                write!(result, "{}{:02x}", sep, byte).unwrap();

                if remain <= 8 {
                    break;
                }
                word >>= 8;
                i += 8;
                sep = '-';
            }
            sep = '|';
        }
        result.push(']');

        result
    }
}

pub struct BitIter<'a, T: From<usize> + Into<usize> + Copy + PartialEq + Debug> {
    /// A copy of the current word, but with any already-visited bits cleared.
    /// (This lets us use `trailing_zeros()` to find the next set bit.) When it
    /// is reduced to 0, we move onto the next word.
    word: Word,

    /// The offset (measured in bits) of the current word.
    offset: usize,

    /// Underlying iterator over the words.
    iter: slice::Iter<'a, Word>,

    marker: PhantomData<T>,
}

impl<'a, T: From<usize> + Into<usize> + Copy + PartialEq + Debug> BitIter<'a, T> {
    #[inline]
    fn new(words: &'a [Word]) -> BitIter<'a, T> {
        // We initialize `word` and `offset` to degenerate values. On the first
        // call to `next()` we will fall through to getting the first word from
        // `iter`, which sets `word` to the first word (if there is one) and
        // `offset` to 0. Doing it this way saves us from having to maintain
        // additional state about whether we have started.
        BitIter {
            word: 0,
            offset: usize::MAX - (WORD_BITS - 1),
            iter: words.iter(),
            marker: PhantomData,
        }
    }
}

impl<'a, T: From<usize> + Into<usize> + Copy + PartialEq + Debug> Iterator for BitIter<'a, T> {
    type Item = T;
    fn next(&mut self) -> Option<T> {
        loop {
            if self.word != 0 {
                // Get the position of the next set bit in the current word,
                // then clear the bit.
                let bit_pos = self.word.trailing_zeros() as usize;
                let bit = 1 << bit_pos;
                self.word ^= bit;
                return Some(T::from(bit_pos + self.offset));
            }

            // Move onto the next word. `wrapping_add()` is needed to handle
            // the degenerate initial value given to `offset` in `new()`.
            let word = self.iter.next()?;
            self.word = *word;
            self.offset = self.offset.wrapping_add(WORD_BITS);
        }
    }
}

#[inline]
fn bitwise<Op>(out_vec: &mut [Word], in_vec: &[Word], op: Op) -> bool
where
    Op: Fn(Word, Word) -> Word,
{
    let out_vec = &mut out_vec[..in_vec.len()];
    let mut changed = 0;
    for (out_elem, in_elem) in out_vec.iter_mut().zip(in_vec) {
        let old_val = *out_elem;
        let new_val = op(old_val, *in_elem);
        *out_elem = new_val;
        // This is essentially equivalent to a != with changed being a bool, but
        // in practice this code gets auto-vectorized by the compiler for most
        // operators. Using != here causes us to generate quite poor code as the
        // compiler tries to go back to a boolean on each loop iteration.
        changed |= old_val ^ new_val;
    }
    changed != 0
}

/// A resizable bitset type with a dense representation.
///
/// `T` is an index type, typically a newtyped `usize` wrapper, but it can also
/// just be `usize`.
///
/// All operations that involve an element will panic if the element is equal
/// to or greater than the domain size.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct GrowableBitSet<T: From<usize> + Into<usize> + Copy + PartialEq + Debug> {
    bit_set: BitSet<T>,
}

impl<T: From<usize> + Into<usize> + Copy + PartialEq + Debug> GrowableBitSet<T> {
    pub fn new_empty() -> GrowableBitSet<T> {
        GrowableBitSet { bit_set: BitSet::new_empty(0) }
    }

    pub fn ensure(&mut self, size: usize) {
        self.bit_set.ensure(size)
    }

    pub fn with_capacity(capacity: usize) -> GrowableBitSet<T> {
        GrowableBitSet { bit_set: BitSet::new_empty(capacity) }
    }

    /// Returns `true` if the set has changed.
    #[inline]
    pub fn insert(&mut self, elem: T) -> bool {
        self.bit_set.ensure(elem.into() + 1);
        self.bit_set.insert(elem)
    }

    /// Returns `true` if the set has changed.
    #[inline]
    pub fn remove(&mut self, elem: T) -> bool {
        self.bit_set.ensure(elem.into() + 1);
        self.bit_set.remove(elem)
    }

    #[inline]
    pub fn is_empty(&self) -> bool {
        self.bit_set.is_empty()
    }

    #[inline]
    pub fn contains(&self, elem: T) -> bool {
        let (word_index, mask) = word_index_and_mask(elem);
        if let Some(word) = self.bit_set.words.get(word_index) {
            (word & mask) != 0
        } else {
            false
        }
    }
}

#[inline]
fn num_words<T: Into<usize>>(domain_size: T) -> usize {
    (domain_size.into() + WORD_BITS - 1) / WORD_BITS
}

#[inline]
fn word_index_and_mask<T: Into<usize>>(elem: T) -> (usize, Word) {
    let elem = elem.into();
    let word_index = elem / WORD_BITS;
    let mask = 1 << (elem % WORD_BITS);
    (word_index, mask)
}

// /// Integral type used to represent the bit set.
// pub trait FiniteBitSetTy:
//     BitAnd<Output = Self>
//     + BitAndAssign
//     + BitOrAssign
//     + Clone
//     + Copy
//     + Shl
//     + Not<Output = Self>
//     + PartialEq
//     + Sized
// {
//     /// Size of the domain representable by this type, e.g. 64 for `u64`.
//     const DOMAIN_SIZE: u32;

//     /// Value which represents the `FiniteBitSet` having every bit set.
//     const FILLED: Self;
//     /// Value which represents the `FiniteBitSet` having no bits set.
//     const EMPTY: Self;

//     /// Value for one as the integral type.
//     const ONE: Self;
//     /// Value for zero as the integral type.
//     const ZERO: Self;

//     /// Perform a checked left shift on the integral type.
//     fn checked_shl(self, rhs: u32) -> Option<Self>;
//     /// Perform a checked right shift on the integral type.
//     fn checked_shr(self, rhs: u32) -> Option<Self>;
// }

// impl FiniteBitSetTy for u32 {
//     const DOMAIN_SIZE: u32 = 32;

//     const FILLED: Self = Self::MAX;
//     const EMPTY: Self = Self::MIN;

//     const ONE: Self = 1u32;
//     const ZERO: Self = 0u32;

//     fn checked_shl(self, rhs: u32) -> Option<Self> {
//         self.checked_shl(rhs)
//     }

//     fn checked_shr(self, rhs: u32) -> Option<Self> {
//         self.checked_shr(rhs)
//     }
// }

// impl std::fmt::Debug for FiniteBitSet<u32> {
//     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
//         write!(f, "{:032b}", self.0)
//     }
// }

// impl FiniteBitSetTy for u64 {
//     const DOMAIN_SIZE: u32 = 64;

//     const FILLED: Self = Self::MAX;
//     const EMPTY: Self = Self::MIN;

//     const ONE: Self = 1u64;
//     const ZERO: Self = 0u64;

//     fn checked_shl(self, rhs: u32) -> Option<Self> {
//         self.checked_shl(rhs)
//     }

//     fn checked_shr(self, rhs: u32) -> Option<Self> {
//         self.checked_shr(rhs)
//     }
// }

// impl std::fmt::Debug for FiniteBitSet<u64> {
//     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
//         write!(f, "{:064b}", self.0)
//     }
// }

// impl FiniteBitSetTy for u128 {
//     const DOMAIN_SIZE: u32 = 128;

//     const FILLED: Self = Self::MAX;
//     const EMPTY: Self = Self::MIN;

//     const ONE: Self = 1u128;
//     const ZERO: Self = 0u128;

//     fn checked_shl(self, rhs: u32) -> Option<Self> {
//         self.checked_shl(rhs)
//     }

//     fn checked_shr(self, rhs: u32) -> Option<Self> {
//         self.checked_shr(rhs)
//     }
// }

// impl std::fmt::Debug for FiniteBitSet<u128> {
//     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
//         write!(f, "{:0128b}", self.0)
//     }
// }

// /// A fixed-sized bitset type represented by an integer type. Indices outwith than the range
// /// representable by `T` are considered set.
// #[derive(Copy, Clone, Eq, PartialEq)]
// pub struct FiniteBitSet<T: FiniteBitSetTy>(pub T);

// impl<T: FiniteBitSetTy> FiniteBitSet<T> {
//     /// Creates a new, empty bitset.
//     pub fn new_empty() -> Self {
//         Self(T::EMPTY)
//     }

//     /// Sets the `index`th bit.
//     pub fn set(&mut self, index: u32) {
//         self.0 |= T::ONE.checked_shl(index).unwrap_or(T::ZERO);
//     }

//     /// Unsets the `index`th bit.
//     pub fn clear(&mut self, index: u32) {
//         self.0 &= !T::ONE.checked_shl(index).unwrap_or(T::ZERO);
//     }

//     /// Sets the `i`th to `j`th bits.
//     pub fn set_range(&mut self, range: Range<u32>) {
//         let bits = T::FILLED
//             .checked_shl(range.end - range.start)
//             .unwrap_or(T::ZERO)
//             .not()
//             .checked_shl(range.start)
//             .unwrap_or(T::ZERO);
//         self.0 |= bits;
//     }

//     /// Is the set empty?
//     pub fn is_empty(&self) -> bool {
//         self.0 == T::EMPTY
//     }

//     /// Returns the domain size of the bitset.
//     pub fn within_domain(&self, index: u32) -> bool {
//         index < T::DOMAIN_SIZE
//     }

//     /// Returns if the `index`th bit is set.
//     pub fn contains(&self, index: u32) -> Option<bool> {
//         self.within_domain(index)
//             .then(|| ((self.0.checked_shr(index).unwrap_or(T::ONE)) & T::ONE) == T::ONE)
//     }
// }

// impl<T: FiniteBitSetTy> Default for FiniteBitSet<T> {
//     fn default() -> Self {
//         Self::new_empty()
//     }
// }
