package d2elklayout

import (
	

	
	
)

const (
	bendIndexCellSize = 128.0
	bendIndexMaxCells = 256
)

type spatialBounds struct {
	minX float64
	minY float64
	maxX float64
	maxY float64
}

func boundsForSegment( geo.Segment) spatialBounds {
	return spatialBounds{
		minX: math.Min(.Start.X, .End.X),
		minY: math.Min(.Start.Y, .End.Y),
		maxX: math.Max(.Start.X, .End.X),
		maxY: math.Max(.Start.Y, .End.Y),
	}
}

func ( spatialBounds) ( float64) spatialBounds {
	.minX -= 
	.minY -= 
	.maxX += 
	.maxY += 
	return 
}

func ( spatialBounds) ( spatialBounds) bool {
	return .minX <= .maxX && .minX <= .maxX &&
		.minY <= .maxY && .minY <= .maxY
}

type spatialCell struct {
	x int
	y int
}

type spatialEntry struct {
	bounds spatialBounds
	cells  []spatialCell
	large  bool
}

// spatialIndex is an exact-query broad phase: it may return false positives,
// but every item whose bounds overlap the query is returned. Very large or
// non-finite entries are kept in a small fallback set instead of filling an
// unbounded number of grid cells.
type spatialIndex[ comparable] struct {
	cellSize float64
	maxCells int
	cells    map[spatialCell]map[]struct{}
	large    map[]struct{}
	entries  map[]spatialEntry
	seen     map[]uint64
	queryID  uint64
}

func newSpatialIndex[ comparable]( int) *spatialIndex[] {
	return &spatialIndex[]{
		cellSize: bendIndexCellSize,
		maxCells: bendIndexMaxCells,
		cells:    make(map[spatialCell]map[]struct{}),
		large:    make(map[]struct{}),
		entries:  make(map[]spatialEntry, ),
		seen:     make(map[]uint64, ),
	}
}

func ( *spatialIndex[]) ( ,  spatialBounds) {
	.remove()
	,  := .coveredCells()
	 := spatialEntry{bounds: , cells: , large: !}
	.entries[] = 
	if ! {
		.large[] = struct{}{}
		return
	}
	for ,  := range  {
		 := .cells[]
		if  == nil {
			 = make(map[]struct{})
			.cells[] = 
		}
		[] = struct{}{}
	}
}

func ( *spatialIndex[]) ( ) {
	,  := .entries[]
	if ! {
		return
	}
	delete(.entries, )
	delete(.seen, )
	if .large {
		delete(.large, )
		return
	}
	for ,  := range .cells {
		 := .cells[]
		delete(, )
		if len() == 0 {
			delete(.cells, )
		}
	}
}

func ( *spatialIndex[]) ( spatialBounds,  func()) {
	,  := .coveredCells()
	if ! {
		for ,  := range .entries {
			if .bounds.overlaps() {
				()
			}
		}
		return
	}

	.queryID++
	if .queryID == 0 {
		clear(.seen)
		.queryID = 1
	}
	 := .queryID
	for ,  := range  {
		for  := range .cells[] {
			if .seen[] ==  {
				continue
			}
			.seen[] = 
			if .entries[].bounds.overlaps() {
				()
			}
		}
	}
	for  := range .large {
		if .seen[] ==  {
			continue
		}
		if .entries[].bounds.overlaps() {
			()
		}
	}
}

func ( *spatialIndex[]) ( spatialBounds) ([]spatialCell, bool) {
	if !finiteBounds() {
		return nil, false
	}
	 := math.Floor(.minX / .cellSize)
	 := math.Floor(.maxX / .cellSize)
	 := math.Floor(.minY / .cellSize)
	 := math.Floor(.maxY / .cellSize)
	// Keep float-to-int conversion safe on every supported target, including
	// wasm32. Leave one unit of headroom so the inclusive loops below cannot
	// overflow when incrementing their final coordinate.
	const  = float64(1<<31 - 2)
	if math.Abs() >  || math.Abs() >  ||
		math.Abs() >  || math.Abs() >  {
		return nil, false
	}
	 :=  -  + 1
	 :=  -  + 1
	if  <= 0 ||  <= 0 ||  > float64(.maxCells) ||
		 > float64(.maxCells) || * > float64(.maxCells) {
		return nil, false
	}
	 := make([]spatialCell, 0, int(*))
	for  := int();  <= int(); ++ {
		for  := int();  <= int(); ++ {
			 = append(, spatialCell{x: , y: })
		}
	}
	return , true
}

func finiteBounds( spatialBounds) bool {
	return !math.IsNaN(.minX) && !math.IsNaN(.minY) &&
		!math.IsNaN(.maxX) && !math.IsNaN(.maxY) &&
		!math.IsInf(.minX, 0) && !math.IsInf(.minY, 0) &&
		!math.IsInf(.maxX, 0) && !math.IsInf(.maxY, 0)
}

type indexedEdgeSegment struct {
	edge    *d2graph.Edge
	segment geo.Segment
}

type bendCollisionIndex struct {
	objects      *spatialIndex[*d2graph.Object]
	segments     *spatialIndex[*indexedEdgeSegment]
	edgeSegments map[*d2graph.Edge][]*indexedEdgeSegment
}

func newBendCollisionIndex( *d2graph.Graph) *bendCollisionIndex {
	 := &bendCollisionIndex{
		objects:      newSpatialIndex[*d2graph.Object](len(.Objects)),
		segments:     newSpatialIndex[*indexedEdgeSegment](len(.Edges) * 3),
		edgeSegments: make(map[*d2graph.Edge][]*indexedEdgeSegment, len(.Edges)),
	}
	 := float64(edge_node_spacing) - 1
	for ,  := range .Objects {
		 := spatialBounds{
			minX: .TopLeft.X,
			minY: .TopLeft.Y,
			maxX: .TopLeft.X + .Width,
			maxY: .TopLeft.Y + .Height,
		}.expanded()
		.objects.add(, )
	}
	for ,  := range .Edges {
		.updateEdge()
	}
	return 
}

func ( *bendCollisionIndex) ( *d2graph.Edge) {
	 := .edgeSegments[]
	for ,  := range  {
		.segments.remove()
	}
	 := max(0, len(.Route)-1)
	 := [:0]
	if cap() <  {
		 = make([]*indexedEdgeSegment, 0, )
	}
	for  := 0; +1 < len(.Route); ++ {
		var  *indexedEdgeSegment
		if  < len() {
			 = []
		} else {
			 = &indexedEdgeSegment{}
		}
		.edge = 
		.segment = geo.Segment{Start: .Route[], End: .Route[+1]}
		 = append(, )
		.segments.add(, boundsForSegment(.segment))
	}
	for  := len();  < len(); ++ {
		[] = nil
	}
	.edgeSegments[] = 
}

func ( *bendCollisionIndex) (,  *d2graph.Object,  geo.Segment) int {
	 := 0
	.objects.query(boundsForSegment(), func( *d2graph.Object) {
		if  ==  ||  ==  {
			return
		}
		if .Intersects(, float64(edge_node_spacing)-1) {
			++
		}
	})
	return 
}

func ( *bendCollisionIndex) ( *d2graph.Edge,  geo.Segment) (int, int, int, int) {
	 := math.Ceil(.Start.Y) == math.Ceil(.End.Y)
	 := 0
	 := 0
	 := 0
	 := 0
	 := boundsForSegment().expanded(float64(edge_node_spacing) / 2)
	.segments.query(, func( *indexedEdgeSegment) {
		if .edge ==  {
			return
		}
		 := .segment
		 := math.Ceil(.Start.Y) == math.Ceil(.End.Y)
		if  ==  {
			if .Overlaps(, !, 0.) {
				if  {
					if math.Abs(.Start.Y-.Start.Y) < float64(edge_node_spacing)/2. {
						++
						if math.Abs(.Start.Y-.Start.Y) < float64(edge_node_spacing)/4. {
							++
							if math.Abs(.Start.Y-.Start.Y) < 1. {
								++
							}
						}
					}
				} else {
					if math.Abs(.Start.X-.Start.X) < float64(edge_node_spacing)/2. {
						++
						if math.Abs(.Start.X-.Start.X) < float64(edge_node_spacing)/4. {
							++
							// Preserve the existing predicate, including its use of Y
							// for vertical touching segments.
							if math.Abs(.Start.Y-.Start.Y) < 1. {
								++
							}
						}
					}
				}
			}
		} else if .Intersects() {
			++
		}
	})
	return , , , 
}