ranges 0.3.3

use core::ops::Bound;

use crate::{Domain, GenericRange, Ranges};

impl<T: Domain> Ranges<T> {
    /// Returns true if the given `item` is contained in any of the internal disjoint ranges.
    ///
    /// # Note
    /// In contrast to the `GenericRange` constructor, item values will not be clamped to
    /// the domain and immediately return false if outside of it.
    ///
    /// # Example
    /// ```
    /// use ranges::Ranges;
    ///
    /// let ranges = Ranges::from(vec![0..3, 5..10]);
    /// assert!(ranges.contains(&2));
    /// assert!(ranges.contains(&7));
    /// assert!(!ranges.contains(&4));
    ///
    /// ```
    #[must_use]
    #[allow(clippy::indexing_slicing, clippy::integer_arithmetic, clippy::integer_division)]
    pub fn contains(&self, item: &T) -> bool {
        let mut comp_range = &self.ranges[..];

        match T::maximum() {
            Bound::Included(ref max) => {
                if item > max {
                    return false;
                }
            }
            Bound::Excluded(ref max) => {
                if item >= max {
                    return false;
                }
            }
            Bound::Unbounded => (),
        }

        match T::minimum() {
            Bound::Included(ref min) => {
                if item < min {
                    return false;
                }
            }
            Bound::Excluded(ref min) => {
                if item <= min {
                    return false;
                }
            }
            Bound::Unbounded => (),
        }

        match self.ranges.len() {
            0 => false,
            1 => self.ranges[0].contains(item),
            _ => loop {
                let slice_len = comp_range.len();
                if slice_len <= 2 {
                    break comp_range[0].contains(item) || comp_range[slice_len - 1].contains(item);
                }

                if !GenericRange::generic_start_end_contains(&comp_range[0].start, &comp_range[slice_len - 1].end, item)
                {
                    return false;
                }

                if comp_range[0].contains(item) || comp_range[slice_len - 1].contains(item) {
                    return true;
                }

                if GenericRange::generic_start_end_contains(&comp_range[0].start, &comp_range[slice_len / 2].end, item)
                {
                    comp_range = &comp_range[..=(slice_len / 2)];
                } else {
                    comp_range = &comp_range[(slice_len / 2)..];
                }
            },
        }
    }
}

#[cfg(test)]
mod tests {
    use crate::Ranges;

    #[test]
    fn empty() {
        let ranges = Ranges::new();
        assert!(!ranges.contains(&4));
    }

    #[test]
    fn single_range() {
        let ranges = Ranges::from(5..10);
        assert!(!ranges.contains(&4));
        assert!(ranges.contains(&7));
        assert!(!ranges.contains(&10));
    }

    #[test]
    fn unbound_start() {
        let ranges = Ranges::from(..10);
        assert!(ranges.contains(&-42));
        assert!(ranges.contains(&4));
        assert!(ranges.contains(&7));
        assert!(!ranges.contains(&10));
    }
    #[test]
    fn binary_search() {
        let mut ranges = Ranges::new();
        assert!(!ranges.contains(&5));
        assert!(!ranges.contains(&10));
        ranges.insert(..5);
        assert!(ranges.contains(&3));
        assert!(!ranges.contains(&5));
        ranges.insert(10..14);
        ranges.insert(75..100);
        ranges.insert(155..300);
        ranges.insert(399..);
        assert!(ranges.contains(&4));
        assert!(ranges.contains(&10));
        assert!(ranges.contains(&80));
        assert!(ranges.contains(&200));
        assert!(ranges.contains(&900));
        assert!(!ranges.contains(&5));
        assert!(!ranges.contains(&7));
        assert!(!ranges.contains(&14));
        assert!(!ranges.contains(&60));
        assert!(!ranges.contains(&100));
        assert!(!ranges.contains(&130));
        assert!(!ranges.contains(&300));
        ranges.ranges.pop();
        assert!(!ranges.contains(&399));
    }
}