//! Defines a [`Collate`] trait to standardize collation methods across data types. The provided //! [`Collator`] struct can be used to collate a collection of items of type `T` where `T: Ord`. //! //! [`Collate`] is useful for implementing a B-Tree, or to handle cases where a collator type is //! more efficient than calling `Ord::cmp` repeatedly, for example when collating localized strings //! using `rust_icu_ucol`. It's also useful to handle types like complex numbers which do not //! necessarily have a natural ordering. //! //! Use the "stream" feature flag to enable `diff` and `try_diff` functions to compute the //! difference between two collated `Stream`s, and the `merge` and `try_merge` functions //! to merge two collated `Stream`s. use std::cmp::Ordering; use std::marker::PhantomData; use std::ops::{ Bound, Range, RangeBounds, RangeFrom, RangeFull, RangeInclusive, RangeTo, RangeToInclusive, }; #[cfg(feature = "stream")] pub use stream::*; #[cfg(feature = "stream")] mod stream; /// A collator for type `Value`. pub trait Collate: Sized + Eq { type Value; /// Return the collation of the `left` value relative to the `right` value. fn cmp(&self, left: &Self::Value, right: &Self::Value) -> Ordering; } pub trait CollateRef: Collate { /// Return the collation of the `left` reference relative to the `right` reference. fn cmp_ref(&self, left: &T, right: &T) -> Ordering; } impl CollateRef for C { fn cmp_ref(&self, left: &C::Value, right: &C::Value) -> Ordering { Collate::cmp(self, left, right) } } /// A generic collator for any type `T: Ord`. pub struct Collator { phantom: PhantomData, } impl Default for Collator { fn default() -> Self { Self { phantom: PhantomData, } } } impl Clone for Collator { fn clone(&self) -> Self { Self { phantom: PhantomData, } } } impl Copy for Collator {} impl PartialEq for Collator { fn eq(&self, _other: &Self) -> bool { // this collator has no configuration state, and therefore must be identical // to any other collator of the same type true } } impl Eq for Collator {} impl Collate for Collator { type Value = T; fn cmp(&self, left: &Self::Value, right: &Self::Value) -> Ordering { left.cmp(right) } } /// An [`Overlap`] is the result of a comparison between two ranges, /// the equivalent of [`Ordering`] for hierarchical data. #[derive(Debug, Eq, PartialEq, Copy, Clone, PartialOrd)] pub enum Overlap { /// A lack of overlap where the compared range is entirely less than another Less, /// A lack of overlap where the compared range is entirely greater than another Greater, /// An overlap where the compared range is identical to another Equal, /// An overlap where the compared range is narrower than another Narrow, /// An overlap where the compared range is wider than another on both sides Wide, /// An overlap where the compared range is wider than another with a lesser start and end point WideLess, /// An overlap where the compared range is wider than another with a greater start and end point WideGreater, } impl Overlap { /// Return the narrowest [`Overlap`] which contains both `self` and `other`. /// Examples: /// ``` /// use collate::Overlap; /// assert_eq!(Overlap::Narrow.then(Overlap::Less), Overlap::WideLess); /// assert_eq!(Overlap::WideLess.then(Overlap::WideGreater), Overlap::Wide); /// assert_eq!(Overlap::Less.then(Overlap::Greater), Overlap::Wide); /// assert_eq!(Overlap::Less.then(Overlap::Less), Overlap::Less); /// ``` pub fn then(self, other: Self) -> Self { match self { Self::Wide => Self::Wide, Self::Narrow => match other { Self::Less | Self::WideLess => Self::WideLess, Self::Narrow | Self::Equal => self, Self::Wide => Self::Wide, Self::Greater | Self::WideGreater => Self::WideGreater, }, Self::Equal => match other { Self::Less | Self::WideLess => Self::WideLess, Self::Equal | Self::Narrow | Self::Wide => other, Self::Greater | Self::WideGreater => Self::WideGreater, }, Self::Less | Self::WideLess => match other { Self::Less => self, Self::WideLess | Self::Narrow | Self::Equal => Self::WideLess, Self::Wide | Self::WideGreater | Self::Greater => Self::Wide, }, Self::Greater | Self::WideGreater => match other { Self::Greater => self, Self::WideGreater | Self::Narrow | Self::Equal => Self::WideGreater, Self::Wide | Self::WideLess | Self::Less => Self::Wide, }, } } } impl From for Overlap { fn from(order: Ordering) -> Self { match order { Ordering::Less => Self::Less, Ordering::Equal => Self::Equal, Ordering::Greater => Self::Greater, } } } /// Range-range comparison methods pub trait OverlapsRange { /// Check whether `other` lies entirely within `self` according to the given `collator`. #[inline] fn contains(&self, other: &T, collator: &C) -> bool { match self.overlaps(other, collator) { Overlap::Wide | Overlap::Equal => true, _ => false, } } /// Check whether `other` lies partially within `self` according to the given `collator`. #[inline] fn contains_partial(&self, other: &T, collator: &C) -> bool { match self.overlaps(other, collator) { Overlap::Narrow | Overlap::Equal => true, Overlap::WideLess | Overlap::Wide | Overlap::WideGreater => true, _ => false, } } /// Check whether `self` overlaps `other` according to the given `collator`. /// /// Examples: /// ``` /// use collate::{Collate, Collator, Overlap, OverlapsRange}; /// let collator = Collator::default(); /// assert_eq!((..1).overlaps(&(2..5), &collator), Overlap::Less); /// assert_eq!((0..1).overlaps(&(0..1), &collator), Overlap::Equal); /// assert_eq!((1..4).overlaps(&(4..5), &collator), Overlap::Less); /// assert_eq!((4..5).overlaps(&(1..4), &collator), Overlap::Greater); /// assert_eq!((3..5).overlaps(&(1..7), &collator), Overlap::Narrow); /// assert_eq!((1..).overlaps(&(3..5), &collator), Overlap::Wide); /// assert_eq!((1..4).overlaps(&(3..), &collator), Overlap::WideLess); /// assert_eq!((3..5).overlaps(&(..4), &collator), Overlap::WideGreater); /// ``` fn overlaps(&self, other: &T, collator: &C) -> Overlap; } type BorrowBounds<'a, V> = (&'a Bound, &'a Bound); impl<'a, T, C> OverlapsRange, C> for BorrowBounds<'a, T> where C: CollateRef, { fn overlaps(&self, other: &BorrowBounds<'a, T>, collator: &C) -> Overlap { let start = cmp_bound( collator, self.0.as_ref(), other.0.as_ref(), Ordering::Greater, Ordering::Less, ); let end = cmp_bound( collator, self.1.as_ref(), other.1.as_ref(), Ordering::Less, Ordering::Greater, ); match (start, end) { (Ordering::Equal, Ordering::Equal) => Overlap::Equal, (Ordering::Greater, Ordering::Less) => Overlap::Narrow, (Ordering::Greater, Ordering::Equal) => Overlap::Narrow, (Ordering::Equal, Ordering::Less) => Overlap::Narrow, (Ordering::Less, Ordering::Greater) => Overlap::Wide, (Ordering::Less, Ordering::Equal) => Overlap::WideLess, (Ordering::Equal, Ordering::Greater) => Overlap::WideGreater, (Ordering::Less, _) => { match cmp_bound( collator, self.1.as_ref(), other.0.as_ref(), Ordering::Less, Ordering::Less, ) { Ordering::Less => Overlap::Less, Ordering::Greater | Ordering::Equal => Overlap::WideLess, } } (_, Ordering::Greater) => { match cmp_bound( collator, self.0.as_ref(), other.1.as_ref(), Ordering::Greater, Ordering::Greater, ) { Ordering::Less | Ordering::Equal => Overlap::WideGreater, Ordering::Greater => Overlap::Greater, } } } } } macro_rules! overlaps_range { ($l:ty, $r:ty) => { impl OverlapsRange<$r, C> for $l { fn overlaps(&self, other: &$r, collator: &C) -> Overlap { overlaps(collator, self, other) } } }; } overlaps_range!(Range, (Bound, Bound)); overlaps_range!(Range, Range); overlaps_range!(Range, RangeFull); overlaps_range!(Range, RangeFrom); overlaps_range!(Range, RangeInclusive); overlaps_range!(Range, RangeTo); overlaps_range!(Range, RangeToInclusive); overlaps_range!(RangeFull, (Bound, Bound)); overlaps_range!(RangeFull, Range); overlaps_range!(RangeFull, RangeFull); overlaps_range!(RangeFull, RangeFrom); overlaps_range!(RangeFull, RangeInclusive); overlaps_range!(RangeFull, RangeTo); overlaps_range!(RangeFull, RangeToInclusive); overlaps_range!(RangeFrom, (Bound, Bound)); overlaps_range!(RangeFrom, Range); overlaps_range!(RangeFrom, RangeFull); overlaps_range!(RangeFrom, RangeFrom); overlaps_range!(RangeFrom, RangeInclusive); overlaps_range!(RangeFrom, RangeTo); overlaps_range!(RangeFrom, RangeToInclusive); overlaps_range!(RangeTo, (Bound, Bound)); overlaps_range!(RangeTo, Range); overlaps_range!(RangeTo, RangeFull); overlaps_range!(RangeTo, RangeFrom); overlaps_range!(RangeTo, RangeInclusive); overlaps_range!(RangeTo, RangeTo); overlaps_range!(RangeTo, RangeToInclusive); overlaps_range!( (Bound, Bound), (Bound, Bound) ); overlaps_range!((Bound, Bound), Range); overlaps_range!((Bound, Bound), RangeFull); overlaps_range!((Bound, Bound), RangeFrom); overlaps_range!((Bound, Bound), RangeInclusive); overlaps_range!((Bound, Bound), RangeTo); overlaps_range!( (Bound, Bound), RangeToInclusive ); /// Range-value comparison methods pub trait OverlapsValue { /// Return `true` if this range contains `value` according to `collator`. fn contains_value(&self, value: &T, collator: &C) -> bool { match self.overlaps_value(value, collator) { Overlap::Less | Overlap::Greater => false, _ => true, } } /// Return `true` if this range overlaps `value` according to `collator`. fn overlaps_value(&self, value: &T, collator: &C) -> Overlap; } macro_rules! overlaps_value { ($t:ty) => { impl OverlapsValue for $t where C: CollateRef, { fn overlaps_value(&self, value: &T, collator: &C) -> Overlap { overlaps_value(self, value, collator) } } }; } overlaps_value!((Bound, Bound)); overlaps_value!(Range); overlaps_value!(RangeFull); overlaps_value!(RangeFrom); overlaps_value!(RangeInclusive); overlaps_value!(RangeTo); overlaps_value!(RangeToInclusive); #[inline] fn cmp_bound<'a, T, C>( collator: &'a C, left: Bound<&'a T>, right: Bound<&'a T>, l_ex: Ordering, r_ex: Ordering, ) -> Ordering where C: CollateRef, { match (left, right) { (Bound::Unbounded, Bound::Unbounded) => Ordering::Equal, (_, Bound::Unbounded) => l_ex, (Bound::Unbounded, _) => r_ex, (Bound::Included(this), Bound::Included(that)) => collator.cmp_ref(this, that), (Bound::Excluded(this), Bound::Excluded(that)) => collator.cmp_ref(this, that), (Bound::Excluded(this), Bound::Included(that)) => match collator.cmp_ref(this, that) { Ordering::Equal => l_ex, ordering => ordering, }, (Bound::Included(this), Bound::Excluded(that)) => match collator.cmp_ref(this, that) { Ordering::Equal => r_ex, ordering => ordering, }, } } fn overlaps(collator: &C, left: &L, right: &R) -> Overlap where C: CollateRef, L: RangeBounds, R: RangeBounds, { let start = cmp_bound( collator, left.start_bound(), right.start_bound(), Ordering::Greater, Ordering::Less, ); let end = cmp_bound( collator, left.end_bound(), right.end_bound(), Ordering::Less, Ordering::Greater, ); match (start, end) { (Ordering::Equal, Ordering::Equal) => Overlap::Equal, (Ordering::Greater, Ordering::Less) => Overlap::Narrow, (Ordering::Greater, Ordering::Equal) => Overlap::Narrow, (Ordering::Equal, Ordering::Less) => Overlap::Narrow, (Ordering::Less, Ordering::Greater) => Overlap::Wide, (Ordering::Less, Ordering::Equal) => Overlap::WideLess, (Ordering::Equal, Ordering::Greater) => Overlap::WideGreater, (Ordering::Less, _) => { match cmp_bound( collator, left.end_bound(), right.start_bound(), Ordering::Less, Ordering::Less, ) { Ordering::Less => Overlap::Less, Ordering::Greater | Ordering::Equal => Overlap::WideLess, } } (_, Ordering::Greater) => { match cmp_bound( collator, left.start_bound(), right.end_bound(), Ordering::Greater, Ordering::Greater, ) { Ordering::Less | Ordering::Equal => Overlap::WideGreater, Ordering::Greater => Overlap::Greater, } } } } #[inline] fn overlaps_value(range: &R, value: &T, collator: &C) -> Overlap where C: CollateRef, R: RangeBounds, { let start = match range.start_bound() { Bound::Unbounded => Ordering::Less, Bound::Included(start) => collator.cmp_ref(start, value), Bound::Excluded(start) => match collator.cmp_ref(start, value) { Ordering::Less => Ordering::Less, Ordering::Greater | Ordering::Equal => Ordering::Greater, }, }; let end = match range.end_bound() { Bound::Unbounded => Ordering::Greater, Bound::Included(end) => collator.cmp_ref(end, value), Bound::Excluded(end) => match collator.cmp_ref(end, value) { Ordering::Greater => Ordering::Greater, Ordering::Less | Ordering::Equal => Ordering::Less, }, }; match (start, end) { (start, Ordering::Less) => { debug_assert_eq!(start, Ordering::Less); Overlap::Less } (Ordering::Greater, end) => { debug_assert_eq!(end, Ordering::Greater); Overlap::Greater } (Ordering::Equal, Ordering::Equal) => Overlap::Equal, (Ordering::Equal, Ordering::Greater) => Overlap::WideGreater, (Ordering::Less, Ordering::Greater) => Overlap::Wide, (Ordering::Less, Ordering::Equal) => Overlap::WideLess, } }