Class: Arrolio::TextLayout::KnuthPlass::Breaker

Inherits:
Object
  • Object
show all
Defined in:
lib/arrolio/text_layout/knuth_plass/breaker.rb

Overview

Optimal line breaking via dynamic programming (Knuth & Plass, 1981). Finds the set of break points that minimizes the total "badness" — the sum of squared adjustment ratios across all lines, plus penalties for flagged breaks.

The algorithm runs in O(n²) worst case (n = item count) but converges in O(n) for typical text because most candidate breaks are pruned early.

When no break sequence is feasible within TOLERANCE (every candidate line is too loose), a second pass runs with emergency stretch added to every line's stretchability — TeX's \emergencystretch. Without it, the only surviving path is the forced final break, which packs the whole paragraph into one overfull line and silently runs off the page.

Produces TextLayout::Line output — compatible with the existing Greedy breaker so the engine can swap freely.

Defined Under Namespace

Classes: Node, RunGroup

Constant Summary collapse

Infinity = 
Float::INFINITY
TOLERANCE =

Tolerance for adjustment ratio — lines with |ratio| above this are infeasible and rejected. Standard TeX default (\tolerance=200) maps to ratio ≈ 1.26 because badness is 100*|r|^3. We use a slightly looser limit (2.5) to allow reasonable stretch on tight paragraphs while rejecting the pathological overfills greedy avoids by construction.

2.5
EMERGENCY_STRETCH =

Stretch added to every line during the emergency pass. Comparable to TeX's \emergencystretch = 2em at body size.

20.0
FLAGGED_PENALTY =

Extra penalty for consecutive flagged breaks (hyphens).

3000.0
OVERFULL_FORCED_PENALTY =

Last-resort cost for a forced break landing an overfull line (ratio beyond the available shrink). Must exceed the worst badness demerits ((1+10000)^2 = 1e8) so ANY breakable alternative wins.

1_000_000_000.0

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(items:, line_widths:, runs:, measurer:, align: :left) ⇒ Breaker

items: Array of KnuthPlass::Item (Box, Glue, Penalty). line_widths: Array of Float — width available per line. If shorter than the number of lines, the last width repeats. runs: Array of InlineRun — for building placed runs. measurer: GlyphMeasurer for width lookups. align: :left, :right, :center, :justify.



56
57
58
59
60
61
62
 
# File 'lib/arrolio/text_layout/knuth_plass/breaker.rb', line 56

def initialize(items:, line_widths:, runs:, measurer:, align: :left)
  @items = items
  @line_widths = line_widths
  @runs = runs
  @measurer = measurer
  @align = align
end

Instance Attribute Details

#align ⇒ Object (readonly)

Returns the value of attribute align.



48
49
50
 
# File 'lib/arrolio/text_layout/knuth_plass/breaker.rb', line 48

def align
  @align
end

#items ⇒ Object (readonly)

Returns the value of attribute items.



48
49
50
 
# File 'lib/arrolio/text_layout/knuth_plass/breaker.rb', line 48

def items
  @items
end

#line_widths ⇒ Object (readonly)

Returns the value of attribute line_widths.



48
49
50
 
# File 'lib/arrolio/text_layout/knuth_plass/breaker.rb', line 48

def line_widths
  @line_widths
end

#measurer ⇒ Object (readonly)

Returns the value of attribute measurer.



48
49
50
 
# File 'lib/arrolio/text_layout/knuth_plass/breaker.rb', line 48

def measurer
  @measurer
end

#runs ⇒ Object (readonly)

Returns the value of attribute runs.



48
49
50
 
# File 'lib/arrolio/text_layout/knuth_plass/breaker.rb', line 48

def runs
  @runs
end

Instance Method Details

#layout ⇒ Object 



64
65
66
67
68
69
70
71
 
# File 'lib/arrolio/text_layout/knuth_plass/breaker.rb', line 64

def layout
  build_prefix_sums
  node = solve
  node = solve(emergency_stretch: EMERGENCY_STRETCH) unless feasible?(node)
  return [] if node.nil?

  build_lines(node)
end