sorted_vec/
lib.rs

1//! Sorted vectors.
2//!
3//! [Repository](https://gitlab.com/spearman/sorted-vec)
4//!
5//! - `SortedVec` -- sorted from least to greatest, may contain duplicates
6//! - `SortedSet` -- sorted from least to greatest, unique elements
7//! - `ReverseSortedVec` -- sorted from greatest to least, may contain
8//!   duplicates
9//! - `ReverseSortedSet` -- sorted from greatest to least, unique elements
10//!
11//! The `partial` module provides sorted vectors of types that only implement
12//! `PartialOrd` where comparison of incomparable elements results in runtime
13//! panic.
14
15#[cfg(feature = "serde")]
16#[macro_use] extern crate serde;
17
18use std::hash::{Hash, Hasher};
19
20pub mod partial;
21
22/// Forward sorted vector
23#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
24#[cfg_attr(all(feature = "serde", not(feature = "serde-nontransparent")),
25  serde(transparent))]
26#[derive(Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
27pub struct SortedVec <T : Ord> {
28  #[cfg_attr(feature = "serde", serde(deserialize_with = "SortedVec::parse_vec"))]
29  #[cfg_attr(feature = "serde",
30    serde(bound(deserialize = "T : serde::Deserialize <'de>")))]
31  vec : Vec <T>
32}
33
34/// Forward sorted set
35#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
36#[cfg_attr(all(feature = "serde", not(feature = "serde-nontransparent")),
37  serde(transparent))]
38#[derive(Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
39pub struct SortedSet <T : Ord> {
40  #[cfg_attr(feature = "serde", serde(deserialize_with = "SortedSet::parse_vec"))]
41  #[cfg_attr(feature = "serde",
42    serde(bound(deserialize = "T : serde::Deserialize <'de>")))]
43  set : SortedVec <T>
44}
45
46/// Value returned when `find_or_insert` is used.
47#[derive(PartialEq, PartialOrd, Eq, Ord, Debug, Hash)]
48pub enum FindOrInsert {
49  /// Contains a found index
50  Found(usize),
51
52  /// Contains an inserted index
53  Inserted(usize),
54}
55
56/// Converts from the `binary_search` result type into the `FindOrInsert` type
57impl From<Result<usize, usize>> for FindOrInsert {
58  fn from(result: Result<usize, usize>) -> Self {
59    match result {
60      Result::Ok(value) => FindOrInsert::Found(value),
61      Result::Err(value) => FindOrInsert::Inserted(value),
62    }
63  }
64}
65
66impl FindOrInsert {
67  /// Get the index of the element that was either found or inserted.
68  pub const fn index (&self) -> usize {
69    match self {
70      FindOrInsert::Found(value) | FindOrInsert::Inserted(value) => *value
71    }
72  }
73
74  /// If an equivalent element was found in the container, get the value of
75  /// its index. Otherwise get None.
76  pub const fn found (&self) -> Option<usize> {
77    match self {
78      FindOrInsert::Found(value) => Some(*value),
79      FindOrInsert::Inserted(_) => None
80    }
81  }
82
83  /// If the provided element was inserted into the container, get the value
84  /// of its index. Otherwise get None.
85  pub const fn inserted (&self) -> Option<usize> {
86    match self {
87      FindOrInsert::Found(_) => None,
88      FindOrInsert::Inserted(value) => Some(*value)
89    }
90  }
91
92  /// Returns true if the element was found.
93  pub const fn is_found (&self) -> bool {
94    matches!(self, FindOrInsert::Found(_))
95  }
96
97  /// Returns true if the element was inserted.
98  pub const fn is_inserted (&self) -> bool {
99    matches!(self, FindOrInsert::Inserted(_))
100  }
101}
102
103//
104//  impl SortedVec
105//
106
107impl <T : Ord> SortedVec <T> {
108  #[inline]
109  pub const fn new() -> Self {
110    SortedVec { vec: Vec::new() }
111  }
112  #[inline]
113  pub fn with_capacity (capacity : usize) -> Self {
114    SortedVec { vec: Vec::with_capacity (capacity) }
115  }
116  /// Uses `sort_unstable()` to sort in place.
117  #[inline]
118  pub fn from_unsorted (mut vec : Vec <T>) -> Self {
119    vec.sort_unstable();
120    SortedVec { vec }
121  }
122  /// Insert an element into sorted position, returning the order index at which
123  /// it was placed.
124  pub fn insert (&mut self, element : T) -> usize {
125    let insert_at = match self.binary_search (&element) {
126      Ok (insert_at) | Err (insert_at) => insert_at
127    };
128    self.vec.insert (insert_at, element);
129    insert_at
130  }
131  /// Find the element and return the index with `Ok`, otherwise insert the
132  /// element and return the new element index with `Err`.
133  pub fn find_or_insert (&mut self, element : T) -> FindOrInsert {
134    self.binary_search (&element)
135      .inspect_err (|&insert_at| self.vec.insert (insert_at, element))
136      .into()
137  }
138  /// Same as insert, except performance is O(1) when the element belongs at the
139  /// back of the container. This avoids an O(log(N)) search for inserting
140  /// elements at the back.
141  #[inline]
142  pub fn push(&mut self, element: T) -> usize {
143    if let Some(last) = self.vec.last() {
144      let cmp = element.cmp(last);
145      if cmp == std::cmp::Ordering::Greater || cmp == std::cmp::Ordering::Equal {
146        // The new element is greater than or equal to the current last element,
147        // so we can simply push it onto the vec.
148        self.vec.push(element);
149        self.vec.len() - 1
150      } else {
151        // The new element is less than the last element in the container, so we
152        // cannot simply push. We will fall back on the normal insert behavior.
153        self.insert(element)
154      }
155    } else {
156      // If there is no last element then the container must be empty, so we
157      // can simply push the element and return its index, which must be 0.
158      self.vec.push(element);
159      0
160    }
161  }
162  /// Reserves additional capacity in the underlying vector.
163  /// See `std::vec::Vec::reserve`.
164  #[inline]
165  pub fn reserve(&mut self, additional: usize) {
166    self.vec.reserve(additional);
167  }
168  /// Same as `find_or_insert`, except performance is O(1) when the element
169  /// belongs at the back of the container.
170  pub fn find_or_push(&mut self, element: T) -> FindOrInsert {
171    if let Some(last) = self.vec.last() {
172      let cmp = element.cmp(last);
173      if cmp == std::cmp::Ordering::Equal {
174        FindOrInsert::Found(self.vec.len() - 1)
175      } else if cmp == std::cmp::Ordering::Greater {
176        self.vec.push(element);
177        FindOrInsert::Inserted(self.vec.len() - 1)
178      } else {
179        // The new element is less than the last element in the container, so we
180        // need to fall back on the regular find_or_insert
181        self.find_or_insert(element)
182      }
183    } else {
184      // If there is no last element then the container must be empty, so we can
185      // simply push the element and return that it was inserted.
186      self.vec.push(element);
187      FindOrInsert::Inserted(0)
188    }
189  }
190  #[inline]
191  pub fn remove_item (&mut self, item : &T) -> Option <T> {
192    match self.vec.binary_search (item) {
193      Ok  (remove_at) => Some (self.vec.remove (remove_at)),
194      Err (_)         => None
195    }
196  }
197  /// Panics if index is out of bounds
198  #[inline]
199  pub fn remove_index (&mut self, index : usize) -> T {
200    self.vec.remove (index)
201  }
202  #[inline]
203  pub fn pop (&mut self) -> Option <T> {
204    self.vec.pop()
205  }
206  #[inline]
207  pub fn clear (&mut self) {
208    self.vec.clear()
209  }
210  #[inline]
211  pub fn dedup (&mut self) {
212    self.vec.dedup();
213  }
214  #[inline]
215  pub fn dedup_by_key <F, K> (&mut self, key : F) where
216    F : FnMut (&mut T) -> K,
217    K : PartialEq <K>
218  {
219    self.vec.dedup_by_key (key);
220  }
221  #[inline]
222  #[expect(mismatched_lifetime_syntaxes)]
223  pub fn drain <R> (&mut self, range : R) -> std::vec::Drain <T> where
224    R : std::ops::RangeBounds <usize>
225  {
226    self.vec.drain (range)
227  }
228  #[inline]
229  pub fn retain <F> (&mut self, f : F) where F : FnMut (&T) -> bool {
230    self.vec.retain (f)
231  }
232  /// NOTE: `to_vec()` is a slice method that is accessible through deref, use
233  /// this instead to avoid cloning
234  #[inline]
235  pub fn into_vec (self) -> Vec <T> {
236    self.vec
237  }
238  /// Apply a closure mutating the sorted vector and use `sort_unstable()`
239  /// to re-sort the mutated vector
240  pub fn mutate_vec <F, O> (&mut self, f : F) -> O where
241    F : FnOnce (&mut Vec <T>) -> O
242  {
243    let res = f (&mut self.vec);
244    self.vec.sort_unstable();
245    res
246  }
247  /// The caller must ensure that the provided vector is already sorted.
248  ///
249  /// # Safety
250  ///
251  /// There is a debug assertion that the input is sorted.
252  ///
253  /// ```should_panic
254  /// use sorted_vec::SortedVec;
255  /// let v = vec![4, 3, 2];
256  /// let _s = unsafe { SortedVec::from_sorted(v) };  // panic!
257  /// ```
258  #[inline]
259  pub unsafe fn from_sorted(vec : Vec<T>) -> Self {
260    debug_assert!(vec.is_sorted());
261    SortedVec { vec }
262  }
263  /// Unsafe access to the underlying vector. The caller must ensure that any
264  /// changes to the values in the vector do not impact the ordering of the
265  /// elements inside, or else this container will misbehave.
266  ///
267  /// # Safety
268  ///
269  /// Not safe.
270  pub const unsafe fn get_unchecked_mut_vec(&mut self) -> &mut Vec<T> {
271    &mut self.vec
272  }
273
274  /// Perform sorting on the input sequence when deserializing with `serde`.
275  ///
276  /// Use with `#[serde(deserialize_with = "SortedVec::deserialize_unsorted")]`:
277  /// ```text
278  /// #[derive(Debug, Eq, Ord, PartialEq, PartialOrd, Deserialize, Serialize)]
279  /// pub struct Foo {
280  ///   #[serde(deserialize_with = "SortedVec::deserialize_unsorted")]
281  ///   pub v : SortedVec <u64>
282  /// }
283  /// ```
284  #[cfg(feature = "serde")]
285  pub fn deserialize_unsorted <'de, D> (deserializer : D)
286    -> Result <Self, D::Error>
287  where
288    D : serde::Deserializer <'de>,
289    T : serde::Deserialize <'de>
290  {
291    use serde::Deserialize;
292    let v = Vec::deserialize (deserializer)?;
293    Ok (SortedVec::from_unsorted (v))
294  }
295
296  #[cfg(feature = "serde")]
297  fn parse_vec <'de, D> (deserializer : D) -> Result <Vec <T>, D::Error> where
298    D : serde::Deserializer <'de>,
299    T : serde::Deserialize <'de>
300  {
301    use serde::Deserialize;
302    use serde::de::Error;
303    let v = Vec::deserialize (deserializer)?;
304    if !v.is_sorted() {
305      Err (D::Error::custom ("input sequence is not sorted"))
306    } else {
307      Ok (v)
308    }
309  }
310}
311impl <T : Ord> Default for SortedVec <T> {
312  fn default() -> Self {
313    Self::new()
314  }
315}
316impl <T : Ord> From <Vec <T>> for SortedVec <T> {
317  fn from (unsorted : Vec <T>) -> Self {
318    Self::from_unsorted (unsorted)
319  }
320}
321impl <T : Ord> std::ops::Deref for SortedVec <T> {
322  type Target = Vec <T>;
323  fn deref (&self) -> &Vec <T> {
324    &self.vec
325  }
326}
327impl <T : Ord> Extend <T> for SortedVec <T> {
328  fn extend <I : IntoIterator <Item = T>> (&mut self, iter : I) {
329    for t in iter {
330      let _ = self.insert (t);
331    }
332  }
333}
334impl <T : Ord> FromIterator <T> for SortedVec <T> {
335  fn from_iter <I> (iter : I) -> Self where I : IntoIterator <Item=T> {
336    let mut s = SortedVec::new();
337    s.extend (iter);
338    s
339  }
340}
341impl <T : Ord> IntoIterator for SortedVec <T> {
342  type Item = T;
343  type IntoIter = std::vec::IntoIter <T>;
344  fn into_iter (self) -> Self::IntoIter {
345    self.vec.into_iter()
346  }
347}
348impl <'a, T : Ord> IntoIterator for &'a SortedVec <T> {
349  type Item = &'a T;
350  type IntoIter = std::slice::Iter <'a, T>;
351  fn into_iter (self) -> Self::IntoIter {
352    self.vec.iter()
353  }
354}
355impl <T : Ord + Hash> Hash for SortedVec <T> {
356  fn hash <H : Hasher> (&self, state : &mut H) {
357    let v : &Vec <T> = self.as_ref();
358    v.hash (state);
359  }
360}
361
362//
363//  impl SortedSet
364//
365
366impl <T : Ord> SortedSet <T> {
367  #[inline]
368  pub const fn new() -> Self {
369    SortedSet { set: SortedVec::new() }
370  }
371  #[inline]
372  pub fn with_capacity (capacity : usize) -> Self {
373    SortedSet { set: SortedVec::with_capacity (capacity) }
374  }
375  /// Uses `sort_unstable()` to sort in place and `dedup()` to remove
376  /// duplicates.
377  #[inline]
378  pub fn from_unsorted (vec : Vec <T>) -> Self {
379    let mut set = SortedVec::from_unsorted (vec);
380    set.dedup();
381    SortedSet { set }
382  }
383  /// Insert an element into sorted position, returning the order index at which
384  /// it was placed. If an existing item was found it will be returned.
385  #[inline]
386  pub fn replace (&mut self, mut element : T) -> (usize, Option <T>) {
387    match self.set.binary_search(&element) {
388      Ok (existing_index) => {
389        unsafe {
390          // If binary_search worked correctly, then this must be the index of a
391          // valid element to get from the vector.
392          std::mem::swap (&mut element,
393            self.set.vec.get_unchecked_mut(existing_index))
394        }
395        (existing_index, Some (element))
396      },
397      Err (insert_index) => {
398        self.set.vec.insert(insert_index, element);
399        (insert_index, None)
400      }
401    }
402  }
403  /// Find the element and return the index with `Ok`, otherwise insert the
404  /// element and return the new element index with `Err`.
405  #[inline]
406  pub fn find_or_insert (&mut self, element : T) -> FindOrInsert {
407    self.set.find_or_insert (element)
408  }
409  /// Same as replace, except performance is O(1) when the element belongs at
410  /// the back of the container. This avoids an O(log(N)) search for inserting
411  /// elements at the back.
412  #[inline]
413  pub fn push(&mut self, element: T) -> (usize, Option<T>) {
414    if let Some(last) = self.vec.last() {
415      let cmp = element.cmp(last);
416      if cmp == std::cmp::Ordering::Greater {
417        // The new element is greater than the current last element, so we can
418        // simply push it onto the vec.
419        self.set.vec.push(element);
420        (self.vec.len() - 1, None)
421      } else if cmp == std::cmp::Ordering::Equal {
422        // The new element is equal to the last element, so we can simply return
423        // the last index in the vec and the value that is being replaced.
424        let original = self.set.vec.pop();
425        self.set.vec.push(element);
426        (self.vec.len() - 1, original)
427      } else {
428        // The new element is less than the last element, so we need to fall
429        // back on the regular insert function.
430        self.replace(element)
431      }
432    } else {
433      // If there is no last element then the container must be empty, so we can
434      // simply push the element and return its index, which must be 0.
435      self.set.vec.push(element);
436      (0, None)
437    }
438  }
439  /// Reserves additional capacity in the underlying vector.
440  /// See `std::vec::Vec::reserve`.
441  #[inline]
442  pub fn reserve(&mut self, additional: usize) {
443    self.set.reserve(additional);
444  }
445  /// Same as `find_or_insert`, except performance is O(1) when the element
446  /// belongs at the back of the container.
447  pub fn find_or_push(&mut self, element: T) -> FindOrInsert {
448    self.set.find_or_insert(element)
449  }
450  #[inline]
451  pub fn remove_item (&mut self, item : &T) -> Option <T> {
452    self.set.remove_item (item)
453  }
454  /// Panics if index is out of bounds
455  #[inline]
456  pub fn remove_index (&mut self, index : usize) -> T {
457    self.set.remove_index (index)
458  }
459  #[inline]
460  pub fn pop (&mut self) -> Option <T> {
461    self.set.pop()
462  }
463  #[inline]
464  pub fn clear (&mut self) {
465    self.set.clear()
466  }
467  #[inline]
468  #[expect(mismatched_lifetime_syntaxes)]
469  pub fn drain <R> (&mut self, range : R) -> std::vec::Drain <T> where
470    R : std::ops::RangeBounds <usize>
471  {
472    self.set.drain (range)
473  }
474  #[inline]
475  pub fn retain <F> (&mut self, f : F) where F : FnMut (&T) -> bool {
476    self.set.retain (f)
477  }
478  /// NOTE: `to_vec()` is a slice method that is accessible through deref, use
479  /// this instead to avoid cloning
480  #[inline]
481  pub fn into_vec (self) -> Vec <T> {
482    self.set.into_vec()
483  }
484  /// Apply a closure mutating the sorted vector and use `sort_unstable()`
485  /// to re-sort the mutated vector and `dedup()` to remove any duplicate
486  /// values
487  pub fn mutate_vec <F, O> (&mut self, f : F) -> O where
488    F : FnOnce (&mut Vec <T>) -> O
489  {
490    let res = self.set.mutate_vec (f);
491    self.set.dedup();
492    res
493  }
494  /// The caller must ensure that the provided vector is already sorted and deduped.
495  ///
496  /// # Safety
497  ///
498  /// There will be debug assertions if the input is not sorted or deduped.
499  ///
500  /// ```should_panic
501  /// use sorted_vec::SortedSet;
502  /// let v = vec![4, 3, 2];
503  /// let _s = unsafe { SortedSet::from_sorted(v) };  // panic!
504  /// ```
505  ///
506  /// ```should_panic
507  /// use sorted_vec::SortedSet;
508  /// let v = vec![1, 2, 3, 3, 4];
509  /// let _s = unsafe { SortedSet::from_sorted(v) };  // panic!
510  /// ```
511  #[inline]
512  pub unsafe fn from_sorted(vec : Vec<T>) -> Self {
513    #[expect(clippy::debug_assert_with_mut_call)]
514    if cfg!(debug_assertions) {
515      let mut unique = std::collections::BTreeSet::new();
516      debug_assert!(vec.iter().all(|x| unique.insert(x)));
517    }
518    let set = unsafe { SortedVec::from_sorted(vec) };
519    SortedSet { set }
520  }
521  /// Unsafe access to the underlying vector. The caller must ensure that any
522  /// changes to the values in the vector do not impact the ordering of the
523  /// elements inside, or else this container will misbehave.
524  ///
525  /// # Safety
526  ///
527  /// Not safe.
528  pub const unsafe fn get_unchecked_mut_vec(&mut self) -> &mut Vec<T> {
529    unsafe { self.set.get_unchecked_mut_vec() }
530  }
531
532  /// Perform deduplication and sorting on the input sequence when deserializing
533  /// with `serde`.
534  ///
535  /// Use with
536  /// `#[serde(deserialize_with = "SortedSet::deserialize_dedup_unsorted")]`:
537  /// ```text
538  /// #[derive(Debug, Eq, Ord, PartialEq, PartialOrd, Deserialize, Serialize)]
539  /// pub struct Foo {
540  ///   #[serde(deserialize_with = "SortedSet::deserialize_dedup_unsorted")]
541  ///   pub s : SortedSet <u64>
542  /// }
543  /// ```
544  #[cfg(feature = "serde")]
545  pub fn deserialize_dedup_unsorted <'de, D> (deserializer : D)
546    -> Result <Self, D::Error>
547  where
548    D : serde::Deserializer <'de>,
549    T : serde::Deserialize <'de>
550  {
551    use serde::Deserialize;
552    let v = Vec::deserialize (deserializer)?;
553    Ok (SortedSet::from_unsorted (v))
554  }
555
556  #[cfg(feature = "serde")]
557  fn parse_vec <'de, D> (deserializer : D)
558    -> Result <SortedVec <T>, D::Error>
559  where
560    D : serde::Deserializer <'de>,
561    T : serde::Deserialize <'de>
562  {
563    use serde::Deserialize;
564    use serde::de::Error;
565    let mut vec = Vec::deserialize (deserializer)?;
566    let input_len = vec.len();
567    vec.dedup();
568    if vec.len() != input_len {
569      Err (D::Error::custom ("input set contains duplicate values"))
570    } else if !vec.is_sorted() {
571      Err (D::Error::custom ("input set is not sorted"))
572    } else {
573      Ok (SortedVec { vec })
574    }
575  }
576}
577impl <T : Ord> Default for SortedSet <T> {
578  fn default() -> Self {
579    Self::new()
580  }
581}
582impl <T : Ord> From <Vec <T>> for SortedSet <T> {
583  fn from (unsorted : Vec <T>) -> Self {
584    Self::from_unsorted (unsorted)
585  }
586}
587impl <T : Ord> std::ops::Deref for SortedSet <T> {
588  type Target = SortedVec <T>;
589  fn deref (&self) -> &SortedVec <T> {
590    &self.set
591  }
592}
593impl <T : Ord> Extend <T> for SortedSet <T> {
594  fn extend <I : IntoIterator <Item = T>> (&mut self, iter : I) {
595    for t in iter {
596      let _ = self.find_or_insert (t);
597    }
598  }
599}
600impl <T : Ord> FromIterator <T> for SortedSet <T> {
601  fn from_iter <I> (iter : I) -> Self where I : IntoIterator <Item=T> {
602    let mut s = SortedSet::new();
603    s.extend (iter);
604    s
605  }
606}
607impl <T : Ord> IntoIterator for SortedSet <T> {
608  type Item = T;
609  type IntoIter = std::vec::IntoIter <T>;
610  fn into_iter (self) -> Self::IntoIter {
611    self.set.into_iter()
612  }
613}
614impl <'a, T : Ord> IntoIterator for &'a SortedSet <T> {
615  type Item = &'a T;
616  type IntoIter = std::slice::Iter <'a, T>;
617  fn into_iter (self) -> Self::IntoIter {
618    self.set.iter()
619  }
620}
621impl <T : Ord + Hash> Hash for SortedSet <T> {
622  fn hash <H : Hasher> (&self, state : &mut H) {
623    let v : &Vec <T> = self.as_ref();
624    v.hash (state);
625  }
626}
627
628/// Reverse-sorted Containers.
629///
630/// Use these containers to have the vector sorted in the reverse order of its
631/// usual comparison.
632///
633/// Note that objects going into the reverse container needs to be wrapped in
634/// `std::cmp::Reverse`.
635///
636/// # Examples
637///
638/// ```
639/// use std::cmp::Reverse;
640/// use sorted_vec::ReverseSortedVec;
641///
642/// let mut vec = ReverseSortedVec::<u64>::new();
643/// vec.insert(Reverse(10));
644/// vec.insert(Reverse(15));
645/// assert_eq!(vec.last().unwrap().0, 10);
646/// ```
647pub type ReverseSortedVec<T> = SortedVec<std::cmp::Reverse<T>>;
648pub type ReverseSortedSet<T> = SortedSet<std::cmp::Reverse<T>>;
649
650#[cfg(test)]
651mod tests {
652  // NOTE: some tests may break in future version of Rust: according to the
653  // documentation of binary_search, if there are multiple matches the index is
654  // chosen deterministically but is subject to change in future versions of
655  // Rust
656  use super::*;
657  use std::cmp::Reverse;
658
659  #[test]
660  fn sorted_vec() {
661    let mut v = SortedVec::new();
662    assert_eq!(v.insert (5), 0);
663    assert_eq!(v.insert (3), 0);
664    assert_eq!(v.insert (4), 1);
665    assert_eq!(v.insert (4), 1);
666    assert_eq!(v.find_or_insert (4), FindOrInsert::Found (2));
667    assert_eq!(v.find_or_insert (4).index(), 2);
668    assert_eq!(v.len(), 4);
669    v.dedup();
670    assert_eq!(v.len(), 3);
671    assert_eq!(v.binary_search (&3), Ok (0));
672    assert_eq!(*SortedVec::from_unsorted (
673      vec![5, -10, 99, -11, 2, 17, 10]),
674      vec![-11, -10, 2, 5, 10, 17, 99]);
675    assert_eq!(SortedVec::from_unsorted (
676      vec![5, -10, 99, -11, 2, 17, 10]),
677      vec![5, -10, 99, -11, 2, 17, 10].into());
678    let mut v = SortedVec::new();
679    v.extend([5, -10, 99, -11, 2, 17, 10]);
680    assert_eq!(*v, vec![-11, -10, 2, 5, 10, 17, 99]);
681    let () = v.mutate_vec (|v|{
682      v[0] = 11;
683      v[3] = 1;
684    });
685    assert_eq!(
686      v.drain(..).collect::<Vec <i32>>(),
687      vec![-10, 1, 2, 10, 11, 17, 99]);
688    let v = SortedVec::from_iter ([5, -10, 99, -11, 2, 17, 10]);
689    assert_eq!(**v, [-11, -10, 2, 5, 10, 17, 99]);
690  }
691
692  #[test]
693  fn sorted_vec_push() {
694    let mut v = SortedVec::new();
695    assert_eq!(v.push (5), 0);
696    assert_eq!(v.push (3), 0);
697    assert_eq!(v.push (4), 1);
698    assert_eq!(v.push (4), 1);
699    assert_eq!(v.find_or_push (4), FindOrInsert::Found (2));
700    assert_eq!(v.find_or_push (4).index(), 2);
701    assert_eq!(v.len(), 4);
702    v.dedup();
703    assert_eq!(v.len(), 3);
704    assert_eq!(v.binary_search (&3), Ok (0));
705    assert_eq!(*SortedVec::from_unsorted (
706      vec![5, -10, 99, -11, 2, 17, 10]),
707      vec![-11, -10, 2, 5, 10, 17, 99]);
708    assert_eq!(SortedVec::from_unsorted (
709      vec![5, -10, 99, -11, 2, 17, 10]),
710      vec![5, -10, 99, -11, 2, 17, 10].into());
711    let mut v = SortedVec::new();
712    v.extend([5, -10, 99, -11, 2, 17, 10]);
713    assert_eq!(*v, vec![-11, -10, 2, 5, 10, 17, 99]);
714    let () = v.mutate_vec (|v|{
715      v[0] = 11;
716      v[3] = 1;
717    });
718    assert_eq!(
719      v.drain(..).collect::<Vec <i32>>(),
720      vec![-10, 1, 2, 10, 11, 17, 99]);
721  }
722
723  #[test]
724  fn sorted_set() {
725    let mut s = SortedSet::new();
726    assert_eq!(s.replace (5), (0, None));
727    assert_eq!(s.replace (3), (0, None));
728    assert_eq!(s.replace (4), (1, None));
729    assert_eq!(s.replace (4), (1, Some (4)));
730    assert_eq!(s.find_or_insert (4), FindOrInsert::Found (1));
731    assert_eq!(s.find_or_insert (4).index(), 1);
732    assert_eq!(s.len(), 3);
733    assert_eq!(s.binary_search (&3), Ok (0));
734    assert_eq!(**SortedSet::from_unsorted (
735      vec![5, -10, 99, -10, -11, 10, 2, 17, 10]),
736      vec![-11, -10, 2, 5, 10, 17, 99]);
737    assert_eq!(SortedSet::from_unsorted (
738      vec![5, -10, 99, -10, -11, 10, 2, 17, 10]),
739      vec![5, -10, 99, -10, -11, 10, 2, 17, 10].into());
740    let mut s = SortedSet::new();
741    s.extend([5, -11, -10, 99, -11, 2, 17, 2, 10]);
742    assert_eq!(**s, vec![-11, -10, 2, 5, 10, 17, 99]);
743    let () = s.mutate_vec (|s|{
744      s[0] = 5;
745      s[3] = 1;
746    });
747    assert_eq!(
748      s.drain(..).collect::<Vec <i32>>(),
749      vec![-10, 1, 2, 5, 10, 17, 99]);
750  }
751
752  #[test]
753  fn sorted_set_push() {
754    let mut s = SortedSet::new();
755    assert_eq!(s.push (5), (0, None));
756    assert_eq!(s.push (3), (0, None));
757    assert_eq!(s.push (4), (1, None));
758    assert_eq!(s.push (4), (1, Some (4)));
759    assert_eq!(s.find_or_push (4), FindOrInsert::Found (1));
760    assert_eq!(s.find_or_push (4).index(), 1);
761    assert_eq!(s.len(), 3);
762    assert_eq!(s.binary_search (&3), Ok (0));
763    assert_eq!(**SortedSet::from_unsorted (
764      vec![5, -10, 99, -10, -11, 10, 2, 17, 10]),
765      vec![-11, -10, 2, 5, 10, 17, 99]);
766    assert_eq!(SortedSet::from_unsorted (
767      vec![5, -10, 99, -10, -11, 10, 2, 17, 10]),
768      vec![5, -10, 99, -10, -11, 10, 2, 17, 10].into());
769    let mut s = SortedSet::new();
770    s.extend([5, -11, -10, 99, -11, 2, 17, 2, 10]);
771    assert_eq!(**s, vec![-11, -10, 2, 5, 10, 17, 99]);
772    let () = s.mutate_vec (|s|{
773      s[0] = 5;
774      s[3] = 1;
775    });
776    assert_eq!(
777      s.drain(..).collect::<Vec <i32>>(),
778      vec![-10, 1, 2, 5, 10, 17, 99]);
779  }
780
781  #[test]
782  fn reverse_sorted_vec() {
783    let mut v = ReverseSortedVec::new();
784    assert_eq!(v.insert (Reverse(5)), 0);
785    assert_eq!(v.insert (Reverse(3)), 1);
786    assert_eq!(v.insert (Reverse(4)), 1);
787    assert_eq!(v.find_or_insert (Reverse(6)), FindOrInsert::Inserted (0));
788    assert_eq!(v.insert (Reverse(4)), 2);
789    assert_eq!(v.find_or_insert (Reverse(4)), FindOrInsert::Found (3));
790    assert_eq!(v.len(), 5);
791    v.dedup();
792    assert_eq!(v.len(), 4);
793    assert_eq!(*ReverseSortedVec::from_unsorted (
794      Vec::from_iter ([5, -10, 99, -11, 2, 17, 10].map (Reverse))),
795      Vec::from_iter ([99, 17, 10, 5, 2, -10, -11].map (Reverse)));
796    assert_eq!(ReverseSortedVec::from_unsorted (
797      Vec::from_iter ([5, -10, 99, -11, 2, 17, 10].map (Reverse))),
798      Vec::from_iter ([5, -10, 99, -11, 2, 17, 10].map (Reverse)).into());
799    let mut v = ReverseSortedVec::new();
800    v.extend([5, -10, 99, -11, 2, 17, 10].map (Reverse));
801    assert_eq!(v.as_slice(), [99, 17, 10, 5, 2, -10, -11].map (Reverse));
802    let () = v.mutate_vec (|v|{
803      v[6] = Reverse(11);
804      v[3] = Reverse(1);
805    });
806    assert_eq!(
807      v.drain(..).collect::<Vec <Reverse<i32>>>(),
808      Vec::from_iter ([99, 17, 11, 10, 2, 1, -10].map (Reverse)));
809  }
810
811  #[test]
812  fn reverse_sorted_set() {
813    let mut s = ReverseSortedSet::new();
814    assert_eq!(s.replace (Reverse(5)), (0, None));
815    assert_eq!(s.replace (Reverse(3)), (1, None));
816    assert_eq!(s.replace (Reverse(4)), (1, None));
817    assert_eq!(s.find_or_insert (Reverse(6)), FindOrInsert::Inserted (0));
818    assert_eq!(s.replace (Reverse(4)), (2, Some (Reverse(4))));
819    assert_eq!(s.find_or_insert (Reverse(4)), FindOrInsert::Found (2));
820    assert_eq!(s.len(), 4);
821    assert_eq!(s.binary_search (&Reverse(3)), Ok (3));
822    assert_eq!(**ReverseSortedSet::from_unsorted (
823      Vec::from_iter ([5, -10, 99, -11, 2, 99, 17, 10, -10].map (Reverse))),
824      Vec::from_iter ([99, 17, 10, 5, 2, -10, -11].map (Reverse)));
825    assert_eq!(ReverseSortedSet::from_unsorted (
826      Vec::from_iter ([5, -10, 99, -11, 2, 99, 17, 10, -10].map (Reverse))),
827      Vec::from_iter ([5, -10, 99, -11, 2, 99, 17, 10, -10].map (Reverse)).into());
828    let mut s = ReverseSortedSet::new();
829    s.extend([5, -10, 2, 99, -11, -11, 2, 17, 10].map (Reverse));
830    assert_eq!(s.as_slice(), [99, 17, 10, 5, 2, -10, -11].map (Reverse));
831    let () = s.mutate_vec (|s|{
832      s[6] = Reverse(17);
833      s[3] = Reverse(1);
834    });
835    assert_eq!(
836      s.drain(..).collect::<Vec <Reverse<i32>>>(),
837      Vec::from_iter ([99, 17, 10, 2, 1, -10].map (Reverse)));
838    let s = ReverseSortedSet::from_iter (
839      [5, -10, 2, 99, -11, -11, 2, 17, 10].map (Reverse));
840    assert_eq!(**s, [99, 17, 10, 5, 2, -10, -11].map (Reverse));
841  }
842  #[cfg(feature = "serde-nontransparent")]
843  #[test]
844  fn deserialize() {
845    let s = r#"{"vec":[-11,-10,2,5,10,17,99]}"#;
846    let _ = serde_json::from_str::<SortedVec <i32>> (s).unwrap();
847  }
848  #[cfg(all(feature = "serde", not(feature = "serde-nontransparent")))]
849  #[test]
850  fn deserialize() {
851    let s = "[-11,-10,2,5,10,17,99]";
852    let _ = serde_json::from_str::<SortedVec <i32>> (s).unwrap();
853  }
854  #[cfg(feature = "serde-nontransparent")]
855  #[test]
856  #[should_panic]
857  fn deserialize_unsorted() {
858    let s = r#"{"vec":[99,-11,-10,2,5,10,17]}"#;
859    let _ = serde_json::from_str::<SortedVec <i32>> (s).unwrap();
860  }
861  #[cfg(all(feature = "serde", not(feature = "serde-nontransparent")))]
862  #[test]
863  #[should_panic]
864  fn deserialize_unsorted() {
865    let s = "[99,-11,-10,2,5,10,17]";
866    let _ = serde_json::from_str::<SortedVec <i32>> (s).unwrap();
867  }
868  #[cfg(feature = "serde-nontransparent")]
869  #[test]
870  fn deserialize_reverse() {
871    let s = r#"{"vec":[99,17,10,5,2,-10,-11]}"#;
872    let _ = serde_json::from_str::<ReverseSortedVec <i32>> (s).unwrap();
873  }
874  #[cfg(all(feature = "serde", not(feature = "serde-nontransparent")))]
875  #[test]
876  fn deserialize_reverse() {
877    let s = "[99,17,10,5,2,-10,-11]";
878    let _ = serde_json::from_str::<ReverseSortedVec <i32>> (s).unwrap();
879  }
880  #[cfg(feature = "serde-nontransparent")]
881  #[test]
882  #[should_panic]
883  fn deserialize_reverse_unsorted() {
884    let s = r#"{"vec":[99,-11,-10,2,5,10,17]}"#;
885    let _ = serde_json::from_str::<ReverseSortedVec <i32>> (s).unwrap();
886  }
887  #[cfg(all(feature = "serde", not(feature = "serde-nontransparent")))]
888  #[test]
889  #[should_panic]
890  fn deserialize_reverse_unsorted() {
891    let s = "[99,-11,-10,2,5,10,17]";
892    let _ = serde_json::from_str::<ReverseSortedVec <i32>> (s).unwrap();
893  }
894}
sorted_vec/lib.rs

sorted_vec/
lib.rs
