key_vec/
lib.rs

1//! Vec-backed container of key-value pairs sorted by key for order 'log n'
2//! lookup.
3//!
4//! [Repository](https://gitlab.com/spearman/key-vec)
5//!
6//! ```
7//! use key_vec::KeyVec;
8//! let v = KeyVec::from (vec![(5, 'a'), (1, 'b'), (-1, 'c')]);
9//! assert_eq!(*v, vec![(-1, 'c'), (1, 'b'), (5, 'a')]);
10//! assert_eq!(&'c', v.get (&-1).unwrap());
11//! assert!(v.get (&-2).is_none());
12//! ```
13//!
14//! When constructing from a vec with duplicate keys, the first of any
15//! duplicates will be retained:
16//!
17//! ```
18//! use key_vec::KeyVec;
19//! let v = KeyVec::from (vec![(5, 'a'), (-10, 'b'), (2, 'c'), (5, 'd')]);
20//! assert_eq!(*v, vec![(-10, 'b'), (2, 'c'), (5, 'a')]);
21//! ```
22//!
23//! When building or extending from an iterator, the last value to appear in the
24//! iterator will supercede any previous values with the same key:
25//!
26//! ```
27//! use key_vec::KeyVec;
28//! let mut v = KeyVec::new();
29//! assert!(v.insert (5, 'a').is_none());
30//! v.extend (vec![(10, 'b'), (5, 'c'), (2, 'd'), (5, 'e')]);
31//! assert_eq!(*v, vec![(2, 'd'), (5, 'e'), (10, 'b')]);
32//! ```
33
34#[cfg(feature="serde")]
35use serde::{Deserialize, Serialize};
36
37pub mod partial;
38
39/// Vec of key-value pairs sorted by key.
40///
41/// See crate-level documentation for examples.
42#[cfg_attr(feature="serde", derive(Deserialize, Serialize))]
43#[derive(Clone, Debug, PartialEq)]
44pub struct KeyVec <K, V> {
45  vec : Vec <(K, V)>
46}
47
48#[derive(Debug)]
49pub struct IterMut <'a, K, V> (std::slice::IterMut <'a, (K, V)>);
50
51impl <K, V> KeyVec <K, V> {
52  #[inline]
53  pub fn new() -> Self {
54    KeyVec::default()
55  }
56  #[inline]
57  pub fn with_capacity (capacity : usize) -> Self {
58    KeyVec { vec: Vec::with_capacity (capacity) }
59  }
60  /// Insert an (key,value) pair, returning an existing value if one was present
61  /// for the corresponding key.
62  pub fn insert (&mut self, key : K, value : V) -> Option <V> where
63    K : Ord + std::fmt::Debug
64  {
65    match &self.vec.binary_search_by_key (&&key, |key_value| &key_value.0) {
66      Ok  (insert_at) => {
67        debug_assert_eq!(self.vec[*insert_at].0, key);
68        let mut value = value;
69        std::mem::swap (&mut self.vec[*insert_at].1, &mut value);
70        Some (value)
71      }
72      Err (insert_at) => {
73        self.vec.insert (*insert_at, (key, value));
74        None
75      }
76    }
77  }
78  /// Same as insert, except performance is O(1) when the element belongs at the
79  /// back of the container. This avoids an O(log(N)) search for inserting
80  /// elements at the back.
81  pub fn push (&mut self, key : K, mut value : V) -> Option <V> where
82    K : Ord + std::fmt::Debug
83  {
84    if let Some((last, original)) = self.vec.last_mut() {
85      let cmp = key.cmp (last);
86      if cmp == std::cmp::Ordering::Greater {
87        self.vec.push ((key, value));
88        None
89      } else if cmp == std::cmp::Ordering::Equal {
90        std::mem::swap (original, &mut value);
91        Some (value)
92      } else {
93        self.insert (key, value)
94      }
95    } else {
96      self.vec.push ((key, value));
97      None
98    }
99  }
100  #[inline]
101  pub fn get (&self, key : &K) -> Option <&V> where K : Ord {
102    match self.vec.binary_search_by_key (&key, |key_value| &key_value.0) {
103      Ok  (index) => Some (&self.vec[index].1),
104      Err (_)     => None
105    }
106  }
107  #[inline]
108  pub fn get_mut (&mut self, key : &K) -> Option <&mut V> where K : Ord {
109    match self.vec.binary_search_by_key (&key, |key_value| &key_value.0) {
110      Ok  (index) => Some (&mut self.vec[index].1),
111      Err (_)     => None
112    }
113  }
114  #[inline]
115  pub fn get_index (&self, key : &K) -> Option <usize> where K : Ord {
116    match self.vec.binary_search_by_key (&key, |key_value| &key_value.0) {
117      Ok  (index) => Some (index),
118      Err (_)     => None
119    }
120  }
121  #[inline]
122  pub fn remove (&mut self, key : &K) -> Option <V> where K : Ord {
123    match self.vec.binary_search_by_key (&key, |key_value| &key_value.0) {
124      Ok  (remove_at) => Some (self.vec.remove (remove_at).1),
125      Err (_)         => None
126    }
127  }
128  /// Panics if index is out of bounds
129  #[inline]
130  pub fn remove_index (&mut self, index : usize) -> (K, V) {
131    self.vec.remove (index)
132  }
133  #[inline]
134  pub fn pop (&mut self) -> Option <(K, V)> {
135    self.vec.pop()
136  }
137  #[inline]
138  pub fn clear (&mut self) {
139    self.vec.clear()
140  }
141  #[inline]
142  pub fn drain <R> (&mut self, range : R) -> std::vec::Drain <(K, V)> where
143    R : std::ops::RangeBounds <usize>
144  {
145    self.vec.drain (range)
146  }
147  #[inline]
148  pub fn iter_mut (&mut self) -> IterMut <K, V> {
149    IterMut (self.vec.iter_mut())
150  }
151  #[inline]
152  pub fn retain <F> (&mut self, f : F) where F : FnMut (&(K, V)) -> bool {
153    self.vec.retain (f);
154  }
155  /// NOTE: to_vec() is a slice method that is accessible through deref, use
156  /// this instead to avoid cloning
157  #[inline]
158  pub fn into_vec (self) -> Vec <(K, V)> {
159    self.vec
160  }
161
162  pub fn truncate (&mut self, len : usize) {
163    self.vec.truncate (len)
164  }
165
166  pub fn split_off (&mut self, at : usize) -> Self {
167    let vec = self.vec.split_off (at);
168    KeyVec { vec }
169  }
170}
171impl <K, V> Default for KeyVec <K, V> {
172  fn default() -> Self {
173    KeyVec { vec: vec![] }
174  }
175}
176impl <K, V> Eq for KeyVec <K, V> where K : Eq, V : Eq { }
177impl <K, V> From <Vec <(K, V)>> for KeyVec <K, V> where
178  K : Ord + Clone + std::fmt::Debug
179{
180  /// Uses `sort_by_key()` and `dedup_by_key()` to remove duplicate key entries.
181  ///
182  /// Note that `dedup_by_key()` will keep the *first* of duplicate keys present
183  /// in the input vector.
184  fn from (mut vec : Vec <(K, V)>) -> Self {
185    vec.sort_unstable_by_key (|key_value| key_value.0.clone());
186    vec.dedup_by_key (|key_value| key_value.0.clone());
187    KeyVec { vec }
188  }
189}
190impl <K, V> std::iter::FromIterator <(K, V)> for KeyVec <K, V> where
191  K : Ord + std::fmt::Debug
192{
193  fn from_iter <I : std::iter::IntoIterator <Item=(K, V)>> (iter : I) -> Self {
194    let mut keyvec = KeyVec::new();
195    keyvec.extend (iter);
196    keyvec
197  }
198}
199impl <K, V> IntoIterator for KeyVec <K, V> {
200  type Item = (K, V);
201  type IntoIter = std::vec::IntoIter <Self::Item>;
202  fn into_iter (self) -> Self::IntoIter {
203    self.vec.into_iter()
204  }
205}
206impl <K, V> std::ops::Deref for KeyVec <K, V> {
207  type Target = Vec <(K, V)>;
208  fn deref (&self) -> &Vec <(K, V)> {
209    &self.vec
210  }
211}
212impl <K, V> Extend <(K, V)> for KeyVec <K, V> where K : Ord + std::fmt::Debug {
213  fn extend <I : IntoIterator <Item = (K, V)>> (&mut self, iter : I) {
214    for (k, v) in iter {
215      let _ = self.insert (k, v);
216    }
217  }
218}
219
220impl <'a, K, V> Iterator for IterMut <'a, K, V> {
221  type Item = &'a mut V;
222  fn next (&mut self) -> Option <&'a mut V> {
223    self.0.next().map (|(_, v)| v)
224  }
225}
226impl <'a, K, V> DoubleEndedIterator for IterMut <'a, K, V> {
227  fn next_back (&mut self) -> Option <&'a mut V> {
228    self.0.next_back().map (|(_, v)| v)
229  }
230}
231impl <'a, K, V> ExactSizeIterator for IterMut <'a, K, V> { }
232impl <'a, K, V> std::iter::FusedIterator for IterMut <'a, K, V> { }
233
234#[cfg(test)]
235mod tests {
236  use super::*;
237  #[test]
238  fn test_key_vec() {
239    let mut v = KeyVec::<i32, char>::new();
240    assert_eq!(v.insert (5, 'a'), None);
241    assert_eq!(v.insert (3, 'b'), None);
242    assert_eq!(v.insert (4, 'c'), None);
243    assert_eq!(v.insert (4, 'd'), Some ('c'));
244    assert_eq!(v.len(), 3);
245    assert_eq!(v.get (&3), Some (&'b'));
246    assert_eq!(v.push (5, 'e'), Some ('a'));
247    assert_eq!(
248      *KeyVec::from (
249        vec![(5, 'd'), (-10, 'b'), (99, 'g'), (-11, 'a'), (2, 'c'), (17, 'f'),
250          (10, 'e'), (2, 'h')]),
251      vec![(-11, 'a'), (-10, 'b'), (2, 'c'), (5, 'd'), (10, 'e'), (17, 'f'),
252        (99, 'g')]
253    );
254  }
255}
key_vec/lib.rs

key_vec/
lib.rs
