line.rs

//! 行分割
//!
//! 両端を揃えるときは、段落全体を見て切れ目を選ぶ（Knuth と Plass のやり方）。
//! 揃えないときは、収まるかぎり詰めていく。
//!
//! 空きは幅と、伸ばせる量と、詰められる量を持つ。行の過不足はその割合で配る。
//! 和文の字間も 0 幅の空きとして置いてあるので、同じ仕組みで両端が揃う。

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


/// 切ってはいけないところに置く罰点
pub const FORBIDDEN: f64 = 10_000.0;


/// かならず切るところに置く罰点
pub const REQUIRED: f64 = -10_000.0;


/// 行末を埋める空きの伸び
pub const FILL: f64 = 100_000.0;


/// `\hfill` の伸び
///
/// 段落の終わりを埋める空きよりずっと大きくする。両方が同じ行にあるとき、
/// 余りはほとんど `\hfill` のほうへ行く
pub const STRONG_FILL: f64 = 10_000_000.0;


/// 行に並べるもの
#[derive(Debug, Clone, PartialEq)]
pub enum Item {
    /// 幅を持つ中身。置くものは左端とベースラインを原点にして持つ
    Content {mark: Vec<Mark>, width: f64, height: f64, depth: f64},
    /// 伸び縮みする空き
    Space {width: f64, stretch: f64, shrink: f64},
    /// 切ってよい場所。width は切ったときに行末へ足す幅
    Break {penalty: f64, width: f64},
}


/// 組み上がった 1 行
#[derive(Debug, Clone, PartialEq)]
pub struct Line {
    /// この行に入るものの範囲
    pub start: usize,
    pub end: usize,
    /// 空きを伸ばす（正）か詰める（負）割合
    pub ratio: f64,
    /// 空きを伸ばす前の幅
    pub width: f64,
    /// この行に使える幅
    pub room: f64,
    /// ベースラインから上
    pub height: f64,
    /// ベースラインから下
    pub depth: f64,
}


/// 幅と伸び縮みの合計
#[derive(Debug, Clone, Copy, PartialEq, Default)]
struct Sums {
    width: f64,
    stretch: f64,
    shrink: f64,
}


/// 切れ目の候補
#[derive(Debug, Clone, Copy, PartialEq)]
struct Node {
    /// 切った位置
    at: usize,
    /// ここまでにできた行の数
    line: usize,
    /// 切ったところまでの合計
    total: Sums,
    demerits: f64,
    ratio: f64,
    previous: Option<usize>,
}


/// 両端を揃えて行に切る
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)
}


/// その位置で切ってよいか。空きは、直前が中身のときだけ切れる
fn breakable(item: &[Item], at: usize) -> bool {
    at > 0 && matches!(item[at - 1], Item::Content {..})
}


/// 合計を進める
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 {..} => {}
    }
}


/// 1 つの切れ目について、そこまでの行を測る
#[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 {
            // どこにも入らないときの逃げ道。いちばん溢れの少ないものを覚えておく
            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);
    }
}


/// 行の過不足を、伸ばす割合に直す
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
}


/// たどり着いた切れ目から行を組み立てる
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
}


/// 収まるかぎり詰めて行に切る。両端は揃えない
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
}


/// 範囲を 1 行にする
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}
}


/// 範囲に入るものの高さと深さ
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)
}


/// 1 行を置く。x と y は行頭のベースライン
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);
    }
}