package layoutgraph

import (
	
	
	
	
	

	
	
	

	
	
)

const (
	minCellSize           = 10.0
	turnPenaltyMultiplier = 0.125
	// Keep the exact value because center-port route scoring is output-sensitive.
	centerPortMultiplier = 0.04287499999999999
)

type Graph struct {
	// Unfortunate, but because we represent root as nil, we need to indicate root hierarchy as a field in graph
	IsRootHierarchy bool
	Nodes           []*Node
	Edges           []*Edge
	CellSize        float64

	// ovg
	crossingCost      float64
	turnCost          float64
	nonCenterPortCost float64
	costMu            sync.RWMutex

	// These are special entities within a graph:

	// -- Containers are nodes which have nodes enclosed inside them
	// ---- They can be nested
	// ---- The top level is considered a container of nil
	// ---- These are inferred
	Containers map[*Node][]*Node

	// -- Clusters are nodes which should stick together and can be reoriented and resized
	// ---- They can be oriented vertically or horizontally depending on where its connections are
	// ---- They can be resized to be all the same dimensions
	// ---- These are inferred
	Clusters map[*Node]*Cluster

	// -- Trees are nodes which are in a tree structure (i.e. any non-cyclic subgraph)
	// ---- They are oriented in one of 4 directions, depending on where its root node ends up
	// ---- These are inferred
	// ---- Trees are pruned from the graph, then after node placement, they are reattached and placed as trees
	Trees      map[*Node][]*Tree
	NodeToTree map[*Node]*Tree

	Hubs map[*Node][]*Node

	Sequences map[*Node]*Sequence

	//  -- Directions is used to lookup the direction the edges should point towards within each container
	// e.g. Bottom means the edges should primarily go from Top to Bottom
	Directions          map[*Node]geo.Orientation
	CommonUncleSiblings map[*Node]Nodes

	edgeLengthCache map[uint64]float64
}

type descendantWalkEntry struct {
	node *Node
	emit bool
}

type descendantWalkScratch struct {
	seen        map[*Node]struct{}
	stack       []descendantWalkEntry
	descendants []*Node
}

var descendantWalkPool = typedpool.New(func() *descendantWalkScratch {
	return &descendantWalkScratch{seen: make(map[*Node]struct{})}
})

func () *Graph {
	return &Graph{
		Nodes: make([]*Node, 0),
		Edges: make([]*Edge, 0),

		Containers:      make(map[*Node][]*Node),
		Clusters:        make(map[*Node]*Cluster),
		Trees:           make(map[*Node][]*Tree),
		Hubs:            make(map[*Node][]*Node),
		Sequences:       make(map[*Node]*Sequence),
		Directions:      make(map[*Node]geo.Orientation),
		edgeLengthCache: make(map[uint64]float64),
	}
}

// Direction reports the layout direction assigned to container.
func ( *Graph) ( *Node) geo.Orientation {
	if ,  := .Directions[];  {
		return 
	}
	return geo.NONE
}

func ( *Graph) ( *Node,  *GraphState,  bool,  workStepper) (bool, error) {
	, ,  := .isStructurallyBadStateContext(, , , )
	if  != nil ||  {
		return , 
	}
	if  {
		return false, .Finish()
	}
	return .hasBadOverlapStateContext(, , )
}

// isStructurallyBadStateContext checks the linear-time node invariants that do
// not depend on any other non-descendant graph node. Keeping these separate
// lets transactions validate every node's containment and fixed-position
// invariants while restricting pairwise overlap checks to relevant candidates.
func ( *Graph) ( *Node,  *GraphState,  bool,  workStepper) (,  bool,  error) {
	return .isStructurallyBadStateWithFixedOriginContext(, , , nil, false, )
}

func ( *Graph) ( *Node,  *GraphState,  bool,  *geo.Point,  bool,  workStepper) (,  bool,  error) {
	if  == nil || .TopLeft == nil {
		return true, false, invariant.New("transaction bad-state check received an incomplete node")
	}
	if  := .Step();  != nil {
		return false, false, 
	}
	// No need to check if cluster node is in bad state, the vessel covers it
	// Right now only happens when checking if containers bad state, since cluster nodes are still containers
	if .Cluster != nil {
		return false, true, nil
	}
	if ! {
		if  := .container();  != nil &&
			.TopLeft != nil && .TopLeft != nil &&
			!.Surrounds(, 0) {
			return true, false, nil
		}
		if .isContainer {
			for ,  := range .Containers[] {
				if  := .Step();  != nil {
					return false, false, 
				}
				if  == nil || .TopLeft == nil {
					return false, false, invariant.New("transaction container has an incomplete child")
				}
				if !.Surrounds(, 0) {
					return true, false, nil
				}
			}
		}
	}

	// Nothing should be past the fixed origin. Transactions cache the first
	// fixed origin for each container once per commit; standalone callers retain
	// the legacy lookup path.
	 := false
	if  {
		 =  != nil &&
			(.TopLeft.X < .X || .TopLeft.Y < .Y)
	} else {
		 = .isPointPastFixedOrigin(.TopLeft.X, .TopLeft.Y, true)
	}
	if  {
		return true, false, nil
	}

	if .FixedTopLeft != nil &&  != nil {
		 := geo.Point{}
		if ,  := .nodeGeometry[];  && .topLeft.pointer != nil {
			 = .topLeft.value
		}
		if .TopLeft.X != .X || .TopLeft.Y != .Y {
			return true, false, nil
		}
	}
	return false, false, nil
}

func ( *Graph) ( *Node,  *GraphState,  workStepper) (bool, error) {
	if  == nil || .TopLeft == nil {
		return true, invariant.New("transaction overlap check received an incomplete node")
	}
	if .Cluster != nil {
		return false, nil
	}
	var  map[*Node]map[*Node]struct{}
	if  != nil {
		 = .existingOverlaps
	}

	var  []*Node
	if .isContainer || .isClusterVessel || .Sequences[] != nil {
		var  error
		,  = .allDescendantNodesGuarded(, true, )
		if  != nil {
			return false, 
		}
	}
	// doesOverlapWithDimensionsContext already skips node identity, so only
	// descendants and ancestors need to be materialized as exceptions.
	if .Container != nil || .Cluster != nil || .Sequence != nil {
		,  := .ancestorsOfGuarded(, )
		if  != nil {
			return false, 
		}
		 = append(, ...)
	}
	return .doesOverlapWithDimensionsContext(, .TopLeft, .Width, .Height, , , )
}

// mirrorAxes performs a reflection of the graph (both horizontal and vertical according to x and y)
// When the graph has containers, the contents of those containers are recursively reflected iff it is reachable from other nodes
// If it is reachable, reflecting maintains edge length. Otherwise, reflecting could reverse edge directions undesirably

// For example, we want to mirror the two outer nodes, but do not want to mirror the contents of the container
//
// . ┌─────────┐
// . │         │
// . │   ┌──┐  │
// . │   │  │  │
// . │   └─┬┘  │
// . │     │   │
// . │   ┌─▼┐  │
// . │   └──┘  │
// . │         │
// . └────▲────┘
// .      │
// .      │
// .  ┌───┴───┐
// .  │       │
// .  └───────┘
// Currently used by container child over container center
func ( *Graph) ( *Node) {
	.Nodes = append(.Nodes, )
	.Graph = 
}

func ( *Graph) (,  *Node) {
	.Containers[] = append(
		.Containers[],
		,
	)
	.Container = 
	if  != nil {
		.isContainer = true
	}
}

func ( *Graph) (,  *Node) {
	.AddNodeUnchecked()
	.AddNodeToContainer(, )
}

func ( *Graph) ( *Node) *Node {
	if ,  := .isOccupied(.TopLeft); ! {
		.AddNodeUnchecked()
		return 
	} else {
		return 
	}
}

func ( *Graph) ( *Node) {
	 := make([]*Node, 0, len(.Nodes)-1)

	for ,  := range .Nodes {
		if  !=  {
			 = append(, )
		}
	}

	.Nodes = 
}

func ( *Graph) ( *Edge) {
	if slices.Contains(.Edges, ) {
		return
	}
	.Edges = append(.Edges, )
}

func ( *Graph) () {
	 := math.Inf(1)
	 := math.Inf(1)
	 := math.Inf(-1)
	 := math.Inf(-1)

	for ,  := range .Nodes {
		 = math.Min(, .Width)
		 = math.Min(, .Height)
		 = math.Max(, .Width)
		 = math.Max(, .Height)
	}

	 := math.Min(, )
	 := math.Max(, )

	if  < (3.0 * ) {
		.CellSize = math.Ceil()
	} else {
		.CellSize = math.Ceil((3.0 * ) / 2.0)
	}
	.CellSize = math.Max(.CellSize, minCellSize)
}

func ( *Graph) ( *Edge) {
	.From.removeEdge()
	.To.removeEdge()

	 := make([]*Edge, 0, len(.Edges))
	for ,  := range .Edges {
		if  !=  {
			 = append(, )
		}
	}

	.Edges = 
}

func ( *Graph) (,  *Node) *Edge {
	 := NewEdge(, )
	.Edges = append(.Edges, )
	.addEdge()
	if  !=  {
		.addEdge()
	}
	return 
}

func ( *Graph) ( *Node,  *geo.Point, ,  float64,  []*Node,  map[*Node]map[*Node]struct{},  workStepper) (bool, error) {
	if  == nil ||  == nil {
		return true, invariant.New("overlap check received an incomplete node")
	}
	 := .X + 
	 := .Y + 
	var  map[*Node]struct{}
	if len() > 0 {
		if len() <= 8 || len() > maxPooledOverlapExceptions {
			// Small maps fit in the compiler's stack-allocated map group; large
			// maps must not enter the pool after a partially populated failure.
			 = make(map[*Node]struct{}, len())
		} else {
			 := overlapExceptionPool.Get()
			defer releaseOverlapExceptions()
			if .nodes == nil {
				.nodes = make(map[*Node]struct{}, len())
			}
			 = .nodes
		}
		for ,  := range  {
			if  := .Step();  != nil {
				return false, 
			}
			[] = struct{}{}
		}
	}
	// Every candidate comparison uses the same moved-node exception set. Resolve
	// it once instead of repeating an outer-map lookup for every graph node.
	 := []

	for ,  := range .Nodes {
		if  := .Step();  != nil {
			return false, 
		}
		if  == nil {
			return false, invariant.New("overlap check encountered a nil graph node")
		}
		if  ==  {
			continue
		}
		if .TopLeft != nil {
			// This heuristic is only a trial filter; the transaction constructor uses
			// the proven graph-wide padding above as its construction bound.
			const  = 500.0
			if .X > .TopLeft.X+.Width+ ||
				.X++ < .TopLeft.X ||
				.Y > .TopLeft.Y+.Height+ ||
				.Y++ < .TopLeft.Y {
				continue
			}
			// Distant boxes cannot overlap regardless of the exception sets. Test
			// geometry first so sparse layouts avoid two map probes per box.
			if ,  := [];  {
				continue
			}
			if ,  := [];  {
				continue
			}
			,  := .deltaToGuarded(, , )
			if  != nil {
				return false, 
			}
			 := float64()

			// Standard overlap test
			if (.X < (.TopLeft.X + .Width + )) && (( + ) > .TopLeft.X) &&
				(.Y < (.TopLeft.Y + .Height + )) && (( + ) > .TopLeft.Y) {
				return true, nil
			}
		}
	}
	return false, .Finish()
}

// WouldOverlapWithWorkGuard reports whether placing node at point overlaps an
// unexcepted graph node while charging the complete comparison.
func ( *Graph) (
	 *Node,
	 *geo.Point,
	 []*Node,
	 map[*Node]map[*Node]struct{},
	 *limits.WorkGuard,
) (bool, error) {
	if  == nil {
		return false, fmt.Errorf("TALA overlap check requires a work guard")
	}
	if  == nil {
		return .doesOverlapWithDimensionsContext(
			,
			,
			0,
			0,
			,
			,
			,
		)
	}
	return .doesOverlapWithDimensionsContext(
		,
		,
		.Width,
		.Height,
		,
		,
		,
	)
}

func ( *Graph) ( *geo.Point) (*Node, bool) {
	for ,  := range .Nodes {
		if (.TopLeft != nil) &&  != nil && nonNilEquals(.TopLeft, ) {
			return , true
		}
	}
	return nil, false
}

func ( *Node) (,  float64,  bool) bool {
	 := .Graph.containerFixedOrigin(.container())
	if  == nil {
		return false
	}
	if ! {
		.X = math.Round(.X / .Graph.CellSize)
		.Y = math.Round(.Y / .Graph.CellSize)
	}
	return  < .X ||  < .Y
}

// if this graph is a subgraph, return the container of the least nested node
// normally this is the nil container
func ( Nodes) () *Node {
	var  *Node
	 := math.MaxInt
	for ,  := range  {
		 := .container()
		if  == nil {
			return nil
		}
		 := .containerLevel()
		if  <  {
			 = 
			 = 
		}
	}
	return 
}

func ( *Graph) () (*geo.Point, *geo.Point) {
	,  := .boundingBox(true)
	if  == nil ||  == nil {
		return nil, nil
	}
	// Placement consumes a pixel-aligned graph box even when edge points are
	// fractional.
	return geo.NewPoint(math.Round(.X), math.Round(.Y)), geo.NewPoint(math.Round(.X), math.Round(.Y))
}

func ( *Graph) () (*geo.Point, *geo.Point) {
	return .boundingBox(false)
}

func ( *Graph) ( bool) (*geo.Point, *geo.Point) {
	var ,  *geo.Point
	if  {
		,  = Nodes(.Nodes).fixedBounds()
	} else {
		,  = Nodes(.Nodes).unroundedFixedBounds()
	}
	if  == nil ||  == nil {
		return nil, nil
	}

	 := .X
	 := .Y

	 := .X
	 := .Y

	for ,  := range .Edges {
		,  := .boundingBoxValues()
		if !math.IsInf(.X, 0) {
			 = math.Min(, .X)
			 = math.Min(, .Y)
			 = math.Max(, .X)
			 = math.Max(, .Y)
		}

	}

	return geo.NewPoint(, ), geo.NewPoint(, )
}

func ( *Graph) () float64 {
	.costMu.RLock()
	if .turnCost != 0.0 {
		 := .turnCost
		.costMu.RUnlock()
		return 
	}
	.costMu.RUnlock()

	.costMu.Lock()
	defer .costMu.Unlock()
	if .turnCost != 0.0 {
		return .turnCost
	}
	 := turnPenaltyMultiplier * float64(len(.Edges)) * .maxEdgeLength()
	.turnCost = 

	return 
}

func ( *Graph) () float64 {
	.costMu.RLock()
	if .nonCenterPortCost != 0.0 {
		 := .nonCenterPortCost
		.costMu.RUnlock()
		return 
	}
	.costMu.RUnlock()

	.costMu.Lock()
	defer .costMu.Unlock()
	if .nonCenterPortCost != 0.0 {
		return .nonCenterPortCost
	}
	if len(.Edges) == 0 {
		return 0
	}
	 := centerPortMultiplier * float64(len(.Edges)) * .maxEdgeLength()

	// For certain diagrams, the `cost` above can be smaller than the distance between ports
	// and then edge routing doesn't prefer center ports as expected
	// ┌──────────────────────────────────────────────────────┐
	// │                                   port               │
	// |                                distance              |
	// │                                                      │
	// │                           │──────────────────│       │
	// └────────┬──────────────────┬──────────────────┬───────┘
	//          │                  │                  │
	//          │                  │                  │
	// the routine below estimates another cost based on the min node size
	 := math.Inf(1)
	for ,  := range .Nodes {
		if .isContainer {
			continue
		}
		 = math.Min(, .Height)
		 = math.Min(, .Width)
	}

	if !math.IsInf(, 1) {
		 = math.Max(, /3.)
	}
	.nonCenterPortCost = 

	return 
}

func ( *Graph) () float64 {
	.costMu.RLock()
	if .crossingCost != 0.0 {
		 := .crossingCost
		.costMu.RUnlock()
		return 
	}
	.costMu.RUnlock()

	.costMu.Lock()
	defer .costMu.Unlock()
	if .crossingCost != 0.0 {
		return .crossingCost
	}
	// c * (m * l_max)

	 := CrossingCostWeight * float64(len(.Edges)) * .maxEdgeLength()
	.crossingCost = 

	return 
}

func ( *Graph) () {
	.costMu.Lock()
	.turnCost = 0
	.costMu.Unlock()
}

func ( *Graph) () float64 {
	 := false
	 := float64(ConnectedNodeGap)
	for ,  := range .Nodes {
		if .TopLeft == nil {
			continue
		}
		for ,  := range .Edges {
			 := .adjacent()
			if .TopLeft == nil {
				continue
			}
			 = true
			 := .distanceTo(, true)
			 = math.Max(, )
		}
	}
	if ! {
		return 0.0
	}
	return 
}

// SplitOptions controls which relationships connect nodes while splitting a
// graph into subgraphs.
type SplitOptions struct {
	IncludeContainers bool
	IncludeNears      bool
	TraverseTrees     bool
}

// SplitSubgraphs partitions the graph into sets of mutually reachable nodes.
func ( *Graph) ( context.Context,  SplitOptions) ([]*Graph, error) {
	return .splitSubgraphsWithOwnership(, , nil, nil)
}

type nodeGraphOwnershipJournal map[*Node]*Graph

func ( nodeGraphOwnershipJournal) () {
	for ,  := range  {
		.Graph = 
	}
}

// splitSubgraphsWithOwnership optionally returns every Node.Graph value changed
// by the split. Reachability includes the bounded Near closure, so a caller can
// restore even Near-only nodes that are not members of the source Graph.Nodes.
func ( *Graph) (
	 context.Context,
	 SplitOptions,
	 *nodeGraphOwnershipJournal,
	 workStepper,
) ([]*Graph, error) {
	 := 
	if  == nil {
		if  := validateEngineGraph(, "SplitSubgraphs", );  != nil {
			return nil, 
		}
		var  error
		,  = limits.NewWorkGuard(, "SplitSubgraphs", maxEngineWorkUnits)
		if  != nil {
			return nil, 
		}
	} else if  := .Finish();  != nil {
		return nil, 
	}
	 := make(map[*Node]*Graph, len(.Nodes))
	for ,  := range .Nodes {
		if  := .Step();  != nil {
			return nil, 
		}
		if  != nil {
			[] = .Graph
		}
	}
	 := false
	defer func() {
		if  {
			return
		}
		for ,  := range  {
			.Graph = 
		}
	}()
	 := make([]*Graph, 0)
	if len(.Nodes) == 0 {
		 = true
		return , nil
	}

	 := map[*Node]struct{}{}
	 := make(map[*Node]*Graph, len(.Nodes))
	 := func( *Node,  *Graph) error {
		,  := .allReachableNodesGuarded(
			.IncludeContainers,
			.IncludeNears,
			.TraverseTrees,
			nil,
			,
		)
		if  != nil {
			return 
		}
		for ,  := range  {
			if  := .Step();  != nil {
				return 
			}
			if ,  := [];  {
				continue
			}
			if ,  := []; ! {
				if len() >= maxEngineNodes {
					return fmt.Errorf("TALA SplitSubgraphs unique node ownership exceeds limit %d", maxEngineNodes)
				}
				[] = .Graph
			}
			.AddNodeUnchecked()
			[] = struct{}{}
			[] = 
		}
		return nil
	}

	 := make([]*Node, 0)
	for ,  := range .Nodes {
		if  := .Step();  != nil {
			return nil, 
		}
		if .FixedTopLeft != nil {
			 = append(, )
		}
	}
	if len() > 0 {
		// create first subgraph with all fixed nodes
		// it will be placed at 0,0 in CombineSubgraphs so fixed locations are accurate
		 := NewGraph()
		.CopyEntitiesFrom()

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

		 = append(, )
	}

	for ,  := range .Nodes {
		if  := .Step();  != nil {
			return nil, 
		}
		if ,  := [];  {
			continue
		}

		 := NewGraph()
		.CopyEntitiesFrom()
		if  := (, );  != nil {
			return nil, 
		}

		 = append(, )
	}

	// Each original edge is considered once. This preserves the original graph's
	// edge order without the quadratic duplicate scan in AddEdge. In the unusual
	// case where a traversal deliberately omits one endpoint into another
	// subgraph, retain the edge in both subgraphs as the old endpoint scan did.
	 := make(map[*Graph]map[*Edge]struct{}, len())
	 := func( *Graph,  *Edge) {
		 := []
		if  == nil {
			 = make(map[*Edge]struct{})
			[] = 
		}
		if ,  := [];  {
			return
		}
		[] = struct{}{}
		.Edges = append(.Edges, )
	}
	for ,  := range .Edges {
		if  := .Step();  != nil {
			return nil, 
		}
		 := [.From]
		 := [.To]
		if  != nil {
			(, )
		}
		if  != nil &&  !=  {
			(, )
		}
	}
	if  := .Finish();  != nil {
		return nil, 
	}

	if  != nil {
		* = 
	}
	 = true
	return , nil
}

func ( *Graph) () float64 {
	if len(.Nodes) == 0 {
		return 0
	}
	,  := .unroundedBounds()
	return math.Abs(.X-.X) * math.Abs(.Y-.Y)
}

// 2D bin packing with rectangles
// Algorithm:
// 1. keep a list of candidate points, which are 3 non-upper-left corners of every placed subgraph. Initially, just (0,0)
// 2. calculate how much empty space remains after potential placement
// 3. the min empty space candidate point gets the subgraph placed there
// Start from largest to smallest subgraphs
func ( *Graph) ( *Node) []*Node {
	var  []*Node

	if  != nil && !.isContainer {
		return 
	}

	for ,  := range slices.Backward(.Containers[]) {

		if .isContainer {
			 = append(, .()...)
			 = append(, )
			continue
		}

		if .isClusterVessel {
			 := .Clusters[]
			for ,  := range slices.Backward(.Nodes) {

				if .isContainer {
					 = append(, .()...)
					 = append(, )
				}
			}
			continue
		}
	}

	return 
}

func ( *Graph) ( *Node,  workStepper) ([]*Node, error) {
	var  []*Node
	if  != nil && !.isContainer {
		return , nil
	}

	for ,  := range slices.Backward(.Containers[]) {
		if  := .Step();  != nil {
			return nil, 
		}

		if .isContainer {
			,  := .(, )
			if  != nil {
				return nil, 
			}
			 = append(, ...)
			 = append(, )
			continue
		}
		if .isClusterVessel {
			 := .Clusters[]
			for ,  := range slices.Backward(.Nodes) {
				if  := .Step();  != nil {
					return nil, 
				}

				if .isContainer {
					,  := .(, )
					if  != nil {
						return nil, 
					}
					 = append(, ...)
					 = append(, )
				}
			}
		}
	}
	return , nil
}

func ( *Graph) () {
	for ,  := range .Nodes {
		if .isContainer {
			.positionContainerChildren(true)
		}
		if .isClusterVessel {
			 := .Clusters[]
			.SyncGeometry()
			// Since cluster nodes can themselves be containers, we can't merely move all children nodes, we must
			// also care to give container children padding
			for ,  := range .Nodes {
				if .isContainer {
					 := .containerPadding(, true)
					for ,  := range .Containers[] {
						.moveNodeWithChildren(.left, .top)
					}
				}
			}
		}
		if ,  := .Sequences[];  {
			.SyncGeometry()
		}
	}
}

// includeClusterNodes should be included when the purpose is to move all nodes
// But if the purpose is to find nodes to perform operations on, the cluster nodes should not be included (vessels will be included)
// Does not include current node
func ( *Graph) ( *Node,  bool) []*Node {
	 := unboundedWork
	,  := .allDescendantNodesGuarded(, , )
	if  != nil {
		panic()
	}
	return 
}

func ( *Graph) ( *Node,  bool,  workStepper) ([]*Node, error) {
	 := descendantWalkPool.Get()
	clear(.seen)
	.stack = .stack[:0]
	.descendants = .descendants[:0]
	defer func() {
		clear(.seen)
		clear(.stack[:cap(.stack)])
		clear(.descendants)
		.stack = .stack[:0]
		.descendants = .descendants[:0]
		descendantWalkPool.Put()
	}()
	if  != nil {
		.seen[] = struct{}{}
	}
	 := func( *Node) error {
		// Push in reverse traversal order so the iterative walk retains the old
		// container-before-cluster-before-sequence preorder.
		if  := .Sequences[];  != nil {
			for ,  := range slices.Backward(.Nodes) {
				if  := .Step();  != nil {
					return 
				}
				.stack = append(.stack, descendantWalkEntry{node: , emit: })
			}
		}
		if  != nil && .isClusterVessel {
			if  := .Clusters[];  != nil {
				for ,  := range slices.Backward(.Nodes) {
					if  := .Step();  != nil {
						return 
					}
					.stack = append(.stack, descendantWalkEntry{node: , emit: })
				}
			}
		}
		if  == nil || .isContainer {
			 := .Containers[]
			for ,  := range slices.Backward() {
				if  := .Step();  != nil {
					return 
				}
				.stack = append(.stack, descendantWalkEntry{node: , emit: true})
			}
		}
		return nil
	}
	if  := ();  != nil {
		return nil, 
	}

	for len(.stack) > 0 {
		if  := .Step();  != nil {
			return nil, 
		}
		 := len(.stack) - 1
		 := .stack[]
		.stack = .stack[:]
		if .node == nil {
			continue
		}
		if ,  := .seen[.node];  {
			continue
		}
		.seen[.node] = struct{}{}
		if .emit {
			.descendants = append(.descendants, .node)
		}
		if  := (.node);  != nil {
			return nil, 
		}
	}
	if  := .Finish();  != nil {
		return nil, 
	}
	return append([]*Node(nil), .descendants...), nil
}

func ( *Graph) ( *Node,  workStepper) ( []*Node,  error) {
	 := make(map[*Node]struct{})
	for  := ;  != nil; {
		if  := .Step();  != nil {
			return nil, 
		}
		if ,  := [];  {
			return nil, invariant.New("cycle in transaction ancestry")
		}
		[] = struct{}{}
		if len() > maxEngineNodes {
			return nil, invariant.New("transaction ancestry exceeds node limit")
		}
		if  !=  {
			// don't include node itself
			 = append(, )
		}
		if .Container != nil {
			 = .Container
		} else if .Cluster != nil {
			 = .Cluster.Vessel
		} else if .Sequence != nil {
			 = .Sequence.Vessel
		} else {
			break
		}
	}
	return , .Finish()
}

func ( *Graph) ( *Node) bool {
	,  := .Trees[]
	return 
}

func ( *Graph) ( *Node) bool {
	,  := .Sequences[]
	return 
}

func ( *Graph) ( *Graph) {
	.Containers = .Containers
	.Clusters = .Clusters
	.Trees = .Trees
	.NodeToTree = .NodeToTree
	.Sequences = .Sequences
	.Hubs = .Hubs
	.Directions = .Directions
	.CommonUncleSiblings = .CommonUncleSiblings
	// TODO maybe not
	.IsRootHierarchy = .IsRootHierarchy
}

func ( Nodes) () []*Node {
	var  []*Node
	for ,  := range  {
		if .FixedTopLeft != nil {
			 = append(, )
		}
	}
	return 
}

func ( *Graph) () []*Node {
	return Nodes(.Nodes).fixedNodes()
}

func ( Nodes) () bool {
	for ,  := range  {
		if .FixedTopLeft != nil {
			return true
		}
	}
	return false
}

func ( *Graph) () bool {
	return Nodes(.Nodes).hasFixedNode()
}

// If container A has child B at (80,30) with a FixedTopLeft of (70,20) (ignoring padding)
// then the FixedOrigin point of the nodes [B,C] should be at (10,10), despite their bounding box TL being at (80,30).
// This way when A positions itself around its children, it has the space for B's FixedTopLeft to be correct.
// | Note: This assumes the relative positions between fixed nodes are correct:
// |  if C also has a FixedTopLeft, then it must be (70,50), otherwise B and C's positions are inconsistent.
//
// .  ┌(10,10)───────────────┐
// .  │ A                    │
// .  │          ┌(80,30)┐   │
// .  │          │   B   ├─┐ │
// .  │          └───────┘ │ │
// .  │          ┌(80,60)┐ │ │
// .  │          │   C   ├─┘ │
// .  │          └───────┘   │
// .  └──────────────────────┘
func ( Nodes) () *geo.Point {
	 := .subgraphContainer()
	for ,  := range  {
		if .container() !=  {
			continue
		}
		// the origin is the same for all fixed nodes in the container (see note above)
		if  := .fixedOrigin();  != nil {
			return 
		}
	}
	return nil
}

func ( *Graph) ( *Node) *geo.Point {
	for ,  := range .Nodes {
		if .container() !=  {
			continue
		}
		if  := .fixedOrigin();  != nil {
			return 
		}
	}
	return nil
}

func ( *Node) () *geo.Point {
	if .TopLeft != nil && .FixedTopLeft != nil {
		return geo.NewPoint(
			.TopLeft.X-.FixedTopLeft.X,
			.TopLeft.Y-.FixedTopLeft.Y,
		)
	}
	return nil
}

// return the amount of padding the container should have on each side. (more padding if there are icons)
// Note: we need the graph reference since container may be the nil container
// considerChildren should be false if the output is used together with the nodes bounding box, becuase it already accounts for icons
func ( *Graph) ( *Node,  bool) Spacing {
	 := float64(ContainerPadding)
	 := Spacing{top: , bottom: , left: , right: }
	if  == nil {
		return 
	}
	if .shapeType == circleType {
		// Circles just need padding so the corner of child doesn't touch corner of circle
		// Optically, there will be a lot of padding on the sides even given a small value
		 /= 4.
	}

	if .Icon != nil && .shapeType != imageType {
		// we don't know if the icon will be placed at an inside position, but leave enough padding so it has that option
		// Note: we don't know what the exact icon size will be until the final layout size so we use max
		 = float64(MaxIconSize + 2*label.PADDING)
	}

	if .Label != nil && !.Label.Position.IsOutside() {
		// First ensure total container width/height can accommodate label
		 := .Label.Width + 2*label.PADDING
		 := .Label.Height + 2*label.PADDING

		switch .Label.Position {
		case label.InsideTopLeft, label.InsideTopCenter, label.InsideTopRight:
			.top = math.Max(.top, )
		case label.InsideBottomLeft, label.InsideBottomCenter, label.InsideBottomRight:
			.bottom = math.Max(.bottom, )
		case label.InsideMiddleLeft:
			.left = math.Max(.left, )
		case label.InsideMiddleRight:
			.right = math.Max(.right, )
		}

		// Ensure total width/height can accommodate label
		 :=  + .left + .right
		if .Width <  {
			 := math.Ceil(( - .Width) / 2)
			.left = math.Max(.left, )
			.right = math.Max(.right, )
		}

		 :=  + .top + .bottom
		if .Height <  {
			 := math.Ceil(( - .Height) / 2)
			.top = math.Max(.top, )
			.bottom = math.Max(.bottom, )
		}
	}

	if  {
		var  bool
		var  Spacing
		for ,  := range .Containers[] {
			if ! && .Icon != nil && .shapeType != imageType && !.Icon.PositionFixed() {
				 = true
			}
			.left = math.Max(.left, .margin.left)
			.right = math.Max(.right, .margin.right)
			.top = math.Max(.top, .margin.top)
			.bottom = math.Max(.bottom, .margin.bottom)
		}
		.left = math.Max(.left, .padding.left+.left)
		.right = math.Max(.right, .padding.right+.right)
		.top = math.Max(.top, .padding.top+.top)
		.bottom = math.Max(.bottom, .padding.bottom+.bottom)

		if  {
			// we don't know if the icon will be placed at an inside position, but leave enough padding so it has that option
			// Note: we don't know what the exact icon size will be until the final layout size so we use max
			 = float64(MaxIconSize + 2*label.PADDING)
		}
	}

	if .shapeType == circleType {
		.top /= 4.
		.left /= 4.
		.bottom /= 4.
		.right /= 4.
	}

	.left = math.Max(.left, math.Max(.padding.left, ))
	.right = math.Max(.right, math.Max(.padding.right, ))
	.top = math.Max(.top, math.Max(.padding.top, ))
	.bottom = math.Max(.bottom, math.Max(.padding.bottom, ))

	return 
}