// Copyright (c) 2016 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 stress

import (
	

	
	
	
	
)

// Majorization implements the localized stress-majorization procedure from
// Gansner, Koren, and North exactly as used by ELK 0.8.1.
type Majorization struct {
	model *graph.Model
	graph *force.FGraph

	apsp [][]float64
	w    [][]float64

	desiredEdgeLength float64
	dimension         string
	epsilon           float64
	iterationLimit    int
	connectedEdges    [][]*force.FEdge
}

func ( *Majorization) ( *graph.Model,  *force.FGraph) {
	if len(.Nodes) <= 1 {
		return
	}
	.model = 
	.graph = 
	 := .Node(.Origin)
	.dimension = graph.Get(&.Properties, Dimension)
	.iterationLimit = graph.Get(&.Properties, IterationLimit)
	.epsilon = graph.Get(&.Properties, Epsilon)
	.desiredEdgeLength = graph.Get(&.Properties, DesiredEdgeLength)

	.connectedEdges = make([][]*force.FEdge, len(.Nodes))
	for ,  := range .Edges {
		.connectedEdges[.Source.ID] = append(.connectedEdges[.Source.ID], )
		.connectedEdges[.Target.ID] = append(.connectedEdges[.Target.ID], )
	}

	 := len(.Nodes)
	.apsp = make([][]float64, )
	for ,  := range .Nodes {
		.apsp[.ID] = make([]float64, )
		.dijkstra(, .apsp[.ID])
	}
	.w = make([][]float64, )
	for  := 0;  < ; ++ {
		.w[] = make([]float64, )
		for  := 0;  < ; ++ {
			 := .apsp[][]
			.w[][] = 1 / ( * )
		}
	}
}

func ( *Majorization) () {
	if .graph == nil || len(.graph.Nodes) <= 1 {
		return
	}
	 := 0
	 := .computeStress()
	 := math.Inf(1)
	for {
		if  > 0 {
			 = 
		}
		for ,  := range .graph.Nodes {
			if graph.Get(&.model.Node(.Origin).Properties, Fixed) {
				continue
			}
			.Position = .computeNewPosition()
		}
		 = .computeStress()
		 :=  == 0 ||
			(-)/ < .epsilon ||
			 >= .iterationLimit
		++
		if  {
			return
		}
	}
}

func ( *Majorization) ( *force.FNode,  []float64) {
	 := make([]bool, len(.graph.Nodes))
	for ,  := range .graph.Nodes {
		if .ID == .ID {
			[.ID] = 0
		} else {
			[.ID] = float64(math.MaxInt32)
		}
	}
	 := javacompat.NewPriorityQueueCapacity(len(.graph.Nodes), func(,  *force.FNode) int {
		return javacompat.DoubleCompare([.ID], [.ID])
	})
	for ,  := range .graph.Nodes {
		.Add()
	}
	for !.IsEmpty() {
		,  := .Poll()
		[.ID] = true
		for ,  := range .connectedEdges[.ID] {
			 := .Source
			if  ==  {
				 = .Target
			}
			if [.ID] {
				continue
			}
			 := .desiredEdgeLength
			if ,  := graph.TryGet(&.model.Edge(.Origin).Properties, DesiredEdgeLength);  {
				 = 
			}
			 := [.ID] + 
			if  < [.ID] {
				[.ID] = 
				.RemoveFirst(func( *force.FNode) bool { return  ==  })
				.Add()
			}
		}
	}
}

func ( *Majorization) () float64 {
	 := 0.0
	for ,  := range .graph.Nodes {
		for  :=  + 1;  < len(.graph.Nodes); ++ {
			 := .graph.Nodes[]
			 := stressDistance(.Position, .Position) - .apsp[.ID][.ID]
			// These same-type conversions intentionally force the intermediate
			// rounding performed by GWT's generated JavaScript. Without them Go
			// may fuse the products with the following addition.
			 := float64(.w[.ID][.ID] * )
			 := float64( * )
			 += 
		}
	}
	return 
}

func ( *Majorization) ( *force.FNode) geometry.Point {
	, ,  := 0.0, 0.0, 0.0
	for ,  := range .graph.Nodes {
		if  ==  {
			continue
		}
		 := .w[.ID][.ID]
		 += 
		 := stressDistance(.Position, .Position)
		if  > 0 && .dimension != DimensionY {
			 := .Position.X - .Position.X
			 := float64(.apsp[.ID][.ID] * )
			 := .Position.X + /
			 := float64( * )
			 += 
		}
		if  > 0 && .dimension != DimensionX {
			 := .Position.Y - .Position.Y
			 := float64(.apsp[.ID][.ID] * )
			 := .Position.Y + /
			 := float64( * )
			 += 
		}
	}
	switch .dimension {
	case DimensionX:
		return geometry.Point{X:  / , Y: .Position.Y}
	case DimensionY:
		return geometry.Point{X: .Position.X, Y:  / }
	default:
		return geometry.Point{X:  / , Y:  / }
	}
}

func stressDistance(,  geometry.Point) float64 {
	 := .X - .X
	 := .Y - .Y
	// Keep the products separately rounded before adding, as KVector.distance
	// does in the generated ELK.js worker.
	 := float64( * )
	 := float64( * )
	return math.Sqrt( + )
}