// Copyright (c) 2010, 2020 Kiel University and others.
// Copyright (c) 2010, 2015 Kiel University and others.
// Copyright (c) 2015, 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 layeredlayout connects ELK Layered's internal five-phase pipeline
// to the core graph engine. It is separate from package layered to keep the
// phase subpackages acyclic.
package layeredlayout

import (
	

	
	basegraph 
	
	
	
	
	
	
	
	
	
	
)

type Provider struct{}

// Register adds the ELK Layered provider and its complete graph-feature
// declaration to the algorithm registry.
func ( *core.AlgorithmRegistry) error {
	return .Register(core.AlgorithmData{
		ID: "org.eclipse.elk.layered",
		Features: core.FeatureSelfLoops | core.FeatureInsideSelfLoops |
			core.FeatureMultiEdges | core.FeatureEdgeLabels | core.FeaturePorts |
			core.FeatureCompound | core.FeatureClusters | core.FeatureDisconnected,
		Create: func() core.LayoutProvider { return &Provider{} },
	})
}

func (*Provider) ( *basegraph.Model,  basegraph.NodeID,  core.ProgressMonitor) error {
	 := layered.NewElkGraphImporter()
	, ,  := .ImportGraph()
	if  != nil {
		return 
	}
	if basegraph.Get(&.Graph().Properties, layered.Hierarchy) == layered.HierarchyIncludeChildren {
		 := &layered.CompoundGraphPreprocessor{}
		if  := .Process(, );  != nil {
			return 
		}
		if  := runHierarchy(, , );  != nil {
			return 
		}
		 := &layered.CompoundGraphPostprocessor{}
		if  := .Process(, );  != nil {
			return 
		}
	} else if  := runComponents(, , );  != nil {
		return 
	}
	return layered.NewElkGraphLayoutTransferrer(, .Maps).ApplyLayout(, )
}

// runComponents mirrors ElkLayered.doLayout: GraphConfigurator is run once
// before splitting, all components share its Random instance, and completed
// component layouts are made layerless before packing.
func runComponents(
	 *layered.LGraphArena,
	 layered.LGraphID,
	 core.ProgressMonitor,
) error {
	layered.ConfigureGraphProperties(, )
	 := basegraph.Get(&.Graph().Properties, layered.Random)
	 := components.NewComponentsProcessor()
	,  := .Split(, )
	if  != nil {
		return 
	}
	for ,  := range  {
		,  := prepareGraphRun(, )
		if  != nil {
			return 
		}
		// prepareGraphRun invokes the configurator because hierarchy layout
		// needs that behavior. For components, restore the single Random object
		// created for the unsplit graph, as Java's copied properties do.
		basegraph.Set(&.Graph().Properties, layered.Random, )
		for  := 0;  < 6; ++ {
			if  := .runSlot(, , true, );  != nil {
				return 
			}
		}
		components.MakeLayerless(, )
	}
	return .Combine(, , )
}

func collectGraphsBottomUp( *layered.LGraphArena,  layered.LGraphID) []layered.LGraphID {
	 := []layered.LGraphID{}
	 := make([]layered.LGraphID, 0, len(.Graphs))
	for len() > 0 {
		 := [0]
		 = [1:]
		 = append(, )
		for ,  := range .Graph().LayerlessNodes {
			if  := .Node().NestedGraph;  != nil {
				 = append(, *)
			}
		}
	}
	for ,  := 0, len()-1;  < ; ,  = +1, -1 {
		[], [] = [], []
	}
	return 
}

func runGraph( *layered.LGraphArena,  layered.LGraphID,  core.ProgressMonitor) error {
	,  := prepareGraphRun(, )
	if  != nil {
		return 
	}
	for  := 0;  < 6; ++ {
		if  := .runSlot(, , true, );  != nil {
			return 
		}
	}
	return nil
}

type graphRun struct {
	graphID       layered.LGraphID
	configuration layered.PipelineConfiguration
	phases        []layered.LayoutProcessor
}

func prepareGraphRun( *layered.LGraphArena,  layered.LGraphID) (*graphRun, error) {
	 := layered.BasePipelineConfiguration(, )
	// GraphConfigurator makes this decision before phase 2 consumes
	// LayerlessNodes; the strict activation threshold is observable.
	if ,  := p3order.GreedySwitchIntermediateForGraph(, );  {
		.Intermediates.AddBefore(layered.PhaseNodePlacement, )
	}
	,  := selectPhases(, , .Phases)
	if  != nil {
		return nil, 
	}
	for ,  := range  {
		if ,  := .(layered.ConfiguredProcessor);  {
			.Intermediates.AddAll(.ProcessorConfiguration(, ))
		}
	}

	return &graphRun{graphID: , configuration: , phases: }, nil
}

func ( *graphRun) (
	 *layered.LGraphArena,
	 int,
	 bool,
	 core.ProgressMonitor,
) error {
	for ,  := range .configuration.Intermediates.Slot() {
		if  := runIntermediate(, .graphID, );  != nil {
			return 
		}
	}
	if  &&  < len(.phases) {
		if  := .phases[].Process(, .graphID);  != nil {
			return 
		}
		.Worked(1)
	}
	return nil
}

// runHierarchy mirrors ElkLayered.hierarchicalLayout around phase 3, the
// hierarchy-aware layer-sweep processor. Every graph is prepared bottom-up,
// paused at the shared sweep, and resumed bottom-up afterwards.
func runHierarchy( *layered.LGraphArena,  layered.LGraphID,  core.ProgressMonitor) error {
	 := collectGraphsBottomUp(, )
	 := make([]*graphRun, 0, len())
	var  *graphRun
	for ,  := range  {
		,  := prepareGraphRun(, )
		if  != nil {
			return 
		}
		 = append(, )
		if  ==  {
			 = 
		}
	}
	if  == nil {
		return fmt.Errorf("layered: root graph %d is missing from its hierarchy", )
	}

	// Layer sweep is the only hierarchy-aware phase in ELK 0.8.1. If the
	// root configuration selects a different crossing minimizer, the Java
	// hierarchy runner simply executes each graph's whole pipeline bottom-up.
	// In particular, it does not reject INTERACTIVE or NONE merely because
	// hierarchy handling is INCLUDE_CHILDREN.
	if ,  := .phases[layered.PhaseNodeOrdering].(*p3order.LayerSweepCrossingMinimizer); ! {
		for ,  := range  {
			for  := 0;  < 6; ++ {
				if  := .runSlot(, , true, );  != nil {
					return 
				}
			}
		}
		return nil
	}

	for ,  := range  {
		for  := 0;  < int(layered.PhaseNodeOrdering); ++ {
			if  := .runSlot(, , true, );  != nil {
				return 
			}
		}
		if  := .runSlot(, int(layered.PhaseNodeOrdering), false, );  != nil {
			return 
		}
	}
	,  := .phases[layered.PhaseNodeOrdering].(*p3order.LayerSweepCrossingMinimizer)
	if ! {
		return fmt.Errorf("layered: hierarchy-aware crossing minimizer is not configured on root graph")
	}
	if  := .ProcessHierarchy(, );  != nil {
		return 
	}
	.Worked(1)

	for ,  := range  {
		for  := int(layered.PhaseNodePlacement);  < 6; ++ {
			if  := .runSlot(, , true, );  != nil {
				return 
			}
		}
	}
	return nil
}

func selectPhases(
	 *layered.LGraphArena,
	 layered.LGraphID,
	 layered.PhaseStrategies,
) ([]layered.LayoutProcessor, error) {
	var  layered.LayoutProcessor
	switch .CycleBreaking {
	case layered.CycleBreakingGreedy:
		 = p1cycles.NewGreedyCycleBreaker()
	case layered.CycleBreakingDepthFirst:
		 = &p1cycles.DepthFirstCycleBreaker{}
	case layered.CycleBreakingInteractive:
		 = &p1cycles.InteractiveCycleBreaker{}
	case layered.CycleBreakingModelOrder:
		 = &p1cycles.ModelOrderCycleBreaker{}
	case layered.CycleBreakingGreedyModelOrder:
		 = p1cycles.NewGreedyModelOrderCycleBreaker()
	case layered.CycleBreakingDFSNodeOrder:
		 = &p1cycles.DFSNodeOrderCycleBreaker{}
	case layered.CycleBreakingSCCNodeType:
		 = &p1cycles.SCCNodeTypeCycleBreaker{}
	default:
		return nil, fmt.Errorf("layered: cycle-breaking strategy %v is not implemented", .CycleBreaking)
	}
	var  layered.LayoutProcessor
	switch .Layering {
	case layered.LayeringNetworkSimplex:
		 = &p2layers.NetworkSimplexLayerer{}
	case layered.LayeringLongestPath:
		 = &p2layers.LongestPathLayerer{}
	case layered.LayeringCoffmanGraham:
		 = &p2layers.CoffmanGrahamLayerer{}
	case layered.LayeringInteractive:
		 = &p2layers.InteractiveLayerer{}
	case layered.LayeringStretchWidth:
		 = &p2layers.StretchWidthLayerer{}
	case layered.LayeringMinWidth:
		 = &p2layers.MinWidthLayerer{}
	default:
		return nil, fmt.Errorf("layered: layering strategy %v is not implemented", .Layering)
	}
	var  layered.LayoutProcessor
	switch .CrossingMinimization {
	case layered.CrossingMinimizationLayerSweep:
		 = &p3order.LayerSweepCrossingMinimizer{}
	case layered.CrossingMinimizationInteractive:
		 = &p3order.InteractiveCrossingMinimizer{}
	case layered.CrossingMinimizationNone:
		 = &p3order.NoCrossingMinimizer{}
	default:
		return nil, fmt.Errorf("layered: crossing-minimization strategy %v is not implemented", .CrossingMinimization)
	}
	,  := selectNodePlacer(.NodePlacement)
	if  != nil {
		return nil, 
	}
	var  layered.LayoutProcessor
	switch .EdgeRouting {
	case layered.EdgeRoutingUndefined, layered.EdgeRoutingOrthogonal:
		// EdgeRouterFactory's default branch is OrthogonalEdgeRouter. Keep the
		// graph property itself undefined because other ELK processors observe
		// that distinction.
		 = &p5edges.OrthogonalEdgeRouter{}
	case layered.EdgeRoutingPolyline:
		 = &p5edges.PolylineEdgeRouter{}
	case layered.EdgeRoutingSplines:
		 = &p5edges.SplineEdgeRouter{}
	default:
		return nil, fmt.Errorf("layered: edge-routing strategy %v is not implemented", .EdgeRouting)
	}
	return []layered.LayoutProcessor{
		,
		,
		,
		,
		,
	}, nil
}

func selectNodePlacer( layered.NodePlacementStrategy) (layered.LayoutProcessor, error) {
	switch  {
	case layered.NodePlacementSimple:
		return &p4nodes.SimpleNodePlacer{}, nil
	case layered.NodePlacementInteractive:
		return &p4nodes.InteractiveNodePlacer{}, nil
	case layered.NodePlacementLinearSegments:
		return &p4nodes.LinearSegmentsNodePlacer{}, nil
	case layered.NodePlacementBrandesKoepf:
		return p4nodes.BrandesKoepfPlacer{}, nil
	case layered.NodePlacementNetworkSimplex:
		return &p4nodes.NetworkSimplexPlacer{}, nil
	default:
		return nil, fmt.Errorf("layered: node-placement strategy %v is not implemented", )
	}
}

func runIntermediate(
	 *layered.LGraphArena,
	 layered.LGraphID,
	 layered.IntermediateProcessorStrategy,
) error {
	switch  {
	case layered.DirectionPreprocessor:
		// ELK 0.8.1's IntermediateProcessorStrategy factory intentionally
		// associates the preprocessor with TO_INPUT_DIRECTION.
		intermediate.TransformGraph(, , intermediate.ToInputDirection)
	case layered.DirectionPostprocessor:
		intermediate.TransformGraph(, , intermediate.ToInternalLTR)
	case layered.EdgeAndLayerConstraintEdgeReverser:
		intermediate.ReverseConstraintEdges(, )
	case layered.InLayerConstraintProcessor:
		intermediate.ProcessInLayerConstraints(, )
	case layered.CommentPreprocessor:
		return intermediate.PreprocessComments(, )
	case layered.InteractiveExternalPortPositioner:
		return intermediate.PositionInteractiveExternalPorts(, )
	case layered.LabelDummyInserter:
		intermediate.InsertLabelDummies(, )
	case layered.LayerConstraintPreprocessor:
		intermediate.ProcessLayerConstraintsBeforeLayering(, )
	case layered.LayerConstraintPostprocessor:
		intermediate.ProcessLayerConstraintsAfterLayering(, )
	case layered.LabelDummySwitcher:
		intermediate.SwitchLabelDummies(, )
	case layered.LabelSideSelector:
		intermediate.SelectLabelSides(, )
	case layered.LabelDummyRemover:
		intermediate.RemoveLabelDummies(, )
	case layered.EndNodePortLabelManagementProcessor:
		intermediate.ManageEndNodePortLabels(, )
	case layered.EndLabelPreprocessor:
		intermediate.PreprocessEndLabels(, )
	case layered.EndLabelSorter:
		intermediate.SortEndLabels(, )
	case layered.EndLabelPostprocessor:
		intermediate.PostprocessEndLabels(, )
	case layered.LongEdgeSplitter:
		intermediate.SplitLongEdges(, )
	case layered.LongEdgeJoiner:
		intermediate.JoinLongEdges(, )
	case layered.PortSideProcessor:
		intermediate.ProcessPortSides(, )
	case layered.PortListSorter:
		return intermediate.SortPortLists(, )
	case layered.OneSidedGreedySwitch, layered.TwoSidedGreedySwitch:
		return p3order.ProcessGreedySwitchIntermediate(, , )
	case layered.HyperedgeDummyMerger:
		return intermediate.MergeHyperedgeDummies(, )
	case layered.LabelAndNodeSizeProcessor:
		intermediate.ProcessLabelAndNodeSizes(, )
	case layered.InnermostNodeMarginCalculator:
		intermediate.CalculateInnermostNodeMargins(, )
	case layered.CommentNodeMarginCalculator:
		intermediate.CalculateCommentNodeMargins(, )
	case layered.SortByInputOrderOfModel:
		return intermediate.SortByInputModel(, )
	case layered.InvertedPortProcessor:
		return intermediate.ProcessInvertedPorts(, )
	case layered.NorthSouthPortPreprocessor:
		intermediate.PreprocessNorthSouthPorts(, )
	case layered.NorthSouthPortPostprocessor:
		intermediate.PostprocessNorthSouthPorts(, )
	case layered.PartitionPreprocessor:
		intermediate.PreprocessPartitions(, )
	case layered.PartitionMidprocessor:
		intermediate.ProcessPartitionsBeforeLayering(, )
	case layered.HighDegreeNodeLayerProcessor:
		intermediate.ProcessHighDegreeNodes(, )
	case layered.NodePromotion:
		intermediate.PromoteNodes(, )
	case layered.PartitionPostprocessor:
		intermediate.PostprocessPartitions(, )
	case layered.SemiInteractiveCrossMinProcessor:
		intermediate.ProcessSemiInteractiveCrossing(, )
	case layered.BreakingPointInserter:
		wrapping.InsertBreakingPoints(, )
	case layered.HierarchicalPortConstraintProcessor:
		return intermediate.ProcessHierarchicalPortConstraints(, )
	case layered.HierarchicalPortDummySizeProcessor:
		return intermediate.SizeHierarchicalPortDummies(, )
	case layered.HierarchicalPortPositionProcessor:
		return intermediate.PositionHierarchicalPorts(, )
	case layered.HierarchicalPortOrthogonalEdgeRouter:
		return intermediate.RouteHierarchicalPorts(, )
	case layered.HierarchicalNodeResizer:
		return intermediate.ResizeHierarchicalNode(, )
	case layered.NodePlacementRepeater:
		,  := basegraph.TryGet(
			&.Graph().Properties,
			layered.NetworkSimplexRecomputeNodePlacement,
		)
		if ! {
			return fmt.Errorf("layered: node-placement repeater has no recomputation strategy")
		}
		,  := selectNodePlacer()
		if  != nil {
			return 
		}
		intermediate.PrepareNodePlacementRepeat(, )
		return .Process(, )
	case layered.LayerSizeAndGraphHeightCalculator:
		intermediate.CalculateLayerSizesAndGraphHeight(, )
	case layered.ReversedEdgeRestorer:
		intermediate.RestoreReversedEdges(, )
	case layered.SelfLoopPreprocessor:
		return intermediate.PreprocessSelfLoops(, )
	case layered.SelfLoopPortRestorer:
		return intermediate.RestoreSelfLoopPorts(, )
	case layered.AlternatingLayerUnzipper:
		unzipping.AlternateLayers(, )
	case layered.BreakingPointProcessor:
		wrapping.ProcessBreakingPoints(, )
	case layered.SingleEdgeGraphWrapper:
		wrapping.WrapSingleEdgeGraph(, )
	case layered.SelfLoopRouter:
		return intermediate.RouteSelfLoops(, )
	case layered.SelfLoopPostprocessor:
		intermediate.PostprocessSelfLoops(, )
	case layered.ConstraintsPostprocessor:
		intermediate.ProcessConstraints(, )
	case layered.CommentPostprocessor:
		return intermediate.PostprocessComments(, )
	case layered.HypernodeProcessor:
		intermediate.ProcessHypernodes(, )
	case layered.BreakingPointRemover:
		wrapping.RemoveBreakingPoints(, )
	case layered.FinalSplineBendpointsCalculator:
		p5edges.FinalizeSplineBendpoints(, )
	case layered.HorizontalCompactor:
		return intermediate.CompactHorizontally(, )
	default:
		return fmt.Errorf("layered: intermediate processor %d is required but not implemented", )
	}
	return nil
}