use std::{
    fmt::Debug,
    //ops::Sub,
    slice,
};

#[derive(PartialEq, Clone, Debug)]
pub struct Ranges<T>(Vec<T>)
where
    T: Ord + Eq + Copy + Debug;

impl<T> Ranges<T>
where
    T: Ord + Eq + Copy + Debug,
{
    pub fn new() -> Ranges<T> {
        Ranges(vec![])
    }

    /// Adds and merges the given range with set.
    pub fn push(&mut self, range: (T, T)) {
        self.0.push(range.0);
        self.0.push(range.1);
    }

    pub fn iter(&self) -> RangesIter<T> {
        RangesIter::new(self.0.iter())
    }

/*
    pub fn intersection_2(&self, other: Ranges<T>) -> Ranges<T> {
        let mut set = BTreeSet::new();
        for [start, end] in other.iter() {
            let (start_found, end_found) = self.contains_start_end_item(start, end);
            if start_found {
                set.insert(start);
            }
            if end_found {
                set.insert(end);
            }
        }
        for [start, end] in self.iter() {
            let (start_found, end_found) = other.contains_start_end_item(start, end);
            if start_found {
                set.insert(start);
            }
            if end_found {
                set.insert(end);
            }
        }
        Ranges(set)
    }

    pub fn intersection(&self, other: Ranges<T>) -> Ranges<T> {
        let mut set = BTreeSet::new();
        let mut iter = self.0.iter();
        while let (Some(a), Some(b)) = (iter.next(), iter.next()) {
            if other.0.contains(a) && other.0.contains(b) {
                set.insert(*a);
                set.insert(*b);
            }
            for v in other.0.range(a..=b) {
                if v > a && v < b {
                    set.insert(*v);
                }
            }
        }
        let mut iter = other.0.iter();
        while let (Some(a), Some(b)) = (iter.next(), iter.next()) {
            for v in self.0.range(a..=b) {
                if v > a && v < b {
                    set.insert(*v);
                }
            }
        }
        Ranges(set)
    }

    #[inline]
    fn contains_start_end_item(&self, start: T, end: T) -> (bool, bool) {
        let mut start_found = false;
        let mut end_found = false;
        let mut iter = self.0.iter();
        while let (Some(a), Some(b)) = (iter.next(), iter.next()) {
            start_found = start_found || (start > *a && start <= *b);
            end_found = end_found || (end >= *a && end < *b);
            if start_found && end_found {
                break;
            }
        }
        (start_found, end_found)
    }
    */
}

/*
impl<T> Sub for Ranges<T>
where
    T: Ord + Eq + Copy + Debug,
{
    type Output = Ranges<T>;

    fn sub(self, other: Ranges<T>) -> Self::Output {
        let mut set = self.0.clone();
        for [start, end] in other.iter() {
            let (start_found, end_found) = self.contains_start_end_item(start, end);

            // Remove items contained in range from set.
            for v in self.0.range(start..=end) {
                set.remove(v);
            }

            // Add start and end item to set.
            if start_found {
                set.insert(start);
            }
            if end_found {
                set.insert(end);
            }
        }
        Ranges(set)
    }
}
*/

impl<T> From<&[(T, T)]> for Ranges<T>
where
    T: Ord + Eq + Copy + Debug,
{
    fn from(values: &[(T, T)]) -> Self {
        let mut res: Ranges<T> = Ranges::new();
        for v in values {
            res.push(*v);
        }
        res
    }
}

impl<T> From<&[T]> for Ranges<T>
where
    T: Ord + Eq + Copy + Debug,
{
    fn from(slice: &[T]) -> Self {
        let mut res: Ranges<T> = Ranges::new();
        if slice.len() >= 2 {
            res.push((slice[0], slice[slice.len() - 1]));
        }
        res
    }
}

pub struct RangesIter<'a, T>(slice::Iter<'a, T>)
where
    T: Ord + Eq + Copy + Debug;

impl<'a, T> RangesIter<'a, T>
where
    T: Ord + Eq + Copy + Debug,
{
    pub fn new(iter: slice::Iter<T>) -> RangesIter<T> {
        RangesIter(iter)
    }
}

impl<'a, T> Iterator for RangesIter<'a, T>
where
    T: Ord + Eq + Copy + Debug,
{
    type Item = (T, T);
    fn next(&mut self) -> Option<Self::Item> {
        if let (Some(a), Some(b)) = (self.0.next(), self.0.next()) {
            Some((*a, *b))
        } else {
            None
        }
    }
}


pub fn remove_inner_items<T>(slice: &mut Vec<T>, ranges: Ranges<T>)
where
    T: Ord + Eq + Copy + Debug,
{
    //let ranges = ranges.intersection(Ranges::from(&slice[..]));
    let mut iter = ranges.iter();
    let mut range = iter.next();
    slice.retain(|item| {
        if let Some(r) = range {
            if *item > r.1 {
                range = iter.next();
            }
        } else {
            return true;
        }
        if let Some(r) = range {
            if *item > r.0 && *item < r.1 {
                false
            } else {
                true
            }
        } else {
            true
        }
    });
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn add_range() {
        for data in vec![
            //(vec![[2, 4], [6, 8]], vec![[2, 4], [6, 8]]),
            //(vec![[2, 4], [2, 4]], vec![[2, 4]]),
            //(vec![[2, 4], [1, 4]], vec![[1, 4]]),
            //(vec![[2, 4], [1, 5]], vec![[1, 5]]),
            //(vec![[2, 4], [4, 8]], vec![[2, 8]]),
            /*(vec![[2, 4], [2, 8]], vec![[2, 8]]),
            (vec![[2, 4], [5, 8], [1, 9]], vec![[1, 9]]),
            (vec![[2, 4], [5, 8], [5, 9]], vec![[2, 4], [5, 9]]),
            (vec![[2, 8], [3, 5]], vec![[2, 8]]),
            (vec![[2, 8], [3, 8]], vec![[2, 8]]),
            (vec![[2, 8], [2, 5]], vec![[2, 8]]),*/
        ] {
            let ranges = Ranges::from(&data.0[..]);
            assert_eq!(data.1, ranges.iter().collect::<Vec<_>>());
        }
    }
/*
    #[test]
    fn subtract() {
        for data in vec![
            (vec![[2, 4]], vec![[2, 4]], vec![]),
            (vec![[2, 4]], vec![[4, 6]], vec![[2, 4]]),
            (vec![[2, 8]], vec![[4, 7]], vec![[2, 4], [7, 8]]),
            (vec![[2, 4], [6, 8]], vec![[4, 6]], vec![[2, 4], [6, 8]]),
            (vec![[4, 6]], vec![[3, 7]], vec![]),
            (vec![[0, 9]], vec![[3, 7]], vec![[0, 3], [7, 9]]),
            (vec![[0, 6]], vec![[4, 6]], vec![[0, 4]]),
            (vec![[0, 4], [6, 9]], vec![[3, 7]], vec![[0, 3], [7, 9]]),
            (vec![[0, 6]], vec![[0, 2], [4, 6]], vec![[2, 4]]),
            (vec![[0, 6]], vec![], vec![[0, 6]]),
            (vec![], vec![[0, 6]], vec![[0, 6]]),
            (
                vec![[0, 9]],
                vec![[1, 2], [4, 6]],
                vec![[0, 1], [2, 4], [6, 9]],
            ),
        ] {
            let op1: Ranges<i32> = Ranges::from(&data.0[..]);
            let op2: Ranges<i32> = Ranges::from(&data.1[..]);
            let expect = Ranges::from(&data.2[..]);
            assert_eq!(expect, op1 - op2);
        }
    }

    #[test]
    fn intersection() {
        for data in vec![
            (vec![[2, 4]], vec![[2, 4]], vec![[2, 4]]),
            (vec![[2, 6]], vec![[4, 9]], vec![[4, 6]]),
            (vec![[4, 6]], vec![[0, 4]], vec![]),
            (vec![[2, 6]], vec![[6, 9]], vec![]),
            (vec![[2, 8]], vec![[4, 7]], vec![[4, 7]]),
            (vec![[2, 4], [6, 8]], vec![[4, 6]], vec![]),
            (vec![[4, 6]], vec![[3, 7]], vec![[4, 6]]),
            (vec![[0, 9]], vec![[3, 7]], vec![[3, 7]]),
            (vec![[0, 6]], vec![[4, 6]], vec![[4, 6]]),
            (vec![[0, 4], [6, 9]], vec![[3, 7]], vec![[3, 4], [6, 7]]),
        ] {
            let op1: Ranges<i32> = Ranges::from(&data.0[..]);
            let op2: Ranges<i32> = Ranges::from(&data.1[..]);
            let expect = Ranges::from(&data.2[..]);
            assert_eq!(expect, op1.intersection(op2));
        }
    }

        #[test]
        fn test_remove_inner_items() {
            for data in vec![
                (vec![[3, 6]], vec![2, 3, 6, 7, 8]),
                //(vec![[3, 9]], vec![2, 3, 8]),
                //(vec![[0, 9]], vec![2, 8]),
                //(vec![[2, 8]], vec![2, 8]),
            ] {
                let mut slice = (2..=8).collect::<Vec<i32>>();
                remove_inner_items(&mut slice, Ranges::from(&data.0[..]));
                assert_eq!(data.1, slice);
            }
        }
    */
}