// Copyright (c) 2013, 2015 Kiel University and others.
// Copyright (c) 2013, 2020 Kiel University and others.
// Copyright (c) 2015, 2020 Kiel University and others.
// Copyright (c) 2017 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
// http://www.eclipse.org/legal/epl-2.0.
//
// SPDX-License-Identifier: EPL-2.0

package mrtree

import (
	
	
	

	
	
	
	
)

type Provider struct{}

// Register adds the provider generated from Tree.melk and its exact feature
// declaration to the algorithm registry.
func ( *core.AlgorithmRegistry) error {
	return .Register(core.AlgorithmData{
		ID:       AlgorithmID,
		Features: core.FeatureDisconnected,
		Create:   func() core.LayoutProvider { return &Provider{} },
		KnownOptions: []string{
			"org.eclipse.elk.padding",
			"org.eclipse.elk.spacing.nodeNode",
			"org.eclipse.elk.spacing.edgeNode",
			"org.eclipse.elk.aspectRatio",
			"org.eclipse.elk.priority",
			"org.eclipse.elk.separateConnectedComponents",
			"org.eclipse.elk.debugMode",
			"org.eclipse.elk.direction",
			"org.eclipse.elk.interactive",
			"org.eclipse.elk.interactiveLayout",
			"org.eclipse.elk.nodeSize.constraints",
			"org.eclipse.elk.nodeSize.fixedGraphSize",
			"org.eclipse.elk.nodeSize.minimum",
			"org.eclipse.elk.nodeSize.options",
			"org.eclipse.elk.nodeLabels.placement",
			"org.eclipse.elk.omitNodeMicroLayout",
			"org.eclipse.elk.portLabels.placement",
			Weighting.ID,
			SearchOrder.ID,
			core.TopdownLayout.ID,
			core.TopdownScaleFactor.ID,
			core.TopdownHierarchicalNodeWidth.ID,
			core.TopdownHierarchicalNodeAspectRatio.ID,
			core.TopdownNodeType.ID,
			PositionConstraint.ID,
			EdgeRoutingMode.ID,
			TreeLevel.ID,
			Compaction.ID,
			EdgeEndTextureLength.ID,
		},
	})
}

func (*Provider) ( *graph.Model,  graph.NodeID,  core.ProgressMonitor) error {
	if !graph.Get(&.Node().Properties, OmitNodeMicroLayout) {
		nodespacing.CalculateLabelAndNodeSizes(, , nil)
		nodespacing.NewNodeMarginCalculator().Process(, )
	}
	 := importGraph(, )
	 := splitComponents()
	for ,  := range  {
		layoutComponent(, .Subtask(1/float64(max(1, len()))))
	}
	 := packComponents()
	return applyLayout(, , )
}

func importGraph( *graph.Model,  graph.NodeID) *tGraph {
	 := .Node()
	 := &tGraph{
		padding:              graph.Get(&.Properties, Padding),
		spacing:              graph.Get(&.Properties, SpacingNodeNode),
		spacingEdgeNode:      graph.Get(&.Properties, SpacingEdgeNode),
		edgeEndTextureLength: graph.Get(&.Properties, EdgeEndTextureLength),
		aspectRatio:          graph.Get(&.Properties, AspectRatio),
		separate:             graph.Get(&.Properties, SeparateConnectedComponents),
		searchOrder:          graph.Get(&.Properties, SearchOrder),
		weighting:            graph.Get(&.Properties, Weighting),
		direction:            graph.Get(&.Properties, Direction),
		edgeRoutingMode:      graph.Get(&.Properties, EdgeRoutingMode),
		compaction:           graph.Get(&.Properties, Compaction),
		fixedGraphSize:       graph.Get(&.Properties, NodeSizeFixedGraphSize),
	}
	if .direction == "UNDEFINED" {
		.direction = "DOWN"
	}
	 := make(map[graph.NodeID]*tNode, len(.Children))
	for ,  := range .Children {
		 := 
		 := .Node()
		 := &tNode{
			id:       ,
			origin:   &,
			position: geometry.Point{X: .Shape.X + .Shape.Width/2, Y: .Shape.Y + .Shape.Height/2},
			size:     geometry.Point{X: math.Max(.Shape.Width, 1), Y: math.Max(.Shape.Height, 1)},
			props:    .Properties.Clone(),
		}
		.nodes = append(.nodes, )
		[] = 
	}

	// ElkGraphUtil.allOutgoingEdges visits each child in model order. Scanning
	// the containing graph's insertion-ordered edge list gives the same order
	// for node- and port-connected edges without depending on Go maps.
	for ,  := range .Children {
		for ,  := range .ContainedEdges {
			 := .Edge()
			if len(.Sources) == 0 || len(.Targets) == 0 {
				continue
			}
			 := .ShapeNode(.Sources[0])
			 := .ShapeNode(.Targets[0])
			if  !=  ||  ==  {
				continue
			}
			 := []
			 := []
			if  == nil ||  == nil {
				continue
			}
			 := 
			 := &tEdge{origin: &, source: , target: }
			.outgoing = append(.outgoing, )
			.incoming = append(.incoming, )
			.edges = append(.edges, )
		}
	}
	return 
}

func splitComponents( *tGraph) []*tGraph {
	if !.separate {
		return []*tGraph{}
	}
	 := make([][]*tEdge, len(.nodes))
	for ,  := range .edges {
		[.source.id] = append([.source.id], )
		[.target.id] = append([.target.id], )
	}
	 := make([]bool, len(.nodes))
	 := make([]*tGraph, 0)
	var  func(*tNode, *tGraph)
	 = func( *tNode,  *tGraph) {
		if [.id] {
			return
		}
		[.id] = true
		.nodes = append(.nodes, )
		for ,  := range [.id] {
			if .source !=  {
				(.source, )
			}
			if .target !=  {
				(.target, )
			}
			if !containsEdge(.edges, ) {
				.edges = append(.edges, )
			}
		}
	}
	for ,  := range .nodes {
		if [.id] {
			continue
		}
		 := .settingsClone()
		(, )
		 = append(, )
	}
	if len() > 1 {
		for ,  := range  {
			for ,  := range .nodes {
				.id = 
			}
		}
	}
	return 
}

func ( *tGraph) () *tGraph {
	return &tGraph{
		padding:              .padding,
		spacing:              .spacing,
		spacingEdgeNode:      .spacingEdgeNode,
		edgeEndTextureLength: .edgeEndTextureLength,
		aspectRatio:          .aspectRatio,
		separate:             .separate,
		searchOrder:          .searchOrder,
		weighting:            .weighting,
		direction:            .direction,
		edgeRoutingMode:      .edgeRoutingMode,
		compaction:           .compaction,
		fixedGraphSize:       .fixedGraphSize,
	}
}

func containsEdge( []*tEdge,  *tEdge) bool {
	for ,  := range  {
		if  ==  {
			return true
		}
	}
	return false
}

func layoutComponent( *tGraph,  core.ProgressMonitor) {
	.Begin("Tree layout", 1)
	treeify()
	 := ensureRoot()
	computeFan()
	computeTreeLevels()
	orderNodes(, .weighting)
	computeLevelHeights(, .direction)
	computeNeighbors()
	placeNodes(, )
	applyDirectionAndNodePositions()
	computeLevelCoordinates()
	compactGraph()
	computeGraphBounds()
	routeEdges()
	.Done()
}

func treeify( *tGraph) {
	for ,  := range .nodes {
		.id = 
	}
	 := make([]int, len(.nodes))
	 := make([]*tEdge, 0)
	var  func(*tNode)
	 = func( *tNode) {
		[.id] = 1
		for ,  := range append([]*tEdge(nil), .outgoing...) {
			 := .target
			switch [.id] {
			case 1:
				 = append(, )
			case 2:
				[.id] = 1
			default:
				()
			}
		}
	}
	var  func(*tNode)
	 = func( *tNode) {
		 := []*tNode{}
		for len() > 0 {
			 := [0]
			 = [1:]
			[.id] = 1
			for ,  := range append([]*tEdge(nil), .outgoing...) {
				 := .target
				switch [.id] {
				case 1:
					 = append(, )
				case 2:
					[.id] = 1
				default:
					 = append(, )
				}
			}
		}
	}
	for ,  := range .nodes {
		if [.id] != 0 {
			continue
		}
		if .searchOrder == "BFS" {
			()
		} else {
			()
		}
		[.id] = 2
	}
	for ,  := range  {
		.source.outgoing = removeEdge(.source.outgoing, )
		.target.incoming = removeEdge(.target.incoming, )
	}
}

func removeEdge( []*tEdge,  *tEdge) []*tEdge {
	for ,  := range  {
		if  ==  {
			return append([:], [+1:]...)
		}
	}
	return 
}

func ensureRoot( *tGraph) *tNode {
	 := make([]*tNode, 0)
	for ,  := range .nodes {
		.root = false
		if len(.incoming) == 0 {
			.root = true
			 = append(, )
		}
	}
	switch len() {
	case 0:
		 := &tNode{id: 0, root: true, dummy: true}
		.nodes = append(.nodes, )
		return 
	case 1:
		return [0]
	default:
		 := &tNode{id: 0, root: true, dummy: true}
		for ,  := range  {
			.root = false
			.addDummyChild(, )
		}
		.nodes = append(.nodes, )
		return 
	}
}

// computeFan is the tree-specialized form of FanProcessor's string-prefix
// accounting: fan is the maximum number of descendants on any one deeper
// level and descendants includes the node itself.
func computeFan( *tNode) []int {
	 := []int{1}
	for ,  := range .children() {
		 := ()
		for ,  := range  {
			for len() <= +1 {
				 = append(, 0)
			}
			[+1] += 
		}
	}
	.descendants = 0
	for ,  := range  {
		.descendants += 
	}
	.fan = 0
	for ,  := range [1:] {
		if  > .fan {
			.fan = 
		}
	}
	return 
}

func computeTreeLevels( *tNode) {
	 := []*tNode{}
	for  := 0; len() > 0; ++ {
		 := make([]*tNode, 0)
		for ,  := range  {
			.treeLevel = 
			 = append(, .children()...)
		}
		 = 
	}
}

func orderNodes( *tNode,  string) {
	if  == "MODEL_ORDER" {
		return
	}
	if  == "CONSTRAINT" {
		orderNodesByConstraint([]*tNode{})
		return
	}
	 :=  == "DESCENDANTS"
	var  func([]*tNode)
	 = func( []*tNode) {
		if len() == 0 {
			return
		}
		 := func( *tNode) int {
			if  {
				return .descendants
			}
			return .fan
		}
		sort.SliceStable(, func(,  int) bool { return ([]) < ([]) })
		 := len()
		for  > 0 && ([-1]) == 0 {
			--
		}
		 := append([]*tNode(nil), [:]...)
		 := append([]*tNode(nil), [:]...)
		 := 0
		if len() == 0 {
			for ,  := range  {
				.positionIndex = 
				++
			}
			return
		}
		for ,  := range  {
			.positionIndex = 
			++
			 := .children()
			()
			sort.SliceStable(, func(,  int) bool { return [].positionIndex > [].positionIndex })
			 := make([]*tEdge, 0, len(.outgoing))
			for ,  := range  {
				for ,  := range .outgoing {
					if .target ==  {
						 = append(, )
					}
				}
			}
			.outgoing = 

			 := len(.outgoing)
			for  := len() - 1;  >= 0 &&  > 0; -- {
				if ([]) != 0 {
					break
				}
				[].positionIndex = 
				++
				--
				 = append([:], [+1:]...)
			}
		}
	}
	([]*tNode{})
}

func orderNodesByConstraint( []*tNode) {
	if len() == 0 {
		return
	}
	 := make([]*tNode, 0, len())
	 := make([]*tNode, 0, len())
	 := make([]*tNode, 0, len())
	for ,  := range  {
		 := graph.Get(&.props, PositionConstraint)
		switch {
		case  < 0:
			 = append(, )
		case  < len():
			 = append(, )
		default:
			 = append(, )
		}
	}

	 := make([]*tNode, len())
	for  := 0;  < len(); {
		 := []
		 := graph.Get(&.props, PositionConstraint)
		// This intentionally uses the shrinking inBounds size. It mirrors the
		// 0.12 Java implementation, including that implementation detail.
		if  >= 0 &&  < len() && [] == nil {
			[] = 
			 = append([:], [+1:]...)
			continue
		}
		++
	}
	for len() > 0 {
		 := [0]
		 = [1:]
		 := graph.Get(&.props, PositionConstraint)
		for  := 0; ; ++ {
			 :=  + 
			if  >= 0 &&  < len() && [] == nil {
				[] = 
				break
			}
			 :=  - 
			if  >= 0 &&  < len() && [] == nil {
				[] = 
				break
			}
		}
	}
	sort.SliceStable(, func(,  int) bool {
		return graph.Get(&[].props, PositionConstraint) > graph.Get(&[].props, PositionConstraint)
	})
	for  := len() - 1;  >= 0 && len() > 0; -- {
		if [] == nil {
			[] = [0]
			 = [1:]
		}
	}
	for  := range  {
		if [] == nil && len() > 0 {
			[] = [0]
			 = [1:]
		}
		[].positionIndex = 
	}

	for ,  := range  {
		if .fan == 0 {
			continue
		}
		 := .children()
		()
		sort.SliceStable(, func(,  int) bool {
			return [].positionIndex < [].positionIndex
		})
		 := make([]*tEdge, 0, len(.outgoing))
		for ,  := range  {
			for ,  := range .outgoing {
				if .target ==  {
					 = append(, )
				}
			}
		}
		.outgoing = 
	}
}

func computeLevelHeights( *tNode,  string) {
	 := []*tNode{}
	for len() > 0 {
		 := 0.0
		 := make([]*tNode, 0)
		for ,  := range  {
			 := .size.Y
			if  == "LEFT" ||  == "RIGHT" {
				 = .size.X
			}
			if  >  {
				 = 
			}
			 = append(, .children()...)
		}
		for ,  := range  {
			.levelHeight = 
		}
		 = 
	}
}

func computeNeighbors( *tNode) {
	for ,  := range descendantsIncluding() {
		.leftNeighbor, .rightNeighbor = nil, nil
		.leftSibling, .rightSibling = nil, nil
	}
	 := .children()
	for len() > 0 {
		var  *tNode
		 := make([]*tNode, 0)
		for ,  := range  {
			 = append(, .children()...)
			if  != nil {
				.rightNeighbor = 
				.leftNeighbor = 
				if .parent() == .parent() {
					.rightSibling = 
					.leftSibling = 
				}
			}
			 = 
		}
		 = 
	}
}

func descendantsIncluding( *tNode) []*tNode {
	 := []*tNode{}
	for  := 0;  < len(); ++ {
		 = append(, [].children()...)
	}
	return 
}

func placeNodes( *tGraph,  *tNode) {
	 := .spacing
	var  func(*tNode, int)
	var  func([]*tNode, int) *tNode
	 = func( []*tNode,  int) *tNode {
		if len() == 0 {
			return nil
		}
		if  > 1 {
			 := make([]*tNode, 0)
			for ,  := range  {
				 = append(, .children()...)
			}
			return (, -1)
		}
		if  < 0 {
			 := make([]*tNode, 0)
			for ,  := range  {
				 = append(, .children()...)
			}
			if len() > 0 {
				return (, )
			}
		}
		return [0]
	}
	 := func(,  *tNode) float64 {
		 := 0.0
		if  != nil {
			if .direction == "LEFT" || .direction == "RIGHT" {
				 += .size.Y / 2
			} else {
				 += .size.X / 2
			}
		}
		if  != nil {
			if .direction == "LEFT" || .direction == "RIGHT" {
				 += .size.Y / 2
			} else {
				 += .size.X / 2
			}
		}
		return 
	}
	var  func(*tNode, int)
	 = func( *tNode,  int) {
		 := .children()
		var  *tNode
		if len() > 0 {
			 = [0]
		}
		var  *tNode
		if  != nil {
			 = .leftNeighbor
		}
		 := 1
		for  != nil &&  != nil {
			,  := 0.0, 0.0
			,  := , 
			for  := 0;  < ; ++ {
				 = .parent()
				 = .parent()
				if  == nil ||  == nil {
					return
				}
				 += .modifier
				 += .modifier
			}
			 := .prelim +  +  + (, ) - .prelim - 
			if  > 0 {
				 := 
				 := 0
				for  != nil &&  !=  {
					++
					 = .leftSibling
				}
				if  == nil {
					return
				}
				 :=  / float64()
				for  = ;  != ;  = .leftSibling {
					.prelim += 
					.modifier += 
					 -= 
				}
			}
			++
			if .leaf() {
				 = (.children(), )
			} else {
				 = .children()[0]
			}
			if  != nil {
				 = .leftNeighbor
			} else {
				 = nil
			}
		}
	}
	 = func( *tNode,  int) {
		.modifier = 0
		 := .leftSibling
		if .leaf() {
			if  != nil {
				.prelim = .prelim +  + (, )
			} else {
				.prelim = 0
			}
			return
		}
		 := .children()
		for ,  := range  {
			(, +1)
		}
		 := ([len()-1].prelim + [0].prelim) / 2
		if  != nil {
			.prelim = .prelim +  + (, )
			.modifier = .prelim - 
			(, )
		} else {
			.prelim = 
		}
	}
	(, 0)
	var  func(*tNode, float64, float64)
	 = func( *tNode, ,  float64) {
		if  == nil {
			return
		}
		 := .prelim + 
		 :=  + .levelHeight/2
		.xCoordinate = javaRound()
		.yCoordinate = javaRound()
		if !.leaf() {
			(.children()[0], +.levelHeight+, +.modifier)
		}
		if .rightSibling != nil {
			(.rightSibling, , )
		}
	}
	(, -.levelHeight/2, 0)
	for ,  := range .nodes {
		.position = geometry.Point{X: float64(.xCoordinate), Y: float64(.yCoordinate)}
	}
}

func javaRound( float64) int { return int(math.Floor( + .5)) }

func applyDirectionAndNodePositions( *tGraph) {
	for ,  := range .nodes {
		,  := .xCoordinate, .yCoordinate
		switch .direction {
		case "UP":
			 = -
		case "RIGHT":
			,  = , 
		case "LEFT":
			,  = -, 
		}
		.xCoordinate, .yCoordinate = , 
		.position = geometry.Point{
			X: float64() - .size.X/2,
			Y: float64() - .size.Y/2,
		}
	}
}

func computeGraphBounds( *tGraph) {
	if len(.nodes) == 0 {
		.graphMin, .graphMax = geometry.Point{}, geometry.Point{}
		return
	}
	.graphMin = geometry.Point{X: math.Inf(1), Y: math.Inf(1)}
	.graphMax = geometry.Point{X: math.Inf(-1), Y: math.Inf(-1)}
	for ,  := range .nodes {
		.graphMin.X = math.Min(.graphMin.X, .position.X)
		.graphMin.Y = math.Min(.graphMin.Y, .position.Y)
		.graphMax.X = math.Max(.graphMax.X, .position.X+.size.X)
		.graphMax.Y = math.Max(.graphMax.Y, .position.Y+.size.Y)
	}
}

func computeLevelCoordinates( *tGraph) {
	type  struct{ ,  float64 }
	 := make(map[int])
	for ,  := range .nodes {
		,  := [.treeLevel]
		if ! {
			 = {: math.Inf(1), : math.Inf(-1)}
		}
		if .direction == "LEFT" || .direction == "RIGHT" {
			. = math.Min(., .position.X)
			. = math.Max(., .position.X+.size.X)
		} else {
			. = math.Min(., .position.Y)
			. = math.Max(., .position.Y+.size.Y)
		}
		[.treeLevel] = 
	}
	for ,  := range .nodes {
		 := [.treeLevel]
		.levelMin, .levelMax = ., .
	}
}

func compactGraph( *tGraph) {
	if !.compaction || len(.nodes) == 0 {
		return
	}
	type  struct{ ,  float64 }
	 := make([], 0)
	for ,  := range .nodes {
		for .treeLevel >= len() {
			 = append(, {: math.Inf(1), : math.Inf(-1)})
		}
		 := [.treeLevel]
		if .direction == "LEFT" || .direction == "RIGHT" {
			. = math.Min(., .position.X)
			. = math.Max(., .position.X+.size.X)
		} else {
			. = math.Min(., .position.Y)
			. = math.Max(., .position.Y+.size.Y)
		}
		[.treeLevel] = 
	}

	computeCompactionConstraints(, .spacing/4)
	 := append([]*tNode(nil), .nodes...)
	sort.SliceStable(, func(,  int) bool {
		return directionProjection(.direction, [].position) < directionProjection(.direction, [].position)
	})
	for ,  := range  {
		if .root {
			continue
		}
		 := lowestDependentNode(, .direction)
		 := lowestParent(, )
		,  := 0.0, 0.0
		if  != nil {
			switch .direction {
			case "LEFT":
				 = .position.X - .spacing - .size.X
				if .position.X-.spacing-.size.X <  {
					 = .position.X - .spacing - .size.X
				}
				 =  + .size.X
			case "RIGHT":
				 = .position.X + .size.X + .spacing
				if .position.X-.spacing-.size.X <  {
					 = .position.X + .size.X + .spacing
				}
				 =  + .size.X
			case "UP":
				 = .position.Y - .spacing - .size.Y
				if .position.Y-.spacing-.size.Y <  {
					 = .position.Y - .spacing - .size.Y
				}
				 =  + .size.Y
			default:
				 = .position.Y + .size.Y + .spacing
				if .position.Y+.spacing >  {
					 = .position.Y + .size.Y + .spacing
				}
				 =  + .size.Y
			}
		} else if  != nil {
			switch .direction {
			case "LEFT":
				 = .position.X - .spacing - .size.X
				 =  + .size.X
			case "RIGHT":
				 = .position.X + .size.X + .spacing
				 =  + .size.X
			case "UP":
				 = .position.Y - .spacing - .size.Y
				 =  + .size.Y
			default:
				 = .position.Y + .size.Y + .spacing
				 =  + .size.Y
			}
		}

		if .edgeRoutingMode != "AVOID_OVERLAP" {
			setDirectionalPosition(, .direction, )
			continue
		}
		 := -1
		for ,  := range  {
			if . <=  && . >=  {
				 = 
				break
			}
		}
		if  < 0 {
			for  := 1;  < len(); ++ {
				if .direction == "LEFT" || .direction == "UP" {
					if []. <=  {
						 = 
						break
					}
				} else if []. >=  {
					 = 
					break
				}
			}
		}
		if  >= 0 {
			setDirectionalPosition(, .direction, [].)
			if  > 0 &&  != .treeLevel {
				.compactLevelAscension = true
				.treeLevel = 
			}
		}
	}
}

func computeCompactionConstraints( *tGraph,  float64) {
	for ,  := range .nodes {
		.compactConstraints = nil
	}
	type  struct {
		  *tNode
		 geometry.Point
		 bool
	}
	 := make([], 0, len(.nodes)*2)
	for ,  := range .nodes {
		if .dummy {
			continue
		}
		 = append(, {: , : geometry.Point{X: .position.X - , Y: .position.Y - }, : true})
	}
	for ,  := range .nodes {
		if .dummy {
			continue
		}
		 = append(, {: , : geometry.Point{X: .position.X + .size.X + , Y: .position.Y + .size.Y + }})
	}
	sort.SliceStable(, func(,  int) bool {
		return perpendicularProjection(.direction, [].) < perpendicularProjection(.direction, [].)
	})
	 := make([]*tNode, 0)
	 := make(map[*tNode]*tNode)
	for ,  := range  {
		 := .
		if . {
			 = compactionSetInsert(, , .direction)
			if  := compactionSetLeft(, , .direction);  != nil {
				[] = 
			}
			if  := compactionSetRight(, , .direction);  != nil {
				[] = 
			}
			continue
		}
		if  := compactionSetLeft(, , .direction);  != nil &&  == [] {
			.compactConstraints = append(.compactConstraints, )
		}
		if  := compactionSetRight(, , .direction);  != nil && [] ==  {
			.compactConstraints = append(.compactConstraints, )
		}
		 = compactionSetRemove(, , .direction)
	}
}

func directionProjection( string,  geometry.Point) float64 {
	switch  {
	case "LEFT":
		return -.X
	case "RIGHT":
		return .X
	case "UP":
		return -.Y
	default:
		return .Y
	}
}

func perpendicularProjection( string,  geometry.Point) float64 {
	if  == "LEFT" ||  == "RIGHT" {
		return .Y
	}
	return .X
}

func compactionSetInsert( []*tNode,  *tNode,  string) []*tNode {
	 := directionProjection(, .position)
	 := sort.Search(len(), func( int) bool {
		return directionProjection(, [].position) >= 
	})
	if  < len() && directionProjection(, [].position) ==  {
		return 
	}
	 = append(, nil)
	copy([+1:], [:])
	[] = 
	return 
}

func compactionSetLeft( []*tNode,  *tNode,  string) *tNode {
	 := directionProjection(, .position)
	 := sort.Search(len(), func( int) bool {
		return directionProjection(, [].position) >= 
	})
	if  == 0 {
		return nil
	}
	return [-1]
}

func compactionSetRight( []*tNode,  *tNode,  string) *tNode {
	 := directionProjection(, .position)
	 := sort.Search(len(), func( int) bool {
		return directionProjection(, [].position) >= 
	})
	if +1 >= len() {
		return nil
	}
	return [+1]
}

func compactionSetRemove( []*tNode,  *tNode,  string) []*tNode {
	 := directionProjection(, .position)
	 := sort.Search(len(), func( int) bool {
		return directionProjection(, [].position) >= 
	})
	if  < len() && directionProjection(, [].position) ==  {
		return append([:], [+1:]...)
	}
	return 
}

func lowestDependentNode( *tNode,  string) *tNode {
	if len(.compactConstraints) == 0 {
		return nil
	}
	 := .compactConstraints[0]
	for ,  := range .compactConstraints[1:] {
		switch  {
		case "LEFT":
			if .position.X < .position.X {
				 = 
			}
		case "RIGHT":
			if .position.X+.size.X > .position.X+.size.X {
				 = 
			}
		case "UP":
			if .position.Y < .position.Y {
				 = 
			}
		default:
			if .position.Y+.size.Y > .position.Y+.size.Y {
				 = 
			}
		}
	}
	return 
}

func lowestParent( *tNode,  *tGraph) *tNode {
	 := make(map[*tNode]bool)
	for ,  := range .edges {
		if .target ==  {
			[.source] = true
		}
	}
	var  *tNode
	 := math.Inf(-1)
	for ,  := range .nodes {
		if ![] {
			continue
		}
		 := geometry.Point{X: .position.X + .size.X/2, Y: .position.Y + .size.Y/2}
		 := directionProjection(.direction, )
		if  == nil ||  >  {
			,  = , 
		}
	}
	return 
}

func setDirectionalPosition( *tNode,  string,  float64) {
	if  == "LEFT" ||  == "RIGHT" {
		.position.X = 
	} else {
		.position.Y = 
	}
}

func routeEdges( *tGraph) {
	for ,  := range .edges {
		.bendPoints = nil
	}
	switch .edgeRoutingMode {
	case "NONE":
		return
	case "MIDDLE_TO_MIDDLE":
		for ,  := range .edges {
			middleToMiddleEdgeRoute()
		}
	default:
		avoidOverlapStartPoints()
		avoidOverlapSpecialEdges()
		avoidOverlapEndPoints()
		for ,  := range .edges {
			if len(.bendPoints) < 2 {
				middleToMiddleEdgeRoute()
			}
		}
	}
}

type multiLevelGapEntry struct {
	edge          *tEdge
	first, second int
}

type multiLevelGap struct {
	neighborOne, neighborTwo *tNode
	entries                  []multiLevelGapEntry
	onFirstSide, onLastSide  bool
}

func ( *multiLevelGap) ( multiLevelGapEntry,  *tGraph) {
	.entries = append(.entries, )
	if len(.entries) > 1 {
		sort.SliceStable(.entries, func(,  int) bool {
			 := .entries[].edge.target.position
			 := .entries[].edge.target.position
			if .direction == "LEFT" || .direction == "RIGHT" {
				return .Y < .Y
			}
			return .X < .X
		})
	}
	.update()
}

func ( *multiLevelGap) ( *tGraph) {
	 := len(.entries)
	for ,  := range .entries {
		 := float64(+1) / float64(+1)
		var ,  geometry.Point
		switch {
		case .neighborOne == nil && .neighborTwo == nil:
			return
		case .neighborOne != nil && .neighborTwo == nil:
			.onLastSide = true
			 := .neighborOne
			switch .direction {
			case "LEFT":
				 := .position.Y + .size.Y + .spacingEdgeNode*float64(+1)
				 = geometry.Point{X: .levelMax + .spacingEdgeNode, Y: }
				 = geometry.Point{X: .levelMin - .spacingEdgeNode, Y: }
			case "RIGHT":
				 := .position.Y + .size.Y + .spacingEdgeNode*float64(+1)
				 = geometry.Point{X: .levelMin - .spacingEdgeNode, Y: }
				 = geometry.Point{X: .levelMax + .spacingEdgeNode, Y: }
			case "UP":
				 := .position.X + .size.X + .spacingEdgeNode*float64(+1)
				 = geometry.Point{X: , Y: .levelMax + .spacingEdgeNode}
				 = geometry.Point{X: , Y: .levelMin - .spacingEdgeNode}
			default:
				 := .position.X + .size.X + .spacingEdgeNode*float64(+1)
				 = geometry.Point{X: , Y: .levelMin - .spacingEdgeNode}
				 = geometry.Point{X: , Y: .levelMax + .spacingEdgeNode}
			}
		case .neighborOne != nil && .neighborTwo != nil:
			,  := .neighborOne, .neighborTwo
			if .direction == "LEFT" || .direction == "RIGHT" {
				 := .position.Y* + (.position.Y+.size.Y)*(1-)
				if .direction == "LEFT" {
					 = geometry.Point{X: .levelMax + .spacingEdgeNode, Y: }
					 = geometry.Point{X: .levelMin - .spacingEdgeNode, Y: }
				} else {
					 = geometry.Point{X: .levelMin - .spacingEdgeNode, Y: }
					 = geometry.Point{X: .levelMax + .spacingEdgeNode, Y: }
				}
			} else {
				 := .position.X* + (.position.X+.size.X)*(1-)
				if .direction == "UP" {
					 = geometry.Point{X: , Y: .levelMax + .spacingEdgeNode}
					 = geometry.Point{X: , Y: .levelMin - .spacingEdgeNode}
				} else {
					 = geometry.Point{X: , Y: .levelMin - .spacingEdgeNode}
					 = geometry.Point{X: , Y: .levelMax + .spacingEdgeNode}
				}
			}
		default:
			.onFirstSide = true
			 := .neighborTwo
			switch .direction {
			case "LEFT":
				 := .position.Y - .spacingEdgeNode*float64(+1)
				 = geometry.Point{X: .levelMax + .spacingEdgeNode, Y: }
				 = geometry.Point{X: .levelMin - .spacingEdgeNode, Y: }
			case "RIGHT":
				 := .position.Y - .spacingEdgeNode*float64(+1)
				 = geometry.Point{X: .levelMin - .spacingEdgeNode, Y: }
				 = geometry.Point{X: .levelMax + .spacingEdgeNode, Y: }
			case "UP":
				 := .position.X - .spacingEdgeNode*float64(+1)
				 = geometry.Point{X: , Y: .levelMax + .spacingEdgeNode}
				 = geometry.Point{X: , Y: .levelMin - .spacingEdgeNode}
			default:
				 := .position.X - .spacingEdgeNode*float64(+1)
				 = geometry.Point{X: , Y: .levelMin - .spacingEdgeNode}
				 = geometry.Point{X: , Y: .levelMax + .spacingEdgeNode}
			}
		}
		.edge.bendPoints[.first] = 
		.edge.bendPoints[.second] = 
	}
}

func avoidOverlapSpecialEdges( *tGraph) {
	 := 0
	for ,  := range .nodes {
		 = max(, .treeLevel)
	}
	 := make([]int, +1)
	 := make([]int, +1)
	 := make(map[[2]int]*multiLevelGap)
	,  := 0, 0

	for ,  := range .edges {
		,  := .source.treeLevel, .target.treeLevel
		 :=  - 
		switch {
		case  > 1:
			for  :=  + 1;  < ; ++ {
				 := make([]*tNode, 0)
				for ,  := range .nodes {
					if .treeLevel ==  {
						 = append(, )
					}
				}
				 := .direction == "LEFT" || .direction == "RIGHT"
				sort.SliceStable(, func(,  int) bool {
					if  {
						return [].position.Y < [].position.Y
					}
					return [].position.X < [].position.X
				})
				 := float64(-) / float64(-)
				 := 0
				for ;  < len(); ++ {
					 := [].position.X
					 := .source.position.X*(1-) + .target.position.X*
					if  {
						 = [].position.Y
						 = .source.position.Y*(1-) + .target.position.Y*
					}
					if  >  {
						break
					}
				}
				if shouldSkipMultiLevelGap(, , , ) {
					continue
				}
				 := len(.bendPoints)
				.bendPoints = append(.bendPoints, geometry.Point{}, geometry.Point{})
				 := [2]int{, }
				 := []
				if  == nil {
					 = &multiLevelGap{}
					if  > 0 {
						.neighborOne = [-1]
					}
					if  < len() {
						.neighborTwo = []
					}
					[] = 
				}
				.add(multiLevelGapEntry{edge: , first: , second:  + 1}, )
				if ! {
					if .onFirstSide && .neighborTwo != nil && .neighborTwo.position.X <= .graphMin.X {
						++
					}
					if .onLastSide && .neighborOne != nil && .neighborOne.position.X+.neighborOne.size.X >= .graphMax.X {
						++
					}
				} else {
					if .onFirstSide && .neighborTwo != nil && .neighborTwo.position.Y <= .graphMin.Y {
						++
					}
					if .onLastSide && .neighborOne != nil && .neighborOne.position.Y+.neighborOne.size.Y >= .graphMax.Y {
						++
					}
				}
			}
		case  == 0:
			middleToMiddleEdgeRoute()
		case  < 0:
			[]++
			[]++
			,  = routeCycleEdge(, , , ,
				[], [])
		}
	}
}

func shouldSkipMultiLevelGap( *tEdge,  []*tNode,  int,  bool) bool {
	if len() == 0 {
		return false
	}
	 := .source.position
	if len(.bendPoints) > 0 {
		 = .bendPoints[len(.bendPoints)-1]
	}
	 := [len()-1]
	 := .position.Add(.size)
	 := [0]
	 := .position.Add(.size)
	if  {
		if  >= len()-1 && .Y > .Y && .target.position.Y > .Y {
			return true
		}
		// first.X is intentional: it matches the 0.12 Java implementation.
		return  <= 0 && .Y < .X && .target.position.Y < .Y
	}
	if  >= len()-1 && .X > .X && .target.position.X > .X {
		return true
	}
	return  <= 0 && .X < .X && .target.position.X < .X
}

func routeCycleEdge( *tGraph,  *tEdge, , , ,  int) (int, int) {
	 := .direction == "LEFT" || .direction == "RIGHT"
	 := 0.0
	for ,  := range .nodes {
		if  {
			 += .position.Y + .size.Y/2
		} else {
			 += .position.X + .size.X/2
		}
	}
	 /= float64(len(.nodes))
	 := .source.position.X + .source.size.X/2
	if  {
		 = .source.position.Y + .source.size.Y/2
	}
	 := 0.0
	if  >  {
		++
		 = math.Inf(-1)
		for ,  := range .nodes {
			 := .position.X + .size.X + .spacingEdgeNode*float64()
			if  {
				 = .position.Y + .size.Y + .spacingEdgeNode*float64()
			}
			 = math.Max(, )
		}
	} else {
		++
		 = math.Inf(1)
		for ,  := range .nodes {
			 := .position.X - .spacingEdgeNode*float64()
			if  {
				 = .position.Y - .spacingEdgeNode*float64()
			}
			 = math.Min(, )
		}
	}

	,  := .source, .target
	switch .direction {
	case "LEFT":
		.bendPoints = append(.bendPoints,
			geometry.Point{X: .levelMin - .spacingEdgeNode, Y: },
			geometry.Point{X: .position.X + .size.X + .spacingEdgeNode + .edgeEndTextureLength, Y: },
			geometry.Point{X: .position.X + .size.X + .spacingEdgeNode + .edgeEndTextureLength, Y: .position.Y + .size.Y/2},
			geometry.Point{X: .position.X + .size.X, Y: .position.Y + .size.Y/2})
	case "RIGHT":
		.bendPoints = append(.bendPoints,
			geometry.Point{X: .levelMax + .spacingEdgeNode, Y: .position.Y + .size.Y/2},
			geometry.Point{X: .position.X + .size.X + .spacingEdgeNode, Y: },
			geometry.Point{X: .position.X - .spacingEdgeNode - .edgeEndTextureLength, Y: },
			geometry.Point{X: .position.X - .spacingEdgeNode - .edgeEndTextureLength, Y: .position.Y + .size.Y/2},
			geometry.Point{X: .position.X, Y: .position.Y + .size.Y/2})
	case "UP":
		.bendPoints = append(.bendPoints,
			geometry.Point{X: , Y: .levelMin - .spacingEdgeNode},
			geometry.Point{X: , Y: .position.Y + .size.Y + .spacingEdgeNode + .edgeEndTextureLength},
			geometry.Point{X: .position.X + .size.X/2, Y: .position.Y + .size.Y + .spacingEdgeNode + .edgeEndTextureLength},
			geometry.Point{X: .position.X + .size.X/2, Y: .position.Y + .size.Y + .spacingEdgeNode})
	default:
		if len(.bendPoints) > 0 {
			.bendPoints[len(.bendPoints)-1].Y = .levelMax + .spacingEdgeNode*float64()
		}
		.bendPoints = append(.bendPoints,
			geometry.Point{X: , Y: .levelMax + .spacingEdgeNode*float64()},
			geometry.Point{X: , Y: .position.Y - .spacingEdgeNode*float64() - .edgeEndTextureLength})
	}
	return , 
}

func middleToMiddleEdgeRoute( *tEdge) {
	 := float64(.source.size.X / 2)
	 := float64(.source.size.Y / 2)
	 := geometry.Point{
		X: float64(.source.position.X + ),
		Y: float64(.source.position.Y + ),
	}
	 := float64(.target.size.X / 2)
	 := float64(.target.size.Y / 2)
	 := geometry.Point{
		X: float64(.target.position.X + ),
		Y: float64(.target.position.Y + ),
	}
	.bendPoints = append(geometry.Chain{}, .bendPoints...)
	.bendPoints = append(.bendPoints, )
	if len(.bendPoints) >= 2 {
		toNodeBorder(&.bendPoints[0], .bendPoints[1], .source.size)
		 := len(.bendPoints) - 1
		toNodeBorder(&.bendPoints[], .bendPoints[-1], .target.size)
	}
}

func avoidOverlapStartPoints( *tGraph) {
	for ,  := range .nodes {
		if .dummy {
			continue
		}
		 := make([]*tEdge, 0)
		for ,  := range .edges {
			if .source ==  && .source.treeLevel != .target.treeLevel {
				 = append(, )
			}
		}
		sort.SliceStable(, func(,  int) bool {
			,  := firstRoutePoint([]), firstRoutePoint([])
			if .direction == "LEFT" || .direction == "RIGHT" {
				return .Y < .Y
			}
			return .X < .X
		})
		for ,  := range  {
			if .compactLevelAscension && .target.treeLevel-.source.treeLevel > 0 {
				continue
			}
			 := .5
			if len() != 1 {
				 = float64(+1) / float64(len()+1)
			}
			var ,  geometry.Point
			switch .direction {
			case "LEFT":
				 := .position.Y + .size.Y*
				 = geometry.Point{X: .position.X, Y: }
				 = geometry.Point{X: math.Min(.levelMin, .position.X-.spacingEdgeNode), Y: }
			case "RIGHT":
				 := .position.Y + .size.Y*
				 = geometry.Point{X: .position.X + .size.X, Y: }
				 = geometry.Point{X: .levelMax + .spacingEdgeNode, Y: }
			case "UP":
				 := .position.X + .size.X*
				 = geometry.Point{X: , Y: .position.Y}
				 = geometry.Point{X: , Y: math.Min(.position.Y-.spacingEdgeNode, .levelMin)}
			default:
				 := .position.X + .size.X*
				 = geometry.Point{X: , Y: .position.Y + .size.Y}
				 = geometry.Point{X: , Y: .levelMax + .spacingEdgeNode}
			}
			.bendPoints = append(geometry.Chain{, }, .bendPoints...)
		}
	}
}

func avoidOverlapEndPoints( *tGraph) {
	for ,  := range .nodes {
		if .dummy {
			continue
		}
		 := make([]*tEdge, 0)
		for ,  := range .edges {
			if .target ==  && .source.treeLevel != .target.treeLevel {
				 = append(, )
			}
		}
		sort.SliceStable(, func(,  int) bool {
			,  := lastRoutePoint([]), lastRoutePoint([])
			if .direction == "LEFT" || .direction == "RIGHT" {
				return .Y < .Y
			}
			return .X < .X
		})
		for ,  := range  {
			 := .5
			if len() != 1 {
				 = float64(+1) / float64(len()+1)
			}
			switch .direction {
			case "LEFT":
				 := .position.Y + .size.Y*
				if .position.X+.size.X+.edgeEndTextureLength < .levelMax {
					.bendPoints = append(.bendPoints, geometry.Point{X: .levelMax + .spacingEdgeNode, Y: })
				} else if steepHorizontalEnd(, , .edgeEndTextureLength) {
					 := lastRoutePoint()
					 := .position.Y + .size.Y/2
					 := 
					if  > .Y {
						 -= .edgeEndTextureLength / 2
					} else {
						 += .edgeEndTextureLength / 2
					}
					.bendPoints = append(.bendPoints, geometry.Point{
						X: .position.X + .size.X + .edgeEndTextureLength/5.3,
						Y: ,
					})
				}
				.bendPoints = append(.bendPoints, geometry.Point{X: .position.X + .size.X, Y: })
			case "RIGHT":
				 := .position.Y + .size.Y*
				if .position.X-.edgeEndTextureLength > .levelMin {
					.bendPoints = append(.bendPoints, geometry.Point{X: .levelMin - .spacingEdgeNode, Y: })
				} else if steepHorizontalEnd(, , .edgeEndTextureLength) {
					 := lastRoutePoint()
					 := .position.Y + .size.Y/2
					 := 
					if  > .Y {
						 -= .edgeEndTextureLength / 2
					} else {
						 += .edgeEndTextureLength / 2
					}
					.bendPoints = append(.bendPoints, geometry.Point{
						X: .position.X - .edgeEndTextureLength/5.3,
						Y: ,
					})
				}
				.bendPoints = append(.bendPoints, geometry.Point{X: .position.X, Y: })
			case "UP":
				 := .position.X + .size.X*
				if .position.Y+.size.Y+.edgeEndTextureLength < .levelMax {
					.bendPoints = append(.bendPoints, geometry.Point{X: , Y: .levelMax + .spacingEdgeNode})
				} else if steepVerticalEnd(, , .edgeEndTextureLength) {
					 := lastRoutePoint()
					 := .position.X + .size.X/2
					 := 
					if  > .X {
						 -= .edgeEndTextureLength / 2
					} else {
						 += .edgeEndTextureLength / 2
					}
					.bendPoints = append(.bendPoints, geometry.Point{
						X: ,
						Y: .position.Y + .size.Y + .edgeEndTextureLength/5.3,
					})
				}
				.bendPoints = append(.bendPoints, geometry.Point{X: , Y: .position.Y + .size.Y})
			default:
				 := .position.X + .size.X*
				if .target.treeLevel-.source.treeLevel < 0 {
					 := lastRoutePoint()
					.bendPoints = append(.bendPoints, geometry.Point{X: , Y: .Y})
				} else if .position.Y-.edgeEndTextureLength > .levelMin {
					.bendPoints = append(.bendPoints, geometry.Point{X: , Y: .levelMin - .spacingEdgeNode})
				} else if steepVerticalEnd(, , .edgeEndTextureLength) {
					 := lastRoutePoint()
					 := .position.X + .size.X/2
					 := 
					if  > .X {
						 -= .edgeEndTextureLength / 2
					} else {
						 += .edgeEndTextureLength / 2
					}
					.bendPoints = append(.bendPoints, geometry.Point{
						X: ,
						Y: .position.Y - .edgeEndTextureLength/5.3,
					})
				}
				.bendPoints = append(.bendPoints, geometry.Point{X: , Y: .position.Y})
			}
		}
	}
}

func steepHorizontalEnd( *tEdge,  *tNode,  float64) bool {
	if  <= 0 || len(.bendPoints) == 0 {
		return false
	}
	 := lastRoutePoint()
	 := geometry.Point{X: .position.X + .size.X/2, Y: .position.Y + .size.Y/2}
	return math.Abs(.Y-.Y)/(math.Abs(.X-.X)/40) > 50
}

func steepVerticalEnd( *tEdge,  *tNode,  float64) bool {
	if  <= 0 || len(.bendPoints) == 0 {
		return false
	}
	 := lastRoutePoint()
	 := geometry.Point{X: .position.X + .size.X/2, Y: .position.Y + .size.Y/2}
	return math.Abs(.X-.X)/(math.Abs(.Y-.Y)/40) > 50
}

func firstRoutePoint( *tEdge) geometry.Point {
	if len(.bendPoints) > 0 {
		return .bendPoints[0]
	}
	return .target.position
}

func lastRoutePoint( *tEdge) geometry.Point {
	if len(.bendPoints) > 0 {
		return .bendPoints[len(.bendPoints)-1]
	}
	return .source.position
}

func packComponents( []*tGraph) *tGraph {
	if len() == 1 {
		normalizeAndApplyPadding([0])
		return [0]
	}
	if len() == 0 {
		return &tGraph{}
	}
	type  struct{ ,  geometry.Point }
	 := make(map[*tGraph], len())
	 := make(map[*tGraph]int, len())
	for ,  := range  {
		 := {: geometry.Point{X: float64(math.MaxInt32), Y: float64(math.MaxInt32)}, : geometry.Point{X: float64(math.MinInt32), Y: float64(math.MinInt32)}}
		for ,  := range .nodes {
			[] += graph.Get(&.props, Priority)
			..X = math.Min(..X, .position.X)
			..Y = math.Min(..Y, .position.Y)
			..X = math.Max(..X, .position.X+.size.X)
			..Y = math.Max(..Y, .position.Y+.size.Y)
		}
		[] = 
	}
	sort.SliceStable(, func(,  int) bool {
		,  := [], []
		if [] != [] {
			return [] > []
		}
		,  := [], []
		 := (..X - ..X) * (..Y - ..Y)
		 := (..X - ..X) * (..Y - ..Y)
		return  < 
	})
	 := [0].settingsClone()
	,  := 0.0, 0.0
	for ,  := range  {
		 := []
		,  := ..X-..X, ..Y-..Y
		 = math.Max(, )
		 +=  * 
	}
	 = math.Max(, float64(float32(math.Sqrt()))*.aspectRatio)
	, ,  := 0.0, 0.0, 0.0
	for ,  := range  {
		 := []
		,  := ..X-..X, ..Y-..Y
		if + >  {
			 = 0
			 +=  + .spacing
			 = 0
		}
		 := geometry.Point{X:  - ..X, Y:  - ..Y}
		for ,  := range .nodes {
			.position = .position.Add()
			.nodes = append(.nodes, )
		}
		for ,  := range .edges {
			.bendPoints.Offset()
			if !containsEdge(.edges, ) {
				.edges = append(.edges, )
			}
		}
		 = math.Max(, )
		 +=  + .spacing
	}
	computeGraphBounds()
	normalizeAndApplyPadding()
	return 
}

func normalizeAndApplyPadding( *tGraph) {
	if len(.nodes) == 0 {
		return
	}
	 := geometry.Point{
		X: .padding.Left - .graphMin.X,
		Y: .padding.Top - .graphMin.Y,
	}
	for ,  := range .nodes {
		.position = .position.Add()
	}
	 := make(map[*tEdge]bool, len(.edges))
	for ,  := range .edges {
		if [] {
			continue
		}
		[] = true
		.bendPoints.Offset()
	}
	.graphMin = .graphMin.Add()
	.graphMax = .graphMax.Add()
}

func applyLayout( *graph.Model,  graph.NodeID,  *tGraph) error {
	,  := float64(math.MaxInt32), float64(math.MaxInt32)
	,  := float64(math.MinInt32), float64(math.MinInt32)
	for ,  := range .nodes {
		 = math.Min(, .position.X-.size.X/2)
		 = math.Min(, .position.Y-.size.Y/2)
		 = math.Max(, .position.X+.size.X/2)
		 = math.Max(, .position.Y+.size.Y/2)
	}
	for ,  := range .nodes {
		if .origin == nil {
			continue
		}
		 := .Node(*.origin)
		.Shape.SetLocation(.position.X, .position.Y)
		.Properties.CopyFrom(&.props)
	}
	for ,  := range .edges {
		if .origin == nil || .source.origin == nil || .target.origin == nil {
			continue
		}
		if len(.bendPoints) < 2 {
			return fmt.Errorf("mrtree: the vector chain must contain at least a source and a target point")
		}
		 := .Edge(*.origin)
		var  graph.SectionID
		if len(.Sections) == 0 {
			 = .AddSection(*.origin)
		} else {
			 = .Sections[0]
		}
		 := .Section()
		.Start = .bendPoints[0]
		.End = .bendPoints[len(.bendPoints)-1]
		.StartPresent, .EndPresent = true, true
		if .edgeRoutingMode == "MIDDLE_TO_MIDDLE" {
			// elkjs 0.12's JSON bridge exposes both vectors in this mode as
			// bend points in addition to using them as the section endpoints.
			.BendPoints = append(.BendPoints[:0], .bendPoints...)
		} else {
			.BendPoints = append(.BendPoints[:0], .bendPoints[1:len(.bendPoints)-1]...)
		}
		.BendPointsPresent = len(.BendPoints) > 0
	}
	 := .Node()
	 :=  -  + .padding.Left + .padding.Right
	 :=  -  + .padding.Top + .padding.Bottom
	if !.fixedGraphSize {
		.Shape.SetDimensions(, )
	}
	graph.Set(&.Properties, core.ChildAreaWidth, -.padding.Left-.padding.Right)
	graph.Set(&.Properties, core.ChildAreaHeight, -.padding.Top-.padding.Bottom)
	return nil
}

func toNodeBorder( *geometry.Point,  geometry.Point,  geometry.Point) {
	,  := float64(.X/2), float64(.Y/2)
	 := float64(.X - .X)
	 := float64(.Y - .Y)
	,  := math.Abs(), math.Abs()
	,  := 1.0, 1.0
	if  >  {
		 = float64( / )
	}
	if  >  {
		 = float64( / )
	}
	 := math.Min(, )
	 := float64( * )
	 := float64( * )
	.X = float64(.X + )
	.Y = float64(.Y + )
}