Gelesen wird, was im Satz steht, nicht was zuerst gezeichnet wurde

Das Berliner Gesetz- und Verordnungsblatt zeichnet den ganzseitenbreiten
Titelblock des Gesetzes zuletzt — nach beiden Spalten, obgleich er über ihnen
steht. Im Inhaltsstrom stand er damit mitten in einem Zitat, das über den
Seitenwechsel läuft: „… zur Sicherung des Be-“, Titelblock, „triebs von
Unterkünften …“. Der Wortlaut der Anlage Nummer 31 trug den Titel des
Änderungsgesetzes in sich, und die Nummer wich als einzige aus einem Grunde von
der amtlichen Nachfassung ab, der weder in der Erkennung noch in der Anwendung lag.

Maßgeblich ist fortan das Satzbild in der einfachen Gestalt, die die
Gesetzblätter durchweg haben: zwei Spalten, dazwischen eine Rinne, und darüber
oder dazwischen einzelne ganzseitenbreite Zeilen. Gesucht wird die Rinne — die
senkrechte Linie, die möglichst wenige Zeilen überschreiten, die nahe der Mitte
des Satzspiegels liegt und zu deren beiden Seiten je eine Spalte von
nennenswerter Breite steht. Die wenigen Zeilen, die sie gleichwohl
überschreiten, sind die breiten; sie zerlegen die Seite in Bänder. Gelesen wird
Band für Band von oben nach unten, in jedem Band erst die linke, dann die rechte
Spalte.

Der übliche XY-Schnitt der Literatur leistet das nicht, und der erste Versuch
danach hat es bewiesen: Teilt man erst waagerecht am weitesten Weißraumband,
so zerfällt eine zweispaltige Seite mit Kolumnentitel in oben und unten, ehe sie
in links und rechts zerfällt; gelesen wird links oben, rechts oben, links unten,
rechts unten. Im Infektionsschutzgesetz zerriss das eine Aufzählung mitten
entzwei und ließ von fünfundsiebzig Befehlen einundvierzig übrig. Die Spalte hat
deshalb den Vorrang vor dem Band.

Zwei Vorsichtsmaßregeln begrenzen den Eingriff, der sonst jeden Extraktionslauf
berührte: Innerhalb einer Spalte bleibt es bei der Reihenfolge des
Inhaltsstroms, und findet sich keine Rinne, so bleibt die Seite unangetastet.
Der Eingriff kann Spalten und breite Zeilen gegeneinander versetzen, niemals
aber den Satz einer Spalte durcheinanderbringen, deren Strom schon stimmte.

Ausgezählt über den ganzen Beispielbestand ändern fünfzehn der fünfundvierzig
PDF-Dateien ihren Auszug; nachgesehen sind sie sämtlich, und wo sie den
Fließtext betreffen, rücken sie einen Vorspann an die Stelle, an der er im Satz
steht (Berlin, Thüringen, die Beispielsynopse zum Produkthaftungsrecht). Die
Anlage Nummer 31 gleicht nunmehr der amtlichen Nachfassung; es verbleiben zwei
benannte Abweichungen, keine davon in der Anwendung begründet. Alle
dreihundertneununddreißig Prüfungen laufen durch, darunter jede gepinnte Zahl
des Bestandes; REUSE meldet 176/176.

Co-Authored-By: Claude Opus 5 <noreply@anthropic.com>
Change-Id: I80f100bba2b8e48d0d292fb310f4a9c98fc519ec

2 files changed, 268 insertions, 6 deletions

diff --git a/src/main/java/eu/mulk/aendggner/aenderung/parse/FontgroessenFilter.java b/src/main/java/eu/mulk/aendggner/aenderung/parse/FontgroessenFilter.java
index 25bc7ab..6a9878c 100644
--- a/src/main/java/eu/mulk/aendggner/aenderung/parse/FontgroessenFilter.java
+++ b/src/main/java/eu/mulk/aendggner/aenderung/parse/FontgroessenFilter.java
@@ -146,9 +146,11 @@ final class FontgroessenFilter {
    *
    * @param seite 1-basierte Seitennummer.
    * @param grundlinie Grundlinie (pt von oben); {@link Float#NaN}, wenn unbekannt.
+   * @param startX linker Anfang der Zeile, an den sichtbaren Zeichen gemessen (pt); {@link
+   *     Float#NaN}, wenn unbekannt.
    * @param endX rechtes Ende der Zeile (pt); {@link Float#NaN}, wenn unbekannt.
    */
-  record Zeile(int seite, float grundlinie, float endX, String text) {}
+  record Zeile(int seite, float grundlinie, float startX, float endX, String text) {}
 
   /**
    * Die Zeilen des Dokuments mit ihrer Geometrie. Hat keine Seite eine dominante Brotschrift,
@@ -164,7 +166,7 @@ final class FontgroessenFilter {
     var schwellen = zaehler.schwellenProSeite();
     if (schwellen.isEmpty()) {
       log.debugf("Keine dominanten Fontgrößen; Kleingedrucktes wird nicht gefiltert.");
-      return zerlege(wegwerf.toString());
+      return inLesereihenfolge(zerlege(wegwerf.toString()), spalte);
     }
     log.debugf("Brotschriftgrößen (je Seite): %s", schwellen);
 
@@ -174,7 +176,17 @@ final class FontgroessenFilter {
     filter.setLineSeparator("\n");
     var ausgabe = new StringWriter();
     filter.writeText(dokument, ausgabe);
-    return zerlege(ausgabe.toString());
+    return inLesereihenfolge(zerlege(ausgabe.toString()), spalte);
+  }
+
+  /**
+   * Der XY-Schnitt gilt nur dem ungeteilten Auszug. Wer ohnehin eine Spalte für sich anfordert (die
+   * Zusammenstellung einer Beschlussempfehlung), hat die Lesereihenfolge schon hergestellt — und
+   * zwar über die Grundlinien, die er hernach noch braucht, um die Spalten zeilensynchron
+   * gegeneinanderzuhalten.
+   */
+  private static List<Zeile> inLesereihenfolge(List<Zeile> zeilen, Spalte spalte) {
+    return spalte == Spalte.GANZ ? Lesereihenfolge.ordne(zeilen) : zeilen;
   }
 
   /** Trennt die {@link #ZEILEN_MARKE}-Metadaten wieder vom Text ab. */
@@ -184,6 +196,7 @@ final class FontgroessenFilter {
     for (var zeile : roh) {
       int seite = 0;
       float grundlinie = Float.NaN;
+      float startX = Float.NaN;
       float endX = Float.NaN;
       if (!zeile.isEmpty() && zeile.charAt(zeile.length() - 1) == ZEILEN_MARKE) {
         int start = zeile.lastIndexOf(ZEILEN_MARKE, zeile.length() - 2);
@@ -193,10 +206,12 @@ final class FontgroessenFilter {
             seite = Integer.parseInt(felder[0]);
             grundlinie = Integer.parseInt(felder[1]) / 10f;
             endX = Integer.parseInt(felder[2]);
+            startX = Integer.parseInt(felder[3]);
             zeile = zeile.substring(0, start);
           } catch (NumberFormatException | ArrayIndexOutOfBoundsException e) {
             seite = 0;
             grundlinie = Float.NaN;
+            startX = Float.NaN;
             endX = Float.NaN;
           }
         }
@@ -205,7 +220,7 @@ final class FontgroessenFilter {
       if (zeile.indexOf(ZEILEN_MARKE) >= 0) {
         zeile = MARKEN_REST.matcher(zeile).replaceAll("");
       }
-      zeilen.add(new Zeile(seite, grundlinie, endX, zeile));
+      zeilen.add(new Zeile(seite, grundlinie, startX, endX, zeile));
     }
     return zeilen;
   }
@@ -275,7 +290,8 @@ final class FontgroessenFilter {
     var ergebnis = new ArrayList<Zeile>(zeilen.size());
     for (int i = 0; i < zeilen.size(); i++) {
       var zeile = zeilen.get(i);
-      ergebnis.add(new Zeile(zeile.seite(), zeile.grundlinie(), zeile.endX(), text[i]));
+      ergebnis.add(
+          new Zeile(zeile.seite(), zeile.grundlinie(), zeile.startX(), zeile.endX(), text[i]));
     }
     return ergebnis;
   }
@@ -433,6 +449,14 @@ final class FontgroessenFilter {
     /** End-X (pt) des breitesten behaltenen Laufs der laufenden Zeile; NaN vor dem ersten. */
     private float zeilenEndX = Float.NaN;
 
+    /**
+     * Anfangs-X (pt) der laufenden Zeile, am ersten <em>sichtbaren</em> Zeichen gemessen. Anders
+     * als beim Zeilenende zählen Leerzeichen hier nicht mit: Der linke Rand einer Spalte bestimmt
+     * mit über die Rinne, an der die {@link Lesereihenfolge} schneidet, und ein Lauf beginnt
+     * regelmäßig mit dem Steg der Spalte davor.
+     */
+    private float zeilenStartX = Float.NaN;
+
     /** Grundlinie (pt von oben) der laufenden Zeile: die tiefste ihrer behaltenen Läufe. */
     private float zeilenGrundlinie = Float.NaN;
 
@@ -556,6 +580,10 @@ final class FontgroessenFilter {
       for (var position : positionen) {
         float endX = position.getXDirAdj() + position.getWidthDirAdj();
         zeilenEndX = Float.isNaN(zeilenEndX) ? endX : Math.max(zeilenEndX, endX);
+        if (!position.getUnicode().isBlank()) {
+          float startX = position.getXDirAdj();
+          zeilenStartX = Float.isNaN(zeilenStartX) ? startX : Math.min(zeilenStartX, startX);
+        }
         // Grundlinie = tiefstes Y des Laufs, wie schon in mitSuperskripten: Hochgestelltes sitzt
         // höher und darf die Zeile nicht nach oben ziehen.
         float y = position.getYDirAdj();
@@ -655,14 +683,16 @@ final class FontgroessenFilter {
     private void schreibeZeilenMarke() throws IOException {
       if (!Float.isNaN(zeilenEndX)) {
         writeString(
-            "%c%d,%d,%d%c"
+            "%c%d,%d,%d,%d%c"
                 .formatted(
                     ZEILEN_MARKE,
                     zeilenSeite,
                     Math.round(zeilenGrundlinie * 10),
                     Math.round(zeilenEndX),
+                    Math.round(Float.isNaN(zeilenStartX) ? zeilenEndX : zeilenStartX),
                     ZEILEN_MARKE));
         zeilenEndX = Float.NaN;
+        zeilenStartX = Float.NaN;
         zeilenGrundlinie = Float.NaN;
       }
     }
diff --git a/src/main/java/eu/mulk/aendggner/aenderung/parse/Lesereihenfolge.java b/src/main/java/eu/mulk/aendggner/aenderung/parse/Lesereihenfolge.java
new file mode 100644
index 0000000..3f64786
--- /dev/null
+++ b/src/main/java/eu/mulk/aendggner/aenderung/parse/Lesereihenfolge.java
@@ -0,0 +1,232 @@
+// SPDX-FileCopyrightText: 2020 Matthias Andreas Benkard <code@mail.matthias.benkard.de>
+// SPDX-License-Identifier: AGPL-3.0-or-later
+package eu.mulk.aendggner.aenderung.parse;
+
+import eu.mulk.aendggner.aenderung.parse.FontgroessenFilter.Zeile;
+import java.util.ArrayList;
+import java.util.List;
+import org.jspecify.annotations.Nullable;
+
+/**
+ * Bringt die Zeilen einer Seite in die Reihenfolge, in der ein Mensch sie liest.
+ *
+ * <p>Die Extraktion folgt sonst dem Inhaltsstrom, und das trägt weit: Gesetzblätter zeichnen ihre
+ * Spalten in aller Regel nacheinander, während eine bloße Sortierung nach der Höhe sie
+ * verschränkte. Es trägt aber nicht überall. Das Berliner Gesetz- und Verordnungsblatt zeichnet den
+ * ganzseitenbreiten Titelblock des Gesetzes <em>zuletzt</em> — nach beiden Spalten, obgleich er
+ * über ihnen steht. Im Inhaltsstrom steht er damit mitten in einem Zitat, das über den
+ * Seitenwechsel läuft: „… zur Sicherung des Be-“, Titelblock, „triebs von Unterkünften …“. Der
+ * Wortlaut der Anlage trug den Titel des Änderungsgesetzes in sich.
+ *
+ * <p>Maßgeblich ist deshalb das Satzbild, und zwar in der einfachen Gestalt, die die Gesetzblätter
+ * durchweg haben: <b>zwei Spalten, dazwischen eine Rinne, und darüber oder dazwischen einzelne
+ * ganzseitenbreite Zeilen</b> — Kolumnentitel, Seitenfuß, Titelblock. Gesucht wird die Rinne: die
+ * senkrechte Linie, die möglichst wenige Zeilen überschreiten und zu deren beiden Seiten je eine
+ * Spalte steht. Die wenigen Zeilen, die sie doch überschreiten, sind die ganzseitenbreiten; sie
+ * zerlegen die Seite in Bänder. Gelesen wird Band für Band von oben nach unten, in jedem Band erst
+ * die linke, dann die rechte Spalte, und die breite Zeile an ihrem Platz dazwischen.
+ *
+ * <p>Wo sich keine solche Rinne findet — einspaltiger Satz, Titelseiten —, bleibt es beim
+ * Inhaltsstrom. Ebenso <b>innerhalb</b> einer Spalte: Der Eingriff versetzt Spalten und breite
+ * Zeilen gegeneinander, bringt aber niemals den Satz einer Spalte durcheinander, deren Strom schon
+ * stimmte. Eine Seite, von der auch nur eine Zeile ohne Geometrie kommt, bleibt unangetastet.
+ *
+ * <p>Der einfache XY-Schnitt der Literatur — erst waagerecht am weitesten Weißraumband teilen, dann
+ * senkrecht — leistet das <em>nicht</em>: Auf einer zweispaltigen Seite mit Kolumnentitel liegt das
+ * weiteste Band regelmäßig mitten im Satzspiegel, und die Seite zerfiele in oben und unten, ehe sie
+ * in links und rechts zerfällt. Gelesen würde alsdann links oben, rechts oben, links unten, rechts
+ * unten — im Infektionsschutzgesetz zerriss das eine Aufzählung mitten entzwei.
+ */
+final class Lesereihenfolge {
+
+  /** Mindestbreite (pt) der Rinne zwischen den Spalten. */
+  private static final float RINNE_MIN_PT = 12f;
+
+  /** Zeilen, die die Rinne überschreiten dürfen, mindestens (Kolumnentitel, Titelblock, Fuß). */
+  private static final int BREITE_ZEILEN_MIN = 4;
+
+  /** … und höchstens, als Anteil der Zeilen der Seite. */
+  private static final double BREITE_ZEILEN_ANTEIL = 0.1;
+
+  /** Mindestzahl der Zeilen je Spalte. */
+  private static final int SPALTEN_ZEILEN_MIN = 3;
+
+  /** … und ihr Mindestanteil an den Zeilen der Seite: Zwei Streuzeilen bilden keine Spalte. */
+  private static final double SPALTEN_ZEILEN_ANTEIL = 0.2;
+
+  /**
+   * Zulässiger Abstand der Rinne von der Mitte des Satzspiegels, als Anteil seiner Breite. Ein
+   * Gesetzblatt teilt seine Seite in der Mitte; was weit daneben liegt, ist keine Spaltenrinne,
+   * sondern der Zwischenraum einer Tabelle.
+   */
+  private static final double MITTE_ABWEICHUNG = 0.1;
+
+  /**
+   * Mindestbreite jeder Spalte, als Anteil des Satzspiegels. Die Zellen einer Tabelle sind
+   * schmäler; die beiden Spalten eines Gesetzblatts messen je knapp die Hälfte.
+   */
+  private static final double SPALTEN_BREITE_ANTEIL = 0.3;
+
+  private Lesereihenfolge() {}
+
+  /**
+   * Ordnet die Zeilen seitenweise. Die Seiten selbst bleiben in ihrer Folge; nur was innerhalb
+   * einer Seite steht, wird umgestellt.
+   */
+  static List<Zeile> ordne(List<Zeile> zeilen) {
+    var ergebnis = new ArrayList<Zeile>(zeilen.size());
+    int i = 0;
+    while (i < zeilen.size()) {
+      int j = i;
+      int seite = zeilen.get(i).seite();
+      while (j < zeilen.size() && zeilen.get(j).seite() == seite) {
+        j++;
+      }
+      var seitenZeilen = zeilen.subList(i, j);
+      ergebnis.addAll(vermessbar(seitenZeilen) ? ordneSeite(seitenZeilen) : seitenZeilen);
+      i = j;
+    }
+    return ergebnis;
+  }
+
+  /** Ohne Seitenangabe oder ohne vollständige Koordinaten ist nichts zu ordnen. */
+  private static boolean vermessbar(List<Zeile> zeilen) {
+    if (zeilen.isEmpty() || zeilen.get(0).seite() <= 0) {
+      return false;
+    }
+    for (var zeile : zeilen) {
+      if (Float.isNaN(zeile.grundlinie())
+          || Float.isNaN(zeile.startX())
+          || Float.isNaN(zeile.endX())
+          || zeile.endX() < zeile.startX()) {
+        return false;
+      }
+    }
+    return true;
+  }
+
+  private static List<Zeile> ordneSeite(List<Zeile> seite) {
+    if (seite.size() < 2 * SPALTEN_ZEILEN_MIN) {
+      return seite;
+    }
+    var rinne = findeRinne(seite);
+    if (rinne == null) {
+      return seite;
+    }
+
+    var breite = new ArrayList<Zeile>();
+    var links = new ArrayList<Zeile>();
+    var rechts = new ArrayList<Zeile>();
+    for (var zeile : seite) {
+      if (zeile.endX() <= rinne.x()) {
+        links.add(zeile);
+      } else if (zeile.startX() >= rinne.x()) {
+        rechts.add(zeile);
+      } else {
+        breite.add(zeile);
+      }
+    }
+    breite.sort((a, b) -> Float.compare(a.grundlinie(), b.grundlinie()));
+
+    var ergebnis = new ArrayList<Zeile>(seite.size());
+    float oben = Float.NEGATIVE_INFINITY;
+    for (var trenner : breite) {
+      bandAusgeben(ergebnis, links, rechts, oben, trenner.grundlinie());
+      ergebnis.add(trenner);
+      oben = trenner.grundlinie();
+    }
+    bandAusgeben(ergebnis, links, rechts, oben, Float.POSITIVE_INFINITY);
+    return ergebnis;
+  }
+
+  /**
+   * Ein Band zwischen zwei breiten Zeilen: erst die linke Spalte, dann die rechte, jede in der
+   * Reihenfolge des Inhaltsstroms.
+   */
+  private static void bandAusgeben(
+      List<Zeile> ergebnis, List<Zeile> links, List<Zeile> rechts, float oben, float unten) {
+    for (var spalte : List.of(links, rechts)) {
+      for (var zeile : spalte) {
+        if (zeile.grundlinie() > oben && zeile.grundlinie() < unten) {
+          ergebnis.add(zeile);
+        }
+      }
+    }
+  }
+
+  /**
+   * Die Rinne einer Seite.
+   *
+   * @param x die Linie in der Rinne: Zeilen links davon enden vor ihr, Zeilen rechts beginnen
+   *     hinter ihr, und was beides nicht tut, ist eine breite Zeile.
+   * @param breite der Abstand zwischen dem rechten Rand der linken und dem linken Rand der rechten
+   *     Spalte (pt).
+   */
+  private record Rinne(float x, float breite) {}
+
+  /**
+   * Sucht die weiteste senkrechte Lücke, die von höchstens einer Handvoll Zeilen überschritten wird
+   * und zu deren beiden Seiten eine Spalte steht. Findet sich keine, so ist die Seite nicht
+   * zweispaltig gesetzt — dann bleibt es beim Inhaltsstrom, also beim bisherigen Ergebnis.
+   */
+  private static @Nullable Rinne findeRinne(List<Zeile> seite) {
+    int hoechstensBreit =
+        Math.max(BREITE_ZEILEN_MIN, (int) Math.round(BREITE_ZEILEN_ANTEIL * seite.size()));
+    int mindestensSpalte =
+        Math.max(SPALTEN_ZEILEN_MIN, (int) Math.round(SPALTEN_ZEILEN_ANTEIL * seite.size()));
+
+    // Der Satzspiegel, gemessen an den Zeilen selbst: Die Seitenbreite steht hier nicht zur
+    // Verfügung, und der bedruckte Bereich ist ohnehin das treffendere Maß.
+    float satzLinks = Float.POSITIVE_INFINITY;
+    float satzRechts = Float.NEGATIVE_INFINITY;
+    for (var zeile : seite) {
+      satzLinks = Math.min(satzLinks, zeile.startX());
+      satzRechts = Math.max(satzRechts, zeile.endX());
+    }
+    float satzBreite = satzRechts - satzLinks;
+    if (satzBreite <= 0) {
+      return null;
+    }
+
+    Rinne beste = null;
+    // Als Prüflinien genügen die rechten Zeilenenden: Zwischen zwei benachbarten Enden ändert
+    // sich keine Zuordnung.
+    for (var kandidat : seite) {
+      float x = kandidat.endX();
+      if (Math.abs(x - (satzLinks + satzRechts) / 2) > MITTE_ABWEICHUNG * satzBreite) {
+        continue;
+      }
+      int breit = 0;
+      int linksZahl = 0;
+      int rechtsZahl = 0;
+      float linkerRand = Float.NEGATIVE_INFINITY;
+      float rechterRand = Float.POSITIVE_INFINITY;
+      for (var zeile : seite) {
+        if (zeile.endX() <= x) {
+          linksZahl++;
+          linkerRand = Math.max(linkerRand, zeile.endX());
+        } else if (zeile.startX() >= x) {
+          rechtsZahl++;
+          rechterRand = Math.min(rechterRand, zeile.startX());
+        } else if (++breit > hoechstensBreit) {
+          break;
+        }
+      }
+      if (breit > hoechstensBreit
+          || linksZahl < mindestensSpalte
+          || rechtsZahl < mindestensSpalte) {
+        continue;
+      }
+      float weite = rechterRand - linkerRand;
+      if (weite < RINNE_MIN_PT
+          || linkerRand - satzLinks < SPALTEN_BREITE_ANTEIL * satzBreite
+          || satzRechts - rechterRand < SPALTEN_BREITE_ANTEIL * satzBreite) {
+        continue;
+      }
+      if (beste == null || weite > beste.breite()) {
+        beste = new Rinne((linkerRand + rechterRand) / 2, weite);
+      }
+    }
+    return beste;
+  }
+}