sorted_vec/
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)]
11#[expect(clippy::derive_partial_eq_without_eq)]
12pub struct SortedVec <T : PartialOrd> {
13  vec : Vec <T>
14}
15
16/// Forward sorted set
17#[derive(Clone, Debug, PartialEq, PartialOrd)]
18pub struct SortedSet <T : PartialOrd> {
19  set : SortedVec <T>
20}
21
22/// Reverse sorted vector
23#[derive(Clone, Debug, PartialEq, PartialOrd)]
24#[expect(clippy::derive_partial_eq_without_eq)]
25pub struct ReverseSortedVec <T : PartialOrd> {
26  vec : Vec <T>
27}
28
29/// Reverse sorted set
30#[derive(Clone, Debug, PartialEq, PartialOrd)]
31pub struct ReverseSortedSet <T : PartialOrd> {
32  set : ReverseSortedVec <T>
33}
34
35/// Unwraps a `partial_cmp`
36fn partial_compare <T : PartialOrd> (lhs : &T, rhs : &T) -> std::cmp::Ordering {
37  lhs.partial_cmp (rhs).unwrap()
38}
39
40//
41//  impl SortedVec
42//
43
44impl <T : PartialOrd> SortedVec <T> {
45  #[inline]
46  pub const fn new() -> Self {
47    SortedVec { vec: Vec::new() }
48  }
49  #[inline]
50  pub fn with_capacity (capacity : usize) -> Self {
51    SortedVec { vec: Vec::with_capacity (capacity) }
52  }
53  /// Uses `sort_unstable_by()` to sort in place.
54  #[inline]
55  pub fn from_unsorted (mut vec : Vec <T>) -> Self {
56    vec.sort_unstable_by (partial_compare);
57    SortedVec { vec }
58  }
59  /// Insert an element into sorted position, returning the order index at which
60  /// it was placed.
61  ///
62  /// Partial order comparison panics if items are not comparable.
63  pub fn insert (&mut self, element : T) -> usize {
64    let insert_at = match self.binary_search (&element) {
65      Ok (insert_at) | Err (insert_at) => insert_at
66    };
67    self.vec.insert (insert_at, element);
68    insert_at
69  }
70  /// Find the element and return the index with `Ok`, otherwise insert the
71  /// element and return the new element index with `Err`.
72  ///
73  /// Partial order comparison panics if items are not comparable.
74  #[inline]
75  pub fn find_or_insert (&mut self, element : T) -> Result <usize, usize> {
76    self.binary_search (&element)
77      .inspect_err (|&insert_at| self.vec.insert (insert_at, element))
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  #[expect(mismatched_lifetime_syntaxes)]
118  pub fn drain <R> (&mut self, range : R) -> std::vec::Drain <T> where
119    R : std::ops::RangeBounds <usize>
120  {
121    self.vec.drain (range)
122  }
123  #[inline]
124  pub fn retain <F> (&mut self, f : F) where F : FnMut (&T) -> bool {
125    self.vec.retain (f)
126  }
127  /// NOTE: `to_vec()` is a slice method that is accessible through deref,
128  /// use this instead to avoid cloning
129  #[inline]
130  pub fn into_vec (self) -> Vec <T> {
131    self.vec
132  }
133  /// Apply a closure mutating the sorted vector and use `sort_unstable_by()` to
134  /// re-sort the mutated vector
135  pub fn mutate_vec <F, O> (&mut self, f : F) -> O where
136    F : FnOnce (&mut Vec <T>) -> O
137  {
138    let res = f (&mut self.vec);
139    self.vec.sort_unstable_by (partial_compare);
140    res
141  }
142  /// The caller must ensure that the provided vector is already sorted.
143  ///
144  /// # Safety
145  ///
146  /// There is a debug assertion that the input is sorted.
147  ///
148  /// ```should_panic
149  /// use sorted_vec::partial::SortedVec;
150  /// let v = vec![4.0, 3.0, 2.0];
151  /// let _s = unsafe { SortedVec::from_sorted(v) };  // panic!
152  /// ```
153  #[inline]
154  pub unsafe fn from_sorted(vec : Vec<T>) -> Self {
155    debug_assert!(vec.is_sorted());
156    SortedVec { vec }
157  }
158}
159impl <T : PartialOrd> Default for SortedVec <T> {
160  fn default() -> Self {
161    Self::new()
162  }
163}
164impl <T : PartialOrd> From <Vec <T>> for SortedVec <T> {
165  fn from (unsorted : Vec <T>) -> Self {
166    Self::from_unsorted (unsorted)
167  }
168}
169impl <T : PartialOrd> std::ops::Deref for SortedVec <T> {
170  type Target = Vec <T>;
171  fn deref (&self) -> &Vec <T> {
172    &self.vec
173  }
174}
175impl <T : PartialOrd> Extend <T> for SortedVec <T> {
176  fn extend <I : IntoIterator <Item = T>> (&mut self, iter : I) {
177    for t in iter {
178      let _ = self.insert (t);
179    }
180  }
181}
182impl <T : PartialOrd> FromIterator <T> for SortedVec <T> {
183  fn from_iter <I> (iter : I) -> Self where I : IntoIterator <Item=T> {
184    let mut s = SortedVec::new();
185    s.extend (iter);
186    s
187  }
188}
189impl <T : PartialOrd> IntoIterator for SortedVec <T> {
190  type Item = T;
191  type IntoIter = std::vec::IntoIter<T>;
192  fn into_iter (self) -> Self::IntoIter {
193    self.vec.into_iter()
194  }
195}
196impl<'a, T : PartialOrd> IntoIterator for &'a SortedVec<T> {
197  type Item = &'a T;
198  type IntoIter = std::slice::Iter<'a, T>;
199  fn into_iter (self) -> Self::IntoIter {
200    self.vec.iter()
201  }
202}
203impl <T : PartialOrd + Hash> Hash for SortedVec <T> {
204  fn hash <H : Hasher> (&self, state : &mut H) {
205    let v : &Vec <T> = self.as_ref();
206    v.hash (state);
207  }
208}
209
210//
211//  impl SortedSet
212//
213
214impl <T : PartialOrd> SortedSet <T> {
215  #[inline]
216  pub const fn new() -> Self {
217    SortedSet { set: SortedVec::new() }
218  }
219  #[inline]
220  pub fn with_capacity (capacity : usize) -> Self {
221    SortedSet { set: SortedVec::with_capacity (capacity) }
222  }
223  /// Uses `sort_unstable()` to sort in place and `dedup()` to remove
224  /// duplicates.
225  #[inline]
226  pub fn from_unsorted (vec : Vec <T>) -> Self {
227    let mut set = SortedVec::from_unsorted (vec);
228    set.dedup();
229    SortedSet { set }
230  }
231  /// Insert an element into sorted position, returning the order index at which
232  /// it was placed.
233  #[inline]
234  pub fn insert (&mut self, element : T) -> usize {
235    let _ = self.remove_item (&element);
236    self.set.insert (element)
237  }
238  /// Find the element and return the index with `Ok`, otherwise insert the
239  /// element and return the new element index with `Err`.
240  #[inline]
241  pub fn find_or_insert (&mut self, element : T) -> Result <usize, usize> {
242    self.set.find_or_insert (element)
243  }
244  #[inline]
245  pub fn remove_item (&mut self, item : &T) -> Option <T> {
246    self.set.remove_item (item)
247  }
248  /// Panics if index is out of bounds
249  #[inline]
250  pub fn remove_index (&mut self, index : usize) -> T {
251    self.set.remove_index (index)
252  }
253  #[inline]
254  pub fn pop (&mut self) -> Option <T> {
255    self.set.pop()
256  }
257  #[inline]
258  pub fn clear (&mut self) {
259    self.set.clear()
260  }
261  #[inline]
262  #[expect(mismatched_lifetime_syntaxes)]
263  pub fn drain <R> (&mut self, range : R) -> std::vec::Drain <T> where
264    R : std::ops::RangeBounds <usize>
265  {
266    self.set.drain (range)
267  }
268  #[inline]
269  pub fn retain <F> (&mut self, f : F) where F : FnMut (&T) -> bool {
270    self.set.retain (f)
271  }
272  /// NOTE: `to_vec()` is a slice method that is accessible through deref, use
273  /// this instead to avoid cloning
274  #[inline]
275  pub fn into_vec (self) -> Vec <T> {
276    self.set.into_vec()
277  }
278  /// Apply a closure mutating the sorted vector and use `sort_unstable()`
279  /// to re-sort the mutated vector and `dedup()` to remove any duplicate
280  /// values
281  pub fn mutate_vec <F, O> (&mut self, f : F) -> O where
282    F : FnOnce (&mut Vec <T>) -> O
283  {
284    let res = self.set.mutate_vec (f);
285    self.set.dedup();
286    res
287  }
288  /// The caller must ensure that the provided vector is already sorted and deduped.
289  ///
290  /// ```
291  /// use sorted_vec::partial::SortedSet;
292  /// let v = vec![1.0, 2.0, 3.0, 4.0];
293  /// let _s = unsafe { SortedSet::from_sorted(v) };
294  /// ```
295  ///
296  /// # Safety
297  ///
298  /// Not safe.
299  ///
300  /// # Panics
301  ///
302  /// There will be debug assertions if the input is not sorted or deduped.
303  ///
304  /// ```should_panic
305  /// use sorted_vec::partial::SortedSet;
306  /// let v = vec![4.0, 3.0, 2.0];
307  /// let _s = unsafe { SortedSet::from_sorted(v) };  // panic!
308  /// ```
309  ///
310  /// ```should_panic
311  /// use sorted_vec::partial::SortedSet;
312  /// let v = vec![1.0, 2.0, 3.0, 3.0, 4.0];
313  /// let _s = unsafe { SortedSet::from_sorted(v) };  // panic!
314  /// ```
315  #[inline]
316  pub unsafe fn from_sorted(vec : Vec<T>) -> Self {
317    let set = unsafe { SortedVec::from_sorted(vec) };
318    if cfg!(debug_assertions) {
319      for i in 0..set.len()-1 {
320        #[expect(clippy::manual_assert)]   // T is not Debug, can't use assert
321        if set[i] == set[i+1] {
322          panic!("input contains duplicates")
323        }
324      }
325    }
326    SortedSet { set }
327  }
328}
329impl <T : PartialOrd> Default for SortedSet <T> {
330  fn default() -> Self {
331    Self::new()
332  }
333}
334impl <T : PartialOrd> From <Vec <T>> for SortedSet <T> {
335  fn from (unsorted : Vec <T>) -> Self {
336    Self::from_unsorted (unsorted)
337  }
338}
339impl <T : PartialOrd> std::ops::Deref for SortedSet <T> {
340  type Target = SortedVec <T>;
341  fn deref (&self) -> &SortedVec <T> {
342    &self.set
343  }
344}
345impl <T : PartialOrd> Extend <T> for SortedSet <T> {
346  fn extend <I : IntoIterator <Item = T>> (&mut self, iter : I) {
347    for t in iter {
348      let _ = self.insert (t);
349    }
350  }
351}
352impl <T : PartialOrd> FromIterator <T> for SortedSet <T> {
353  fn from_iter <I> (iter : I) -> Self where I : IntoIterator <Item=T> {
354    let mut s = SortedSet::new();
355    s.extend (iter);
356    s
357  }
358}
359impl<T : PartialOrd> IntoIterator for SortedSet<T> {
360  type Item = T;
361  type IntoIter = std::vec::IntoIter<T>;
362  fn into_iter (self) -> Self::IntoIter {
363    self.set.vec.into_iter()
364  }
365}
366impl<'a, T : PartialOrd> IntoIterator for &'a SortedSet<T> {
367  type Item = &'a T;
368  type IntoIter = std::slice::Iter<'a, T>;
369  fn into_iter (self) -> Self::IntoIter {
370    self.set.iter()
371  }
372}
373impl <T : PartialOrd + Hash> Hash for SortedSet <T> {
374  fn hash <H : Hasher> (&self, state : &mut H) {
375    let v : &Vec <T> = self.as_ref();
376    v.hash (state);
377  }
378}
379
380//
381//  impl ReverseSortedVec
382//
383
384impl <T : PartialOrd> ReverseSortedVec <T> {
385  #[inline]
386  pub const fn new() -> Self {
387    ReverseSortedVec { vec: Vec::new() }
388  }
389  #[inline]
390  pub fn with_capacity (capacity : usize) -> Self {
391    ReverseSortedVec { vec: Vec::with_capacity (capacity) }
392  }
393  /// Uses `sort_unstable_by()` to sort in place.
394  #[inline]
395  pub fn from_unsorted (mut vec : Vec <T>) -> Self {
396    vec.sort_unstable_by (|x,y| partial_compare (x,y).reverse());
397    ReverseSortedVec { vec }
398  }
399  /// Insert an element into (reverse) sorted position, returning the order
400  /// index at which it was placed.
401  ///
402  /// Partial order comparison panics if items are not comparable.
403  pub fn insert (&mut self, element : T) -> usize {
404    let insert_at = match self.binary_search (&element) {
405      Ok (insert_at) | Err (insert_at) => insert_at
406    };
407    self.vec.insert (insert_at, element);
408    insert_at
409  }
410  /// Find the element and return the index with `Ok`, otherwise insert the
411  /// element and return the new element index with `Err`.
412  ///
413  /// Partial order comparison panics if items are not comparable.
414  #[inline]
415  pub fn find_or_insert (&mut self, element : T) -> Result <usize, usize> {
416    self.binary_search (&element)
417      .inspect_err (|&insert_at| self.vec.insert (insert_at, element))
418  }
419  #[inline]
420  pub fn remove_item (&mut self, item : &T) -> Option <T> {
421    match self.vec.binary_search_by (
422      |other_item| partial_compare (other_item, item).reverse()
423    ) {
424      Ok  (remove_at) => Some (self.vec.remove (remove_at)),
425      Err (_)         => None
426    }
427  }
428  /// Panics if index is out of bounds
429  #[inline]
430  pub fn remove_index (&mut self, index : usize) -> T {
431    self.vec.remove (index)
432  }
433  #[inline]
434  pub fn binary_search (&self, x : &T) -> Result <usize, usize> {
435    self.vec.binary_search_by (|y| partial_compare (y, x).reverse())
436  }
437  #[inline]
438  pub fn pop (&mut self) -> Option <T> {
439    self.vec.pop()
440  }
441  #[inline]
442  pub fn clear (&mut self) {
443    self.vec.clear()
444  }
445  pub fn dedup (&mut self) {
446    self.vec.dedup();
447  }
448  #[inline]
449  pub fn dedup_by_key <F, K> (&mut self, key : F) where
450    F : FnMut (&mut T) -> K,
451    K : PartialEq <K>
452  {
453    self.vec.dedup_by_key (key);
454  }
455  #[inline]
456  #[expect(mismatched_lifetime_syntaxes)]
457  pub fn drain <R> (&mut self, range : R) -> std::vec::Drain <T> where
458    R : std::ops::RangeBounds <usize>
459  {
460    self.vec.drain (range)
461  }
462  #[inline]
463  pub fn retain <F> (&mut self, f : F) where F : FnMut (&T) -> bool {
464    self.vec.retain (f)
465  }
466  /// NOTE: `to_vec()` is a slice method that is accessible through deref,
467  /// use this instead to avoid cloning
468  #[inline]
469  pub fn into_vec (self) -> Vec <T> {
470    self.vec
471  }
472  /// Apply a closure mutating the reverse-sorted vector and use
473  /// `sort_unstable_by()` to re-sort the mutated vector
474  pub fn mutate_vec <F, O> (&mut self, f : F) -> O where
475    F : FnOnce (&mut Vec <T>) -> O
476  {
477    let res = f (&mut self.vec);
478    self.vec.sort_unstable_by (|x,y| partial_compare (x,y).reverse());
479    res
480  }
481}
482impl <T : PartialOrd> Default for ReverseSortedVec <T> {
483  fn default() -> Self {
484    Self::new()
485  }
486}
487impl <T : PartialOrd> From <Vec <T>> for ReverseSortedVec <T> {
488  fn from (unsorted : Vec <T>) -> Self {
489    Self::from_unsorted (unsorted)
490  }
491}
492impl <T : PartialOrd> std::ops::Deref for ReverseSortedVec <T> {
493  type Target = Vec <T>;
494  fn deref (&self) -> &Vec <T> {
495    &self.vec
496  }
497}
498impl <T : PartialOrd> Extend <T> for ReverseSortedVec <T> {
499  fn extend <I : IntoIterator <Item = T>> (&mut self, iter : I) {
500    for t in iter {
501      let _ = self.insert (t);
502    }
503  }
504}
505impl <T : PartialOrd> FromIterator <T> for ReverseSortedVec <T> {
506  fn from_iter <I> (iter : I) -> Self where I : IntoIterator <Item=T> {
507    let mut s = ReverseSortedVec::new();
508    s.extend (iter);
509    s
510  }
511}
512impl <T : PartialOrd + Hash> Hash for ReverseSortedVec <T> {
513  fn hash <H : Hasher> (&self, state : &mut H) {
514    let v : &Vec <T> = self.as_ref();
515    v.hash (state);
516  }
517}
518
519//
520//  impl ReverseSortedSet
521//
522
523impl <T : PartialOrd> ReverseSortedSet <T> {
524  #[inline]
525  pub const fn new() -> Self {
526    ReverseSortedSet { set: ReverseSortedVec::new() }
527  }
528  #[inline]
529  pub fn with_capacity (capacity : usize) -> Self {
530    ReverseSortedSet { set: ReverseSortedVec::with_capacity (capacity) }
531  }
532  /// Uses `sort_unstable()` to sort in place and `dedup()` to remove
533  /// duplicates.
534  #[inline]
535  pub fn from_unsorted (vec : Vec <T>) -> Self {
536    let mut set = ReverseSortedVec::from_unsorted (vec);
537    set.dedup();
538    ReverseSortedSet { set }
539  }
540  /// Insert an element into sorted position, returning the order index at which
541  /// it was placed.
542  #[inline]
543  pub fn insert (&mut self, element : T) -> usize {
544    let _ = self.remove_item (&element);
545    self.set.insert (element)
546  }
547  /// Find the element and return the index with `Ok`, otherwise insert the
548  /// element and return the new element index with `Err`.
549  #[inline]
550  pub fn find_or_insert (&mut self, element : T) -> Result <usize, usize> {
551    self.set.find_or_insert (element)
552  }
553  #[inline]
554  pub fn remove_item (&mut self, item : &T) -> Option <T> {
555    self.set.remove_item (item)
556  }
557  /// Panics if index is out of bounds
558  #[inline]
559  pub fn remove_index (&mut self, index : usize) -> T {
560    self.set.remove_index (index)
561  }
562  #[inline]
563  pub fn pop (&mut self) -> Option <T> {
564    self.set.pop()
565  }
566  #[inline]
567  pub fn clear (&mut self) {
568    self.set.clear()
569  }
570  #[inline]
571  #[expect(mismatched_lifetime_syntaxes)]
572  pub fn drain <R> (&mut self, range : R) -> std::vec::Drain <T> where
573    R : std::ops::RangeBounds <usize>
574  {
575    self.set.drain (range)
576  }
577  #[inline]
578  pub fn retain <F> (&mut self, f : F) where F : FnMut (&T) -> bool {
579    self.set.retain (f)
580  }
581  /// NOTE: `to_vec()` is a slice method that is accessible through deref, use
582  /// this instead to avoid cloning
583  #[inline]
584  pub fn into_vec (self) -> Vec <T> {
585    self.set.into_vec()
586  }
587  /// Apply a closure mutating the sorted vector and use `sort_unstable()`
588  /// to re-sort the mutated vector and `dedup()` to remove any duplicate
589  /// values
590  pub fn mutate_vec <F, O> (&mut self, f : F) -> O where
591    F : FnOnce (&mut Vec <T>) -> O
592  {
593    let res = self.set.mutate_vec (f);
594    self.set.dedup();
595    res
596  }
597}
598impl <T : PartialOrd> Default for ReverseSortedSet <T> {
599  fn default() -> Self {
600    Self::new()
601  }
602}
603impl <T : PartialOrd> From <Vec <T>> for ReverseSortedSet <T> {
604  fn from (unsorted : Vec <T>) -> Self {
605    Self::from_unsorted (unsorted)
606  }
607}
608impl <T : PartialOrd> std::ops::Deref for ReverseSortedSet <T> {
609  type Target = ReverseSortedVec <T>;
610  fn deref (&self) -> &ReverseSortedVec <T> {
611    &self.set
612  }
613}
614impl <T : PartialOrd> Extend <T> for ReverseSortedSet <T> {
615  fn extend <I : IntoIterator <Item = T>> (&mut self, iter : I) {
616    for t in iter {
617      let _ = self.insert (t);
618    }
619  }
620}
621impl <T : PartialOrd> FromIterator <T> for ReverseSortedSet <T> {
622  fn from_iter <I> (iter : I) -> Self where I : IntoIterator <Item=T> {
623    let mut s = ReverseSortedSet::new();
624    s.extend (iter);
625    s
626  }
627}
628impl <T : PartialOrd + Hash> Hash for ReverseSortedSet <T> {
629  fn hash <H : Hasher> (&self, state : &mut H) {
630    let v : &Vec <T> = self.as_ref();
631    v.hash (state);
632  }
633}
634
635#[cfg(test)]
636mod tests {
637  // NOTE: some tests may break in future version of Rust: according to the
638  // documentation of binary_search, if there are multiple matches the index is
639  // chosen deterministically but is subject to change in future versions of
640  // Rust
641  use super::*;
642
643  #[test]
644  fn sorted_vec() {
645    let mut v = SortedVec::new();
646    assert_eq!(v.insert (5.0), 0);
647    assert_eq!(v.insert (3.0), 0);
648    assert_eq!(v.insert (4.0), 1);
649    assert_eq!(v.insert (4.0), 1);
650    assert_eq!(v.find_or_insert (4.0), Ok (2));
651    assert_eq!(v.len(), 4);
652    v.dedup();
653    assert_eq!(v.len(), 3);
654    assert_eq!(v.binary_search (&3.0), Ok (0));
655    assert_eq!(*SortedVec::from_unsorted (
656      vec![  5.0, -10.0, 99.0, -11.0,  2.0, 17.0, 10.0]),
657      vec![-11.0, -10.0,  2.0,   5.0, 10.0, 17.0, 99.0]);
658    assert_eq!(SortedVec::from_unsorted (
659      vec![  5.0, -10.0, 99.0, -11.0,  2.0, 17.0, 10.0]),
660      vec![  5.0, -10.0, 99.0, -11.0,  2.0, 17.0, 10.0].into());
661    let mut v = SortedVec::new();
662    v.extend([5.0, -10.0, 99.0, -11.0, 2.0, 17.0, 10.0]);
663    assert_eq!(
664      v.drain(..).collect::<Vec <f32>>(),
665      vec![-11.0, -10.0, 2.0, 5.0, 10.0, 17.0, 99.0]);
666    let v = SortedVec::from_iter (
667      [5.0, -10.0, 99.0, -11.0, 2.0, 17.0, 10.0]);
668    assert_eq!(**v, [-11.0, -10.0, 2.0, 5.0, 10.0, 17.0, 99.0]);
669  }
670
671  #[test]
672  fn sorted_set() {
673    let mut s = SortedSet::new();
674    assert_eq!(s.insert (5.0), 0);
675    assert_eq!(s.insert (3.0), 0);
676    assert_eq!(s.insert (4.0), 1);
677    assert_eq!(s.insert (4.0), 1);
678    assert_eq!(s.find_or_insert (4.0), Ok (1));
679    assert_eq!(s.len(), 3);
680    assert_eq!(s.binary_search (&3.0), Ok (0));
681    assert_eq!(**SortedSet::from_unsorted (
682      vec![  5.0, -10.0, 99.0, -10.0, -11.0,  10.0, 2.0, 17.0, 10.0]),
683      vec![-11.0, -10.0,  2.0,   5.0, 10.0, 17.0, 99.0]);
684    assert_eq!(SortedSet::from_unsorted (
685      vec![  5.0, -10.0, 99.0, -10.0, -11.0,  10.0, 2.0, 17.0, 10.0]),
686      vec![  5.0, -10.0, 99.0, -10.0, -11.0,  10.0, 2.0, 17.0, 10.0].into());
687    let mut s = SortedSet::new();
688    s.extend(
689      vec![5.0, -11.0, -10.0, 99.0, -11.0, 2.0, 17.0, 2.0, 10.0]);
690    assert_eq!(**s, vec![-11.0, -10.0, 2.0, 5.0, 10.0, 17.0, 99.0]);
691    let () = s.mutate_vec (|s|{
692      s[0] = 5.0;
693      s[3] = 11.0;
694    });
695    assert_eq!(
696      s.drain(..).collect::<Vec <f32>>(),
697      vec![-10.0, 2.0, 5.0, 10.0, 11.0, 17.0, 99.0]);
698    let s = SortedSet::from_iter (
699      [5.0, -11.0, -10.0, 99.0, -11.0, 2.0, 17.0, 2.0, 10.0]);
700    assert_eq!(***s, [-11.0, -10.0, 2.0, 5.0, 10.0, 17.0, 99.0]);
701  }
702
703  #[test]
704  fn reverse_sorted_vec() {
705    let mut v = ReverseSortedVec::new();
706    assert_eq!(v.insert (5.0), 0);
707    assert_eq!(v.insert (3.0), 1);
708    assert_eq!(v.insert (4.0), 1);
709    assert_eq!(v.find_or_insert (6.0), Err (0));
710    assert_eq!(v.insert (4.0), 2);
711    assert_eq!(v.find_or_insert (4.0), Ok (3));
712    assert_eq!(v.len(), 5);
713    v.dedup();
714    assert_eq!(v.len(), 4);
715    assert_eq!(v.binary_search (&3.0), Ok (3));
716    assert_eq!(*ReverseSortedVec::from_unsorted (
717      vec![5.0, -10.0, 99.0, -11.0, 2.0,  17.0,  10.0]),
718      vec![99.0, 17.0, 10.0,   5.0, 2.0, -10.0, -11.0]);
719    assert_eq!(ReverseSortedVec::from_unsorted (
720      vec![5.0, -10.0, 99.0, -11.0, 2.0,  17.0,  10.0]),
721      vec![5.0, -10.0, 99.0, -11.0, 2.0,  17.0,  10.0].into());
722    let mut v = ReverseSortedVec::new();
723    v.extend([5.0, -10.0, 99.0, -11.0, 2.0, 17.0, 10.0]);
724    assert_eq!(
725      v.drain(..).collect::<Vec <f32>>(),
726      vec![99.0, 17.0, 10.0, 5.0, 2.0, -10.0, -11.0]);
727    let v = ReverseSortedVec::from_iter (
728      [5.0, -10.0, 99.0, -11.0, 2.0, 17.0, 10.0]);
729    assert_eq!(**v, [99.0, 17.0, 10.0, 5.0, 2.0, -10.0, -11.0]);
730  }
731
732  #[test]
733  fn reverse_sorted_set() {
734    let mut s = ReverseSortedSet::new();
735    assert_eq!(s.insert (5.0), 0);
736    assert_eq!(s.insert (3.0), 1);
737    assert_eq!(s.insert (4.0), 1);
738    assert_eq!(s.find_or_insert (6.0), Err (0));
739    assert_eq!(s.insert (4.0), 2);
740    assert_eq!(s.find_or_insert (4.0), Ok (2));
741    assert_eq!(s.len(), 4);
742    assert_eq!(s.binary_search (&3.0), Ok (3));
743    assert_eq!(**ReverseSortedSet::from_unsorted (
744      vec![5.0, -10.0, 99.0, -11.0, 2.0,  17.0,  10.0, -10.0]),
745      vec![99.0, 17.0, 10.0,   5.0, 2.0, -10.0, -11.0]);
746    assert_eq!(ReverseSortedSet::from_unsorted (
747      vec![5.0, -10.0, 99.0, -11.0, 2.0,  17.0,  10.0, -10.0]),
748      vec![5.0, -10.0, 99.0, -11.0, 2.0,  17.0,  10.0, -10.0].into());
749    let mut s = ReverseSortedSet::new();
750    s.extend(vec![5.0, -10.0, 2.0, 99.0, -11.0, -11.0, 2.0, 17.0, 10.0]);
751    assert_eq!(**s, vec![99.0, 17.0, 10.0, 5.0, 2.0, -10.0, -11.0]);
752    let () = s.mutate_vec (|s|{
753      s[6] = 17.0;
754      s[3] = 1.0;
755    });
756    assert_eq!(
757      s.drain(..).collect::<Vec <f32>>(),
758      vec![99.0, 17.0, 10.0, 2.0, 1.0, -10.0]);
759    let s = ReverseSortedSet::from_iter(
760      [5.0, -10.0, 2.0, 99.0, -11.0, -11.0, 2.0, 17.0, 10.0]);
761    assert_eq!(***s, [99.0, 17.0, 10.0, 5.0, 2.0, -10.0, -11.0]);
762  }
763}
sorted_vec/partial.rs

sorted_vec/
partial.rs
