//! The [`Frequency`][frequency] trait represents types that keep track of the 
//! observed counts of items. The [`HashMapFrequency`][hashmapfrequency] type
//! is a frequency counter backed by a [`HashMap`][hashmap].
//!
//! # Usage
//! Add [`frequency`][freq_crate] and `frequency-hashmap` to your `Cargo.toml`:
//!
//! ```
//! [dependencies]
//! frequency = "^1.0.0"
//! frequency-hashmap = "^1.0.0"
//! ```
//!
//! Import both [`Frequency`][frequency] and 
//! [`HashMapFrequency`][hashmapfrequency]:
//!
//! ```
//! extern crate frequency;
//! extern crate frequency_hashmap;
//!
//! use frequency::Frequency;
//! use frequency_hashmap::HashMapFrequency;
//! ```
//!
//! [freq_crate]: https://docs.rs/frequency/~1/
//! [frequency]: https://docs.rs/frequency/~1/frequency/trait.Frequency.html
//! [hashmapfrequency]: struct.HashMapFrequency.html
//! [hashmap]: https://doc.rust-lang.org/std/collections/struct.HashMap.html

extern crate frequency;
extern crate fnv;
extern crate num_traits;

use frequency::Frequency;
use fnv::FnvBuildHasher;
use num_traits::{Num, One, Zero};
use std::hash::Hash;
use std::iter::FromIterator;
use std::hash::BuildHasher;
use std::collections::hash_map::{Iter, Keys, Values, HashMap};

/// A frequency counter backed by a [`HashMap`][hashmap].
/// [hashmap]: https://doc.rust-lang.org/std/collections/struct.HashMap.html
pub struct HashMapFrequency<T, N=usize, S=FnvBuildHasher>
    where T: Hash + Eq,
          N: Num,
          S: BuildHasher
{
    frequency: HashMap<T, N, S>,
}

impl<'t, T, N, S> Frequency<'t, T> for HashMapFrequency<T, N, S>
    where T: 't + Eq + Hash,
          N: 't + Num + Clone,
          S: 't + BuildHasher
{
    type N      = N;
    type Iter   = Iter<'t, T, Self::N>;
    type Items  = Keys<'t, T, Self::N>;
    type Counts = Values<'t, T, Self::N>;

    #[inline]
    fn count(&self, key: &T) -> Self::N {
        self.frequency.get(key).cloned().unwrap_or_else(Zero::zero)
    }

    #[inline]
    fn increment(&mut self, value: T) {
        let value = self.frequency.entry(value).or_insert_with(Zero::zero);
        *value = value.clone() + One::one();
    }

    #[inline]
    fn iter(&'t self) -> Self::Iter {
        self.frequency.iter()
    }

    #[inline]
    fn items(&'t self) -> Self::Items {
        self.frequency.keys()
    }

    #[inline]
    fn counts(&'t self) -> Self::Counts {
        self.frequency.values()
    }
}

impl<T, N, S> HashMapFrequency<T, N, S>
    where T: Eq + Hash,
          N: Num,
          S: BuildHasher + Default
{
    /// Creates an empty `HashMapFrequency`, a frequency counter backed
    /// by a HashMap.
    #[inline]
    pub fn new() -> HashMapFrequency<T, N, S> {
        Default::default()
    }

    /// Creates an empty `HashMapFrequency`, a frequency counter backed
    /// by a HashMap with the specified capacity.
    ///
    /// The hash map will be able to hold at least `capacity` elements without
    /// reallocating. If `capacity` is 0, the hash map will not allocate.
    /// ```
    #[inline]
    pub fn with_capacity(capacity: usize) -> HashMapFrequency<T, N, S> {
        HashMapFrequency::with_capacity_and_hasher(capacity, Default::default())
    }
}

impl<T, N, S> HashMapFrequency<T, N, S>
    where T: Eq + Hash,
          N: Num,
          S: BuildHasher
{
    /// Creates an empty `HashMapFrequency`, a frequency counter backed
    /// by a HashMap which will use the given hash builder to hash
    /// keys.
    ///
    /// The created map has the default initial capacity.
    ///
    /// Warning: `hash_builder` is normally randomly generated, and
    /// is designed to allow HashMaps to be resistant to attacks that
    /// cause many collisions and very poor performance. Setting it
    /// manually using this function can expose a DoS attack vector.
    /// ```
    #[inline]
    pub fn with_hasher(hash_builder: S) -> HashMapFrequency<T, N, S> {
        HashMapFrequency {
            frequency: HashMap::with_hasher(hash_builder)
        }
    }

    /// Creates an empty `HashMapFrequency`, a frequency counter backed
    /// by a HashMap with the specified capacity, using `hasher`
    /// to hash the keys.
    ///
    /// The hash map will be able to hold at least `capacity` elements without
    /// reallocating. If `capacity` is 0, the hash map will not allocate.
    /// Warning: `hasher` is normally randomly generated, and
    /// is designed to allow HashMaps to be resistant to attacks that
    /// cause many collisions and very poor performance. Setting it
    /// manually using this function can expose a DoS attack vector.
    #[inline]
    pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> HashMapFrequency<T, N, S> {
        HashMapFrequency {
            frequency: HashMap::with_capacity_and_hasher(capacity, hash_builder)
        }
    }

    /// Returns the number of elements that have been counted.
    #[inline]
    pub fn len(&self) -> usize {
        self.frequency.len()
    }

    /// Returns true if the counter contains no elements.
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Reserves capacity for at least `additional` more elements to be inserted
    /// in the `HashMap` backing this frequency counter. The collection may 
    /// reserve more space to avoid frequent reallocations.
    ///
    /// # Panics
    ///
    /// Panics if the new allocation size overflows [`usize`].
    ///
    /// [`usize`]: ../../std/primitive.usize.html
    /// ```
    #[inline]
    pub fn reserve(&mut self, additional: usize) {
        self.frequency.reserve(additional)
    }
}

impl<T, N, S> Default for HashMapFrequency<T, N, S>
    where T: Eq + Hash,
          N: Num,
          S: BuildHasher + Default
{
    /// Creates an empty `HashMapFrequency<T, V, S>`, a frequency counter backed
    /// by a HashMap with the `Default` value for the hasher.
    fn default() -> HashMapFrequency<T, N, S> {
        HashMapFrequency::with_hasher(Default::default())
    }
}

impl<T, N, S> Extend<T> for HashMapFrequency<T, N, S>
    where T: Eq + Hash,
          N: Num + Clone,
          S: BuildHasher
{
    fn extend<I: IntoIterator<Item=T>>(&mut self, iter: I) {
        // Keys may be already present or show multiple times in the iterator.
        // Reserve the entire hint lower bound if the map is empty.
        // Otherwise reserve half the hint (rounded up), so the map
        // will only resize twice in the worst case.
        let iter = iter.into_iter();
        let reserve = if self.is_empty() {
            iter.size_hint().0
        } else {
            (iter.size_hint().0 + 1) / 2
        };
        self.reserve(reserve);
        for k in iter {
            self.increment(k);
        }
    }
}

impl<T, N, S> FromIterator<T> for HashMapFrequency<T, N, S>
    where T: Eq + Hash,
          N: Num + Clone,
          S: BuildHasher + Default
{
    fn from_iter<I: IntoIterator<Item=T>>(iter: I) -> Self {
        let mut frequency = HashMapFrequency::default();
        frequency.extend(iter);
        frequency
    }
}

impl<'t, T, N, S> IntoIterator for &'t HashMapFrequency<T, N, S>
    where T: 't + Eq + Hash,
          N: 't + Num + Clone,
          S: 't + BuildHasher
{
    type Item = <<HashMapFrequency<T, N, S> as Frequency<'t, T>>::Iter as Iterator>::Item;
    type IntoIter = <HashMapFrequency<T, N, S> as Frequency<'t, T>>::Iter;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

impl<T, N, S> AsRef<HashMap<T, N, S>> for HashMapFrequency<T, N, S>
    where T: Eq + Hash,
          N: Num,
          S: BuildHasher
{
    fn as_ref(&self) -> &HashMap<T, N, S> {
        &self.frequency
    }
}

impl<T, N, S> AsMut<HashMap<T, N, S>> for HashMapFrequency<T, N, S>
    where T: Eq + Hash,
          N: Num,
          S: BuildHasher
{
    fn as_mut(&mut self) -> &mut HashMap<T, N, S> {
        &mut self.frequency
    }
}