Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_austenite/src/hyphenate.rs

3.8 KiB, 1 run

created by r1870400018:35948, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! Liang's pattern hyphenation, the algorithm behind TeX's `\patterns`.
2//!
3//! A word is padded with boundary dots (`.word.`), every substring is looked up against the pattern
4//! set, and the odd/even inter-letter values combine by maximum. An odd value at a gap that clears
5//! the left and right minima is a legal hyphenation point. The patterns are Liang's US-English set,
6//! embedded as a crate asset (see `patterns/`); the breaker turns each returned point into a flagged
7//! discretionary.
8
9use oxedyne_fe2o3_core::prelude::*;
10
11use std::collections::HashMap;
12
13const PATTERNS: &str = include_str!("../patterns/hyph-en-us.txt");
14
15/// A hyphenator: the pattern set plus the two minima that keep stubs off the line ends.
16pub struct Hyphenator {
17 left_min: usize, // letters that must precede the first break (TeX lefthyphenmin)
18 right_min: usize, // letters that must follow the last break (TeX righthyphenmin)
19 patterns: HashMap<String, Vec<u8>>, // letters-and-dots key -> inter-letter values
20}
21
22impl Hyphenator {
23 /// Builds a hyphenator from pattern text: one pattern per line, `%` comments and blanks ignored.
24 pub fn from_patterns(text: &str, left_min: usize, right_min: usize) -> Self {
25 let mut patterns = HashMap::new();
26 for line in text.lines() {
27 let line = line.trim();
28 if line.is_empty() || line.starts_with('%') {
29 continue;
30 }
31 let (key, vals) = parse_pattern(line);
32 patterns.insert(key, vals);
33 }
34 Self { left_min, right_min, patterns }
35 }
36
37 /// The US-English hyphenator over the embedded Liang patterns, with the usual 2/3 minima.
38 pub fn en_us() -> Self {
39 Self::from_patterns(PATTERNS, 2, 3)
40 }
41
42 /// The char offsets within `word` at which a discretionary hyphen is legal -- each the count of
43 /// characters to the left of the break, honouring the minima. A run that is not all ASCII letters,
44 /// or too short to break, yields none.
45 pub fn hyphenate(&self, word: &str) -> Vec<usize> {
46 let lower: Vec<char> = word.chars().flat_map(|c| c.to_lowercase()).collect();
47 if lower.len() < self.left_min + self.right_min || lower.len() != word.chars().count() {
48 // Case folding that changes the char count (e.g. the German eszett) breaks the offset
49 // mapping back to the original word; refuse rather than mis-split.
50 return Vec::new();
51 }
52 if !lower.iter().all(|c| c.is_ascii_lowercase()) {
53 return Vec::new();
54 }
55
56 // Pad with boundary dots and score every gap by the maximum over all matching substrings.
57 let mut s: Vec<char> = Vec::with_capacity(lower.len() + 2);
58 s.push('.');
59 s.extend_from_slice(&lower);
60 s.push('.');
61 let n = s.len();
62 let mut val = vec![0u8; n + 1];
63 for i in 0..n {
64 let mut key = String::new();
65 for j in (i + 1)..=n {
66 key.push(s[j - 1]);
67 if let Some(vs) = self.patterns.get(&key) {
68 for (g, &v) in vs.iter().enumerate() {
69 if val[i + g] < v {
70 val[i + g] = v;
71 }
72 }
73 }
74 }
75 }
76
77 // A break after original char `c` (zero-based) reads the gap at `val[c + 2]`: one for the
78 // leading dot, one because the gap sits after the char.
79 let no = lower.len();
80 let mut pts = Vec::new();
81 for c in 0..no {
82 let before = c + 1;
83 let after = no - before;
84 if val[c + 2] % 2 == 1 && before >= self.left_min && after >= self.right_min {
85 pts.push(before);
86 }
87 }
88 pts
89 }
90}
91
92/// Splits a pattern into its letters-and-dots key and the value at each gap. A digit sets the value
93/// of the gap it precedes; a missing digit leaves it zero. The value vector is one longer than the
94/// key: a score before the first letter through to after the last.
95fn parse_pattern(p: &str) -> (String, Vec<u8>) {
96 let mut key = String::new();
97 let mut vals = vec![0u8];
98 let mut gap = 0usize; // the gap being scored == key.len()
99 for c in p.chars() {
100 match c.to_digit(10) {
101 Some(d) => vals[gap] = d as u8,
102 None => {
103 key.push(c);
104 gap += 1;
105 vals.push(0);
106 },
107 }
108 }
109 (key, vals)
110}