internal.go

package region

// overlapFunc is called to handle overlapping bands during region operations.
type overlapFunc func(result *[]Box, r1, r2 []Box, y1, y2 int32)

// quickSortRects sorts rectangles by (Y1, X1) in ascending order.
func quickSortRects(rects []Box) {
	numRects := len(rects)
	if numRects <= 1 {
		return
	}

	// Always called with numRects > 1
	for numRects > 1 {
		if numRects == 2 {
			if rects[0].Y1 > rects[1].Y1 ||
				(rects[0].Y1 == rects[1].Y1 && rects[0].X1 > rects[1].X1) {
				rects[0], rects[1] = rects[1], rects[0]
			}
			return
		}

		// Choose partition element, stick in location 0
		rects[0], rects[numRects>>1] = rects[numRects>>1], rects[0]
		y1 := rects[0].Y1
		x1 := rects[0].X1

		// Partition array
		i := 0
		j := numRects

		for {
			// Find element from left that should be on right
			for {
				i++
				if i == numRects || !(rects[i].Y1 < y1 || (rects[i].Y1 == y1 && rects[i].X1 < x1)) {
					break
				}
			}

			// Find element from right that should be on left
			for {
				j--
				if !(y1 < rects[j].Y1 || (y1 == rects[j].Y1 && x1 < rects[j].X1)) {
					break
				}
			}

			if i < j {
				rects[i], rects[j] = rects[j], rects[i]
			} else {
				break
			}
		}

		// Move partition element back to middle
		rects[0], rects[j] = rects[j], rects[0]

		// Recurse on right side (larger partition)
		if numRects-j-1 > 1 {
			quickSortRects(rects[j+1 : numRects])
		}

		// Loop on left side (tail recursion optimization)
		numRects = j
	}
}

// coalesce attempts to merge the current band with the previous band.
// Returns the new index for the previous band.
func coalesce(rects []Box, prevStart, curStart int) ([]Box, int) {
	if curStart >= len(rects) {
		return rects, prevStart
	}

	numRects := curStart - prevStart
	curNum := len(rects) - curStart

	// Must have same number of rectangles in both bands
	if numRects != curNum || numRects == 0 {
		return rects, curStart
	}

	// Check if bands can be merged (bottom of prev == top of cur)
	if rects[prevStart].Y2 != rects[curStart].Y1 {
		return rects, curStart
	}

	// Check if all rectangles have same X coordinates
	for i := 0; i < numRects; i++ {
		if rects[prevStart+i].X1 != rects[curStart+i].X1 ||
			rects[prevStart+i].X2 != rects[curStart+i].X2 {
			return rects, curStart
		}
	}

	// Merge: extend Y2 of previous band and remove current band
	y2 := rects[curStart].Y2
	for i := 0; i < numRects; i++ {
		rects[prevStart+i].Y2 = y2
	}

	// Remove current band
	return rects[:curStart], prevStart
}

// findBandEnd finds the end index of the current band (rectangles with same Y1).
func findBandEnd(rects []Box, start int) int {
	if start >= len(rects) {
		return start
	}
	y1 := rects[start].Y1
	end := start + 1
	for end < len(rects) && rects[end].Y1 == y1 {
		end++
	}
	return end
}

// regionOp performs a generic region operation.
func regionOp(r *Region, reg1, reg2 *Region, overlap overlapFunc, appendNon1, appendNon2 bool) {
	r1 := reg1.getRects()
	r2 := reg2.getRects()

	if len(r1) == 0 && len(r2) == 0 {
		r.Clear()
		return
	}

	if len(r1) == 0 {
		if appendNon2 {
			r.rects = make([]Box, len(r2))
			copy(r.rects, r2)
			r.setExtents()
		} else {
			r.Clear()
		}
		return
	}

	if len(r2) == 0 {
		if appendNon1 {
			r.rects = make([]Box, len(r1))
			copy(r.rects, r1)
			r.setExtents()
		} else {
			r.Clear()
		}
		return
	}

	// Result buffer
	result := make([]Box, 0, len(r1)+len(r2))

	// Indices into r1 and r2
	i1, i2 := 0, 0

	// Initialize ybot
	ybot := r1[0].Y1
	if r2[0].Y1 < ybot {
		ybot = r2[0].Y1
	}

	prevBand := 0

	for i1 < len(r1) && i2 < len(r2) {
		// Find current bands
		band1End := findBandEnd(r1, i1)
		band2End := findBandEnd(r2, i2)

		r1y1 := r1[i1].Y1
		r2y1 := r2[i2].Y1
		r1y2 := r1[i1].Y2
		r2y2 := r2[i2].Y2

		// Handle non-overlapping bands
		if r1y1 < r2y1 {
			if appendNon1 {
				top := max32(r1y1, ybot)
				bot := min32(r1y2, r2y1)
				if top < bot {
					curBand := len(result)
					for k := i1; k < band1End; k++ {
						result = append(result, Box{r1[k].X1, top, r1[k].X2, bot})
					}
					result, prevBand = coalesce(result, prevBand, curBand)
				}
			}
			if r1y2 <= r2y1 {
				i1 = band1End
				continue
			}
		} else if r2y1 < r1y1 {
			if appendNon2 {
				top := max32(r2y1, ybot)
				bot := min32(r2y2, r1y1)
				if top < bot {
					curBand := len(result)
					for k := i2; k < band2End; k++ {
						result = append(result, Box{r2[k].X1, top, r2[k].X2, bot})
					}
					result, prevBand = coalesce(result, prevBand, curBand)
				}
			}
			if r2y2 <= r1y1 {
				i2 = band2End
				continue
			}
		}

		// Handle overlapping region
		ytop := max32(r1y1, r2y1)
		ybot = min32(r1y2, r2y2)

		if ybot > ytop {
			curBand := len(result)
			overlap(&result, r1[i1:band1End], r2[i2:band2End], ytop, ybot)
			if len(result) > curBand {
				result, prevBand = coalesce(result, prevBand, curBand)
			}
		}

		// Move to next band
		if r1y2 == ybot {
			i1 = band1End
		}
		if r2y2 == ybot {
			i2 = band2End
		}
	}

	// Handle remaining bands from r1
	// First band gets Y clipping + COALESCE, rest are appended as-is
	if i1 < len(r1) && appendNon1 {
		// Do first non-overlap call, which may be able to coalesce
		band1End := findBandEnd(r1, i1)
		r1y1 := r1[i1].Y1
		r1y2 := r1[i1].Y2

		top := max32(r1y1, ybot)
		if top < r1y2 {
			curBand := len(result)
			for k := i1; k < band1End; k++ {
				result = append(result, Box{r1[k].X1, top, r1[k].X2, r1y2})
			}
			result, prevBand = coalesce(result, prevBand, curBand)
		}

		// Just append the rest of the boxes (APPEND_REGIONS)
		for k := band1End; k < len(r1); k++ {
			result = append(result, r1[k])
		}
	}

	// Handle remaining bands from r2
	// First band gets Y clipping + COALESCE, rest are appended as-is
	if i2 < len(r2) && appendNon2 {
		// Do first non-overlap call, which may be able to coalesce
		band2End := findBandEnd(r2, i2)
		r2y1 := r2[i2].Y1
		r2y2 := r2[i2].Y2

		top := max32(r2y1, ybot)
		if top < r2y2 {
			curBand := len(result)
			for k := i2; k < band2End; k++ {
				result = append(result, Box{r2[k].X1, top, r2[k].X2, r2y2})
			}
			result, _ = coalesce(result, prevBand, curBand)
		}

		// Just append the rest of the boxes (APPEND_REGIONS)
		for k := band2End; k < len(r2); k++ {
			result = append(result, r2[k])
		}
	}

	// Set result
	if len(result) == 0 {
		r.Clear()
	} else if len(result) == 1 {
		r.extents = result[0]
		r.rects = nil
	} else {
		r.rects = result
		r.setExtents()
	}
}

// regionInfo tracks a mini-region during validate's Step 2.
type regionInfo struct {
	reg      Region
	prevBand int
	curBand  int
}

// validate normalizes an unsorted collection of rectangles into Y-X banded format.
//
// Take a "region" which is a non-y-x-banded random collection of
// rectangles, and compute a nice region which is the union of all the
// rectangles.
//
// Strategy:
//   - Step 1: Sort the rectangles into ascending order with primary key y1
//     and secondary key x1.
//   - Step 2: Split the rectangles into the minimum number of proper y-x
//     banded regions.
//   - Step 3: Merge the regions and set the extents.
func (r *Region) validate() {
	if r.rects == nil {
		return
	}

	numRects := len(r.rects)
	if numRects == 0 {
		r.Clear()
		return
	}

	// If extents is already valid, region is already normalized
	if r.extents.X1 < r.extents.X2 {
		if numRects == 1 {
			r.rects = nil
		}
		return
	}

	// Step 1: Sort the rects array into ascending (y1, x1) order
	quickSortRects(r.rects)

	// Step 2: Scatter the sorted array into the minimum number of regions
	// Set up the first region to be the first rectangle
	ri := make([]regionInfo, 0, 64)
	ri = append(ri, regionInfo{
		reg: Region{
			extents: r.rects[0],
			rects:   []Box{r.rects[0]},
		},
		prevBand: 0,
		curBand:  0,
	})

	// Now scatter rectangles into the minimum set of valid regions.
	// If the next rectangle to be added to a region would force an existing rectangle
	// in the region to be split up in order to maintain y-x banding, just
	// forget it. Try the next region. If it doesn't fit cleanly into any
	// region, make a new one.
	for i := 1; i < numRects; i++ {
		box := r.rects[i]
		foundRegion := false

		// Look for a region to append box to
		for j := 0; j < len(ri); j++ {
			rit := &ri[j]
			reg := &rit.reg
			riBox := reg.rects[len(reg.rects)-1] // Last box in this region

			if box.Y1 == riBox.Y1 && box.Y2 == riBox.Y2 {
				// box is in same band as riBox. Merge or append it
				if box.X1 <= riBox.X2 {
					// Merge it with riBox
					if box.X2 > reg.rects[len(reg.rects)-1].X2 {
						reg.rects[len(reg.rects)-1].X2 = box.X2
					}
				} else {
					// Append to band
					reg.rects = append(reg.rects, box)
				}
				foundRegion = true
				break
			} else if box.Y1 >= riBox.Y2 {
				// Put box into new band
				if reg.extents.X2 < riBox.X2 {
					reg.extents.X2 = riBox.X2
				}
				if reg.extents.X1 > box.X1 {
					reg.extents.X1 = box.X1
				}

				// Coalesce previous band
				reg.rects, rit.prevBand = coalesce(reg.rects, rit.prevBand, rit.curBand)
				rit.curBand = len(reg.rects)

				// Append new box
				reg.rects = append(reg.rects, box)
				foundRegion = true
				break
			}
			// Well, this region was inappropriate. Try the next one.
		}

		if !foundRegion {
			// No regions were appropriate. Create a new one.
			ri = append(ri, regionInfo{
				reg: Region{
					extents: box,
					rects:   []Box{box},
				},
				prevBand: 0,
				curBand:  0,
			})
		}
	}

	// Finish up each region: coalesce and set extents
	for j := 0; j < len(ri); j++ {
		rit := &ri[j]
		reg := &rit.reg

		// Coalesce final band
		reg.rects, _ = coalesce(reg.rects, rit.prevBand, rit.curBand)

		// Update extents from last rectangle
		if len(reg.rects) > 0 {
			lastBox := reg.rects[len(reg.rects)-1]
			if reg.extents.X2 < lastBox.X2 {
				reg.extents.X2 = lastBox.X2
			}
		}

		// Set Y extents
		if len(reg.rects) > 0 {
			reg.extents.Y1 = reg.rects[0].Y1
			reg.extents.Y2 = reg.rects[len(reg.rects)-1].Y2
		}

		// Handle single rectangle optimization
		if len(reg.rects) == 1 {
			reg.rects = nil
		}
	}

	// Step 3: Union all regions into a single region (binary merge)
	for len(ri) > 1 {
		half := len(ri) / 2
		start := len(ri) & 1 // Start from 0 if even, 1 if odd

		for j := start; j < half+start; j++ {
			reg := &ri[j].reg
			hreg := &ri[j+half].reg

			// Union hreg into reg
			regionOp(reg, reg, hreg, unionOverlap, true, true)

			// Merge extents
			if hreg.extents.X1 < reg.extents.X1 {
				reg.extents.X1 = hreg.extents.X1
			}
			if hreg.extents.Y1 < reg.extents.Y1 {
				reg.extents.Y1 = hreg.extents.Y1
			}
			if hreg.extents.X2 > reg.extents.X2 {
				reg.extents.X2 = hreg.extents.X2
			}
			if hreg.extents.Y2 > reg.extents.Y2 {
				reg.extents.Y2 = hreg.extents.Y2
			}
		}

		ri = ri[:len(ri)-half]
	}

	// Copy result to r
	if len(ri) > 0 {
		*r = ri[0].reg
	} else {
		r.Clear()
	}
}

// unionOverlap handles overlapping bands for union operation.
func unionOverlap(result *[]Box, r1, r2 []Box, y1, y2 int32) {
	i1, i2 := 0, 0
	var x1, x2 int32

	// Start with leftmost rectangle
	if r1[0].X1 < r2[0].X1 {
		x1 = r1[0].X1
		x2 = r1[0].X2
		i1++
	} else {
		x1 = r2[0].X1
		x2 = r2[0].X2
		i2++
	}

	for i1 < len(r1) || i2 < len(r2) {
		var nextX1, nextX2 int32
		if i1 < len(r1) && (i2 >= len(r2) || r1[i1].X1 < r2[i2].X1) {
			nextX1 = r1[i1].X1
			nextX2 = r1[i1].X2
			i1++
		} else {
			nextX1 = r2[i2].X1
			nextX2 = r2[i2].X2
			i2++
		}

		if nextX1 <= x2 {
			// Merge
			if nextX2 > x2 {
				x2 = nextX2
			}
		} else {
			// Add current rectangle, start new one
			*result = append(*result, Box{x1, y1, x2, y2})
			x1 = nextX1
			x2 = nextX2
		}
	}

	// Add final rectangle
	*result = append(*result, Box{x1, y1, x2, y2})
}

// intersectOverlap handles overlapping bands for intersection operation.
func intersectOverlap(result *[]Box, r1, r2 []Box, y1, y2 int32) {
	i1, i2 := 0, 0

	for i1 < len(r1) && i2 < len(r2) {
		x1 := max32(r1[i1].X1, r2[i2].X1)
		x2 := min32(r1[i1].X2, r2[i2].X2)

		if x1 < x2 {
			*result = append(*result, Box{x1, y1, x2, y2})
		}

		// Advance pointer with leftmost right edge
		if r1[i1].X2 < r2[i2].X2 {
			i1++
		} else if r2[i2].X2 < r1[i1].X2 {
			i2++
		} else {
			// Equal right edges - advance both
			i1++
			i2++
		}
	}
}

// subtractOverlap handles overlapping bands for subtraction operation.
func subtractOverlap(result *[]Box, r1, r2 []Box, y1, y2 int32) {
	i1, i2 := 0, 0
	x1 := r1[0].X1

	for i1 < len(r1) && i2 < len(r2) {
		if r2[i2].X2 <= x1 {
			// Subtrahend entirely to left: skip it
			i2++
		} else if r2[i2].X1 <= x1 {
			// Subtrahend precedes or covers left edge of minuend
			x1 = r2[i2].X2
			if x1 >= r1[i1].X2 {
				// Minuend completely covered
				i1++
				if i1 < len(r1) {
					x1 = r1[i1].X1
				}
			} else {
				i2++
			}
		} else if r2[i2].X1 < r1[i1].X2 {
			// Add uncovered part of minuend
			*result = append(*result, Box{x1, y1, r2[i2].X1, y2})
			x1 = r2[i2].X2
			if x1 >= r1[i1].X2 {
				i1++
				if i1 < len(r1) {
					x1 = r1[i1].X1
				}
			} else {
				i2++
			}
		} else {
			// Subtrahend is to the right of minuend
			if r1[i1].X2 > x1 {
				*result = append(*result, Box{x1, y1, r1[i1].X2, y2})
			}
			i1++
			if i1 < len(r1) {
				x1 = r1[i1].X1
			}
		}
	}

	// Add remaining minuend rectangles
	for i1 < len(r1) {
		if r1[i1].X2 > x1 {
			*result = append(*result, Box{x1, y1, r1[i1].X2, y2})
		}
		i1++
		if i1 < len(r1) {
			x1 = r1[i1].X1
		}
	}
}