xdlol 0.0.0

//! Frequency Analysis
// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at http://mozilla.org/MPL/2.0/.

use std::iter::FromIterator;
use std::collections::hash_map;
use std::collections::HashMap;
use std::borrow::Borrow;
use std::hash::Hash;
use num::{FromPrimitive, One, Unsigned, Zero};
use arithmetic::UnsignedArithmetic;

#[derive(Clone)]
pub struct FrequencyMap<K, V>
where
    K: Hash + Eq,
    V: Unsigned + UnsignedArithmetic,
{
    default: V,
    freq_map: HashMap<K, V>,
}

impl<K, V> FrequencyMap<K, V>
where
    K: Hash + Eq + Copy,
    V: Unsigned + UnsignedArithmetic + Clone + Copy,
{
    /// Creates an empty `FrequencyMap`.
    ///
    /// The map is initially created with a capacity of 0, so it will not allocate until it
    /// is first inserted into.
    ///
    /// # Examples
    ///
    /// ```
    /// use xdlol::statistics::FrequencyMap;
    /// let mut map: FrequencyMap<&str, u32> = FrequencyMap::new();
    /// ```
    #[inline]
    pub fn new() -> Self {
        FrequencyMap {
            default: Zero::zero(),
            freq_map: HashMap::new(),
        }
    }

    /// Creates an empty `FrequencyMap` with the specified capacity.
    ///
    /// The map will be able to hold at least `capacity` elements without
    /// reallocating. If `capacity` is 0, the hash map will not allocate.
    ///
    /// # Examples
    ///
    /// ```
    /// use xdlol::statistics::FrequencyMap;
    /// let mut map: FrequencyMap<&str, u32> = FrequencyMap::with_capacity(10);
    /// ```
    #[inline]
    pub fn with_capacity(capacity: usize) -> FrequencyMap<K, V> {
        FrequencyMap {
            default: Zero::zero(),
            freq_map: HashMap::with_capacity_and_hasher(capacity, Default::default()),
        }
    }

    /// Returns a reference to the frequency of the corresponding key.
    ///
    /// The key may be any borrowed form of the map's key type, but
    /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for
    /// the key type.
    ///
    /// # Examples
    ///
    /// ```
    /// use xdlol::statistics::FrequencyMap;
    ///
    /// let mut map: FrequencyMap<u32, u32> = FrequencyMap::new();
    /// map.insert(1);
    /// assert_eq!(map.get(&1), &1u32);
    /// assert_eq!(map.get(&2), &0u32);
    /// ```
    #[inline]
    pub fn get<Q: ?Sized>(&self, k: &Q) -> &V
    where
        K: Borrow<Q>,
        Q: Hash + Eq,
    {
        self.freq_map.get(k).unwrap_or_else(|| &self.default)
    }

    /// Adds one to the frequency of the key in the map.
    ///
    /// If the map did not have this key present, `0` is returned.
    ///
    /// If the map did have this key present, the value is updated, and the old
    /// value is returned. The key is not updated, though; this matters for
    /// types that can be `==` without being identical.
    ///
    /// # Examples
    ///
    /// ```
    /// use xdlol::statistics::FrequencyMap;
    ///
    /// let mut map: FrequencyMap<u32, u32> = FrequencyMap::new();
    /// assert_eq!(map.insert(42), 1);
    /// assert_eq!(map.insert(42), 2);
    /// ```
    #[inline]
    pub fn insert(&mut self, k: K) -> V {
        *self.freq_map.entry(k).or_insert(Zero::zero()) += One::one();
        self.get(&k).clone()
    }

    /// An iterator visiting all values in arbitrary order.
    /// The iterator element type is `&'a V`.
    ///
    /// # Examples
    ///
    /// ```
    /// use xdlol::statistics::FrequencyMap;
    ///
    /// let mut map: FrequencyMap<&str, u32> = FrequencyMap::new();
    /// map.insert("a");
    /// map.insert("a");
    /// map.insert("b");
    /// map.insert("c");
    ///
    /// for val in map.values() {
    ///     println!("{:?}", val);
    /// }
    /// ```
    pub fn values(&self) -> hash_map::Values<K, V> {
        self.freq_map.values()
    }

    pub fn iter(&self) -> hash_map::Iter<K, V> {
        self.freq_map.iter()
    }
}

// It does not make sense to have a type bigger than `usize` here
// since an iterator can not contain more than that number of items.
//
// FIXME: Make this ``TryFrom`` when it stabalizes.
// ```
//     V::try_form();
// ```
impl<K, V> FromIterator<K> for FrequencyMap<K, V>
where
    K: Hash + Eq + Clone + Copy,
    V: Unsigned + UnsignedArithmetic + FromPrimitive,
{
    fn from_iter<I: IntoIterator<Item = K>>(iter: I) -> Self {
        let mut frequency_map: HashMap<K, V> = HashMap::new();
        let elements: Vec<K> = iter.into_iter().collect();
        for item in elements.iter().cloned() {
            let freq = V::from_usize(elements.iter().filter(|n| *n == &item).count())
                .expect("Can not convert `usize` into V");
            frequency_map.insert(item, freq);
        }
        FrequencyMap {
            default: Zero::zero(),
            freq_map: frequency_map,
        }
    }
}

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

    #[test]
    fn frequency_map_insert_get() {
        let mut freqs: FrequencyMap<u32, u32> = FrequencyMap::new();
        for i in 1..6 {
            freqs.insert(i);
        }
        assert_eq!(&0, freqs.get(&0));
        assert_eq!(&1, freqs.get(&1));
        assert_eq!(&1, freqs.get(&2));
        assert_eq!(&1, freqs.get(&3));
        assert_eq!(&1, freqs.get(&4));
        assert_eq!(&1, freqs.get(&5));
        assert_eq!(&0, freqs.get(&6));

        for i in 1..6 {
            freqs.insert(i);
        }
        assert_eq!(&0, freqs.get(&0));
        assert_eq!(&2, freqs.get(&1));
        assert_eq!(&2, freqs.get(&2));
        assert_eq!(&2, freqs.get(&3));
        assert_eq!(&2, freqs.get(&4));
        assert_eq!(&2, freqs.get(&5));
        assert_eq!(&0, freqs.get(&6));
    }

    #[test]
    fn frequency_map_insert_return() {
        let mut freqs: FrequencyMap<u32, u32> = FrequencyMap::new();
        for i in 1..6 {
            assert_eq!(1, freqs.insert(i));
        }
        for i in 1..6 {
            assert_eq!(2, freqs.insert(i));
        }
    }

    #[test]
    fn frequency_map_from_iter_get() {
        let test_vec: Vec<u32> = vec![1, 2, 3, 4, 5];
        let freqs: FrequencyMap<u32, usize> = test_vec.iter().cloned().collect();
        assert_eq!(&0, freqs.get(&0));
        assert_eq!(&1, freqs.get(&1));
        assert_eq!(&1, freqs.get(&2));
        assert_eq!(&1, freqs.get(&3));
        assert_eq!(&1, freqs.get(&4));
        assert_eq!(&1, freqs.get(&5));
        assert_eq!(&0, freqs.get(&6));
    }
}