Utilities for range types. Consider using the `rangetools` crate instead.

range_utils.rs

//! Utilities for range types.
//!
//! Consider using the `rangetools` crate instead.

use crate::num::PrimInt;
use std::fmt::Debug;
use std::ops::{Bound, RangeBounds, RangeInclusive};

/// An iterator over an arbitrary implementation of [`RangeBounds`].
///
/// Even if the range is unbounded,
/// this will return a finite number of values.
/// In this respect, this iterator differs from the standard library.
///
/// This is likely to be slower than a type-specific iterator.
pub struct ArbitraryRangeIter<T: PrimInt> {
    start: T,
    end: T,
    finished: bool,
}
impl<T: PrimInt> ArbitraryRangeIter<T> {
    /// Create a new iterator from the specified range.
    pub fn new(range: &impl RangeBounds<T>) -> Self {
         match to_inclusive_range(range) {
            Ok(range) => {
                let (start, end) = range.into_inner();
                ArbitraryRangeIter {
                    start,
                    end,
                    finished: false, // guarenteed non-empty
                }
            },
            Err(EmptyRangeError) => ArbitraryRangeIter {
                start: T::ZERO,
                end: T::ZERO,
                finished: true, // empty
            }
        }
    }
}
impl<T: PrimInt> Iterator for ArbitraryRangeIter<T> {
    type Item = T;

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        if !self.finished && self.start <= self.end {
            let current = self.start;
            match current.checked_add(T::ONE) {
                // overflow, so this is the last value
                None => {
                    self.finished = true;
                },
                Some(next_start) => {
                    self.start = next_start;
                }
            }
            Some(current)
        } else {
            None
        }
    }
}

/// Indicates that a range is empty,
/// so it cannot be represented as an [`RangeInclusive`].
#[derive(Copy, Clone, Debug, Eq, PartialEq)]
pub struct EmptyRangeError;

/// Convert a range to an [`RangeInclusive`],
/// returning an error if it is empty.
#[inline]
pub fn to_inclusive_range<T: PrimInt, R: RangeBounds<T>>(range: &R) -> Result<RangeInclusive<T>, EmptyRangeError> {
    let inclusive_start = match range.start_bound() {
        Bound::Included(&val) => val,
        Bound::Excluded(&val) => val.checked_add(T::ONE).ok_or(EmptyRangeError)?,
        Bound::Unbounded => T::MIN,
    };
    let inclusive_end = match range.end_bound() {
        Bound::Included(&val) => val,
        Bound::Excluded(&val) => val.checked_sub(T::ONE).ok_or(EmptyRangeError)?,
        Bound::Unbounded => T::MAX,
    };
    // malformed range is empty
    if inclusive_start > inclusive_end {
        return Err(EmptyRangeError);
    }
    Ok(inclusive_start..=inclusive_end)
}

/// Check if the two ranges are disjoint (don't overlap).
#[inline]
pub fn are_disjoint_ranges<T, U, Idx>(x: &T, y: &U) -> bool
where
    T: RangeBounds<Idx>,
    U: RangeBounds<Idx>,
    Idx: PrimInt
{
    // Convert to RangeInclusive for easier comparison
    let (x_start_inclusive, x_end_inclusive) = match to_inclusive_range(x) {
        Err(EmptyRangeError) => return false, // empty ranges never overlap
        Ok(val) => val.into_inner(),
    };
    let (y_start_inclusive, y_end_inclusive) = match to_inclusive_range(y) {
        Err(EmptyRangeError) => return false, // empty ranges never overlap
        Ok(val) => val.into_inner(),
    };
    // OVERLAP: y.start <= x.end && y.end >= x.start
    // [      ]
    //     [     ]
    // OVERLAP: y.start <= x.end && y.end >= x.start
    // [     ]
    //   [ ]
    // NO OVERLAP: y.start <= x.end && y.end <= x.start
    //     [   ]
    // [ ]
    // NO OVERLAP: y.start >= x.end && y.end >= x.start
    // [     ]
    //         []
    //
    // so overlap iff y.start <= x.end && y.end >= x.start
    y_start_inclusive <= x_end_inclusive &&
        y_end_inclusive >= x_start_inclusive
}

/// An error indicating that two ranges do not overlap.
#[derive(Copy, Clone, Debug, Eq, PartialEq)]
pub struct DisjointRangeError;

/// Determine the intersection between two ranges
/// as a [`RangeInclusive`].
///
/// Return [`DisjointRangeError`] if the ranges are disjoint.
#[inline]
pub fn determine_range_intersection<T, U, Idx>(x: &T, y: &U) -> Result<RangeInclusive<Idx>, DisjointRangeError>
where
    T: RangeBounds<Idx>,
    U: RangeBounds<Idx>,
    Idx: PrimInt {
    let (x_start_inclusive, x_end_inclusive) = match to_inclusive_range(x) {
        Err(EmptyRangeError) => return Err(DisjointRangeError), // empty ranges never overlap
        Ok(val) => val.into_inner(),
    };
    let (y_start_inclusive, y_end_inclusive) = match to_inclusive_range(y) {
        Err(EmptyRangeError) => return Err(DisjointRangeError), // empty ranges never overlap
        Ok(val) => val.into_inner(),
    };

    let min_start = x_start_inclusive.max(y_start_inclusive);
    let max_end = x_end_inclusive.min(y_end_inclusive);
    if min_start <= max_end {
        Ok(min_start..=max_end)
    } else {
        Err(DisjointRangeError)
    }
}

#[cfg(test)]
mod test {
    use super::*;
    use foldhash::HashSet;
    use std::ops::RangeBounds;
    use quickcheck::QuickCheck;

    #[test]
    fn test_range_iter() {
        fn do_test<T: RangeBounds<u8> + Clone + Iterator<Item=u8>>(val: T) {
            assert_ne!(
                val.end_bound(),
                Bound::Unbounded,
                "Range unbounded above will cause overflow"
            );
            assert_eq!(
                ArbitraryRangeIter::new(&val).collect::<Vec<u8>>(),
                val.clone().collect::<Vec<u8>>(),
            );
        }
        do_test(0..0);
        do_test(0..=0);
        do_test(0..8);
        do_test(1..=u8::MAX);
        do_test(0..=u8::MAX);
        do_test(1..u8::MAX);
        do_test(u8::MAX..u8::MAX);
    }

    #[test]
    fn test_range_overlap() {
        fn do_test<T: RangeBounds<u8>, U: RangeBounds<u8>>(first: T, second: U) {
            let claimed_overlap = match determine_range_intersection(&first, &second) {
                Ok(overlap) => {
                    assert!(!overlap.is_empty());
                    overlap.collect::<Vec<u8>>()
                },
                Err(DisjointRangeError) => Vec::new(),
            };
            let first_elements = ArbitraryRangeIter::new(&first)
                .collect::<HashSet<u8>>();
            let second_elements = ArbitraryRangeIter::new(&second)
                .collect::<HashSet<u8>>();
            let mut actual_overlap = first_elements.intersection(&second_elements)
                .copied()
                .collect::<Vec<u8>>();
            actual_overlap.sort();
            assert_eq!(
                claimed_overlap,
                actual_overlap,
                "({:?}, {:?}) & ({:?}, {:?})",
                first.start_bound(),
                first.end_bound(),
                second.start_bound(),
                second.end_bound(),
            );
            assert_eq!(
                !claimed_overlap.is_empty(),
                are_disjoint_ranges(&first, &second),
            )
        }
        do_test(17..32, 1..=17);
        do_test(18.., 1..18);
        do_test(..=u8::MAX, 1..u8::MAX);
        do_test(0..17, (Bound::Excluded(0), Bound::Included(u8::MAX)));
        QuickCheck::new().quickcheck((|a: Bound<u8>, b, c: Bound<u8>, d| {
            do_test((a, b), (c, d))
        }) as fn(_, _, _, _))
    }
}