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

import (
	
	

	basegraph 
	
)

type minWidthResult struct {
	maximumWidth float64
	layers       [][]layered.LNodeID
}

// MinWidthLayerer is ELK 0.8.1's size-aware minimum-width heuristic.
type MinWidthLayerer struct {
	dummySize      float64
	normalizedSize []float64
	averageSize    float64
	inDegree       []int
	outDegree      []int
}

func (*MinWidthLayerer) (
	 *layered.LGraphArena,
	 layered.LGraphID,
) layered.ProcessorConfiguration {
	return layered.NetworkSimplexLayeringConfiguration()
}

func ( *MinWidthLayerer) ( *layered.LGraphArena,  layered.LGraphID) error {
	 := .Graph()
	 := .LayerlessNodes
	if len() == 0 {
		return nil
	}
	 := basegraph.Get(&.Properties, layered.MinWidthUpperBound)
	 := basegraph.Get(&.Properties, layered.MinWidthUpperLayerScaling)
	.dummySize = basegraph.Get(&.Properties, layered.SpacingEdgeEdge)
	 := math.Inf(1)
	for ,  := range  {
		if  := .Node(); .Type == layered.NormalNode {
			 = math.Min(, .Size.Y)
		}
	}
	 = math.Max(1, )
	.inDegree = make([]int, len())
	.outDegree = make([]int, len())
	.normalizedSize = make([]float64, len())
	.averageSize = 0
	for ,  := range  {
		 := .Node()
		.ID = 
		.inDegree[] = minWidthDegree(, .NodeIncomingEdges())
		.outDegree[] = minWidthDegree(, .NodeOutgoingEdges())
		.normalizedSize[] = .Size.Y / 
		.averageSize += .normalizedSize[]
	}
	.dummySize /= 
	.averageSize /= float64(len())

	 := make([]map[layered.LNodeID]struct{}, len())
	for ,  := range  {
		 := make(map[layered.LNodeID]struct{})
		for ,  := range .NodeOutgoingEdges() {
			if !.EdgeIsSelfLoop() {
				[.EdgeTargetNode()] = struct{}{}
			}
		}
		[.Node().ID] = 
	}
	sort.SliceStable(, func(,  int) bool {
		return .outDegree[.Node([]).ID] > .outDegree[.Node([]).ID]
	})

	,  := , 
	,  := , 
	if  < 0 {
		,  = 1, 4
	}
	if  < 0 {
		,  = 1, 2
	}
	 := math.Inf(1)
	 := int(^uint32(0) >> 1)
	var  [][]layered.LNodeID
	for  := ;  <= ; ++ {
		for  := ;  <= ; ++ {
			 := .compute(, , , , )
			if .maximumWidth <  ||
				.maximumWidth ==  && len(.layers) <  {
				 = .maximumWidth
				 = len(.layers)
				 = .layers
			}
		}
	}
	for ,  := range  {
		 := .AddLayer()
		for ,  := range  {
			.SetNodeLayer(, &)
		}
		.Layers = append(.Layers, )
	}
	for ,  := 0, len(.Layers)-1;  < ; ,  = +1, -1 {
		.Layers[], .Layers[] = .Layers[], .Layers[]
	}
	.LayerlessNodes = .LayerlessNodes[:0]
	return nil
}

func ( *MinWidthLayerer) (
	 *layered.LGraphArena,
	,  int,
	 []layered.LNodeID,
	 []map[layered.LNodeID]struct{},
) minWidthResult {
	 := append([]layered.LNodeID(nil), ...)
	 := make(map[layered.LNodeID]struct{})
	 := make(map[layered.LNodeID]struct{})
	 := make([]layered.LNodeID, 0)
	 := make([][]layered.LNodeID, 0)
	 := float64() * .averageSize
	,  := 0.0, 0.0
	,  := 0.0, 0.0
	,  := 0.0, 0.0

	for len() > 0 {
		 := -1
		for ,  := range  {
			 := true
			for  := range [.Node().ID] {
				if ,  := []; ! {
					 = false
					break
				}
			}
			if  {
				 = 
				break
			}
		}
		var  layered.LNodeID
		 :=  >= 0
		,  := 0, 0
		if  {
			 = []
			 = append([:], [+1:]...)
			 = append(, )
			[] = struct{}{}
			 := .Node().ID
			 = .outDegree[]
			 += .normalizedSize[] - float64()*.dummySize
			 = .inDegree[]
			 += float64() * .dummySize
			 += float64() * .dummySize
			 += .normalizedSize[]
		}
		 := ! || len() == 0
		if  {
			 := .Node().ID
			 =  ||  >=  &&
				.normalizedSize[] > float64()*.dummySize ||
				 >= float64()*
		}
		if  {
			 = append(, )
			 = make([]layered.LNodeID, 0)
			for  := range  {
				[] = struct{}{}
			}
			clear()
			 -= 
			 = math.Max(, *.dummySize+)
			 += 
			,  = , 0
			,  = 0, 0
		}
	}
	return minWidthResult{maximumWidth: , layers: }
}

func minWidthDegree( *layered.LGraphArena,  []layered.LEdgeID) int {
	 := 0
	for ,  := range  {
		if !.EdgeIsSelfLoop() {
			++
		}
	}
	return 
}