// Copyright (c) 2010, 2020 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 orthogonal

import (
	
	

	basegraph 
	
	
)

const (
	Tolerance                       = 1e-3
	criticalConflictsDetected       = -1
	conflictThresholdFactor         = 0.5
	criticalConflictThresholdFactor = 0.2
	conflictPenalty                 = 1
	crossingPenalty                 = 16
)

// Generator is ELK 0.8.1's direction-independent orthogonal routing
// generator. One instance is reused for every adjacent layer pair in phase 5.
type Generator struct {
	segmentSplitter           *segmentSplitter
	strategy                  *routingDirectionStrategy
	edgeSpacing               float64
	conflictThreshold         float64
	criticalConflictThreshold float64
}

func ( RoutingDirection,  float64) *Generator {
	return &Generator{
		strategy:          newRoutingDirectionStrategy(),
		edgeSpacing:       ,
		conflictThreshold: conflictThresholdFactor * ,
	}
}

// RouteEdges routes the connected components formed by output ports on the
// selected sides of two adjacent layers. A nil node slice represents a graph
// boundary, just like a null Java iterable.
func ( *Generator) (
	 *layered.LGraphArena,
	 layered.LGraphID,
	 []layered.LNodeID,
	 int,
	 []layered.LNodeID,
	 float64,
) int {
	_ =  // retained because it identifies debug graphs upstream
	 := make(map[layered.LPortID]*HyperEdgeSegment)
	 := make([]*HyperEdgeSegment, 0)
	.createHyperEdgeSegments(, , .strategy.sourcePortSide(), &, )
	.createHyperEdgeSegments(, , .strategy.targetPortSide(), &, )

	.criticalConflictThreshold = criticalConflictThresholdFactor * minimumHorizontalSegmentDistance()
	 := 0
	for  := 0;  < len()-1; ++ {
		for  :=  + 1;  < len(); ++ {
			 += .CreateDependencyIfNecessary([], [])
		}
	}
	 := basegraph.Get(&.Graph().Properties, layered.Random)
	if  == nil {
		 = javacompat.NewRandom(int64(basegraph.Get(&.Graph().Properties, layered.RandomSeed)))
		basegraph.Set(&.Graph().Properties, layered.Random, )
	}
	if  >= 2 {
		 = .breakCriticalCycles(, )
	}
	BreakNonCriticalCycles(, )
	TopologicalNumbering()

	 := -1
	for ,  := range  {
		if math.Abs(.Start-.End) < Tolerance {
			continue
		}
		if .RoutingSlot >  {
			 = .RoutingSlot
		}
		.strategy.calculateBendPoints(, , , .edgeSpacing)
	}
	.strategy.clearCreatedJunctionPoints()
	return  + 1
}

func ( *Generator) (
	 *layered.LGraphArena,
	 []layered.LNodeID,
	 layered.PortSide,
	 *[]*HyperEdgeSegment,
	 map[layered.LPortID]*HyperEdgeSegment,
) {
	for ,  := range  {
		for ,  := range .Node().Ports {
			 := .Port()
			if .Side !=  || len(.OutgoingEdges) == 0 {
				continue
			}
			if ,  := [];  {
				continue
			}
			 := newHyperEdgeSegment(.strategy)
			* = append(*, )
			.addPortPositions(, , )
		}
	}
}

func minimumHorizontalSegmentDistance( []*HyperEdgeSegment) float64 {
	,  := make([]float64, 0), make([]float64, 0)
	for ,  := range  {
		 = append(, .IncomingCoordinates...)
		 = append(, .OutgoingCoordinates...)
	}
	return math.Min(minimumDifference(), minimumDifference())
}

func minimumDifference( []float64) float64 {
	if len() < 2 {
		return math.MaxFloat64
	}
	 = append([]float64(nil), ...)
	sort.Float64s()
	 := math.MaxFloat64
	 := [0]
	for  := 1;  < len(); ++ {
		 := []
		if  ==  {
			continue
		}
		 = math.Min(, -)
		 = 
	}
	return 
}

// CreateDependencyIfNecessary ports the conflict and crossing comparison used
// both during graph construction and after a critical segment split.
func ( *Generator) (,  *HyperEdgeSegment) int {
	if math.Abs(.Start-.End) < Tolerance || math.Abs(.Start-.End) < Tolerance {
		return 0
	}
	 := .countConflicts(.OutgoingCoordinates, .IncomingCoordinates)
	 := .countConflicts(.OutgoingCoordinates, .IncomingCoordinates)
	if  == criticalConflictsDetected ||  == criticalConflictsDetected {
		 := 0
		if  == criticalConflictsDetected {
			AddCriticalDependency(, )
			++
		}
		if  == criticalConflictsDetected {
			AddCriticalDependency(, )
			++
		}
		return 
	}

	 := CountCrossings(.OutgoingCoordinates, .Start, .End) +
		CountCrossings(.IncomingCoordinates, .Start, .End)
	 := CountCrossings(.OutgoingCoordinates, .Start, .End) +
		CountCrossings(.IncomingCoordinates, .Start, .End)
	 := conflictPenalty* + crossingPenalty*
	 := conflictPenalty* + crossingPenalty*
	switch {
	case  < :
		AddRegularDependency(, , -)
	case  > :
		AddRegularDependency(, , -)
	case  > 0 &&  > 0:
		AddRegularDependency(, , 0)
		AddRegularDependency(, , 0)
	}
	return 0
}

func ( *Generator) (,  []float64) int {
	if len() == 0 || len() == 0 {
		return 0
	}
	, ,  := 0, 0, 0
	,  := [0], [0]
	for {
		if  > -.criticalConflictThreshold &&
			 < +.criticalConflictThreshold {
			return criticalConflictsDetected
		}
		if  > -.conflictThreshold &&
			 < +.conflictThreshold {
			++
		}
		if  <=  && +1 < len() {
			++
			 = []
		} else if  <=  && +1 < len() {
			++
			 = []
		} else {
			break
		}
	}
	return 
}

func ( []float64, ,  float64) int {
	 := 0
	for ,  := range  {
		if  >  {
			break
		}
		if  >=  {
			++
		}
	}
	return 
}

func ( *Generator) ( []*HyperEdgeSegment,  *javacompat.Random) []*HyperEdgeSegment {
	 := DetectCycles(, true, )
	if .segmentSplitter == nil {
		.segmentSplitter = &segmentSplitter{generator: }
	}
	.segmentSplitter.splitSegments(, &, .criticalConflictThreshold)
	return 
}

// TopologicalNumbering assigns routing slots and then pushes purely
// right-pointing targets as far toward their target layer as possible.
func ( []*HyperEdgeSegment) {
	,  := make([]*HyperEdgeSegment, 0), make([]*HyperEdgeSegment, 0)
	for ,  := range  {
		.InWeight = len(.IncomingDependencies)
		.OutWeight = len(.OutgoingDependencies)
		if .InWeight == 0 {
			 = append(, )
		}
		if .OutWeight == 0 && len(.IncomingCoordinates) == 0 {
			 = append(, )
		}
	}
	 := -1
	for len() > 0 {
		 := [0]
		 = [1:]
		for ,  := range .OutgoingDependencies {
			 := .Target
			.RoutingSlot = maxInt(.RoutingSlot, .RoutingSlot+1)
			 = maxInt(, .RoutingSlot)
			.InWeight--
			if .InWeight == 0 {
				 = append(, )
			}
		}
	}
	if  <= -1 {
		return
	}
	for ,  := range  {
		.RoutingSlot = 
	}
	for len() > 0 {
		 := [0]
		 = [1:]
		for ,  := range .IncomingDependencies {
			 := .Source
			if len(.IncomingCoordinates) > 0 {
				continue
			}
			.RoutingSlot = minInt(.RoutingSlot, .RoutingSlot-1)
			.OutWeight--
			if .OutWeight == 0 {
				 = append(, )
			}
		}
	}
}

func minInt(,  int) int {
	if  <  {
		return 
	}
	return 
}

func maxInt(,  int) int {
	if  >  {
		return 
	}
	return 
}