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.

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

Defined Under Namespace

Classes: Node

Constant Summary collapse

Infinity = 
Float::INFINITY
TOLERANCE =

Tolerance for adjustment ratio — lines with ratio above this are considered "underfull" and penalized.

100.0
FLAGGED_PENALTY =

Extra penalty for consecutive flagged breaks (hyphens).

3000.0
DEMERITS_LAST_LINE =

Extra penalty for the last line being underfull.

50.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.



38
39
40
41
42
43
44
 
# File 'lib/arrolio/text_layout/knuth_plass/breaker.rb', line 38

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.



30
31
32
 
# File 'lib/arrolio/text_layout/knuth_plass/breaker.rb', line 30

def align
  @align
end

#items ⇒ Object (readonly)

Returns the value of attribute items.



30
31
32
 
# File 'lib/arrolio/text_layout/knuth_plass/breaker.rb', line 30

def items
  @items
end

#line_widths ⇒ Object (readonly)

Returns the value of attribute line_widths.



30
31
32
 
# File 'lib/arrolio/text_layout/knuth_plass/breaker.rb', line 30

def line_widths
  @line_widths
end

#measurer ⇒ Object (readonly)

Returns the value of attribute measurer.



30
31
32
 
# File 'lib/arrolio/text_layout/knuth_plass/breaker.rb', line 30

def measurer
  @measurer
end

#runs ⇒ Object (readonly)

Returns the value of attribute runs.



30
31
32
 
# File 'lib/arrolio/text_layout/knuth_plass/breaker.rb', line 30

def runs
  @runs
end

Instance Method Details

#layout ⇒ Object 



46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
# File 'lib/arrolio/text_layout/knuth_plass/breaker.rb', line 46

def layout
  nodes = active_nodes
  return [] if nodes.empty?

  # Only consider nodes that reached the end of the items
  # (the FINISHED penalty at the last position).
  final_nodes = nodes.select { |n| n.position == @items.length - 1 }
  return [] if final_nodes.empty?

  # Backtrack from the best final node.
  breaks = reconstruct_breaks(best_final_node(final_nodes))

  # Build Line objects from the break points.
  lines = []
  prev_item = 0
  breaks.each_with_index do |br, line_idx|
    width = line_width_for(line_idx)
    placed = build_placed_runs(prev_item, br, width)
    used = compute_line_width(prev_item, br)
    lines << Line.new(placed, width: used, max_width: width, align: @align)
    prev_item = br
  end
  lines
end