key-vec 0.4.1

//! Vec-backed container of key-value pairs sorted by key for order 'log n'
//! lookup.
//!
//! [Repository](https://gitlab.com/spearman/key-vec)
//!
//! ```
//! use key_vec::KeyVec;
//! let v = KeyVec::from (vec![(5, 'a'), (1, 'b'), (-1, 'c')]);
//! assert_eq!(*v, vec![(-1, 'c'), (1, 'b'), (5, 'a')]);
//! assert_eq!(&'c', v.get (&-1).unwrap());
//! assert!(v.get (&-2).is_none());
//! ```
//!
//! When constructing from a vec with duplicate keys, the first of any
//! duplicates will be retained:
//!
//! ```
//! use key_vec::KeyVec;
//! let v = KeyVec::from (vec![(5, 'a'), (-10, 'b'), (2, 'c'), (5, 'd')]);
//! assert_eq!(*v, vec![(-10, 'b'), (2, 'c'), (5, 'a')]);
//! ```
//!
//! When building or extending from an iterator, the last value to appear in the
//! iterator will supercede any previous values with the same key:
//!
//! ```
//! use key_vec::KeyVec;
//! let mut v = KeyVec::new();
//! assert!(v.insert (5, 'a').is_none());
//! v.extend (vec![(10, 'b'), (5, 'c'), (2, 'd'), (5, 'e')]);
//! assert_eq!(*v, vec![(2, 'd'), (5, 'e'), (10, 'b')]);
//! ```

#[cfg(feature="serde")]
use serde::{Deserialize, Serialize};

pub mod partial;

/// Vec of key-value pairs sorted by key.
///
/// See crate-level documentation for examples.
#[cfg_attr(feature="serde", derive(Deserialize, Serialize))]
#[derive(Clone, Debug, PartialEq)]
pub struct KeyVec <K, V> {
  vec : Vec <(K, V)>
}

#[derive(Debug)]
pub struct IterMut <'a, K, V> (std::slice::IterMut <'a, (K, V)>);

impl <K, V> KeyVec <K, V> {
  #[inline]
  pub fn new() -> Self {
    KeyVec::default()
  }
  #[inline]
  pub fn with_capacity (capacity : usize) -> Self {
    KeyVec { vec: Vec::with_capacity (capacity) }
  }
  /// Insert an (key,value) pair, returning an existing value if one was present
  /// for the corresponding key.
  pub fn insert (&mut self, key : K, value : V) -> Option <V> where
    K : Ord + std::fmt::Debug
  {
    match &self.vec.binary_search_by_key (&&key, |key_value| &key_value.0) {
      Ok  (insert_at) => {
        debug_assert_eq!(self.vec[*insert_at].0, key);
        let mut value = value;
        std::mem::swap (&mut self.vec[*insert_at].1, &mut value);
        Some (value)
      }
      Err (insert_at) => {
        self.vec.insert (*insert_at, (key, value));
        None
      }
    }
  }
  /// Same as insert, except performance is O(1) when the element belongs at the
  /// back of the container. This avoids an O(log(N)) search for inserting
  /// elements at the back.
  pub fn push (&mut self, key : K, mut value : V) -> Option <V> where
    K : Ord + std::fmt::Debug
  {
    if let Some((last, original)) = self.vec.last_mut() {
      let cmp = key.cmp (last);
      if cmp == std::cmp::Ordering::Greater {
        self.vec.push ((key, value));
        None
      } else if cmp == std::cmp::Ordering::Equal {
        std::mem::swap (original, &mut value);
        Some (value)
      } else {
        self.insert (key, value)
      }
    } else {
      self.vec.push ((key, value));
      None
    }
  }
  #[inline]
  pub fn get (&self, key : &K) -> Option <&V> where K : Ord {
    match self.vec.binary_search_by_key (&key, |key_value| &key_value.0) {
      Ok  (index) => Some (&self.vec[index].1),
      Err (_)     => None
    }
  }
  #[inline]
  pub fn get_mut (&mut self, key : &K) -> Option <&mut V> where K : Ord {
    match self.vec.binary_search_by_key (&key, |key_value| &key_value.0) {
      Ok  (index) => Some (&mut self.vec[index].1),
      Err (_)     => None
    }
  }
  #[inline]
  pub fn get_index (&self, key : &K) -> Option <usize> where K : Ord {
    match self.vec.binary_search_by_key (&key, |key_value| &key_value.0) {
      Ok  (index) => Some (index),
      Err (_)     => None
    }
  }
  #[inline]
  pub fn remove (&mut self, key : &K) -> Option <V> where K : Ord {
    match self.vec.binary_search_by_key (&key, |key_value| &key_value.0) {
      Ok  (remove_at) => Some (self.vec.remove (remove_at).1),
      Err (_)         => None
    }
  }
  /// Panics if index is out of bounds
  #[inline]
  pub fn remove_index (&mut self, index : usize) -> (K, V) {
    self.vec.remove (index)
  }
  #[inline]
  pub fn pop (&mut self) -> Option <(K, V)> {
    self.vec.pop()
  }
  #[inline]
  pub fn clear (&mut self) {
    self.vec.clear()
  }
  #[inline]
  pub fn drain <R> (&mut self, range : R) -> std::vec::Drain <(K, V)> where
    R : std::ops::RangeBounds <usize>
  {
    self.vec.drain (range)
  }
  #[inline]
  pub fn iter_mut (&mut self) -> IterMut <K, V> {
    IterMut (self.vec.iter_mut())
  }
  #[inline]
  pub fn retain <F> (&mut self, f : F) where F : FnMut (&(K, V)) -> bool {
    self.vec.retain (f);
  }
  /// NOTE: to_vec() is a slice method that is accessible through deref, use
  /// this instead to avoid cloning
  #[inline]
  pub fn into_vec (self) -> Vec <(K, V)> {
    self.vec
  }

  pub fn truncate (&mut self, len : usize) {
    self.vec.truncate (len)
  }

  pub fn split_off (&mut self, at : usize) -> Self {
    let vec = self.vec.split_off (at);
    KeyVec { vec }
  }
}
impl <K, V> Default for KeyVec <K, V> {
  fn default() -> Self {
    KeyVec { vec: vec![] }
  }
}
impl <K, V> Eq for KeyVec <K, V> where K : Eq, V : Eq { }
impl <K, V> From <Vec <(K, V)>> for KeyVec <K, V> where
  K : Ord + Clone + std::fmt::Debug
{
  /// Uses `sort_by_key()` and `dedup_by_key()` to remove duplicate key entries.
  ///
  /// Note that `dedup_by_key()` will keep the *first* of duplicate keys present
  /// in the input vector.
  fn from (mut vec : Vec <(K, V)>) -> Self {
    vec.sort_unstable_by_key (|key_value| key_value.0.clone());
    vec.dedup_by_key (|key_value| key_value.0.clone());
    KeyVec { vec }
  }
}
impl <K, V> std::iter::FromIterator <(K, V)> for KeyVec <K, V> where
  K : Ord + std::fmt::Debug
{
  fn from_iter <I : std::iter::IntoIterator <Item=(K, V)>> (iter : I) -> Self {
    let mut keyvec = KeyVec::new();
    keyvec.extend (iter);
    keyvec
  }
}
impl <K, V> IntoIterator for KeyVec <K, V> {
  type Item = (K, V);
  type IntoIter = std::vec::IntoIter <Self::Item>;
  fn into_iter (self) -> Self::IntoIter {
    self.vec.into_iter()
  }
}
impl <K, V> std::ops::Deref for KeyVec <K, V> {
  type Target = Vec <(K, V)>;
  fn deref (&self) -> &Vec <(K, V)> {
    &self.vec
  }
}
impl <K, V> Extend <(K, V)> for KeyVec <K, V> where K : Ord + std::fmt::Debug {
  fn extend <I : IntoIterator <Item = (K, V)>> (&mut self, iter : I) {
    for (k, v) in iter {
      let _ = self.insert (k, v);
    }
  }
}

impl <'a, K, V> Iterator for IterMut <'a, K, V> {
  type Item = &'a mut V;
  fn next (&mut self) -> Option <&'a mut V> {
    self.0.next().map (|(_, v)| v)
  }
}
impl <'a, K, V> DoubleEndedIterator for IterMut <'a, K, V> {
  fn next_back (&mut self) -> Option <&'a mut V> {
    self.0.next_back().map (|(_, v)| v)
  }
}
impl <'a, K, V> ExactSizeIterator for IterMut <'a, K, V> { }
impl <'a, K, V> std::iter::FusedIterator for IterMut <'a, K, V> { }

#[cfg(test)]
mod tests {
  use super::*;
  #[test]
  fn test_key_vec() {
    let mut v = KeyVec::<i32, char>::new();
    assert_eq!(v.insert (5, 'a'), None);
    assert_eq!(v.insert (3, 'b'), None);
    assert_eq!(v.insert (4, 'c'), None);
    assert_eq!(v.insert (4, 'd'), Some ('c'));
    assert_eq!(v.len(), 3);
    assert_eq!(v.get (&3), Some (&'b'));
    assert_eq!(v.push (5, 'e'), Some ('a'));
    assert_eq!(
      *KeyVec::from (
        vec![(5, 'd'), (-10, 'b'), (99, 'g'), (-11, 'a'), (2, 'c'), (17, 'f'),
          (10, 'e'), (2, 'h')]),
      vec![(-11, 'a'), (-10, 'b'), (2, 'c'), (5, 'd'), (10, 'e'), (17, 'f'),
        (99, 'g')]
    );
  }
}