page.rs

//! Paginates the vertical list
//!
//! Blocks are placed one after another from the top. When one no longer fits, the page is broken
//! at the break before it that costs least. A footnote goes on the same page as the line it
//! belongs to, and the height available for the body text decreases by that amount.
//!
//! A float goes at the top of the first page where it fits. Only when `[h]` is written and it
//! fits in place is it put there. [`Style::float_fraction`] sets the fraction of a page that
//! floats may use, and a float larger than that goes on a page by itself.

use crate::draw::{self, Letter, Mark, Page};
use crate::font::{self, Library};
use crate::layout::{Block, Note};
use crate::line;
use crate::number::Numbering;
use crate::pdf::Destination;
use crate::style::{self, Style};


/// The cost of the empty space at the bottom of a page, per line squared
const BLANK_COST: f64 = 100.0;


/// A float that has not been placed yet
#[derive(Debug, Clone)]
struct Waiting {
    mark: Vec<Mark>,
    height: f64,
    anchor: Vec<String>,
}


/// A place where the page may be broken, and the lengths of placed, note, and waiting there
#[derive(Debug, Clone, Copy)]
struct Candidate {
    cost: f64,
    at: usize,
    placed: usize,
    note: usize,
    waiting: usize,
}


/// Paginates the vertical list
pub fn paginate(
    block: &[Block],
    library: &Library,
    style: &Style,
    numbering: &mut Numbering,
) -> (Vec<Page>, Vec<Destination>) {
    let goal = style::body_height(style);
    let mut out: Vec<Page> = Vec::new();
    let mut destination = Vec::new();
    let mut waiting: Vec<Waiting> = Vec::new();
    let mut at = 0;

    while at < block.len() || !waiting.is_empty() {
        let number = out.len();
        let (top, float_height) = take_floats(&mut waiting, style, goal);
        let room = goal - float_height;
        // If the floats alone fill the page, no body text goes on this page
        let (placed, note, end) = if room < style.leading {
            (Vec::new(), Vec::new(), at)
        } else {
            take_body(block, at, room, style, &mut waiting)
        };
        let mut mark = Vec::new();
        let mut y = 0.0;

        for one in &top {
            let mut copy = one.mark.clone();
            draw::shift(&mut copy, style.margin_left, style.margin_top + y);
            mark.extend(copy);
            remember(numbering, &one.anchor, number + 1);
            y += one.height + style.float_gap;
        }

        for (index, offset) in &placed {
            let at_y = style.margin_top + float_height + offset;

            match &block[*index] {
                Block::Content {mark: inner, anchor, heading, ..} => {
                    let mut copy = inner.clone();
                    draw::shift(&mut copy, style.margin_left, at_y);
                    mark.extend(copy);
                    remember(numbering, anchor, number + 1);

                    if let Some((level, title)) = heading {
                        destination.push(Destination {
                            level: *level,
                            title: title.clone(),
                            page: number,
                        });
                    }
                }
                Block::Float {mark: inner, anchor, ..} => {
                    let mut copy = inner.clone();
                    draw::shift(&mut copy, style.margin_left, at_y);
                    mark.extend(copy);
                    remember(numbering, anchor, number + 1);
                }
                _ => {}
            }
        }

        if !note.is_empty() {
            place_notes(&mut mark, &note, style, goal);
        }

        if style.page_number {
            mark.extend(page_number(library, style, number + 1));
        }

        out.push(Page {
            mark,
            width: style.page_width,
            height: style.page_height,
        });

        at = if end == at && top.is_empty() && at < block.len() {
            at + 1
        } else {
            end
        };
    }

    if out.is_empty() {
        out.push(Page {
            mark: Vec::new(),
            width: style.page_width,
            height: style.page_height,
        });
    }

    (out, destination)
}


/// Ties the names to the page number
fn remember(numbering: &mut Numbering, anchor: &[String], page: usize) {
    for name in anchor {
        numbering.page.insert(name.clone(), page);
    }
}


/// Takes the floats to put at the top of this page
fn take_floats(waiting: &mut Vec<Waiting>, style: &Style, goal: f64) -> (Vec<Waiting>, f64) {
    let budget = goal * style.float_fraction;
    let mut top = Vec::new();
    let mut height = 0.0;

    while !waiting.is_empty() {
        let want = waiting[0].height + style.float_gap;

        if top.is_empty() && want > budget {
            // Takes the whole page
            height += want.max(goal);
            top.push(waiting.remove(0));

            break;
        }

        if height + want > budget {
            break;
        }

        height += want;
        top.push(waiting.remove(0));
    }

    (top, height)
}


/// Decides which body text goes on this page
fn take_body(
    block: &[Block],
    from: usize,
    room: f64,
    style: &Style,
    waiting: &mut Vec<Waiting>,
) -> (Vec<(usize, f64)>, Vec<Note>, usize) {
    let mut placed: Vec<(usize, f64)> = Vec::new();
    let mut note: Vec<Note> = Vec::new();
    let mut used = 0.0;
    let mut bottom = 0.0;
    let mut best: Option<Candidate> = None;
    let mut at = from;
    let mut forced = false;

    while at < block.len() {
        match &block[at] {
            Block::NewPage => {
                at += 1;
                forced = true;

                break;
            }
            Block::Break {penalty} => {
                if *penalty < line::FORBIDDEN && !placed.is_empty() {
                    let blank = (room - bottom - note_area(&note, style)).max(0.0)
                        / style.leading.max(1.0);
                    let cost = *penalty + BLANK_COST * blank * blank;

                    if best.is_none_or(|found| cost <= found.cost) {
                        best = Some(Candidate {
                            cost,
                            at,
                            placed: placed.len(),
                            note: note.len(),
                            waiting: waiting.len(),
                        });
                    }
                }

                at += 1;
            }
            Block::Space {height, ..} => {
                if !placed.is_empty() {
                    used += height;
                }

                at += 1;
            }
            Block::Float {placement, mark: inner, height, anchor} => {
                let here = placement.contains('h') || placement.contains('H');
                // Even when it is put in place, leave a space between it and the body text
                let lead = if placed.is_empty() {0.0} else {style.float_gap};
                let want = lead + height + style.float_gap + note_area(&note, style);

                if here && used + want <= room {
                    used += lead;
                    placed.push((at, used));
                    used += height;
                    bottom = used;
                    used += style.float_gap;

                } else {
                    waiting.push(Waiting {
                        mark: inner.clone(),
                        height: *height,
                        anchor: anchor.clone(),
                    });
                }

                at += 1;
            }
            Block::Content {height, note: mine, ..} => {
                let mut after = note.clone();
                after.extend(mine.iter().cloned());
                let total = used + height + note_area(&after, style);

                if total > room && !placed.is_empty() {
                    break;
                }

                placed.push((at, used));
                used += height;
                bottom = used;
                note = after;
                at += 1;
            }
        }
    }

    if at >= block.len() || forced {
        return (placed, note, at);
    }

    match best {
        Some(found) => {
            placed.truncate(found.placed);
            note.truncate(found.note);
            // Floats after the break are met again on the next page
            waiting.truncate(found.waiting);

            (placed, note, found.at + 1)
        }
        None => (placed, note, at),
    }
}


/// The height that the footnote area takes
fn note_area(note: &[Note], style: &Style) -> f64 {
    if note.is_empty() {
        return 0.0;
    }

    style.footnote_gap + note.iter().map(|one| one.height).sum::<f64>()
}


/// Puts the footnotes at the bottom of the page
fn place_notes(mark: &mut Vec<Mark>, note: &[Note], style: &Style, goal: f64) {
    let total: f64 = note.iter().map(|one| one.height).sum();
    let base = style.margin_top + goal - total;
    mark.push(Mark::Rule {
        x: style.margin_left,
        y: base - style.footnote_gap * 0.6,
        width: style.footnote_rule,
        height: style.rule_width,
    });
    let mut y = base;

    for one in note {
        let mut copy = one.mark.clone();
        draw::shift(&mut copy, style.margin_left, y);
        mark.extend(copy);
        y += one.height;
    }
}


/// Places the page number
fn page_number(library: &Library, style: &Style, number: usize) -> Vec<Mark> {
    let index = library.role.roman;
    let face = &library.face[index];
    let size = style.size * 0.9;
    let mut letter = Vec::new();
    let mut width = 0.0;

    for character in number.to_string().chars() {
        if let Some(glyph) = font::glyph(face, character) {
            width += font::advance(face, glyph) * size;
            letter.push(Letter {glyph, text: character.to_string()});
        }
    }

    if letter.is_empty() {
        return Vec::new();
    }

    vec![Mark::Text {
        face: index,
        size,
        stretch: 1.0,
        x: style.page_width / 2.0 - width / 2.0,
        y: style.page_height - style.margin_bottom * 0.45,
        letter,
    }]
}


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

    fn text_line() -> Block {
        Block::Content {
            mark: Vec::new(),
            height: 17.0,
            baseline: 13.0,
            note: Vec::new(),
            anchor: Vec::new(),
            heading: None,
        }
    }

    #[test]
    fn a_float_too_large_for_the_top_takes_a_page_by_itself() {
        let style = Style::default();
        let goal = style::body_height(&style);
        let mut waiting = vec![Waiting {mark: Vec::new(), height: goal * 0.8, anchor: Vec::new()}];
        let (top, height) = take_floats(&mut waiting, &style, goal);
        assert_eq!(top.len(), 1);
        assert!(waiting.is_empty());
        assert!(height >= goal);
    }

    #[test]
    fn the_page_is_broken_between_paragraphs() {
        let style = Style::default();
        let block = vec![
            text_line(),
            Block::Break {penalty: style.first_line_penalty},
            text_line(),
            Block::Break {penalty: 0.0},
            text_line(),
            Block::Break {penalty: style.first_line_penalty},
            text_line(),
            Block::Break {penalty: 0.0},
        ];
        let (placed, _, end) = take_body(&block, 0, 51.0, &style, &mut Vec::new());
        assert_eq!(placed.len(), 2);
        assert_eq!(end, 4);
    }

    #[test]
    fn the_last_line_of_a_paragraph_does_not_go_on_alone() {
        let style = Style::default();
        let block = vec![
            text_line(),
            Block::Break {penalty: style.first_line_penalty},
            text_line(),
            Block::Break {penalty: 0.0},
            text_line(),
            Block::Break {penalty: style.last_line_penalty},
            text_line(),
            Block::Break {penalty: 0.0},
        ];
        let (placed, _, end) = take_body(&block, 0, 51.0, &style, &mut Vec::new());
        assert_eq!(placed.len(), 2);
        assert_eq!(end, 4);
    }

    #[test]
    fn a_float_after_the_break_waits_only_once() {
        let style = Style::default();
        let block = vec![
            text_line(),
            Block::Break {penalty: 0.0},
            Block::Float {
                placement: "tbp".to_string(),
                mark: Vec::new(),
                height: 100.0,
                anchor: Vec::new(),
            },
            text_line(),
            Block::Break {penalty: style.first_line_penalty},
            text_line(),
        ];
        let mut waiting = Vec::new();
        let (placed, _, end) = take_body(&block, 0, 34.0, &style, &mut waiting);
        assert_eq!(placed.len(), 1);
        assert_eq!(end, 2);
        assert!(waiting.is_empty());
    }
}