// Just some code the help learn Rust, traits, lifetimes, etc.

mod group {
  use core::slice::Iter;
  use std::collections::HashMap;
  use std::hash::Hash;

  pub struct GroupByIter<'a, E: 'a, F: 'a, G: Eq + 'a> where F: Fn(&'a E) -> G {
    iter: Iter<'a, E>,
    test: Box<F>,
    curr: Option<G>,
    last: Option<&'a E>
  } 

  impl<'a, E: 'a, F: 'a, G: Eq + 'a> GroupByIter<'a, E, F, G> where F: Fn(&'a E) -> G {
    fn new(slice: &'a [E], test: F) -> GroupByIter<'a, E, F, G> {
      GroupByIter { iter: slice.iter(), test: Box::new(test), curr: None, last: None }
    }
  }

  pub trait GroupBy {
    type Item;

    fn group_by<'a, F: 'a, G: Eq + 'a>(&'a self, test: F) -> GroupByIter<'a, Self::Item, F, G> where Self::Item: 'a, F: Fn(&'a Self::Item) -> G;
  }

  impl<E> GroupBy for [E] {
    type Item = E;

    fn group_by<'a, F: 'a, G: Eq + 'a>(&'a self, test: F) -> GroupByIter<'a, E, F, G> where E: 'a, F: Fn(&'a E) -> G {
      GroupByIter::new(self, test)
    }
  }

  impl<'a, E: 'a, F: 'a, G: Eq + 'a> Iterator for GroupByIter<'a, E, F, G> where F: Fn(&'a E) -> G {
    type Item = Vec<&'a E>; 

    fn next(&mut self) -> Option<Self::Item> {
      let mut group = Vec::new();
      if let Some(e) = self.last {
        group.push(e);
        self.last = None;
      };
      let test = &self.test;
      loop {
        match self.iter.next() {
          None => break,
          Some(e) => {
            let new = Some(test(e));
            if self.curr == new || self.curr.is_none() {
              group.push(e);
              self.curr = new;
            } else {
              self.last = Some(e);
              self.curr = new;
              break;
            }
          }
        }
      };
      if !group.is_empty() { Some(group) } else { None }
    }
  }

  pub trait Countable {
    type Item: Eq + Hash;
    
    fn counts<'a>(&'a self) -> HashMap<&'a Self::Item, usize>;
  }

  impl<E: Eq + Hash> Countable for [E] {
    type Item = E;

    fn counts<'a>(&'a self) -> HashMap<&'a E, usize> {
      let mut map = HashMap::new();
      for e in self {
        map.insert(e, map.get(e).unwrap_or(&0) + 1);
      }
      map
    }
  }
}