// Copyright (c) 2009, 2020 Kiel University and others.
// Copyright (c) 2015, 2020 Kiel University and others.
//
// 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 box implements org.eclipse.elk.box from ELK 0.12.0.
package box

import (
	
	

	
	
	
	
	
	
)

const defaultAspectRatio = 1.3

type Provider struct{}

func ( *core.AlgorithmRegistry) error {
	return .Register(core.AlgorithmData{
		ID:     "org.eclipse.elk.box",
		Create: func() core.LayoutProvider { return &Provider{} },
		KnownOptions: []string{
			basicoptions.BoxPadding.ID,
			basicoptions.BoxSpacingNodeNode.ID,
			basicoptions.Priority.ID,
			basicoptions.ExpandNodes.ID,
			core.NodeSizeConstraints.ID,
			basicoptions.NodeSizeOptions.ID,
			basicoptions.BoxAspectRatio.ID,
			basicoptions.Interactive.ID,
			core.NodeSizeMinimum.ID,
			basicoptions.PackingMode.ID,
			core.ContentAlignment.ID,
		},
	})
}

func (*Provider) ( *graph.Model,  graph.NodeID,  core.ProgressMonitor) error {
	 := .Node()
	// BoxLayoutProvider narrows spacing through floatValue().
	 := float64(float32(graph.Get(&.Properties, basicoptions.BoxSpacingNodeNode)))
	 := graph.Get(&.Properties, basicoptions.BoxPadding)
	 := graph.Get(&.Properties, basicoptions.ExpandNodes)
	 := graph.Get(&.Properties, basicoptions.Interactive)
	if graph.Get(&.Properties, basicoptions.PackingMode) == "SIMPLE" {
		placeBoxesSimple(, , , , , )
	} else {
		placeBoxesGrouping(, , float32(), , )
	}
	return nil
}

func placeBoxesSimple( *graph.Model,  graph.NodeID,  float64,  geometry.Spacing, ,  bool) {
	 := sortBoxes(, , )
	 := elkutil.EffectiveMinSizeConstraintFor(, )
	 := graph.Get(&.Node().Properties, basicoptions.BoxAspectRatio)
	if  <= 0 {
		 = defaultAspectRatio
	}
	 := placeBoxes(, , , , .X, .Y, , )
	elkutil.ResizeNode(, , .X, .Y, false, true)
}

func sortBoxes( *graph.Model,  graph.NodeID,  bool) []graph.NodeID {
	 := append([]graph.NodeID(nil), .Node().Children...)
	sort.SliceStable(, func(,  int) bool {
		,  := .Node([]), .Node([])
		 := graph.Get(&.Properties, basicoptions.Priority)
		 := graph.Get(&.Properties, basicoptions.Priority)
		if  !=  {
			return  > 
		}
		if  {
			if  := javaDoubleCompare(.Shape.Y, .Shape.Y);  != 0 {
				return  < 0
			}
			if  := javaDoubleCompare(.Shape.X, .Shape.X);  != 0 {
				return  < 0
			}
		}
		 := .Shape.Width * .Shape.Height
		 := .Shape.Width * .Shape.Height
		return javaDoubleCompare(, ) < 0
	})
	return 
}

func placeBoxes(
	 *graph.Model,
	 []graph.NodeID,
	 float64,
	 geometry.Spacing,
	,  float64,
	 bool,
	 float64,
) geometry.Point {
	,  := 0.0, 0.0
	for ,  := range  {
		elkutil.ResizeNodeForConstraints(, )
		 := .Node()
		 = math.Max(, .Shape.Width)
		 += .Shape.Width * .Shape.Height
	}
	 :=  / float64(len())
	 := areaStdDev(, , )
	 += float64(len()) * 
	// ELK 0.12 includes padding in its target-area estimate. Preserve the
	// source's sequential square-root updates (including its right-only term).
	 += math.Sqrt() * (.Bottom + .Top)
	 += math.Sqrt() * .Right
	 = math.Max(, math.Sqrt(*)) + .Left

	,  := .Left, .Top
	,  := 0.0, .Horizontal()
	 := []int{0}
	 := make([]float64, 0)
	for ,  := range  {
		 := .Node()
		,  := .Shape.Width, .Shape.Height
		if + >  {
			if  {
				 = append(, )
				 = append(, )
			}
			 = .Left
			 +=  + 
			 = 0
			 = math.Max(, .Horizontal()+)
		}
		.Shape.SetLocation(, )
		 = math.Max(, ++.Right)
		 = math.Max(, )
		 +=  + 
	}
	 = math.Max(, )
	 :=  +  + .Bottom
	if  <  {
		 +=  - 
		 = 
	}

	if  {
		 = .Left
		 = append(, len())
		 := 0
		 := []
		 = append(, )
		 := 0
		 := 0.0
		for ,  := range  {
			if  ==  {
				 = .Left
				 = []
				++
				++
				 = []
			}
			 := .Node()
			 := geometry.Point{X: .Shape.Width, Y: .Shape.Height}
			.Shape.Height = 
			 := 
			if +1 ==  {
				 :=  -  - .Right
				.Shape.Width = 
				elkutil.TranslateAligned(, , geometry.Point{X: , Y: }, )
			}
			.Shape.Presence |= graph.HasWidth | graph.HasHeight
			 += .Shape.Width + 
		}
	}
	return geometry.Point{X: , Y: }
}

func areaStdDev( *graph.Model,  []graph.NodeID,  float64) float64 {
	 := 0.0
	for ,  := range  {
		 := .Node()
		 := .Shape.Width*.Shape.Height - 
		 += math.Pow(, 2)
	}
	return math.Sqrt( / float64(len()-1))
}

type group struct {
	node     *graph.NodeID
	children []*group
	size     geometry.Point
	bottom   []*group
	right    []*group
}

func newLeaf( *graph.Model,  graph.NodeID) *group {
	.Node().Shape.SetLocation(0, 0)
	 := 
	return &group{node: &}
}

func newGroup( []*group) *group {
	return &group{children: append([]*group(nil), ...)}
}

func ( *group) ( *graph.Model) float64 {
	if .node != nil {
		return .Node(*.node).Shape.Width
	}
	return .size.X
}

func ( *group) ( *graph.Model) float64 {
	if .node != nil {
		return .Node(*.node).Shape.Height
	}
	return .size.Y
}

func ( *group) ( *graph.Model) float64 {
	return .width() * .height()
}

func ( *group) ( *graph.Model,  float64) {
	if .node != nil {
		 := .Node(*.node)
		.Shape.Width = 
		.Shape.Presence |= graph.HasWidth
		return
	}
	 :=  - .width()
	for ,  := range .right {
		.(, .width()+)
	}
}

func ( *group) ( *graph.Model,  float64) {
	if .node != nil {
		 := .Node(*.node)
		.Shape.Height = 
		.Shape.Presence |= graph.HasHeight
		return
	}
	 :=  - .height()
	for ,  := range .bottom {
		.(, .height()+)
	}
}

func ( *group) ( *graph.Model, ,  float64) {
	if .node != nil {
		 := .Node(*.node)
		.Shape.X += 
		.Shape.Y += 
		.Shape.Presence |= graph.HasX | graph.HasY
		return
	}
	for ,  := range .children {
		.(, , )
	}
}

func ( *group) ( *graph.Model, ,  float64) {
	if .node != nil {
		elkutil.Translate(, *.node, , )
		return
	}
	for ,  := range .children {
		.(, , )
	}
}

func placeBoxesGrouping( *graph.Model,  graph.NodeID,  float32,  geometry.Spacing,  bool) {
	 := graph.Get(&.Node().Properties, core.NodeSizeMinimum)
	.X = math.Max(.X-.Left-.Right, 0)
	.Y = math.Max(.Y-.Top-.Bottom, 0)
	 := graph.Get(&.Node().Properties, basicoptions.BoxAspectRatio)
	if  <= 0 {
		 = defaultAspectRatio
	}
	 := make([]*group, 0, len(.Node().Children))
	for ,  := range .Node().Children {
		 = append(, newLeaf(, ))
	}
	var  []*group
	switch graph.Get(&.Node().Properties, basicoptions.PackingMode) {
	case "GROUP_INC":
		 = mergeAndPlaceIncreasing(, , float64(), .X, .Y, )
	case "GROUP_DEC":
		 = mergeAndPlaceDecreasing(, , float64(), .X, .Y, )
	default:
		 = mergeAndPlaceMixed(, , float64(), .X, .Y, )
	}
	 := newGroup()
	 := placeInnerBoxes(, , float64(), , .X, .Y, , )
	elkutil.ResizeNode(, , .X, .Y, false, true)
}

func placeInnerBoxes(
	 *graph.Model,
	 *group,
	 float64,
	 geometry.Spacing,
	,  float64,
	 bool,
	 float64,
) geometry.Point {
	,  := 0.0, 0.0
	for ,  := range .children {
		if .node != nil {
			elkutil.ResizeNodeForConstraints(, *.node)
		}
		 = math.Max(, .width())
		 += .area()
	}
	 :=  / float64(len(.children))
	 := 0.0
	for ,  := range .children {
		 := .area() - 
		 += math.Pow(, 2)
	}
	 := math.Sqrt( / float64(len(.children)-1))
	 += float64(len(.children)) * 
	 = math.Max(, math.Sqrt(*)) + .Left

	,  := .Left, .Top
	,  := 0.0, .Horizontal()
	 := []int{0}
	 := make([]float64, 0)
	var  *group
	 := make([]*group, 0)
	for ,  := range .children {
		,  := .width(), .height()
		if + >  {
			if  {
				 = append(, )
				 = append(, )
				.right = append(.right, )
				 = [:0]
			}
			 = .Left
			 +=  + 
			 = 0
			 = math.Max(, .Horizontal()+)
		}
		 = append(, )
		.translate(, , )
		 = math.Max(, ++.Right)
		 = math.Max(, )
		 +=  + 
		 = 
	}
	.bottom = append(.bottom, ...)
	.right = append(.right, [len()-1])
	 = math.Max(, )
	 :=  +  + .Bottom
	if  <  {
		 +=  - 
		 = 
	}

	if  {
		 = .Left
		 = append(, len(.children))
		 := 0
		 := []
		 = append(, )
		 := 0
		 := 0.0
		for ,  := range .children {
			if  ==  {
				 = .Left
				 = []
				++
				++
				 = []
			}
			.setHeight(, )
			if +1 ==  {
				 :=  -  - .Right
				 := .width()
				.setWidth(, )
				.translateInnerNodes(, (-)/2, 0)
			}
			 += .width() + 
		}
	}
	return geometry.Point{X: , Y: }
}

func mergeAndPlaceDecreasing( *graph.Model,  []*group, , ,  float64,  bool) []*group {
	sort.SliceStable(, func(,  int) bool {
		return javaDoubleCompare([].area(), [].area()) > 0
	})
	 := append([]*group(nil), ...)
	 := make([]*group, 0)
	 := make([]*group, 0)
	var  *group
	 := 0.0
	for len() > 0 {
		 := [0]
		 = [1:]
		if  == nil || .area()/2 < .area() {
			 = 
			 = append(, )
		} else {
			 += .area()
			 = append(, )
			if len() > 1 && ( > .area()/2 || len() == 0) {
				 := newGroup()
				 := .width() / .height()
				.size = placeInnerBoxes(, , , geometry.Spacing{}, , , , )
				 = 
				 = append(, )
				 = 0
				 = [:0]
			}
		}
	}
	return append(, ...)
}

func mergeAndPlaceMixed( *graph.Model,  []*group, , ,  float64,  bool) []*group {
	 := make([]float64, len())
	 := javacompat.NewGWTPriorityQueue(func(,  *group) int {
		return javaDoubleCompare(.area(), .area())
	})
	.AddAll()
	 := 0
	 := make([]*group, 0)
	for !.IsEmpty() {
		,  := .Peek()
		if  > 1 && .area()/2 > [0] {
			 := 0
			for  < len()-1 && .area()/2 > [] {
				++
			}
			 := append([]*group(nil), [:+1]...)
			 := append([]*group(nil), [+1:]...)
			 := newGroup()
			 := .width() / .height()
			.size = placeInnerBoxes(, , , geometry.Spacing{}, , , , )
			.Add()
			.AddAll()
			 = [:0]
			 = 0
			clear()
		} else {
			, _ = .Poll()
			if  > 0 {
				[] = [-1]
			}
			[] += .area()
			++
			 = append(, )
		}
	}
	return 
}

func mergeAndPlaceIncreasing( *graph.Model,  []*group, , ,  float64,  bool) []*group {
	sort.SliceStable(, func(,  int) bool {
		return javaDoubleCompare([].area(), [].area()) < 0
	})
	 := make([]*group, 0)
	 := 0.0
	for ,  := range  {
		if len() > 0 && .area() > *2 {
			 := newGroup()
			 := .width() / .height()
			.size = placeInnerBoxes(, , , geometry.Spacing{}, , , , )
			 = [:0]
			 = 0
			 = append(, , )
			 = .area() + .area()
		} else {
			 = append(, )
			 += .area()
		}
	}
	return 
}

func javaDoubleCompare(,  float64) int {
	if  <  {
		return -1
	}
	if  >  {
		return 1
	}
	 := int64(math.Float64bits())
	 := int64(math.Float64bits())
	if math.IsNaN() {
		 = int64(0x7ff8000000000000)
	}
	if math.IsNaN() {
		 = int64(0x7ff8000000000000)
	}
	if  ==  {
		return 0
	}
	if  <  {
		return -1
	}
	return 1
}