linesweeper 0.3.0

use std::iter::Peekable;

use kurbo::BezPath;

use crate::{
    geom::{monotonic_pieces, Point, Segment},
    num::CheapOrderedFloat,
};

/// An index into our segment arena.
///
/// Throughout this library, we assign identities to segments, so that we may
/// consider segments as different even if they have the same start- and end-points.
///
/// This index is used to identify a segment, whose data can be retrieved by looking
/// it up in [`Segments`]. (Of course, this index-as-identifier breaks down if there are
/// multiple `Segments` in flight. Just be careful not to mix them up.)
#[cfg_attr(test, derive(serde::Serialize))]
#[derive(Clone, Copy, PartialOrd, Ord, PartialEq, Eq, Hash)]
pub struct SegIdx(pub(crate) usize);

/// A vector indexed by `SegIdx`.
#[cfg_attr(test, derive(serde::Serialize))]
#[derive(Clone, Hash, PartialEq, Eq)]
#[cfg_attr(test, serde(transparent))]
pub struct SegVec<T> {
    inner: Vec<T>,
}

impl_typed_vec!(SegVec, SegIdx, "s");

/// An arena of segments, each of which is a cubic Bézier.
///
/// Segments are indexed by [`SegIdx`] and can be retrieved by indexing (i.e. with square brackets).
#[derive(Clone, Default)]
pub struct Segments {
    segs: SegVec<Segment>,
    contour_prev: SegVec<Option<SegIdx>>,
    contour_next: SegVec<Option<SegIdx>>,
    /// For each segment, stores true if the sweep-line order (small y to big y)
    /// is the same as the orientation in its original contour.
    orientation: SegVec<bool>,
    /// For each segment, stores its parameter range in the original input
    /// segment (which may have been split into monotonic sub-segments). Keeping
    /// track of where the splits happened allows us to potentially merge things
    /// back at the end.
    pub(crate) split_from_predecessor: SegVec<(f64, f64)>,
    /// The original input segments, for reconstructing/merging. (TODO: this
    /// representation is wasteful, since we only need it for segments that
    /// got split.)
    pub(crate) input_segs: SegVec<kurbo::PathSeg>,

    /// All the entrance heights, of segments, ordered by height.
    /// This includes horizontal segments.
    enter: Vec<(f64, SegIdx)>,
    /// All the exit heights of segments, ordered by height.
    /// This does not include horizontal segments.
    exit: Vec<(f64, SegIdx)>,
}

/// Certain operations expect closed paths, and return this as an error when a path is not closed.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct NonClosedPath {
    /// The point at the start of the non-closed path (always generated by a [`kurbo::PathEl::MoveTo`]).
    pub start_point: kurbo::Point,
    /// The point at the end of the non-closed path.
    pub end_point: kurbo::Point,
}

impl std::fmt::Display for NonClosedPath {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(
            f,
            "non-closed path starting at {} and ending at {}",
            self.start_point, self.end_point,
        )
    }
}

impl std::error::Error for NonClosedPath {}

struct SegmentEntryFormatter<'a> {
    idx: SegIdx,
    seg: &'a Segment,
    prev: Option<SegIdx>,
    next: Option<SegIdx>,
    oriented: bool,
}

impl std::fmt::Debug for SegmentEntryFormatter<'_> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let seg_idx = self.idx;
        let seg = self.seg;
        let prefix = if self.oriented {
            self.prev.map(|i| format!("{i:?} -> ")).unwrap_or_default()
        } else {
            self.next.map(|i| format!("{i:?} <- ")).unwrap_or_default()
        };
        let suffix = if self.oriented {
            self.next.map(|i| format!(" -> {i:?}")).unwrap_or_default()
        } else {
            self.prev.map(|i| format!(" <- {i:?}")).unwrap_or_default()
        };
        write!(f, "{seg_idx:?}: {prefix}{seg:?}{suffix}")
    }
}

impl std::fmt::Debug for Segments {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let mut list = f.debug_list();
        for (idx, seg) in self.segs.iter() {
            list.entry(&SegmentEntryFormatter {
                idx,
                seg,
                prev: self.contour_prev[idx],
                next: self.contour_next[idx],
                oriented: self.orientation[idx],
            });
        }
        list.finish()
    }
}

fn cyclic_pairs<T>(xs: &[T]) -> impl Iterator<Item = (&T, &T)> {
    pairs(xs).chain(xs.last().zip(xs.first()))
}

fn pairs<T>(xs: &[T]) -> impl Iterator<Item = (&T, &T)> {
    xs.windows(2).map(|pair| (&pair[0], &pair[1]))
}

struct SubpathIter<'a, I: Iterator> {
    inner: &'a mut Peekable<I>,
    started: bool,
}

impl<I> Iterator for SubpathIter<'_, I>
where
    I: Iterator<Item = kurbo::PathEl>,
{
    type Item = kurbo::PathEl;

    fn next(&mut self) -> Option<Self::Item> {
        let ret = self.inner.peek()?;
        if matches!(ret, kurbo::PathEl::MoveTo(_)) && self.started {
            None
        } else {
            self.started = true;
            self.inner.next()
        }
    }
}

struct Subpaths<I: Iterator> {
    inner: Peekable<I>,
}

impl<I> Subpaths<I>
where
    I: Iterator<Item = kurbo::PathEl>,
{
    fn next(&mut self) -> Option<SubpathIter<'_, I>> {
        if self.inner.peek().is_none() {
            None
        } else {
            Some(SubpathIter {
                inner: &mut self.inner,
                started: false,
            })
        }
    }
}

impl Segments {
    /// The number of segments in this arena.
    #[allow(clippy::len_without_is_empty)]
    pub fn len(&self) -> usize {
        self.segs.len()
    }

    /// Iterate over all indices that can be used to index into this arena.
    pub fn indices(&self) -> impl Iterator<Item = SegIdx> {
        (0..self.segs.len()).map(SegIdx)
    }

    /// Iterate over all segments in this arena.
    pub fn segments(&self) -> impl Iterator<Item = &Segment> {
        self.segs.iter().map(|(_, s)| s)
    }

    /// Returns the starting point of the segment at `idx`, relative to the segment's original orientation.
    ///
    /// The segment itself is stored in sweep-line order (i.e. its starting
    /// point has the smaller y coordinate) regardless of the original
    /// orientation of the segment. Use this method to retrieve the segment's
    /// original start point.
    pub fn oriented_start(&self, idx: SegIdx) -> Point {
        if self.orientation[idx] {
            self[idx].start()
        } else {
            self[idx].end()
        }
    }

    /// Returns the ending point of the segment at `idx`, relative to the segment's original orientation.
    ///
    /// The segment itself is stored in sweep-line order (i.e. its starting
    /// point has the smaller y coordinate) regardless of the original
    /// orientation of the segment. Use this method to retrieve the segment's
    /// original end point.
    pub fn oriented_end(&self, idx: SegIdx) -> Point {
        if self.orientation[idx] {
            self[idx].end()
        } else {
            self[idx].start()
        }
    }

    /// Returns the index of the segment following `idx`.
    ///
    /// If `idx` is part of a non-closed path and it is the last segment,
    /// this returns `None`. If `idx` is part of a closed path, this will
    /// always return `Some`, and you might need to be careful to avoid looping
    /// infinitely.
    pub fn contour_next(&self, idx: SegIdx) -> Option<SegIdx> {
        self.contour_next[idx]
    }

    /// Returns the index of the segment preceding `idx`.
    ///
    /// If `idx` is part of a non-closed path and it is the first segment,
    /// this returns `None`. If `idx` is part of a closed path, this will
    /// always return `Some`, and you might need to be careful to avoid looping
    /// infinitely.
    pub fn contour_prev(&self, idx: SegIdx) -> Option<SegIdx> {
        self.contour_prev[idx]
    }

    /// Does the sweep-line orientation of `idx` agree with its original orientation?
    pub fn positively_oriented(&self, idx: SegIdx) -> bool {
        self.orientation[idx]
    }

    /// Add a (non-closed) polyline to this arena.
    pub fn add_points<P: Into<Point>>(&mut self, ps: impl IntoIterator<Item = P>) {
        let old_len = self.segs.len();

        let ps: Vec<_> = ps.into_iter().map(|p| p.into()).collect();
        if ps.len() <= 1 {
            return;
        }

        for (p, q) in pairs(&ps) {
            let (a, b, orient) = if p < q { (p, q, true) } else { (q, p, false) };
            self.segs.push(Segment::straight(*a, *b));
            self.orientation.push(orient);
            self.split_from_predecessor.push((0.0, 1.0));
            self.input_segs
                .push(kurbo::PathSeg::Line((p.to_kurbo(), q.to_kurbo()).into()));
            self.contour_prev
                .push(Some(SegIdx(self.segs.len().saturating_sub(2))));
            self.contour_next.push(Some(SegIdx(self.segs.len())));
        }

        if old_len < self.segs.len() {
            self.contour_prev[SegIdx(old_len)] = None;
            // unwrap: contour_next has the same length as `segs`, which is
            // non-empty because we checked its length
            *self.contour_next.inner.last_mut().unwrap() = None;
        }

        self.update_enter_exit(old_len);
    }

    /// Add a collection of closed polylines to this arena.
    ///
    /// This can be much faster than calling `add_cycles` repeatedly.
    pub fn add_closed_polylines<P: Into<Point>>(
        &mut self,
        ps: impl IntoIterator<Item = impl IntoIterator<Item = P>>,
    ) {
        let old_len = self.segs.len();
        for p in ps {
            self.add_polyline_without_updating_enter_exit(p);
        }
        self.update_enter_exit(old_len);
    }

    /// Add a closed polyline to this arena.
    pub fn add_closed_polyline<P: Into<Point>>(&mut self, ps: impl IntoIterator<Item = P>) {
        let old_len = self.segs.len();
        self.add_polyline_without_updating_enter_exit(ps);
        self.update_enter_exit(old_len);
    }

    /// Add a Bézier path to this arena.
    ///
    /// The path can contain multiple subpaths, and each of them must be closed.
    pub fn add_bez_path(&mut self, p: &BezPath) -> Result<(), NonClosedPath> {
        let old_len = self.segs.len();
        self.add_path_without_updating_enter_exit(p, true)?;
        self.update_enter_exit(old_len);
        Ok(())
    }

    /// Add a Bézier path to this arena.
    ///
    /// The path can contain multiple subpaths, and each of them may or may not be closed.
    pub fn add_non_closed_bez_path(&mut self, p: &BezPath) -> Result<(), NonClosedPath> {
        let old_len = self.segs.len();
        self.add_path_without_updating_enter_exit(p, false)?;
        self.update_enter_exit(old_len);
        Ok(())
    }

    pub(crate) fn add_path_without_updating_enter_exit(
        &mut self,
        p: &BezPath,
        must_be_closed: bool,
    ) -> Result<(), NonClosedPath> {
        let mut subpaths = Subpaths {
            inner: p.iter().peekable(),
        };
        while let Some(subpath) = subpaths.next() {
            let old_len = self.segs.len();
            for seg in kurbo::segments(subpath) {
                match seg {
                    kurbo::PathSeg::Line(ell) => {
                        let p0: Point = ell.p0.into();
                        let p1: Point = ell.p1.into();
                        let (p0, p1, orient) = if p0 <= p1 {
                            (p0, p1, true)
                        } else {
                            (p1, p0, false)
                        };
                        if p0 != p1 {
                            self.segs.push(Segment::straight(p0, p1));
                            self.orientation.push(orient);
                            self.split_from_predecessor.push((0.0, 1.0));
                            self.input_segs.push(seg);
                            self.contour_prev
                                .push(Some(SegIdx(self.segs.len().saturating_sub(2))));
                            self.contour_next.push(Some(SegIdx(self.segs.len())));
                        }
                    }
                    _ => {
                        let cubic = to_cubic(seg);
                        let cubics = monotonic_pieces(cubic);
                        for monotonic in cubics {
                            let c = monotonic.piece;
                            let (p0, p1, p2, p3, orient) = if (c.p0.y, c.p0.x) <= (c.p3.y, c.p3.x) {
                                (c.p0, c.p1, c.p2, c.p3, true)
                            } else {
                                (c.p3, c.p2, c.p1, c.p0, false)
                            };
                            self.segs.push(Segment::monotonic_cubic(
                                p0.into(),
                                p1.into(),
                                p2.into(),
                                p3.into(),
                            ));
                            self.orientation.push(orient);
                            self.split_from_predecessor
                                .push((monotonic.start_t, monotonic.end_t));
                            self.input_segs.push(seg);
                            self.contour_prev
                                .push(Some(SegIdx(self.segs.len().saturating_sub(2))));
                            self.contour_next.push(Some(SegIdx(self.segs.len())));
                        }
                    }
                }
            }
            if old_len < self.segs.len() {
                let start_idx = SegIdx(old_len);
                let end_idx = SegIdx(self.segs.len() - 1);

                // unwrap: contour_next has the same length as `segs`, which is
                // non-empty because we checked its length
                let start_point = self.oriented_start(start_idx).to_kurbo();
                let end_point = self.oriented_end(end_idx).to_kurbo();
                if start_point == end_point {
                    self.contour_prev[start_idx] = Some(end_idx);
                    self.contour_next[end_idx] = Some(start_idx);
                } else if must_be_closed {
                    return Err(NonClosedPath {
                        start_point,
                        end_point,
                    });
                }
            }
        }
        Ok(())
    }

    fn add_polyline_without_updating_enter_exit<P: Into<Point>>(
        &mut self,
        ps: impl IntoIterator<Item = P>,
    ) {
        let old_len = self.segs.len();

        let ps: Vec<_> = ps.into_iter().map(|p| p.into()).collect();
        if ps.len() <= 1 {
            return;
        }

        for (p, q) in cyclic_pairs(&ps) {
            let (a, b, orient) = if p < q { (p, q, true) } else { (q, p, false) };
            self.segs.push(Segment::straight(*a, *b));
            self.orientation.push(orient);
            self.split_from_predecessor.push((0.0, 1.0));
            self.input_segs
                .push(kurbo::PathSeg::Line((p.to_kurbo(), q.to_kurbo()).into()));
            self.contour_prev
                .push(Some(SegIdx(self.segs.len().saturating_sub(2))));
            self.contour_next.push(Some(SegIdx(self.segs.len())));
        }

        if old_len < self.segs.len() {
            self.contour_prev[SegIdx(old_len)] = Some(SegIdx(self.segs.len() - 1));
            // unwrap: contour_next has the same length as `segs`, which is
            // non-empty because we checked its length
            *self.contour_next.inner.last_mut().unwrap() = Some(SegIdx(old_len));
        }
    }

    /// Construct a segment arena from a single closed polyline.
    pub fn from_closed_polyline<P: Into<Point>>(ps: impl IntoIterator<Item = P>) -> Self {
        let mut ret = Self::default();
        ret.add_closed_polyline(ps);
        ret
    }

    pub(crate) fn update_enter_exit(&mut self, old_len: usize) {
        for idx in old_len..self.len() {
            let seg_idx = SegIdx(idx);
            let seg = &self.segs[seg_idx];

            self.enter.push((seg.start().y, seg_idx));
            if !seg.is_horizontal() {
                self.exit.push((seg.end().y, seg_idx));
            }
        }

        // We sort the enter segments by y position, and then by horizontal
        // start position so that they're fairly likely to get inserted in the
        // sweep-line in order (which makes the indexing fix-ups faster).
        self.enter.sort_by(|(y1, seg1), (y2, seg2)| {
            CheapOrderedFloat::from(*y1)
                .cmp(&CheapOrderedFloat::from(*y2))
                .then_with(|| {
                    CheapOrderedFloat::from(self.segs[*seg1].at_y(*y1))
                        .cmp(&CheapOrderedFloat::from(self.segs[*seg2].at_y(*y1)))
                })
        });
        self.exit.sort_by(|(y1, _), (y2, _)| {
            CheapOrderedFloat::from(*y1).cmp(&CheapOrderedFloat::from(*y2))
        });
    }

    /// All the entrance heights of segments, ordered by height.
    ///
    /// Includes horizontal segments.
    pub fn entrances(&self) -> &[(f64, SegIdx)] {
        &self.enter
    }

    /// All the exit heights of segments, ordered by height.
    ///
    /// Does not include horizontal segments.
    pub fn exits(&self) -> &[(f64, SegIdx)] {
        &self.exit
    }

    /// Checks that we satisfy our internal invariants. For testing only.
    pub fn check_invariants(&self) {
        for (idx, seg) in self.segs.iter() {
            assert!(seg.start() <= seg.end());
            if let Some(next_idx) = self.contour_next(idx) {
                assert_eq!(self.oriented_end(idx), self.oriented_start(next_idx));
                assert_eq!(self.contour_prev(next_idx), Some(idx));
            }
        }
    }
}

// kurbo's PathSeg::to_cubic turns lines into degenerate cubics, which are numerically
// annoying (e.g. they confuse the monotonicity checker). So we roll our own version,
// but eventually we should just handle lines and quadratics without converting them.
fn to_cubic(seg: kurbo::PathSeg) -> kurbo::CubicBez {
    match seg {
        kurbo::PathSeg::Line(kurbo::Line { p0, p1 }) => kurbo::CubicBez {
            p0,
            p1: p0 + (p1 - p0) * (1.0 / 3.0),
            p2: p0 + (p1 - p0) * (2.0 / 3.0),
            p3: p1,
        },
        kurbo::PathSeg::Quad(_) => seg.to_cubic(),
        kurbo::PathSeg::Cubic(c) => c,
    }
}

impl std::ops::Index<SegIdx> for Segments {
    type Output = Segment;

    fn index(&self, index: SegIdx) -> &Self::Output {
        &self.segs[index]
    }
}