use std::collections::HashSet;

/// Backing store for an allowlist.
/// Chosen automatically based on ID density:
/// - Dense sequential IDs  → BitVec (1 bit/slot, cache-friendly, no hashing)
/// - Sparse / large-range IDs → HashSet (general, O(1) average)
enum Inner {
    Bits {
        bits: Vec<u64>,  // each u64 holds 64 slots
        max_id: u64,
    },
    Hash(HashSet<u64>),
}

/// Pre-search allowlist filter. Applied BEFORE scoring — not after.
///
/// Automatically picks the fastest backing structure:
/// - If IDs are dense (bitvec fits in <= 32× raw ID bytes): bitvec, O(1) with a single bit test.
/// - Otherwise: HashSet, O(1) average with hash overhead.
pub struct Allowlist {
    inner: Inner,
    len: usize,
}

impl Allowlist {
    pub fn new(ids: &[u64]) -> Self {
        if ids.is_empty() {
            return Self { inner: Inner::Hash(HashSet::new()), len: 0 };
        }

        let max_id = *ids.iter().max().unwrap();
        // Bitvec word count = (max_id / 64) + 1
        let words_needed = (max_id / 64 + 1) as usize;
        // Use bitvec if it fits in ≤ 32× the raw byte count of the ID list.
        // ids.len() * 8 bytes (u64 each) vs words_needed * 8 bytes (u64 words).
        // Condition: words_needed <= ids.len() * 32
        let use_bits = words_needed <= ids.len().saturating_mul(32)
            && words_needed <= 1 << 20; // cap at 8MB bitvec

        if use_bits {
            let mut bits = vec![0u64; words_needed];
            for &id in ids {
                bits[(id / 64) as usize] |= 1u64 << (id % 64);
            }
            Self { inner: Inner::Bits { bits, max_id }, len: ids.len() }
        } else {
            Self { inner: Inner::Hash(ids.iter().copied().collect()), len: ids.len() }
        }
    }

    #[inline(always)]
    pub fn contains(&self, id: u64) -> bool {
        match &self.inner {
            Inner::Bits { bits, max_id } => {
                if id > *max_id { return false; }
                let word = (id / 64) as usize;
                (bits[word] >> (id % 64)) & 1 == 1
            }
            Inner::Hash(h) => h.contains(&id),
        }
    }

    pub fn len(&self) -> usize { self.len }
    pub fn is_empty(&self) -> bool { self.len == 0 }

    /// True if this allowlist is backed by a bitvec (for testing/diagnostics).
    #[cfg(test)]
    pub fn is_bitvec(&self) -> bool {
        matches!(self.inner, Inner::Bits { .. })
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn membership_hashset() {
        // Sparse IDs → HashSet path
        let al = Allowlist::new(&[1, 2, 5, 100]);
        assert!( al.contains(1));
        assert!( al.contains(100));
        assert!(!al.contains(3));
        assert!(!al.contains(0));
    }

    #[test]
    fn membership_bitvec() {
        // Dense IDs → bitvec path
        let ids: Vec<u64> = (0u64..200).collect();
        let al = Allowlist::new(&ids);
        assert!(al.is_bitvec(), "expected bitvec for dense IDs");
        for id in 0u64..200 {
            assert!(al.contains(id), "should contain {id}");
        }
        assert!(!al.contains(200));
        assert!(!al.contains(999));
    }

    #[test]
    fn bitvec_and_hashset_agree() {
        // Same IDs, verify both paths return identical results
        let ids = vec![0u64, 3, 7, 15, 63, 64, 65, 127, 128];
        let dense  = Allowlist::new(&ids);
        // Force hashset by making IDs very sparse
        let sparse_ids: Vec<u64> = ids.iter().map(|&x| x * 100_000).collect();
        let sparse = Allowlist::new(&sparse_ids);

        for &id in &ids {
            assert!(dense.contains(id), "dense should contain {id}");
        }
        for &id in &sparse_ids {
            assert!(sparse.contains(id), "sparse should contain {id}");
        }
        assert!(!dense.contains(1000));
        assert!(!sparse.contains(1));
    }

    #[test]
    fn empty_allowlist() {
        let al = Allowlist::new(&[]);
        assert!(al.is_empty());
        assert!(!al.contains(0));
        assert!(!al.contains(u64::MAX));
    }

    #[test]
    fn single_id() {
        let al = Allowlist::new(&[42]);
        assert!(al.contains(42));
        assert!(!al.contains(41));
        assert!(!al.contains(43));
    }

    #[test]
    fn bitvec_word_boundary() {
        // IDs right at u64 word boundaries (63, 64, 127, 128)
        let ids = vec![63u64, 64, 127, 128];
        let al = Allowlist::new(&ids);
        assert!(al.contains(63));
        assert!(al.contains(64));
        assert!(al.contains(127));
        assert!(al.contains(128));
        assert!(!al.contains(62));
        assert!(!al.contains(65));
    }

    #[test]
    fn large_dense_uses_bitvec() {
        let ids: Vec<u64> = (0u64..1000).collect();
        let al = Allowlist::new(&ids);
        assert!(al.is_bitvec());
        assert_eq!(al.len(), 1000);
    }
}
