// Copyright (c) 2010, 2015 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 p4nodes

import (
	

	basegraph 
	
)

// LinearSegmentsNodePlacer is the ELK 0.8.1 Sander-style placement phase. A
// segment consists of one regular node or a chain of long-edge / north-south
// port dummies. The dependency order is placed first, then balanced by the
// alternating pendulum and rubber iterations from the Java implementation.
type LinearSegmentsNodePlacer struct {
	segments       []*linearSegment
	inputPriority  map[layered.LNodeID]int
	outputPriority map[layered.LNodeID]int
}

type linearSegment struct {
	nodes            []layered.LNodeID
	id               int
	indexInLastLayer int
	lastLayer        int
	deflection       float64
	weight           int
	reference        *linearSegment
	nodeType         layered.NodeType
}

func ( *linearSegment) () *linearSegment {
	 := 
	for .reference != nil {
		 = .reference
	}
	return 
}

func ( *linearSegment) (
	 *layered.LGraphArena,
	 layered.LNodeID,
	 int,
) *linearSegment {
	 := 0
	for  < len(.nodes) && .nodes[] !=  {
		++
	}
	 := &linearSegment{
		nodes:            append([]layered.LNodeID(nil), .nodes[:]...),
		id:               ,
		indexInLastLayer: -1,
		lastLayer:        -1,
	}
	.nodes = .nodes[:]
	for ,  := range .nodes {
		.Node().ID = 
	}
	return 
}

func (*LinearSegmentsNodePlacer) (
	 *layered.LGraphArena,
	 layered.LGraphID,
) layered.ProcessorConfiguration {
	var  layered.ProcessorConfiguration
	if basegraph.Get(&.Graph().Properties, layered.GraphProperties)&layered.GraphPropertyExternalPorts != 0 {
		.AddBefore(layered.PhaseEdgeRouting, layered.HierarchicalPortPositionProcessor)
	}
	return 
}

func ( *LinearSegmentsNodePlacer) (
	 *layered.LGraphArena,
	 layered.LGraphID,
) error {
	.sortLinearSegments(, )
	.createUnbalancedPlacement(, )
	.balancePlacement(, )
	.postProcess(, )
	.segments = nil
	.inputPriority = nil
	.outputPriority = nil
	return nil
}

func ( *LinearSegmentsNodePlacer) (
	 *layered.LGraphArena,
	 layered.LGraphID,
) {
	.inputPriority = make(map[layered.LNodeID]int)
	.outputPriority = make(map[layered.LNodeID]int)
	 := make([]*linearSegment, 0)
	for ,  := range .Graph().Layers {
		for ,  := range .Layer().Nodes {
			 := .Node()
			.ID = -1
			,  := math.MinInt, math.MinInt
			for ,  := range .Ports {
				 := .Port()
				for ,  := range .IncomingEdges {
					 = max(, basegraph.Get(&.Edge().Properties, layered.PriorityStraightness))
				}
				for ,  := range .OutgoingEdges {
					 = max(, basegraph.Get(&.Edge().Properties, layered.PriorityStraightness))
				}
			}
			.inputPriority[] = 
			.outputPriority[] = 
		}
	}

	 := 0
	for ,  := range .Graph().Layers {
		for ,  := range .Layer().Nodes {
			if .Node().ID < 0 {
				 := &linearSegment{id: , indexInLastLayer: -1, lastLayer: -1}
				++
				.fillSegment(, , )
				 = append(, )
			}
		}
	}

	 := make([][]*linearSegment, len())
	 := make([]int, len())
	.createDependencyGraphEdges(, , &, &, &)

	 := make([]*linearSegment, 0)
	for ,  := range  {
		if [] == 0 {
			 = append(, )
		}
	}
	 := make([]int, len())
	 := 0
	for len() > 0 {
		 := [0]
		 = [1:]
		[.id] = 
		++
		for len([.id]) > 0 {
			 := [.id][0]
			[.id] = [.id][1:]
			[.id]--
			if [.id] == 0 {
				 = append(, )
			}
		}
	}

	.segments = make([]*linearSegment, len())
	for ,  := range  {
		 := []
		.segments[] = 
		.id = 
		for ,  := range .nodes {
			.Node().ID = 
		}
	}
}

func ( *LinearSegmentsNodePlacer) (
	 *layered.LGraphArena,
	 layered.LGraphID,
	 *[]*linearSegment,
	 *[][]*linearSegment,
	 *[]int,
) {
	 := len(*)
	 := 0
	for ,  := range .Graph().Layers {
		 := .Layer().Nodes
		if len() == 0 {
			continue
		}
		var  *layered.LNodeID
		for ,  := range  {
			 := (*)[.Node().ID]
			if .indexInLastLayer >= 0 {
				var  *linearSegment
				for ,  := range [+1:] {
					 := (*)[.Node().ID]
					if .lastLayer == .lastLayer &&
						.indexInLastLayer < .indexInLastLayer {
						 = 
						break
					}
				}
				if  != nil {
					if  != nil {
						 := .Node().ID
						(*)[]--
						 := .Node(*).ID
						(*)[] = removeLinearSegment((*)[], )
					}
					 = .split(, , )
					++
					* = append(*, )
					* = append(*, nil)
					if  != nil {
						 := .Node(*).ID
						(*)[] = append((*)[], )
						* = append(*, 1)
					} else {
						* = append(*, 0)
					}
				}
			}

			if +1 < len() {
				 := [+1]
				 := (*)[.Node().ID]
				 := .Node().ID
				 := .Node().ID
				(*)[] = append((*)[], )
				(*)[]++
			}
			.lastLayer = 
			.indexInLastLayer = 
			 := 
			 = &
		}
		++
	}
}

func removeLinearSegment( []*linearSegment,  *linearSegment) []*linearSegment {
	for ,  := range  {
		if  ==  {
			return append([:], [+1:]...)
		}
	}
	return 
}

func ( *LinearSegmentsNodePlacer) (
	 *layered.LGraphArena,
	 layered.LNodeID,
	 *linearSegment,
) bool {
	 := .Node()
	if .ID >= 0 {
		return false
	}
	.ID = .id
	.nodes = append(.nodes, )
	.nodeType = .Type
	if .Type != layered.LongEdgeNode && .Type != layered.NorthSouthPortNode {
		return true
	}
	for ,  := range .Ports {
		for ,  := range .Port().OutgoingEdges {
			 := .EdgeTargetNode()
			 := .Node()
			if .Layer != nil && .Layer != nil && *.Layer == *.Layer {
				continue
			}
			if .Type == layered.LongEdgeNode || .Type == layered.NorthSouthPortNode {
				if .(, , ) {
					return true
				}
			}
		}
	}
	return true
}

func ( *LinearSegmentsNodePlacer) (
	 *layered.LGraphArena,
	 layered.LGraphID,
) {
	 := .Graph()
	 := make([]int, len(.Layers))
	 := make([]*layered.LNodeID, len(.Layers))
	for ,  := range .segments {
		 := 0.0
		for ,  := range .nodes {
			 := .Node()
			 := .LayerIndex(*.Layer)
			[]++
			 := basegraph.Get(&.Properties, layered.SpacingEdgeEdge)
			if [] != nil {
				 = layered.VerticalSpacing(, *[], )
			}
			 = math.Max(, .Layer(*.Layer).Size.Y+)
		}
		for ,  := range .nodes {
			 := .Node()
			.Position.Y =  + .Margin.Top
			 := .Layer(*.Layer)
			.Size.Y =  + .Margin.Top + .Size.Y + .Margin.Bottom
			 := 
			[.LayerIndex(*.Layer)] = &
		}
	}
}

type linearSegmentsMode uint8

const (
	linearSegmentsForwardPendulum linearSegmentsMode = iota
	linearSegmentsBackwardPendulum
	linearSegmentsRubber
)

func ( *LinearSegmentsNodePlacer) (
	 *layered.LGraphArena,
	 layered.LGraphID,
) {
	 := .Graph()
	 := basegraph.Get(&.Properties, layered.LinearSegmentsDeflectionDampening)
	 := basegraph.Get(&.Properties, layered.Thoroughness)
	 := 4
	 := 3
	 := 20.0 / float64()
	 := false
	 := linearSegmentsForwardPendulum
	 := float64(math.MaxInt)
	for !( &&  <= 0) {
		 :=  != linearSegmentsBackwardPendulum
		 :=  != linearSegmentsForwardPendulum
		 := 0.0
		for ,  := range .segments {
			.reference = nil
			.calculateDeflection(, , , , )
			 += math.Abs(.deflection)
		}
		for .mergeRegions(, ) {
		}
		for ,  := range .segments {
			 := .region().deflection
			if  != 0 {
				for ,  := range .nodes {
					.Node().Position.Y += 
				}
			}
		}
		if  == linearSegmentsForwardPendulum ||  == linearSegmentsBackwardPendulum {
			--
			if  <= 0 && ( <  || - > ) {
				 = linearSegmentsRubber
				 = float64(math.MaxInt)
			} else if  == linearSegmentsForwardPendulum {
				 = linearSegmentsBackwardPendulum
				 = 
			} else {
				 = linearSegmentsForwardPendulum
				 = 
			}
		} else {
			 =  >=  || - < 
			 = 
			if  {
				--
			}
		}
	}
}

func ( *LinearSegmentsNodePlacer) (
	 *layered.LGraphArena,
	 *linearSegment,
	,  bool,
	 float64,
) {
	 := 0.0
	 := 0
	for ,  := range .nodes {
		 := .Node()
		 := 0.0
		 := 0
		,  := math.MinInt, math.MinInt
		if  {
			 = .inputPriority[]
		}
		if  {
			 = .outputPriority[]
		}
		 := max(, )
		for ,  := range .Ports {
			 := .Port()
			 := .Position.Y + .Position.Y + .Anchor.Y
			if  {
				for ,  := range .OutgoingEdges {
					 := *.Edge().Target
					 := *.Port().Node
					if  == .segments[.Node().ID] {
						continue
					}
					 := max(.inputPriority[], .outputPriority[])
					 := basegraph.Get(&.Edge().Properties, layered.PriorityStraightness)
					if  >=  &&  >=  {
						 := .Port()
						 += .Node().Position.Y + .Position.Y + .Anchor.Y - 
						++
					}
				}
			}
			if  {
				for ,  := range .IncomingEdges {
					 := *.Edge().Source
					 := *.Port().Node
					if  == .segments[.Node().ID] {
						continue
					}
					 := max(.inputPriority[], .outputPriority[])
					 := basegraph.Get(&.Edge().Properties, layered.PriorityStraightness)
					if  >=  &&  >=  {
						 := .Port()
						 += .Node().Position.Y + .Position.Y + .Anchor.Y - 
						++
					}
				}
			}
		}
		if  > 0 {
			 +=  / float64()
			++
		}
	}
	if  > 0 {
		.deflection =  *  / float64()
		.weight = 
	} else {
		.deflection = 0
		.weight = 0
	}
}

func ( *LinearSegmentsNodePlacer) (
	 *layered.LGraphArena,
	 layered.LGraphID,
) bool {
	 := false
	 := 0.0001 * basegraph.Get(&.Graph().Properties, layered.SpacingNodeNode)
	for ,  := range .Graph().Layers {
		 := .Layer().Nodes
		if len() == 0 {
			continue
		}
		 := [0]
		 := .segments[.Node().ID].region()
		for ,  := range [1:] {
			 := .segments[.Node().ID].region()
			if  !=  {
				,  := .Node(), .Node()
				 := layered.VerticalSpacing(, , )
				 := .Position.Y + .Size.Y + .Margin.Bottom + .deflection + 
				 := .Position.Y - .Margin.Top + .deflection
				if  > + {
					 := .weight + .weight
					.deflection = (float64(.weight)*.deflection + float64(.weight)*.deflection) / float64()
					.weight = 
					.reference = 
					 = true
				}
			}
			 = 
			 = 
		}
	}
	return 
}

func ( *LinearSegmentsNodePlacer) (
	 *layered.LGraphArena,
	 layered.LGraphID,
) {
	_ = 
	for ,  := range .segments {
		,  := float64(math.MaxInt), float64(math.MaxInt)
		for ,  := range .nodes {
			 := .Node()
			 := .Layer(*.Layer).Nodes
			 := 0
			for [] !=  {
				++
			}
			var  float64
			if  > 0 {
				 := [-1]
				 := .Node()
				 = .Position.Y - .Margin.Top -
					(.Position.Y + .Size.Y + .Margin.Bottom + layered.VerticalSpacing(, , ))
			} else {
				 = .Position.Y - .Margin.Top
			}
			 = math.Min(, )
			var  float64
			if +1 < len() {
				 := [+1]
				 := .Node()
				 = .Position.Y - .Margin.Top -
					(.Position.Y + .Size.Y + .Margin.Bottom + layered.VerticalSpacing(, , ))
			} else {
				 = 2 * .Position.Y
			}
			 = math.Min(, )
		}

		 := float64(math.MaxInt)
		 := false
		 := .Node(.nodes[0])
		for ,  := range .Ports {
			 := .Port()
			 := .Position.Y + .Position.Y + .Anchor.Y
			for ,  := range .IncomingEdges {
				 := .Port(*.Edge().Source)
				 := .Node(*.Node)
				 := .Position.Y + .Position.Y + .Anchor.Y - 
				 := 
				if  < 0 {
					 = 
				}
				if math.Abs() < math.Abs() && math.Abs() <  {
					,  = , true
				}
			}
		}
		 := .Node(.nodes[len(.nodes)-1])
		for ,  := range .Ports {
			 := .Port()
			 := .Position.Y + .Position.Y + .Anchor.Y
			for ,  := range .OutgoingEdges {
				 := .Port(*.Edge().Target)
				 := .Node(*.Node)
				 := .Position.Y + .Position.Y + .Anchor.Y - 
				 := 
				if  < 0 {
					 = 
				}
				if math.Abs() < math.Abs() && math.Abs() <  {
					,  = , true
				}
			}
		}
		if  &&  != 0 {
			for ,  := range .nodes {
				.Node().Position.Y += 
			}
		}
	}
}