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

sorted_vec2/
lib.rs
