use std::{
    collections::{btree_set, BTreeSet},
    fmt::Debug,
    ops::Sub,
};

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

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

    /// Adds and merges the given range with set.
    pub fn push(&mut self, range: [T; 2]) {
        // Search if start or end item are contained in set ranges.
        let [start, end] = range;
        if start >= end {
            panic!("start item must be smaller than end item");
        }
        let (start_found, end_found) = self.contains_start_end_item(start, end);

        // Remove items contained in range from set.
        let values: Vec<_> = self.0.range(start..=end).map(|v| *v).collect();
        for v in &values {
            self.0.remove(v);
        }

        // Add start and end item to set.
        if !start_found {
            self.0.insert(start);
        }
        if !end_found {
            self.0.insert(end);
        }
    }

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

    pub fn union(&self, _other: Ranges<T>) -> Ranges<T> {
        Ranges(self.0.clone())
    }

    #[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; 2]]> for Ranges<T>
where
    T: Ord + Eq + Copy + Debug,
{
    fn from(values: &[[T; 2]]) -> 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>(btree_set::Iter<'a, T>);

impl<'a, T> RangesIter<'a, T> {
    pub fn new(iter: btree_set::Iter<'a, T>) -> RangesIter<'a, T> {
        RangesIter(iter)
    }
}

impl<'a, T> Iterator for RangesIter<'a, T>
where
    T: Copy,
{
    type Item = [T; 2];
    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.union(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]]),
        ] {
            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 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);
        }
    }
}