package routing

import (
	

	
	
)

// simplifyEdgeRoutes post-processes edge routes to remove unnecessary bending caused by the constraint that routes have to go through OVG nodes
// It identifies unnecessary bends in routes and eliminates them when possible.
func ( context.Context,  *layoutgraph.Graph) error {
	return simplifyEdgeRoutesWithLimit(, , maxRouteStageWorkUnits)
}

func simplifyEdgeRoutesWithLimit( context.Context,  *layoutgraph.Graph,  uint64) error {
	return runAtomicRouteStage(, "SimplifyEdgeRoutes", , nil, , func( *routeWorkGuard) error {
		for ,  := range .Edges {
			if  := .step();  != nil {
				return 
			}
			for  := true; ; {
				,  := simplifyPoints(, , )
				if  != nil {
					return 
				}
				 = len() < len(.Points)
				if  {
					.Points = 
				}
			}
		}
		return nil
	})
}

func simplifyPoints( *layoutgraph.Graph,  *layoutgraph.Edge,  *routeWorkGuard) ([]*geo.Point, error) {
	 := .Points

	if len() < 5 {
		return , .step()
	}

	// Make a copy of the points to avoid modifying the original
	 := []*geo.Point{[0]}
	 := 0

	/*
			We want to find these and just simplify to L-shape
			 //                 ▲
		   //                 │
		   //                 │
		   //                 │
		   // ────────┐       │
		   //         │       │
		   //         │       │
		   //         │       │
		   //         └───────┘
	*/
	for  < len()-4 {
		if  := .step();  != nil {
			return nil, 
		}
		 := []
		 := [+1]
		 := [+2]
		 := [+3]
		 := [+4]

		,  := .X-.X, .Y-.Y // p1→p2
		,  := .X-.X, .Y-.Y // p2→p3
		,  := .X-.X, .Y-.Y // p3→p4
		,  := .X-.X, .Y-.Y // p4→p5

		 := isHorizontalSegment(, )
		 := isVerticalSegment(, )
		 := isHorizontalSegment(, )
		 := isVerticalSegment(, )
		 := isHorizontalSegment(, )
		 := isVerticalSegment(, )
		 := isHorizontalSegment(, )
		 := isVerticalSegment(, )

		// Pattern detection for special case:
		// 1. p2→p3 and p4→p5 are both vertical and going in opposite directions
		// 2. p1→p2 and p3→p4 are both horizontal and going in the same direction
		 :=  &&  &&
			(( > 0 &&  < 0) || ( < 0 &&  > 0))

		 :=  &&  &&
			(( > 0 &&  > 0) || ( < 0 &&  < 0))

		// Alternative pattern:
		// 1. p2→p3 and p4→p5 are both horizontal and going in opposite directions
		// 2. p1→p2 and p3→p4 are both vertical and going in the same direction
		 :=  &&  &&
			(( > 0 &&  < 0) || ( < 0 &&  > 0))

		 :=  &&  &&
			(( > 0 &&  > 0) || ( < 0 &&  < 0))

		// Check for the pattern described
		 := ( && ) ||
			( && )

		var  *geo.Point
		 := false

		if  {
			// Find the intersection point between the first segment (p1→p2) and fourth segment (p4→p5)
			 = findIntersectionPoint(, , , )

			// Both emitted legs must be legal. Checking only the extension of
			// the first leg misses obstacles crossed by the second leg, and can
			// even reverse the approach into a fixed row port.
			 =  == nil
			if  != nil {
				if  == 0 && .From.ContainsPoint(, 1) && !sameRouteDirection(, , , ) {
					 = true
				}
				if +4 == len()-1 && .To.ContainsPoint(, 1) && !sameRouteDirection(, , , ) {
					 = true
				}
				for ,  := range [][2]*geo.Point{{, }, {, }} {
					,  := lineIntersectsUnrelatedNode(, , [0], [1], )
					if  != nil {
						return nil, 
					}
					 =  || 
					,  = lineIntersectsOtherEdges(, , [0], [1], )
					if  != nil {
						return nil, 
					}
					 =  || 
				}
			}
		}

		 :=  && !

		if  {
			// For a simplified route, we want: p1 → intersection → p5
			// p1 is already in the result array, so just add intersection and p5
			 = append(, )
			 = append(, )

			 += 4

			// Assume 1 simplification per edge
			break
		} else {
			// If no pattern detected or it can't be simplified, keep the current point and move to the next
			 = append(, )
			++
		}
	}

	// Add remaining points, making sure we don't go out of bounds
	 :=  + 1
	if  < len() {
		for  := ;  < len(); ++ {
			if  := .step();  != nil {
				return nil, 
			}
			 = append(, [])
		}
	}

	return , nil
}

// findIntersectionPoint calculates the intersection point of the lines p1→p2 and p3→p4
// This is used to find the intersection point between segments
func findIntersectionPoint(, , ,  *geo.Point) *geo.Point {
	if isHorizontalSegment(, ) && isVerticalSegment(, ) {
		return &geo.Point{
			X: .X,
			Y: .Y,
		}
	} else if isVerticalSegment(, ) && isHorizontalSegment(, ) {
		return &geo.Point{
			X: .X,
			Y: .Y,
		}
	}

	return nil
}

func isHorizontalSegment(,  *geo.Point) bool {
	return .Y == .Y
}

func isVerticalSegment(,  *geo.Point) bool {
	return .X == .X
}

// sameRouteDirection preserves the signed departure/approach direction, not
// merely the axis. A zero-length replacement cannot preserve a port approach.
func sameRouteDirection(, , ,  *geo.Point) bool {
	return (.X-.X)*(.X-.X)+(.Y-.Y)*(.Y-.Y) > 0 &&
		(.X-.X)*(.Y-.Y) == (.Y-.Y)*(.X-.X)
}

// lineIntersectsUnrelatedNode checks every obstacle's open interior. Contact at
// an endpoint is legal; entering the endpoint's node from its far side is not.
// Ancestor containers are allowed because their descendants route inside them.
func lineIntersectsUnrelatedNode( *layoutgraph.Graph,  *layoutgraph.Edge, ,  *geo.Point,  *routeWorkGuard) (bool, error) {
	for ,  := range .Nodes {
		if  := .step();  != nil {
			return false, 
		}
		if .TopLeft == nil || .Width <= 0 || .Height <= 0 {
			continue
		}
		if  != .From &&  != .To &&
			(.From.IsDescendantOf() || .To.IsDescendantOf()) {
			continue
		}
		if orthogonalSegmentEntersNode(, , ) {
			return true, nil
		}
	}
	return false, nil
}

func orthogonalSegmentEntersNode( *layoutgraph.Node, ,  *geo.Point) bool {
	const  = 1e-6
	,  := .TopLeft.X+, .TopLeft.X+.Width-
	,  := .TopLeft.Y+, .TopLeft.Y+.Height-
	if .Y == .Y {
		return  < .Y && .Y <  && min(.X, .X) <  && max(.X, .X) > 
	}
	if .X == .X {
		return  < .X && .X <  && min(.Y, .Y) <  && max(.Y, .Y) > 
	}
	return true
}

// lineIntersectsOtherEdges checks if the line from p1 to p2 intersects with any
// other edges in the graph (excluding the edge being simplified)
func lineIntersectsOtherEdges( *layoutgraph.Graph,  *layoutgraph.Edge, ,  *geo.Point,  *routeWorkGuard) (bool, error) {
	for ,  := range .Edges {
		if  := .step();  != nil {
			return false, 
		}
		if  ==  {
			continue
		}

		if len(.Points) < 2 {
			continue
		}

		for  := 0;  < len(.Points)-1; ++ {
			if  := .step();  != nil {
				return false, 
			}
			if intersects(, , .Points[], .Points[+1]) {
				return true, nil
			}
		}
	}

	return false, nil
}