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

import (
	
	

	basegraph 
	
	
	
)

var (
	modelOrderCrossingCounterNodeInfluence = basegraph.PropertyWithDefault(
		"org.eclipse.elk.layered.considerModelOrder.crossingCounterNodeInfluence",
		func() float64 { return 0 },
	)
	modelOrderCrossingCounterPortInfluence = basegraph.PropertyWithDefault(
		"org.eclipse.elk.layered.considerModelOrder.crossingCounterPortInfluence",
		func() float64 { return 0 },
	)
)

// LayerSweepCrossingMinimizer is ELK Layered's phase-three layer sweep. Its
// zero value is the BARYCENTER phase implementation used by the provider.
type LayerSweepCrossingMinimizer struct {
	Type CrossMinType

	graphInfoHolders            []*GraphInfoHolder
	graphsWhoseNodeOrderChanged []int
	random                      *javacompat.Random
	randomSeed                  int64
}

func ( CrossMinType) *LayerSweepCrossingMinimizer {
	return &LayerSweepCrossingMinimizer{Type: }
}

// HierarchyAware is a marker used by the layered executor. In an
// INCLUDE_CHILDREN layout this processor must be paused on child graphs and
// invoked once on the root after every graph has completed all processors
// preceding phase three.
func (*LayerSweepCrossingMinimizer) () {}

func ( *LayerSweepCrossingMinimizer) (
	 *layered.LGraphArena,
	 layered.LGraphID,
) error {
	return .ProcessHierarchy(, )
}

// ProcessHierarchy is the source-shaped hierarchy-aware entry point. graphID
// must be the hierarchy root; initialization then discovers every child graph
// breadth-first and assigns GraphInfoHolder indices before sweeping bottom-up
// or through nested graphs as decided by LayerSweepTypeDecider.
func ( *LayerSweepCrossingMinimizer) (
	 *layered.LGraphArena,
	 layered.LGraphID,
) error {
	if .Graph().ParentNode != nil {
		return fmt.Errorf("p3order: hierarchy-aware layer sweep must be invoked on the root graph")
	}
	 := .Graph()
	 := len(.Layers) == 0
	if ! {
		 = true
		for ,  := range .Layers {
			if len(.Layer().Nodes) > 0 {
				 = false
				break
			}
		}
	}
	 := len(.Layers) == 1 && len(.Layer(.Layers[0]).Nodes) == 1
	 := basegraph.Get(&.Properties, layered.Hierarchy) == layered.HierarchyIncludeChildren
	if  ||  && ! {
		return nil
	}
	,  := .initialize(, )
	if  != nil {
		return 
	}
	if len() == 0 {
		return nil
	}
	 := .graphInfoHolders[[0]]
	for ,  := range  {
		 := .graphInfoHolders[]
		if len(.CurrentNodeOrder) == 0 {
			continue
		}
		switch {
		case !.CrossMinDeterministic():
			.compareDifferentRandomizedLayouts(, )
		case .CrossMinAlwaysImproves():
			.minimizeCrossingsNoCounter(, )
		default:
			.minimizeCrossingsWithCounter(, )
		}
		if .HasParent {
			.setPortOrderOnParentGraph(, )
		}
	}
	.transferNodeAndPortOrdersToGraph()
	return nil
}

func ( *LayerSweepCrossingMinimizer) (
	 *layered.LGraphArena,
	 int,
) {
	 := .graphInfoHolders[]
	 := .random.NextBoolean()
	 := true
	for  {
		 = .CrossMinimizer.SetFirstLayerOrder(.CurrentNodeOrder, )
		 = .sweepReducingCrossings(, , , false) || 
		 = !
	}
	.setCurrentlyBestNodeOrders()
}

func ( *LayerSweepCrossingMinimizer) (
	 *layered.LGraphArena,
	 layered.LGraphID,
) layered.ProcessorConfiguration {
	var  layered.ProcessorConfiguration
	.AddBefore(layered.PhaseNodeOrdering, layered.LongEdgeSplitter)
	.AddBefore(layered.PhaseNodeOrdering, layered.PortListSorter)
	.AddBefore(layered.PhaseNodePlacement, layered.InLayerConstraintProcessor)
	.AddAfter(layered.PhaseEdgeRouting, layered.LongEdgeJoiner)
	return 
}

func ( *LayerSweepCrossingMinimizer) (
	 *layered.LGraphArena,
	 layered.LGraphID,
) ([]int, error) {
	.graphInfoHolders = nil
	.graphsWhoseNodeOrderChanged = nil
	,  := basegraph.TryGet(&.Graph().Properties, layered.Random)
	if ! ||  == nil {
		 := basegraph.Get(&.Graph().Properties, layered.RandomSeed)
		 = javacompat.NewRandom(int64())
		basegraph.Set(&.Graph().Properties, layered.Random, )
	}
	.random = 
	.randomSeed = .NextLong()

	 := make([]int, 0)
	 := []layered.LGraphID{}
	for  := 0;  < len(); ++ {
		 := []
		.Graph().ID = 
		,  := NewGraphInfoHolder(
			, , .Type, .graphInfoHolders, ,
		)
		if  != nil {
			return nil, 
		}
		 = append(, .ChildGraphs...)
		.graphInfoHolders = append(.graphInfoHolders, )
		if .DontSweepInto() {
			 = append([]int{}, ...)
		}
	}
	return , nil
}

func ( *LayerSweepCrossingMinimizer) (
	 *layered.LGraphArena,
	 int,
) {
	.random.SetSeed(.randomSeed)
	.graphsWhoseNodeOrderChanged = .graphsWhoseNodeOrderChanged[:0]
	 := .graphInfoHolders[]
	 := .Graph(.LGraph)
	 := basegraph.Get(&.Properties, modelOrderCrossingCounterNodeInfluence)

	// ELK 0.8.1 checks the node influence twice here. Preserve the typo: the
	// port influence alone must not select the floating-point counter path.
	if  != 0 ||
		basegraph.Get(&.Properties, modelOrderCrossingCounterNodeInfluence) != 0 {
		 := math.MaxFloat64
		if basegraph.Get(&.Properties, layered.ConsiderModelOrder) != layered.OrderingNone {
			basegraph.Set(&.Properties, layered.FirstTryWithInitialOrder, true)
		}
		for  := 0;  < basegraph.Get(&.Properties, layered.Thoroughness); ++ {
			 := .minimizeCrossingsNodePortOrderWithCounter(, )
			if  <  {
				 = 
				.saveAllNodeOrdersOfChangedGraphs()
				if  == 0 {
					break
				}
			}
		}
		return
	}

	 := int(^uint(0) >> 1)
	if basegraph.Get(&.Properties, layered.ConsiderModelOrder) != layered.OrderingNone {
		basegraph.Set(&.Properties, layered.FirstTryWithInitialOrder, true)
	}
	for  := 0;  < basegraph.Get(&.Properties, layered.Thoroughness); ++ {
		 := .minimizeCrossingsWithCounter(, )
		if  <  {
			 = 
			.saveAllNodeOrdersOfChangedGraphs()
			if  == 0 {
				break
			}
		}
	}
}

func ( *LayerSweepCrossingMinimizer) (
	 *layered.LGraphArena,
	 int,
) int {
	 := .graphInfoHolders[]
	 := .Graph(.LGraph)
	 := .random.NextBoolean()

	// ELK 0.9 keeps a crossing-free model order completely unchanged. A
	// regular first sweep may otherwise shuffle unconnected ports even though
	// the input order is already optimal.
	if basegraph.Get(&.Properties, layered.FirstTryWithInitialOrder) &&
		.countCurrentNumberOfCrossings(, ) == 0 {
		return 0
	}
	if (!basegraph.Get(&.Properties, layered.FirstTryWithInitialOrder) &&
		!basegraph.Get(&.Properties, layered.SecondTryWithInitialOrder)) ||
		basegraph.Get(&.Properties, layered.ConsiderModelOrder) == layered.OrderingNone {
		.CrossMinimizer.SetFirstLayerOrder(.CurrentNodeOrder, )
	} else {
		 = basegraph.Get(&.Properties, layered.FirstTryWithInitialOrder)
	}
	.sweepReducingCrossings(, , , true)

	// These two properties intentionally share one raw key in ELK 0.8.1.
	// Re-read after each mutation instead of caching both values.
	if basegraph.Get(&.Properties, layered.SecondTryWithInitialOrder) {
		basegraph.Set(&.Properties, layered.SecondTryWithInitialOrder, false)
	}
	if basegraph.Get(&.Properties, layered.FirstTryWithInitialOrder) {
		basegraph.Set(&.Properties, layered.FirstTryWithInitialOrder, false)
		basegraph.Set(&.Properties, layered.SecondTryWithInitialOrder, true)
	}

	 := .countCurrentNumberOfCrossings(, )
	 := 
	for {
		.setCurrentlyBestNodeOrders()
		if  == 0 {
			return 0
		}
		 = !
		 = 
		.sweepReducingCrossings(, , , false)
		 = .countCurrentNumberOfCrossings(, )
		if  <=  {
			return 
		}
	}
}

func ( *LayerSweepCrossingMinimizer) (
	 *layered.LGraphArena,
	 int,
) float64 {
	 := .graphInfoHolders[]
	 := .Graph(.LGraph)
	 := .random.NextBoolean()

	// See minimizeCrossingsWithCounter. Preserve the initial node and port
	// order when the weighted counter already reports an optimum.
	if basegraph.Get(&.Properties, layered.FirstTryWithInitialOrder) &&
		.countCurrentNumberOfCrossingsNodePortOrder(, ) == 0 {
		return 0
	}
	if (!basegraph.Get(&.Properties, layered.FirstTryWithInitialOrder) &&
		!basegraph.Get(&.Properties, layered.SecondTryWithInitialOrder)) ||
		basegraph.Get(&.Properties, layered.ConsiderModelOrder) == layered.OrderingNone {
		.CrossMinimizer.SetFirstLayerOrder(.CurrentNodeOrder, )
	} else {
		 = basegraph.Get(&.Properties, layered.FirstTryWithInitialOrder)
	}
	.sweepReducingCrossings(, , , true)
	if basegraph.Get(&.Properties, layered.SecondTryWithInitialOrder) {
		basegraph.Set(&.Properties, layered.SecondTryWithInitialOrder, false)
	}
	if basegraph.Get(&.Properties, layered.FirstTryWithInitialOrder) {
		basegraph.Set(&.Properties, layered.FirstTryWithInitialOrder, false)
		basegraph.Set(&.Properties, layered.SecondTryWithInitialOrder, true)
	}

	 := .countCurrentNumberOfCrossingsNodePortOrder(, )
	 := 
	for {
		.setCurrentlyBestNodeOrders()
		if  == 0 {
			return 0
		}
		 = !
		 = 
		.sweepReducingCrossings(, , , false)
		 = .countCurrentNumberOfCrossingsNodePortOrder(, )
		if  <=  {
			return 
		}
	}
}

func ( *LayerSweepCrossingMinimizer) (
	 *layered.LGraphArena,
	 int,
	,  bool,
) bool {
	 := .graphInfoHolders[]
	 := .CurrentNodeOrder
	 := len()
	 := sweepFirstIndex(, )
	 := .PortDistributor.DistributePortsWhileSweeping(, , , )
	 = .sweepInHierarchicalNodes(, [], , ) || 
	for  := sweepFirstFree(, ); sweepNotAtEnd(, , );  += sweepNext() {
		 := .Graph(.LGraph)
		 :=  &&
			!basegraph.Get(&.Properties, layered.FirstTryWithInitialOrder) &&
			!basegraph.Get(&.Properties, layered.SecondTryWithInitialOrder)
		 = .CrossMinimizer.MinimizeCrossings(, , , ) || 
		 = .PortDistributor.DistributePortsWhileSweeping(, , , ) || 
		 = .sweepInHierarchicalNodes(, [], , ) || 
	}
	.markGraphChanged()
	return 
}

func ( *LayerSweepCrossingMinimizer) (
	 *layered.LGraphArena,
	 []layered.LNodeID,
	,  bool,
) bool {
	 := false
	for ,  := range  {
		 := .Node().NestedGraph
		if  == nil {
			continue
		}
		 := .Graph(*).ID
		if .graphInfoHolders[].DontSweepInto() {
			continue
		}
		 = .sweepInHierarchicalNode(, , , ) || 
	}
	return 
}

func ( *LayerSweepCrossingMinimizer) (
	 *layered.LGraphArena,
	 layered.LNodeID,
	,  bool,
) bool {
	 := *.Node().NestedGraph
	 := .Graph().ID
	 := .graphInfoHolders[]
	 := sweepFirstIndex(, len(.CurrentNodeOrder))
	 := .CurrentNodeOrder[][0]
	if .Node().Type == layered.ExternalPortNode {
		.CurrentNodeOrder[] = .sortPortDummiesByPortPositions(
			, , .CurrentNodeOrder[], sideOpposedSweep(),
		)
	} else {
		.CrossMinimizer.SetFirstLayerOrder(.CurrentNodeOrder, )
	}
	 := .sweepReducingCrossings(, , , )
	.sortPortsByDummyPositionsInLastLayer(, .CurrentNodeOrder, *.Parent, )
	return 
}

func ( *LayerSweepCrossingMinimizer) (
	 *layered.LGraphArena,
	 layered.LNodeID,
	 []layered.LNodeID,
	 layered.PortSide,
) []layered.LNodeID {
	 := make([]layered.LNodeID, 0, len())
	for ,  := range portsInNorthSouthEastWestOrder(, , ) {
		if !basegraph.Get(&.Port().Properties, layered.InsideConnections) {
			continue
		}
		,  := basegraph.TryGet(&.Port().Properties, layered.PortDummy)
		if  {
			 = append(, )
		}
	}
	if len() < len() {
		panic(fmt.Sprintf(
			"p3order: expected %d hierarchical ports, but found only %d",
			len(), len(),
		))
	}
	return 
}

func ( *LayerSweepCrossingMinimizer) (
	 *layered.LGraphArena,
	 [][]layered.LNodeID,
	 layered.LNodeID,
	 bool,
) {
	 := sweepEndIndex(, len())
	 := []
	 := sweepFirstIndex(, len())
	if .Node([]).Type != layered.ExternalPortNode {
		return
	}
	 := .Node().Ports
	for ,  := range  {
		 := .Port()
		 :=  && .Side == layered.EastSide ||
			! && .Side == layered.WestSide
		if ! || !basegraph.Get(&.Properties, layered.InsideConnections) {
			continue
		}
		if  < 0 ||  >= len() {
			panic(fmt.Sprintf(
				"p3order: hierarchical port/dummy mismatch for parent %d graph %d side %v: port %d at parent index %d needs dummy index %d in layer %v",
				, .Node().Graph, .Side, , , , ,
			))
		}
		,  := basegraph.TryGet(&.Node([]).Properties, layered.OriginalElement)
		if ! || .Kind != layered.OriginLPort {
			panic("p3order: external port dummy has no LPort origin")
		}
		[] = .LPort
		 += sweepNext()
	}
	.Node().Ports = 
	.InvalidatePortSideCache()
}

func ( *LayerSweepCrossingMinimizer) (
	 *layered.LGraphArena,
	 *GraphInfoHolder,
) {
	if !.HasExternalPorts {
		return
	}
	 := .GetBestSweep()
	if  == nil {
		return
	}
	.sortPortsByDummyPositionsInLastLayer(, .Nodes(), *.Parent, true)
	.sortPortsByDummyPositionsInLastLayer(, .Nodes(), *.Parent, false)
	basegraph.Set(
		&.Node(*.Parent).Properties,
		layered.PortConstraintsOption,
		layered.PortConstraintsFixedOrder,
	)
}

func ( *LayerSweepCrossingMinimizer) (
	 *layered.LGraphArena,
	 int,
) int {
	 := .graphInfoHolders[]
	 := .CrossingsCounter.CountAllCrossings(, .CurrentNodeOrder)
	for ,  := range .ChildGraphs {
		 := .Graph().ID
		if !.graphInfoHolders[].DontSweepInto() {
			 += .(, )
		}
	}
	return 
}

func ( *LayerSweepCrossingMinimizer) (
	 *layered.LGraphArena,
	 int,
) float64 {
	 := .graphInfoHolders[]
	 := .Graph(.LGraph)
	 := 0.0
	 := basegraph.Get(&.Properties, layered.ConsiderModelOrder)
	if  != layered.OrderingNone {
		 += basegraph.Get(&.Properties, modelOrderCrossingCounterNodeInfluence) *
			float64(countModelOrderNodeChanges(, .CurrentNodeOrder, ))
		 += basegraph.Get(&.Properties, modelOrderCrossingCounterPortInfluence) *
			float64(countModelOrderPortChanges(, .CurrentNodeOrder, ,
				basegraph.Get(&.Properties, layered.PortModelOrder)))
	}
	 := float64(.CrossingsCounter.CountAllCrossings(, .CurrentNodeOrder)) + 
	for ,  := range .ChildGraphs {
		 := .Graph().ID
		if !.graphInfoHolders[].DontSweepInto() {
			// ELK calls the integer counting method for children here.
			 += float64(.countCurrentNumberOfCrossings(, ))
		}
	}
	return 
}

func ( *LayerSweepCrossingMinimizer) (
	 *layered.LGraphArena,
) {
	for ,  := range .graphsWhoseNodeOrderChanged {
		 := .graphInfoHolders[]
		.CurrentlyBestNodeAndPortOrder = NewSweepCopy(, .CurrentNodeOrder)
	}
}

func ( *LayerSweepCrossingMinimizer) () {
	for ,  := range .graphsWhoseNodeOrderChanged {
		 := .graphInfoHolders[]
		if .CurrentlyBestNodeAndPortOrder != nil {
			.BestNodeAndPortOrder = .CurrentlyBestNodeAndPortOrder.Clone()
		}
	}
}

func ( *LayerSweepCrossingMinimizer) (
	 *layered.LGraphArena,
) {
	for ,  := range .graphInfoHolders {
		if  := .GetBestSweep();  != nil {
			.TransferNodeAndPortOrdersToGraph(, .LGraph, true)
		}
	}
}

func ( *LayerSweepCrossingMinimizer) ( int) {
	for ,  := range .graphsWhoseNodeOrderChanged {
		if  ==  {
			return
		}
	}
	.graphsWhoseNodeOrderChanged = append(.graphsWhoseNodeOrderChanged, )
}

func countModelOrderNodeChanges(
	 *layered.LGraphArena,
	 [][]layered.LNodeID,
	 layered.OrderingStrategy,
) int {
	 := 0
	 := -1
	for ,  := range  {
		 := [0]
		if  >= 0 {
			 = []
		}
		 := preserveorder.NewNodeComparator(
			, , , preserveorder.LongEdgeEqual, false)
		for  := 0;  < len(); ++ {
			for  :=  + 1;  < len(); ++ {
				if basegraph.Has(&.Node([]).Properties, layered.ModelOrder) &&
					basegraph.Has(&.Node([]).Properties, layered.ModelOrder) &&
					.Compare([], []) > 0 {
					++
				}
			}
		}
		++
	}
	return 
}

func countModelOrderPortChanges(
	 *layered.LGraphArena,
	 [][]layered.LNodeID,
	 layered.OrderingStrategy,
	 bool,
) int {
	 := 0
	 := -1
	for ,  := range  {
		 := [0]
		if  >= 0 {
			 = []
		}
		for ,  := range  {
			 := .Node()
			 := preserveorder.NewPortComparator(
				,
				,
				,
				basegraph.Get(&.Properties, layered.TargetNodeModelOrder),
				,
			)
			 := .Node().Ports
			for  := 0;  < len(); ++ {
				for  :=  + 1;  < len(); ++ {
					if .Compare([], []) > 0 {
						++
					}
				}
			}
		}
		++
	}
	return 
}

func sweepFirstIndex( bool,  int) int {
	if  {
		return 0
	}
	return  - 1
}

func sweepEndIndex( bool,  int) int {
	if  {
		return  - 1
	}
	return 0
}

func sweepFirstFree( bool,  int) int {
	if  {
		return 1
	}
	return  - 2
}

func sweepNext( bool) int {
	if  {
		return 1
	}
	return -1
}

func sweepNotAtEnd( bool, ,  int) bool {
	if  {
		return  < 
	}
	return  >= 0
}

func sideOpposedSweep( bool) layered.PortSide {
	if  {
		return layered.WestSide
	}
	return layered.EastSide
}