line.rs

//! Line breaking
//!
//! To justify, breaks are chosen by looking at the whole paragraph (the Knuth and Plass method).
//! Without justifying, each line takes as much as fits.
//!
//! A space has a width, an amount it can stretch, and an amount it can shrink. The excess or
//! shortfall of a line is shared out in proportion to those amounts.
//! The space between characters of Japanese text is also put in as a space of zero width, so
//! Japanese text is justified in the same way.

use crate::draw::{self, Mark};
use crate::node::Align;


/// The penalty put where the line must not be broken
pub const FORBIDDEN: f64 = 10_000.0;


/// The penalty put where the line must be broken
pub const REQUIRED: f64 = -10_000.0;


/// The stretch of the space that fills the end of a line
pub const FILL: f64 = 100_000.0;


/// The stretch of `\hfill`
///
/// It is much larger than that of the space that fills the end of a paragraph. When both are on
/// the same line, almost all of the leftover width goes to `\hfill`
pub const STRONG_FILL: f64 = 10_000_000.0;


/// Something to put in a line
#[derive(Debug, Clone, PartialEq)]
pub enum Item {
    /// Content with a width. Its marks have their origin at the left end, on the baseline
    Content {mark: Vec<Mark>, width: f64, height: f64, depth: f64},
    /// A space that can stretch and shrink
    Space {width: f64, stretch: f64, shrink: f64},
    /// A place where the line may be broken. width is added to the end of the line when it is
    /// broken here
    Break {penalty: f64, width: f64},
}


/// One typeset line
#[derive(Debug, Clone, PartialEq)]
pub struct Line {
    /// The range of the items in this line
    pub start: usize,
    pub end: usize,
    /// The ratio by which the spaces stretch (positive) or shrink (negative)
    pub ratio: f64,
    /// The width before the spaces stretch
    pub width: f64,
    /// The width available for this line
    pub room: f64,
    /// The height above the baseline
    pub height: f64,
    /// The depth below the baseline
    pub depth: f64,
}


/// The sums of the width, the stretch, and the shrink
#[derive(Debug, Clone, Copy, PartialEq, Default)]
struct Sums {
    width: f64,
    stretch: f64,
    shrink: f64,
}


/// A candidate for a break
#[derive(Debug, Clone, Copy, PartialEq)]
struct Node {
    /// The position of the break
    at: usize,
    /// The number of lines made up to here
    line: usize,
    /// The sums up to the break
    total: Sums,
    demerits: f64,
    ratio: f64,
    previous: Option<usize>,
}


/// Breaks into lines and justifies them
pub fn split(item: &[Item], room: &[f64], tolerance: f64) -> Vec<Line> {
    if item.is_empty() || room.is_empty() {
        return Vec::new();
    }

    let mut node = vec![Node {
        at: 0,
        line: 0,
        total: Sums::default(),
        demerits: 0.0,
        ratio: 0.0,
        previous: None,
    }];
    let mut active = vec![0usize];
    let mut total = Sums::default();

    for at in 0..=item.len() {
        let (penalty, extra) = match item.get(at) {
            Some(Item::Break {penalty, width}) => (*penalty, *width),
            Some(Item::Space {..}) if breakable(item, at) => (0.0, 0.0),
            Some(one) => {
                advance(&mut total, one);

                continue;
            }
            None => (REQUIRED, 0.0),
        };

        if penalty >= FORBIDDEN {
            continue;
        }

        let mut after = total;

        if let Some(one) = item.get(at) {
            advance(&mut after, one);
        }

        consider(&mut node, &mut active, at, penalty, extra, total, after, room, tolerance);

        if let Some(one) = item.get(at) {
            advance(&mut total, one);
        }
    }

    gather(&node, item, room)
}


/// Whether the line may be broken at that position. A space allows a break only when it comes
/// right after content
fn breakable(item: &[Item], at: usize) -> bool {
    at > 0 && matches!(item[at - 1], Item::Content {..})
}


/// Adds one item to the sums
fn advance(total: &mut Sums, item: &Item) {
    match item {
        Item::Content {width, ..} => total.width += width,
        Item::Space {width, stretch, shrink} => {
            total.width += width;
            total.stretch += stretch;
            total.shrink += shrink;
        }
        Item::Break {..} => {}
    }
}


/// For one break, measures each line that would end there
#[allow(clippy::too_many_arguments)]
fn consider(
    node: &mut Vec<Node>,
    active: &mut Vec<usize>,
    at: usize,
    penalty: f64,
    extra: f64,
    total: Sums,
    after: Sums,
    room: &[f64],
    tolerance: f64,
) {
    let mut best: Option<(f64, usize, f64)> = None;
    let mut spare: Option<(f64, usize, f64)> = None;
    let mut remove = Vec::new();

    for (place, index) in active.iter().enumerate() {
        let base = node[*index];
        let natural = total.width - base.total.width + extra;
        let stretch = total.stretch - base.total.stretch;
        let shrink = total.shrink - base.total.shrink;
        let available = room[base.line.min(room.len() - 1)];
        let ratio = fit(natural, stretch, shrink, available);
        let forced = penalty <= REQUIRED;

        if ratio < -1.0 || forced {
            remove.push(place);
        }

        if ratio < -1.0 {
            // The fallback for when nothing fits. Keep the one that overflows the least
            let demerits = base.demerits + 100_000.0 + (natural - available).abs();

            if spare.is_none_or(|(found, _, _)| demerits < found) {
                spare = Some((demerits, *index, -1.0));
            }

            continue;
        }

        if ratio > tolerance && !forced {
            continue;
        }

        let badness = 100.0 * ratio.abs().powi(3);
        let mut demerits = (10.0 + badness).powi(2);

        if penalty > 0.0 && penalty < FORBIDDEN {
            demerits += penalty * penalty;

        } else if penalty > REQUIRED && penalty < 0.0 {
            demerits -= penalty * penalty;
        }

        let demerits = base.demerits + demerits;

        if best.is_none_or(|(found, _, _)| demerits < found) {
            best = Some((demerits, *index, ratio));
        }
    }

    for place in remove.iter().rev() {
        active.remove(*place);
    }

    let chosen = match best {
        Some(found) => Some(found),
        None if active.is_empty() => spare,
        None => None,
    };

    if let Some((demerits, previous, ratio)) = chosen {
        node.push(Node {
            at,
            line: node[previous].line + 1,
            total: after,
            demerits,
            ratio,
            previous: Some(previous),
        });
        active.push(node.len() - 1);
    }
}


/// Converts the excess or shortfall of a line into the ratio for stretching
fn fit(natural: f64, stretch: f64, shrink: f64, available: f64) -> f64 {
    let gap = available - natural;

    if gap.abs() < 1e-9 {
        return 0.0;
    }

    if gap > 0.0 {
        if stretch <= 0.0 {
            return FILL;
        }

        return gap / stretch;
    }

    if shrink <= 0.0 {
        return -FILL;
    }

    gap / shrink
}


/// Builds the lines from the breaks that were reached
fn gather(node: &[Node], item: &[Item], room: &[f64]) -> Vec<Line> {
    let last = match node.iter().skip(1).enumerate().max_by_key(|(_, one)| one.at) {
        Some((index, _)) => index + 1,
        None => return Vec::new(),
    };
    let mut chain = Vec::new();
    let mut current = Some(last);

    while let Some(index) = current {
        chain.push(index);
        current = node[index].previous;
    }

    chain.reverse();
    let mut out = Vec::new();

    for pair in chain.windows(2) {
        let from = node[pair[0]];
        let to = node[pair[1]];
        let start = if from.previous.is_none() {from.at} else {from.at + 1};
        let (height, depth) = size_of(item, start, to.at);
        out.push(Line {
            start,
            end: to.at,
            ratio: to.ratio,
            width: to.total.width - from.total.width,
            room: room[from.line.min(room.len() - 1)],
            height,
            depth,
        });
    }

    out
}


/// Breaks into lines, putting as much as fits on each line. Does not justify
pub fn fill(item: &[Item], room: &[f64]) -> Vec<Line> {
    let mut out: Vec<Line> = Vec::new();
    let mut start = 0;
    let mut at = 0;
    let mut width = 0.0;
    let mut last: Option<(usize, f64)> = None;

    while at < item.len() {
        let available = room[out.len().min(room.len() - 1)];

        match &item[at] {
            Item::Break {penalty, ..} if *penalty <= REQUIRED => {
                out.push(one_line(item, start, at, available));
                start = at + 1;
                width = 0.0;
                last = None;
                at += 1;

                continue;
            }
            Item::Break {penalty, ..} if *penalty < FORBIDDEN => last = Some((at, width)),
            Item::Space {width: size, ..} => {
                if breakable(item, at) {
                    last = Some((at, width));
                }

                width += size;
            }
            Item::Content {width: size, ..} => width += size,
            _ => {}
        }

        if width > available + 0.01 {
            if let Some((place, _)) = last {
                out.push(one_line(item, start, place, available));
                start = place + 1;
                at = place + 1;
                width = 0.0;
                last = None;

                continue;
            }
        }

        at += 1;
    }

    if start < item.len() {
        let available = room[out.len().min(room.len() - 1)];
        out.push(one_line(item, start, item.len(), available));
    }

    out
}


/// Makes a range into one line
fn one_line(item: &[Item], start: usize, end: usize, room: f64) -> Line {
    let mut width = 0.0;

    for one in &item[start..end] {
        match one {
            Item::Content {width: size, ..} => width += size,
            Item::Space {width: size, ..} => width += size,
            Item::Break {..} => {}
        }
    }

    let (height, depth) = size_of(item, start, end);

    Line {start, end, ratio: 0.0, width, room, height, depth}
}


/// The height and depth of the items in a range
fn size_of(item: &[Item], start: usize, end: usize) -> (f64, f64) {
    let mut height: f64 = 0.0;
    let mut depth: f64 = 0.0;

    for one in item.get(start..end).unwrap_or_default() {
        if let Item::Content {height: above, depth: below, ..} = one {
            height = height.max(*above);
            depth = depth.max(*below);
        }
    }

    (height, depth)
}


/// Places one line. x and y are on the baseline at the start of the line
pub fn place(item: &[Item], line: &Line, x: f64, y: f64, align: Align) -> Vec<Mark> {
    let slack = line.room - line.width;
    let offset = match align {
        Align::Center => slack.max(0.0) / 2.0,
        Align::Right => slack.max(0.0),
        _ => 0.0,
    };
    let mut pen = x + offset;
    let mut out = Vec::new();

    for one in item.get(line.start..line.end).unwrap_or_default() {
        match one {
            Item::Content {mark, width, ..} => {
                let mut copy = mark.clone();
                draw::shift(&mut copy, pen, y);
                out.extend(copy);
                pen += width;
            }
            Item::Space {width, stretch, shrink} => {
                let adjust = if align == Align::Justify {
                    if line.ratio >= 0.0 {
                        line.ratio.min(FILL) * stretch
                    } else {
                        line.ratio.max(-1.0) * shrink
                    }
                } else {
                    0.0
                };
                pen += width + adjust;
            }
            Item::Break {..} => {}
        }
    }

    out
}


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

    fn word(width: f64) -> Item {
        Item::Content {mark: Vec::new(), width, height: 7.0, depth: 2.0}
    }

    fn gap() -> Item {
        Item::Space {width: 4.0, stretch: 2.0, shrink: 1.0}
    }

    fn paragraph(count: usize) -> Vec<Item> {
        let mut item = Vec::new();

        for index in 0..count {
            if index > 0 {
                item.push(gap());
            }

            item.push(word(20.0));
        }

        item.push(Item::Break {penalty: FORBIDDEN, width: 0.0});
        item.push(Item::Space {width: 0.0, stretch: FILL, shrink: 0.0});
        item
    }

    #[test]
    fn a_short_paragraph_stays_on_one_line() {
        let item = paragraph(3);
        let line = split(&item, &[500.0], 4.0);
        assert_eq!(line.len(), 1);
        assert_eq!(line[0].start, 0);
    }

    #[test]
    fn a_long_paragraph_is_cut_into_lines() {
        let item = paragraph(20);
        let line = split(&item, &[100.0], 4.0);
        assert!(line.len() >= 5, "{}", line.len());

        for one in &line {
            assert!(one.start < one.end);
        }
    }

    #[test]
    fn every_word_is_used_once() {
        let item = paragraph(12);
        let line = split(&item, &[120.0], 4.0);
        let mut count = 0;

        for one in &line {
            for piece in &item[one.start..one.end] {
                if matches!(piece, Item::Content {..}) {
                    count += 1;
                }
            }
        }

        assert_eq!(count, 12);
    }

    #[test]
    fn filling_also_uses_every_word() {
        let item = paragraph(12);
        let line = fill(&item, &[120.0]);
        let mut count = 0;

        for one in &line {
            for piece in &item[one.start..one.end] {
                if matches!(piece, Item::Content {..}) {
                    count += 1;
                }
            }
        }

        assert_eq!(count, 12);
    }

    #[test]
    fn a_word_wider_than_the_line_still_comes_out() {
        let item = vec![
            word(300.0),
            Item::Break {penalty: FORBIDDEN, width: 0.0},
            Item::Space {width: 0.0, stretch: FILL, shrink: 0.0},
        ];
        let line = split(&item, &[100.0], 4.0);
        assert_eq!(line.len(), 1);
    }
}