int_ranges 0.1.1

// Copyright 2022 hjiayz
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#[doc = include_str!("../README.md")]
use std::{
    marker::PhantomData,
    ops::{Bound, RangeBounds},
    vec,
};

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Ranges<T: Int>(Vec<Range<T>>);

#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub struct Range<T: Int>(T, T);

pub trait Int: PartialOrd + Ord + PartialEq + Eq + Copy + Clone {
    const MAX: Self;
    const MIN: Self;
    fn inc(self) -> Self;
    fn dec(self) -> Self;
}

macro_rules! impl_int {
    ($ident:ty) => {
        impl Int for $ident {
            const MAX : Self = <$ident>::MAX;
            const MIN : Self = <$ident>::MIN;
            fn inc(self)->Self {
                self.saturating_add(1)
            }
            fn dec(self)->Self {
                self.saturating_sub(1)
            }
        }
    };
    ($($ident:ty),*) => {
        $( impl_int!($ident); )*
    }
}

impl_int!(u8, i8, u16, i16, u32, i32, u64, i64, u128, i128, usize, isize);

impl<T: Int> From<(Bound<T>, Bound<T>)> for Range<T> {
    /// # Panics
    /// It is asserted that `start <= end`.
    #[inline]
    fn from(src: (Bound<T>, Bound<T>)) -> Self {
        let start = match src.0 {
            Bound::Excluded(i) => i.dec(),
            Bound::Included(i) => i,
            Bound::Unbounded => T::MIN,
        };
        let end = match src.1 {
            Bound::Excluded(i) => i.inc(),
            Bound::Included(i) => i,
            Bound::Unbounded => T::MAX,
        };
        assert!(
            start <= end,
            "range start has to be less or equal to the end"
        );
        Range(start, end)
    }
}

pub struct Wrap<I: Int, T: RangeBounds<I>>(T, PhantomData<I>);

pub fn wrap<I: Int, T: RangeBounds<I>>(src: T) -> Wrap<I, T> {
    Wrap(src, PhantomData)
}

impl<I: Int, T: RangeBounds<I>> From<Wrap<I, T>> for Range<I> {
    /// # Panics
    /// It is asserted that `start <= end`.
    #[inline]
    fn from(src: Wrap<I, T>) -> Self {
        let start = match src.0.start_bound() {
            Bound::Excluded(i) => i.dec(),
            Bound::Included(i) => *i,
            Bound::Unbounded => I::MIN,
        };
        let end = match src.0.end_bound() {
            Bound::Excluded(i) => i.inc(),
            Bound::Included(i) => *i,
            Bound::Unbounded => I::MAX,
        };
        assert!(
            start <= end,
            "range start has to be less or equal to the end"
        );
        Range(start, end)
    }
}

impl<T: Int> From<(T, T)> for Range<T> {
    /// # Panics
    /// It is asserted that `start <= end`.
    #[inline]
    fn from(src: (T, T)) -> Self {
        let start = src.0;
        let end = src.1;
        assert!(
            start <= end,
            "range start has to be less or equal to the end"
        );
        Range(start, end)
    }
}

impl<T: Int> From<Range<T>> for (T, T) {
    #[inline]
    fn from(val: Range<T>) -> Self {
        (val.0, val.1)
    }
}

impl<T: Int> From<Ranges<T>> for Vec<(T, T)> {
    #[inline]
    fn from(val: Ranges<T>) -> Self {
        val.0.into_iter().map(|i| i.into()).collect()
    }
}

impl<T: Int, U> From<Vec<U>> for Ranges<T>
where
    U: Into<Range<T>>,
{
    #[inline]
    fn from(src: Vec<U>) -> Self {
        let mut ranges: Vec<Range<T>> = src.into_iter().map(|u| u.into()).collect();
        ranges.sort_by_cached_key(|val| val.0);
        let mut result = Vec::new();
        for cur in ranges {
            if result.is_empty() {
                result.push(cur);
                continue;
            }
            let prev = result.last_mut().unwrap();
            if prev.1 < (cur.0.dec()) {
                result.push(cur);
                continue;
            }
            prev.1 = T::max(prev.1, cur.1);
        }
        Ranges(result)
    }
}

impl<T: Int> Ranges<T> {
    /// Inverts the range set.
    #[inline]
    pub fn invert(self) -> Self {
        let ranges = self.0;
        let mut new_ranges = vec![];
        if ranges.is_empty() {
            return Ranges(vec![Range(T::MIN, T::MAX)]);
        }
        if ranges[0].0 != T::MIN {
            new_ranges.push(Range(T::MIN, ranges[0].0.dec()));
        }
        for slice in ranges.windows(2) {
            new_ranges.push(Range(slice[0].1.inc(), slice[1].0.dec()));
        }
        let last = ranges.last().unwrap().1;
        if last != T::MAX {
            new_ranges.push(Range(last.inc(), T::MAX));
        }
        Ranges(new_ranges)
    }

    #[inline]
    pub fn full() -> Self {
        Ranges(vec![Range(T::MIN, T::MAX)])
    }

    #[inline]
    pub fn empty() -> Self {
        Ranges(vec![])
    }

    #[inline]
    pub fn union<R: Into<Self>>(mut self, other: R) -> Self {
        self.0.append(&mut other.into().0);
        Self::from(self.0)
    }

    #[inline]
    pub fn intersect<R: Into<Self>>(&self, other: R) -> Self {
        let mut left = self.0.iter();
        let other = other.into();
        let mut right = other.0.iter();
        let mut left_next = left.next();
        let mut right_next = right.next();
        let mut result = Vec::new();
        while let (Some(left_value), Some(right_value)) = (left_next, right_next) {
            let start = T::max(left_value.0, right_value.0);
            let end;
            if left_value.1 < right_value.1 {
                end = left_value.1;
                left_next = left.next();
            } else {
                end = right_value.1;
                right_next = right.next();
            }
            if start > end {
                continue;
            }
            let cur = Range(start, end);
            if result.is_empty() {
                result.push(cur);
                continue;
            }
            let prev = result.last_mut().unwrap();
            if prev.1 < (cur.0.dec()) {
                result.push(cur);
                continue;
            }
            prev.1 = T::max(prev.1, cur.1);
        }
        Ranges(result)
    }

    #[inline]
    pub fn contains<R: Into<Self>>(&self, other: R) -> bool {
        let mut left = self.0.iter();
        let other = other.into();
        let mut right = other.0.iter();
        let mut left_next = left.next();
        let mut right_next = right.next();
        while let (Some(left_value), Some(right_value)) = (left_next, right_next) {
            let start = T::max(left_value.0, right_value.0);
            let end;
            if left_value.1 < right_value.1 {
                end = left_value.1;
                left_next = left.next();
            } else {
                end = right_value.1;
                right_next = right.next();
            }
            if start > end {
                continue;
            }
            return true;
        }
        false
    }
}