[balance-text] Implement balancing algorithm
This patch implements `NGParagraphLineBreaker` that implements
the headline balancing algorithm. It computes the minimum
available width that produces the same number of lines as the
normal line breaker by bisecting.
The algorithm is O(log n). To mitigate the performance penalty,
it skips if the block has more than 4 lines, or it is
estimated to have more than 8 lines.
See the document[1] for more details.
[1] https://docs.google.com/document/d/16-T9gqCagJxcST6hcnneSb7qGunxXa37_UHYqMqhPL0/edit?usp=sharing
Bug: 1251079
Change-Id: I31a5859293622c14dda05e785c4495cd82db6f14
Reviewed-on: https://chromium-review.googlesource.com/c/chromium/src/+/3752780
Commit-Queue: Koji Ishii <kojii@chromium.org>
Reviewed-by: Ian Kilpatrick <ikilpatrick@chromium.org>
Cr-Commit-Position: refs/heads/main@{#1110765}
diff --git a/css/css-text/white-space/text-wrap-balance-001.html b/css/css-text/white-space/text-wrap-balance-001.html
new file mode 100644
index 0000000..3360681
--- /dev/null
+++ b/css/css-text/white-space/text-wrap-balance-001.html
@@ -0,0 +1,32 @@
+<!DOCTYPE html>
+<link rel="help" href="https://w3c.github.io/csswg-drafts/css-text-4/#text-wrap">
+<script src="/resources/testharness.js"></script>
+<script src="/resources/testharnessreport.js"></script>
+<style>
+#container {
+ width: 20ch;
+}
+.balance {
+ text-wrap: balance;
+}
+</style>
+<div id="container"></div>
+<script>
+const container = document.getElementById('container');
+for (const text of [
+ 'Balancing should',
+ 'Balancing should not change',
+ 'Balancing should not change the number of lines.',
+ ]) {
+ const normal = document.createElement('div');
+ const balance = document.createElement('div');
+ normal.textContent = text;
+ balance.textContent = text;
+ balance.classList.add('balance');
+ container.appendChild(normal);
+ container.appendChild(balance);
+ test(() => {
+ assert_equals(normal.offsetHeight, balance.offsetHeight);
+ });
+}
+</script>
