use bloomfilter::reexports::bit_vec::BitVec;
use bloomfilter::Bloom;
use std::fmt;
use std::hash::Hash;

#[derive(Debug)]
pub struct Filter<K> {
    capacity: usize,
    resets: usize,
    odd: Option<Bloom<K>>,
    even: Option<Bloom<K>>,
}

impl<K> fmt::Display for Filter<K>
where
    K: Hash,
{
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(
            f,
            "{{ capacity: {}, age: {}, level: {:0.2} }}",
            self.capacity(),
            self.age(),
            self.level()
        )
    }
}

const BLOOM_ITEMS_COUNT_FACTOR: usize = 10;
const BLOOM_FP_RATE: f64 = 0.1;
const BLOOM_LEVEL_LIMIT: f64 = 0.2;
const APPROX_WEIGHT_BITS: usize = 30;

/// Opinionated Bloom filter.
///
/// This is the main struct, implementing a Bloom filter, with a few
/// opinionated options and choices:
///
/// - used 2 filters internally, switches from one to the other to solve aging problem
/// - the only option you have is the capacity, period.
///
/// # Examples
///
/// ```
/// use ofilter::Filter;
/// use std::hash::Hash;
///
/// #[derive(Hash)]
/// struct Obj {
///     some: usize,
///     thing: usize,
/// }
///
/// let mut filter: Filter<Obj> = Filter::new(1_000);
/// let obj = Obj{ some: 1, thing: 2};
///
/// filter.set(&obj); // put object in filter
/// assert!(filter.check(&obj)); // check object is in filter
///
impl<K> Filter<K> {
    pub fn new(capacity: usize) -> Self {
        Filter {
            capacity,
            resets: 0,
            odd: Self::fresh_bloom(capacity),
            even: Self::fresh_bloom(capacity),
        }
    }

    fn fresh_bloom(capacity: usize) -> Option<Bloom<K>> {
        if capacity > 0 {
            let items_count = capacity * BLOOM_ITEMS_COUNT_FACTOR;
            Some(Bloom::new_for_fp_rate(items_count, BLOOM_FP_RATE))
        } else {
            None
        }
    }

    pub fn level(&self) -> f64 {
        let odd_level = self.odd_level();
        let even_level = self.even_level();
        if odd_level < even_level {
            odd_level
        } else {
            even_level
        }
    }

    pub fn age(&self) -> usize {
        self.resets
    }

    fn odd_level(&self) -> f64 {
        match &self.odd {
            Some(odd) => level(odd.bit_vec()),
            None => 0.0,
        }
    }

    fn even_level(&self) -> f64 {
        match &self.even {
            Some(even) => level(even.bit_vec()),
            None => 0.0,
        }
    }

    pub fn capacity(&self) -> usize {
        self.capacity
    }

    pub fn resize(&mut self, capacity: usize) {
        self.capacity = capacity;
    }

    pub fn clear(&mut self) {
        if let Some(odd) = &mut self.odd {
            odd.clear();
        }
        if let Some(even) = &mut self.even {
            even.clear();
        }
    }
}

impl<K> Filter<K>
where
    K: Hash,
{
    pub fn set(&mut self, key: &K) {
        if self.capacity == 0 {
            return;
        }

        let odd_level = match &mut self.odd {
            Some(odd) => {
                odd.set(key);
                level(odd.bit_vec())
            }
            None => 1.0,
        };
        let even_level = match &mut self.even {
            Some(even) => {
                even.set(key);
                level(even.bit_vec())
            }
            None => 1.0,
        };
        if odd_level < 1.0 || even_level < 1.0 {
            return;
        }

        // In case capacity is 0 this will increase very fast, but after
        // all it's logical -> there's no capacity, it's exceeded very fast.
        // Also doing this, when resizing from 0 to something else, the new
        // capacity is immediately used, which is nice.
        self.resets += 1;

        // At this stage both bloom filters are above the accepted level.
        // So they will not perform as well as expected, what we'll do
        // is discard the one which has the highest level, very likely
        // the most used one, but not necessarily. But by doing so we
        // ensure we'll never reach a level of 1.0 (that would mean all
        // bits set to 1, so a wasted filter accepting everything).
        if odd_level > even_level {
            self.odd = Self::fresh_bloom(self.capacity);
        } else {
            self.even = Self::fresh_bloom(self.capacity);
        }
    }

    pub fn check(&self, key: &K) -> bool {
        if self.capacity == 0 {
            return false;
        }
        match &self.odd {
            Some(odd) => {
                if odd.check(key) {
                    true
                } else {
                    match &self.even {
                        Some(even) => even.check(key),
                        None => false,
                    }
                }
            }
            None => false,
        }
    }
}

fn level(bv: &BitVec) -> f64 {
    // In theory we should the manning weight:
    // https://docs.rs/hamming/0.1.3/hamming/fn.weight.html
    // In practice sampling of a few bits is good enough...
    let l = bv.len();
    let n = std::cmp::min(l, APPROX_WEIGHT_BITS);
    if n == 0 {
        return 0f64;
    }
    let mut c: usize = 0;
    for i in 0..n {
        if bv.get(i).unwrap() {
            c += 1;
        }
    }
    c as f64 / (n as f64 * BLOOM_LEVEL_LIMIT)
}

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

    #[test]
    fn test_filter_capacity_0() {
        let filter: Filter<usize> = Filter::new(0);
        assert!(!filter.check(&42));
    }

    #[test]
    fn test_filter_level_avg_dev() {
        let capacities: Vec<usize> = vec![
            1, 2, 5, 8, 10, 100, 200, 500, 800, 1_000, 2_000, 3_000, 4_000, 5_000, 6_000, 7_000,
            8_000, 9_000, 10_000, 20_000, 50_000, 80_000, 100_000, 200_000, 500_000,
        ];
        let n = capacities.len();
        let mut levels: Vec<f64> = Vec::new();
        let mut total: f64 = 0.0;
        for capacity in capacities.into_iter() {
            let mut filter: Filter<usize> = Filter::new(capacity);
            for i in 0..capacity {
                filter.set(&i);
            }
            let level = filter.level();
            total += level;
            levels.push(level);
            println!("capacity: {} -> level: {}", capacity, level);
            // [TODO] fix flaky tests, below, and generally speaking as well.
            // assert_eq!(0, filter.resets, "there should have been no resets");

            // Normally this is even < 1.0 but we tolerate outliers.
            // The idea follows: once we've exactly put the number of keys
            // require to access the filter limit, there should be enough
            // bits set, so the hamming weight increases.
            assert!(level < 2.0, "level must be < 2.0");
        }
        let avg_level = total / n as f64;
        let mut sq: f64 = 0f64;
        for level in levels.into_iter() {
            let diff = level - avg_level;
            sq += diff * diff;
        }
        let dev_level = sq.sqrt() / n as f64;
        println!("level average: {}", avg_level);
        println!("level deviation: {}", dev_level);
        assert!(avg_level < 0.9, "level average must be < 0.9");
        assert!(avg_level > 0.2, "level average must be > 0.2");
        assert!(dev_level < 0.2, "level deviation must be < 0.1");
    }

    #[test]
    fn test_filter_len_ratio() {
        let capacities: Vec<usize> = vec![
            1, 2, 5, 8, 10, 50, 100, 110, 120, 130, 140, 150, 160, 170, 180, 190, 200, 500,
        ];
        let n = capacities.len();
        let mut len_ratios: Vec<f64> = Vec::new();
        let mut total: f64 = 0.0;
        const N: usize = 100;
        for capacity in capacities.into_iter() {
            let mut filter: Filter<usize> = Filter::new(capacity);
            for i in 0..capacity * N {
                filter.set(&i);
            }
            let mut set: HashSet<usize> = HashSet::new();
            for i in 0..capacity * N {
                if filter.check(&i) {
                    set.insert(i);
                }
            }
            let len = set.len();
            let len_ratio = len as f64 / capacity as f64;
            total += len_ratio;
            len_ratios.push(len_ratio);
            println!("capacity: {} -> len: {}", capacity, len);
            assert_ne!(0, filter.resets, "there should have been some resets");
            if capacity >= 50 {
                assert!(len_ratio > 0.8, "len should be at least 80% capacity");
                assert!(len_ratio < 30.0, "len should be less than capacity*30");
            }
        }
        let avg_len_ratio = total as f64 / n as f64;
        let mut sq: f64 = 0.0;
        for len_ratio in len_ratios.into_iter() {
            let diff = len_ratio - avg_len_ratio;
            sq += diff * diff;
        }
        let dev_len_ratio = sq.sqrt() / n as f64;
        println!("len ratio average: {}", avg_len_ratio);
        println!("len ratio deviation: {}", dev_len_ratio);
        assert!(avg_len_ratio > 1.3, "len ratio average must be > 1.3");
        assert!(avg_len_ratio < 10.0, "len ratio average must be < 10.0");
        assert!(dev_len_ratio < 3.0, "len ratio deviation must be < 3.0");
    }

    #[test]
    fn test_keeps_relevant_items() {
        let capacities: Vec<usize> = vec![
            1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100,
        ];
        const N: usize = 1_000;
        for capacity in capacities.into_iter() {
            let mut filter: Filter<usize> = Filter::new(capacity);
            for i in 0..capacity * N {
                filter.set(&i);
            }
            let mut set: HashSet<usize> = HashSet::new();
            for i in 0..capacity * N {
                if filter.check(&i) {
                    set.insert(i);
                }
            }
            let len = set.len();
            assert!(len > capacity, "len should be greater than capacity");
            for i in (capacity * (N - 1))..(capacity * N) {
                assert!(set.contains(&i), "recent keys should be in filter");
            }
        }
    }
}
