key_vec/
partial.rs

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

key_vec/
partial.rs
