package hierarchy

import (
	
	
	
	

	
	
	
	
)

// A compound candidate reuses already laid-out interiors as rigid blocks. The
// first implementation is deliberately bounded to one connected outer graph;
// separate outer components must not be expanded into one another before routing.
const maxCompoundBlocks = 64
const maxCompoundInterfaces = 256

type compoundBlock struct {
	original *layoutgraph.Node
	proxy    *layoutgraph.Node
	members  []*layoutgraph.Node
}

type compoundInterface struct {
	from, to *compoundBlock
	// Coordinates relative to each block retain the ordering of real descendant
	// endpoints. They are projected to the appropriate boundary after placement.
	fromOffset, toOffset geo.Point
}

// PlaceCompound lays out the outer flow of detailed containers after their
// interiors have been placed and rescaled, but before edge routing. It preserves
// every interior coordinate relative to its container, including local directions
// and specialized inner layouts. The caller compares this complete candidate
// against ordinary placement; this stage is not an unconditional improvement.
func ( context.Context,  *layoutgraph.Graph,  *rand.Rand) ( bool,  error) {
	if  := layoutgraph.Validate(, "PlaceCompound", );  != nil {
		return false, 
	}
	if len(.Containers[nil]) < 3 || len(.Containers[nil]) > maxCompoundBlocks {
		return false, nil
	}
	, ,  := layoutgraph.EnsureTransactionWorkGuard(, "PlaceCompoundTransactions")
	if  != nil {
		return false, 
	}
	 := layoutgraph.NewGraph()
	.Directions[nil] = .Direction(nil)
	 := make([]*compoundBlock, 0, len(.Containers[nil]))
	 := make(map[*layoutgraph.Node]*compoundBlock)
	for ,  := range .Containers[nil] {
		if  := .Step();  != nil {
			return false, 
		}
		 := layoutgraph.NewNode(.ID, .Width, .Height)
		.TopLeft = .TopLeft.Copy()
		.AddNewNodeToContainer(nil, )
		 := &compoundBlock{original: , proxy: }
		 = append(, )
		[] = 
	}
	 := make(map[*layoutgraph.Node]*compoundBlock, len(.Nodes))
	for ,  := range .Nodes {
		if  := .Step();  != nil {
			return false, 
		}
		// Absolute coordinates and active grouping vessels are not rigid-block input.
		if .FixedTopLeft != nil || .IsSequenceVessel() || .IsClusterVessel() {
			return false, nil
		}
		 := 
		for .Container != nil {
			if  := .Step();  != nil {
				return false, 
			}
			 = .Container
		}
		 := []
		if  == nil {
			return false, nil
		}
		.members = append(.members, )
		[] = 
	}
	// Trees must already be restored into the ordinary node collection. A tree
	// sentinel can be an authored node; it is safe to move once all members exist.
	for  := range .NodeToTree {
		if  := .Step();  != nil {
			return false, 
		}
		if [] == nil {
			return false, nil
		}
	}
	 := make([]compoundInterface, 0)
	 := false
	for ,  := range .Edges {
		if  := .Step();  != nil {
			return false, 
		}
		,  := [.From], [.To]
		if  == nil ||  == nil {
			return false, nil
		}
		if  ==  {
			 =  || (.original.IsContainer() && .From != .To)
			continue
		}
		if len() == maxCompoundInterfaces {
			return false, nil
		}
		 := .Connect(.proxy, .proxy)
		.ID = .ID
		.SourceArrowhead = .SourceArrowhead
		.TargetArrowhead = .TargetArrowhead
		if .Label != nil {
			 := *.Label
			.Label = &
		}
		 = append(, compoundInterface{
			from: , to: ,
			fromOffset: compoundEndpointOffset(.From, .original, .FromTableColumnIndex),
			toOffset:   compoundEndpointOffset(.To, .original, .ToTableColumnIndex),
		})
	}
	if ! || !compoundConnected(, ) {
		return false, nil
	}
	// The compactness heuristics for ordinary nodes do not decide whether
	// rearranging these opaque blocks helps the completed drawing. Rank only
	// this isolated proxy, then retain the compound proposal's original directed
	// backbone requirement. The caller compares its finished route geometry.
	,  := build(, , true, Candidates(), nil)
	if  != nil {
		return false, 
	}
	if  == nil {
		return false, nil
	}
	,  := countEdgeDirection(, )
	if .LevelCount < 2 ||  == 0 || float64() < 1.5*float64() {
		return false, nil
	}
	for ,  := range .Nodes {
		if  := .Step();  != nil {
			return false, 
		}
		.Hierarchy = 
	}
	if  := Place(, , nil, );  != nil {
		return false, 
	}
	if  := orderCompoundInterfaces(, , .Direction(nil).IsHorizontal(), );  != nil {
		return false, 
	}
	,  := layoutgraph.Nodes(.Nodes).BoundingBox()
	if .X-.X > limits.MaxGraphSize || .Y-.Y > limits.MaxGraphSize {
		return false, nil
	}
	// All planning is isolated. Snapshot only when there is an applicable plan, and
	// keep mutations atomic even if cancellation arrives during rigid translation.
	 := layoutgraph.NewGraphStateSnapshot(layoutgraph.GraphStateSnapshotOptions{CaptureTopology: true, CaptureEdgeRoutes: true})
	if  := .UpdateWithWorkGuard(, );  != nil {
		return false, 
	}
	 := &layoutgraph.Transaction{Graph: , PriorGraphState: }
	 := false
	defer func() {
		if ! {
			.Rollback()
		}
	}()
	,  := layoutgraph.Nodes(.Containers[nil]).BoundingBox()
	 := layoutgraph.NewHierarchy()
	.LevelCount = .Nodes[0].Hierarchy.LevelCount
	for ,  := range  {
		if  := .Step();  != nil {
			return false, 
		}
		 := .proxy.TopLeft.X - .X + .X - .original.TopLeft.X
		 := .proxy.TopLeft.Y - .Y + .Y - .original.TopLeft.Y
		for ,  := range .members {
			if  := .Step();  != nil {
				return false, 
			}
			.Translate(, )
		}
		// Only the opaque block belongs to the outer hierarchy. Its descendants
		// retain their own hierarchy and rank, rather than being flattened into one row.
		if  := .original.Hierarchy;  != nil {
			delete(.Levels(), .original)
		}
		.original.Hierarchy = 
		.Levels()[.original] = .proxy.HierarchyLevel()
	}
	if  := .Finish();  != nil {
		return false, 
	}
	 = true
	return true, nil
}

func compoundEndpointOffset(,  *layoutgraph.Node,  *int) geo.Point {
	 := .Center()
	if  != nil {
		if ,  := nodeshape.TableColumnPortValue(.Shape, geo.Right, *);  {
			 = &
		}
	}
	return geo.Point{X: math.Max(0, math.Min(.Width, .X-.TopLeft.X)), Y: math.Max(0, math.Min(.Height, .Y-.TopLeft.Y))}
}

func compoundConnected( []*compoundBlock,  []compoundInterface) bool {
	 := make(map[*compoundBlock][]*compoundBlock, len())
	for ,  := range  {
		[.from] = append([.from], .to)
		[.to] = append([.to], .from)
	}
	 := map[*compoundBlock]bool{[0]: true}
	 := []*compoundBlock{[0]}
	for len() > 0 {
		 := [0]
		 = [1:]
		for ,  := range [] {
			if ![] {
				[] = true
				 = append(, )
			}
		}
	}
	return len() == len()
}

// orderCompoundInterfaces refines the center-based layered ordering using actual
// boundary offsets. At most two adjacent-swap sweeps are attempted. Blocks keep
// their rank and size, so accepted swaps cannot introduce node overlap.
func orderCompoundInterfaces( []*compoundBlock,  []compoundInterface,  bool,  *limits.WorkGuard) error {
	 := make(map[int][]*compoundBlock)
	for ,  := range  {
		[.proxy.HierarchyLevel()] = append([.proxy.HierarchyLevel()], )
	}
	 := func( *compoundBlock) (*float64, float64) {
		if  {
			return &.proxy.TopLeft.Y, .proxy.Height
		}
		return &.proxy.TopLeft.X, .proxy.Width
	}
	for  := 0;  < [0].proxy.Hierarchy.LevelCount; ++ {
		 := []
		slices.SortFunc(, func(,  *compoundBlock) int {
			,  := ()
			,  := ()
			if * < * {
				return -1
			}
			if * > * {
				return 1
			}
			return 0
		})
		[] = 
	}
	,  := compoundInterfaceScore(, , )
	if  != nil {
		return 
	}
	for  := 0;  < 2; ++ {
		 := false
		for  := 0;  < [0].proxy.Hierarchy.LevelCount; ++ {
			 := []
			for  := 0; +1 < len(); ++ {
				if  := .Step();  != nil {
					return 
				}
				,  := [], [+1]
				,  := ()
				,  := ()
				,  := *, *
				*, * = +-, 
				,  := compoundInterfaceScore(, , )
				if  != nil {
					return 
				}
				if .crossings < .crossings || (.crossings == .crossings && .span < .span) {
					 = 
					[], [+1] = , 
					 = true
				} else {
					*, * = , 
				}
			}
		}
		if ! {
			break
		}
	}
	return .Finish()
}

type compoundScore struct {
	crossings int
	span      float64
}
type compoundSegment struct{ a, b geo.Point }

func compoundInterfaceScore( []compoundInterface,  bool,  *limits.WorkGuard) (compoundScore, error) {
	 := compoundScore{}
	 := make([]compoundSegment, len())
	for ,  := range  {
		if  := .Step();  != nil {
			return , 
		}
		,  := .from.proxy, .to.proxy
		 := geo.Point{X: .TopLeft.X + .fromOffset.X, Y: .TopLeft.Y + .fromOffset.Y}
		 := geo.Point{X: .TopLeft.X + .toOffset.X, Y: .TopLeft.Y + .toOffset.Y}
		if  {
			if .Center().X < .Center().X {
				.X = .TopLeft.X + .Width
				.X = .TopLeft.X
			} else {
				.X = .TopLeft.X
				.X = .TopLeft.X + .Width
			}
			.span += math.Abs(.Y - .Y)
		} else {
			if .Center().Y < .Center().Y {
				.Y = .TopLeft.Y + .Height
				.Y = .TopLeft.Y
			} else {
				.Y = .TopLeft.Y
				.Y = .TopLeft.Y + .Height
			}
			.span += math.Abs(.X - .X)
		}
		[] = compoundSegment{, }
	}
	 := func(, ,  geo.Point) float64 { return (.X-.X)*(.Y-.Y) - (.Y-.Y)*(.X-.X) }
	for ,  := range  {
		for ,  := range [+1:] {
			if  := .Step();  != nil {
				return , 
			}
			if (.a, .b, .a)*(.a, .b, .b) < 0 && (.a, .b, .a)*(.a, .b, .b) < 0 {
				.crossings++
			}
		}
	}
	return , nil
}