package placement

import (
	
	

	
	
	
)

// dejitter performs micro-movements on nodes to remove the jittery connections that can be straightened out with slight adjustments in one direction
// E.g. jittery line:
// .             +--------->
// . +-----------+
func ( context.Context,  *layoutgraph.Graph) (bool, error) {
	, ,  := layoutgraph.EnsureTransactionWorkGuard(, "DejitterTransactions")
	if  != nil {
		return false, 
	}
	 := false
	,  := .NewRequestTransaction(, layoutgraph.TransactionOptions{AffectContainers: true})
	if  != nil {
		return false, 
	}
	if len(.Nodes) == 0 {
		return false, nil
	}
	var  *layoutgraph.Transaction
	 := false
	defer func() {
		if  != nil && ! {
			.Rollback()
		}
	}()
	for ,  := range .Nodes {
		if .Cluster != nil {
			continue
		}
		// Too much trouble to have to jitter all children too
		if .IsContainer() {
			continue
		}
		if ,  := .NodeToTree[];  {
			continue
		}
		if .Sequence != nil {
			continue
		}
		if .FixedTopLeft != nil {
			continue
		}

		,  := placementcost.NodeSymmetry(, , nil)
		if  != nil {
			return false, 
		}
		for ,  := range .Edges {
			// No jitter possible with less than 3 segments
			if .NumSegments() < 3 {
				continue
			}
			if .Adjacent().Cluster != nil {
				continue
			}

			var  *geo.Point
			var  *geo.Point
			 := make([]*geo.Point, 0)
			// Skip the first of each since it's the port
			if .From ==  {
				 = append(, .Points[1], .Points[2])
				 = .Points[3]
				 = .Points[0]
			} else if .To ==  {
				 = append(, .Points[len(.Points)-2], .Points[len(.Points)-3])
				 = .Points[len(.Points)-4]
				 = .Points[len(.Points)-1]
			}

			// Only a jitter if the last two bends fall within threshold
			if geo.EuclideanDistance([0].X, [0].Y, [1].X, [1].Y) > jitterThreshold {
				continue
			}

			// A vertical line moves horizontally to the second bend's X to straighten it.
			 := [0].Y == [1].Y

			// TODO: support correcting U-turns.
			// Leave them unchanged here because they are not straightforward to collapse safely.
			// A U-turn has both the point before the bends and the point on the node on one side of the bends.
			if  {
				if (.Y > [0].Y) && (.Y > [0].Y) {
					continue
				}
				if (.Y < [0].Y) && (.Y < [0].Y) {
					continue
				}
			} else {
				if (.X > [0].X) && (.X > [0].X) {
					continue
				}
				if (.X < [0].X) && (.X < [0].X) {
					continue
				}
			}

			if  {
				if [1].X == [0].X {
					continue
				}
			} else {
				if [1].Y == [0].Y {
					continue
				}
			}

			// ---- from here on we know it is a jitter line

			// Look for other connected edges which are straight lines
			 := false
			for ,  := range .Edges {
				if  ==  {
					continue
				}
				if .NumSegments() > 1 {
					continue
				}
				// If the jittering one is vertical, we only look for other vertical ones
				if .From ==  {
					if  && (.Points[0].X == .Points[1].X) {
						 = true
						break
					}
					if ! && (.Points[0].Y == .Points[1].Y) {
						 = true
						break
					}
				} else {
					if  && (.Points[len(.Points)-1].X == .Points[len(.Points)-2].X) {
						 = true
						break
					}
					if ! && (.Points[len(.Points)-1].Y == .Points[len(.Points)-2].Y) {
						 = true
						break
					}
				}
			}
			// Don't want to move other nodes
			if  {
				continue
			}

			// ---- from here on we know there is no adjacent node connected via a tangent straight line

			var  float64
			if  {
				 = math.Round([1].X - [0].X)
			} else {
				 = math.Round([1].Y - [0].Y)
			}

			// Sometimes it'll get real close to a sign flip but not yet. We want to prevent these super short edges, so we'll extend delta a little to consider those a sign flip
			var  float64
			if  < 0 {
				 =  - signFlipPadding
			} else {
				 =  + signFlipPadding
			}

			// A sign flip is when there's movement on the endpoint but not the bend, and the new endpoint ends up
			// on the other axis of the bend (potentially going into the node)
			// For edges that are opposite directions (one vert one horiz), the concern is that the jitter causes it to go past the nearest bend
			// For edges that are same directions, the concern is that the jitter causes it to go past the second nearest bend
			 := false
			// Map of the original edge to its closest two segments
			 := make(map[*layoutgraph.Edge][]*geo.Point)

			// Note that the edge itself is included in this search when it's opposite direction, as it needs to be checked for new intersections as well
			for ,  := range .Edges {
				var  bool
				if .From ==  {
					 = .Points[0].X == .Points[1].X
				} else {
					 = .Points[len(.Points)-1].X == .Points[len(.Points)-2].X
				}

				// This can happen if they are really close to each other
				// Diagonal points should be free to move around for the purpose of dejitter
				 := (len(.Points) == 2) && (.Points[0].X != .Points[1].X) && (.Points[0].Y != .Points[1].Y)
				// The distance will be so small we don't have to worry about new intersections, and sign flips can't happen
				if  {
					continue
				}

				// Moving horizontally and edge vertical (move both x distance)
				if  &&  {
					var  int
					var  int
					if .From ==  {
						 = 1
						 = 2
						[] = []*geo.Point{
							geo.NewPoint(.Points[0].X+, .Points[0].Y),
							geo.NewPoint(.Points[1].X+, .Points[1].Y),
						}
					} else {
						 = len(.Points) - 2
						 = len(.Points) - 3
						[] = []*geo.Point{
							geo.NewPoint(.Points[len(.Points)-1].X+, .Points[len(.Points)-1].Y),
							geo.NewPoint(.Points[len(.Points)-2].X+, .Points[len(.Points)-2].Y),
						}
					}
					if  !=  {
						if ((.Points[].X+ < .Points[].X) && (.Points[].X > .Points[].X)) ||
							((.Points[].X+ > .Points[].X) && (.Points[].X < .Points[].X)) {
							 = true
						}
					}
				}
				// Moving horizontally and edge horizontal (move closest x distance)
				if  && ! {
					var  int
					var  int
					if .From ==  {
						 = 0
						 = 1
						[] = []*geo.Point{
							geo.NewPoint(.Points[0].X+, .Points[0].Y),
							.Points[1],
						}
					} else {
						 = len(.Points) - 1
						 = len(.Points) - 2
						[] = []*geo.Point{
							geo.NewPoint(.Points[len(.Points)-1].X+, .Points[len(.Points)-1].Y),
							.Points[len(.Points)-2],
						}
					}
					if ((.Points[].X+ < .Points[].X) && (.Points[].X > .Points[].X)) ||
						((.Points[].X+ > .Points[].X) && (.Points[].X < .Points[].X)) {
						 = true
					}
				}
				// Moving vertical and edge horizontal (move both y distance)
				if ! && ! {
					var  int
					var  int
					if .From ==  {
						 = 1
						 = 2
						[] = []*geo.Point{
							geo.NewPoint(.Points[0].X, .Points[0].Y+),
							geo.NewPoint(.Points[1].X, .Points[1].Y+),
						}
					} else {
						 = len(.Points) - 2
						 = len(.Points) - 3
						[] = []*geo.Point{
							geo.NewPoint(.Points[len(.Points)-1].X, .Points[len(.Points)-1].Y+),
							geo.NewPoint(.Points[len(.Points)-2].X, .Points[len(.Points)-2].Y+),
						}
					}
					if  !=  {
						if ((.Points[].Y+ < .Points[].Y) && (.Points[].Y > .Points[].Y)) ||
							((.Points[].Y+ > .Points[].Y) && (.Points[].Y < .Points[].Y)) {
							 = true
						}
					}
				}
				// Moving vertical and edge vertical (move closest y distance)
				if ! &&  {
					var  int
					var  int
					if .From ==  {
						 = 0
						 = 1
						[] = []*geo.Point{
							geo.NewPoint(.Points[0].X, .Points[0].Y+),
							.Points[1],
						}
					} else {
						 = len(.Points) - 1
						 = len(.Points) - 2
						[] = []*geo.Point{
							geo.NewPoint(.Points[len(.Points)-1].X, .Points[len(.Points)-1].Y+),
							.Points[len(.Points)-2],
						}
					}
					if ((.Points[].Y+ < .Points[].Y) && (.Points[].Y > .Points[].Y)) ||
						((.Points[].Y+ > .Points[].Y) && (.Points[].Y < .Points[].Y)) {
						 = true
					}
				}

				if  {
					break
				}
			}

			if  {
				continue
			}

			 := false
			for ,  := range  {
				// Check for intersections on other nodes
				for ,  := range .Nodes {
					if  ==  {
						continue
					}
					// Can intersect with a container if one endpoint is inside it
					if .From.IsDescendantOf() {
						continue
					}
					if .To.IsDescendantOf() {
						continue
					}
					// It can touch the node it's connected to
					if (( != .To) && ( != .From)) && .PassesThrough([0], [1]) {
						 = true
						break
					}
				}
				if  {
					break
				}
			}
			if  {
				continue
			}

			// ---- from here on we know there is no object intersection introduced by updating all the edges to avoid the jitter, so we can safely shift to dejitter

			 := 0
			for ,  := range .Edges {
				if (.From == ) || (.To == ) {
					continue
				}

				for  := 0;  < len(.Points)-1; ++ {
					if .PassesThrough(.Points[], .Points[+1]) {
						++
					}
				}
			}

			if  == nil {
				 := layoutgraph.NewGraphStateSnapshot(layoutgraph.GraphStateSnapshotOptions{
					CaptureEdgeRoutes: true,
				})
				if  := .UpdateWithWorkGuard(, );  != nil {
					return false, 
				}
				 = &layoutgraph.Transaction{Graph: , PriorGraphState: }
			}

			.AddOp(func() error {
				// Tentatively commit the node
				if  {
					.TopLeft.X += 
				} else {
					.TopLeft.Y += 
				}

				 := 0
				for ,  := range .Edges {
					if (.From == ) || (.To == ) {
						continue
					}

					for  := 0;  < len(.Points)-1; ++ {
						if .PassesThrough(.Points[], .Points[+1]) {
							++
						}
					}
				}

				,  := placementcost.NodeSymmetry(, , nil)
				if  != nil {
					return 
				}
				if  >  {
					return layoutgraph.ErrNonImprovingCandidate
				} else if (.Container != nil) && .SpillsOutOf(.Container) {
					return layoutgraph.ErrInvalidCandidate
				} else if  <  {
					return layoutgraph.ErrNonImprovingCandidate
				}
				return nil
			})

			if  := .Commit();  != nil {
				.Clear()
				if layoutgraph.IsCandidateRejection() {
					continue
				}
				return false, 
			}
			if  := .UpdateState();  != nil {
				return false, 
			}
			.Clear()

			// ---- from here on we know jittering this node does not introduce any more route intersections

			// Commit new segments
			for ,  := range .Edges {

				var  bool
				if .From ==  {
					 = .Points[0].X == .Points[1].X
				} else {
					 = .Points[len(.Points)-1].X == .Points[len(.Points)-2].X
				}

				 := (len(.Points) == 2) && (.Points[0].X != .Points[1].X) && (.Points[0].Y != .Points[1].Y)
				// If it's diagonal, we just need to update the one point on the node that's moved
				if  {
					if  {
						if .From ==  {
							.Points[0].X += 
						} else {
							.Points[len(.Points)-1].X += 
						}
					} else {
						if .From ==  {
							.Points[0].Y += 
						} else {
							.Points[len(.Points)-1].Y += 
						}
					}
				} else {
					// Moving horizontally and edge vertical (move both x distance)
					if  &&  {
						if .From ==  {
							.Points[0].X += 
							.Points[1].X += 
						} else {
							.Points[len(.Points)-1].X += 
							.Points[len(.Points)-2].X += 
						}
					}
					// Moving horizontally and edge horizontal (move closest x distance)
					if  && ! {
						if .From ==  {
							.Points[0].X += 
						} else {
							.Points[len(.Points)-1].X += 
						}
					}
					// Moving vertical and edge horizontal (move both y distance)
					if ! && ! {
						if .From ==  {
							.Points[0].Y += 
							.Points[1].Y += 
						} else {
							.Points[len(.Points)-1].Y += 
							.Points[len(.Points)-2].Y += 
						}
					}
					// Moving vertical and edge vertical (move closest y distance)
					if ! &&  {
						if .From ==  {
							.Points[0].Y += 
						} else {
							.Points[len(.Points)-1].Y += 
						}
					}
				}
			}

			// Remove the two defunct points corresponding to the old bends
			if .From ==  {
				// This should remove 1 and 2
				.Points = append(.Points[:1], .Points[3:]...)
			} else {
				.Points = append(.Points[:len(.Points)-3], .Points[len(.Points)-1:]...)
			}
			 = true
		}
	}
	if  {
		if  := .Finish();  != nil {
			return false, 
		}
	}
	 = true
	return , nil
}