const testString =
"What is the shortest way to travel from Rotterdam to Groningen, in general: from given city to given city. It is the algorithm for the shortest path, which I designed in about twenty minutes. One morning I was shopping in Amsterdam with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. As I said, it was a twenty-minute invention. In fact, it was published in ’59, three years later. The publication is still readable, it is, in fact, quite nice. One of the reasons that it is so nice was that I designed it without pencil and paper. I learned later that one of the advantages of designing without pencil and paper is that you are almost forced to avoid all avoidable complexities. Eventually, that algorithm became to my great amazement, one of the cornerstones of my fame.";
const Alinea = {
helpers: {
hyphenCost: 75,
runtCost: 50,
maxBadness: 1e9,
endsInHyphen: segment =>
!!(segment.needsHyphen || segment.text.match(/-$/))
},
settings: {
locale: "en-GB"
},
hyphen: {
cache: {},
dict: {},
patternToPoints: pattern => {
let points = [];
pattern.split("").forEach(glyph => {
if (glyph.match(/[0-9]/)) {
points.pop();
points.push(+glyph);
} else {
points.push(0);
}
});
return points;
},
mergeBreakpoints: (wordPoints, patternPoints, endIdx) => {
const startIdx = endIdx - patternPoints.length;
for (idx = 0; idx < patternPoints.length; idx++) {
wordPoints[startIdx + idx] = Math.max(
wordPoints[startIdx + idx],
patternPoints[idx]
);
}
},
hyphenateWord: (word, patterns) => {
if (word.length < 5 || !patterns || word.includes("\u00AD")) {
return word;
}
const baseWord = word.toLocaleLowerCase(Alinea.settings.locale);
if (word in Alinea.hyphen.cache) {
return Alinea.hyphen.cache[word];
}
let breakpoints = new Array(word.length).fill(0);
for (letter = 2; letter <= word.length; letter++) {
const fragment = baseWord.slice(0, letter);
let matches = patterns.general.filter(pattern =>
fragment.match(pattern[0])
);
if (letter == word.length) {
matches.push(
...patterns.final.filter(pattern =>
fragment.match(pattern[0])
)
);
}
for (const matchedPattern of matches) {
Alinea.hyphen.mergeBreakpoints(
breakpoints,
Alinea.hyphen.patternToPoints(matchedPattern[1]),
letter
);
}
}
breakpoints[0] = 0;
breakpoints[breakpoints.length - 1] = 0;
breakpoints[breakpoints.length - 2] = 0;
const breakpointIndices = breakpoints
.map((el, idx) => (el % 2 ? idx + 1 : 0))
.filter(el => el != 0);
let hyphenated = [];
for (idx = 0; idx <= breakpointIndices.length; idx++) {
if (idx == 0) {
hyphenated.push(word.slice(0, breakpointIndices[idx]));
} else if (idx == breakpointIndices.length) {
hyphenated.push(word.slice(breakpointIndices[idx - 1]));
} else {
hyphenated.push(
word.slice(
breakpointIndices[idx - 1],
breakpointIndices[idx]
)
);
}
}
hyphenated = hyphenated.join("\u00AD");
Alinea.hyphen.cache[word] = hyphenated;
return hyphenated;
}
},
measure: {
canvas: new OffscreenCanvas(1, 1),
ctx: null,
widthCache: {},
width: (input, font) => {
Alinea.measure.ctx.font = font;
const measuredWidth = Alinea.measure.ctx.measureText(input).width;
if (!(font in Alinea.measure.widthCache)) {
Alinea.measure.widthCache[font] = {};
}
Alinea.measure.widthCache[font][input] = measuredWidth;
return measuredWidth;
},
getElementFont: el => {
const styles = window.getComputedStyle(el);
const fontSize = styles.getPropertyValue("font-size");
const fontFamily = styles.getPropertyValue("font-family");
const fontStyle = styles.getPropertyValue("font-style");
const fontWeight = styles.getPropertyValue("font-weight");
return `${fontStyle} ${fontWeight} ${fontSize} ${fontFamily}`;
}
},
segmentText: (string, font) => {
const segmenter = new Intl.Segmenter(Alinea.settings.locale, {
granularity: "word"
});
const segmentedString = [...segmenter.segment(string)]
.map(word =>
Alinea.hyphen.hyphenateWord(
word.segment,
Alinea.hyphen.dict[Alinea.settings.locale]
)
)
.flatMap(word =>
word.includes("\u00AD")
? word.split("\u00AD").map((el, idx, arr) => ({
segment: el,
needsHyphen: idx + 1 < arr.length,
hyphenSplit: [
arr.slice(0, idx + 1).join("").length,
arr.slice(idx + 1).join("").length
]
}))
: { segment: word }
);
let segments = [];
for (const el of segmentedString) {
const isGlue = !!el.segment.match(/^\s+$/u);
if (segments.length) {
if (el.segment == "\u00AD") {
segments.at(-1).needsHyphen = true;
continue;
}
if (
segments.at(-1).type == "box" &&
!(
isGlue ||
Alinea.helpers.endsInHyphen(segments.at(-1)) ||
segments.at(-1).text.match(/–—\//) ||
el.segment.match(/–—/)
)
) {
segments.at(-1).text = segments
.at(-1)
.text.concat(el.segment);
segments.at(-1).width += Alinea.measure.width(
el.segment,
font
);
continue;
}
}
const measuredWidth = Alinea.measure.width(el.segment, font);
segments.push({
text: el.segment,
type: isGlue ? "glue" : "box",
width: Alinea.measure.width(el.segment, font),
widthPlusHyphen: Alinea.measure.width(`${el.segment}-`, font),
stretch: isGlue ? measuredWidth * 0.5 : 0,
shrink: isGlue ? measuredWidth * 0.333 : 0,
needsHyphen: el.needsHyphen ?? false,
hyphenSplit: el.hyphenSplit ?? null,
log: {
bestCost: -1,
tail: null
}
});
}
segments.push({
text: "",
type: "glue",
width: 0,
stretch: Infinity,
shrink: 0,
needsHyphen: false,
log: {
bestCost: 0,
tail: null
}
});
return segments;
},
adjustmentRatio: (line, goalWidth) => {
if (line.length == 0) return 1e9;
if (line.at(-1).type == "glue" && line.at(-1).stretch != Infinity) {
line = line.slice(0, -1);
}
if (line.length == 0) return 1e9;
let lineWidth = line.map(el => el.width).reduce((a, b) => a + b);
const lineStretch = line.map(el => el.stretch).reduce((a, b) => a + b);
const lineShrink = line.map(el => el.shrink).reduce((a, b) => a + b);
if (line.at(-1).needsHyphen) {
lineWidth =
lineWidth - line.at(-1).width + line.at(-1).widthPlusHyphen;
}
if (lineWidth == goalWidth) return 0;
if (lineWidth < goalWidth) return (lineWidth - goalWidth) / lineStretch;
return (lineWidth - goalWidth) / lineShrink;
},
lineCost: (line, goalWidth) => {
if (line[0].type == "glue") {
line = line.slice(1);
}
const ratio = Alinea.adjustmentRatio(line, goalWidth);
const badness =
ratio > 1 ? Alinea.helpers.maxBadness : 100 * Math.abs(ratio) ** 3;
let penalty = 0;
if (
line.filter(el => {
el.type == "glue";
}).length == 1 &&
line.at(-1).type == "glue"
) {
penalty += Alinea.helpers.runtCost;
}
if (line.length && Alinea.helpers.endsInHyphen(line.at(-1))) {
if (line.at(-1).needsHyphen) {
let worstHyphenSplit = Math.min(
line.at(-1).hyphenSplit[0] * 1.5,
line.at(-1).hyphenSplit[1]
);
penalty +=
Alinea.helpers.hyphenCost *
(1 + 15 / worstHyphenSplit ** 3);
} else {
penalty += Alinea.helpers.hyphenCost;
}
}
return (1 + badness + penalty) ** 2;
},
solveKnuthPlass: (segments, startIdx = 0, goalWidth = 70) => {
let currentLine = [segments[startIdx]];
let lineWidth = segments[startIdx].width;
let bestCost = Infinity;
let bestTail = null;
for (let idx = startIdx + 1; idx <= segments.length; idx++) {
if (idx < segments.length && segments[idx].log.bestCost == -1) {
Alinea.solveKnuthPlass(segments, idx, goalWidth);
}
if (lineWidth > goalWidth * 1.5) {
break;
}
let currentCost = Alinea.lineCost(currentLine, goalWidth);
const nextBestCost =
idx < segments.length ? segments[idx].log.bestCost : 0;
if (currentCost + nextBestCost <= bestCost) {
bestCost = currentCost + nextBestCost;
bestTail = idx;
}
if (idx < segments.length) {
currentLine.push(segments[idx]);
lineWidth += segments[idx].width;
}
}
segments[startIdx].log.bestCost = bestCost;
segments[startIdx].log.tail = bestTail;
return segments;
},
prettyLinebreak: (segments, goalWidth = 70) => {
Alinea.solveKnuthPlass(segments, 0, goalWidth);
let lines = [[segments[0]]];
let tail = segments[0].log.tail;
for (let idx = 1; idx < segments.length; idx++) {
if (idx == tail) {
lines.push([segments[idx]]);
tail = segments[idx].log.tail;
} else {
lines.at(-1).push(segments[idx]);
}
}
return lines;
},
flowText: (text, element) => {
const solved = Alinea.prettyLinebreak(
Alinea.segmentText(text, Alinea.measure.getElementFont(element)),
element.getBoundingClientRect().width
);
const htmlOutput = solved
.map(line =>
line
.map((word, idx, arr) => {
if (idx == arr.length - 1 && word.needsHyphen) {
return `${word.text}-`;
} else {
return word.text;
}
})
.join("")
)
.map((line, idx, arr) =>
idx == arr.length - 1
? `<span class="last-line">${line}</span>`
: line
)
.join("<br>");
element.innerHTML = htmlOutput;
}
};
Alinea.measure.ctx = Alinea.measure.canvas.getContext("2d");
documentReady(async () => {
Alinea.hyphen.dict["en-GB"] = (
await import("/sandbox/hyph/hyph-en-gb.js")
).default;
Alinea.flowText(testString, $("#graff"))
});