Source file src/oss.terrastruct.com/d2/d2layouts/d2grid/layout.go

Documentation: oss.terrastruct.com/d2/d2layouts/d2grid

     1  package d2grid
     2  
     3  import (
     4  	"bytes"
     5  	"context"
     6  	"fmt"
     7  	"math"
     8  
     9  	"oss.terrastruct.com/d2/d2graph"
    10  	"oss.terrastruct.com/d2/d2target"
    11  	"oss.terrastruct.com/d2/lib/geo"
    12  	"oss.terrastruct.com/d2/lib/label"
    13  	"oss.terrastruct.com/util-go/go2"
    14  )
    15  
    16  const (
    17  	CONTAINER_PADDING = 60
    18  	DEFAULT_GAP       = 40
    19  )
    20  
    21  // Layout runs the grid layout on containers with rows/columns
    22  // Note: children are not allowed edges or descendants
    23  // 1. Run grid layout on the graph root
    24  // 2. Set the resulting dimensions to the graph root
    25  func Layout(ctx context.Context, g *d2graph.Graph) error {
    26  	obj := g.Root
    27  
    28  	gd, err := layoutGrid(g, obj)
    29  	if err != nil {
    30  		return err
    31  	}
    32  
    33  	if obj.HasLabel() && obj.LabelPosition == nil {
    34  		obj.LabelPosition = go2.Pointer(label.InsideTopCenter.String())
    35  	}
    36  	if obj.Icon != nil && obj.IconPosition == nil {
    37  		obj.IconPosition = go2.Pointer(label.InsideTopLeft.String())
    38  	}
    39  
    40  	if obj.Box != nil {
    41  		// CONTAINER_PADDING is default, but use gap value if set
    42  		horizontalPadding, verticalPadding := CONTAINER_PADDING, CONTAINER_PADDING
    43  		if obj.GridGap != nil || obj.HorizontalGap != nil {
    44  			horizontalPadding = gd.horizontalGap
    45  		}
    46  		if obj.GridGap != nil || obj.VerticalGap != nil {
    47  			verticalPadding = gd.verticalGap
    48  		}
    49  
    50  		contentWidth, contentHeight := gd.width, gd.height
    51  
    52  		var labelPosition, iconPosition label.Position
    53  		if obj.LabelPosition != nil {
    54  			labelPosition = label.FromString(*obj.LabelPosition)
    55  		}
    56  		if obj.IconPosition != nil {
    57  			iconPosition = label.FromString(*obj.IconPosition)
    58  		}
    59  
    60  		// compute how much space the label and icon occupy
    61  		_, padding := obj.Spacing()
    62  
    63  		var labelWidth, labelHeight float64
    64  		if obj.LabelDimensions.Width > 0 {
    65  			labelWidth = float64(obj.LabelDimensions.Width) + 2*label.PADDING
    66  		}
    67  		if obj.LabelDimensions.Height > 0 {
    68  			labelHeight = float64(obj.LabelDimensions.Height) + 2*label.PADDING
    69  		}
    70  
    71  		if labelWidth > 0 {
    72  			switch labelPosition {
    73  			case label.OutsideTopLeft, label.OutsideTopCenter, label.OutsideTopRight,
    74  				label.InsideTopLeft, label.InsideTopCenter, label.InsideTopRight,
    75  				label.InsideBottomLeft, label.InsideBottomCenter, label.InsideBottomRight,
    76  				label.OutsideBottomLeft, label.OutsideBottomCenter, label.OutsideBottomRight:
    77  				overflow := labelWidth - contentWidth
    78  				if overflow > 0 {
    79  					padding.Left += overflow / 2
    80  					padding.Right += overflow / 2
    81  				}
    82  			}
    83  		}
    84  		if labelHeight > 0 {
    85  			switch labelPosition {
    86  			case label.OutsideLeftTop, label.OutsideLeftMiddle, label.OutsideLeftBottom,
    87  				label.InsideMiddleLeft, label.InsideMiddleCenter, label.InsideMiddleRight,
    88  				label.OutsideRightTop, label.OutsideRightMiddle, label.OutsideRightBottom:
    89  				overflow := labelHeight - contentHeight
    90  				if overflow > 0 {
    91  					padding.Top += overflow / 2
    92  					padding.Bottom += overflow / 2
    93  				}
    94  			}
    95  		}
    96  
    97  		// configure spacing for default label+icon
    98  		if iconPosition == label.InsideTopLeft && labelPosition == label.InsideTopCenter {
    99  			// . ├────┤───────├────┤
   100  			// .  icon  label  icon
   101  			// with an icon in top left we need 2x the space to fit the label in the center
   102  			iconSize := float64(d2target.MAX_ICON_SIZE) + 2*label.PADDING
   103  			padding.Left = math.Max(padding.Left, iconSize)
   104  			padding.Right = math.Max(padding.Right, iconSize)
   105  			minWidth := 2*iconSize + float64(obj.LabelDimensions.Width) + 2*label.PADDING
   106  			overflow := minWidth - contentWidth
   107  			if overflow > 0 {
   108  				padding.Left = math.Max(padding.Left, overflow/2)
   109  				padding.Right = math.Max(padding.Right, overflow/2)
   110  			}
   111  		}
   112  
   113  		padding.Top = math.Max(padding.Top, float64(verticalPadding))
   114  		padding.Bottom = math.Max(padding.Bottom, float64(verticalPadding))
   115  		padding.Left = math.Max(padding.Left, float64(horizontalPadding))
   116  		padding.Right = math.Max(padding.Right, float64(horizontalPadding))
   117  
   118  		totalWidth := padding.Left + contentWidth + padding.Right
   119  		totalHeight := padding.Top + contentHeight + padding.Bottom
   120  		obj.SizeToContent(totalWidth, totalHeight, 0, 0)
   121  
   122  		// compute where the grid should be placed inside shape
   123  		s := obj.ToShape()
   124  		innerTL := s.GetInsidePlacement(totalWidth, totalHeight, 0, 0)
   125  		// depending on the shape innerBox may be larger than totalWidth, totalHeight
   126  		// if this is the case, we want to center the cells within the larger innerBox
   127  		innerBox := s.GetInnerBox()
   128  		var resizeDx, resizeDy float64
   129  		if innerBox.Width > totalWidth {
   130  			resizeDx = (innerBox.Width - totalWidth) / 2
   131  		}
   132  		if innerBox.Height > totalHeight {
   133  			resizeDy = (innerBox.Height - totalHeight) / 2
   134  		}
   135  
   136  		// move from horizontalPadding,verticalPadding to innerTL.X+padding.Left, innerTL.Y+padding.Top
   137  		// and if innerBox is larger than content dimensions, adjust to center within innerBox
   138  		dx := -float64(horizontalPadding) + innerTL.X + padding.Left + resizeDx
   139  		dy := -float64(verticalPadding) + innerTL.Y + padding.Top + resizeDy
   140  		if dx != 0 || dy != 0 {
   141  			gd.shift(dx, dy)
   142  		}
   143  	}
   144  
   145  	// simple straight line edge routing between grid objects
   146  	for _, e := range g.Edges {
   147  		if !e.Src.Parent.IsDescendantOf(obj) && !e.Dst.Parent.IsDescendantOf(obj) {
   148  			continue
   149  		}
   150  		// if edge is within grid, remove it from outer layout
   151  		gd.edges = append(gd.edges, e)
   152  
   153  		if e.Src.Parent != obj || e.Dst.Parent != obj {
   154  			continue
   155  		}
   156  		// if edge is grid child, use simple routing
   157  		e.Route = []*geo.Point{e.Src.Center(), e.Dst.Center()}
   158  		e.TraceToShape(e.Route, 0, 1)
   159  		if e.Label.Value != "" {
   160  			e.LabelPosition = go2.Pointer(label.InsideMiddleCenter.String())
   161  		}
   162  	}
   163  
   164  	if g.Root.IsGridDiagram() && len(g.Root.ChildrenArray) != 0 {
   165  		g.Root.TopLeft = geo.NewPoint(0, 0)
   166  	}
   167  
   168  	if g.RootLevel > 0 {
   169  		horizontalPadding, verticalPadding := CONTAINER_PADDING, CONTAINER_PADDING
   170  		if obj.GridGap != nil || obj.HorizontalGap != nil {
   171  			horizontalPadding = gd.horizontalGap
   172  		}
   173  		if obj.GridGap != nil || obj.VerticalGap != nil {
   174  			verticalPadding = gd.verticalGap
   175  		}
   176  
   177  		// shift the grid from (0, 0)
   178  		gd.shift(
   179  			obj.TopLeft.X+float64(horizontalPadding),
   180  			obj.TopLeft.Y+float64(verticalPadding),
   181  		)
   182  	}
   183  	return nil
   184  }
   185  
   186  func layoutGrid(g *d2graph.Graph, obj *d2graph.Object) (*gridDiagram, error) {
   187  	gd := newGridDiagram(obj)
   188  
   189  	// position labels and icons
   190  	for _, o := range gd.objects {
   191  		positionedLabel := false
   192  		if o.Icon != nil && o.IconPosition == nil {
   193  			if len(o.ChildrenArray) > 0 {
   194  				o.IconPosition = go2.Pointer(label.OutsideTopLeft.String())
   195  				// don't overwrite position if nested graph layout positioned label/icon
   196  				if o.LabelPosition == nil {
   197  					o.LabelPosition = go2.Pointer(label.OutsideTopRight.String())
   198  					positionedLabel = true
   199  				}
   200  			} else {
   201  				o.IconPosition = go2.Pointer(label.InsideMiddleCenter.String())
   202  			}
   203  		}
   204  		if !positionedLabel && o.HasLabel() && o.LabelPosition == nil {
   205  			if len(o.ChildrenArray) > 0 {
   206  				o.LabelPosition = go2.Pointer(label.OutsideTopCenter.String())
   207  			} else if o.HasOutsideBottomLabel() {
   208  				o.LabelPosition = go2.Pointer(label.OutsideBottomCenter.String())
   209  			} else if o.Icon != nil {
   210  				o.LabelPosition = go2.Pointer(label.InsideTopCenter.String())
   211  			} else {
   212  				o.LabelPosition = go2.Pointer(label.InsideMiddleCenter.String())
   213  			}
   214  		}
   215  	}
   216  
   217  	// to handle objects with outside labels, we adjust their dimensions before layout and
   218  	// after layout, we remove the label adjustment and reposition TopLeft if needed
   219  	revertAdjustments := gd.sizeForOutsideLabels()
   220  
   221  	if gd.rows != 0 && gd.columns != 0 {
   222  		gd.layoutEvenly(g, obj)
   223  	} else {
   224  		gd.layoutDynamic(g, obj)
   225  	}
   226  
   227  	revertAdjustments()
   228  
   229  	return gd, nil
   230  }
   231  
   232  func (gd *gridDiagram) layoutEvenly(g *d2graph.Graph, obj *d2graph.Object) {
   233  	// layout objects in a grid with these 2 properties:
   234  	// all objects in the same row should have the same height
   235  	// all objects in the same column should have the same width
   236  
   237  	getObject := func(rowIndex, columnIndex int) *d2graph.Object {
   238  		var index int
   239  		if gd.rowDirected {
   240  			index = rowIndex*gd.columns + columnIndex
   241  		} else {
   242  			index = columnIndex*gd.rows + rowIndex
   243  		}
   244  		if index < len(gd.objects) {
   245  			return gd.objects[index]
   246  		}
   247  		return nil
   248  	}
   249  
   250  	rowHeights := make([]float64, 0, gd.rows)
   251  	colWidths := make([]float64, 0, gd.columns)
   252  	for i := 0; i < gd.rows; i++ {
   253  		rowHeight := 0.
   254  		for j := 0; j < gd.columns; j++ {
   255  			o := getObject(i, j)
   256  			if o == nil {
   257  				break
   258  			}
   259  			rowHeight = math.Max(rowHeight, o.Height)
   260  		}
   261  		rowHeights = append(rowHeights, rowHeight)
   262  	}
   263  	for j := 0; j < gd.columns; j++ {
   264  		columnWidth := 0.
   265  		for i := 0; i < gd.rows; i++ {
   266  			o := getObject(i, j)
   267  			if o == nil {
   268  				break
   269  			}
   270  			columnWidth = math.Max(columnWidth, o.Width)
   271  		}
   272  		colWidths = append(colWidths, columnWidth)
   273  	}
   274  
   275  	horizontalGap := float64(gd.horizontalGap)
   276  	verticalGap := float64(gd.verticalGap)
   277  
   278  	cursor := geo.NewPoint(0, 0)
   279  	if gd.rowDirected {
   280  		for i := 0; i < gd.rows; i++ {
   281  			for j := 0; j < gd.columns; j++ {
   282  				o := getObject(i, j)
   283  				if o == nil {
   284  					break
   285  				}
   286  				o.Width = colWidths[j]
   287  				o.Height = rowHeights[i]
   288  				o.MoveWithDescendantsTo(cursor.X, cursor.Y)
   289  				cursor.X += o.Width + horizontalGap
   290  			}
   291  			cursor.X = 0
   292  			cursor.Y += rowHeights[i] + verticalGap
   293  		}
   294  	} else {
   295  		for j := 0; j < gd.columns; j++ {
   296  			for i := 0; i < gd.rows; i++ {
   297  				o := getObject(i, j)
   298  				if o == nil {
   299  					break
   300  				}
   301  				o.Width = colWidths[j]
   302  				o.Height = rowHeights[i]
   303  				o.MoveWithDescendantsTo(cursor.X, cursor.Y)
   304  				cursor.Y += o.Height + verticalGap
   305  			}
   306  			cursor.X += colWidths[j] + horizontalGap
   307  			cursor.Y = 0
   308  		}
   309  	}
   310  
   311  	var totalWidth, totalHeight float64
   312  	for _, w := range colWidths {
   313  		totalWidth += w + horizontalGap
   314  	}
   315  	for _, h := range rowHeights {
   316  		totalHeight += h + verticalGap
   317  	}
   318  	totalWidth -= horizontalGap
   319  	totalHeight -= verticalGap
   320  	gd.width = totalWidth
   321  	gd.height = totalHeight
   322  }
   323  
   324  func (gd *gridDiagram) layoutDynamic(g *d2graph.Graph, obj *d2graph.Object) {
   325  	// assume we have the following objects to layout:
   326  	// . ┌A──────────────┐  ┌B──┐  ┌C─────────┐  ┌D────────┐  ┌E────────────────┐
   327  	// . └───────────────┘  │   │  │          │  │         │  │                 │
   328  	// .                    │   │  └──────────┘  │         │  │                 │
   329  	// .                    │   │                │         │  └─────────────────┘
   330  	// .                    └───┘                │         │
   331  	// .                                         └─────────┘
   332  	// Note: if the grid is row dominant, all objects should be the same height (same width if column dominant)
   333  	// . ┌A─────────────┐  ┌B──┐  ┌C─────────┐  ┌D────────┐  ┌E────────────────┐
   334  	// . ├ ─ ─ ─ ─ ─ ─ ─┤  │   │  │          │  │         │  │                 │
   335  	// . │              │  │   │  ├ ─ ─ ─ ─ ─┤  │         │  │                 │
   336  	// . │              │  │   │  │          │  │         │  ├ ─ ─ ─ ─ ─ ─ ─ ─ ┤
   337  	// . │              │  ├ ─ ┤  │          │  │         │  │                 │
   338  	// . └──────────────┘  └───┘  └──────────┘  └─────────┘  └─────────────────┘
   339  
   340  	horizontalGap := float64(gd.horizontalGap)
   341  	verticalGap := float64(gd.verticalGap)
   342  
   343  	// we want to split up the total width across the N rows or columns as evenly as possible
   344  	var totalWidth, totalHeight float64
   345  	for _, o := range gd.objects {
   346  		totalWidth += o.Width
   347  		totalHeight += o.Height
   348  	}
   349  	totalWidth += horizontalGap * float64(len(gd.objects)-gd.rows)
   350  	totalHeight += verticalGap * float64(len(gd.objects)-gd.columns)
   351  
   352  	var layout [][]*d2graph.Object
   353  	if gd.rowDirected {
   354  		targetWidth := totalWidth / float64(gd.rows)
   355  		layout = gd.getBestLayout(targetWidth, false)
   356  	} else {
   357  		targetHeight := totalHeight / float64(gd.columns)
   358  		layout = gd.getBestLayout(targetHeight, true)
   359  	}
   360  
   361  	cursor := geo.NewPoint(0, 0)
   362  	var maxY, maxX float64
   363  	if gd.rowDirected {
   364  		// measure row widths
   365  		rowWidths := []float64{}
   366  		for _, row := range layout {
   367  			x := 0.
   368  			for _, o := range row {
   369  				x += o.Width + horizontalGap
   370  			}
   371  			rowWidth := x - horizontalGap
   372  			rowWidths = append(rowWidths, rowWidth)
   373  			maxX = math.Max(maxX, rowWidth)
   374  		}
   375  
   376  		// TODO if object is a nested grid, consider growing descendants according to the inner grid layout
   377  
   378  		// then expand thinnest objects to make each row the same width
   379  		// . ┌A─────────────┐  ┌B──┐  ┌C─────────┐ ┬ maxHeight(A,B,C)
   380  		// . │              │  │   │  │          │ │
   381  		// . │              │  │   │  │          │ │
   382  		// . │              │  │   │  │          │ │
   383  		// . └──────────────┘  └───┘  └──────────┘ ┴
   384  		// . ┌D────────┬────┐  ┌E────────────────┐ ┬ maxHeight(D,E)
   385  		// . │              │  │                 │ │
   386  		// . │         │    │  │                 │ │
   387  		// . │              │  │                 │ │
   388  		// . │         │    │  │                 │ │
   389  		// . └─────────┴────┘  └─────────────────┘ ┴
   390  		for i, row := range layout {
   391  			rowWidth := rowWidths[i]
   392  			if rowWidth == maxX {
   393  				continue
   394  			}
   395  			delta := maxX - rowWidth
   396  			var widest float64
   397  			for _, o := range row {
   398  				widest = math.Max(widest, o.Width)
   399  			}
   400  			diffs := make([]float64, len(row))
   401  			totalDiff := 0.
   402  			for i, o := range row {
   403  				diffs[i] = widest - o.Width
   404  				totalDiff += diffs[i]
   405  			}
   406  			if totalDiff > 0 {
   407  				// expand smaller nodes up to the size of the larger ones with delta
   408  				// percentage diff
   409  				for i := range diffs {
   410  					diffs[i] /= totalDiff
   411  				}
   412  				growth := math.Min(delta, totalDiff)
   413  				// expand smaller objects to fill remaining space
   414  				for i, o := range row {
   415  					o.Width += diffs[i] * growth
   416  				}
   417  			}
   418  			if delta > totalDiff {
   419  				growth := (delta - totalDiff) / float64(len(row))
   420  				for _, o := range row {
   421  					o.Width += growth
   422  				}
   423  			}
   424  		}
   425  
   426  		// if we have 2 rows, then each row's objects should have the same height
   427  		// . ┌A─────────────┐  ┌B──┐  ┌C─────────┐ ┬ maxHeight(A,B,C)
   428  		// . ├ ─ ─ ─ ─ ─ ─ ─┤  │   │  │          │ │
   429  		// . │              │  │   │  ├ ─ ─ ─ ─ ─┤ │
   430  		// . │              │  │   │  │          │ │
   431  		// . └──────────────┘  └───┘  └──────────┘ ┴
   432  		// . ┌D────────┐  ┌E────────────────┐ ┬ maxHeight(D,E)
   433  		// . │         │  │                 │ │
   434  		// . │         │  │                 │ │
   435  		// . │         │  ├ ─ ─ ─ ─ ─ ─ ─ ─ ┤ │
   436  		// . │         │  │                 │ │
   437  		// . └─────────┘  └─────────────────┘ ┴
   438  		for _, row := range layout {
   439  			rowHeight := 0.
   440  			for _, o := range row {
   441  				o.MoveWithDescendantsTo(cursor.X, cursor.Y)
   442  				cursor.X += o.Width + horizontalGap
   443  				rowHeight = math.Max(rowHeight, o.Height)
   444  			}
   445  
   446  			// set all objects in row to the same height
   447  			for _, o := range row {
   448  				o.Height = rowHeight
   449  			}
   450  
   451  			// new row
   452  			cursor.X = 0
   453  			cursor.Y += rowHeight + verticalGap
   454  		}
   455  		maxY = cursor.Y - verticalGap
   456  	} else {
   457  		// measure column heights
   458  		colHeights := []float64{}
   459  		for _, column := range layout {
   460  			y := 0.
   461  			for _, o := range column {
   462  				y += o.Height + verticalGap
   463  			}
   464  			colHeight := y - verticalGap
   465  			colHeights = append(colHeights, colHeight)
   466  			maxY = math.Max(maxY, colHeight)
   467  		}
   468  
   469  		// then expand shortest objects to make each column the same height
   470  		// . ├maxWidth(A,B)─┤  ├maxW(C,D)─┤  ├maxWidth(E)──────┤
   471  		// . ┌A─────────────┐  ┌C─────────┐  ┌E────────────────┐
   472  		// . ├ ─ ─ ─ ─ ─ ─  ┤  │          │  │                 │
   473  		// . │              │  └──────────┘  │                 │
   474  		// . └──────────────┘  ┌D─────────┐  ├ ─ ─ ─ ─ ─ ─ ─ ─ ┤
   475  		// . ┌B─────────────┐  │          │  │                 │
   476  		// . │              │  │          │  │                 │
   477  		// . │              │  │          │  │                 │
   478  		// . │              │  │          │  │                 │
   479  		// . └──────────────┘  └──────────┘  └─────────────────┘
   480  		for i, column := range layout {
   481  			colHeight := colHeights[i]
   482  			if colHeight == maxY {
   483  				continue
   484  			}
   485  			delta := maxY - colHeight
   486  			var tallest float64
   487  			for _, o := range column {
   488  				tallest = math.Max(tallest, o.Height)
   489  			}
   490  			diffs := make([]float64, len(column))
   491  			totalDiff := 0.
   492  			for i, o := range column {
   493  				diffs[i] = tallest - o.Height
   494  				totalDiff += diffs[i]
   495  			}
   496  			if totalDiff > 0 {
   497  				// expand smaller nodes up to the size of the larger ones with delta
   498  				// percentage diff
   499  				for i := range diffs {
   500  					diffs[i] /= totalDiff
   501  				}
   502  				growth := math.Min(delta, totalDiff)
   503  				// expand smaller objects to fill remaining space
   504  				for i, o := range column {
   505  					o.Height += diffs[i] * growth
   506  				}
   507  			}
   508  			if delta > totalDiff {
   509  				growth := (delta - totalDiff) / float64(len(column))
   510  				for _, o := range column {
   511  					o.Height += growth
   512  				}
   513  			}
   514  		}
   515  		// if we have 3 columns, then each column's objects should have the same width
   516  		// . ├maxWidth(A,B)─┤  ├maxW(C,D)─┤  ├maxWidth(E)──────┤
   517  		// . ┌A─────────────┐  ┌C─────────┐  ┌E────────────────┐
   518  		// . └──────────────┘  │          │  │                 │
   519  		// . ┌B──┬──────────┐  └──────────┘  │                 │
   520  		// . │              │  ┌D────────┬┐  └─────────────────┘
   521  		// . │   │          │  │          │
   522  		// . │              │  │         ││
   523  		// . └───┴──────────┘  │          │
   524  		// .                   │         ││
   525  		// .                   └─────────┴┘
   526  		for _, column := range layout {
   527  			colWidth := 0.
   528  			for _, o := range column {
   529  				o.MoveWithDescendantsTo(cursor.X, cursor.Y)
   530  				cursor.Y += o.Height + verticalGap
   531  				colWidth = math.Max(colWidth, o.Width)
   532  			}
   533  			// set all objects in column to the same width
   534  			for _, o := range column {
   535  				o.Width = colWidth
   536  			}
   537  
   538  			// new column
   539  			cursor.Y = 0
   540  			cursor.X += colWidth + horizontalGap
   541  		}
   542  		maxX = cursor.X - horizontalGap
   543  	}
   544  	gd.width = maxX
   545  	gd.height = maxY
   546  }
   547  
   548  // generate the best layout of objects aiming for each row to be the targetSize width
   549  // if columns is true, each column aims to have the targetSize height
   550  func (gd *gridDiagram) getBestLayout(targetSize float64, columns bool) [][]*d2graph.Object {
   551  	debug := false
   552  	var nCuts int
   553  	if columns {
   554  		nCuts = gd.columns - 1
   555  	} else {
   556  		nCuts = gd.rows - 1
   557  	}
   558  	if nCuts == 0 {
   559  		return GenLayout(gd.objects, nil)
   560  	}
   561  
   562  	var bestLayout [][]*d2graph.Object
   563  	bestDist := math.MaxFloat64
   564  	fastIsBest := false
   565  	// try fast layout algorithm as a baseline
   566  	if fastLayout := gd.fastLayout(targetSize, nCuts, columns); fastLayout != nil {
   567  		dist := getDistToTarget(fastLayout, targetSize, float64(gd.horizontalGap), float64(gd.verticalGap), columns)
   568  		if debug {
   569  			fmt.Printf("fast dist %v dist per row %v\n", dist, dist/(float64(nCuts)+1))
   570  		}
   571  		if dist == 0 {
   572  			return fastLayout
   573  		}
   574  		bestDist = dist
   575  		bestLayout = fastLayout
   576  		fastIsBest = true
   577  	}
   578  
   579  	var gap float64
   580  	if columns {
   581  		gap = float64(gd.verticalGap)
   582  	} else {
   583  		gap = float64(gd.horizontalGap)
   584  	}
   585  	getSize := func(o *d2graph.Object) float64 {
   586  		if columns {
   587  			return o.Height
   588  		} else {
   589  			return o.Width
   590  		}
   591  	}
   592  
   593  	sizes := []float64{}
   594  	for _, obj := range gd.objects {
   595  		size := getSize(obj)
   596  		sizes = append(sizes, size)
   597  	}
   598  	sd := stddev(sizes)
   599  	if debug {
   600  		fmt.Printf("sizes (%d): %v\n", len(sizes), sizes)
   601  		fmt.Printf("std dev: %v; targetSize %v\n", sd, targetSize)
   602  	}
   603  
   604  	skipCount := 0
   605  	count := 0
   606  	// quickly eliminate bad row groupings
   607  	startingCache := make(map[int]bool)
   608  	// Note: we want a low threshold to explore good options within attemptLimit,
   609  	// but the best option may require a few rows that are far from the target size.
   610  	okThreshold := STARTING_THRESHOLD
   611  	rowOk := func(row []*d2graph.Object, starting bool) (ok bool) {
   612  		if starting {
   613  			// we can cache results from starting positions since they repeat and don't change
   614  			// with starting=true it will always be the 1st N objects based on len(row)
   615  			if ok, has := startingCache[len(row)]; has {
   616  				return ok
   617  			}
   618  			defer func() {
   619  				// cache result before returning
   620  				startingCache[len(row)] = ok
   621  			}()
   622  		}
   623  
   624  		rowSize := 0.
   625  		for _, obj := range row {
   626  			rowSize += getSize(obj)
   627  		}
   628  		if len(row) > 1 {
   629  			rowSize += gap * float64(len(row)-1)
   630  			// if multiple nodes are too big, it isn't ok. but a single node can't shrink so only check here
   631  			if rowSize > okThreshold*targetSize {
   632  				skipCount++
   633  				// there may even be too many to skip
   634  				return skipCount >= SKIP_LIMIT
   635  			}
   636  		}
   637  		// row is too small to be good overall
   638  		if rowSize < targetSize/okThreshold {
   639  			skipCount++
   640  			return skipCount >= SKIP_LIMIT
   641  		}
   642  		return true
   643  	}
   644  
   645  	// get all options for where to place these cuts, preferring later cuts over earlier cuts
   646  	// with 5 objects and 2 cuts we have these options:
   647  	// .       A   B   C │ D │ E     <- these cuts would produce: ┌A─┐ ┌B─┐ ┌C─┐
   648  	// .       A   B │ C   D │ E                                  └──┘ └──┘ └──┘
   649  	// .       A │ B   C   D │ E                                  ┌D───────────┐
   650  	// .       A   B │ C │ D   E                                  └────────────┘
   651  	// .       A │ B   C │ D   E                                  ┌E───────────┐
   652  	// .       A │ B │ C   D   E                                  └────────────┘
   653  	// of these divisions, find the layout with rows closest to the targetSize
   654  	tryDivision := func(division []int) bool {
   655  		layout := GenLayout(gd.objects, division)
   656  		dist := getDistToTarget(layout, targetSize, float64(gd.horizontalGap), float64(gd.verticalGap), columns)
   657  		if dist < bestDist {
   658  			bestLayout = layout
   659  			bestDist = dist
   660  			fastIsBest = false
   661  		} else if fastIsBest && dist == bestDist {
   662  			// prefer ordered search solution to fast layout solution
   663  			bestLayout = layout
   664  			fastIsBest = false
   665  		}
   666  		count++
   667  		// with few objects we can try all options to get best result but this won't scale, so only try up to 100k options
   668  		return count >= ATTEMPT_LIMIT || skipCount >= SKIP_LIMIT
   669  	}
   670  
   671  	// try number of different okThresholds depending on std deviation of sizes
   672  	thresholdAttempts := int(math.Ceil(sd))
   673  	if thresholdAttempts < MIN_THRESHOLD_ATTEMPTS {
   674  		thresholdAttempts = MIN_THRESHOLD_ATTEMPTS
   675  	} else if thresholdAttempts > MAX_THRESHOLD_ATTEMPTS {
   676  		thresholdAttempts = MAX_THRESHOLD_ATTEMPTS
   677  	}
   678  	for i := 0; i < thresholdAttempts || bestLayout == nil; i++ {
   679  		count = 0.
   680  		skipCount = 0.
   681  		iterDivisions(gd.objects, nCuts, tryDivision, rowOk)
   682  		okThreshold += THRESHOLD_STEP_SIZE
   683  		if debug {
   684  			fmt.Printf("count %d, skip count %d, bestDist %v increasing ok threshold to %v\n", count, skipCount, bestDist, okThreshold)
   685  		}
   686  		startingCache = make(map[int]bool)
   687  		if skipCount == 0 {
   688  			// threshold isn't skipping anything so increasing it won't help
   689  			break
   690  		}
   691  		// okThreshold isn't high enough yet, we skipped every option so don't count it
   692  		if count == 0 && thresholdAttempts < MAX_THRESHOLD_ATTEMPTS {
   693  			thresholdAttempts++
   694  		}
   695  	}
   696  
   697  	if debug {
   698  		fmt.Printf("best layout: %v\n", layoutString(bestLayout, sizes))
   699  	}
   700  	return bestLayout
   701  }
   702  
   703  func sum(values []float64) float64 {
   704  	s := 0.
   705  	for _, v := range values {
   706  		s += v
   707  	}
   708  	return s
   709  }
   710  
   711  func avg(values []float64) float64 {
   712  	return sum(values) / float64(len(values))
   713  }
   714  
   715  func variance(values []float64) float64 {
   716  	mean := avg(values)
   717  	total := 0.
   718  	for _, value := range values {
   719  		dev := mean - value
   720  		total += dev * dev
   721  	}
   722  	return total / float64(len(values))
   723  }
   724  
   725  func stddev(values []float64) float64 {
   726  	return math.Sqrt(variance(values))
   727  }
   728  
   729  func (gd *gridDiagram) fastLayout(targetSize float64, nCuts int, columns bool) (layout [][]*d2graph.Object) {
   730  	var gap float64
   731  	if columns {
   732  		gap = float64(gd.verticalGap)
   733  	} else {
   734  		gap = float64(gd.horizontalGap)
   735  	}
   736  
   737  	debt := 0.
   738  	fastDivision := make([]int, 0, nCuts)
   739  	rowSize := 0.
   740  	for i := 0; i < len(gd.objects); i++ {
   741  		o := gd.objects[i]
   742  		var size float64
   743  		if columns {
   744  			size = o.Height
   745  		} else {
   746  			size = o.Width
   747  		}
   748  		if rowSize == 0 {
   749  			// if a single object meets the target size, end the row here
   750  			if size > targetSize-debt {
   751  				// cut row with just this object
   752  				fastDivision = append(fastDivision, i)
   753  				// we build up a debt of distance past the target size across rows
   754  				newDebt := size - targetSize
   755  				debt += newDebt
   756  			} else {
   757  				rowSize += size
   758  			}
   759  			continue
   760  		}
   761  		// debt is paid by decreasing threshold to start new row and ending below targetSize
   762  		if rowSize+gap+(size)/2. > targetSize-debt {
   763  			// start a new row before this object since it is mostly past the target size
   764  			// .              size
   765  			// ├...row─┼gap┼───┼───┤
   766  			// ├──targetSize──┤ (debt=0)
   767  			fastDivision = append(fastDivision, i-1)
   768  			newDebt := rowSize - targetSize
   769  			debt += newDebt
   770  			rowSize = size
   771  		} else {
   772  			rowSize += gap + size
   773  		}
   774  	}
   775  	if len(fastDivision) == nCuts {
   776  		layout = GenLayout(gd.objects, fastDivision)
   777  	}
   778  
   779  	return layout
   780  }
   781  
   782  func layoutString(layout [][]*d2graph.Object, sizes []float64) string {
   783  	buf := &bytes.Buffer{}
   784  	i := 0
   785  	fmt.Fprintf(buf, "[\n")
   786  	for _, r := range layout {
   787  		vals := sizes[i : i+len(r)]
   788  		fmt.Fprintf(buf, "%v:\t%v\n", sum(vals), vals)
   789  		i += len(r)
   790  	}
   791  	fmt.Fprintf(buf, "]\n")
   792  	return buf.String()
   793  }
   794  
   795  // process current division, return true to stop iterating
   796  type iterDivision func(division []int) (done bool)
   797  type checkCut func(objects []*d2graph.Object, starting bool) (ok bool)
   798  
   799  // get all possible divisions of objects by the number of cuts
   800  func iterDivisions(objects []*d2graph.Object, nCuts int, f iterDivision, check checkCut) {
   801  	if len(objects) < 2 || nCuts == 0 {
   802  		return
   803  	}
   804  	done := false
   805  	// we go in this order to prefer extra objects in starting rows rather than later ones
   806  	lastObj := len(objects) - 1
   807  	// with objects=[A, B, C, D, E]; nCuts=2
   808  	// d:depth; i:index; n:nCuts;
   809  	// ┌────┬───┬───┬─────────────────────┬────────────┐
   810  	// │ d  │ i │ n │ objects             │ cuts       │
   811  	// ├────┼───┼───┼─────────────────────┼────────────┤
   812  	// │ 0  │ 4 │ 2 │ [A   B   C   D | E] │            │
   813  	// ├────┼───┼───┼─────────────────────┼────────────┤
   814  	// │ └1 │ 3 │ 1 │ [A   B   C | D]     │ + | E]     │
   815  	// ├────┼───┼───┼─────────────────────┼────────────┤
   816  	// │ └1 │ 2 │ 1 │ [A   B | C   D]     │ + | E]     │
   817  	// ├────┼───┼───┼─────────────────────┼────────────┤
   818  	// │ └1 │ 1 │ 1 │ [A | B   C   D]     │ + | E]     │
   819  	// ├────┼───┼───┼─────────────────────┼────────────┤
   820  	// │ 0  │ 3 │ 2 │ [A   B   C | D   E] │            │
   821  	// ├────┼───┼───┼─────────────────────┼────────────┤
   822  	// │ └1 │ 2 │ 1 │ [A   B | C]         │ + | D E]   │
   823  	// ├────┼───┼───┼─────────────────────┼────────────┤
   824  	// │ └1 │ 1 │ 1 │ [A | B   C]         │ + | D E]   │
   825  	// ├────┼───┼───┼─────────────────────┼────────────┤
   826  	// │ 0  │ 2 │ 2 │ [A   B | C   D   E] │            │
   827  	// ├────┼───┼───┼─────────────────────┼────────────┤
   828  	// │ └1 │ 1 │ 1 │ [A | B]             │ + | C D E] │
   829  	// └────┴───┴───┴─────────────────────┴────────────┘
   830  	for index := lastObj; index >= nCuts; index-- {
   831  		if !check(objects[index:], false) {
   832  			// optimization: if current cut gives a bad grouping, don't recurse
   833  			continue
   834  		}
   835  		if nCuts > 1 {
   836  			iterDivisions(objects[:index], nCuts-1, func(inner []int) bool {
   837  				done = f(append(inner, index-1))
   838  				return done
   839  			}, check)
   840  		} else {
   841  			if !check(objects[:index], true) {
   842  				// e.g. [A   B   C | D] if [A,B,C] is bad, skip it
   843  				continue
   844  			}
   845  			done = f([]int{index - 1})
   846  		}
   847  		if done {
   848  			return
   849  		}
   850  	}
   851  }
   852  
   853  // generate a grid of objects from the given cut indices
   854  // each cut index applies after the object at that index
   855  // e.g. [0 1 2 3 4 5 6 7] with cutIndices [0, 2, 6] => [[0], [1, 2], [3,4,5,6], [7]]
   856  func GenLayout(objects []*d2graph.Object, cutIndices []int) [][]*d2graph.Object {
   857  	layout := make([][]*d2graph.Object, len(cutIndices)+1)
   858  	objIndex := 0
   859  	for i := 0; i <= len(cutIndices); i++ {
   860  		var stop int
   861  		if i < len(cutIndices) {
   862  			stop = cutIndices[i]
   863  		} else {
   864  			stop = len(objects) - 1
   865  		}
   866  		if stop >= objIndex {
   867  			layout[i] = make([]*d2graph.Object, 0, stop-objIndex+1)
   868  		}
   869  		for ; objIndex <= stop; objIndex++ {
   870  			layout[i] = append(layout[i], objects[objIndex])
   871  		}
   872  	}
   873  	return layout
   874  }
   875  
   876  func getDistToTarget(layout [][]*d2graph.Object, targetSize float64, horizontalGap, verticalGap float64, columns bool) float64 {
   877  	totalDelta := 0.
   878  	for _, row := range layout {
   879  		rowSize := 0.
   880  		for _, o := range row {
   881  			if columns {
   882  				rowSize += o.Height + verticalGap
   883  			} else {
   884  				rowSize += o.Width + horizontalGap
   885  			}
   886  		}
   887  		if len(row) > 0 {
   888  			if columns {
   889  				rowSize -= verticalGap
   890  			} else {
   891  				rowSize -= horizontalGap
   892  			}
   893  		}
   894  		totalDelta += math.Abs(rowSize - targetSize)
   895  	}
   896  	return totalDelta
   897  }
   898  
   899  func (gd *gridDiagram) sizeForOutsideLabels() (revert func()) {
   900  	margins := make(map[*d2graph.Object]geo.Spacing)
   901  
   902  	for _, o := range gd.objects {
   903  		margin := o.GetMargin()
   904  		margins[o] = margin
   905  
   906  		o.Height += margin.Top + margin.Bottom
   907  		o.Width += margin.Left + margin.Right
   908  	}
   909  
   910  	// Example: a single column with 3 shapes and
   911  	// `x.label: long label {near: outside-bottom-left}`
   912  	// `y.label: outsider {near: outside-right-center}`
   913  	// . ┌───────────────────┐
   914  	// . │ widest shape here │
   915  	// . └───────────────────┘
   916  	// . ┌───┐
   917  	// . │ x │
   918  	// . └───┘
   919  	// . long label
   920  	// . ├─────────┤ x's new width
   921  	// .     ├─mr──┤ margin.right added to width during layout
   922  	// . ┌───┐
   923  	// . │ y │ outsider
   924  	// . └───┘
   925  	// . ├─────────────┤ y's new width
   926  	// .     ├───mr────┤ margin.right added to width during layout
   927  
   928  	// BEFORE LAYOUT
   929  	// . ┌───────────────────┐
   930  	// . │ widest shape here │
   931  	// . └───────────────────┘
   932  	// . ┌─────────┐
   933  	// . │ x       │
   934  	// . └─────────┘
   935  	// . ┌─────────────┐
   936  	// . │ y           │
   937  	// . └─────────────┘
   938  
   939  	// AFTER LAYOUT
   940  	// . ┌───────────────────┐
   941  	// . │ widest shape here │
   942  	// . └───────────────────┘
   943  	// . ┌───────────────────┐
   944  	// . │ x                 │
   945  	// . └───────────────────┘
   946  	// . ┌───────────────────┐
   947  	// . │ y                 │
   948  	// . └───────────────────┘
   949  
   950  	// CLEANUP 1/2
   951  	// . ┌───────────────────┐
   952  	// . │ widest shape here │
   953  	// . └───────────────────┘
   954  	// . ┌─────────────┐
   955  	// . │ x           │
   956  	// . └─────────────┘
   957  	// . long label    ├─mr──┤ remove margin we added
   958  	// . ┌─────────┐
   959  	// . │ y       │ outsider
   960  	// . └─────────┘
   961  	// .           ├───mr────┤ remove margin we added
   962  	// CLEANUP 2/2
   963  	// . ┌───────────────────┐
   964  	// . │ widest shape here │
   965  	// . └───────────────────┘
   966  	// . ┌───────────────────┐
   967  	// . │ x                 │
   968  	// . └───────────────────┘
   969  	// . long label    ├─mr──┤ we removed too much so add back margin we subtracted, then subtract new margin
   970  	// . ┌─────────┐
   971  	// . │ y       │ outsider
   972  	// . └─────────┘
   973  	// .           ├───mr────┤ margin.right is still needed
   974  
   975  	return func() {
   976  		for _, o := range gd.objects {
   977  			m, has := margins[o]
   978  			if !has {
   979  				continue
   980  			}
   981  			dy := m.Top + m.Bottom
   982  			dx := m.Left + m.Right
   983  			o.Height -= dy
   984  			o.Width -= dx
   985  
   986  			// less margin may be needed if layout grew the object
   987  			// compute the new margin after removing the old margin we added
   988  			margin := o.GetMargin()
   989  			marginX := margin.Left + margin.Right
   990  			marginY := margin.Top + margin.Bottom
   991  			if marginX < dx {
   992  				// layout grew width and now we need less of a margin (but we subtracted too much)
   993  				// add back dx and subtract the new amount
   994  				o.Width += dx - marginX
   995  			}
   996  			if marginY < dy {
   997  				o.Height += dy - marginY
   998  			}
   999  
  1000  			if margin.Left > 0 || margin.Top > 0 {
  1001  				o.MoveWithDescendants(margin.Left, margin.Top)
  1002  			}
  1003  		}
  1004  	}
  1005  }
  1006  

View as plain text