sorted_vec2/
partial.rs

1//! Sorted vectors of types implementing `PartialOrd`.
2//!
3//! It is a runtime panic if an incomparable element is compared.
4
5use std;
6use std::hash::{Hash, Hasher};
7
8
9/// Forward sorted vector
10#[derive(Clone, Debug, PartialEq, PartialOrd)]
11pub struct SortedVec <T : PartialOrd> {
12  vec : Vec <T>
13}
14
15/// Forward sorted set
16#[derive(Clone, Debug, PartialEq, PartialOrd)]
17pub struct SortedSet <T : PartialOrd> {
18  set : SortedVec <T>
19}
20
21/// Reverse sorted vector
22#[derive(Clone, Debug, PartialEq, PartialOrd)]
23pub struct ReverseSortedVec <T : PartialOrd> {
24  vec : Vec <T>
25}
26
27/// Reverse sorted set
28#[derive(Clone, Debug, PartialEq, PartialOrd)]
29pub struct ReverseSortedSet <T : PartialOrd> {
30  set : ReverseSortedVec <T>
31}
32
33/// Unwraps a `partial_cmp`
34fn partial_compare <T : PartialOrd> (lhs : &T, rhs : &T) -> std::cmp::Ordering {
35  lhs.partial_cmp (rhs).unwrap()
36}
37
38//
39//  impl SortedVec
40//
41
42impl <T : PartialOrd> SortedVec <T> {
43  #[inline]
44  pub fn new() -> Self {
45    SortedVec { vec: Vec::new() }
46  }
47  #[inline]
48  pub fn with_capacity (capacity : usize) -> Self {
49    SortedVec { vec: Vec::with_capacity (capacity) }
50  }
51  /// Uses `sort_unstable_by()` to sort in place.
52  #[inline]
53  pub fn from_unsorted (mut vec : Vec <T>) -> Self {
54    vec.sort_unstable_by (partial_compare);
55    SortedVec { vec }
56  }
57  /// Insert an element into sorted position, returning the order index at which
58  /// it was placed.
59  ///
60  /// Partial order comparison panics if items are not comparable.
61  pub fn insert (&mut self, element : T) -> usize {
62    let insert_at = match self.binary_search (&element) {
63      Ok (insert_at) | Err (insert_at) => insert_at
64    };
65    self.vec.insert (insert_at, element);
66    insert_at
67  }
68  /// Find the element and return the index with `Ok`, otherwise insert the
69  /// element and return the new element index with `Err`.
70  ///
71  /// Partial order comparison panics if items are not comparable.
72  #[inline]
73  pub fn find_or_insert (&mut self, element : T) -> Result <usize, usize> {
74    self.binary_search (&element).map_err (|insert_at| {
75      self.vec.insert (insert_at, element);
76      insert_at
77    })
78  }
79  #[inline]
80  pub fn remove_item (&mut self, item : &T) -> Option <T> {
81    match self.vec.binary_search_by (
82      |other_item| partial_compare (other_item, item)
83    ) {
84      Ok  (remove_at) => Some (self.vec.remove (remove_at)),
85      Err (_)         => None
86    }
87  }
88  /// Panics if index is out of bounds
89  #[inline]
90  pub fn remove_index (&mut self, index : usize) -> T {
91    self.vec.remove (index)
92  }
93  #[inline]
94  pub fn binary_search (&self, x : &T) -> Result <usize, usize> {
95    self.vec.binary_search_by (|y| partial_compare (y, x))
96  }
97  #[inline]
98  pub fn pop (&mut self) -> Option <T> {
99    self.vec.pop()
100  }
101  #[inline]
102  pub fn clear (&mut self) {
103    self.vec.clear()
104  }
105  #[inline]
106  pub fn dedup (&mut self) {
107    self.vec.dedup();
108  }
109  #[inline]
110  pub fn dedup_by_key <F, K> (&mut self, key : F) where
111    F : FnMut (&mut T) -> K,
112    K : PartialEq <K>
113  {
114    self.vec.dedup_by_key (key);
115  }
116  #[inline]
117  pub fn drain <R> (&mut self, range : R) -> std::vec::Drain <T> where
118    R : std::ops::RangeBounds <usize>
119  {
120    self.vec.drain (range)
121  }
122  #[inline]
123  pub fn retain <F> (&mut self, f : F) where F : FnMut (&T) -> bool {
124    self.vec.retain (f)
125  }
126  /// NOTE: to_vec() is a slice method that is accessible through deref,
127  /// use this instead to avoid cloning
128  #[inline]
129  pub fn into_vec (self) -> Vec <T> {
130    self.vec
131  }
132  /// Apply a closure mutating the sorted vector and use `sort_unstable_by()` to
133  /// re-sort the mutated vector
134  pub fn mutate_vec <F, O> (&mut self, f : F) -> O where
135    F : FnOnce (&mut Vec <T>) -> O
136  {
137    let res = f (&mut self.vec);
138    self.vec.sort_unstable_by (partial_compare);
139    res
140  }
141}
142impl <T : PartialOrd> Default for SortedVec <T> {
143  fn default() -> Self {
144    Self::new()
145  }
146}
147impl <T : PartialOrd> From <Vec <T>> for SortedVec <T> {
148  fn from (unsorted : Vec <T>) -> Self {
149    Self::from_unsorted (unsorted)
150  }
151}
152impl <T : PartialOrd> std::ops::Deref for SortedVec <T> {
153  type Target = Vec <T>;
154  fn deref (&self) -> &Vec <T> {
155    &self.vec
156  }
157}
158impl <T : PartialOrd> Extend <T> for SortedVec <T> {
159  fn extend <I : IntoIterator <Item = T>> (&mut self, iter : I) {
160    for t in iter {
161      let _ = self.insert (t);
162    }
163  }
164}
165impl <T : PartialOrd + Hash> Hash for SortedVec <T> {
166  fn hash <H : Hasher> (&self, state : &mut H) {
167    let v : &Vec <T> = self.as_ref();
168    v.hash (state);
169  }
170}
171
172//
173//  impl SortedSet
174//
175
176impl <T : PartialOrd> SortedSet <T> {
177  #[inline]
178  pub fn new() -> Self {
179    SortedSet { set: SortedVec::new() }
180  }
181  #[inline]
182  pub fn with_capacity (capacity : usize) -> Self {
183    SortedSet { set: SortedVec::with_capacity (capacity) }
184  }
185  /// Uses `sort_unstable()` to sort in place and `dedup()` to remove
186  /// duplicates.
187  #[inline]
188  pub fn from_unsorted (vec : Vec <T>) -> Self {
189    let mut set = SortedVec::from_unsorted (vec);
190    set.dedup();
191    SortedSet { set }
192  }
193  /// Insert an element into sorted position, returning the order index at which
194  /// it was placed.
195  #[inline]
196  pub fn insert (&mut self, element : T) -> usize {
197    let _ = self.remove_item (&element);
198    self.set.insert (element)
199  }
200  /// Find the element and return the index with `Ok`, otherwise insert the
201  /// element and return the new element index with `Err`.
202  #[inline]
203  pub fn find_or_insert (&mut self, element : T) -> Result <usize, usize> {
204    self.set.find_or_insert (element)
205  }
206  #[inline]
207  pub fn remove_item (&mut self, item : &T) -> Option <T> {
208    self.set.remove_item (item)
209  }
210  /// Panics if index is out of bounds
211  #[inline]
212  pub fn remove_index (&mut self, index : usize) -> T {
213    self.set.remove_index (index)
214  }
215  #[inline]
216  pub fn pop (&mut self) -> Option <T> {
217    self.set.pop()
218  }
219  #[inline]
220  pub fn clear (&mut self) {
221    self.set.clear()
222  }
223  #[inline]
224  pub fn drain <R> (&mut self, range : R) -> std::vec::Drain <T> where
225    R : std::ops::RangeBounds <usize>
226  {
227    self.set.drain (range)
228  }
229  #[inline]
230  pub fn retain <F> (&mut self, f : F) where F : FnMut (&T) -> bool {
231    self.set.retain (f)
232  }
233  /// NOTE: to_vec() is a slice method that is accessible through deref, use
234  /// this instead to avoid cloning
235  #[inline]
236  pub fn into_vec (self) -> Vec <T> {
237    self.set.into_vec()
238  }
239  /// Apply a closure mutating the sorted vector and use `sort_unstable()`
240  /// to re-sort the mutated vector and `dedup()` to remove any duplicate
241  /// values
242  pub fn mutate_vec <F, O> (&mut self, f : F) -> O where
243    F : FnOnce (&mut Vec <T>) -> O
244  {
245    let res = self.set.mutate_vec (f);
246    self.set.dedup();
247    res
248  }
249}
250impl <T : PartialOrd> Default for SortedSet <T> {
251  fn default() -> Self {
252    Self::new()
253  }
254}
255impl <T : PartialOrd> From <Vec <T>> for SortedSet <T> {
256  fn from (unsorted : Vec <T>) -> Self {
257    Self::from_unsorted (unsorted)
258  }
259}
260impl <T : PartialOrd> std::ops::Deref for SortedSet <T> {
261  type Target = SortedVec <T>;
262  fn deref (&self) -> &SortedVec <T> {
263    &self.set
264  }
265}
266impl <T : PartialOrd> Extend <T> for SortedSet <T> {
267  fn extend <I : IntoIterator <Item = T>> (&mut self, iter : I) {
268    for t in iter {
269      let _ = self.insert (t);
270    }
271  }
272}
273impl <T : PartialOrd + Hash> Hash for SortedSet <T> {
274  fn hash <H : Hasher> (&self, state : &mut H) {
275    let v : &Vec <T> = self.as_ref();
276    v.hash (state);
277  }
278}
279
280//
281//  impl ReverseSortedVec
282//
283
284impl <T : PartialOrd> ReverseSortedVec <T> {
285  #[inline]
286  pub fn new() -> Self {
287    ReverseSortedVec { vec: Vec::new() }
288  }
289  #[inline]
290  pub fn with_capacity (capacity : usize) -> Self {
291    ReverseSortedVec { vec: Vec::with_capacity (capacity) }
292  }
293  /// Uses `sort_unstable_by()` to sort in place.
294  #[inline]
295  pub fn from_unsorted (mut vec : Vec <T>) -> Self {
296    vec.sort_unstable_by (|x,y| partial_compare (x,y).reverse());
297    ReverseSortedVec { vec }
298  }
299  /// Insert an element into (reverse) sorted position, returning the order
300  /// index at which it was placed.
301  ///
302  /// Partial order comparison panics if items are not comparable.
303  pub fn insert (&mut self, element : T) -> usize {
304    let insert_at = match self.binary_search (&element) {
305      Ok (insert_at) | Err (insert_at) => insert_at
306    };
307    self.vec.insert (insert_at, element);
308    insert_at
309  }
310  /// Find the element and return the index with `Ok`, otherwise insert the
311  /// element and return the new element index with `Err`.
312  ///
313  /// Partial order comparison panics if items are not comparable.
314  #[inline]
315  pub fn find_or_insert (&mut self, element : T) -> Result <usize, usize> {
316    self.binary_search (&element).map_err (|insert_at| {
317      self.vec.insert (insert_at, element);
318      insert_at
319    })
320  }
321  #[inline]
322  pub fn remove_item (&mut self, item : &T) -> Option <T> {
323    match self.vec.binary_search_by (
324      |other_item| partial_compare (other_item, item).reverse()
325    ) {
326      Ok  (remove_at) => Some (self.vec.remove (remove_at)),
327      Err (_)         => None
328    }
329  }
330  /// Panics if index is out of bounds
331  #[inline]
332  pub fn remove_index (&mut self, index : usize) -> T {
333    self.vec.remove (index)
334  }
335  #[inline]
336  pub fn binary_search (&self, x : &T) -> Result <usize, usize> {
337    self.vec.binary_search_by (|y| partial_compare (y, x).reverse())
338  }
339  #[inline]
340  pub fn pop (&mut self) -> Option <T> {
341    self.vec.pop()
342  }
343  #[inline]
344  pub fn clear (&mut self) {
345    self.vec.clear()
346  }
347  pub fn dedup (&mut self) {
348    self.vec.dedup();
349  }
350  #[inline]
351  pub fn dedup_by_key <F, K> (&mut self, key : F) where
352    F : FnMut (&mut T) -> K,
353    K : PartialEq <K>
354  {
355    self.vec.dedup_by_key (key);
356  }
357  #[inline]
358  pub fn drain <R> (&mut self, range : R) -> std::vec::Drain <T> where
359    R : std::ops::RangeBounds <usize>
360  {
361    self.vec.drain (range)
362  }
363  #[inline]
364  pub fn retain <F> (&mut self, f : F) where F : FnMut (&T) -> bool {
365    self.vec.retain (f)
366  }
367  /// NOTE: to_vec() is a slice method that is accessible through deref,
368  /// use this instead to avoid cloning
369  #[inline]
370  pub fn into_vec (self) -> Vec <T> {
371    self.vec
372  }
373  /// Apply a closure mutating the reverse-sorted vector and use
374  /// `sort_unstable_by()` to re-sort the mutated vector
375  pub fn mutate_vec <F, O> (&mut self, f : F) -> O where
376    F : FnOnce (&mut Vec <T>) -> O
377  {
378    let res = f (&mut self.vec);
379    self.vec.sort_unstable_by (|x,y| partial_compare (x,y).reverse());
380    res
381  }
382}
383impl <T : PartialOrd> Default for ReverseSortedVec <T> {
384  fn default() -> Self {
385    Self::new()
386  }
387}
388impl <T : PartialOrd> From <Vec <T>> for ReverseSortedVec <T> {
389  fn from (unsorted : Vec <T>) -> Self {
390    Self::from_unsorted (unsorted)
391  }
392}
393impl <T : PartialOrd> std::ops::Deref for ReverseSortedVec <T> {
394  type Target = Vec <T>;
395  fn deref (&self) -> &Vec <T> {
396    &self.vec
397  }
398}
399impl <T : PartialOrd> Extend <T> for ReverseSortedVec <T> {
400  fn extend <I : IntoIterator <Item = T>> (&mut self, iter : I) {
401    for t in iter {
402      let _ = self.insert (t);
403    }
404  }
405}
406impl <T : PartialOrd + Hash> Hash for ReverseSortedVec <T> {
407  fn hash <H : Hasher> (&self, state : &mut H) {
408    let v : &Vec <T> = self.as_ref();
409    v.hash (state);
410  }
411}
412
413//
414//  impl ReverseSortedSet
415//
416
417impl <T : PartialOrd> ReverseSortedSet <T> {
418  #[inline]
419  pub fn new() -> Self {
420    ReverseSortedSet { set: ReverseSortedVec::new() }
421  }
422  #[inline]
423  pub fn with_capacity (capacity : usize) -> Self {
424    ReverseSortedSet { set: ReverseSortedVec::with_capacity (capacity) }
425  }
426  /// Uses `sort_unstable()` to sort in place and `dedup()` to remove
427  /// duplicates.
428  #[inline]
429  pub fn from_unsorted (vec : Vec <T>) -> Self {
430    let mut set = ReverseSortedVec::from_unsorted (vec);
431    set.dedup();
432    ReverseSortedSet { set }
433  }
434  /// Insert an element into sorted position, returning the order index at which
435  /// it was placed.
436  #[inline]
437  pub fn insert (&mut self, element : T) -> usize {
438    let _ = self.remove_item (&element);
439    self.set.insert (element)
440  }
441  /// Find the element and return the index with `Ok`, otherwise insert the
442  /// element and return the new element index with `Err`.
443  #[inline]
444  pub fn find_or_insert (&mut self, element : T) -> Result <usize, usize> {
445    self.set.find_or_insert (element)
446  }
447  #[inline]
448  pub fn remove_item (&mut self, item : &T) -> Option <T> {
449    self.set.remove_item (item)
450  }
451  /// Panics if index is out of bounds
452  #[inline]
453  pub fn remove_index (&mut self, index : usize) -> T {
454    self.set.remove_index (index)
455  }
456  #[inline]
457  pub fn pop (&mut self) -> Option <T> {
458    self.set.pop()
459  }
460  #[inline]
461  pub fn clear (&mut self) {
462    self.set.clear()
463  }
464  #[inline]
465  pub fn drain <R> (&mut self, range : R) -> std::vec::Drain <T> where
466    R : std::ops::RangeBounds <usize>
467  {
468    self.set.drain (range)
469  }
470  #[inline]
471  pub fn retain <F> (&mut self, f : F) where F : FnMut (&T) -> bool {
472    self.set.retain (f)
473  }
474  /// NOTE: to_vec() is a slice method that is accessible through deref, use
475  /// this instead to avoid cloning
476  #[inline]
477  pub fn into_vec (self) -> Vec <T> {
478    self.set.into_vec()
479  }
480  /// Apply a closure mutating the sorted vector and use `sort_unstable()`
481  /// to re-sort the mutated vector and `dedup()` to remove any duplicate
482  /// values
483  pub fn mutate_vec <F, O> (&mut self, f : F) -> O where
484    F : FnOnce (&mut Vec <T>) -> O
485  {
486    let res = self.set.mutate_vec (f);
487    self.set.dedup();
488    res
489  }
490}
491impl <T : PartialOrd> Default for ReverseSortedSet <T> {
492  fn default() -> Self {
493    Self::new()
494  }
495}
496impl <T : PartialOrd> From <Vec <T>> for ReverseSortedSet <T> {
497  fn from (unsorted : Vec <T>) -> Self {
498    Self::from_unsorted (unsorted)
499  }
500}
501impl <T : PartialOrd> std::ops::Deref for ReverseSortedSet <T> {
502  type Target = ReverseSortedVec <T>;
503  fn deref (&self) -> &ReverseSortedVec <T> {
504    &self.set
505  }
506}
507impl <T : PartialOrd> Extend <T> for ReverseSortedSet <T> {
508  fn extend <I : IntoIterator <Item = T>> (&mut self, iter : I) {
509    for t in iter {
510      let _ = self.insert (t);
511    }
512  }
513}
514impl <T : PartialOrd + Hash> Hash for ReverseSortedSet <T> {
515  fn hash <H : Hasher> (&self, state : &mut H) {
516    let v : &Vec <T> = self.as_ref();
517    v.hash (state);
518  }
519}
520
521#[cfg(test)]
522mod tests {
523  use super::*;
524
525  #[test]
526  fn test_sorted_vec() {
527    let mut v = SortedVec::new();
528    assert_eq!(v.insert (5.0), 0);
529    assert_eq!(v.insert (3.0), 0);
530    assert_eq!(v.insert (4.0), 1);
531    assert_eq!(v.insert (4.0), 1);
532    assert_eq!(v.find_or_insert (4.0), Ok (2));
533    assert_eq!(v.len(), 4);
534    v.dedup();
535    assert_eq!(v.len(), 3);
536    assert_eq!(v.binary_search (&3.0), Ok (0));
537    assert_eq!(*SortedVec::from_unsorted (
538      vec![  5.0, -10.0, 99.0, -11.0,  2.0, 17.0, 10.0]),
539      vec![-11.0, -10.0,  2.0,   5.0, 10.0, 17.0, 99.0]);
540    assert_eq!(SortedVec::from_unsorted (
541      vec![  5.0, -10.0, 99.0, -11.0,  2.0, 17.0, 10.0]),
542      vec![  5.0, -10.0, 99.0, -11.0,  2.0, 17.0, 10.0].into());
543    let mut v = SortedVec::new();
544    v.extend(vec![5.0, -10.0, 99.0, -11.0, 2.0, 17.0, 10.0].into_iter());
545    assert_eq!(
546      v.drain(..).collect::<Vec <f32>>(),
547      vec![-11.0, -10.0, 2.0, 5.0, 10.0, 17.0, 99.0]);
548  }
549
550  #[test]
551  fn test_sorted_set() {
552    let mut s = SortedSet::new();
553    assert_eq!(s.insert (5.0), 0);
554    assert_eq!(s.insert (3.0), 0);
555    assert_eq!(s.insert (4.0), 1);
556    assert_eq!(s.insert (4.0), 1);
557    assert_eq!(s.find_or_insert (4.0), Ok (1));
558    assert_eq!(s.len(), 3);
559    assert_eq!(s.binary_search (&3.0), Ok (0));
560    assert_eq!(**SortedSet::from_unsorted (
561      vec![  5.0, -10.0, 99.0, -10.0, -11.0,  10.0, 2.0, 17.0, 10.0]),
562      vec![-11.0, -10.0,  2.0,   5.0, 10.0, 17.0, 99.0]);
563    assert_eq!(SortedSet::from_unsorted (
564      vec![  5.0, -10.0, 99.0, -10.0, -11.0,  10.0, 2.0, 17.0, 10.0]),
565      vec![  5.0, -10.0, 99.0, -10.0, -11.0,  10.0, 2.0, 17.0, 10.0].into());
566    let mut s = SortedSet::new();
567    s.extend(
568      vec![5.0, -11.0, -10.0, 99.0, -11.0, 2.0, 17.0, 2.0, 10.0].into_iter());
569    assert_eq!(**s, vec![-11.0, -10.0, 2.0, 5.0, 10.0, 17.0, 99.0]);
570    let _ = s.mutate_vec (|s|{
571      s[0] = 5.0;
572      s[3] = 11.0;
573    });
574    assert_eq!(
575      s.drain(..).collect::<Vec <f32>>(),
576      vec![-10.0, 2.0, 5.0, 10.0, 11.0, 17.0, 99.0]);
577  }
578
579  #[test]
580  fn test_reverse_sorted_vec() {
581    let mut v = ReverseSortedVec::new();
582    assert_eq!(v.insert (5.0), 0);
583    assert_eq!(v.insert (3.0), 1);
584    assert_eq!(v.insert (4.0), 1);
585    assert_eq!(v.find_or_insert (6.0), Err (0));
586    assert_eq!(v.insert (4.0), 2);
587    assert_eq!(v.find_or_insert (4.0), Ok (2));
588    assert_eq!(v.len(), 5);
589    v.dedup();
590    assert_eq!(v.len(), 4);
591    assert_eq!(v.binary_search (&3.0), Ok (3));
592    assert_eq!(*ReverseSortedVec::from_unsorted (
593      vec![5.0, -10.0, 99.0, -11.0, 2.0,  17.0,  10.0]),
594      vec![99.0, 17.0, 10.0,   5.0, 2.0, -10.0, -11.0]);
595    assert_eq!(ReverseSortedVec::from_unsorted (
596      vec![5.0, -10.0, 99.0, -11.0, 2.0,  17.0,  10.0]),
597      vec![5.0, -10.0, 99.0, -11.0, 2.0,  17.0,  10.0].into());
598    let mut v = ReverseSortedVec::new();
599    v.extend(vec![5.0, -10.0, 99.0, -11.0, 2.0, 17.0, 10.0].into_iter());
600    assert_eq!(
601      v.drain(..).collect::<Vec <f32>>(),
602      vec![99.0, 17.0, 10.0, 5.0, 2.0, -10.0, -11.0]);
603  }
604
605  #[test]
606  fn test_reverse_sorted_set() {
607    let mut s = ReverseSortedSet::new();
608    assert_eq!(s.insert (5.0), 0);
609    assert_eq!(s.insert (3.0), 1);
610    assert_eq!(s.insert (4.0), 1);
611    assert_eq!(s.find_or_insert (6.0), Err (0));
612    assert_eq!(s.insert (4.0), 2);
613    assert_eq!(s.find_or_insert (4.0), Ok (2));
614    assert_eq!(s.len(), 4);
615    assert_eq!(s.binary_search (&3.0), Ok (3));
616    assert_eq!(**ReverseSortedSet::from_unsorted (
617      vec![5.0, -10.0, 99.0, -11.0, 2.0,  17.0,  10.0, -10.0]),
618      vec![99.0, 17.0, 10.0,   5.0, 2.0, -10.0, -11.0]);
619    assert_eq!(ReverseSortedSet::from_unsorted (
620      vec![5.0, -10.0, 99.0, -11.0, 2.0,  17.0,  10.0, -10.0]),
621      vec![5.0, -10.0, 99.0, -11.0, 2.0,  17.0,  10.0, -10.0].into());
622    let mut s = ReverseSortedSet::new();
623    s.extend(vec![5.0, -10.0, 2.0, 99.0, -11.0, -11.0, 2.0, 17.0, 10.0].into_iter());
624    assert_eq!(**s, vec![99.0, 17.0, 10.0, 5.0, 2.0, -10.0, -11.0]);
625    let _ = s.mutate_vec (|s|{
626      s[6] = 17.0;
627      s[3] = 1.0;
628    });
629    assert_eq!(
630      s.drain(..).collect::<Vec <f32>>(),
631      vec![99.0, 17.0, 10.0, 2.0, 1.0, -10.0]);
632  }
633}
sorted_vec2/partial.rs

sorted_vec2/
partial.rs
