func projectToBoundary(u, v float64, rect r2.Rect) r2.Point {
	du0 := math.Abs(u - rect.X.Lo)
	du1 := math.Abs(u - rect.X.Hi)
	dv0 := math.Abs(v - rect.Y.Lo)
	dv1 := math.Abs(v - rect.Y.Hi)
	dmin := math.Min(math.Min(du0, du1), math.Min(dv0, dv1))
	if du0 == dmin {
		return r2.Point{rect.X.Lo, rect.Y.ClampPoint(v)}
	}
	if du1 == dmin {
		return r2.Point{rect.X.Hi, rect.Y.ClampPoint(v)}
	}
	if dv0 == dmin {
		return r2.Point{rect.X.ClampPoint(u), rect.Y.Lo}
	}
	return r2.Point{rect.X.ClampPoint(u), rect.Y.Hi}
}
projectToBoundary returns the closest point to uv on the boundary of rect.
package s2
import (
	"math"
	"reflect"
	"testing"
	"github.com/golang/geo/r2"
	"github.com/golang/geo/s1"
)
func TestCellIDFromFace(t *testing.T) {
	for face := 0; face < 6; face++ {
		fpl := CellIDFromFacePosLevel(face, 0, 0)
		f := CellIDFromFace(face)
		if fpl != f {
			t.Errorf("CellIDFromFacePosLevel(%d, 0, 0) != CellIDFromFace(%d), got %v wanted %v", face, face, f, fpl)
		}
	}
}
func TestCellIDSentinelRangeMinMax(t *testing.T) {
	s := SentinelCellID
	if got := s.RangeMin(); s != got {
		t.Errorf("sentinel.RangeMin() = %v, want %v", got, s)
	}
	if got := s.RangeMax(); s != got {
		t.Errorf("sentinel.RangeMax() = %v, want %v", got, s)
	}
}
func TestCellIDParentChildRelationships(t *testing.T) {
	ci := CellIDFromFacePosLevel(3, 0x12345678, maxLevel-4)
	if !ci.IsValid() {
		t.Errorf("CellID %v should be valid", ci)
	}
	if f := ci.Face(); f != 3 {
		t.Errorf("ci.Face() is %v, want 3", f)
	}
	if p := ci.Pos(); p != 0x12345700 {
		t.Errorf("ci.Pos() is 0x%X, want 0x12345700", p)
	}
	if l := ci.Level(); l != 26 {  
		t.Errorf("ci.Level() is %v, want 26", l)
	}
	if ci.IsLeaf() {
		t.Errorf("CellID %v should not be a leaf", ci)
	}
	if kid2 := ci.ChildBeginAtLevel(ci.Level() + 2).Pos(); kid2 != 0x12345610 {
		t.Errorf("child two levels down is 0x%X, want 0x12345610", kid2)
	}
	if kid0 := ci.ChildBegin().Pos(); kid0 != 0x12345640 {
		t.Errorf("first child is 0x%X, want 0x12345640", kid0)
	}
	if kid0 := ci.Children()[0].Pos(); kid0 != 0x12345640 {
		t.Errorf("first child is 0x%X, want 0x12345640", kid0)
	}
	if parent := ci.immediateParent().Pos(); parent != 0x12345400 {
		t.Errorf("ci.immediateParent().Pos() = 0x%X, want 0x12345400", parent)
	}
	if parent := ci.Parent(ci.Level() - 2).Pos(); parent != 0x12345000 {
		t.Errorf("ci.Parent(l-2).Pos() = 0x%X, want 0x12345000", parent)
	}
	if uint64(ci.ChildBegin()) >= uint64(ci) {
		t.Errorf("ci.ChildBegin() is 0x%X, want < 0x%X", ci.ChildBegin(), ci)
	}
	if uint64(ci.ChildEnd()) <= uint64(ci) {
		t.Errorf("ci.ChildEnd() is 0x%X, want > 0x%X", ci.ChildEnd(), ci)
	}
	if ci.ChildEnd() != ci.ChildBegin().Next().Next().Next().Next() {
		t.Errorf("ci.ChildEnd() is 0x%X, want 0x%X", ci.ChildEnd(), ci.ChildBegin().Next().Next().Next().Next())
	}
	if ci.RangeMin() != ci.ChildBeginAtLevel(maxLevel) {
		t.Errorf("ci.RangeMin() is 0x%X, want 0x%X", ci.RangeMin(), ci.ChildBeginAtLevel(maxLevel))
	}
	if ci.RangeMax().Next() != ci.ChildEndAtLevel(maxLevel) {
		t.Errorf("ci.RangeMax().Next() is 0x%X, want 0x%X", ci.RangeMax().Next(), ci.ChildEndAtLevel(maxLevel))
	}
}
func TestCellIDContainment(t *testing.T) {
	a := CellID(0x80855c0000000000)  
	b := CellID(0x80855d0000000000)  
	c := CellID(0x80855dc000000000)  
	d := CellID(0x8085630000000000)  
	tests := []struct {
		x, y                                 CellID
		xContainsY, yContainsX, xIntersectsY bool
	}{
		{a, a, true, true, true},
		{a, b, true, false, true},
		{a, c, true, false, true},
		{a, d, false, false, false},
		{b, b, true, true, true},
		{b, c, true, false, true},
		{b, d, false, false, false},
		{c, c, true, true, true},
		{c, d, false, false, false},
		{d, d, true, true, true},
	}
	should := func(b bool) string {
		if b {
			return "should"
		}
		return "should not"
	}
	for _, test := range tests {
		if test.x.Contains(test.y) != test.xContainsY {
			t.Errorf("%v %s contain %v", test.x, should(test.xContainsY), test.y)
		}
		if test.x.Intersects(test.y) != test.xIntersectsY {
			t.Errorf("%v %s intersect %v", test.x, should(test.xIntersectsY), test.y)
		}
		if test.y.Contains(test.x) != test.yContainsX {
			t.Errorf("%v %s contain %v", test.y, should(test.yContainsX), test.x)
		}
	}
}
func TestCellIDString(t *testing.T) {
	ci := CellID(0xbb04000000000000)
	if s, exp := ci.String(), "5/31200"; s != exp {
		t.Errorf("ci.String() = %q, want %q", s, exp)
	}
}
func TestCellIDFromString(t *testing.T) {
	tests := []struct {
		have string
		want CellID
	}{
		{have: "3/", want: CellIDFromFace(3)},
		{have: "0/21", want: CellIDFromFace(0).Children()[2].Children()[1]},
		{have: "4/000000000000000000000000000000", want: CellIDFromFace(4).RangeMin()},
		{have: "4/0000000000000000000000000000000", want: 0},
		{have: "", want: 0},
		{have: "7/", want: 0},
		{have: " /", want: 0},
		{have: "3:0", want: 0},
		{have: "3/ 12", want: 0},
		{have: "3/1241", want: 0},
	}
	for _, test := range tests {
		if got := cellIDFromString(test.have); got != test.want {
			t.Errorf("cellIDFromString(%q) = %v, want %v", test.have, got, test.want)
		}
	}
}
func TestCellIDLatLng(t *testing.T) {
	tests := []struct {
		id       CellID
		lat, lng float64
	}{
		{0x47a1cbd595522b39, 49.703498679, 11.770681595},
		{0x46525318b63be0f9, 55.685376759, 12.588490937},
		{0x52b30b71698e729d, 45.486546517, -93.449700022},
		{0x46ed8886cfadda85, 58.299984854, 23.049300056},
		{0x3663f18a24cbe857, 34.364439040, 108.330699969},
		{0x10a06c0a948cf5d, -30.694551352, -30.048758753},
		{0x2b2bfd076787c5df, -25.285264027, 133.823116966},
		{0xb09dff882a7809e1, -75.000000031, 0.000000133},
		{0x94daa3d000000001, -24.694439215, -47.537363213},
		{0x87a1000000000001, 38.899730392, -99.901813021},
		{0x4fc76d5000000001, 81.647200334, -55.631712940},
		{0x3b00955555555555, 10.050986518, 78.293170610},
		{0x1dcc469991555555, -34.055420593, 18.551140038},
		{0xb112966aaaaaaaab, -69.219262171, 49.670072392},
	}
	for _, test := range tests {
		l1 := LatLngFromDegrees(test.lat, test.lng)
		l2 := test.id.LatLng()
		if l1.Distance(l2) > 1e-9*s1.Degree {  
			t.Errorf("LatLng() for CellID %x (%s) : got %s, want %s", uint64(test.id), test.id, l2, l1)
		}
		c1 := test.id
		c2 := CellIDFromLatLng(l1)
		if c1 != c2 {
			t.Errorf("CellIDFromLatLng(%s) = %x (%s), want %s", l1, uint64(c2), c2, c1)
		}
	}
}
func TestCellIDEdgeNeighbors(t *testing.T) {
	faces := []int{5, 3, 2, 0}
	for i, nbr := range cellIDFromFaceIJ(1, 0, 0).Parent(0).EdgeNeighbors() {
		if !nbr.isFace() {
			t.Errorf("CellID(%d) is not a face", nbr)
		}
		if got, want := nbr.Face(), faces[i]; got != want {
			t.Errorf("CellID(%d).Face() = %d, want %d", nbr, got, want)
		}
	}
	const maxIJ = maxSize - 1
	for level := 1; level <= maxLevel; level++ {
		id := cellIDFromFaceIJ(1, 0, 0).Parent(level)
		levelSizeIJ := sizeIJ(level)
		want := []CellID{
			cellIDFromFaceIJ(5, maxIJ, maxIJ).Parent(level),
			cellIDFromFaceIJ(1, levelSizeIJ, 0).Parent(level),
			cellIDFromFaceIJ(1, 0, levelSizeIJ).Parent(level),
			cellIDFromFaceIJ(0, maxIJ, 0).Parent(level),
		}
		for i, nbr := range id.EdgeNeighbors() {
			if nbr != want[i] {
				t.Errorf("CellID(%d).EdgeNeighbors()[%d] = %v, want %v", id, i, nbr, want[i])
			}
		}
	}
}
func TestCellIDVertexNeighbors(t *testing.T) {
	id := cellIDFromPoint(PointFromCoords(0, 0, 1))
	neighbors := id.VertexNeighbors(5)
	sortCellIDs(neighbors)
	for n, nbr := range neighbors {
		i, j := 1<<29, 1<<29
		if n < 2 {
			i--
		}
		if n == 0 || n == 3 {
			j--
		}
		want := cellIDFromFaceIJ(2, i, j).Parent(5)
		if nbr != want {
			t.Errorf("CellID(%s).VertexNeighbors()[%d] = %v, want %v", id, n, nbr, want)
		}
	}
	id = CellIDFromFacePosLevel(0, 0, maxLevel)
	neighbors = id.VertexNeighbors(0)
	sortCellIDs(neighbors)
	if len(neighbors) != 3 {
		t.Errorf("len(CellID(%d).VertexNeighbors()) = %d, wanted %d", id, len(neighbors), 3)
	}
	if neighbors[0] != CellIDFromFace(0) {
		t.Errorf("CellID(%d).VertexNeighbors()[0] = %d, wanted %d", id, neighbors[0], CellIDFromFace(0))
	}
	if neighbors[1] != CellIDFromFace(4) {
		t.Errorf("CellID(%d).VertexNeighbors()[1] = %d, wanted %d", id, neighbors[1], CellIDFromFace(4))
	}
}
func dedupCellIDs(ids []CellID) []CellID {
	var out []CellID
	var prev CellID
	for _, id := range ids {
		if id != prev {
			out = append(out, id)
		}
		prev = id
	}
	return out
}
func TestCellIDAllNeighbors(t *testing.T) {
	for i := 0; i < 1000; i++ {
		id := randomCellID()
		if id.IsLeaf() {
			id = id.immediateParent()
		}
		maxDiff := minInt(6, maxLevel-id.Level()-1)
		level := id.Level() + randomUniformInt(maxDiff)
		var want []CellID
		all := id.AllNeighbors(level)
		end := id.ChildEndAtLevel(level + 1)
		for c := id.ChildBeginAtLevel(level + 1); c != end; c = c.Next() {
			all = append(all, c.immediateParent())
			want = append(want, c.VertexNeighbors(level)...)
		}
		sortCellIDs(all)
		sortCellIDs(want)
		all = dedupCellIDs(all)
		want = dedupCellIDs(want)
		if !reflect.DeepEqual(all, want) {
			t.Errorf("%v.AllNeighbors(%d) = %v, want %v", id, level, all, want)
		}
	}
}
func TestCellIDTokensNominal(t *testing.T) {
	tests := []struct {
		token string
		id    CellID
	}{
		{"1", 0x1000000000000000},
		{"3", 0x3000000000000000},
		{"14", 0x1400000000000000},
		{"41", 0x4100000000000000},
		{"094", 0x0940000000000000},
		{"537", 0x5370000000000000},
		{"3fec", 0x3fec000000000000},
		{"72f3", 0x72f3000000000000},
		{"52b8c", 0x52b8c00000000000},
		{"990ed", 0x990ed00000000000},
		{"4476dc", 0x4476dc0000000000},
		{"2a724f", 0x2a724f0000000000},
		{"7d4afc4", 0x7d4afc4000000000},
		{"b675785", 0xb675785000000000},
		{"40cd6124", 0x40cd612400000000},
		{"3ba32f81", 0x3ba32f8100000000},
		{"08f569b5c", 0x08f569b5c0000000},
		{"385327157", 0x3853271570000000},
		{"166c4d1954", 0x166c4d1954000000},
		{"96f48d8c39", 0x96f48d8c39000000},
		{"0bca3c7f74c", 0x0bca3c7f74c00000},
		{"1ae3619d12f", 0x1ae3619d12f00000},
		{"07a77802a3fc", 0x07a77802a3fc0000},
		{"4e7887ec1801", 0x4e7887ec18010000},
		{"4adad7ae74124", 0x4adad7ae74124000},
		{"90aba04afe0c5", 0x90aba04afe0c5000},
		{"8ffc3f02af305c", 0x8ffc3f02af305c00},
		{"6fa47550938183", 0x6fa4755093818300},
		{"aa80a565df5e7fc", 0xaa80a565df5e7fc0},
		{"01614b5e968e121", 0x01614b5e968e1210},
		{"aa05238e7bd3ee7c", 0xaa05238e7bd3ee7c},
		{"48a23db9c2963e5b", 0x48a23db9c2963e5b},
	}
	for _, test := range tests {
		ci := CellIDFromToken(test.token)
		if ci != test.id {
			t.Errorf("CellIDFromToken(%q) = %x, want %x", test.token, uint64(ci), uint64(test.id))
		}
		token := ci.ToToken()
		if token != test.token {
			t.Errorf("ci.ToToken = %q, want %q", token, test.token)
		}
	}
}
func TestCellIDFromTokensErrorCases(t *testing.T) {
	noneToken := CellID(0).ToToken()
	if noneToken != "X" {
		t.Errorf("CellID(0).Token() = %q, want X", noneToken)
	}
	noneID := CellIDFromToken(noneToken)
	if noneID != CellID(0) {
		t.Errorf("CellIDFromToken(%q) = %x, want 0", noneToken, uint64(noneID))
	}
	sentinel := SentinelCellID.ToToken()
	if got, want := CellIDFromToken(sentinel), SentinelCellID; got != want {
		t.Errorf("CellIDFromToken(%v) = %v, want %v", sentinel, got, want)
	}
	face7 := CellIDFromFace(7).ToToken()
	if got, want := CellIDFromToken(face7), CellIDFromFace(7); got != want {
		t.Errorf("CellIDFromToken(%v) = %v, want %v", face7, got, want)
	}
	tests := []string{
		"876b e99",
		"876bee99\n",
		"876[ee99",
		" 876bee99",
	}
	for _, test := range tests {
		ci := CellIDFromToken(test)
		if uint64(ci) != 0 {
			t.Errorf("CellIDFromToken(%q) = %x, want 0", test, uint64(ci))
		}
	}
}
func TestIJLevelToBoundUV(t *testing.T) {
	maxIJ := 1<<maxLevel - 1
	tests := []struct {
		i     int
		j     int
		level int
		want  r2.Rect
	}{
		{
			-1, -1, 0,
			r2.RectFromPoints(r2.Point{-5, -5}, r2.Point{-1, -1}),
		},
		{
			-1 * maxIJ, -1 * maxIJ, 0,
			r2.RectFromPoints(r2.Point{-5, -5}, r2.Point{-1, -1}),
		},
		{
			-1, -1, maxLevel,
			r2.RectFromPoints(r2.Point{-1.0000000024835267, -1.0000000024835267},
				r2.Point{-1, -1}),
		},
		{
			0, 0, maxLevel + 1,
			r2.RectFromPoints(r2.Point{-1, -1}, r2.Point{-1, -1}),
		},
		{
			0, 0, 0,
			r2.RectFromPoints(r2.Point{-1, -1}, r2.Point{1, 1}),
		},
		{
			0, 0, maxLevel / 2,
			r2.RectFromPoints(r2.Point{-1, -1},
				r2.Point{-0.999918621033430099, -0.999918621033430099}),
		},
		{
			0, 0, maxLevel,
			r2.RectFromPoints(r2.Point{-1, -1},
				r2.Point{-0.999999997516473060, -0.999999997516473060}),
		},
		{
			1, 1, 0,
			r2.RectFromPoints(r2.Point{-1, -1}, r2.Point{1, 1}),
		},
		{
			1, 1, maxLevel / 2,
			r2.RectFromPoints(r2.Point{-1, -1},
				r2.Point{-0.999918621033430099, -0.999918621033430099}),
		},
		{
			1, 1, maxLevel,
			r2.RectFromPoints(r2.Point{-0.9999999975164731, -0.9999999975164731},
				r2.Point{-0.9999999950329462, -0.9999999950329462}),
		},
		{
			maxIJ / 2, maxIJ / 2, 0,
			r2.RectFromPoints(r2.Point{-1, -1}, r2.Point{1, 1})},
		{
			maxIJ / 2, maxIJ / 2, maxLevel / 2,
			r2.RectFromPoints(r2.Point{-0.000040691345930099, -0.000040691345930099},
				r2.Point{0, 0})},
		{
			maxIJ / 2, maxIJ / 2, maxLevel,
			r2.RectFromPoints(r2.Point{-0.000000001241763433, -0.000000001241763433},
				r2.Point{0, 0})},
		{
			maxIJ, maxIJ, 0,
			r2.RectFromPoints(r2.Point{-1, -1}, r2.Point{1, 1}),
		},
		{
			maxIJ, maxIJ, maxLevel / 2,
			r2.RectFromPoints(r2.Point{0.999918621033430099, 0.999918621033430099},
				r2.Point{1, 1}),
		},
		{
			maxIJ, maxIJ, maxLevel,
			r2.RectFromPoints(r2.Point{0.999999997516473060, 0.999999997516473060},
				r2.Point{1, 1}),
		},
	}
	for _, test := range tests {
		uv := ijLevelToBoundUV(test.i, test.j, test.level)
		if !float64Eq(uv.X.Lo, test.want.X.Lo) ||
			!float64Eq(uv.X.Hi, test.want.X.Hi) ||
			!float64Eq(uv.Y.Lo, test.want.Y.Lo) ||
			!float64Eq(uv.Y.Hi, test.want.Y.Hi) {
			t.Errorf("ijLevelToBoundUV(%d, %d, %d), got %v, want %v",
				test.i, test.j, test.level, uv, test.want)
		}
	}
}
func TestCellIDCommonAncestorLevel(t *testing.T) {
	tests := []struct {
		ci     CellID
		other  CellID
		want   int
		wantOk bool
	}{
		{
			CellIDFromFace(0),
			CellIDFromFace(0),
			0,
			true,
		},
		{
			CellIDFromFace(0).ChildBeginAtLevel(30),
			CellIDFromFace(0).ChildBeginAtLevel(30),
			30,
			true,
		},
		{
			CellIDFromFace(0).ChildBeginAtLevel(30),
			CellIDFromFace(0),
			0,
			true,
		},
		{
			CellIDFromFace(5),
			CellIDFromFace(5).ChildEndAtLevel(30).Prev(),
			0,
			true,
		},
		{
			CellIDFromFace(0),
			CellIDFromFace(5),
			0,
			false,
		},
		{
			CellIDFromFace(2).ChildBeginAtLevel(30),
			CellIDFromFace(3).ChildBeginAtLevel(20),
			0,
			false,
		},
		{
			CellIDFromFace(5).ChildBeginAtLevel(9).Next().ChildBeginAtLevel(15),
			CellIDFromFace(5).ChildBeginAtLevel(9).ChildBeginAtLevel(20),
			8,
			true,
		},
		{
			CellIDFromFace(0).ChildBeginAtLevel(2).ChildBeginAtLevel(30),
			CellIDFromFace(0).ChildBeginAtLevel(2).Next().ChildBeginAtLevel(5),
			1,
			true,
		},
	}
	for _, test := range tests {
		if got, ok := test.ci.CommonAncestorLevel(test.other); ok != test.wantOk || got != test.want {
			t.Errorf("CellID(%v).CommonAncestorLevel(%v) = %d, %t; want %d, %t", test.ci, test.other, got, ok, test.want, test.wantOk)
		}
	}
}
func TestCellIDDistanceToBegin(t *testing.T) {
	tests := []struct {
		id   CellID
		want int64
	}{
		{
			id:   CellIDFromFace(5).ChildEndAtLevel(0),
			want: 6,
		},
		{
			id:   CellIDFromFace(5).ChildEndAtLevel(maxLevel),
			want: 6 * (1 << uint(2*maxLevel)),
		},
		{
			id:   CellIDFromFace(0).ChildBeginAtLevel(0),
			want: 0,
		},
		{
			id:   CellIDFromFace(0).ChildBeginAtLevel(maxLevel),
			want: 0,
		},
	}
	for _, test := range tests {
		if got := test.id.distanceFromBegin(); got != test.want {
			t.Errorf("%v.distanceToBegin() = %v, want %v", test.id, got, test.want)
		}
	}
	id := CellIDFromFacePosLevel(3, 0x12345678, maxLevel-4)
	if got := CellIDFromFace(0).ChildBeginAtLevel(id.Level()).Advance(id.distanceFromBegin()); got != id {
		t.Errorf("advancing from the beginning by the distance of a cell should return us to that cell. got %v, want %v", got, id)
	}
}
func TestCellIDWrapping(t *testing.T) {
	id := CellIDFromFacePosLevel(3, 0x12345678, maxLevel-4)
	tests := []struct {
		msg  string
		got  CellID
		want CellID
	}{
		{
			"test wrap from beginning to end of Hilbert curve",
			CellIDFromFace(5).ChildEndAtLevel(0).Prev(),
			CellIDFromFace(0).ChildBeginAtLevel(0).PrevWrap(),
		},
		{
			"smallest end leaf wraps to smallest first leaf using PrevWrap",
			CellIDFromFacePosLevel(5, ^uint64(0)>>faceBits, maxLevel),
			CellIDFromFace(0).ChildBeginAtLevel(maxLevel).PrevWrap(),
		},
		{
			"smallest end leaf wraps to smallest first leaf using AdvanceWrap",
			CellIDFromFacePosLevel(5, ^uint64(0)>>faceBits, maxLevel),
			CellIDFromFace(0).ChildBeginAtLevel(maxLevel).AdvanceWrap(-1),
		},
		{
			"PrevWrap is the same as AdvanceWrap(-1)",
			CellIDFromFace(0).ChildBeginAtLevel(maxLevel).AdvanceWrap(-1),
			CellIDFromFace(0).ChildBeginAtLevel(maxLevel).PrevWrap(),
		},
		{
			"Prev + NextWrap stays the same at given level",
			CellIDFromFace(0).ChildBeginAtLevel(4),
			CellIDFromFace(5).ChildEndAtLevel(4).Prev().NextWrap(),
		},
		{
			"AdvanceWrap forward and back stays the same at given level",
			CellIDFromFace(0).ChildBeginAtLevel(4),
			CellIDFromFace(5).ChildEndAtLevel(4).Advance(-1).AdvanceWrap(1),
		},
		{
			"Prev().NextWrap() stays same for first cell at level",
			CellIDFromFacePosLevel(0, 0, maxLevel),
			CellIDFromFace(5).ChildEndAtLevel(maxLevel).Prev().NextWrap(),
		},
		{
			"AdvanceWrap forward and back stays same for first cell at level",
			CellIDFromFacePosLevel(0, 0, maxLevel),
			CellIDFromFace(5).ChildEndAtLevel(maxLevel).Advance(-1).AdvanceWrap(1),
		},
		{
			"advancing 7 steps around cube should end up one past start.",
			CellIDFromFace(1),
			CellIDFromFace(0).ChildBeginAtLevel(0).AdvanceWrap(7),
		},
		{
			"twice around should end up where we started",
			CellIDFromFace(0).ChildBeginAtLevel(0),
			CellIDFromFace(0).ChildBeginAtLevel(0).AdvanceWrap(12),
		},
		{
			"backwards once around plus one step should be one before we started",
			CellIDFromFace(4),
			CellIDFromFace(5).AdvanceWrap(-7),
		},
		{
			"wrapping even multiple of times around should end where we started",
			CellIDFromFace(0).ChildBeginAtLevel(0),
			CellIDFromFace(0).ChildBeginAtLevel(0).AdvanceWrap(-12000000),
		},
		{
			"wrapping combination of even times around should end where it started",
			CellIDFromFace(0).ChildBeginAtLevel(5).AdvanceWrap(6644),
			CellIDFromFace(0).ChildBeginAtLevel(5).AdvanceWrap(-11788),
		},
		{
			"moving 256 should advance us one cell at max level",
			id.Next().ChildBeginAtLevel(maxLevel),
			id.ChildBeginAtLevel(maxLevel).AdvanceWrap(256),
		},
		{
			"wrapping by 4 times cells per face should advance 4 faces",
			CellIDFromFacePosLevel(1, 0, maxLevel),
			CellIDFromFacePosLevel(5, 0, maxLevel).AdvanceWrap(2 << (2 * maxLevel)),
		},
	}
	for _, test := range tests {
		if test.got != test.want {
			t.Errorf("%s: got %v want %v", test.msg, test.got, test.want)
		}
	}
}
func TestCellIDAdvance(t *testing.T) {
	tests := []struct {
		ci    CellID
		steps int64
		want  CellID
	}{
		{
			CellIDFromFace(0).ChildBeginAtLevel(0),
			7,
			CellIDFromFace(5).ChildEndAtLevel(0),
		},
		{
			CellIDFromFace(0).ChildBeginAtLevel(0),
			12,
			CellIDFromFace(5).ChildEndAtLevel(0),
		},
		{
			CellIDFromFace(5).ChildEndAtLevel(0),
			-7,
			CellIDFromFace(0).ChildBeginAtLevel(0),
		},
		{
			CellIDFromFace(5).ChildEndAtLevel(0),
			-12000000,
			CellIDFromFace(0).ChildBeginAtLevel(0),
		},
		{
			CellIDFromFace(0).ChildBeginAtLevel(5),
			500,
			CellIDFromFace(5).ChildEndAtLevel(5).Advance(500 - (6 << (2 * 5))),
		},
		{
			CellIDFromFacePosLevel(3, 0x12345678, maxLevel-4).ChildBeginAtLevel(maxLevel),
			256,
			CellIDFromFacePosLevel(3, 0x12345678, maxLevel-4).Next().ChildBeginAtLevel(maxLevel),
		},
		{
			CellIDFromFacePosLevel(1, 0, maxLevel),
			4 << (2 * maxLevel),
			CellIDFromFacePosLevel(5, 0, maxLevel),
		},
	}
	for _, test := range tests {
		if got := test.ci.Advance(test.steps); got != test.want {
			t.Errorf("CellID(%v).Advance(%d) = %v; want = %v", test.ci, test.steps, got, test.want)
		}
	}
}
func TestCellIDFaceSiTi(t *testing.T) {
	id := CellIDFromFacePosLevel(3, 0x12345678, maxLevel)
	for level := 0; level <= maxLevel; level++ {
		l := maxLevel - level
		want := uint32(1) << uint(level)
		mask := uint32(1)<<(uint(level)+1) - 1
		_, si, ti := id.Parent(l).faceSiTi()
		if want != si&mask {
			t.Errorf("CellID.Parent(%d).faceSiTi(), si = %b, want %b", l, si&mask, want)
		}
		if want != ti&mask {
			t.Errorf("CellID.Parent(%d).faceSiTi(), ti = %b, want %b", l, ti&mask, want)
		}
	}
}
func TestCellIDContinuity(t *testing.T) {
	const maxWalkLevel = 8
	const cellSize = 1.0 / (1 << maxWalkLevel)
	maxDist := MaxWidthMetric.Value(maxWalkLevel)
	end := CellIDFromFace(5).ChildEndAtLevel(maxWalkLevel)
	id := CellIDFromFace(0).ChildBeginAtLevel(maxWalkLevel)
	for ; id != end; id = id.Next() {
		if got := id.rawPoint().Angle(id.NextWrap().rawPoint()); float64(got) > maxDist {
			t.Errorf("%v.rawPoint().Angle(%v.NextWrap().rawPoint()) = %v > %v", id, id, got, maxDist)
		}
		if id.NextWrap() != id.AdvanceWrap(1) {
			t.Errorf("%v.NextWrap() != %v.AdvanceWrap(1) %v != %v)", id, id, id.NextWrap(), id.AdvanceWrap(1))
		}
		if id != id.NextWrap().AdvanceWrap(-1) {
			t.Errorf("%v.NextWrap().AdvanceWrap(-1) = %v want %v)", id, id.NextWrap().AdvanceWrap(-1), id)
		}
		_, u, v := xyzToFaceUV(id.rawPoint())
		if !float64Eq(math.Remainder(uvToST(u), 0.5*cellSize), 0.0) {
			t.Errorf("uvToST(%v) = %v, want %v", u, uvToST(u), 0.5*cellSize)
		}
		if !float64Eq(math.Remainder(uvToST(v), 0.5*cellSize), 0.0) {
			t.Errorf("uvToST(%v) = %v, want %v", v, uvToST(v), 0.5*cellSize)
		}
	}
}
func sampleBoundary(rect r2.Rect) (u, v float64) {
	if oneIn(2) {
		v = randomUniformFloat64(rect.Y.Lo, rect.Y.Hi)
		if oneIn(2) {
			u = rect.X.Lo
		} else {
			u = rect.X.Hi
		}
	} else {
		u = randomUniformFloat64(rect.X.Lo, rect.X.Hi)
		if oneIn(2) {
			v = rect.Y.Lo
		} else {
			v = rect.Y.Hi
		}
	}
	return u, v
}