odsek 0.1.0

use crate::{interval::*, Intervals};

/// An [`Intervals`] stream backed by a borrowed slice of pre-sorted
/// [`Interval`]s.
///
/// `head(pos)` does a binary search on the slice, so random-access queries
/// are `O(log n)`. The caller is responsible for ensuring the slice is
/// already sorted by left endpoint and that intervals do not overlap.
pub struct IntervalsFromArray<'a, E, V> {
    array: &'a [Interval<E, V>],
}

impl<'a, E, V> IntervalsFromArray<'a, E, V> {
    /// Wrap a borrowed slice of intervals.
    ///
    /// The slice must already be sorted by left endpoint and contain no
    /// overlapping intervals.
    pub fn new(array: &'a [Interval<E, V>]) -> Self {
        Self { array }
    }
}

impl<'a, E, V> Intervals for IntervalsFromArray<'a, E, V>
where
    E: Clone + EndpointToggle,
    V: Clone,
    LeftT<E>: Ord,
{
    type Endpoint = E;
    type Value = V;

    fn head(&mut self, pos: Option<LeftT<E>>) -> Option<Interval<E, V>> {
        if self.array.is_empty() {
            return None;
        }
        if pos.is_none() {
            return Some(self.array[0].clone());
        }
        let _pos = pos.unwrap();
        let mut head = 0;
        let mut n = self.array.len();
        while n > 0 {
            let step = n / 2;
            let p = head + step;
            if _pos < self.array[p].right().into_left() {
                n = step;
            } else {
                head = p + 1;
                n -= step + 1;
            }
        }
        if head == self.array.len() {
            None // end of stream
        } else {
            Some(self.array[head].clone())
        }
    }
}

#[cfg(test)]
mod tests {
    //use core::println;
    //use core::option::Option;
    use crate::{EndpointOC, Interval, Intervals, IntervalsFromArray, IntoIntervals, LeftT};
    use std::vec::Vec;

    #[test]
    fn test() {
        let a = Interval::new(EndpointOC::Closed(1), EndpointOC::Closed(2), 3);
        let arr = [a];
        let ia = IntervalsFromArray::new(&arr);
        if let Some(i) = ia.into_iter().next() {
            let x = i.left().endpoint().closed();
            let y = i.right().endpoint().closed();
            let v = i.value();
            assert_eq!(x.unwrap(), 1);
            assert_eq!(y.unwrap(), 2);
            assert_eq!(v, 3);
        }
    }

    #[test]
    fn test_arr_open_open() {
        let mut v = Vec::new();
        let n = 4;
        for i in 0..n {
            let a = Interval::new(EndpointOC::Open(3 * i + 1), EndpointOC::Open(3 * i + 2), i);
            v.push(a);
        }

        for ni in [n - 1, n] {
            let varr = &v[0..ni];
            let mut ia = IntervalsFromArray::new(varr);
            for p in 0..=(3 * ni) {
                let mut ib = IntervalsFromArray::new(varr);
                let ep_expected = if p + 3 >= 3 * ni + 2 {
                    None
                } else {
                    let m = p % 3;
                    let i = if m >= 2 { p / 3 + 1 } else { p / 3 };
                    Some(Interval::new(
                        EndpointOC::Open(3 * i + 1),
                        EndpointOC::Open(3 * i + 2),
                        i,
                    ))
                };
                let ep = LeftT::Left(EndpointOC::Closed(p));

                let mapf = |e: Interval<EndpointOC<usize>, usize>| {
                    Interval::new(
                        e.left().endpoint().clone(),
                        e.right().endpoint().clone(),
                        e.value(),
                    )
                };

                let iah = ia.head(Some(ep.clone())).map(mapf);
                assert_eq!(iah, ep_expected);

                let ibh = ib.head(Some(ep)).map(mapf);
                assert_eq!(ibh, ep_expected);
            }
        }
    }

    #[test]
    fn test_arr_close_close() {
        let mut v = Vec::new();
        let n = 4;
        for i in 0..n {
            let a = Interval::new(
                EndpointOC::Closed(3 * i + 1),
                EndpointOC::Closed(3 * i + 2),
                i,
            );
            v.push(a);
        }

        for ni in [n - 1, n] {
            let varr = &v[0..ni];
            let mut ia = IntervalsFromArray::new(varr);
            for p in 0..=(3 * ni) {
                let mut ib = IntervalsFromArray::new(varr);
                let ep_expected = if p + 3 >= 3 * ni + 3 {
                    None
                } else {
                    let m = p % 3;
                    let i = if m >= 3 { p / 3 + 1 } else { p / 3 };
                    Some(Interval::new(
                        EndpointOC::Closed(3 * i + 1),
                        EndpointOC::Closed(3 * i + 2),
                        i,
                    ))
                };
                let ep = LeftT::Left(EndpointOC::Closed(p));

                let mapf = |e: Interval<EndpointOC<usize>, usize>| {
                    Interval::new(
                        e.left().endpoint().clone(),
                        e.right().endpoint().clone(),
                        e.value(),
                    )
                };

                let iah = ia.head(Some(ep.clone())).map(mapf);
                assert_eq!(iah, ep_expected);

                let ibh = ib.head(Some(ep)).map(mapf);
                assert_eq!(ibh, ep_expected);
            }
        }
    }
}