use crate::extract::{PageRuns, TextRun};
use super::rows::{self, Row};
use super::Line;
const X0_CLUSTER_TOL: f32 = 4.0;
const SPLIT_BAND: (f32, f32) = (0.33, 0.75);
const MIN_ROWS: usize = 8;
const MIN_CLUSTER_ROW_FRACTION: f32 = 0.35;
const MIN_SEGMENT_ROWS: usize = 6;
const GUTTER_CLEARANCE: f32 = 24.0;
fn detect_candidate(page_rows: &[Row], page_width: f32) -> Option<f32> {
if page_rows.len() < MIN_ROWS {
return None;
}
let mut starts: Vec<(f32, usize)> = Vec::new(); for (i, row) in page_rows.iter().enumerate() {
for run in &row.runs {
starts.push((run.bbox.0, i));
}
}
starts.sort_by(|a, b| a.0.total_cmp(&b.0));
let mut clusters: Vec<(f32, Vec<usize>)> = Vec::new(); for (x, row) in starts {
match clusters.last_mut() {
Some((center, members)) if (x - *center).abs() <= X0_CLUSTER_TOL => {
if members.last() != Some(&row) {
members.push(row);
}
}
_ => clusters.push((x, vec![row])),
}
}
let min_rows = ((page_rows.len() as f32 * MIN_CLUSTER_ROW_FRACTION) as usize).max(6);
let mut candidates: Vec<(f32, usize)> = clusters
.iter()
.filter(|(center, members)| {
*center >= SPLIT_BAND.0 * page_width
&& *center <= SPLIT_BAND.1 * page_width
&& members.len() >= min_rows
})
.map(|(center, members)| (*center, members.len()))
.collect();
if candidates.is_empty() {
return None;
}
let best_count = candidates.iter().map(|c| c.1).max().unwrap_or(0);
candidates.retain(|c| c.1 * 5 >= best_count * 3);
candidates.sort_by(|a, b| a.0.total_cmp(&b.0));
Some(candidates[0].0 - X0_CLUSTER_TOL)
}
fn crosses_gutter(row: &Row, split: f32) -> bool {
row.runs.iter().any(|run| {
let x0 = run.bbox.0;
if x0 < split - GUTTER_CLEARANCE {
x0 + rows::width_est(run) > split
} else {
x0 < split }
})
}
struct Segment {
start: usize,
end: usize, columnar: bool,
}
fn segment(page_rows: &[Row], split: f32) -> Option<Vec<Segment>> {
let mut classes: Vec<bool> = page_rows
.iter()
.map(|row| !crosses_gutter(row, split))
.collect();
let mut i = 0;
while i < classes.len() {
if !classes[i] {
let start = i;
while i < classes.len() && !classes[i] {
i += 1;
}
let sandwiched = start > 0 && i < classes.len();
if sandwiched && i - start <= 2 {
for class in &mut classes[start..i] {
*class = true;
}
}
} else {
i += 1;
}
}
let mut segments: Vec<Segment> = Vec::new();
for (i, &columnar) in classes.iter().enumerate() {
match segments.last_mut() {
Some(seg) if seg.columnar == columnar => seg.end = i + 1,
_ => segments.push(Segment {
start: i,
end: i + 1,
columnar,
}),
}
}
for seg in &mut segments {
if seg.columnar && seg.end - seg.start < MIN_SEGMENT_ROWS {
seg.columnar = false;
}
}
segments.iter().any(|s| s.columnar).then_some(segments)
}
pub fn lines_in_reading_order(
page_rows: Vec<Row>,
page: &PageRuns,
page_index: usize,
) -> Vec<Line> {
let split = detect_candidate(&page_rows, page.width);
let segments = split.and_then(|s| segment(&page_rows, s));
let mut placed: Vec<(Line, f32)> = Vec::new();
let page_left = page_rows
.iter()
.flat_map(|r| &r.runs)
.map(|r| r.bbox.0)
.fold(f32::INFINITY, f32::min);
let page_right = (page.width - page_left).max(page_left + 1.0);
match (split, segments) {
(Some(split_x), Some(segments)) => {
for seg in segments {
let seg_rows = &page_rows[seg.start..seg.end];
if seg.columnar {
for column in 0..2u8 {
for row in seg_rows {
let runs: Vec<TextRun> = row
.runs
.iter()
.filter(|r| (r.bbox.0 < split_x) == (column == 0))
.cloned()
.collect();
if let Some(line) = make_line(row.baseline, &runs, column, page_index) {
let right = if column == 0 { split_x } else { page_right };
placed.push((line, right));
}
}
}
} else {
for row in seg_rows {
if let Some(line) = make_line(row.baseline, &row.runs, 0, page_index) {
placed.push((line, page_right));
}
}
}
}
}
_ => {
for row in &page_rows {
if let Some(line) = make_line(row.baseline, &row.runs, 0, page_index) {
placed.push((line, page_right));
}
}
}
}
let x0s: Vec<f32> = placed.iter().map(|(l, _)| l.x0).collect();
let popular = |x0: f32| {
x0s.iter()
.filter(|&&x| (x - x0).abs() <= X0_CLUSTER_TOL)
.count()
>= 3
};
let mut col_lefts: Vec<f32> = Vec::new();
for (line, right) in &placed {
let left = placed
.iter()
.filter(|(l, r)| l.column == line.column && r == right)
.map(|(l, _)| l.x0)
.fold(f32::INFINITY, f32::min);
col_lefts.push(left);
}
let mut out = Vec::with_capacity(placed.len());
for (i, (mut line, right)) in placed.into_iter().enumerate() {
line.centered = is_centered(&line, col_lefts[i], right) && !popular(line.x0);
out.push(line);
}
out
}
fn make_line(baseline: f32, runs: &[TextRun], column: u8, page_index: usize) -> Option<Line> {
if runs.is_empty() {
return None;
}
let text = rows::join_runs(runs);
if text.trim().is_empty() {
return None;
}
let x0 = runs[0].bbox.0;
let total_chars: usize = runs.iter().map(|r| r.text.chars().count()).sum();
let mut best = (0usize, runs[0].font_size);
for run in runs {
let same: usize = runs
.iter()
.filter(|r| (r.font_size - run.font_size).abs() <= 0.25)
.map(|r| r.text.chars().count())
.sum();
if same > best.0 {
best = (same, run.font_size);
}
}
let bold_chars: usize = runs
.iter()
.filter(|r| r.bold)
.map(|r| r.text.chars().count())
.sum();
Some(Line {
text,
x0,
baseline,
indent: 0,
font_size: best.1,
bold: total_chars > 0 && bold_chars * 2 > total_chars,
centered: false,
column,
pages: vec![page_index],
})
}
fn is_centered(line: &Line, col_left: f32, col_right: f32) -> bool {
let col_width = col_right - col_left;
if col_width <= 0.0 || line.text.trim().len() < 2 {
return false;
}
let width = rows::advance_est(line.text.trim_end(), line.font_size);
if width >= 0.75 * col_width {
return false;
}
if line.x0 - col_left < 0.08 * col_width {
return false; }
let line_mid = line.x0 + width / 2.0;
let col_mid = (col_left + col_right) / 2.0;
(line_mid - col_mid).abs() <= (0.045 * col_width).max(6.0)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::layout::testutil::{page, run};
use crate::layout::{reconstruct, Layout};
fn two_column_page() -> crate::extract::PageRuns {
let mut runs = Vec::new();
for i in 0..12 {
let y = 700.0 - i as f32 * 11.0;
runs.push(run(
&format!("left column line {i} of body"),
80.0,
y,
10.0,
0,
));
runs.push(run(
&format!("right column line {i} of body"),
313.0,
y,
10.0,
0,
));
}
page(runs)
}
fn full_text(layout: &Layout) -> String {
layout.text()
}
#[test]
fn two_column_page_reads_left_column_first() {
let layout = reconstruct(&[two_column_page()]);
let text = full_text(&layout);
let left_last = text.find("left column line 11").expect("left col present");
let right_first = text.find("right column line 0").expect("right col present");
assert!(
left_last < right_first,
"left column must be read before the right column:\n{text}"
);
}
#[test]
fn full_width_lines_veto_a_false_split() {
let mut runs = Vec::new();
for i in 0..12 {
let y = 700.0 - i as f32 * 12.0;
let left = run(
"a full width single column line of text that runs on",
72.0,
y,
10.0,
0,
);
let right_x = 72.0 + rows::width_est(&left) + 3.0;
runs.push(left);
runs.push(run(
"and keeps going to the right margin",
right_x,
y,
10.0,
0,
));
}
let layout = reconstruct(&[page(runs)]);
assert_eq!(layout.blocks.iter().flat_map(|b| &b.lines).count(), 12);
let first = &layout.blocks[0].lines[0];
assert!(
first.text.contains("that runs on and keeps going"),
"row fragments must join into one line, got {:?}",
first.text
);
}
#[test]
fn mixed_page_keeps_full_width_band_above_columns() {
let mut runs = Vec::new();
for i in 0..7 {
runs.push(run(
&format!("full width oath sentence number {i} spanning the whole page width here"),
95.0,
700.0 - i as f32 * 11.0,
10.0,
0,
));
}
for i in 0..8 {
let y = 600.0 - i as f32 * 11.0;
runs.push(run(&format!("narrow left {i} text"), 84.0, y, 10.0, 0));
runs.push(run(&format!("narrow right {i} text"), 317.0, y, 10.0, 0));
}
let layout = reconstruct(&[page(runs)]);
let text = full_text(&layout);
let oath_end = text.find("oath sentence number 6").expect("band present");
let left_start = text.find("narrow left 0").expect("left col present");
let left_end = text.find("narrow left 7").expect("left col present");
let right_start = text.find("narrow right 0").expect("right col present");
assert!(
oath_end < left_start,
"band reads before the columns:\n{text}"
);
assert!(left_end < right_start, "left column before right:\n{text}");
assert!(
!text.contains("narrow left 0 text narrow right 0"),
"columns must not interleave:\n{text}"
);
}
#[test]
fn short_pages_are_never_split() {
let runs = vec![
run("left", 80.0, 700.0, 10.0, 0),
run("right", 313.0, 700.0, 10.0, 0),
];
let rows_v = rows::assemble(&page(runs), 0);
assert_eq!(detect_candidate(&rows_v, 612.0), None);
}
#[test]
fn tab_layout_near_left_margin_is_not_a_column() {
let mut runs = Vec::new();
for i in 0..12 {
let y = 700.0 - i as f32 * 12.0;
runs.push(run(&format!("§ 10{i}."), 72.0, y, 11.0, 0));
runs.push(run("Some Section Heading Here.", 136.8, y, 11.0, 0));
}
let rows_v = rows::assemble(&page(runs), 0);
assert_eq!(detect_candidate(&rows_v, 612.0), None);
}
#[test]
fn centered_heading_is_flagged() {
let mut runs = vec![run("PART 2. OFFICE OF THE GOVERNOR", 216.6, 700.0, 10.0, 0)];
for i in 1..5 {
runs.push(run(
"body text line that is long enough to reach toward the right margin",
126.0,
700.0 - i as f32 * 12.0,
10.0,
0,
));
}
let layout = reconstruct(&[page(runs)]);
let lines: Vec<&Line> = layout.blocks.iter().flat_map(|b| &b.lines).collect();
assert!(lines[0].centered, "heading should be centered");
assert!(!lines[1].centered, "body must not be centered");
}
}