//! The [`Frequency`][frequency] trait represents types that keep track of the 
//! observed counts of items. The [`OrderMapFrequency`][ordermapfrequency] type
//! is a frequency counter backed by a [`OrderMap`][ordermap].
//!
//! # Usage
//! Add [`frequency`][freq_crate] and `frequency-ordermap` to your `Cargo.toml`:
//!
//! ```
//! [dependencies]
//! frequency = "^1.0.0"
//! frequency-ordermap = "^1.0.0"
//! ```
//!
//! Import both [`Frequency`][frequency] and 
//! [`OrderMapFrequency`][ordermapfrequency]:
//!
//! ```
//! extern crate frequency;
//! extern crate frequency_ordermap;
//!
//! use frequency::Frequency;
//! use frequency_ordermap::OrderMapFrequency;
//! ```
//!
//! [freq_crate]: https://docs.rs/frequency/~1/
//! [frequency]: https://docs.rs/frequency/~1/frequency/trait.Frequency.html
//! [ordermapfrequency]: struct.OrderMapFrequency.html
//! [ordermap]: https://docs.rs/ordermap/0.2.8/ordermap/struct.OrderMap.html

extern crate frequency;
extern crate fnv;
extern crate num_traits;
extern crate ordermap as om;

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 om::{Iter, Keys, Values, OrderMap};

/// A frequency counter backed by an [`OrderMap`][ordermap]
/// [ordermap]: https://docs.rs/ordermap/
pub struct OrderMapFrequency<T, N=usize, S=FnvBuildHasher>
    where T: Hash + Eq,
          N: Num,
          S: BuildHasher
{
    frequency: OrderMap<T, N, S>,
}

impl<'t, T, N, S> Frequency<'t, T> for OrderMapFrequency<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> OrderMapFrequency<T, N, S>
    where T: Eq + Hash,
          N: Num,
          S: BuildHasher + Default
{
    /// Creates an empty `OrderMapFrequency`, a frequency counter backed
    /// by a OrderMap. Does not allocate.
    #[inline]
    pub fn new() -> OrderMapFrequency<T, N, S> {
        Default::default()
    }

    /// Creates an empty `OrderMapFrequency`, a frequency counter backed
    /// by a OrderMap 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) -> OrderMapFrequency<T, N, S> {
        OrderMapFrequency::with_capacity_and_hasher(capacity, Default::default())
    }
}

impl<T, N, S> OrderMapFrequency<T, N, S>
    where T: Eq + Hash,
          N: Num,
          S: BuildHasher
{
    /// Creates an empty `OrderMapFrequency`, a frequency counter backed
    /// by a OrderMap 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.
    #[inline]
    pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> OrderMapFrequency<T, N, S> {
        OrderMapFrequency {
            frequency: OrderMap::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 `OrderMap` 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 OrderMapFrequency<T, N, S>
    where T: Eq + Hash,
          N: Num,
          S: BuildHasher + Default
{
    /// Creates an empty `OrderMapFrequency<T, V, S>`, a frequency counter backed
    /// by a OrderMap with the `Default` value for the hasher.
    fn default() -> OrderMapFrequency<T, N, S> {
        OrderMapFrequency::with_capacity_and_hasher(0, Default::default())
    }
}

impl<T, N, S> Extend<T> for OrderMapFrequency<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 OrderMapFrequency<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 = OrderMapFrequency::default();
        frequency.extend(iter);
        frequency
    }
}

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

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

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

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