query.go

package region

// IsEmpty returns true if the region contains no rectangles.
func (r *Region) IsEmpty() bool {
	return !r.extents.IsValid()
}

// NotEmpty returns true if the region contains at least one rectangle.
func (r *Region) NotEmpty() bool {
	return r.extents.IsValid()
}

// Extents returns the bounding box of the entire region.
// Returns an invalid box if the region is empty.
func (r *Region) Extents() Box {
	return r.extents
}

// NumRects returns the number of rectangles in the region.
func (r *Region) NumRects() int {
	return r.numRects()
}

// Rectangles returns a copy of all rectangles in the region.
// The rectangles are in Y-X banded order.
func (r *Region) Rectangles() []Box {
	rects := r.getRects()
	if rects == nil {
		return nil
	}
	result := make([]Box, len(rects))
	copy(result, rects)
	return result
}

// ContainsPoint returns true if the point (x, y) is inside the region.
func (r *Region) ContainsPoint(x, y int32) bool {
	ok, _ := r.ContainsPointBox(x, y)
	return ok
}

// ContainsPointBox returns true if the point (x, y) is inside the region,
// along with the box that contains the point (if found).
func (r *Region) ContainsPointBox(x, y int32) (bool, Box) {
	numRects := r.numRects()

	// Check numRects == 0 or point not in extents
	if numRects == 0 || !r.extents.Contains(x, y) {
		return false, Box{}
	}

	// Single rectangle optimization
	if numRects == 1 {
		return true, r.extents
	}

	rects := r.rects // We know rects != nil since numRects > 1

	// Binary search: find first rectangle where Y2 > y (find_box_for_y)
	n := len(rects)
	lo, hi := 0, n
	for lo < hi {
		mid := (lo + hi) / 2
		if rects[mid].Y2 <= y {
			lo = mid + 1
		} else {
			hi = mid
		}
	}

	// Scan through rectangles in the band
	for i := lo; i < n; i++ {
		pbox := &rects[i]

		// If we've passed the point's Y or X, we missed it
		if y < pbox.Y1 || x < pbox.X1 {
			break
		}

		// Not far enough over yet
		if x >= pbox.X2 {
			continue
		}

		// Found it
		return true, *pbox
	}

	return false, Box{}
}

// ContainsRectangle returns the overlap relationship between the region and a box.
// Returns:
//   - OverlapOut if the box is completely outside the region
//   - OverlapIn if the box is completely inside the region
//   - OverlapPart if the box partially overlaps the region
//
// Boxes are not validated here; invalid boxes may return any OverlapType
// depending on their coordinates.
// The algorithm walks the banded rectangles to cover the box, tracking whether
// any part is covered (partIn) and any part is uncovered (partOut). It stops
// once the box is fully covered, partially covered, or disjoint.
func (r *Region) ContainsRectangle(box Box) OverlapType {
	rects := r.getRects()
	numRects := len(rects)

	// Useful optimization: check numRects == 0 or no extent overlap
	if numRects == 0 || !r.extents.Intersects(box) {
		return OverlapOut
	}

	// Single rectangle optimization
	if numRects == 1 {
		// We know that it must be OverlapIn or OverlapPart
		if r.extents.Subsumes(box) {
			return OverlapIn
		}
		return OverlapPart
	}

	partOut := false
	partIn := false

	// (x, y) starts at upper left of rect, moving to the right and down
	x := box.X1
	y := box.Y1

	// Can stop when both partOut and partIn are TRUE, or we reach box.Y2
	pboxEnd := numRects
	for pbox := 0; pbox < pboxEnd; pbox++ {
		// Getting up to speed or skipping remainder of band
		if rects[pbox].Y2 <= y {
			pbox = findBoxForY(rects, pbox, pboxEnd, y)
			if pbox == pboxEnd {
				break
			}
		}

		if rects[pbox].Y1 > y {
			partOut = true // Missed part of rectangle above
			if partIn || rects[pbox].Y1 >= box.Y2 {
				break
			}
			y = rects[pbox].Y1 // x guaranteed to be == box.X1
		}

		if rects[pbox].X2 <= x {
			continue // Not far enough over yet
		}

		if rects[pbox].X1 > x {
			partOut = true // Missed part of rectangle to left
			if partIn {
				break
			}
		}

		if rects[pbox].X1 < box.X2 {
			partIn = true // Definitely overlap
			if partOut {
				break
			}
		}

		if rects[pbox].X2 >= box.X2 {
			y = rects[pbox].Y2 // Finished with this band
			if y >= box.Y2 {
				break
			}
			x = box.X1 // Reset x out to left again
		} else {
			// Because boxes in a band are maximal width, if the first box
			// to overlap the rectangle doesn't completely cover it in that
			// band, the rectangle must be partially out, since some of it
			// will be uncovered in that band. partIn will have been set true
			// by now...
			partOut = true
			break
		}
	}

	if partIn {
		if y < box.Y2 {
			return OverlapPart
		}
		return OverlapIn
	}
	return OverlapOut
}

// findBoxForY locates the first box whose Y2 is greater than y using binary search.
// Returns end if no such box exists.
// In time O(log n), locate the first box whose y2 is greater than y.
func findBoxForY(rects []Box, begin, end int, y int32) int {
	if end == begin {
		return end
	}

	if end-begin == 1 {
		if rects[begin].Y2 > y {
			return begin
		}
		return end
	}

	mid := begin + (end-begin)/2
	if rects[mid].Y2 > y {
		// If no box is found in [begin, mid], the function
		// will return mid, which is then known to be the correct answer.
		return findBoxForY(rects, begin, mid, y)
	}
	return findBoxForY(rects, mid, end, y)
}

// Equal returns true if two regions contain the same set of rectangles.
func (r *Region) Equal(other *Region) bool {
	if r == other {
		return true
	}

	if r == nil || other == nil {
		return false
	}

	// Quick check: extents must be equal
	if !r.extents.Equal(other.extents) {
		return false
	}

	// Both empty
	if r.IsEmpty() && other.IsEmpty() {
		return true
	}

	rects1 := r.getRects()
	rects2 := other.getRects()

	if len(rects1) != len(rects2) {
		return false
	}

	for i := range rects1 {
		if !rects1[i].Equal(rects2[i]) {
			return false
		}
	}

	return true
}

// SelfCheck validates the internal consistency of the region.
// Returns true if the region is valid, false otherwise.
// This is primarily useful for debugging.
func (r *Region) SelfCheck() bool {
	if r == nil {
		return false
	}

	// Empty region is valid
	if !r.extents.IsValid() {
		return len(r.rects) == 0
	}

	rects := r.getRects()
	if len(rects) == 0 {
		return false // Valid extents but no rects
	}

	// Check that all rectangles are valid
	for _, rect := range rects {
		if !rect.IsValid() {
			return false
		}
	}

	// Check basic Y-X ordering (Y1 sorted, then X1 within same Y1)
	for i := 1; i < len(rects); i++ {
		prev := &rects[i-1]
		curr := &rects[i]

		// Check Y ordering
		if curr.Y1 < prev.Y1 {
			return false // Not sorted by Y1
		}

		// Same band: check X ordering and non-overlap
		if prev.Y1 == curr.Y1 && prev.Y2 == curr.Y2 {
			if curr.X1 < prev.X1 {
				return false // Not sorted by X1 in same band
			}
			if prev.X2 > curr.X1 {
				return false // Overlapping in same band
			}
		}
	}

	// Check that extents correctly bound all rectangles
	computedExtents := rects[0]
	for _, rect := range rects[1:] {
		computedExtents = computedExtents.Union(rect)
	}

	return r.extents.Equal(computedExtents)
}