#![cfg_attr(feature = "serde", feature(is_sorted))]
#[cfg(feature = "serde")]
#[macro_use] extern crate serde;
use std::hash::{Hash, Hasher};
pub mod partial;
#[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>
}
#[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>
}
#[derive(PartialEq, PartialOrd, Eq, Ord, Debug, Hash)]
pub enum FindOrInsert {
Found(usize),
Inserted(usize),
}
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 {
pub fn index(&self) -> usize {
match self {
FindOrInsert::Found(value) | FindOrInsert::Inserted(value) => *value
}
}
pub fn found(&self) -> Option<usize> {
match self {
FindOrInsert::Found(value) => Some(*value),
FindOrInsert::Inserted(_) => None
}
}
pub fn inserted(&self) -> Option<usize> {
match self {
FindOrInsert::Found(_) => None,
FindOrInsert::Inserted(value) => Some(*value)
}
}
pub fn is_found(&self) -> bool {
matches!(self, FindOrInsert::Found(_))
}
pub fn is_inserted(&self) -> bool {
matches!(self, FindOrInsert::Inserted(_))
}
}
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) }
}
#[inline]
pub fn from_unsorted (mut vec : Vec <T>) -> Self {
vec.sort_unstable();
SortedVec { vec }
}
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
}
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()
}
#[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 {
self.vec.push(element);
return self.vec.len() - 1;
} else {
return self.insert(element);
}
} else {
self.vec.push(element);
return 0;
}
}
#[inline]
pub fn reserve(&mut self, additional: usize) {
self.vec.reserve(additional);
}
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 {
return self.find_or_insert(element);
}
} else {
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
}
}
#[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)
}
#[inline]
pub fn into_vec (self) -> Vec <T> {
self.vec
}
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
}
#[inline]
pub unsafe fn from_sorted(vec: Vec<T>) -> Self {
SortedVec { vec }
}
pub unsafe fn get_unchecked_mut_vec(&mut self) -> &mut Vec<T> {
return &mut self.vec;
}
#[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::Deserialize;
use serde::de::Error;
let v = Vec::deserialize (deserializer)?;
if !v.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 <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) }
}
#[inline]
pub fn from_unsorted (vec : Vec <T>) -> Self {
let mut set = SortedVec::from_unsorted (vec);
set.dedup();
SortedSet { set }
}
#[inline]
pub fn replace (&mut self, mut element : T) -> (usize, Option <T>) {
match self.set.binary_search(&element) {
Ok (existing_index) => {
unsafe {
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)
}
}
}
#[inline]
pub fn find_or_insert (&mut self, element : T) -> FindOrInsert {
self.set.find_or_insert (element)
}
#[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 {
self.set.vec.push(element);
return (self.vec.len() - 1, None);
} else if cmp == std::cmp::Ordering::Equal {
let original = self.set.vec.pop();
self.set.vec.push(element);
return (self.vec.len() - 1, original);
} else {
return self.replace(element);
}
} else {
self.set.vec.push(element);
return (0, None);
}
}
#[inline]
pub fn reserve(&mut self, additional: usize) {
self.set.reserve(additional);
}
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)
}
#[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)
}
#[inline]
pub fn into_vec (self) -> Vec <T> {
self.set.into_vec()
}
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
}
#[inline]
pub unsafe fn from_sorted(vec: Vec<T>) -> Self {
let set = unsafe { SortedVec::from_sorted(vec) };
SortedSet { set }
}
pub unsafe fn get_unchecked_mut_vec(&mut self) -> &mut Vec<T> {
return self.set.get_unchecked_mut_vec();
}
#[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::Deserialize;
use serde::de::Error;
let mut vec = Vec::deserialize (deserializer)?;
let input_len = vec.len();
vec.dedup();
if vec.len() != input_len {
Err (D::Error::custom ("input set contains duplicate values"))
} else if !vec.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);
}
}
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();
}
}