// Copyright (c) 2008, 2018 Kiel University and others.
// Copyright (c) 2018, 2020 TypeFox GmbH 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 core

import (
	

	
	
)

const DefaultAlgorithmID = "org.eclipse.elk.layered"

// Engine applies registered providers recursively across graph hierarchy.
type Engine struct {
	Options    *OptionRegistry
	Algorithms *AlgorithmRegistry
	Monitor    ProgressMonitor
}

func ( *OptionRegistry,  *AlgorithmRegistry) *Engine {
	if  == nil {
		 = NewOptionRegistry()
	}
	if  == nil {
		 = NewAlgorithmRegistry()
	}
	return &Engine{Options: , Algorithms: , Monitor: NullProgressMonitor}
}

func ( *Engine) ( *graph.Model) error {
	if  == nil || len(.Nodes) == 0 {
		return fmt.Errorf("layout graph must contain a root node")
	}
	if .Monitor == nil {
		.Monitor = NullProgressMonitor
	}
	if  := .resolveAlgorithms();  != nil {
		return 
	}
	,  := .layoutRecursively(, .Root, .Monitor)
	return 
}

func ( *Engine) ( *graph.Model) error {
	 := append([]graph.NodeID{.Root}, .Descendants(.Root)...)
	for ,  := range  {
		 := .Node()
		if graph.Get(&.Properties, NoLayout) {
			continue
		}
		 := len(.Children) > 0 || len(gatherInsideSelfLoops(, )) > 0
		 := graph.Get(&.Properties, Algorithm)
		 := .Algorithms.BySuffix()
		if  == nil &&  == "" &&  {
			 = .Algorithms.BySuffix(DefaultAlgorithmID)
		}
		if  == nil {
			if ! {
				continue
			}
			if  == "" {
				return fmt.Errorf("default layout algorithm %q is not registered", DefaultAlgorithmID)
			}
			return fmt.Errorf("layout algorithm %q not found for %s", , nodePath(, ))
		}
		graph.Set(&.Properties, ResolvedAlgorithm, )
	}
	return nil
}

func ( *Engine) ( *graph.Model,  graph.NodeID,  ProgressMonitor) ([]graph.EdgeID, error) {
	 := .Node()
	 := gatherInsideSelfLoops(, )
	if graph.Get(&.Properties, NoLayout) || len(.Children) == 0 && len() == 0 {
		return nil, nil
	}
	,  := graph.TryGet(&.Properties, ResolvedAlgorithm)
	if ! ||  == nil {
		return nil, fmt.Errorf("resolved algorithm is not set for %s", nodePath(, ))
	}
	.evaluateHierarchyHandling(, )
	 := .Features.Has(FeatureInsideSelfLoops)
	if len(.Children) == 0 && len() > 0 && ! {
		return nil, nil
	}
	 := make([]graph.EdgeID, 0)
	 := graph.Get(&.Properties, HierarchyHandling) == "INCLUDE_CHILDREN" &&
		(.Features.Has(FeatureCompound) || .Features.Has(FeatureClusters))
	 := graph.Get(&.Properties, TopdownLayout)
	 := false
	if  {
		if  {
			return nil, fmt.Errorf("Topdown layout cannot be used together with hierarchy handling.")
		}
		 := append([]graph.NodeID(nil), .Children...)
		for len() > 0 {
			 := [0]
			 = [1:]
			.evaluateHierarchyHandling(, )
			 := .Node()
			,  := graph.TryGet(&.Properties, ResolvedAlgorithm)
			 := graph.Get(&.Properties, HierarchyHandling) == "SEPARATE_CHILDREN"
			 := graph.Has(&.Properties, Algorithm) && (! || .ID != .ID)
			if  ||  {
				,  := .(
					, , .Subtask(float64(len(.Children))))
				if  != nil {
					return nil, 
				}
				 = append(, ...)
				graph.Set(&.Properties, HierarchyHandling, "SEPARATE_CHILDREN")
				applyScale(, )
			} else {
				 = append(, .Children...)
			}
		}
	} else {
		if  {
			if  := .layoutTopdown(, , , );  != nil {
				return nil, 
			}
			 = true
		}
		 := append([]graph.NodeID(nil), .Children...)
		for ,  := range  {
			,  := .(
				, , .Subtask(float64(len(.Node().Children))))
			if  != nil {
				return nil, 
			}
			 = append(, ...)
			applyScale(, )
		}
	}
	if .Canceled() {
		return nil, nil
	}
	for ,  := range  {
		graph.Set(&.Edge().Properties, NoLayout, true)
	}
	if ! {
		if  := .executeAlgorithm(, , , );  != nil {
			return nil, 
		}
	}
	for ,  := range  {
		postProcessInsideSelfLoop(, )
	}
	if  {
		return , nil
	}
	return nil, nil
}

func ( *Engine) (
	 *graph.Model,
	 graph.NodeID,
	 *AlgorithmData,
	 ProgressMonitor,
) error {
	 := .Create()
	if  == nil {
		return fmt.Errorf("layout algorithm %q returned a nil provider", .ID)
	}
	.Begin(.ID, float64(len(.Node().Children)))
	 := .Layout(, , )
	.Done()
	if  != nil {
		return fmt.Errorf("layout algorithm %s: %w", .ID, )
	}
	return nil
}

func gatherInsideSelfLoops( *graph.Model,  graph.NodeID) []graph.EdgeID {
	 := .Node()
	if !graph.Get(&.Properties, InsideSelfLoopsActivate) {
		return nil
	}
	 := make([]graph.EdgeID, 0)
	 := make(map[graph.EdgeID]bool)
	 := func( graph.EdgeID) {
		if [] {
			return
		}
		[] = true
		if graph.Get(&.Edge().Properties, InsideSelfLoopsEdge) &&
			IsSelfLoop(, ) && insideSelfLoopNode(, ) ==  {
			 = append(, )
		}
	}
	for ,  := range .OutgoingEdges {
		()
	}
	for ,  := range .Ports {
		for ,  := range .Port().OutgoingEdges {
			()
		}
	}
	return 
}

func insideSelfLoopNode( *graph.Model,  graph.EdgeID) graph.NodeID {
	 := .Edge()
	if len(.Sources) > 0 {
		return .ShapeNode(.Sources[0])
	}
	return 0
}

func postProcessInsideSelfLoop( *graph.Model,  graph.EdgeID) {
	 := .Edge()
	if len(.Sources) == 0 || len(.Sections) == 0 {
		return
	}
	 := .Node(.ShapeNode(.Sources[0])).Shape.Position()
	 := .Section(.Sections[0])
	.Start = .Start.Add()
	.End = .End.Add()
	.BendPoints.Offset()
	if ,  := graph.TryGet(&.Properties, JunctionPoints);  {
		.Offset()
		graph.Set(&.Properties, JunctionPoints, )
	}
}

func ( *Engine) ( *graph.Model,  graph.NodeID) {
	 := .Node()
	if graph.Get(&.Properties, HierarchyHandling) != "INHERIT" {
		return
	}
	 := "SEPARATE_CHILDREN"
	if .Parent != nil {
		 = graph.Get(&.Node(*.Parent).Properties, HierarchyHandling)
	}
	graph.Set(&.Properties, HierarchyHandling, )
}

func applyScale( *graph.Model,  graph.NodeID) {
	 := graph.Get(&.Node().Properties, ScaleFactor)
	if  == 1 {
		return
	}
	 := .Node()
	.Shape.Width *= 
	.Shape.Height *= 
	 := func( *graph.Shape,  *graph.PropertyMap) {
		.X *= 
		.Y *= 
		.Width *= 
		.Height *= 
		if ,  := graph.TryGet(, PortAnchor);  {
			.X *= 
			.Y *= 
			graph.Set(, PortAnchor, )
		}
	}
	for ,  := range .Labels {
		 := .Label()
		(&.Shape, &.Properties)
	}
	for ,  := range .Ports {
		 := .Port()
		(&.Shape, &.Properties)
		for ,  := range .Labels {
			 := .Label()
			(&.Shape, &.Properties)
		}
	}
}

// TranslateSection moves every point in a section by offset.
func ( *graph.Model,  graph.SectionID,  geometry.Point) {
	 := .Section()
	.Start = .Start.Add()
	.End = .End.Add()
	.BendPoints.Offset()
}

func ( *graph.Model,  graph.EdgeID) bool {
	 := .Edge()
	if len(.Sources)+len(.Targets) == 0 {
		return false
	}
	 := graph.NodeID(0)
	 := false
	for ,  := range append(append([]graph.ShapeID(nil), .Sources...), .Targets...) {
		 := .ShapeNode()
		if ! {
			,  = , true
		} else if  !=  {
			return false
		}
	}
	return true
}

func nodePath( *graph.Model,  graph.NodeID) string {
	 := make([]string, 0)
	for  := &;  != nil;  = .Node(*).Parent {
		 := .Node(*)
		 := .Identifier
		if !.IdentifierPresent {
			 = fmt.Sprintf("#%d", *)
		}
		 = append(, )
	}
	for ,  := 0, len()-1;  < ; ,  = +1, -1 {
		[], [] = [], []
	}
	 := ""
	for ,  := range  {
		if  > 0 {
			 += " > "
		}
		 += 
	}
	return 
}