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

import (
	
	

	basegraph 
	
)

var breakingPointInfo = basegraph.NewProperty[*BPInfo]("breakingPoint.info")

type BPInfo struct {
	Start, End                         layered.LNodeID
	NodeStartEdge, StartEndEdge        layered.LEdgeID
	OriginalEdge                       layered.LEdgeID
	StartInLayerDummy, EndInLayerDummy *layered.LNodeID
	StartInLayerEdge, EndInLayerEdge   *layered.LEdgeID
	Prev, Next                         *BPInfo
}

func ( *layered.LGraphArena,  layered.LNodeID) bool {
	,  := basegraph.TryGet(&.Node().Properties, breakingPointInfo)
	return  &&  != nil && .Start == 
}

func ( *layered.LGraphArena,  layered.LNodeID) bool {
	,  := basegraph.TryGet(&.Node().Properties, breakingPointInfo)
	return  &&  != nil && .End == 
}

// InsertBreakingPoints computes multi-edge cuts after layering and introduces
// the paired marker layers used by the later wrapping processors.
func ( *layered.LGraphArena,  layered.LGraphID) {
	 := .Graph()
	 := NewGraphStats(, )
	var  cutIndexCalculator
	switch basegraph.Get(&.Properties, layered.WrappingCuttingStrategy) {
	case layered.CuttingManual:
		 = manualCutIndexCalculator{}
	case layered.CuttingARD:
		 = ardCutIndexHeuristic{}
	default:
		 = msdCutIndexHeuristic{}
	}
	 := .cutIndexes(, , )
	if basegraph.Get(&.Properties, layered.WrappingMultiEdgeImproveCuts) {
		 = improveCuts(, , )
	}
	if !.guaranteesValid() && basegraph.Has(&.Properties, layered.WrappingValidifyStrategy) {
		switch basegraph.Get(&.Properties, layered.WrappingValidifyStrategy) {
		case layered.ValidifyLookBack:
			 = ValidifyIndexesLookingBack(, )
		case layered.ValidifyGreedy:
			 = ValidifyIndexesGreedily(, )
		}
	}
	if len() == 0 {
		return
	}
	applyCuts(, , )
}

func applyCuts( *layered.LGraphArena,  layered.LGraphID,  []int) int {
	 := .Graph()
	, ,  := 0, 0, 0
	 := [0]
	 := 0
	 := make(map[layered.LEdgeID]bool)
	 := make([]layered.LEdgeID, 0)
	 := make(map[layered.LEdgeID]bool)

	for  < len(.Layers) {
		 := .Layers[]
		++
		for ,  := range .Layer().Nodes {
			for ,  := range .NodeOutgoingEdges() {
				if ![] {
					[] = true
					 = append(, )
				}
			}
			for ,  := range .NodeIncomingEdges() {
				if [] {
					[] = false
				}
			}
		}

		if +1 ==  {
			 := .AddLayer()
			.Layers = insertLayer(.Layers, , )
			++
			 := .AddLayer()
			.Layers = insertLayer(.Layers, , )
			++

			for ,  := range  {
				if ![] {
					continue
				}
				if ![] {
					++
					[] = true
				}

				 := .AddNode()
				.Node().Type = layered.BreakingPointNode
				basegraph.Set(&.Node().Properties, layered.PortConstraintsOption, layered.PortConstraintsFixedSide)
				.SetNodeLayer(, &)
				 := .AddPort()
				.SetPortNode(, &)
				.SetPortSide(, layered.WestSide)
				 := .AddPort()
				.SetPortNode(, &)
				.SetPortSide(, layered.EastSide)

				 := .AddNode()
				.Node().Type = layered.BreakingPointNode
				basegraph.Set(&.Node().Properties, layered.PortConstraintsOption, layered.PortConstraintsFixedSide)
				.SetNodeLayer(, &)
				 := .AddPort()
				.SetPortNode(, &)
				.SetPortSide(, layered.WestSide)
				 := .AddPort()
				.SetPortNode(, &)
				.SetPortSide(, layered.EastSide)

				 := .AddEdge()
				 := *.Edge().Source
				.SetEdgeSource(, &)
				.SetEdgeTarget(, &)
				 := .AddEdge()
				.SetEdgeSource(, &)
				.SetEdgeTarget(, &)
				if ,  := basegraph.TryGet(
					&.Edge().Properties,
					layered.ModelOrder,
				);  {
					basegraph.Set(&.Edge().Properties, layered.ModelOrder, )
					basegraph.Set(&.Edge().Properties, layered.ModelOrder, )
				}
				.SetEdgeSource(, &)

				 := &BPInfo{
					Start: , End: ,
					NodeStartEdge: , StartEndEdge: ,
					OriginalEdge: ,
				}
				basegraph.Set(&.Node().Properties, breakingPointInfo, )
				basegraph.Set(&.Node().Properties, breakingPointInfo, )
				 := .EdgeSourceNode()
				if .Node().Type == layered.BreakingPointNode {
					 := basegraph.Get(&.Node().Properties, breakingPointInfo)
					.Next = 
					.Prev = 
				}
			}

			++
			if  < len() {
				 = []
			} else {
				break
			}
		}
		++
	}
	return 
}

func insertLayer( []layered.LayerID,  int,  layered.LayerID) []layered.LayerID {
	 = append(, 0)
	copy([+1:], [:])
	[] = 
	return 
}

type cut struct {
	index, newIndex int
	prev, successor *cut
	assigned        bool
}

func ( *cut) () *cut {
	if !.assigned {
		return 
	}
	if .successor != nil {
		return .successor.()
	}
	return nil
}

func ( *cut) () *cut {
	if .successor != nil {
		return .successor.selfOrNext()
	}
	return nil
}

func ( *cut) () {
	 := .newIndex - .index
	.offsetSelf()
	.offsetPrevious()
	.offsetSuccessor()
}

func ( *cut) ( int) { .index +=  }

func ( *cut) ( int) {
	if .prev != nil && !.prev.assigned {
		.prev.offsetSelf()
		.prev.()
	}
}

func ( *cut) ( int) {
	if .successor != nil && !.successor.assigned {
		.successor.offsetSelf()
		.successor.()
	}
}

func improveCuts( *layered.LGraphArena,  layered.LGraphID,  []int) []int {
	 := make([]int, 0, len())
	 := make([]*cut, 0, len())
	var  *cut
	for ,  := range  {
		 := &cut{index: }
		 = append(, )
		if  != nil {
			.prev = 
			.successor = 
		}
		 = 
	}
	 := computeEdgeSpans(, )
	for range  {
		var  *cut
		 := [0].selfOrNext()
		var  *cut
		 := math.Inf(1)
		for  := 1;  < len(.Graph().Layers); ++ {
			var  *cut
			var  int
			if  != nil {
				 = absInt(.index - )
			} else {
				 = absInt(-.index) + 1
			}
			 :=  + 1
			if  != nil {
				 = absInt( - .index)
			}
			 := 
			 = 
			if  <  {
				 = 
				 = 
			}
			 := computeCutScore(, , [], )
			if  <  {
				 = 
				 = 
				.newIndex = 
			}
			if  != nil &&  == .index {
				 = 
				 = .next()
			}
		}
		if  != nil {
			 = append(, .newIndex)
			.assigned = true
			.offset()
		}
	}
	sort.Ints()
	return 
}

func computeCutScore( *layered.LGraphArena,  layered.LGraphID, ,  int) float64 {
	 := basegraph.Get(&.Graph().Properties, layered.WrappingMultiEdgeDistancePenalty)
	return float64() + math.Pow(float64(), )
}

func computeEdgeSpans( *layered.LGraphArena,  layered.LGraphID) []int {
	 := make([]int, len(.Graph().Layers)+1)
	 := make(map[layered.LEdgeID]bool)
	for ,  := range .Graph().Layers {
		[] = len()
		for ,  := range .Layer().Nodes {
			for ,  := range .NodeOutgoingEdges() {
				[] = true
			}
		}
		for ,  := range .Layer().Nodes {
			for ,  := range .NodeIncomingEdges() {
				delete(, )
			}
		}
	}
	return 
}

func absInt( int) int {
	if  < 0 {
		return -
	}
	return 
}