Class: RSyntaxTree::BaseGraph

Inherits:
Object
  • Object
show all
Defined in:
lib/rsyntaxtree/base_graph.rb

Direct Known Subclasses

LsifGraph, SVGGraph

Constant Summary collapse

TIDY_HEIGHT_BUDGET =

Vertical drop for the connectors descending from parent.

Fraction of the tree's baseline height that tidy mode may spend on taller connectors. The budget goes to the levels whose branches are spread widest, evening out branch angles without making the figure noticeably taller.

0.05
TIDY_EXTRA_CAP =

No single level's extra drop may exceed this multiple of the base connector height, so one very wide level cannot consume the whole budget and tower over the rest.

1.5
TIDY_MAX_ITERATIONS =

Compression passes alternate with height recalculation until the layout stops moving (the dynamic connector height couples y to the horizontal spread, so the two must settle together). The cap only guards against pathological oscillation.

10
TIDY_CONVERGENCE =

px; a pass shifting less than this is stable

0.5
TIDY_LEVEL_BALANCE =

Minimum sibling-center distance as a fraction of the widest child-level spread inside the pair's own subtrees. Prevents a parent's pair from being compressed narrower than the level right below it (an inversion that reads as a needle-thin top over flat lower branches); branch angles then stay comparable between adjacent levels. 1.0 = a pair is never tighter than the widest pair among its own children. Applied in the :ordered nest mode only; see tidy_compress.

1.0
TIDY_BASE_SPACING =

Base multiplier for the minimum clearance between adjacent subtrees. At 1.0 (= raw h_gap_between_nodes) leaf labels sit closer than in the standard layout, which reads as crowded; 2.5 restores comparable air while keeping a good part of the compression.

2.5
3.0 / 0.8 + 0.25 * 2

Instance Method Summary collapse

Constructor Details

#initialize(element_list, params, global) ⇒ BaseGraph

Returns a new instance of BaseGraph.



14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
 
# File 'lib/rsyntaxtree/base_graph.rb', line 14

def initialize(element_list, params, global)
  @global = global
  @element_list = element_list
  @symmetrize = params[:symmetrize] == true
  @direction = params[:direction] || "ttb"

  case params[:color]
  # Okabe-Ito Color
  when "modern"
    @col_node = "#0072B2" # blue
    @col_leaf = "#009E73" # bluishgreen
    @col_path = "#CC79A7" # reddishpurple
    @col_extra = "#CC79A7" # orange
    @col_emph = "#D55E00" # vermillion
    # "#000000" black
    # "#56B4E9" skyblue
    # "#F0E442" yellow
    # "#999999" grey
  when "traditional"
    @col_node  = "blue"
    @col_leaf  = "green"
    @col_path = "purple"
    @col_extra = "purple"
    @col_emph = "red"
  # Text stays black; the lines that hold the diagram together are drawn
  # lighter. A figure whose links outnumber its labels — an ontology, a
  # construction network — reads as a black thicket in the monochrome
  # scheme, and grey scaffolding lets the labels come forward again.
  when "gray"
    @col_node = "black"
    @col_leaf = "black"
    @col_path = "#666666"
    @col_extra = "#666666"
    @col_emph = "black"
    @col_connector = "#666666"
  else
    @col_node  = "black"
    @col_leaf  = "black"
    @col_path = "black"
    @col_extra = "black"
  end

  @col_bg   = "none"
  @col_fg   = "black"
  @col_connector ||= "black"

  @col_line = if params[:hide_default_connectors] == true
                "none"
              else
                @col_connector
              end

  @leafstyle = params[:leafstyle]
  @fontset = params[:fontset]
  @fontsize = params[:fontsize]
  @mirror = params[:mirror] == true
  @derivation = params[:derivation] == true
  # tidy is one layout scale: "symmetric" (radical symmetrization) |
  # "off" | "low" (packing, strict leaf positions) | "medium" (packing
  # with cross-row tucking as long as no two leaves swap left-right
  # order) | "high" (free tucking; leaf order kept per row only).
  # Legacy inputs upgrade into the scale: tidy_nest: on lifts "low" to
  # "high", and the old standalone symmetrize: on lifts "off" to
  # "symmetric". When tidy packing is active the symmetric layout is
  # meaningless, so packing wins over a legacy symmetrize flag.
  tidy_mode = params[:tidy].to_s
  tidy_mode = "high" if tidy_mode == "low" && params[:tidy_nest] == true
  tidy_mode = "symmetric" if tidy_mode == "off" && @symmetrize
  @tidy = %w[low medium high].include?(tidy_mode)
  # :none — leaf spans may not overlap at all (strict positions)
  # :ordered — spans may overlap, but leaf centers keep their order
  # :free — no cross-row constraint (contours guard within rows)
  @tidy_nest = case tidy_mode
               when "high" then :free
               when "medium" then :ordered
               else :none
               end
  # Tidy packing bundles the dynamic connector height: contour
  # compression pulls sibling subtrees together, and the dynamic drop
  # keeps branch angles even as the horizontal spread shrinks.
  @dynamic_connector = @tidy
  @symmetrize = tidy_mode == "symmetric"
end

Instance Method Details

#ancestor_ids(element) ⇒ Object

Ids of the strict ancestors of element (not including the element itself): the nodes that must stay put while a linked pair is spread, so they can be re-centred over their children afterwards.



809
810
811
812
813
814
815
816
817
 
# File 'lib/rsyntaxtree/base_graph.rb', line 809

def ancestor_ids(element)
  ids = []
  current = element
  until current.parent.to_i.zero?
    current = @element_list.get_id(current.parent)
    ids << current.id
  end
  ids
end

#calculate_height(id = 1) ⇒ Object 



214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
 
# File 'lib/rsyntaxtree/base_graph.rb', line 214

def calculate_height(id = 1)
  target = @element_list.get_id(id)
  if id == 1
    # Drops depend on the current horizontal layout, which changes
    # between tidy passes — recompute them for each full pass.
    @level_connector_heights = nil
    target.vertical_indent = 0
  else
    parent = @element_list.get_id(target.parent)

    # A leaf with nothing drawn over it is pulled up against its node; one
    # with a triangle over it needs the room the triangle takes. Which is
    # which is the same question the connector asks, so it is asked the same
    # way — reading only the leaf's own mark left `[^NP cats]` a triangle
    # squashed into a gap that had been closed.
    vertical_indent = if !triangle_asked_for?(parent, target) &&
                         (@leafstyle == "nothing" || @leafstyle == "none") &&
                         ETYPE_LEAF == target.type && parent.children.size == 1
                        if @direction == "ltr"
                          # LTR: add small horizontal gap between parent and leaf
                          parent.vertical_indent + parent.content_height + @global[:height_connector_to_text]
                        else
                          parent.vertical_indent + parent.content_height
                        end
                      else
                        parent.vertical_indent + parent.content_height + connector_height_for(parent)
                      end
    target.vertical_indent = vertical_indent
  end

  if target.children.empty?
    target.height = target.content_height
    target.vertical_indent + target.content_height
  else
    accum_array = []
    target.children.each do |c|
      accum_array << calculate_height(c)
    end
    target.height = accum_array.max - target.vertical_indent
    accum_array.max
  end.tap { level_derivation_rows if id == 1 && @derivation }
end

#calculate_indent ⇒ Object 



371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
 
# File 'lib/rsyntaxtree/base_graph.rb', line 371

def calculate_indent
  node_groups = @element_list.get_elements.group_by(&:parent)
  node_groups.each do |k, v|
    next if k.zero?

    parent = @element_list.get_id(k)
    if @symmetrize
      num_leaves = v.size
      partition_width = parent.width / num_leaves
      left_offset = parent.horizontal_indent + parent.content_width / 2.0 - parent.width / 2.0
      v.each do |e|
        indent = left_offset + (partition_width - e.content_width) / 2.0
        e.horizontal_indent = indent
        left_offset += partition_width
      end
    else
      left_offset = parent.horizontal_indent + parent.content_width / 2.0 - parent.width / 2.0
      v.each do |e|
        indent = left_offset + (e.width - e.content_width) / 2.0
        e.horizontal_indent = indent
        left_offset += e.width
      end
    end
  end
end

#calculate_level ⇒ Object 



154
155
156
157
158
159
 
# File 'lib/rsyntaxtree/base_graph.rb', line 154

def calculate_level
  @element_list.get_elements.select { |e| e.type == 2 }.each do |e|
    parent = @element_list.get_id(e.parent)
    e.level = @element_list.get_id(e.parent).level + 1 if parent
  end
end

#calculate_width(id = 1) ⇒ Object 



161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
 
# File 'lib/rsyntaxtree/base_graph.rb', line 161

def calculate_width(id = 1)
  target = @element_list.get_id(id)
  if target.children.empty?
    target.width = target.content_width + @global[:h_gap_between_nodes] * 4

    parent = @element_list.get_id(target.parent)
    while parent && parent.children.size == 1
      w = parent.content_width
      target.width = w + @global[:h_gap_between_nodes] * 4 if w > target.content_width
      parent = @element_list.get_id(parent.parent)
    end
    target.width
  else
    return target.width if target.width != 0

    accum_array = []
    target.children.each do |c|
      accum_array << calculate_width(c)
    end
    accum_width = if @symmetrize
                    accum_array.max * target.children.size
                  else
                    accum_array.sum
                  end

    # The name of the step hangs past the right end of its rule, and the
    # rule reaches the full width of what the step combines. With no room
    # kept for it the name lands on the next subtree's rule and two steps
    # read as one, so the node claims that much more width. The label is
    # drawn from the left edge and does not move.
    #
    # Doubled: the children sit centred in the width their mother claims,
    # so half of whatever is added lands on the left where nothing needs
    # it, and only the other half reaches the side the name is on.
    accum_width += rule_name_room(target) * 2

    if target.content_width > accum_width
      # Parent label is wider than children's total width.
      # Distribute the excess equally among children to prevent
      # child labels from overlapping when centered in their slots.
      excess = target.content_width - accum_width
      per_child = excess / target.children.size.to_f
      target.children.each do |c|
        child = @element_list.get_id(c)
        child.width += per_child
      end
      target.width = target.content_width
    else
      target.width = accum_width
    end
  end
end

#child_spread(node) ⇒ Object

Spread (max center-to-center distance) of +node+'s immediate children, or nil when it has fewer than two.



674
675
676
677
678
679
680
 
# File 'lib/rsyntaxtree/base_graph.rb', line 674

def child_spread(node)
  kids = node.children.map { |c| @element_list.get_id(c) }
  return nil if kids.size < 2

  centers = kids.map { |k| k.horizontal_indent + k.content_width / 2.0 }
  centers.max - centers.min
end

#connector_height_for(parent) ⇒ Object

With a fixed drop, branch angles differ sharply between nodes whose children sit close together (deep in a binary tree) and nodes whose children are far apart (near the root, where the branches flatten out). In tidy mode each level's drop is the base height plus a share of a small height budget (TIDY_HEIGHT_BUDGET x baseline height), allocated in proportion to how widely that level's branches spread — the widest (flattest) levels get the most relief. All parents on a level share one drop so same-depth cousins stay vertically aligned.



119
120
121
122
123
124
 
# File 'lib/rsyntaxtree/base_graph.rb', line 119

def connector_height_for(parent)
  base = @global[:height_connector]
  return base unless @dynamic_connector

  level_connector_heights[parent.level] || base
end

#contour_clearance(left_rects, right_rects) ⇒ Object

Minimum horizontal clearance between two sets of rects over the y intervals where both sets have coverage; nil when they never co-occur in y. Exact: within an elementary y interval the covering rects are constant, so comparing the max right edge against the min left edge gives the worst point of that interval.



658
659
660
661
662
663
664
665
666
667
668
669
670
 
# File 'lib/rsyntaxtree/base_graph.rb', line 658

def contour_clearance(left_rects, right_rects)
  boundaries = (left_rects + right_rects).flat_map { |r| [r[0], r[1]] }.uniq.sort
  clearance = Float::INFINITY
  boundaries.each_cons(2) do |y0, y1|
    left = left_rects.select { |r| r[0] < y1 && r[1] > y0 }
    right = right_rects.select { |r| r[0] < y1 && r[1] > y0 }
    next if left.empty? || right.empty?

    gap = right.map { |r| r[2] }.min - left.map { |r| r[3] }.max
    clearance = gap if gap < clearance
  end
  clearance.infinite? ? nil : clearance
end

#derivation_row_extent(row) ⇒ Object

How far a row reaches, read from the labels as they stand. Taken when the rows were levelled it would be the measured height, and the drawing works to a slightly different one.



307
308
309
310
311
312
313
314
 
# File 'lib/rsyntaxtree/base_graph.rb', line 307

def derivation_row_extent(row)
  @derivation_extents ||= {}
  @derivation_extents[row] ||= begin
    members = @element_list.get_elements.select { |e| @derivation_rows[e.id] == row }
    [members.map(&:vertical_indent).min,
     members.map { |e| e.vertical_indent + e.content_height }.max]
  end
end

#derivation_rule_band(parent) ⇒ Object

The rule for a step runs between the row its result sits in and the row holding the last of its premises — always the next row along, since a step is one taller than the tallest thing it draws on.



319
320
321
322
323
324
325
326
327
328
329
 
# File 'lib/rsyntaxtree/base_graph.rb', line 319

def derivation_rule_band(parent)
  return nil unless @derivation_rows

  row = @derivation_rows[parent.id]
  neighbour = row + (@direction == "btt" ? -1 : 1)
  return nil unless @derivation_rows.value?(neighbour)

  here = derivation_row_extent(row)
  there = derivation_row_extent(neighbour)
  @direction == "btt" ? [there[1], here[0]] : [here[1], there[0]]
end

#draw_connector(id = 1) ⇒ Object 



419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
 
# File 'lib/rsyntaxtree/base_graph.rb', line 419

def draw_connector(id = 1)
  parent = @element_list.get_id(id)
  children = parent.children.map { |c| @element_list.get_id(c) }

  # A derivation joins its premises with one rule drawn across all of them,
  # not with a line to each. The rule replaces the lines, so a tree is drawn
  # this way throughout or not at all.
  if @derivation && !children.empty?
    rule_to_parent(parent, children)
    parent.children.each { |c| draw_connector(c) }
    return
  end

  if children.size == 1
    child = children[0]
    forced = triangle_asked_for?(parent, child)
    case @leafstyle
    when "auto"
      if forced || child.contains_phrase
        triangle_to_parent(parent, child)
      else
        line_to_parent(parent, child)
      end
    when "bar"
      if forced
        triangle_to_parent(parent, child)
      else
        line_to_parent(parent, child)
      end
    when "nothing", "none"
      if forced
        triangle_to_parent(parent, child)
      elsif ETYPE_LEAF != child.type
        line_to_parent(parent, child)
      end
    end
  else
    children.each do |child|
      line_to_parent(parent, child)
    end
  end

  parent.children.each do |c|
    draw_connector(c)
  end
end

#draw_elements ⇒ Object 



397
398
399
400
401
 
# File 'lib/rsyntaxtree/base_graph.rb', line 397

def draw_elements
  @element_list.get_elements.each do |element|
    draw_element(element)
  end
end

#effective_rect(node) ⇒ Object

Effective visual rectangle of node as [y0, y1, x0, x1], widening the content rect where the drawing extends beyond it. Mirrors the geometry of SVGGraph#element_visual_box: enclosures (#/##/###) paint brackets or a rectangle outside the label, so the contour must reserve that space. Triangles need no widening (their base spans exactly the child's content width). Vertically the full content box is kept — a conservative superset of the glyph box, which is what the horizontal contour comparison needs.



572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
 
# File 'lib/rsyntaxtree/base_graph.rb', line 572

def effective_rect(node)
  x0 = node.horizontal_indent
  x1 = node.horizontal_indent + node.content_width
  if [:brackets, :rectangle, :brectangle].include?(node.enclosure)
    ext = @global[:h_gap_between_nodes] / 2 + @global[:stroke_bold]
    x0 -= ext
    x1 += ext
  end
  # A step's name is drawn past the right end of its rule, and the rule
  # reaches the full width of what the step combines. Packing sees only the
  # labels, so without this the neighbour is pulled up against the name and
  # two steps read as one long rule.
  x1 = [x1, subtree_right(node.id) + rule_name_room(node)].max if @derivation
  [node.vertical_indent, node.vertical_indent + node.content_height, x0, x1]
end

#finalize_ltr ⇒ Object

Phase 2 (after layout, before drawing): swap position axes and restore original content dimensions for correct text rendering.



983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
 
# File 'lib/rsyntaxtree/base_graph.rb', line 983

def finalize_ltr
  @element_list.get_elements.each do |e|
    # Swap position axes
    h = e.horizontal_indent
    v = e.vertical_indent
    e.horizontal_indent = v
    e.vertical_indent = h

    # Restore original content dimensions (text is still horizontal)
    cw = e.content_width
    ch = e.content_height
    e.content_width = ch
    e.content_height = cw
  end

  # Restore original global values
  @global[:h_gap_between_nodes] = @saved_h_gap
  @global[:height_connector] = @saved_height_connector
end

#flip_vertical ⇒ Object

Flip the laid-out tree vertically: the root ends up at the bottom and the leaves at the top, which is how a derivation is written — the words at the top, each step below the material it combines. Done after the layout is final, like the horizontal flip, so connectors, triangles, paths and region shades follow from the coordinates without knowing about it.



510
511
512
513
514
515
516
 
# File 'lib/rsyntaxtree/base_graph.rb', line 510

def flip_vertical
  elements = @element_list.get_elements
  max_bottom = elements.map { |e| e.vertical_indent + e.content_height }.max
  elements.each do |e|
    e.vertical_indent = max_bottom - (e.vertical_indent + e.content_height)
  end
end

#get_leftmost(id = 1) ⇒ Object 



466
467
468
469
470
471
 
# File 'lib/rsyntaxtree/base_graph.rb', line 466

def get_leftmost(id = 1)
  target = @element_list.get_id(id)
  target_indent = target.horizontal_indent
  children_indent = target.children.map { |c| get_leftmost(c) }
  (children_indent << target_indent).min
end

#get_rightmost(id = 1) ⇒ Object 



487
488
489
490
491
492
 
# File 'lib/rsyntaxtree/base_graph.rb', line 487

def get_rightmost(id = 1)
  target = @element_list.get_id(id)
  target_right_end = target.horizontal_indent + target.content_width
  children_right_end = target.children.map { |c| get_rightmost(c) }
  (children_right_end << target_right_end).max
end

#layout_overlaps? ⇒ Boolean

Pairwise intersection over the effective (decoration-aware) rects.

Returns:

  • (Boolean) 


941
942
943
944
945
946
 
# File 'lib/rsyntaxtree/base_graph.rb', line 941

def layout_overlaps?
  rects = @element_list.get_elements.map { |e| effective_rect(e) }
  rects.combination(2).any? do |a, b|
    a[2] < b[3] - 0.01 && b[2] < a[3] - 0.01 && a[0] < b[1] - 0.01 && b[0] < a[1] - 0.01
  end
end

#layout_snapshot ⇒ Object

Snapshot / restore of everything the tidy passes mutate.



928
929
930
 
# File 'lib/rsyntaxtree/base_graph.rb', line 928

def layout_snapshot
  @element_list.get_elements.map { |e| [e.horizontal_indent, e.vertical_indent, e.height] }
end

#level_connector_heights ⇒ Object 



126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
 
# File 'lib/rsyntaxtree/base_graph.rb', line 126

def level_connector_heights
  @level_connector_heights ||= begin
    base = @global[:height_connector]
    spreads = {}
    row_heights = {}
    @element_list.get_elements.each do |e|
      row_heights[e.level] = [row_heights[e.level] || 0, e.content_height || 0].max
      next if e.children.size < 2

      kids = e.children.map { |c| @element_list.get_id(c) }.compact
      centers = kids.map { |k| k.horizontal_indent + k.content_width / 2.0 }
      spread = centers.max - centers.min
      spreads[e.level] = [spreads[e.level] || 0, spread].max if spread.positive?
    end

    levels_with_children = @element_list.get_elements.reject { |e| e.children.empty? }
                                        .map(&:level).uniq.size
    baseline = levels_with_children * base + row_heights.values.sum
    budget = baseline * TIDY_HEIGHT_BUDGET
    total_spread = spreads.values.sum

    spreads.each_with_object({}) do |(lv, spread), drops|
      extra = total_spread.positive? ? budget * spread / total_spread : 0.0
      drops[lv] = base + [extra, base * TIDY_EXTRA_CAP].min
    end
  end
end

#level_derivation_rows(flipped: false) ⇒ Object

In a derivation every premise is given at the start, so the words stand in one row and each step sits below everything it draws on. A node's row is therefore its distance from the words rather than its distance from the root: a step joining a category to a derivation three deep goes below both. Placed by depth from the root instead, the words come out in a staircase, each at the depth of its own branch.

Run after the ordinary placement, so the row heights and the drop between them are the ones that pass settled on. Levelled twice, and the two are not the same pass. The first runs inside the layout, because tidy packs subtrees by their contours and a contour is read off the vertical positions: rows it has not seen levelled pack as though the figure were a tree, and two rules of one row come out overlapping. The second runs after the layout has been turned over, since turning it over sets each box against its own bottom edge, which leaves a tall label — a feature matrix, say — standing proud of its row. Counting rows from the end the words are at is what makes the second pass the same reckoning as the first, read the other way up.



275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
 
# File 'lib/rsyntaxtree/base_graph.rb', line 275

def level_derivation_rows(flipped: false)
  root_height = subtree_height(1)
  rows = {}
  tallest = Hash.new(0.0)
  @element_list.get_elements.each do |e|
    height = subtree_height(e.id)
    row = flipped ? height : root_height - height
    rows[e.id] = row
    tallest[row] = [tallest[row], e.content_height].max
  end

  drop = @global[:height_connector].to_f
  top = {}
  y = 0.0
  tallest.keys.sort.each do |row|
    top[row] = y
    y += tallest[row] + drop
  end

  @element_list.get_elements.each { |e| e.vertical_indent = top[rows[e.id]] }

  # Which row each element ended up in, kept for the drawing: a rule belongs
  # between two rows, not between two labels. Placed from the label instead,
  # a step whose result is taller than its neighbours — a feature matrix
  # among plain categories — had its rule drawn at a height of its own while
  # the rules beside it stayed on the row.
  @derivation_rows = rows
end

#link_connection_pairs ⇒ Object

Pairs of elements joined by a line-type connection (path entries of the -N / ->N / -<N form), mirroring the pool in SvgGraph#draw_paths.



794
795
796
797
798
799
800
801
802
803
804
 
# File 'lib/rsyntaxtree/base_graph.rb', line 794

def link_connection_pairs
  pool = {}
  @element_list.get_elements.each do |e|
    e.path.each do |tr|
      next unless /\A-(>|<)?(\d+)\z/ =~ tr

      (pool[$2] ||= []) << e
    end
  end
  pool.values.select { |ends| ends.size == 2 }
end

#make_balance(id = 1) ⇒ Object 



339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
 
# File 'lib/rsyntaxtree/base_graph.rb', line 339

def make_balance(id = 1)
  target = @element_list.get_id(id)
  if target.children.empty?
    parent = @element_list.get_id(target.parent)
    # A childless element with no parent is a root standing alone —
    # text in front of the tree makes one. It has no siblings to match
    # widths with, so its own width is already the answer.
    return target.width if parent.nil?

    accum_array = []
    parent.children.each do |c|
      accum_array << @element_list.get_id(c).width
    end
    max = accum_array.max
    parent.children.each do |c|
      @element_list.get_id(c).width = max
    end
    max
  else
    accum_array = []
    target.children.each do |c|
      accum_array << make_balance(c)
    end
    accum_width = accum_array.max
    max = [accum_width, target.content_width].max
    target.children.each do |c|
      @element_list.get_id(c).width = max
    end
    target.width
  end
end

#middle_child_alignment ⇒ Object

For every parent with an odd number of children, the offset of the middle child's centre from the centre of the children's span. In a balanced tree that offset is zero and the parent's edge to the middle child is vertical. The spread below moves the right side of a linked pair rightward, so re-centring the parents afterwards puts the span centre — and the parent — off the middle child. Recorded before the spread so the pass can hand the alignment back; see restore_middle_child_alignment.



827
828
829
830
831
832
833
834
835
836
 
# File 'lib/rsyntaxtree/base_graph.rb', line 827

def middle_child_alignment
  @element_list.get_elements
               .reject { |e| e.children.empty? || e.children.size.even? }
               .to_h do |p|
    kids = p.children.map { |c| @element_list.get_id(c) }
    centers = kids.map { |k| k.horizontal_indent + k.content_width / 2.0 }
    mid = kids[kids.size / 2]
    [p.id, (mid.horizontal_indent + mid.content_width / 2.0) - (centers.min + centers.max) / 2.0]
  end
end

#mirror_layout ⇒ Object

Flip the laid-out tree horizontally (RTL linguistics convention: the first word sits at the right edge). Connectors, triangles, polylines, movement paths, and region shades all derive from element coordinates, so flipping every element here keeps them consistent. Works for both directions: ttb yields a right-to-left vertical tree; ltr puts the root at the right edge of the horizontal tree.



524
525
526
527
528
529
530
531
532
 
# File 'lib/rsyntaxtree/base_graph.rb', line 524

def mirror_layout
  max_right = @element_list.get_elements.map { |e| e.horizontal_indent + e.content_width }.max
  @element_list.get_elements.each do |e|
    e.horizontal_indent = max_right - (e.horizontal_indent + e.content_width)
  end
  # Re-align the left edge to the standard left margin
  offset = @global[:h_gap_between_nodes] - get_leftmost
  @element_list.get_elements.each { |e| e.horizontal_indent += offset }
end

#node_centering ⇒ Object 



494
495
496
497
498
499
500
501
502
503
 
# File 'lib/rsyntaxtree/base_graph.rb', line 494

def node_centering
  node_groups = @element_list.get_elements.group_by(&:parent)
  node_groups.sort_by { |k, _v| -k }.each do |k, v|
    next if k.zero?

    parent = @element_list.get_id(k)
    child_positions = v.map { |child| child.horizontal_indent + child.content_width / 2 }
    parent.horizontal_indent = child_positions.min + (child_positions.max - child_positions.min - parent.content_width) / 2
  end
end

#normalize_horizontal ⇒ Object

Shift the whole tree so the leftmost node lands one gap from the edge.



776
777
778
779
 
# File 'lib/rsyntaxtree/base_graph.rb', line 776

def normalize_horizontal
  offset = @global[:h_gap_between_nodes] - get_leftmost
  @element_list.get_elements.each { |e| e.horizontal_indent += offset }
end

#parse_list ⇒ Object 



1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
 
# File 'lib/rsyntaxtree/base_graph.rb', line 1003

def parse_list
  # Phase 1: swap content dimensions for LTR layout calculation
  prepare_ltr if @direction == "ltr"

  if @element_list.elements.size > 1
    calculate_level
    calculate_width
    make_balance if @symmetrize
    calculate_indent
    node_centering
  end

  top = @element_list.get_id(1)
  diff = top.horizontal_indent
  @element_list.get_elements.each do |e|
    e.horizontal_indent -= diff
  end

  offset_l = (top.horizontal_indent - get_leftmost) + @global[:h_gap_between_nodes]

  @element_list.get_elements.each do |e|
    e.horizontal_indent += offset_l
  end

  calculate_height

  # Tidy mode: compress sibling subtrees by their contours, then let the
  # dynamic connector height settle. Each pass compresses against the
  # current vertical layout and recomputes heights for the next one;
  # repeat until neither moves (see tidy_compress for why passes must
  # also be able to push subtrees back apart). For LTR this runs in the
  # swapped coordinate system, where the same logic applies.
  #
  # Safety net: convergence is not proven, and a height recalculation
  # can transiently move nodes into a shared y band (which the NEXT
  # pass repairs by pushing subtrees apart). So passes are allowed to
  # continue through transient overlaps, but the last overlap-free
  # state is always remembered, and any overlapping final state is
  # rolled back to it — tidy never emits an overlapping tree.
  if @tidy && @element_list.elements.size > 1
    snapshot = layout_snapshot # the pre-tidy layout is overlap-free
    TIDY_MAX_ITERATIONS.times do
      max_shift = tidy_compress
      normalize_horizontal
      calculate_height
      next if layout_overlaps?

      snapshot = layout_snapshot
      break if max_shift < TIDY_CONVERGENCE
    end
    restore_layout(snapshot) if layout_overlaps?
  end

  # Give line-linked pairs room for a full-size arrow (no-op without
  # links). Guarded the same way tidy is: if spreading ever produced an
  # overlap, roll back and let the arrow clamp instead.
  if @element_list.elements.size > 1
    snapshot = layout_snapshot
    spread_linked_pairs
    restore_layout(snapshot) if layout_overlaps?
  end

  # Phase 2: swap axes and restore content dimensions for LTR
  finalize_ltr if @direction == "ltr"

  # RTL flip (mirror option): after the layout is final, before drawing
  # btt is the top-to-bottom layout turned over, so the layout runs as
  # usual and the flip comes after it.
  flip_vertical if @direction == "btt"
  level_derivation_rows(flipped: true) if @derivation && @direction == "btt"
  mirror_layout if @mirror

  draw_elements
  draw_connector
  draw_paths

  # Calculate final bounds
  max_x = 0
  max_y = 0
  @element_list.get_elements.each do |e|
    r = e.horizontal_indent + e.content_width
    b = e.vertical_indent + e.content_height
    max_x = r if r > max_x
    max_y = b if b > max_y
  end
  # A rule's name is set beside the rule, past the right edge of every box
  # the loop above measured.
  max_x = @rule_name_edge if @rule_name_edge.to_f > max_x
  width = max_x + @global[:h_gap_between_nodes]
  height = max_y
  height = @height if @height > height
  { height: height, width: width }
end

#prepare_ltr ⇒ Object

LTR layout: two-phase coordinate transformation.

Phase 1 (before layout): swap content dimensions so the layout algorithm uses text height for sibling spreading (→ vertical) and text width for depth spacing (→ horizontal).



953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
 
# File 'lib/rsyntaxtree/base_graph.rb', line 953

def prepare_ltr
  @element_list.get_elements.each do |e|
    cw = e.content_width
    ch = e.content_height
    e.content_width = ch
    e.content_height = cw
  end

  # Save original global values for restoration in finalize_ltr
  @saved_h_gap = @global[:h_gap_between_nodes]
  @saved_height_connector = @global[:height_connector]

  # In LTR, siblings stack vertically. The TTB h_gap (char_width * 0.8)
  # is disproportionately large relative to the swapped content dimensions.
  # Use height_connector_to_text / 2 (= font_height / 4) for tight
  # vertical packing proportional to the font size.
  @global[:h_gap_between_nodes] = @global[:height_connector_to_text] / 2

  # In LTR, height_connector becomes horizontal depth between levels.
  # After content swap, content_height = original content_width (small),
  # so depth = small_value + height_connector. To maintain proportional
  # depth similar to TTB (where depth = content_height + height_connector),
  # compensate for the content dimension difference.
  metrics = @global[:single_x_metrics]
  content_diff = @global[:single_line_height] - metrics.width
  @global[:height_connector] = @global[:height_connector] + [content_diff, 0].max
end

#restore_layout(snapshot) ⇒ Object 



932
933
934
935
936
937
938
 
# File 'lib/rsyntaxtree/base_graph.rb', line 932

def restore_layout(snapshot)
  @element_list.get_elements.zip(snapshot) do |e, (h, v, ht)|
    e.horizontal_indent = h
    e.vertical_indent = v
    e.height = ht
  end
end

#restore_middle_child_alignment(before) ⇒ Object

Undo whatever the spread did to the middle-child alignment of every odd-child parent, deepest first. The drift is cancelled by shifting the whole side the drift points away from: when the span centre ran right of the middle child, everything right of the middle child's subtree moves right by twice the drift (moving the span centre back by exactly the drift). The side moves rigidly, so no gap inside it changes, and the gap across the middle only widens — no overlaps.



845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
 
# File 'lib/rsyntaxtree/base_graph.rb', line 845

def restore_middle_child_alignment(before)
  parents = @element_list.get_elements
                         .reject { |e| e.children.empty? || e.children.size.even? }
  parents.sort_by { |p| -p.level }.each do |p|
    kids = p.children.map { |c| @element_list.get_id(c) }
    mid = kids[kids.size / 2]
    centers = kids.map { |k| k.horizontal_indent + k.content_width / 2.0 }
    dx = (mid.horizontal_indent + mid.content_width / 2.0) - (centers.min + centers.max) / 2.0
    drift = dx - before[p.id]
    next if drift.abs < 0.01

    if drift.positive?
      split = get_rightmost(mid.id)
      @element_list.get_elements.each do |e|
        e.horizontal_indent += drift * 2 if e.horizontal_indent >= split - 0.001
      end
    else
      split = get_leftmost(mid.id)
      @element_list.get_elements.each do |e|
        e.horizontal_indent += drift * 2 if e.horizontal_indent + e.content_width <= split + 0.001
      end
    end
    node_centering
  end
end

#rule_name_room(element) ⇒ Object

Width to keep clear to the right of a step's rule for the name beside it, with a gap between the name and whatever follows. Zero unless the tree is drawn as a derivation and the step has a name.



476
477
478
479
480
481
482
483
484
485
 
# File 'lib/rsyntaxtree/base_graph.rb', line 476

def rule_name_room(element)
  return 0 unless @derivation

  name = element.rule_name
  return 0 if name.nil? || name.empty?

  size = (@fontsize * 0.8).round(2)
  width = FontMetrics.get_metrics(name, @fontset[:family], size, :normal, :normal).width
  width + @global[:width_half_x]
end

#shift_subtree(id, delta) ⇒ Object 



682
683
684
685
686
 
# File 'lib/rsyntaxtree/base_graph.rb', line 682

def shift_subtree(id, delta)
  node = @element_list.get_id(id)
  node.horizontal_indent += delta
  node.children.each { |c| shift_subtree(c, delta) }
end

#spread_linked_pairs ⇒ Object

Push linked pairs apart until the gap between their boxes holds a full-size arrow. Runs after the tidy passes: a compression pass would simply undo any room reserved in the width calculation, while shifting the right-hand side rightward here can never create an overlap, so tidy's guarantee survives. Only links drawn horizontally need room — the two y ranges must overlap, the same test draw_paths applies. The pair's own ancestors stay put and are re-centred over their children afterwards; everything else right of the split moves by the deficit. LTR is excluded: its sibling links are vertical, and sizing them to the same span would stretch every stacked pair far beyond what the compact stacking justifies — the clamp covers those.



882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
 
# File 'lib/rsyntaxtree/base_graph.rb', line 882

def spread_linked_pairs
  return if @direction == "ltr"

  pairs = link_connection_pairs
  return if pairs.empty?

  hct = @global[:height_connector_to_text]
  required = @global[:h_gap_between_nodes] * LINK_ARROW_CLEARANCE
  alignment_before = middle_child_alignment
  spread = false
  pairs.map { |a, b| [a, b].sort_by(&:horizontal_indent) }
       .sort_by { |a, _b| a.horizontal_indent }
       .each do |a, b|
    a_top = a.vertical_indent + hct / 2
    b_top = b.vertical_indent + hct / 2
    a_bottom = a.vertical_indent + a.content_height + hct
    b_bottom = b.vertical_indent + b.content_height + hct
    next if a_top > b_bottom || b_top > a_bottom

    gap = b.horizontal_indent - (a.horizontal_indent + a.content_width)
    deficit = required - gap
    next if deficit <= 0.01

    ancestors = ancestor_ids(a) + ancestor_ids(b)
    split = a.horizontal_indent + a.content_width
    @element_list.get_elements.each do |e|
      e.horizontal_indent += deficit if e.horizontal_indent >= split - 0.001 && !ancestors.include?(e.id)
    end
    spread = true
  end
  # A figure whose links already had their room is left exactly as tidy
  # left it: re-centring it would move nothing but the last decimal.
  return unless spread

  node_centering
  # The spread pushed the right side of each linked pair rightward, which
  # pulls an odd-child parent's span centre off its middle child (the
  # middle edge slants). Give the alignment back before settling.
  restore_middle_child_alignment(alignment_before)
  normalize_horizontal
  # The dynamic connector height couples level spacing to the horizontal
  # spread, so let it settle against the widened layout.
  calculate_height
end

#subtree_height(id) ⇒ Object

Steps from id down to the furthest word under it. A word is zero.



332
333
334
335
336
337
 
# File 'lib/rsyntaxtree/base_graph.rb', line 332

def subtree_height(id)
  node = @element_list.get_id(id)
  return 0 if node.children.empty?

  1 + node.children.map { |c| subtree_height(c) }.max
end

#subtree_leaf_center_span(id) ⇒ Object

[leftmost leaf center, rightmost leaf center] of the subtree rooted at id, or nil when the subtree has no leaf.



616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
 
# File 'lib/rsyntaxtree/base_graph.rb', line 616

def subtree_leaf_center_span(id)
  leaves = []
  stack = [@element_list.get_id(id)]
  until stack.empty?
    node = stack.pop
    if node.children.empty?
      leaves << node
    else
      node.children.each { |c| stack << @element_list.get_id(c) }
    end
  end
  return nil if leaves.empty?

  centers = leaves.map { |e| e.horizontal_indent + e.content_width / 2.0 }
  [centers.min, centers.max]
end

#subtree_leaf_span(id) ⇒ Object

[left edge of the leftmost leaf, right edge of the rightmost leaf] of the subtree rooted at id (effective extents), or nil when the subtree has no leaf.



636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
 
# File 'lib/rsyntaxtree/base_graph.rb', line 636

def subtree_leaf_span(id)
  leaves = []
  stack = [@element_list.get_id(id)]
  until stack.empty?
    node = stack.pop
    if node.children.empty?
      leaves << node
    else
      node.children.each { |c| stack << @element_list.get_id(c) }
    end
  end
  return nil if leaves.empty?

  rects = leaves.map { |e| effective_rect(e) }
  [rects.map { |r| r[2] }.min, rects.map { |r| r[3] }.max]
end

#subtree_rects(id) ⇒ Object

Effective-rect list of the subtree rooted at id, as [y0, y1, x0, x1]. A region-shaded (%) node additionally contributes the shade's padded bounding rect so that neighboring subtrees keep clear of the plane.



600
601
602
603
604
605
606
607
608
609
610
611
612
 
# File 'lib/rsyntaxtree/base_graph.rb', line 600

def subtree_rects(id)
  node = @element_list.get_id(id)
  rects = [effective_rect(node)]
  node.children.each { |c| rects.concat(subtree_rects(c)) }
  if node.region
    pad = @global[:h_gap_between_nodes]
    rects << [rects.map { |r| r[0] }.min - pad / 2.0,
              rects.map { |r| r[1] }.max + pad,
              rects.map { |r| r[2] }.min - pad,
              rects.map { |r| r[3] }.max + pad]
  end
  rects
end

#subtree_right(id) ⇒ Object

Right edge of the subtree rooted at id, from wherever the layout has put things so far.



590
591
592
593
594
595
 
# File 'lib/rsyntaxtree/base_graph.rb', line 590

def subtree_right(id)
  node = @element_list.get_id(id)
  right = node.horizontal_indent + node.content_width
  node.children.each { |c| right = [right, subtree_right(c)].max }
  right
end

#tidy_compress ⇒ Object

One compression pass. For each internal node (deepest first), adjacent child subtrees are pulled together until (a) their contours clear each other by tidy_gap and (b) — unless tidy_nest is on — the leftmost leaf of the right subtree stays right of the rightmost leaf of the left subtree; (b) keeps the global leaf order intact even where the two subtrees never share a y band (contours alone cannot see that case). With tidy_nest on, only (a) applies: elements on the same visual row still keep their order and spacing, but a shallow subtree may nest above the deep tail of its neighbor (e.g. a spec NP tucking toward the head across rows) — leaf x-order is then guaranteed within rows, not globally. A negative clearance (possible when the previous height recalculation raised nodes into a shared y band) pushes the right subtree back out — the dynamic connector height couples y to the horizontal spread, so passes must run in both directions to reach a fixpoint. Moving the right subtree only ever drives the gap to its left neighbor toward the constraints and grows the gap to its right neighbor, so a single left-to-right sweep per parent cannot create new collisions; non-adjacent subtrees stay separated transitively. The parent is then re-centered over its children (node_centering rule).

Returns the largest absolute shift applied (for convergence testing).



710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
 
# File 'lib/rsyntaxtree/base_graph.rb', line 710

def tidy_compress
  max_shift = 0.0
  parents = @element_list.get_elements.reject { |e| e.children.empty? }
  parents.sort_by { |p| [-p.level, -p.id] }.each do |parent|
    children = parent.children.map { |c| @element_list.get_id(c) }
    children.each_cons(2) do |left_child, right_child|
      clearance = contour_clearance(subtree_rects(left_child.id), subtree_rects(right_child.id))
      delta = clearance.nil? ? 0.0 : tidy_gap - clearance

      case @tidy_nest
      when :none
        # Strict leaf positions: the right subtree's leaves stay a full
        # gap right of the left subtree's leaves.
        left_span = subtree_leaf_span(left_child.id)
        right_span = subtree_leaf_span(right_child.id)
        if left_span && right_span
          leaf_delta = left_span[1] + tidy_gap - right_span[0]
          delta = leaf_delta if leaf_delta > delta
        end
      when :ordered
        # Leaf boxes may overlap across rows, but no leaf of the right
        # subtree may move left past a leaf of the left subtree: leaf
        # centers keep their left-to-right (word) order.
        left_centers = subtree_leaf_center_span(left_child.id)
        right_centers = subtree_leaf_center_span(right_child.id)
        if left_centers && right_centers
          order_delta = left_centers[1] + 1.0 - right_centers[0]
          delta = order_delta if order_delta > delta
        end
      end

      # Level-balance floor (:ordered only): keep the pair at least a
      # fraction of the widest child-level spread found inside its own
      # two subtrees. Nesting can tuck an upper pair far narrower than
      # the level right below it — an inversion that reads as a
      # needle-thin top over flat lower branches.
      #
      # :none does not need it, since the leaf-span guard already
      # prevents such inversions. :free deliberately goes without: it is
      # the end of the scale where density outranks even branch angles,
      # and with the floor in place it compressed no further than
      # :ordered on all but a handful of trees.
      #
      # Compression is a negative delta (the right subtree moves left),
      # so the floor bounds delta from below.
      if @tidy_nest == :ordered && delta.negative?
        dist = (right_child.horizontal_indent + right_child.content_width / 2.0) -
               (left_child.horizontal_indent + left_child.content_width / 2.0)
        below = [left_child, right_child].map { |c| child_spread(c) }.compact.max
        if below
          min_dist = below * TIDY_LEVEL_BALANCE
          delta = [delta, min_dist - dist].max
        end
      end
      next if delta.abs < 0.01

      shift_subtree(right_child.id, delta)
      max_shift = delta.abs if delta.abs > max_shift
    end
    centers = children.map { |c| c.horizontal_indent + c.content_width / 2.0 }
    parent.horizontal_indent = centers.min + (centers.max - centers.min - parent.content_width) / 2
  end
  max_shift
end

#tidy_gap ⇒ Object

Minimum horizontal clearance kept between adjacent subtrees. The global hspacing factor is already baked into h_gap_between_nodes.



560
561
562
 
# File 'lib/rsyntaxtree/base_graph.rb', line 560

def tidy_gap
  @global[:h_gap_between_nodes] * TIDY_BASE_SPACING
end

#triangle_asked_for?(parent, child) ⇒ Boolean

Whether a ^ has asked for a triangle over this leaf. It may be written at the head of the node's label or at the head of the leaf's own text — [^NP cats] and [NP ^cats] — and both forms are in the gallery. Only the first was honoured here, and the second was dropped without a word: the caret vanished from the text and a bar was drawn, so an example named for its triangles had none. The rest of the layout already reads the leaf's own flag — a leaf marked this way keeps the gap a triangle needs even when connectors are off — which is what left the two sides of one rule disagreeing.

Asked of a leaf only. A ^ on an internal node is that node's own mark, and it is honoured when that node is in turn the parent here.

Returns:

  • (Boolean) 


415
416
417
 
# File 'lib/rsyntaxtree/base_graph.rb', line 415

def triangle_asked_for?(parent, child)
  parent.triangle || (ETYPE_LEAF == child.type && child.triangle)
end