// Copyright (c) 2018, 2020 Kiel University and others.
// Copyright (c) 2020 Kiel University and others.
// Copyright (c) 2026 The elk-go Authors.
//
// This program and the accompanying materials are made available under the
// terms of the Eclipse Public License 2.0 which is available at
// https://www.eclipse.org/legal/epl-2.0.
//
// SPDX-License-Identifier: EPL-2.0


// Package rectpacking ports org.eclipse.elk.alg.rectpacking from ELK 0.12.0.
package rectpacking

import (
	
	
	

	
	
	
	
	
	
	
)

type Provider struct{}

func ( *core.AlgorithmRegistry) error {
	return .Register(core.AlgorithmData{
		ID:     "org.eclipse.elk.rectpacking",
		Create: func() core.LayoutProvider { return &Provider{} },
		KnownOptions: []string{
			AspectRatio.ID,
			basicoptions.NodeSizeFixedGraphSize.ID,
			Padding.ID,
			SpacingNodeNode.ID,
			core.ContentAlignment.ID,
			core.NodeSizeConstraints.ID,
			core.NodeSizeMinimum.ID,
			basicoptions.NodeSizeOptions.ID,
			"org.eclipse.elk.nodeLabels.placement",
			OmitNodeMicroLayout.ID,
			"org.eclipse.elk.portLabels.placement",
			OptimizationGoal.ID,
			LastPlaceShift.ID,
			TargetWidth.ID,
			WidthApproximationStrategy.ID,
			PackingStrategy.ID,
			RowHeightReevaluation.ID,
			CompactionIterations.ID,
			WhiteSpaceEliminationStrategy.ID,
			Interactive.ID,
			core.InteractiveLayout.ID,
			DesiredPosition.ID,
			CurrentPosition.ID,
			InNewRow.ID,
			TryBox.ID,
			OrderBySize.ID,
		},
	})
}

func (*Provider) ( *graph.Model,  graph.NodeID,  core.ProgressMonitor) error {
	 := .Node()
	 := append([]graph.NodeID(nil), .Children...)
	 := graph.Get(&.Properties, Padding)
	 := graph.Get(&.Properties, SpacingNodeNode)

	// RectPackingLayoutProvider runs node micro layout both before packing and
	// after optional whitespace expansion, since expansion can change child
	// dimensions. The Go node-spacing utility is the matching common phase.
	if !graph.Get(&.Properties, OmitNodeMicroLayout) {
		nodespacing.CalculateLabelAndNodeSizes(, , nil)
	}

	// ELK 0.12's trybox special case deliberately falls back to Box only when
	// no consecutive triple is vertically stackable.
	 := false
	if graph.Get(&.Properties, TryBox) && len() >= 3 {
		,  := [0], [1]
		for  := 2;  < len(); ++ {
			 := []
			 := .Node().Shape.Height
			 := .Node().Shape.Height
			 := .Node().Shape.Height
			if  >= ++ ||
				 >= ++ {
				 = true
				break
			}
			,  = , 
		}
	} else {
		 = true
	}
	if ! {
		 := len()
		for ,  := range  {
			graph.Set(&.Node().Properties, basicoptions.Priority, )
			--
		}
		return (&box.Provider{}).Layout(, , )
	}

	// ELK's phase-independent processors run in this order before width
	// approximation: minimum-size preprocessing, size ordering, interaction.
	 := elkutil.EffectiveMinSizeConstraintFor(, )
	if graph.Get(&.Properties, OrderBySize) {
		sort.SliceStable(, func(,  int) bool {
			return .Node([]).Shape.Height > .Node([]).Shape.Height
		})
		.Children = append(.Children[:0], ...)
	}

	if graph.Get(&.Properties, Interactive) {
		var  error
		,  = interactiveOrder(, )
		if  != nil {
			return 
		}
		// ELK mutates the parent's child EList in interactive mode.
		.Children = append(.Children[:0], ...)
		for ,  := range  {
			graph.Set(&.Node().Properties, CurrentPosition, )
		}
	}

	 := graph.Get(&.Properties, AspectRatio)
	var  float64
	switch graph.Get(&.Properties, WidthApproximationStrategy) {
	case "TARGET_WIDTH":
		if !graph.Has(&.Properties, TargetWidth) {
			return fmt.Errorf("rectpacking TARGET_WIDTH requires %s", TargetWidth.ID)
		}
		 = graph.Get(&.Properties, TargetWidth)
	case "GREEDY":
		if len() == 0 {
			 = 0
		} else {
			 := approximate(
				, , , , ,
				graph.Get(&.Properties, OptimizationGoal),
				graph.Get(&.Properties, LastPlaceShift),
			)
			 = .width
		}
	default:
		return fmt.Errorf("unsupported rectpacking width approximation strategy %q",
			graph.Get(&.Properties, WidthApproximationStrategy))
	}
	// MinSizePostProcessor clamps the internal target width to the unadjusted
	// minimum width. Padding is removed later when P2 calculates dimensions.
	 = math.Max(, .X)

	 := graph.Get(&.Properties, PackingStrategy)
	var  drawingData
	var  []*rectRow
	switch  {
	case "COMPACTION":
		,  = compactPlacement(
			, , , , , , ,
			graph.Get(&.Properties, RowHeightReevaluation),
			graph.Get(&.Properties, CompactionIterations),
		)
	case "SIMPLE":
		,  = simplePlacement(, , , , , , )
	case "NONE":
		 = noPlacement(, , , , )
	default:
		return fmt.Errorf("unsupported rectpacking packing strategy %q", )
	}

	 := graph.Get(&.Properties, WhiteSpaceEliminationStrategy)
	if  != "NONE" {
		if  == nil {
			return fmt.Errorf("rectpacking whitespace elimination requires a packing strategy that produces rows")
		}
		if  == "TO_ASPECT_RATIO" {
			if .width/.height <  {
				.width = .height * 
			} else {
				.additionalHeight += .width/ - .height
				.height += .additionalHeight
			}
		} else if  != "EQUAL_BETWEEN_STRUCTURES" {
			return fmt.Errorf("unsupported rectpacking whitespace elimination strategy %q", )
		}
		expandRows(, , .width, .additionalHeight)
	}

	// Content alignment is applied to the unpadded drawing before every child
	// is shifted by the requested top/left padding.
	 := rectangleDimensions(, )
	elkutil.TranslateAligned(, ,
		geometry.Point{X: .width, Y: .height}, )
	for ,  := range  {
		 := .Node()
		.Shape.SetLocation(.Shape.X+.Left, .Shape.Y+.Top)
	}
	if !graph.Get(&.Properties, basicoptions.NodeSizeFixedGraphSize) {
		elkutil.ResizeNode(, , .width+.Horizontal(), .height+.Vertical(), false, true)
	}
	if !graph.Get(&.Properties, OmitNodeMicroLayout) {
		nodespacing.CalculateLabelAndNodeSizes(, , nil)
	}
	return nil
}

func interactiveOrder( *graph.Model,  []graph.NodeID) ([]graph.NodeID, error) {
	 := make([]graph.NodeID, 0, len())
	 := make([]graph.NodeID, 0)
	for ,  := range  {
		if graph.Has(&.Node().Properties, DesiredPosition) {
			 = append(, )
		} else {
			 = append(, )
		}
	}
	sort.SliceStable(, func(,  int) bool {
		 := graph.Get(&.Node([]).Properties, DesiredPosition)
		 := graph.Get(&.Node([]).Properties, DesiredPosition)
		if  ==  {
			// The Java comparator returns -1 here. Stable insertion in reverse
			// order is its deterministic GWT result.
			return true
		}
		return  < 
	})
	for ,  := range  {
		 := graph.Get(&.Node().Properties, DesiredPosition)
		if  < 0 {
			return nil, fmt.Errorf("rectpacking desired position %d is negative", )
		}
		if  > len() {
			 = len()
		}
		 = append(, 0)
		copy([+1:], [:])
		[] = 
	}
	return , nil
}

type placement uint8

const (
	wholeDrawing placement = iota
	lastRight
	lastBelow
	wholeRight
	wholeBelow
)

type drawingData struct {
	dar, width, height, area, aspect, scale float64
	additionalHeight                        float64
	option                                  placement
	nextX, nextY                            float64
}

func newDrawing(, ,  float64,  placement, ,  float64) drawingData {
	 := drawingData{dar: , width: , height: , option: , nextX: , nextY: }
	if  > 0 &&  > 0 {
		.area =  * 
		.aspect =  / 
		.scale = math.Min(/, 1/)
	}
	return 
}

func approximate( *graph.Model,  []graph.NodeID,  float64,  geometry.Spacing,  float64,  string,  bool) drawingData {
	 := .Node([0])
	.Shape.SetLocation(0, 0)
	 := []graph.NodeID{[0]}
	 := [0]
	 := newDrawing(, .Shape.Width, .Shape.Height, wholeDrawing, 0, 0)
	for ,  := range [1:] {
		 := []drawingData{
			candidate(, , , , , , , lastRight),
			candidate(, , , , , , , lastBelow),
			candidate(, , , , , , , wholeRight),
			candidate(, , , , , , , wholeBelow),
		}
		 := bestCandidate(, , , , , )
		.Node().Shape.SetLocation(.nextX, .nextY)
		.option = wholeDrawing
		 = 
		 = 
		 = append(, )
	}
	return 
}

func candidate( *graph.Model, ,  graph.NodeID,  drawingData,  []graph.NodeID,  float64,  bool,  placement) drawingData {
	,  := .Node(), .Node()
	,  := 0.0, 0.0
	,  := .width, .height
	switch  {
	case lastRight:
		 = .Shape.X + .Shape.Width + 
		 = .Shape.Y
		if  {
			 = shiftedY(, , , , )
		}
		 = math.Max(, +.Shape.Width)
		 = math.Max(, +.Shape.Height)
	case lastBelow:
		 = .Shape.Y + .Shape.Height + 
		 = .Shape.X
		if  {
			 = shiftedX(, , , , )
		}
		 = math.Max(, +.Shape.Width)
		 = math.Max(, +.Shape.Height)
	case wholeRight:
		 = .width + 
		 = .width +  + .Shape.Width
		 = math.Max(.height, .Shape.Height)
	case wholeBelow:
		 = .height + 
		 = math.Max(.width, .Shape.Width)
		 = .height +  + .Shape.Height
	}
	return newDrawing(.dar, , , , , )
}

func shiftedY( *graph.Model,  float64,  []graph.NodeID,  *graph.Node,  float64) float64 {
	 := false
	 := 0.0
	for ,  := range  {
		 := .Node()
		 := .Shape.Y + .Shape.Height
		if  < .Shape.X+.Shape.Width+ {
			if ! || .Shape.Y- < .Shape.Y- {
				 = 
				 = true
			}
		}
	}
	if ! {
		return 0
	}
	return  + 
}

func shiftedX( *graph.Model,  float64,  []graph.NodeID,  *graph.Node,  float64) float64 {
	 := false
	 := 0.0
	for ,  := range  {
		 := .Node()
		 := .Shape.X + .Shape.Width
		if  < .Shape.Y+.Shape.Height+ {
			if ! || .Shape.X- < .Shape.X- {
				 = 
				 = true
			}
		}
	}
	if ! {
		return 0
	}
	return  + 
}

func bestCandidate( *graph.Model,  []drawingData, ,  graph.NodeID,  geometry.Spacing,  string) drawingData {
	 := []func([]drawingData) []drawingData{}
	 := func( []drawingData) []drawingData {
		 := math.Inf(-1)
		for ,  := range  {
			 = math.Max(, math.Min(.dar/(.width+.Horizontal()), 1/(.height+.Vertical())))
		}
		 := [:0]
		for ,  := range  {
			if math.Min(.dar/(.width+.Horizontal()), 1/(.height+.Vertical())) ==  {
				 = append(, )
			}
		}
		return 
	}
	 := func( []drawingData) []drawingData {
		 := math.Inf(1)
		for ,  := range  {
			 = math.Min(, (.width+.Horizontal())*(.height+.Vertical()))
		}
		 := [:0]
		for ,  := range  {
			if (.width+.Horizontal())*(.height+.Vertical()) ==  {
				 = append(, )
			}
		}
		return 
	}
	 := func( []drawingData) []drawingData {
		 := math.Inf(1)
		for ,  := range  {
			 = math.Min(, math.Abs((.width+.Horizontal())/(.height+.Vertical())-.dar))
		}
		 := [:0]
		for ,  := range  {
			if math.Abs((.width+.Horizontal())/(.height+.Vertical())-.dar) ==  {
				 = append(, )
			}
		}
		return 
	}
	switch  {
	case "ASPECT_RATIO_DRIVEN":
		 = append(, , , )
	case "AREA_DRIVEN":
		 = append(, , , )
	default:
		 = append(, , , )
	}
	for ,  := range  {
		if len() > 1 {
			 = ()
		}
	}
	if len() == 1 {
		return [0]
	}
	if len() != 2 {
		return [0]
	}
	,  := [0], [1]
	 := .option == lastBelow || .option == wholeBelow
	 := .option == lastBelow || .option == wholeBelow
	 := .option == lastRight || .option == wholeRight
	 := .option == lastRight || .option == wholeRight
	if  &&  {
		if .option == wholeBelow {
			return 
		}
		return 
	}
	if  &&  {
		if .option == wholeRight {
			return 
		}
		return 
	}
	if (.option == lastRight || .option == lastBelow) && (.option == lastRight || .option == lastBelow) {
		,  := , 
		if .option == lastRight {
			,  = , 
		}
		,  := .Node(), .Node()
		 := math.Max(.Shape.Y+.Shape.Height, .nextY+.Shape.Height) - math.Min(.Shape.Y, .nextY)
		 := (.nextX + .Shape.Width - .Shape.X) * 
		 := math.Max(.Shape.X+.Shape.Width, .nextX+.Shape.Width) - math.Min(.Shape.X, .nextX)
		 :=  * (.nextY + .Shape.Height - .Shape.Y)
		if  <=  {
			return 
		}
		return 
	}
	return 
}