sorted-vec2 0.1.0

//! Sorted vectors.
//!
//! [Repository](https://gitlab.com/spearman/sorted-vec)
//!
//! - `SortedVec` -- sorted from least to greatest, may contain duplicates
//! - `SortedSet` -- sorted from least to greatest, unique elements
//! - `ReverseSortedVec` -- sorted from greatest to least, may contain
//!   duplicates
//! - `ReverseSortedSet` -- sorted from greatest to least, unique elements
//!
//! The `partial` module provides sorted vectors of types that only implement
//! `PartialOrd` where comparison of incomparable elements results in runtime
//! panic.

#[cfg(feature = "serde")]
#[macro_use]
extern crate serde;

#[cfg(feature = "serde")]
extern crate is_sorted;

// At the time of writing, is_sorted() is not available on stable Rust
#[cfg(feature = "serde")]
use is_sorted::IsSorted;

use std::hash::{Hash, Hasher};

pub mod partial;

/// Forward sorted vector
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[cfg_attr(
    all(feature = "serde", not(feature = "serde-nontransparent")),
    serde(transparent)
)]
#[derive(Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
pub struct SortedVec<T: Ord> {
    #[cfg_attr(feature = "serde", serde(deserialize_with = "SortedVec::parse_vec"))]
    #[cfg_attr(
        feature = "serde",
        serde(bound(deserialize = "T : serde::Deserialize <'de>"))
    )]
    vec: Vec<T>,
}

/// Forward sorted set
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[cfg_attr(
    all(feature = "serde", not(feature = "serde-nontransparent")),
    serde(transparent)
)]
#[derive(Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
pub struct SortedSet<T: Ord> {
    #[cfg_attr(feature = "serde", serde(deserialize_with = "SortedSet::parse_vec"))]
    #[cfg_attr(
        feature = "serde",
        serde(bound(deserialize = "T : serde::Deserialize <'de>"))
    )]
    set: SortedVec<T>,
}

/// Value returned when find_or_insert is used.
#[derive(PartialEq, PartialOrd, Eq, Ord, Debug, Hash)]
pub enum FindOrInsert {
    /// Contains a found index
    Found(usize),

    /// Contains an inserted index
    Inserted(usize),
}

/// Converts from the binary_search result type into the FindOrInsert type
impl From<Result<usize, usize>> for FindOrInsert {
    fn from(result: Result<usize, usize>) -> Self {
        match result {
            Result::Ok(value) => FindOrInsert::Found(value),
            Result::Err(value) => FindOrInsert::Inserted(value),
        }
    }
}

impl FindOrInsert {
    /// Get the index of the element that was either found or inserted.
    pub fn index(&self) -> usize {
        match self {
            FindOrInsert::Found(value) | FindOrInsert::Inserted(value) => *value,
        }
    }

    /// If an equivalent element was found in the container, get the value of
    /// its index. Otherwise get None.
    pub fn found(&self) -> Option<usize> {
        match self {
            FindOrInsert::Found(value) => Some(*value),
            FindOrInsert::Inserted(_) => None,
        }
    }

    /// If the provided element was inserted into the container, get the value
    /// of its index. Otherwise get None.
    pub fn inserted(&self) -> Option<usize> {
        match self {
            FindOrInsert::Found(_) => None,
            FindOrInsert::Inserted(value) => Some(*value),
        }
    }

    /// Returns true if the element was found.
    pub fn is_found(&self) -> bool {
        matches!(self, FindOrInsert::Found(_))
    }

    /// Returns true if the element was inserted.
    pub fn is_inserted(&self) -> bool {
        matches!(self, FindOrInsert::Inserted(_))
    }
}

//
//  impl SortedVec
//

impl<T: Ord> SortedVec<T> {
    #[inline]
    pub fn new() -> Self {
        SortedVec { vec: Vec::new() }
    }
    #[inline]
    pub fn with_capacity(capacity: usize) -> Self {
        SortedVec {
            vec: Vec::with_capacity(capacity),
        }
    }
    /// Uses `sort_unstable()` to sort in place.
    #[inline]
    pub fn from_unsorted(mut vec: Vec<T>) -> Self {
        vec.sort_unstable();
        SortedVec { vec }
    }

    /// The caller must ensure that the provided vector is already sorted.
    pub unsafe fn from_unsorted_unchecked(vec: Vec<T>) -> Self {
        SortedVec { vec }
    }

    /// Insert an element into sorted position, returning the order index at which
    /// it was placed.
    pub fn insert(&mut self, element: T) -> usize {
        let insert_at = match self.binary_search(&element) {
            Ok(insert_at) | Err(insert_at) => insert_at,
        };
        self.vec.insert(insert_at, element);
        insert_at
    }
    /// Find the element and return the index with `Ok`, otherwise insert the
    /// element and return the new element index with `Err`.
    pub fn find_or_insert(&mut self, element: T) -> FindOrInsert {
        self.binary_search(&element)
            .map_err(|insert_at| {
                self.vec.insert(insert_at, element);
                insert_at
            })
            .into()
    }
    /// Same as insert, except performance is O(1) when the element belongs at the
    /// back of the container. This avoids an O(log(N)) search for inserting
    /// elements at the back.
    #[inline]
    pub fn push(&mut self, element: T) -> usize {
        if let Some(last) = self.vec.last() {
            let cmp = element.cmp(last);
            if cmp == std::cmp::Ordering::Greater || cmp == std::cmp::Ordering::Equal {
                // The new element is greater than or equal to the current last element,
                // so we can simply push it onto the vec.
                self.vec.push(element);
                return self.vec.len() - 1;
            } else {
                // The new element is less than the last element in the container, so we
                // cannot simply push. We will fall back on the normal insert behavior.
                return self.insert(element);
            }
        } else {
            // If there is no last element then the container must be empty, so we
            // can simply push the element and return its index, which must be 0.
            self.vec.push(element);
            return 0;
        }
    }
    /// Reserves additional capacity in the underlying vector.
    /// See std::vec::Vec::reserve.
    #[inline]
    pub fn reserve(&mut self, additional: usize) {
        self.vec.reserve(additional);
    }
    /// Same as find_or_insert, except performance is O(1) when the element
    /// belongs at the back of the container.
    pub fn find_or_push(&mut self, element: T) -> FindOrInsert {
        if let Some(last) = self.vec.last() {
            let cmp = element.cmp(last);
            if cmp == std::cmp::Ordering::Equal {
                return FindOrInsert::Found(self.vec.len() - 1);
            } else if cmp == std::cmp::Ordering::Greater {
                self.vec.push(element);
                return FindOrInsert::Inserted(self.vec.len() - 1);
            } else {
                // The new element is less than the last element in the container, so we
                // need to fall back on the regular find_or_insert
                return self.find_or_insert(element);
            }
        } else {
            // If there is no last element then the container must be empty, so we can
            // simply push the element and return that it was inserted.
            self.vec.push(element);
            return FindOrInsert::Inserted(0);
        }
    }
    #[inline]
    pub fn remove_item(&mut self, item: &T) -> Option<T> {
        match self.vec.binary_search(item) {
            Ok(remove_at) => Some(self.vec.remove(remove_at)),
            Err(_) => None,
        }
    }
    /// Panics if index is out of bounds
    #[inline]
    pub fn remove_index(&mut self, index: usize) -> T {
        self.vec.remove(index)
    }
    #[inline]
    pub fn pop(&mut self) -> Option<T> {
        self.vec.pop()
    }
    #[inline]
    pub fn clear(&mut self) {
        self.vec.clear()
    }
    #[inline]
    pub fn dedup(&mut self) {
        self.vec.dedup();
    }
    #[inline]
    pub fn dedup_by_key<F, K>(&mut self, key: F)
    where
        F: FnMut(&mut T) -> K,
        K: PartialEq<K>,
    {
        self.vec.dedup_by_key(key);
    }
    #[inline]
    pub fn drain<R>(&mut self, range: R) -> std::vec::Drain<T>
    where
        R: std::ops::RangeBounds<usize>,
    {
        self.vec.drain(range)
    }
    #[inline]
    pub fn retain<F>(&mut self, f: F)
    where
        F: FnMut(&T) -> bool,
    {
        self.vec.retain(f)
    }
    /// NOTE: to_vec() is a slice method that is accessible through deref, use
    /// this instead to avoid cloning
    #[inline]
    pub fn into_vec(self) -> Vec<T> {
        self.vec
    }
    /// Apply a closure mutating the sorted vector and use `sort_unstable()`
    /// to re-sort the mutated vector
    pub fn mutate_vec<F, O>(&mut self, f: F) -> O
    where
        F: FnOnce(&mut Vec<T>) -> O,
    {
        let res = f(&mut self.vec);
        self.vec.sort_unstable();
        res
    }
    /// Unsafe access to the underlying vector. The caller must ensure that any
    /// changes to the values in the vector do not impact the ordering of the
    /// elements inside, or else this container will misbehave.
    pub unsafe fn get_unchecked_mut_vec(&mut self) -> &mut Vec<T> {
        return &mut self.vec;
    }

    /// Perform sorting on the input sequence when deserializing with `serde`.
    ///
    /// Use with `#[serde(deserialize_with = "SortedVec::deserialize_unsorted")]`:
    /// ```text
    /// #[derive(Debug, Eq, Ord, PartialEq, PartialOrd, Deserialize, Serialize)]
    /// pub struct Foo {
    ///   #[serde(deserialize_with = "SortedVec::deserialize_unsorted")]
    ///   pub v : SortedVec <u64>
    /// }
    /// ```
    #[cfg(feature = "serde")]
    pub fn deserialize_unsorted<'de, D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: serde::Deserializer<'de>,
        T: serde::Deserialize<'de>,
    {
        use serde::Deserialize;
        let v = Vec::deserialize(deserializer)?;
        Ok(SortedVec::from_unsorted(v))
    }

    #[cfg(feature = "serde")]
    fn parse_vec<'de, D>(deserializer: D) -> Result<Vec<T>, D::Error>
    where
        D: serde::Deserializer<'de>,
        T: serde::Deserialize<'de>,
    {
        use serde::de::Error;
        use serde::Deserialize;
        let v = Vec::deserialize(deserializer)?;
        let is_sorted = {
            let mut iter = v.iter();
            IsSorted::is_sorted(&mut iter)
        };
        if !is_sorted {
            Err(D::Error::custom("input sequence is not sorted"))
        } else {
            Ok(v)
        }
    }
}
impl<T: Ord> Default for SortedVec<T> {
    fn default() -> Self {
        Self::new()
    }
}
impl<T: Ord> From<Vec<T>> for SortedVec<T> {
    fn from(unsorted: Vec<T>) -> Self {
        Self::from_unsorted(unsorted)
    }
}
impl<T: Ord> std::ops::Deref for SortedVec<T> {
    type Target = Vec<T>;
    fn deref(&self) -> &Vec<T> {
        &self.vec
    }
}
impl<T: Ord> Extend<T> for SortedVec<T> {
    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        for t in iter {
            let _ = self.insert(t);
        }
    }
}
impl<T: Ord + Hash> Hash for SortedVec<T> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        let v: &Vec<T> = self.as_ref();
        v.hash(state);
    }
}

//
//  impl SortedSet
//

impl<T: Ord> SortedSet<T> {
    #[inline]
    pub fn new() -> Self {
        SortedSet {
            set: SortedVec::new(),
        }
    }
    #[inline]
    pub fn with_capacity(capacity: usize) -> Self {
        SortedSet {
            set: SortedVec::with_capacity(capacity),
        }
    }
    /// Uses `sort_unstable()` to sort in place and `dedup()` to remove
    /// duplicates.
    #[inline]
    pub fn from_unsorted(vec: Vec<T>) -> Self {
        let mut set = SortedVec::from_unsorted(vec);
        set.dedup();
        SortedSet { set }
    }
    /// Insert an element into sorted position, returning the order index at which
    /// it was placed. If an existing item was found it will be returned.
    #[inline]
    pub fn replace(&mut self, mut element: T) -> (usize, Option<T>) {
        match self.set.binary_search(&element) {
            Ok(existing_index) => {
                unsafe {
                    // If binary_search worked correctly, then this must be the index of a
                    // valid element to get from the vector.
                    std::mem::swap(&mut element, self.set.vec.get_unchecked_mut(existing_index))
                }
                (existing_index, Some(element))
            }
            Err(insert_index) => {
                self.set.vec.insert(insert_index, element);
                (insert_index, None)
            }
        }
    }
    /// Find the element and return the index with `Ok`, otherwise insert the
    /// element and return the new element index with `Err`.
    #[inline]
    pub fn find_or_insert(&mut self, element: T) -> FindOrInsert {
        self.set.find_or_insert(element)
    }
    /// Same as replace, except performance is O(1) when the element belongs at
    /// the back of the container. This avoids an O(log(N)) search for inserting
    /// elements at the back.
    #[inline]
    pub fn push(&mut self, element: T) -> (usize, Option<T>) {
        if let Some(last) = self.vec.last() {
            let cmp = element.cmp(last);
            if cmp == std::cmp::Ordering::Greater {
                // The new element is greater than the current last element, so we can
                // simply push it onto the vec.
                self.set.vec.push(element);
                return (self.vec.len() - 1, None);
            } else if cmp == std::cmp::Ordering::Equal {
                // The new element is equal to the last element, so we can simply return
                // the last index in the vec and the value that is being replaced.
                let original = self.set.vec.pop();
                self.set.vec.push(element);
                return (self.vec.len() - 1, original);
            } else {
                // The new element is less than the last element, so we need to fall
                // back on the regular insert function.
                return self.replace(element);
            }
        } else {
            // If there is no last element then the container must be empty, so we can
            // simply push the element and return its index, which must be 0.
            self.set.vec.push(element);
            return (0, None);
        }
    }
    /// Reserves additional capacity in the underlying vector.
    /// See std::vec::Vec::reserve.
    #[inline]
    pub fn reserve(&mut self, additional: usize) {
        self.set.reserve(additional);
    }
    /// Same as find_or_insert, except performance is O(1) when the element
    /// belongs at the back of the container.
    pub fn find_or_push(&mut self, element: T) -> FindOrInsert {
        self.set.find_or_insert(element)
    }
    #[inline]
    pub fn remove_item(&mut self, item: &T) -> Option<T> {
        self.set.remove_item(item)
    }
    /// Panics if index is out of bounds
    #[inline]
    pub fn remove_index(&mut self, index: usize) -> T {
        self.set.remove_index(index)
    }
    #[inline]
    pub fn pop(&mut self) -> Option<T> {
        self.set.pop()
    }
    #[inline]
    pub fn clear(&mut self) {
        self.set.clear()
    }
    #[inline]
    pub fn drain<R>(&mut self, range: R) -> std::vec::Drain<T>
    where
        R: std::ops::RangeBounds<usize>,
    {
        self.set.drain(range)
    }
    #[inline]
    pub fn retain<F>(&mut self, f: F)
    where
        F: FnMut(&T) -> bool,
    {
        self.set.retain(f)
    }
    /// NOTE: to_vec() is a slice method that is accessible through deref, use
    /// this instead to avoid cloning
    #[inline]
    pub fn into_vec(self) -> Vec<T> {
        self.set.into_vec()
    }
    /// Apply a closure mutating the sorted vector and use `sort_unstable()`
    /// to re-sort the mutated vector and `dedup()` to remove any duplicate
    /// values
    pub fn mutate_vec<F, O>(&mut self, f: F) -> O
    where
        F: FnOnce(&mut Vec<T>) -> O,
    {
        let res = self.set.mutate_vec(f);
        self.set.dedup();
        res
    }
    /// Unsafe access to the underlying vector. The caller must ensure that any
    /// changes to the values in the vector do not impact the ordering of the
    /// elements inside, or else this container will misbehave.
    pub unsafe fn get_unchecked_mut_vec(&mut self) -> &mut Vec<T> {
        return self.set.get_unchecked_mut_vec();
    }

    /// Perform deduplication and sorting on the input sequence when deserializing
    /// with `serde`.
    ///
    /// Use with
    /// `#[serde(deserialize_with = "SortedSet::deserialize_dedup_unsorted")]`:
    /// ```text
    /// #[derive(Debug, Eq, Ord, PartialEq, PartialOrd, Deserialize, Serialize)]
    /// pub struct Foo {
    ///   #[serde(deserialize_with = "SortedSet::deserialize_dedup_unsorted")]
    ///   pub s : SortedSet <u64>
    /// }
    /// ```
    #[cfg(feature = "serde")]
    pub fn deserialize_dedup_unsorted<'de, D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: serde::Deserializer<'de>,
        T: serde::Deserialize<'de>,
    {
        use serde::Deserialize;
        let v = Vec::deserialize(deserializer)?;
        Ok(SortedSet::from_unsorted(v))
    }

    #[cfg(feature = "serde")]
    fn parse_vec<'de, D>(deserializer: D) -> Result<SortedVec<T>, D::Error>
    where
        D: serde::Deserializer<'de>,
        T: serde::Deserialize<'de>,
    {
        use serde::de::Error;
        use serde::Deserialize;
        let mut vec = Vec::deserialize(deserializer)?;
        let input_len = vec.len();
        vec.dedup();
        if vec.len() != input_len {
            return Err(D::Error::custom("input set contains duplicate values"));
        };
        let is_sorted = {
            let mut iter = vec.iter();
            IsSorted::is_sorted(&mut iter)
        };
        if !is_sorted {
            Err(D::Error::custom("input set is not sorted"))
        } else {
            Ok(SortedVec { vec })
        }
    }
}
impl<T: Ord> Default for SortedSet<T> {
    fn default() -> Self {
        Self::new()
    }
}
impl<T: Ord> From<Vec<T>> for SortedSet<T> {
    fn from(unsorted: Vec<T>) -> Self {
        Self::from_unsorted(unsorted)
    }
}
impl<T: Ord> std::ops::Deref for SortedSet<T> {
    type Target = SortedVec<T>;
    fn deref(&self) -> &SortedVec<T> {
        &self.set
    }
}
impl<T: Ord> Extend<T> for SortedSet<T> {
    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        for t in iter {
            let _ = self.find_or_insert(t);
        }
    }
}
impl<T: Ord + Hash> Hash for SortedSet<T> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        let v: &Vec<T> = self.as_ref();
        v.hash(state);
    }
}

/// Reverse-sorted Containers.
///
/// Use these containers to have the vector sorted in the reverse order of its
/// usual comparison.
///
/// Note that objects going into the reverse container needs to be wrapped in
/// std::cmp::Reverse.
///
/// # Examples
///
/// ```
/// use std::cmp::Reverse;
/// use sorted_vec::ReverseSortedVec;
///
/// let mut vec = ReverseSortedVec::<u64>::new();
/// vec.insert(Reverse(10));
/// vec.insert(Reverse(15));
/// assert_eq!(vec.last().unwrap().0, 10);
/// ```
pub type ReverseSortedVec<T> = SortedVec<std::cmp::Reverse<T>>;
pub type ReverseSortedSet<T> = SortedSet<std::cmp::Reverse<T>>;

#[cfg(test)]
mod tests {
    use super::*;
    use std::cmp::Reverse;

    #[test]
    fn test_sorted_vec() {
        let mut v = SortedVec::new();
        assert_eq!(v.insert(5), 0);
        assert_eq!(v.insert(3), 0);
        assert_eq!(v.insert(4), 1);
        assert_eq!(v.insert(4), 1);
        assert_eq!(v.find_or_insert(4), FindOrInsert::Found(2));
        assert_eq!(v.find_or_insert(4).index(), 2);
        assert_eq!(v.len(), 4);
        v.dedup();
        assert_eq!(v.len(), 3);
        assert_eq!(v.binary_search(&3), Ok(0));
        assert_eq!(
            *SortedVec::from_unsorted(vec![5, -10, 99, -11, 2, 17, 10]),
            vec![-11, -10, 2, 5, 10, 17, 99]
        );
        assert_eq!(
            SortedVec::from_unsorted(vec![5, -10, 99, -11, 2, 17, 10]),
            vec![5, -10, 99, -11, 2, 17, 10].into()
        );
        let mut v = SortedVec::new();
        v.extend(vec![5, -10, 99, -11, 2, 17, 10].into_iter());
        assert_eq!(*v, vec![-11, -10, 2, 5, 10, 17, 99]);
        let _ = v.mutate_vec(|v| {
            v[0] = 11;
            v[3] = 1;
        });
        assert_eq!(
            v.drain(..).collect::<Vec<i32>>(),
            vec![-10, 1, 2, 10, 11, 17, 99]
        );
    }

    #[test]
    fn test_sorted_vec_push() {
        let mut v = SortedVec::new();
        assert_eq!(v.push(5), 0);
        assert_eq!(v.push(3), 0);
        assert_eq!(v.push(4), 1);
        assert_eq!(v.push(4), 1);
        assert_eq!(v.find_or_push(4), FindOrInsert::Found(2));
        assert_eq!(v.find_or_push(4).index(), 2);
        assert_eq!(v.len(), 4);
        v.dedup();
        assert_eq!(v.len(), 3);
        assert_eq!(v.binary_search(&3), Ok(0));
        assert_eq!(
            *SortedVec::from_unsorted(vec![5, -10, 99, -11, 2, 17, 10]),
            vec![-11, -10, 2, 5, 10, 17, 99]
        );
        assert_eq!(
            SortedVec::from_unsorted(vec![5, -10, 99, -11, 2, 17, 10]),
            vec![5, -10, 99, -11, 2, 17, 10].into()
        );
        let mut v = SortedVec::new();
        v.extend(vec![5, -10, 99, -11, 2, 17, 10].into_iter());
        assert_eq!(*v, vec![-11, -10, 2, 5, 10, 17, 99]);
        let _ = v.mutate_vec(|v| {
            v[0] = 11;
            v[3] = 1;
        });
        assert_eq!(
            v.drain(..).collect::<Vec<i32>>(),
            vec![-10, 1, 2, 10, 11, 17, 99]
        );
    }

    #[test]
    fn test_sorted_set() {
        let mut s = SortedSet::new();
        assert_eq!(s.replace(5), (0, None));
        assert_eq!(s.replace(3), (0, None));
        assert_eq!(s.replace(4), (1, None));
        assert_eq!(s.replace(4), (1, Some(4)));
        assert_eq!(s.find_or_insert(4), FindOrInsert::Found(1));
        assert_eq!(s.find_or_insert(4).index(), 1);
        assert_eq!(s.len(), 3);
        assert_eq!(s.binary_search(&3), Ok(0));
        assert_eq!(
            **SortedSet::from_unsorted(vec![5, -10, 99, -10, -11, 10, 2, 17, 10]),
            vec![-11, -10, 2, 5, 10, 17, 99]
        );
        assert_eq!(
            SortedSet::from_unsorted(vec![5, -10, 99, -10, -11, 10, 2, 17, 10]),
            vec![5, -10, 99, -10, -11, 10, 2, 17, 10].into()
        );
        let mut s = SortedSet::new();
        s.extend(vec![5, -11, -10, 99, -11, 2, 17, 2, 10].into_iter());
        assert_eq!(**s, vec![-11, -10, 2, 5, 10, 17, 99]);
        let _ = s.mutate_vec(|s| {
            s[0] = 5;
            s[3] = 1;
        });
        assert_eq!(
            s.drain(..).collect::<Vec<i32>>(),
            vec![-10, 1, 2, 5, 10, 17, 99]
        );
    }

    #[test]
    fn test_sorted_set_push() {
        let mut s = SortedSet::new();
        assert_eq!(s.push(5), (0, None));
        assert_eq!(s.push(3), (0, None));
        assert_eq!(s.push(4), (1, None));
        assert_eq!(s.push(4), (1, Some(4)));
        assert_eq!(s.find_or_push(4), FindOrInsert::Found(1));
        assert_eq!(s.find_or_push(4).index(), 1);
        assert_eq!(s.len(), 3);
        assert_eq!(s.binary_search(&3), Ok(0));
        assert_eq!(
            **SortedSet::from_unsorted(vec![5, -10, 99, -10, -11, 10, 2, 17, 10]),
            vec![-11, -10, 2, 5, 10, 17, 99]
        );
        assert_eq!(
            SortedSet::from_unsorted(vec![5, -10, 99, -10, -11, 10, 2, 17, 10]),
            vec![5, -10, 99, -10, -11, 10, 2, 17, 10].into()
        );
        let mut s = SortedSet::new();
        s.extend(vec![5, -11, -10, 99, -11, 2, 17, 2, 10].into_iter());
        assert_eq!(**s, vec![-11, -10, 2, 5, 10, 17, 99]);
        let _ = s.mutate_vec(|s| {
            s[0] = 5;
            s[3] = 1;
        });
        assert_eq!(
            s.drain(..).collect::<Vec<i32>>(),
            vec![-10, 1, 2, 5, 10, 17, 99]
        );
    }

    #[test]
    fn test_reverse_sorted_vec() {
        let mut v = ReverseSortedVec::new();
        assert_eq!(v.insert(Reverse(5)), 0);
        assert_eq!(v.insert(Reverse(3)), 1);
        assert_eq!(v.insert(Reverse(4)), 1);
        assert_eq!(v.find_or_insert(Reverse(6)), FindOrInsert::Inserted(0));
        assert_eq!(v.insert(Reverse(4)), 2);
        assert_eq!(v.find_or_insert(Reverse(4)), FindOrInsert::Found(2));
        assert_eq!(v.len(), 5);
        v.dedup();
        assert_eq!(v.len(), 4);
        assert_eq!(
            *ReverseSortedVec::from_unsorted(Vec::from_iter(
                [5, -10, 99, -11, 2, 17, 10].map(Reverse)
            )),
            Vec::from_iter([99, 17, 10, 5, 2, -10, -11].map(Reverse))
        );
        assert_eq!(
            ReverseSortedVec::from_unsorted(Vec::from_iter(
                [5, -10, 99, -11, 2, 17, 10].map(Reverse)
            )),
            Vec::from_iter([5, -10, 99, -11, 2, 17, 10].map(Reverse)).into()
        );
        let mut v = ReverseSortedVec::new();
        v.extend([5, -10, 99, -11, 2, 17, 10].map(Reverse));
        assert_eq!(v.as_slice(), [99, 17, 10, 5, 2, -10, -11].map(Reverse));
        let _ = v.mutate_vec(|v| {
            v[6] = Reverse(11);
            v[3] = Reverse(1);
        });
        assert_eq!(
            v.drain(..).collect::<Vec<Reverse<i32>>>(),
            Vec::from_iter([99, 17, 11, 10, 2, 1, -10].map(Reverse))
        );
    }

    #[test]
    fn test_reverse_sorted_set() {
        let mut s = ReverseSortedSet::new();
        assert_eq!(s.replace(Reverse(5)), (0, None));
        assert_eq!(s.replace(Reverse(3)), (1, None));
        assert_eq!(s.replace(Reverse(4)), (1, None));
        assert_eq!(s.find_or_insert(Reverse(6)), FindOrInsert::Inserted(0));
        assert_eq!(s.replace(Reverse(4)), (2, Some(Reverse(4))));
        assert_eq!(s.find_or_insert(Reverse(4)), FindOrInsert::Found(2));
        assert_eq!(s.len(), 4);
        assert_eq!(s.binary_search(&Reverse(3)), Ok(3));
        assert_eq!(
            **ReverseSortedSet::from_unsorted(Vec::from_iter(
                [5, -10, 99, -11, 2, 99, 17, 10, -10].map(Reverse)
            )),
            Vec::from_iter([99, 17, 10, 5, 2, -10, -11].map(Reverse))
        );
        assert_eq!(
            ReverseSortedSet::from_unsorted(Vec::from_iter(
                [5, -10, 99, -11, 2, 99, 17, 10, -10].map(Reverse)
            )),
            Vec::from_iter([5, -10, 99, -11, 2, 99, 17, 10, -10].map(Reverse)).into()
        );
        let mut s = ReverseSortedSet::new();
        s.extend([5, -10, 2, 99, -11, -11, 2, 17, 10].map(Reverse));
        assert_eq!(s.as_slice(), [99, 17, 10, 5, 2, -10, -11].map(Reverse));
        let _ = s.mutate_vec(|s| {
            s[6] = Reverse(17);
            s[3] = Reverse(1);
        });
        assert_eq!(
            s.drain(..).collect::<Vec<Reverse<i32>>>(),
            Vec::from_iter([99, 17, 10, 2, 1, -10].map(Reverse))
        );
    }
    #[cfg(feature = "serde-nontransparent")]
    #[test]
    fn test_deserialize() {
        let s = r#"{"vec":[-11,-10,2,5,10,17,99]}"#;
        let _ = serde_json::from_str::<SortedVec<i32>>(s).unwrap();
    }
    #[cfg(all(feature = "serde", not(feature = "serde-nontransparent")))]
    #[test]
    fn test_deserialize() {
        let s = "[-11,-10,2,5,10,17,99]";
        let _ = serde_json::from_str::<SortedVec<i32>>(s).unwrap();
    }
    #[cfg(feature = "serde-nontransparent")]
    #[test]
    #[should_panic]
    fn test_deserialize_unsorted() {
        let s = r#"{"vec":[99,-11,-10,2,5,10,17]}"#;
        let _ = serde_json::from_str::<SortedVec<i32>>(s).unwrap();
    }
    #[cfg(all(feature = "serde", not(feature = "serde-nontransparent")))]
    #[test]
    #[should_panic]
    fn test_deserialize_unsorted() {
        let s = "[99,-11,-10,2,5,10,17]";
        let _ = serde_json::from_str::<SortedVec<i32>>(s).unwrap();
    }
    #[cfg(feature = "serde-nontransparent")]
    #[test]
    fn test_deserialize_reverse() {
        let s = r#"{"vec":[99,17,10,5,2,-10,-11]}"#;
        let _ = serde_json::from_str::<ReverseSortedVec<i32>>(s).unwrap();
    }
    #[cfg(all(feature = "serde", not(feature = "serde-nontransparent")))]
    #[test]
    fn test_deserialize_reverse() {
        let s = "[99,17,10,5,2,-10,-11]";
        let _ = serde_json::from_str::<ReverseSortedVec<i32>>(s).unwrap();
    }
    #[cfg(feature = "serde-nontransparent")]
    #[test]
    #[should_panic]
    fn test_deserialize_reverse_unsorted() {
        let s = r#"{vec:[99,-11,-10,2,5,10,17]}"#;
        let _ = serde_json::from_str::<ReverseSortedVec<i32>>(s).unwrap();
    }
    #[cfg(all(feature = "serde", not(feature = "serde-nontransparent")))]
    #[test]
    #[should_panic]
    fn test_deserialize_reverse_unsorted() {
        let s = "[99,-11,-10,2,5,10,17]";
        let _ = serde_json::from_str::<ReverseSortedVec<i32>>(s).unwrap();
    }
}