ranges 0.4.0

use alloc::{vec, vec::Vec};
use core::iter::FromIterator;

use crate::{generic_range::GenericRange, Arrangement, Domain};

/// Trait implementation of `Arbitrary` for use in fuzzers.
#[cfg(feature = "arbitrary")]
mod arbitrary;
/// Ranges methods to find out if a value is contained within.
mod contains;
/// Ranges difference.
mod difference;
/// Ranges formatting.
mod format;
/// Ranges insertion.
mod insert;
/// Ranges intersection.
mod intersect;
/// Ranges inversion.
mod invert;
/// Iterator implementations.
mod iterators;
/// Proptest `Arbitrary`.
#[cfg(any(feature = "proptest", test))]
mod proptest;
/// Ranges removal.
mod remove;
/// Ranges symmetric difference.
mod symmetric_difference;
/// Ranges unionization.
mod union;

/// A range set storing `GenericRange`s in the most memory-optimal fashion possible.
///
/// The two guarantees of storing ranges disjoint and sorted allows for the following optimizations:
/// - keeping them ordered, upper and lower bounds for searches can be used to keep the search
///   space as small as possible
/// - storing them disjoint is a by-product of automatically merging newly inserted ranges, which
///   additionally helps to reduce reindexing of the internal vector
///
#[allow(clippy::missing_inline_in_public_items)]
#[derive(Clone, Debug, Default, Hash, PartialEq, Eq)]
pub struct Ranges<T: Domain> {
    /// Inner storage - can and probably will be replaced with something more efficient
    /// as soon as const generics are available (like an array with a pre-defined size,
    /// which makes sense if you know how many discrete singletons you may have, e.g. for integers).
    pub(crate) ranges: Vec<GenericRange<T>>,
}

impl<T: Domain> Ranges<T> {
    /// Creates a new empty `Ranges` with an initial capacity of 0.
    #[must_use]
    pub fn new() -> Self {
        Self::with_capacity(0)
    }

    /// Initializes the underlying vector with a given capacity.
    #[must_use]
    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            ranges: Vec::with_capacity(capacity),
        }
    }

    /// Initializes the underlying vector with a single full range.
    #[must_use]
    pub fn full() -> Self {
        Self {
            ranges: vec![GenericRange::full()],
        }
    }

    /// Returns true if the whole domain is in this range.
    #[allow(clippy::indexing_slicing)]
    #[must_use]
    pub fn is_full(&self) -> bool
    where
        T: PartialEq,
    {
        // we could do `*self == Self::full()` but that would require vector allocation at runtime
        // however, as soon as Self::full() becomes constant, it should be used instead
        self.ranges.len() == 1 && self.ranges[0] == GenericRange::full()
    }

    /// Returns the amount of saved disjoint ranges.
    #[must_use]
    pub fn len(&self) -> usize {
        self.ranges.len()
    }

    /// Returns true if there are no ranges and we have an empty set.
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.ranges.is_empty()
    }

    /// Find the `GenericRange`s in `self` which at least touch `other`.
    ///
    /// Since `other` is a `GenericRange` (i.e. contiguous),
    /// the overlapping ranges must all be consecutive.
    /// Therefore, this only returns the indices of the first and last ranges which overlap.
    ///
    /// This returns a (start, end) pair of indices into `self.ranges`.
    ///
    /// # Example
    /// ```
    /// use ranges::Ranges;
    ///
    /// let ranges = Ranges::from(vec![0..5, 10..20, 25..30, 45..50]);
    /// assert_eq!(ranges.find_intersecting_ranges(&(7..47).into()), Some((1, 3)))
    /// ```
    #[must_use]
    pub fn find_intersecting_ranges(&self, other: &GenericRange<T>) -> Option<(usize, usize)> {
        let mut seen_overlap = false;
        let mut indices = None;

        for (index, range) in self.ranges.iter().enumerate() {
            #[allow(clippy::wildcard_enum_match_arm)]
            let overlap = match other.arrangement(range) {
                Arrangement::Disjoint { .. } => false,
                Arrangement::Empty { .. } => return None,
                _ => true,
            };

            match (seen_overlap, overlap) {
                // we have not seen overlap and there is none... continue
                //
                // range     |----|
                // new_range        |--------|
                (false, false) => {}
                // this is the first intersecting range
                //
                // either starting in the same place:
                // range            |----|
                // new_range        |--------|
                //
                // or starting before with overlap:
                // range          |------|
                // new_range        |--------|
                (false, true) => {
                    seen_overlap = true;
                    indices = Some((index, index));
                }
                // we're in the middle of ranges that intersect
                //
                // either completely within the new range:
                // range                 |--|
                // new_range        |--------|
                //
                // or extending past:
                // range                  |----|
                // new_range        |--------|
                (true, true) => {
                    indices = indices.map(|(start, _)| (start, index));
                }
                // we've reached the end of intersecting ranges
                // even if there are more ranges after this,
                // they could not possibly overlap.
                //
                // range                      |---|
                // new_range        |--------|
                (true, false) => {
                    break;
                }
            }
        }

        indices
    }

    /// Returns the internal vector of `GenericRange`s as a slice.
    #[must_use]
    pub fn as_slice(&self) -> &[GenericRange<T>] {
        self.ranges.as_slice()
    }
}

impl<T: Domain, U> From<U> for Ranges<T>
where
    U: Into<GenericRange<T>>,
{
    #[must_use]
    fn from(range_value: U) -> Self {
        let range = range_value.into();

        let mut ranges = Self::new();
        #[allow(clippy::let_underscore_untyped)]
        let _ = ranges.insert(range);

        ranges
    }
}

impl<T: Domain, U> From<Vec<U>> for Ranges<T>
where
    U: Into<GenericRange<T>>,
{
    #[must_use]
    fn from(items: Vec<U>) -> Self {
        let mut ranges = Self::with_capacity(items.capacity());
        // we can not just transfer the contents, as there might be overlapping entries
        #[allow(clippy::let_underscore_untyped)]
        for range in items {
            let _ = ranges.insert(range.into());
        }

        ranges
    }
}

impl<T: Domain> FromIterator<GenericRange<T>> for Ranges<T> {
    #[allow(clippy::shadow_reuse)]
    fn from_iter<I: IntoIterator<Item = GenericRange<T>>>(iter: I) -> Self {
        let iter = iter.into_iter();
        // edge case: n ranges, all being empty, would unnecessarily allocate but is better
        // than the alternative: n ranges all being separately allocated.
        let (lower_bound, _) = iter.size_hint();

        let mut ranges = Self::with_capacity(lower_bound);
        #[allow(clippy::let_underscore_untyped)]
        for range in iter {
            let _ = ranges.insert(range);
        }

        ranges.ranges.shrink_to_fit();

        ranges
    }
}

impl<T: Domain> AsRef<Vec<GenericRange<T>>> for Ranges<T> {
    fn as_ref(&self) -> &Vec<GenericRange<T>> {
        &self.ranges
    }
}

#[cfg(test)]
mod tests {
    use alloc::vec;
    use core::ops::Bound;

    use crate::{GenericRange, Ranges};

    #[test]
    fn from_core_ranges() {
        // [x, y) - x..y
        assert_eq!(
            Ranges::from(1..5),
            Ranges {
                ranges: vec![GenericRange {
                    start: Bound::Included(1),
                    end: Bound::Excluded(5)
                }]
            }
        );

        // [x, y] - x..=y
        assert_eq!(
            Ranges::from(6..=10),
            Ranges {
                ranges: vec![GenericRange {
                    start: Bound::Included(6),
                    end: Bound::Included(10)
                }]
            }
        );

        // [x, +inf) - x..
        assert_eq!(
            Ranges::from(12..),
            Ranges {
                ranges: vec![GenericRange {
                    start: Bound::Included(12),
                    end: Bound::Included(2_147_483_647)
                }]
            }
        );

        // (-inf, y) - ..y
        assert_eq!(
            Ranges::from(..15),
            Ranges {
                ranges: vec![GenericRange {
                    start: Bound::Included(-2_147_483_648),
                    end: Bound::Excluded(15)
                }]
            }
        );

        // (-inf, y] - ..=y
        assert_eq!(
            Ranges::from(..=20),
            Ranges {
                ranges: vec![GenericRange {
                    start: Bound::Included(-2_147_483_648),
                    end: Bound::Included(20)
                }]
            }
        );

        // (-inf, +inf) - ..
        let ranges: Ranges<usize> = Ranges::from(..);
        assert_eq!(
            ranges,
            Ranges {
                ranges: vec![GenericRange {
                    start: Bound::Included(0),
                    end: Bound::Included(18_446_744_073_709_551_615)
                }]
            }
        );

        // (x, y) - has no Rust equivalent
        assert_eq!(
            Ranges::from((Bound::Excluded(30), Bound::Excluded(42))),
            Ranges {
                ranges: vec![GenericRange {
                    start: Bound::Excluded(30),
                    end: Bound::Excluded(42)
                }]
            }
        );

        // (x, y] - has no Rust equivalent
        assert_eq!(
            Ranges::from((Bound::Excluded(45), Bound::Included(50))),
            Ranges {
                ranges: vec![GenericRange {
                    start: Bound::Excluded(45),
                    end: Bound::Included(50)
                }]
            }
        );

        // (x, +inf) - has no Rust equivalent
        assert_eq!(
            Ranges::from((Bound::Excluded(55), Bound::Unbounded)),
            Ranges {
                ranges: vec![GenericRange {
                    start: Bound::Excluded(55),
                    end: Bound::Included(2_147_483_647)
                }]
            }
        );
    }
}