// Copyright (c) 2016 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
// https://www.eclipse.org/legal/epl-2.0.
//
// SPDX-License-Identifier: EPL-2.0

package intermediate

import (
	
	
	

	
	
	
	basegraph 
	
)

const (
	compactionFuzzyTolerance = 0.0001
	compactionSpacingEpsilon = 0.5
	compactionSmallEpsilon   = 0.01
)

// CompactHorizontally is the arena-backed port of ELK 0.8.1's
// HorizontalGraphCompactor and its one-dimensional constraint graph.
func ( *layered.LGraphArena,  layered.LGraphID) error {
	 := basegraph.Get(&.Graph().Properties, layered.PostCompactionStrategy)
	if  == layered.GraphCompactionNone {
		return nil
	}
	 := newLayeredCompactionTransformer(, )
	,  := .transform()
	if  != nil {
		return 
	}
	 := newOneDimensionalCompactor(, )
	 := basegraph.Get(&.Graph().Properties, layered.PostCompactionConstraints)
	.quadraticConstraints =  == layered.ConstraintCalculationQuadratic

	switch  {
	case layered.GraphCompactionLeft:
		.compact(false)
	case layered.GraphCompactionRight:
		.changeDirection(compactRight)
		.compact(false)
	case layered.GraphCompactionLeftRightConstraintLocking:
		.compact(false)
		.changeDirection(compactRight)
		.lock = func( *compactNode,  compactDirection) bool {
			return .group.outDegreeReal == 0
		}
		.compact(false)
	case layered.GraphCompactionLeftRightConnectionLocking:
		.compact(false)
		.changeDirection(compactRight)
		.lock = func( *compactNode,  compactDirection) bool {
			 := .locks[]
			return  == compactLeft && .left ||  == compactRight && .right
		}
		.compact(false)
	case layered.GraphCompactionEdgeLength:
		.compact(true)
	default:
		return fmt.Errorf("layered: unsupported post-compaction strategy %d", )
	}
	.changeDirection(compactLeft)
	.applyLayout()
	return nil
}

type compactDirection uint8

const (
	compactUndefined compactDirection = iota
	compactLeft
	compactRight
)

type compactLock struct{ left, right bool }

type compactGraph struct {
	nodes      []*compactNode
	groups     []*compactGroup
	predefined [][2]*compactNode
}

type compactNode struct {
	id          int
	node        *layered.LNodeID
	segment     *verticalSegment
	group       *compactGroup
	groupOffset geometry.Point
	hitbox      geometry.Rectangle
	before      geometry.Rectangle
	constraints []*compactNode
	start       float64
}

type compactGroup struct {
	id            int
	nodes         []*compactNode
	master        *compactNode
	reference     *compactNode
	start         float64
	outDegree     int
	outDegreeReal int
}

func ( *compactGraph) ( *compactNode) *compactNode {
	.nodes = append(.nodes, )
	return 
}

func ( *compactGraph) ( ...*compactNode) *compactGroup {
	 := &compactGroup{nodes: append([]*compactNode(nil), ...)}
	for ,  := range  {
		if .group != nil {
			panic("layered: compaction node belongs to multiple groups")
		}
		.group = 
	}
	if len() > 0 {
		.reference = [0]
	}
	.groups = append(.groups, )
	return 
}

func ( *compactGroup) ( *compactNode) {
	if .group != nil {
		panic("layered: compaction node belongs to multiple groups")
	}
	.nodes = append(.nodes, )
	.group = 
	if .reference == nil {
		.reference = 
	}
}

type verticalSegment struct {
	potentialParents      []*compactNode
	edges                 []layered.LEdgeID
	sourcePorts           []layered.LPortID
	targetPorts           []layered.LPortID
	affectedBends         []*geometry.Point
	affectedControls      []*geometry.Point
	affectedBoundingBoxes []*geometry.Rectangle
	affectedJunctions     []*geometry.Point
	hitbox                geometry.Rectangle
	ignoreUp              bool
	ignoreDown            bool
	constraints           []*verticalSegment
	port                  *layered.LPortID
	joined                []*verticalSegment
}

func newVerticalSegment(
	 *layered.LGraphArena,
	,  *geometry.Point,
	 *compactNode,
	 layered.LEdgeID,
) *verticalSegment {
	 := &verticalSegment{
		edges:         []layered.LEdgeID{},
		affectedBends: []*geometry.Point{, },
		hitbox: geometry.Rectangle{
			X:      math.Min(.X, .X),
			Y:      math.Min(.Y, .Y),
			Width:  math.Abs(.X - .X),
			Height: math.Abs(.Y - .Y),
		},
	}
	if  != nil {
		.potentialParents = append(.potentialParents, )
	}
	if ,  := basegraph.TryGet(&.Edge().Properties, layered.JunctionPoints);  {
		for  := range  {
			if fuzzyEqual([].X, .X) {
				.affectedJunctions = append(.affectedJunctions, &[])
			}
		}
	}
	return 
}

func ( *verticalSegment) ( *verticalSegment) bool {
	return fuzzyEqual(.hitbox.X, .hitbox.X) &&
		!(fuzzyLess(.hitbox.MaxY(), .hitbox.Y) ||
			fuzzyLess(.hitbox.MaxY(), .hitbox.Y))
}

func ( *verticalSegment) ( *verticalSegment) {
	.edges = append(.edges, .edges...)
	.sourcePorts = append(.sourcePorts, .sourcePorts...)
	.targetPorts = append(.targetPorts, .targetPorts...)
	.affectedBends = append(.affectedBends, .affectedBends...)
	.affectedControls = append(.affectedControls, .affectedControls...)
	.affectedBoundingBoxes = append(
		.affectedBoundingBoxes, .affectedBoundingBoxes...)
	.affectedJunctions = append(.affectedJunctions, .affectedJunctions...)
	.constraints = append(.constraints, .constraints...)
	.potentialParents = append(.potentialParents, .potentialParents...)
	.hitbox = .hitbox.Union(.hitbox)
	.ignoreUp = .ignoreUp || .ignoreUp
	.ignoreDown = .ignoreDown || .ignoreDown
	if .port == nil {
		.port = .port
	}
	.joined = append(.joined, .joined...)
	.joined = append(.joined, )
}

type commentOffset struct {
	comment layered.LNodeID
	other   layered.LNodeID
	offset  geometry.Point
}

type layeredCompactionTransformer struct {
	arena   *layered.LGraphArena
	graphID layered.LGraphID
	graph   *compactGraph

	nodes        map[layered.LNodeID]*compactNode
	segmentNodes map[*verticalSegment]*compactNode
	locks        map[*compactNode]compactLock
	comments     []commentOffset
	edgeRouting  layered.EdgeRouting
}

func newLayeredCompactionTransformer(
	 *layered.LGraphArena,
	 layered.LGraphID,
) *layeredCompactionTransformer {
	return &layeredCompactionTransformer{
		arena:        ,
		graphID:      ,
		graph:        &compactGraph{},
		nodes:        make(map[layered.LNodeID]*compactNode),
		segmentNodes: make(map[*verticalSegment]*compactNode),
		locks:        make(map[*compactNode]compactLock),
		edgeRouting:  basegraph.Get(&.Graph().Properties, layered.EdgeRoutingOption),
	}
}

func ( *layeredCompactionTransformer) () (*compactGraph, error) {
	.transformNodes()
	var  []*verticalSegment
	switch .edgeRouting {
	case layered.EdgeRoutingOrthogonal:
		 = .collectOrthogonalSegments()
	case layered.EdgeRoutingSplines:
		 = .collectSplineSegments()
	default:
		return nil, fmt.Errorf("layered: post-compaction does not support edge routing %d", .edgeRouting)
	}
	.mergeSegments()
	for ,  := range .segmentNodes {
		for ,  := range .constraints {
			if  := .segmentNodes[];  != nil {
				.graph.predefined = append(.graph.predefined, [2]*compactNode{, })
			}
		}
	}
	return .graph, nil
}

func ( *layeredCompactionTransformer) () {
	 := .arena.Graph(.graphID)
	for ,  := range .Layers {
		.arena.Layer().ID = 
		for ,  := range .arena.Layer().Nodes {
			 := .arena.Node()
			// Comment nodes are represented by their owner's margin and are
			// restored by relative offset after compaction.
			if basegraph.Get(&.Properties, core.CommentBox) {
				 := .arena.NodeConnectedEdges()
				if len() > 0 {
					 := .arena.EdgeSourceNode([0])
					if  ==  {
						 = .arena.EdgeTargetNode([0])
					}
					.comments = append(.comments, commentOffset{
						comment: ,
						other:   ,
						offset:  .Position.Sub(.arena.Node().Position),
					})
					continue
				}
			}
			 := 
			 := .graph.addNode(&compactNode{
				node: &,
				hitbox: geometry.Rectangle{
					X:      .Position.X - .Margin.Left,
					Y:      .Position.Y - .Margin.Top,
					Width:  .Size.X + .Margin.Left + .Margin.Right,
					Height: .Size.Y + .Margin.Top + .Margin.Bottom,
				},
			})
			 := .graph.addGroup()
			.master = 
			 := compactLock{}
			 := len(.arena.NodeIncomingEdges()) - len(.arena.NodeOutgoingEdges())
			if  < 0 {
				.left = true
			} else if  > 0 {
				.right = true
			}
			if .Type == layered.ExternalPortNode {
				 = compactLock{}
			}
			.nodes[] = 
			.locks[] = 
		}
	}
}

func ( *layeredCompactionTransformer) () []*verticalSegment {
	 := make([]*verticalSegment, 0)
	for ,  := range .arena.Graph(.graphID).Layers {
		for ,  := range .arena.Layer().Nodes {
			 := .nodes[]
			for ,  := range .arena.NodeOutgoingEdges() {
				 := .arena.Edge()
				if len(.BendPoints) == 0 ||  == nil {
					continue
				}
				 := &.BendPoints[0]
				 := true
				var  *verticalSegment
				 := .arena.Port(*.Source)
				switch .Side {
				case layered.NorthSide:
					 := &geometry.Point{X: .X, Y: .hitbox.Y}
					 := newVerticalSegment(.arena, , , , )
					.ignoreDown = true
					 := *.Source
					.port = &
					 = append(, )
				case layered.SouthSide:
					 := &geometry.Point{X: .X, Y: .hitbox.MaxY()}
					 := newVerticalSegment(.arena, , , , )
					.ignoreUp = true
					 := *.Source
					.port = &
					 = append(, )
				}

				for  := 1;  < len(.BendPoints); ++ {
					 := &.BendPoints[]
					if !fuzzyEqual(.Y, .Y) {
						 = newVerticalSegment(.arena, , , nil, )
						 = append(, )
						if  {
							 = false
							if .Y < .hitbox.Y {
								.ignoreDown = true
							} else if .Y > .hitbox.MaxY() {
								.ignoreUp = true
							} else {
								.ignoreUp, .ignoreDown = true, true
							}
						}
					}
					// ELK only advances bend1 when another iterator element
					// remains; the endpoint used below is consequently the
					// penultimate bend.
					if +1 < len(.BendPoints) {
						 = 
					}
				}
				if  != nil {
					 := .nodes[.arena.EdgeTargetNode()]
					if  != nil {
						if .Y < .hitbox.Y {
							.ignoreDown = true
						} else if .Y > .hitbox.MaxY() {
							.ignoreUp = true
						} else {
							.ignoreUp, .ignoreDown = true, true
						}
					}
				}
			}

			for ,  := range .arena.NodeIncomingEdges() {
				 := .arena.Edge()
				if len(.BendPoints) == 0 ||  == nil {
					continue
				}
				 := &.BendPoints[len(.BendPoints)-1]
				 := .arena.Port(*.Target)
				switch .Side {
				case layered.NorthSide:
					 := &geometry.Point{X: .X, Y: .hitbox.Y}
					 := newVerticalSegment(.arena, , , , )
					.ignoreDown = true
					 := *.Target
					.port = &
					 = append(, )
				case layered.SouthSide:
					 := &geometry.Point{X: .X, Y: .hitbox.MaxY()}
					 := newVerticalSegment(.arena, , , , )
					.ignoreUp = true
					 := *.Target
					.port = &
					 = append(, )
				}
			}
		}
	}
	return 
}

func ( *layeredCompactionTransformer) () []*verticalSegment {
	 := make([]*verticalSegment, 0)
	for ,  := range .arena.Graph(.graphID).Layers {
		for ,  := range .arena.Layer().Nodes {
			for ,  := range .arena.NodeOutgoingEdges() {
				if .arena.EdgeIsSelfLoop() {
					continue
				}
				 := .arena.Edge()
				,  := basegraph.TryGet(&.Properties, layered.SplineControlPointSegments)
				if ! {
					continue
				}
				,  := basegraph.TryGet(
					&.Properties, layered.SplineCompactionSegments)
				var  *verticalSegment
				if  && len() == len() {
					for  := range  {
						 := &[]
						if .Straight {
							continue
						}
						 := []
						 := make([]*geometry.Point, 0, len())
						for  := range  {
							 = append(, &[])
						}
						 := &verticalSegment{
							edges:                 []layered.LEdgeID{.Edge},
							sourcePorts:           []layered.LPortID{.SourcePort},
							targetPorts:           []layered.LPortID{.TargetPort},
							affectedControls:      ,
							affectedBoundingBoxes: []*geometry.Rectangle{&.BoundingBox},
							hitbox:                .BoundingBox,
						}
						 = append(, )
						if  != nil {
							.constraints = append(.constraints, )
						}
						 = 
					}
					continue
				}

				// Compatibility for graphs constructed directly against the
				// arena without phase-5 SplineSegment metadata.
				for  := range  {
					 := []
					if len() <= 1 {
						continue
					}
					,  := math.Inf(1), math.Inf(1)
					,  := math.Inf(-1), math.Inf(-1)
					 := make([]*geometry.Point, 0, len())
					for  := range  {
						 := &[]
						 = append(, )
						,  = math.Min(, .X), math.Min(, .Y)
						,  = math.Max(, .X), math.Max(, .Y)
					}
					 := &verticalSegment{
						edges:            []layered.LEdgeID{},
						affectedControls: ,
						hitbox: geometry.Rectangle{
							X: , Y: , Width:  - , Height:  - ,
						},
					}
					 = append(, )
					if  != nil {
						.constraints = append(.constraints, )
					}
					 = 
				}
			}
		}
	}
	return 
}

func ( *layeredCompactionTransformer) ( []*verticalSegment) {
	if len() == 0 {
		return
	}
	sort.SliceStable(, func(,  int) bool {
		 := fuzzyCompare([].hitbox.X, [].hitbox.X)
		if  == 0 {
			return [].hitbox.Y < [].hitbox.Y
		}
		return  < 0
	})
	 := [0]
	for ,  := range [1:] {
		if .intersects() {
			.join()
			continue
		}
		.segmentToNode()
		 = 
	}
	.segmentToNode()
}

func ( *layeredCompactionTransformer) ( *verticalSegment) {
	 := .graph.addNode(&compactNode{segment: , hitbox: .hitbox})
	if len(.potentialParents) > 0 {
		.potentialParents[0].group.add()
	}
	 := compactLock{}
	 := make(map[layered.LPortID]struct{})
	 := make(map[layered.LPortID]struct{})
	for ,  := range .sourcePorts {
		[] = struct{}{}
	}
	for ,  := range .targetPorts {
		[] = struct{}{}
	}
	for ,  := range .edges {
		 := .arena.Edge()
		if .Source != nil {
			[*.Source] = struct{}{}
		}
		if .Target != nil {
			[*.Target] = struct{}{}
		}
	}
	if len() < len() {
		.left = true
	} else if len() > len() {
		.right = true
	}
	.locks[] = 
	for ,  := range .joined {
		.segmentNodes[] = 
	}
	.segmentNodes[] = 
}

func absoluteCompactionPortAnchor( *layered.LGraphArena,  layered.LPortID) geometry.Point {
	 := .Port()
	return .Node(*.Node).Position.Add(.Position).Add(.Anchor)
}

type oneDimensionalCompactor struct {
	graph                *compactGraph
	transformer          *layeredCompactionTransformer
	direction            compactDirection
	quadraticConstraints bool
	lock                 func(*compactNode, compactDirection) bool
}

func newOneDimensionalCompactor(
	 *compactGraph,
	 *layeredCompactionTransformer,
) *oneDimensionalCompactor {
	 := &oneDimensionalCompactor{graph: , transformer: }
	.calculateGroupOffsets()
	for ,  := range .nodes {
		if .group == nil {
			.addGroup()
		}
		.before = .hitbox
	}
	return 
}

func ( *oneDimensionalCompactor) ( bool) {
	if .direction == compactUndefined {
		.changeDirection(compactLeft)
	}
	for ,  := range .graph.groups {
		.outDegree = .outDegreeReal
	}
	for ,  := range .graph.nodes {
		.start = math.Inf(-1)
	}
	if  {
		.networkSimplexCompact()
	} else {
		.longestPathCompact()
	}
}

func ( *oneDimensionalCompactor) ( compactDirection) {
	if  == .direction {
		return
	}
	 := .direction
	.direction = 
	switch {
	case  == compactUndefined &&  == compactLeft:
		.calculateConstraints()
	case  == compactUndefined &&  == compactRight:
		.mirrorHitboxes()
		.calculateConstraints()
	case  == compactLeft &&  == compactRight,
		 == compactRight &&  == compactLeft:
		.mirrorHitboxes()
		.reverseConstraints()
	default:
		panic("layered: unsupported one-dimensional compaction direction transition")
	}
}

func ( *oneDimensionalCompactor) () {
	for ,  := range .graph.groups {
		.reference = nil
		for ,  := range .nodes {
			.groupOffset = geometry.Point{}
			if .reference == nil || .hitbox.X < .reference.hitbox.X {
				.reference = 
			}
		}
		if .reference == nil {
			continue
		}
		for ,  := range .nodes {
			.groupOffset.X = .hitbox.X - .reference.hitbox.X
			.groupOffset.Y = .hitbox.Y - .reference.hitbox.Y
		}
	}
}

func ( *oneDimensionalCompactor) () {
	for ,  := range .graph.nodes {
		.hitbox.X = -.hitbox.X - .hitbox.Width
	}
	.calculateGroupOffsets()
}

func ( *oneDimensionalCompactor) () {
	for ,  := range .graph.nodes {
		.constraints = .constraints[:0]
	}
	for ,  := range .graph.predefined {
		if .direction == compactLeft {
			[0].constraints = append([0].constraints, [1])
		} else {
			[1].constraints = append([1].constraints, [0])
		}
	}
	if .quadraticConstraints {
		.calculateQuadraticConstraints()
	} else {
		.calculateEdgeAwareConstraints()
	}
	.calculateConstraintsForGroups()
}

func ( *oneDimensionalCompactor) () {
	for ,  := range .graph.groups {
		.outDegree, .outDegreeReal = 0, 0
	}
	for ,  := range .graph.groups {
		for ,  := range .nodes {
			for ,  := range .constraints {
				if .group !=  {
					.group.outDegree++
					.group.outDegreeReal++
				}
			}
		}
	}
}

func ( *oneDimensionalCompactor) () {
	 := make(map[*compactNode][]*compactNode, len(.graph.nodes))
	for ,  := range .graph.nodes {
		.start = math.Inf(-1)
		for ,  := range .constraints {
			[] = append([], )
		}
	}
	for ,  := range .graph.nodes {
		.constraints = []
	}
	.calculateConstraintsForGroups()
}

func ( *oneDimensionalCompactor) ( *compactNode) bool {
	return .lock != nil && .lock(, .direction)
}

func ( *oneDimensionalCompactor) ( *compactGroup) bool {
	for ,  := range .nodes {
		if .isLocked() {
			return true
		}
	}
	return false
}

func ( *oneDimensionalCompactor) () {
	 := math.Inf(1)
	for ,  := range .graph.nodes {
		 = math.Min(, .group.reference.hitbox.X+.groupOffset.X)
	}
	 := make([]*compactGroup, 0)
	for ,  := range .graph.groups {
		.start = 
		if .outDegree == 0 {
			 = append(, )
		}
	}
	for len() > 0 {
		 := [0]
		 = [1:]
		for ,  := range .nodes {
			 := .start + .groupOffset.X
			if !.groupIsLocked() || .hitbox.X <  {
				.start = 
			} else {
				.start = .hitbox.X
			}
		}
		for ,  := range .nodes {
			for ,  := range .constraints {
				 := .horizontalSpacing(, )
				.group.start = math.Max(.group.start,
					.start+.hitbox.Width+-.groupOffset.X)
				if .isLocked() {
					.group.start = math.Max(.group.start,
						.hitbox.X-.groupOffset.X)
				}
				.group.outDegree--
				if .group.outDegree == 0 {
					 = append(, .group)
				}
			}
		}
	}
	for ,  := range .graph.nodes {
		.hitbox.X = .start
	}
}

func ( *oneDimensionalCompactor) (,  *compactNode) float64 {
	if verticalSegmentsShareEdge(, ) {
		return 0
	}
	,  := .compactionNodeType()
	,  := .compactionNodeType()
	if  ||  {
		return 0
	}
	return layered.HorizontalSpacingByType(
		.transformer.arena, .transformer.graphID, , )
}

func ( *oneDimensionalCompactor) (,  *compactNode) float64 {
	if verticalSegmentsShareEdge(, ) {
		return 1
	}
	,  := .compactionNodeType()
	,  := .compactionNodeType()
	return layered.VerticalSpacingByType(
		.transformer.arena, .transformer.graphID, , )
}

func ( *oneDimensionalCompactor) ( *compactNode) (layered.NodeType, bool) {
	if .node == nil {
		return layered.LongEdgeNode, false
	}
	 := .transformer.arena.Node(*.node).Type
	return ,  == layered.ExternalPortNode
}

func verticalSegmentsShareEdge(,  *compactNode) bool {
	if .segment == nil || .segment == nil {
		return false
	}
	 := make(map[layered.LEdgeID]struct{}, len(.segment.edges))
	for ,  := range .segment.edges {
		[] = struct{}{}
	}
	for ,  := range .segment.edges {
		if ,  := [];  {
			return true
		}
	}
	return false
}

func ( *oneDimensionalCompactor) () {
	// ELK's quadratic implementation clears the predefined constraints that
	// the surrounding compactor installed immediately beforehand.
	for ,  := range .graph.nodes {
		.constraints = .constraints[:0]
	}
	for ,  := range .graph.nodes {
		for ,  := range .graph.nodes {
			if  ==  || .group == .group {
				continue
			}
			 := .verticalSpacing(, )
			if (.hitbox.X > .hitbox.X ||
				(.hitbox.X == .hitbox.X && .hitbox.Width < .hitbox.Width)) &&
				fuzzyGreater(.hitbox.MaxY()+, .hitbox.Y) &&
				fuzzyLess(.hitbox.Y, .hitbox.MaxY()+) {
				.constraints = append(.constraints, )
			}
		}
	}
}

func ( *oneDimensionalCompactor) () {
	switch .transformer.edgeRouting {
	case layered.EdgeRoutingOrthogonal:
		.calculateOrthogonalConstraints()
	case layered.EdgeRoutingSplines:
		.calculateSplineConstraints()
	default:
		panic("layered: edge-aware constraints require orthogonal or spline routing")
	}
}

func ( *oneDimensionalCompactor) () {
	.scanline(func( *compactNode) bool { return .segment != nil })
	 := .minimumExpansionSpacing()
	for ,  := range .graph.nodes {
		if .node != nil {
			.alterHitbox(, , 1)
		}
	}
	.scanline(func(*compactNode) bool { return true })
	for ,  := range .graph.nodes {
		if .node != nil {
			.alterHitbox(, , -1)
		}
	}
}

func ( *oneDimensionalCompactor) () {
	 := basegraph.Get(
		&.transformer.arena.Graph(.transformer.graphID).Properties,
		layered.SpacingEdgeEdge,
	)
	 := math.Max(0, /2-compactionSpacingEpsilon)
	for ,  := range .graph.nodes {
		if .segment != nil {
			.alterHitbox(, , 1)
		}
	}
	.scanline(func( *compactNode) bool { return .segment != nil })
	for ,  := range .graph.nodes {
		if .segment != nil {
			.alterHitbox(, , -1)
		}
	}

	for ,  := range .graph.nodes {
		if .node == nil {
			continue
		}
		 := layered.IndividualOrDefault(
			.transformer.arena, *.node, &layered.SpacingEdgeEdge)
		.alterHitbox(, math.Max(0, /2-compactionSpacingEpsilon), 1)
	}
	.scanline(func( *compactNode) bool { return .node != nil })
	for ,  := range .graph.nodes {
		if .node == nil {
			continue
		}
		 := layered.IndividualOrDefault(
			.transformer.arena, *.node, &layered.SpacingEdgeEdge)
		.alterHitbox(, math.Max(0, /2-compactionSpacingEpsilon), -1)
	}

	 := .minimumExpansionSpacing()
	for ,  := range .graph.groups {
		.alterGroupedHitbox(, , 1)
	}
	.scanline(func(*compactNode) bool { return true })
	for ,  := range .graph.groups {
		.alterGroupedHitbox(, , -1)
	}
}

func ( *oneDimensionalCompactor) () float64 {
	 := basegraph.Get(
		&.transformer.arena.Graph(.transformer.graphID).Properties,
		layered.SpacingEdgeEdge,
	)
	 := math.Inf(1)
	for ,  := range .graph.nodes {
		if .node != nil && .transformer.arena.Node(*.node).Type == layered.ExternalPortNode {
			continue
		}
		if .segment != nil {
			 = math.Min(, math.Max(0, /2-compactionSpacingEpsilon))
		} else if .node != nil {
			 := layered.IndividualOrDefault(
				.transformer.arena, *.node, &layered.SpacingNodeNode)
			 = math.Min(, math.Max(0, /2-compactionSpacingEpsilon))
		}
	}
	if math.IsInf(, 1) {
		return 0
	}
	return 
}

func ( *oneDimensionalCompactor) (
	 *compactGroup,
	,  float64,
) {
	 := .master
	if  == nil && len(.nodes) > 0 {
		 = .nodes[0]
	}
	if  == nil {
		return
	}
	.alterHitbox(, , )
	if len(.nodes) == 1 {
		return
	}
	 :=  * 
	for ,  := range .nodes {
		if  ==  || .segment == nil {
			continue
		}
		if .segment.ignoreUp {
			.hitbox.Y +=  + compactionSmallEpsilon
			.hitbox.Height -=  + compactionSmallEpsilon
		} else if .segment.ignoreDown {
			.hitbox.Height -=  + compactionSmallEpsilon
		}
	}
}

func ( *oneDimensionalCompactor) (
	 *compactNode,
	,  float64,
) {
	 :=  * 
	if .segment != nil {
		if !.segment.ignoreUp {
			.hitbox.Y -=  + compactionSmallEpsilon
			.hitbox.Height +=  + compactionSmallEpsilon
		} else if !.segment.ignoreDown {
			.hitbox.Height +=  + compactionSmallEpsilon
		}
	} else if .node != nil {
		.hitbox.Y -= 
		.hitbox.Height += 2 * 
	}
}

type compactTimestamp struct {
	node  *compactNode
	low   bool
	order int
}

func ( compactTimestamp) () float64 {
	if .low {
		return .node.hitbox.Y
	}
	return .node.hitbox.MaxY()
}

func ( *oneDimensionalCompactor) ( func(*compactNode) bool) {
	 := make([]compactTimestamp, 0, len(.graph.nodes)*2)
	 := 0
	for ,  := range .graph.nodes {
		if () {
			 = append(,
				compactTimestamp{node: , low: true, order: },
				compactTimestamp{node: , low: false, order:  + 1})
			 += 2
		}
	}
	sort.SliceStable(, func(,  int) bool {
		,  := [].coordinate(), [].coordinate()
		if  !=  {
			return  < 
		}
		if [].low != [].low {
			// High (deletion) timestamps precede low (insertion) timestamps.
			return ![].low
		}
		return [].order < [].order
	})

	 := make([]*compactNode, 0)
	 := make(map[*compactNode]*compactNode)
	 := func( *compactNode) float64 { return .hitbox.X + .hitbox.Width/2 }
	 := func( *compactNode) int {
		for ,  := range  {
			if  ==  {
				return 
			}
		}
		return -1
	}
	for ,  := range  {
		if .low {
			 := sort.Search(len(), func( int) bool {
				return ([]) >= (.node)
			})
			if  < len() && ([]) == (.node) {
				panic(fmt.Sprintf("layered: invalid hitboxes for scanline constraint calculation: center %v, first %+v, second %+v",
					(.node), [].hitbox, .node.hitbox))
			}
			 = append(, nil)
			copy([+1:], [:])
			[] = .node
			if  > 0 {
				[.node] = [-1]
			}
			if +1 < len() {
				[[+1]] = .node
			}
			continue
		}

		 := (.node)
		if  < 0 {
			continue
		}
		if  > 0 {
			 := [-1]
			if [.node] ==  && .group != .node.group {
				.constraints = append(.constraints, .node)
			}
		}
		if +1 < len() {
			 := [+1]
			if [] == .node && .group != .node.group {
				.node.constraints = append(.node.constraints, )
			}
		}
		copy([:], [+1:])
		[len()-1] = nil
		 = [:len()-1]
	}
}

func ( *oneDimensionalCompactor) () {
	 := networksimplex.NewGraph()
	 := make([]networksimplex.NodeID, len(.graph.groups))
	for ,  := range .graph.groups {
		.id = 
		 := .AddNode()
		.Node().ID = 
		.Node().Origin = 
		[] = 
	}

	for ,  := range .graph.nodes {
		for ,  := range .constraints {
			if .group == .group {
				continue
			}
			 := .horizontalSpacing(, )
			 := int(math.Ceil(.groupOffset.X + .hitbox.Width +  - .groupOffset.X))
			 = max(0, )
			if !verticalSegmentsShareEdge(, ) {
				 := 1.0
				if .segment != nil && .node != nil ||
					.segment != nil && .node != nil {
					 = 2
				}
				.AddEdge([.group.id], [.group.id], , )
				continue
			}

			 := .AddNode()
			 := int(math.Ceil(.groupOffset.X - .groupOffset.X))
			 := float64() - (.groupOffset.X - .groupOffset.X)
			 := 
			 := .segment.port
			if  == nil {
				 = .segment.port
				 = -
				 = 
			}
			if  != nil {
				.groupOffset.X -= 
				.transformer.arena.Port(*).Position.X -= 
			}
			.AddEdge(, [.group.id], 1, max(0, ))
			.AddEdge(, [.group.id], 1, max(0, -))
		}
	}

	 := make(map[layered.LEdgeID][]*compactNode)
	for ,  := range .graph.nodes {
		if .segment == nil {
			continue
		}
		 := make(map[layered.LEdgeID]struct{})
		for ,  := range .segment.edges {
			if ,  := [];  {
				continue
			}
			[] = struct{}{}
			[] = append([], )
		}
	}
	for ,  := range .graph.nodes {
		if .node == nil {
			continue
		}
		for ,  := range .transformer.arena.NodeOutgoingEdges(*.node) {
			if .transformer.arena.EdgeIsSelfLoop() {
				continue
			}
			 := .transformer.arena.Edge()
			,  := .transformer.arena.Port(*.Source), .transformer.arena.Port(*.Target)
			if isNorthSouth(.Side) && isNorthSouth(.Side) {
				continue
			}
			 := .transformer.nodes[.transformer.arena.EdgeTargetNode()]
			if  == nil {
				continue
			}
			.AddEdge([.group.id], [.group.id], 100, 0)

			if .Side == layered.WestSide && len(.OutgoingEdges) > 0 {
				for ,  := range [] {
					if .hitbox.X < .hitbox.X && .group != .group {
						.AddEdge([.group.id], [.group.id], 100, 1)
					}
				}
			}
			if .Side == layered.EastSide && len(.IncomingEdges) > 0 {
				for ,  := range [] {
					if .hitbox.X > .hitbox.X && .group != .group {
						.AddEdge([.group.id], [.group.id], 100, 1)
					}
				}
			}
		}
	}

	 := make([]networksimplex.NodeID, 0)
	for ,  := range .Nodes {
		if len(.Node().IncomingEdges) == 0 {
			 = append(, )
		}
	}
	if len() > 1 {
		 := .AddNode()
		for ,  := range  {
			.AddEdge(, , 0, 1)
		}
	}
	networksimplex.ForGraph().Execute()
	for ,  := range .graph.nodes {
		.hitbox.X = float64(.Node([.group.id]).Layer) + .groupOffset.X
	}
}

func isNorthSouth( layered.PortSide) bool {
	return  == layered.NorthSide ||  == layered.SouthSide
}

func ( *layeredCompactionTransformer) () {
	for ,  := range .graph.nodes {
		if .node != nil {
			 := .arena.Node(*.node)
			.Position.X = .hitbox.X + .Margin.Left
		}
	}
	for ,  := range .comments {
		.arena.Node(.comment).Position =
			.arena.Node(.other).Position.Add(.offset)
	}
	for ,  := range .graph.nodes {
		if .segment == nil {
			continue
		}
		 := .hitbox.X - .before.X
		for ,  := range .segment.affectedBends {
			.X += 
		}
		for ,  := range .segment.affectedControls {
			.X += 
		}
		for ,  := range .segment.affectedBoundingBoxes {
			.X += 
		}
		for ,  := range .segment.affectedJunctions {
			.X += 
		}
	}

	if .edgeRouting == layered.EdgeRoutingSplines {
		for ,  := range .nodes {
			 := .hitbox.X - .before.X
			for ,  := range .arena.NodeOutgoingEdges() {
				if .arena.EdgeIsSelfLoop() {
					for  := range .arena.Edge().BendPoints {
						.arena.Edge().BendPoints[].X += 
					}
				}
			}
		}
		.adjustStraightSplineControls()
	}

	 := geometry.Point{X: math.Inf(1), Y: math.Inf(1)}
	 := geometry.Point{X: math.Inf(-1), Y: math.Inf(-1)}
	for ,  := range .graph.nodes {
		.X, .Y = math.Min(.X, .hitbox.X), math.Min(.Y, .hitbox.Y)
		.X, .Y = math.Max(.X, .hitbox.MaxX()), math.Max(.Y, .hitbox.MaxY())
	}
	if len(.graph.nodes) == 0 {
		,  = geometry.Point{}, geometry.Point{}
	}
	 := .arena.Graph(.graphID)
	.Offset = geometry.Point{X: -.X, Y: -.Y}
	.Size = .Sub()

	for ,  := range .graph.nodes {
		if .node == nil {
			continue
		}
		 := .arena.Node(*.node)
		if .Type != layered.ExternalPortNode {
			continue
		}
		switch basegraph.Get(&.Properties, layered.ExternalPortSide) {
		case layered.WestSide:
			.Position.X = .X
		case layered.EastSide:
			.Position.X = .X - (.Size.X + .Margin.Right)
		case layered.NorthSide:
			.Position.Y = .Y
		case layered.SouthSide:
			.Position.Y = .Y - (.Size.Y + .Margin.Bottom)
		}
	}
}

func ( *layeredCompactionTransformer) () {
	for ,  := range .arena.Graph(.graphID).Layers {
		for ,  := range .arena.Layer().Nodes {
			for ,  := range .arena.NodeOutgoingEdges() {
				 := .arena.Edge()
				,  := basegraph.TryGet(&.Properties, layered.SplineControlPointSegments)
				if ! || len() == 0 {
					continue
				}
				,  := basegraph.TryGet(
					&.Properties, layered.SplineCompactionSegments)
				if  && len() == len() {
					.adjustStraightSplineSegmentBoxes(
						, , )
					continue
				}

				// Compatibility for directly assembled test arenas that only
				// provide the old control-point representation.
				for  := 0;  < len(); {
					if len([]) != 1 {
						++
						continue
					}
					 := 
					for +1 < len() && len([+1]) == 1 {
						++
					}
					 := absoluteCompactionPortAnchor(.arena, *.Source).X
					if  > 0 && len([-1]) > 0 {
						 = [-1][len([-1])-1].X
					}
					 := absoluteCompactionPortAnchor(.arena, *.Target).X
					if +1 < len() && len([+1]) > 0 {
						 = [+1][0].X
					}
					 := ( - ) / float64(max(2, -+2))
					for  := ;  <= ; ++ {
						[][0].X =  + *float64(-+1)
					}
					 =  + 1
				}
			}
		}
	}
}

// adjustStraightSplineSegmentBoxes is the source-shaped implementation of
// LGraphToCGraphTransformer.adjustSplineControlPoints(). Non-straight segment
// boxes were moved as compaction nodes; the straight boxes between them are
// redistributed equidistantly afterwards.
func ( *layeredCompactionTransformer) (
	 layered.LEdgeID,
	 []geometry.Chain,
	 []layered.SplineCompactionSegment,
) {
	if len() == 0 {
		return
	}
	if len() == 1 {
		.adjustSplineControlsBetween(
			, , , 0, 0, 1, 0)
		return
	}

	 := 0
	for  := 1;  < len(); {
		if  == 0 || ![].Straight {
			 := 
			for  < len()-1 && [].Straight {
				++
			}
			.adjustSplineControlsBetween(
				, , , , , , )
			 =  + 1
			 = 
		}
	}
}

func ( *layeredCompactionTransformer) (
	 layered.LEdgeID,
	 []geometry.Chain,
	 []layered.SplineCompactionSegment,
	, , ,  int,
) {
	 := [].BoundingBox.MaxX()
	 := 
	if  == 0 && [].Straight {
		 := .nodes[.arena.EdgeSourceNode()]
		if  != nil {
			 = .hitbox.MaxX()
		}
		--
	}

	 := [].BoundingBox.X
	 := 
	if  == len()-1 && [].Straight {
		 := .nodes[.arena.EdgeTargetNode()]
		if  != nil {
			 = .hitbox.X
		}
		++
	}

	 := ( - ) / float64(max(2, -))
	 :=  + 
	for  := ;  < ; ++ {
		 := [].BoundingBox.X +
			[].BoundingBox.Width/2
		[].BoundingBox.X =  -
			[].BoundingBox.Width/2
		 :=  - 
		for  := range [] {
			[][].X += 
		}
		 += 
	}
}

func fuzzyCompare(,  float64) int {
	if math.Abs(-) <= compactionFuzzyTolerance ||  ==  {
		return 0
	}
	if  <  {
		return -1
	}
	return 1
}

func fuzzyEqual(,  float64) bool   { return fuzzyCompare(, ) == 0 }
func fuzzyLess(,  float64) bool    { return fuzzyCompare(, ) < 0 }
func fuzzyGreater(,  float64) bool { return fuzzyCompare(, ) > 0 }