#[cfg(feature="serde")]
use serde::{Deserialize, Serialize};
pub mod partial;
#[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) }
}
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
}
}
}
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
}
}
#[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);
}
#[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
{
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')]
);
}
}