// 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 
	
)

// StretchWidthLayerer is ELK 0.8.1's minimum-width heuristic. It builds the
// layering bottom-up and increases its width bound only when a layer cannot
// accept any eligible node.
type StretchWidthLayerer struct{}

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

func (*StretchWidthLayerer) ( *layered.LGraphArena,  layered.LGraphID) error {
	 := .Graph()
	if len(.LayerlessNodes) == 0 {
		return nil
	}

	,  := math.Inf(1), math.Inf(-1)
	 := basegraph.Get(&.Properties, layered.SpacingEdgeEdge)
	 := append([]layered.LNodeID(nil), .LayerlessNodes...)
	for ,  := range .LayerlessNodes {
		.Node().ID = stretchWidthRank(, )
	}
	sort.SliceStable(, func(,  int) bool {
		return .Node([]).ID > .Node([]).ID
	})
	for ,  := range  {
		.Node().ID = 
	}

	 := make([]int, len())
	 := make([]int, len())
	for ,  := range  {
		 := .Node().ID
		[] = len(.NodeIncomingEdges())
		[] = len(.NodeOutgoingEdges())
		if .Node().Type == layered.NormalNode {
			 = math.Min(, .Node().Size.Y)
			 = math.Max(, .Node().Size.Y)
		}
	}
	 := make([]float64, len())
	for ,  := range  {
		[.Node().ID] = .Node().Size.Y / 
	}
	 = math.Max(1, )
	 = math.Max(1, )
	 /= 
	 :=  / 
	 := 0.0
	for ,  := range .LayerlessNodes {
		 += float64(len(.NodeOutgoingEdges()))
	}
	 :=  / float64(len(.LayerlessNodes))

	 := .AddLayer()
	.Layers = append(.Layers, )
	 := append([]layered.LNodeID(nil), ...)
	 := append([]int(nil), ...)
	 := make(map[layered.LNodeID]struct{})
	 := make(map[layered.LNodeID]struct{})
	,  := 0.0, 0.0

	 := func( layered.LNodeID) bool {
		 := .Node().ID
		 := -float64([])*+[] > 
		 := +float64([])* > **
		return  || 
	}
	for len() > 0 {
		 := -1
		for ,  := range  {
			if [.Node().ID] <= 0 {
				 = 
				break
			}
		}
		if  < 0 || ([]) && len() > 0 {
			for ,  := range .Layer().Nodes {
				for ,  := range .NodeIncomingEdges() {
					 := .EdgeSourceNode()
					[.Node().ID]--
				}
			}
			 = .AddLayer()
			.Layers = append(.Layers, )
			for  := range  {
				[] = struct{}{}
			}
			clear()
			,  = , 0
			continue
		}

		 := []
		if () {
			.Layers = .Layers[:0]
			 = .AddLayer()
			.Layers = append(.Layers, )
			,  = 0, 0
			clear()
			clear()
			++
			 = append([:0], ...)
			copy(, )
			continue
		}

		.SetNodeLayer(, &)
		 = append([:], [+1:]...)
		[] = struct{}{}
		 := .Node().ID
		 =  - float64([])* + []
		 += float64([]) * 
	}

	.LayerlessNodes = .LayerlessNodes[:0]
	for ,  := 0, len(.Layers)-1;  < ; ,  = +1, -1 {
		.Layers[], .Layers[] = .Layers[], .Layers[]
	}
	return nil
}

func stretchWidthRank( *layered.LGraphArena,  layered.LNodeID) int {
	 := len(.NodeOutgoingEdges())
	for ,  := range .NodeIncomingEdges() {
		 := .EdgeSourceNode()
		if  := len(.NodeOutgoingEdges());  >  {
			 = 
		}
	}
	return 
}