package packing

import (
	
	
	
	
	

	
	
	
)

type exactSliceSnapshot[ ~[],  any] struct {
	original 
	backing  []
}

func captureExactSlice[ ~[],  any]( ) exactSliceSnapshot[, ] {
	if  == nil {
		return exactSliceSnapshot[, ]{}
	}
	 := [:cap()]
	 := make([], len())
	copy(, )
	return exactSliceSnapshot[, ]{original: , backing: }
}

func ( exactSliceSnapshot[, ]) ()  {
	if .original == nil {
		return nil
	}
	copy(.original[:cap(.original)], .backing)
	return .original
}

type combineEdgeSnapshot struct {
	value                layoutgraph.Edge
	d2ID                 pointerSnapshot[string]
	points               exactSliceSnapshot[[]*geo.Point, *geo.Point]
	pointValues          []pointerSnapshot[geo.Point]
	label                pointerSnapshot[layoutgraph.Label]
	sourceArrowheadLabel pointerSnapshot[layoutgraph.Label]
	targetArrowheadLabel pointerSnapshot[layoutgraph.Label]
	fromTableColumnIndex pointerSnapshot[int]
	toTableColumnIndex   pointerSnapshot[int]
}

func captureCombineEdge( *layoutgraph.Edge) combineEdgeSnapshot {
	 := .Points[:cap(.Points)]
	 := make([]pointerSnapshot[geo.Point], len())
	for ,  := range  {
		[] = snapshotPointer()
	}
	return combineEdgeSnapshot{
		value:                *,
		d2ID:                 snapshotPointer(.D2ID),
		points:               captureExactSlice(.Points),
		pointValues:          ,
		label:                snapshotPointer(.Label),
		sourceArrowheadLabel: snapshotPointer(.SourceArrowheadLabel),
		targetArrowheadLabel: snapshotPointer(.TargetArrowheadLabel),
		fromTableColumnIndex: snapshotPointer(.FromTableColumnIndex),
		toTableColumnIndex:   snapshotPointer(.ToTableColumnIndex),
	}
}

func ( combineEdgeSnapshot) ( *layoutgraph.Edge) {
	.d2ID.restore()
	.label.restore()
	.sourceArrowheadLabel.restore()
	.targetArrowheadLabel.restore()
	.fromTableColumnIndex.restore()
	.toTableColumnIndex.restore()
	for ,  := range .pointValues {
		.restore()
	}
	 := .points.restore()
	* = .value
	.D2ID = .d2ID.pointer
	.Points = 
	.Label = .label.pointer
	.SourceArrowheadLabel = .sourceArrowheadLabel.pointer
	.TargetArrowheadLabel = .targetArrowheadLabel.pointer
	.FromTableColumnIndex = .fromTableColumnIndex.pointer
	.ToTableColumnIndex = .toTableColumnIndex.pointer
}

// CombineSubgraphs arranges laid-out subgraphs and returns a combined graph
// view that shares the master graph's topology.
func ( context.Context,  *layoutgraph.Graph,  []*layoutgraph.Graph,  []geo.Box) ( *layoutgraph.Graph,  error) {
	if  == nil {
		return nil, fmt.Errorf("TALA CombineSubgraphs requires a master graph")
	}
	if  := layoutgraph.Validate(, "CombineSubgraphs", );  != nil {
		return nil, 
	}
	if len() > limits.MaxEngineNodes {
		return nil, fmt.Errorf("TALA CombineSubgraphs subgraph count %d exceeds limit %d", len(), limits.MaxEngineNodes)
	}
	type  struct {
		, , ,  uintptr
		, , ,    uintptr
	}
	 := func( *layoutgraph.Graph)  {
		return {
			: reflect.ValueOf(.Containers).Pointer(),
			:   reflect.ValueOf(.Clusters).Pointer(),
			:      reflect.ValueOf(.Trees).Pointer(),
			: reflect.ValueOf(.NodeToTree).Pointer(),
			:       reflect.ValueOf(.Hubs).Pointer(),
			:  reflect.ValueOf(.Sequences).Pointer(),
			: reflect.ValueOf(.Directions).Pointer(),
			:   reflect.ValueOf(.CommonUncleSiblings).Pointer(),
		}
	}
	// Identical map identities mean identical graph-owned topology, so that
	// expensive portion only needs one full preflight. Node-owned topology is
	// deliberately validated for every graph below as one distinct-record union.
	 := map[]struct{}{
		(): {},
	}
	 := make([]*layoutgraph.Graph, 1, len()+1)
	[0] = 
	for ,  := range  {
		if  == nil {
			return nil, fmt.Errorf("TALA CombineSubgraphs received a nil subgraph")
		}
		 := ()
		if ,  := []; ! {
			if  := layoutgraph.Validate(, "CombineSubgraphs", );  != nil {
				return nil, 
			}
			[] = struct{}{}
		}
		 = append(, )
	}
	if  := layoutgraph.ValidateSubgraphCombination(, );  != nil {
		return nil, 
	}

	,  := limits.NewWorkGuard(, "CombineSubgraphs", limits.MaxEngineWorkUnits)
	if  != nil {
		return nil, 
	}
	 := make([]*layoutgraph.Node, 0, len(.Nodes))
	 := make(map[*layoutgraph.Node]struct{}, len(.Nodes))
	 := make(map[*layoutgraph.Edge]combineEdgeSnapshot, len(.Edges))
	var  int64
	 := func( *layoutgraph.Graph) error {
		for ,  := range .Nodes {
			if  := .Step();  != nil {
				return 
			}
			if  == nil {
				return fmt.Errorf("TALA CombineSubgraphs contains a nil node")
			}
			if ,  := []; ! {
				[] = struct{}{}
				if len() > limits.MaxEngineNodes {
					return fmt.Errorf("TALA CombineSubgraphs unique node count exceeds limit %d", limits.MaxEngineNodes)
				}
				 = append(, )
			}
		}
		for ,  := range .Edges {
			if  := .Step();  != nil {
				return 
			}
			if  == nil {
				return fmt.Errorf("TALA CombineSubgraphs contains a nil edge")
			}
			if .From == nil || .To == nil {
				return fmt.Errorf("TALA CombineSubgraphs edge %d has missing endpoints", .ID)
			}
			if ,  := []; ! {
				if len() >= limits.MaxEngineEdges {
					return fmt.Errorf("TALA CombineSubgraphs unique edge count exceeds limit %d", limits.MaxEngineEdges)
				}
				 := int64(cap(.Points))
				if  > layoutgraph.MaxRoutePoints- {
					return fmt.Errorf("TALA CombineSubgraphs route point count exceeds limit %d", layoutgraph.MaxRoutePoints)
				}
				 += 
				for ,  := range .Points {
					if  := .Step();  != nil {
						return 
					}
					if  == nil {
						return fmt.Errorf("TALA CombineSubgraphs edge %d contains a nil route point", .ID)
					}
				}
				[] = captureCombineEdge()
			}
		}
		return nil
	}
	if  := ();  != nil {
		return nil, 
	}
	for ,  := range  {
		if  := ();  != nil {
			return nil, 
		}
	}
	,  := snapshotCombineNodePositions(, )
	if  != nil {
		return nil, 
	}
	 := make(map[*layoutgraph.Node]*layoutgraph.Graph, len())
	for ,  := range  {
		[.node] = .node.Graph
	}
	 := false
	defer func() {
		if  {
			return
		}
		restoreCombineNodePositions()
		for ,  := range  {
			.Graph = 
		}
		for ,  := range  {
			.restore()
		}
	}()

	 := layoutgraph.NewGraph()
	.CopyEntitiesFrom()
	if len() == 0 {
		 = true
		return , nil
	}

	 := geo.NewPoint(math.Inf(-1), math.Inf(-1))
	 := []*geo.Point{}

	// first subgraph (contains all fixed nodes) is always placed at 0,0
	if  := [0]; .HasFixedNode() {
		 = [1:]
		,  := .BoundingBox()

		for ,  := range .Nodes {
			if  := .Step();  != nil {
				return nil, 
			}
			.AddNodeUnchecked()
			for ,  := range .AllDescendantNodes(, true) {
				if  := .Step();  != nil {
					return nil, 
				}
				.AddNodeUnchecked()
			}
		}
		for ,  := range .Edges {
			if  := .Step();  != nil {
				return nil, 
			}
			.AddEdge()
		}

		.X = math.Max(.X, .X)
		.Y = math.Max(.Y, .Y)

		// Add this graph's new candidate points (at 1,2,3 with and without subgraphPadding).
		//  ┌───┐ 1
		//  │ g │
		//  └───┘ 2
		//  3
		 = append(,
			geo.NewPoint(.X, 0),
			geo.NewPoint(.X, .Y),
			geo.NewPoint(0, .Y),
			geo.NewPoint(.X+subgraphPadding, 0),
			geo.NewPoint(.X+subgraphPadding, .Y),
			geo.NewPoint(0, .Y+subgraphPadding),
		)
	}

	 := make([]*layoutgraph.Graph, len())
	copy(, )
	sort.Slice(, func(,  int) bool {
		return [].Area() > [].Area()
	})
	if  := .Finish();  != nil {
		return nil, 
	}

	for ,  := range  {
		if  := .Step();  != nil {
			return nil, 
		}
		,  := .BoundingBox()

		 := math.Inf(1)
		 := math.MaxInt
		// place the first graph at (0,0) so that combined's top left is always there
		 := geo.NewPoint(0, 0)
		var  int

		// For each candidate point, see if it fits at that point
		// If it does, calculate the area and compare to see if it's the best point to place it
		for ,  := range  {
			if  := .Step();  != nil {
				return nil, 
			}
			// points relative to graph top left would now be relative to the candidate point
			 := .X - .X
			 := .Y - .Y

			 := false
			 := 0
			for ,  := range .Nodes {
				if  := .Step();  != nil {
					return nil, 
				}
				.MoveWithChildren(, )
				for ,  := range .Nodes {
					if  := .Step();  != nil {
						return nil, 
					}
					if .DoesOverlap() {
						 = true
						break
					}
				}
				if ! {
					for ,  := range  {
						if  := .Step();  != nil {
							return nil, 
						}
						if .TopLeft.X == -layoutgraph.ContainerPadding && .TopLeft.Y == -layoutgraph.ContainerPadding {
							continue
						}
						if .Box.Overlaps() {
							++
						}
					}
				}
				.MoveWithChildren(-, -)
				if  {
					break
				}
			}
			if  {
				continue
			}
			if  >  {
				continue
			}

			// The new combined width is only (candidate point + graph width) if that is wider than the existing width (same for height)
			 := math.Max(.X, .X+(.X-.X))
			 := math.Max(.Y, .Y+(.Y-.Y))
			// A: Area
			// D: Deviation from square (squared)
			// Heuristic: A + cD
			// Note: the base cost is area, but we add an additional cost based on how far it is from being a square.
			// we square the difference between width and height to match area's unit (length^2)
			 := * + math.Pow(-, 2.0)*subgraphSquareDampener

			if  <  || ( ==  &&  < ) {
				 = 
				 = 
				 = 
				 = 
			}
		}

		if len() > 0 {
			// Remove the candidate point used
			[] = [len()-1]
			[len()-1] = nil
			 = [:len()-1]
		}

		// Since we are placing the graph at minCandidatePoint,
		// each point relative to the graph top left now needs to be relative to minCandidatePoint
		 := .X - .X
		 := .Y - .Y

		for ,  := range .Nodes {
			if  := .Step();  != nil {
				return nil, 
			}
			.MoveWithChildren(, )
			.AddNodeUnchecked()
			for ,  := range .AllDescendantNodes(, true) {
				if  := .Step();  != nil {
					return nil, 
				}
				.AddNodeUnchecked()
			}
		}
		for ,  := range .Edges {
			if  := .Step();  != nil {
				return nil, 
			}
			for ,  := range .Points {
				if  := .Step();  != nil {
					return nil, 
				}
				.X += 
				.Y += 
			}
			.AddEdge()
		}

		// update graph tl and br to be relative to combined
		.X += 
		.Y += 
		.X += 
		.Y += 

		.X = math.Max(.X, .X)
		.Y = math.Max(.Y, .Y)

		// Add this graph's new candidate points (at 1,2,3 with and without subgraphPadding).
		//  ┌───┐ 1
		//  │ g │
		//  └───┘ 2
		//  3
		 = append(,
			geo.NewPoint(.X, .Y),
			geo.NewPoint(.X, .Y),
			geo.NewPoint(.X, .Y),
			geo.NewPoint(.X+subgraphPadding, .Y),
			geo.NewPoint(.X+subgraphPadding, .Y),
			geo.NewPoint(.X, .Y+subgraphPadding),
		)
	}

	if  := .Finish();  != nil {
		return nil, 
	}
	 = true
	return , nil
}