use std::collections::HashMap;
use std::hash::Hash;
use std::iter::FromIterator;
use std::ops::Add;

struct Counter<K: Hash + Eq> {
    storage: HashMap<K, usize>,
}

impl<K: Hash + Eq> Counter<K> {
    fn new() -> Self {
        Self {
            storage: HashMap::new(),
        }
    }

    fn with_capacity(capacity: usize) -> Self {
        Self {
            storage: HashMap::with_capacity(capacity),
        }
    }

    fn append(&mut self, key: K) {
        *self.storage.entry(key).or_insert(0) += 1
    }

    fn most_common<'a>(&'a self, n: usize) -> Vec<&'a K> {
        let mut entries: Vec<_> = self.storage.iter().collect();

        entries.sort_by(|(_, v1), (_, &v2)| v2.cmp(v1));

        entries.iter().map(|&(k, _)| k).take(n).collect()
    }
}

impl<K: Hash + Eq> FromIterator<K> for Counter<K> {
    fn from_iter<T: IntoIterator<Item = K>>(iter: T) -> Self {
        let iterator = iter.into_iter();
        let (min, max) = iterator.size_hint();
        let mut counter = Self::with_capacity(max.unwrap_or(min));

        for key in iterator {
            counter.append(key);
        }

        counter
    }
}


impl<K: Hash + Eq> Add<K> for Counter<K> {
    type Output = Counter<K>;

    fn add(&self, other: Counter<K>) -> Counter<K> {
        let mut new_counter = Counter::new();
        new_counter.merge(&self);

        for (key, value) in &other {
            new_counter.entry(key).or_insert(value);
        }

        new_counter
    }
}

fn main() {
    let collected_counter: Counter<&str> = vec!["test", "test", "test", "hello", "hello", "world"]
        .into_iter()
        .collect();

    let mut my_counter: Counter<&str> = Counter::new();
    my_counter.append("test");
    my_counter.append("test");
    my_counter.append("test");
    my_counter.append("hello");
    my_counter.append("hello");
    my_counter.append("world");

    println!("{:?}", my_counter.most_common(2));

    let mut my_counter_2: Counter<&str> = Counter::new();
    my_counter_2.append("x");
    my_counter_2.append("x");
    my_counter_2.append("x");
    my_counter_2.append("y");

    println!("{:?}", my_counter_2.most_common(2));

    println!("{:?}", my_counter + my_counter_2);
}