func (cu *CellUnion) ContainsCellID(id CellID) bool {
	i := sort.Search(len(*cu), func(i int) bool { return id < (*cu)[i] })
	if i != len(*cu) && (*cu)[i].RangeMin() <= id {
		return true
	}
	return i != 0 && (*cu)[i-1].RangeMax() >= id
}
ContainsCellID reports whether the CellUnion contains the given cell ID.
Containment is defined with respect to regions, e.g. a cell contains its 4 children.

CAVEAT: If you have constructed a non-normalized CellUnion, note that groups
of 4 child cells are *not* considered to contain their parent cell. To get
this behavior you must use one of the call Normalize() explicitly.
package s2
import (
	"fmt"
	"io"
	"sort"
	"github.com/golang/geo/s1"
)
type CellUnion []CellID
func CellUnionFromRange(begin, end CellID) CellUnion {
	var cu CellUnion
	for id := begin.MaxTile(end); id != end; id = id.Next().MaxTile(end) {
		cu = append(cu, id)
	}
	return cu
}
func CellUnionFromUnion(cellUnions ...CellUnion) CellUnion {
	var cu CellUnion
	for _, cellUnion := range cellUnions {
		cu = append(cu, cellUnion...)
	}
	cu.Normalize()
	return cu
}
func CellUnionFromIntersection(x, y CellUnion) CellUnion {
	var cu CellUnion
	var i, j int
	for i < len(x) && j < len(y) {
		iMin := x[i].RangeMin()
		jMin := y[j].RangeMin()
		if iMin > jMin {
			if x[i] <= y[j].RangeMax() {
				cu = append(cu, x[i])
				i++
			} else {
				j = y.lowerBound(j+1, len(y), iMin)
				if x[i] <= y[j-1].RangeMax() {
					j--
				}
			}
		} else if jMin > iMin {
			if y[j] <= x[i].RangeMax() {
				cu = append(cu, y[j])
				j++
			} else {
				i = x.lowerBound(i+1, len(x), jMin)
				if y[j] <= x[i-1].RangeMax() {
					i--
				}
			}
		} else {
			if x[i] < y[j] {
				cu = append(cu, x[i])
				i++
			} else {
				cu = append(cu, y[j])
				j++
			}
		}
	}
	cu.Normalize()
	return cu
}
func CellUnionFromIntersectionWithCellID(x CellUnion, id CellID) CellUnion {
	var cu CellUnion
	if x.ContainsCellID(id) {
		cu = append(cu, id)
		cu.Normalize()
		return cu
	}
	idmax := id.RangeMax()
	for i := x.lowerBound(0, len(x), id.RangeMin()); i < len(x) && x[i] <= idmax; i++ {
		cu = append(cu, x[i])
	}
	cu.Normalize()
	return cu
}
func CellUnionFromDifference(x, y CellUnion) CellUnion {
	var cu CellUnion
	for _, xid := range x {
		cu.cellUnionDifferenceInternal(xid, &y)
	}
	return cu
}
func (cu *CellUnion) IsValid() bool {
	for i, cid := range *cu {
		if !cid.IsValid() {
			return false
		}
		if i == 0 {
			continue
		}
		if (*cu)[i-1].RangeMax() >= cid.RangeMin() {
			return false
		}
	}
	return true
}
func (cu *CellUnion) IsNormalized() bool {
	for i, cid := range *cu {
		if !cid.IsValid() {
			return false
		}
		if i == 0 {
			continue
		}
		if (*cu)[i-1].RangeMax() >= cid.RangeMin() {
			return false
		}
		if i < 3 {
			continue
		}
		if areSiblings((*cu)[i-3], (*cu)[i-2], (*cu)[i-1], cid) {
			return false
		}
	}
	return true
}
func (cu *CellUnion) Normalize() {
	sortCellIDs(*cu)
	output := make([]CellID, 0, len(*cu))  
	for _, ci := range *cu {
		if len(output) > 0 && output[len(output)-1].Contains(ci) {
			continue
		}
		j := len(output) - 1  
		for j >= 0 {
			if !ci.Contains(output[j]) {
				break
			}
			j--
		}
		output = output[:j+1]
		for len(output) >= 3 && areSiblings(output[len(output)-3], output[len(output)-2], output[len(output)-1], ci) {
			output = output[:len(output)-3]
			ci = ci.immediateParent()  
		}
		output = append(output, ci)
	}
	*cu = output
}
func (cu *CellUnion) IntersectsCellID(id CellID) bool {
	i := sort.Search(len(*cu), func(i int) bool { return id < (*cu)[i] })
	if i != len(*cu) && (*cu)[i].RangeMin() <= id.RangeMax() {
		return true
	}
	return i != 0 && (*cu)[i-1].RangeMax() >= id.RangeMin()
}