summaryrefslogtreecommitdiff
path: root/vendor/github.com/golang/geo/s2/cellunion_test.go
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/github.com/golang/geo/s2/cellunion_test.go')
-rw-r--r--vendor/github.com/golang/geo/s2/cellunion_test.go723
1 files changed, 723 insertions, 0 deletions
diff --git a/vendor/github.com/golang/geo/s2/cellunion_test.go b/vendor/github.com/golang/geo/s2/cellunion_test.go
new file mode 100644
index 0000000..a48ca1b
--- /dev/null
+++ b/vendor/github.com/golang/geo/s2/cellunion_test.go
@@ -0,0 +1,723 @@
+/*
+Copyright 2014 Google Inc. All rights reserved.
+
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+*/
+
+package s2
+
+import (
+ "math"
+ "reflect"
+ "testing"
+
+ "github.com/golang/geo/r1"
+ "github.com/golang/geo/s1"
+)
+
+func TestCellUnionNormalization(t *testing.T) {
+ cu := CellUnion{
+ 0x80855c0000000000, // A: a cell over Pittsburg CA
+ 0x80855d0000000000, // B, a child of A
+ 0x8085634000000000, // first child of X, disjoint from A
+ 0x808563c000000000, // second child of X
+ 0x80855dc000000000, // a child of B
+ 0x808562c000000000, // third child of X
+ 0x8085624000000000, // fourth child of X
+ 0x80855d0000000000, // B again
+ }
+ exp := CellUnion{
+ 0x80855c0000000000, // A
+ 0x8085630000000000, // X
+ }
+ cu.Normalize()
+ if !reflect.DeepEqual(cu, exp) {
+ t.Errorf("got %v, want %v", cu, exp)
+ }
+
+ // add a redundant cell
+ /* TODO(dsymonds)
+ cu.Add(0x808562c000000000)
+ if !reflect.DeepEqual(cu, exp) {
+ t.Errorf("after redundant add, got %v, want %v", cu, exp)
+ }
+ */
+}
+
+func TestCellUnionBasic(t *testing.T) {
+ empty := CellUnion{}
+ empty.Normalize()
+ if len(empty) != 0 {
+ t.Errorf("empty CellUnion had %d cells, want 0", len(empty))
+ }
+
+ face1ID := CellIDFromFace(1)
+ face1Cell := CellFromCellID(face1ID)
+ face1Union := CellUnion{face1ID}
+ face1Union.Normalize()
+ if len(face1Union) != 1 {
+ t.Errorf("%v had %d cells, want 1", face1Union, len(face1Union))
+ }
+ if face1ID != face1Union[0] {
+ t.Errorf("%v[0] = %v, want %v", face1Union, face1Union[0], face1ID)
+ }
+ if got := face1Union.ContainsCell(face1Cell); !got {
+ t.Errorf("%v.ContainsCell(%v) = %t, want %t", face1Union, face1Cell, got, true)
+ }
+
+ face2ID := CellIDFromFace(2)
+ face2Cell := CellFromCellID(face2ID)
+ face2Union := CellUnion{face2ID}
+ face2Union.Normalize()
+ if len(face2Union) != 1 {
+ t.Errorf("%v had %d cells, want 1", face2Union, len(face2Union))
+ }
+ if face2ID != face2Union[0] {
+ t.Errorf("%v[0] = %v, want %v", face2Union, face2Union[0], face2ID)
+ }
+
+ if got := face1Union.ContainsCell(face2Cell); got {
+ t.Errorf("%v.ContainsCell(%v) = %t, want %t", face1Union, face2Cell, got, false)
+ }
+
+}
+
+func TestCellUnion(t *testing.T) {
+ tests := []struct {
+ cells []CellID // A test CellUnion.
+ contained []CellID // List of cellIDs contained in the CellUnion.
+ overlaps []CellID // List of CellIDs that intersects the CellUnion but not contained in it.
+ disjoint []CellID // List of CellIDs that are disjoint from the CellUnion.
+ }{
+ {
+ // Single cell around NYC, and some simple nearby probes
+ cells: []CellID{0x89c25c0000000000},
+ contained: []CellID{
+ CellID(0x89c25c0000000000).ChildBegin(),
+ CellID(0x89c25c0000000000).ChildBeginAtLevel(28),
+ },
+ overlaps: []CellID{
+ CellID(0x89c25c0000000000).immediateParent(),
+ CellIDFromFace(CellID(0x89c25c0000000000).Face()), // the whole face
+ },
+ disjoint: []CellID{
+ CellID(0x89c25c0000000000).Next(), // Cell next to this one at same level
+ CellID(0x89c25c0000000000).Next().ChildBeginAtLevel(28), // Cell next to this one at deep level
+ 0x89c2700000000000, // Big(er) neighbor cell
+ 0x89e9000000000000, // Very big next door cell.
+ 0x89c1000000000000, // Very big cell, smaller value than probe
+ },
+ },
+
+ {
+ // NYC and SFO:
+ cells: []CellID{
+ 0x89c25b0000000000, // NYC
+ 0x89c2590000000000, // NYC
+ 0x89c2f70000000000, // NYC
+ 0x89c2f50000000000, // NYC
+ 0x8085870000000000, // SFO
+ 0x8085810000000000, // SFO
+ 0x808f7d0000000000, // SFO
+ 0x808f7f0000000000, // SFO
+ },
+ contained: []CellID{
+ 0x808f7ef300000000, // SFO
+ 0x808f7e5cf0000000, // SFO
+ 0x808587f000000000, // SFO
+ 0x89c25ac000000000, // NYC
+ 0x89c259a400000000, // NYC
+ 0x89c258fa10000000, // NYC
+ 0x89c258f174007000, // NYC
+ },
+ overlaps: []CellID{
+ 0x808c000000000000, // Big SFO
+ 0x89c4000000000000, // Big NYC
+ },
+ disjoint: []CellID{
+ 0x89c15a4fcb1bb000, // outside NYC
+ 0x89c15a4e4aa95000, // outside NYC
+ 0x8094000000000000, // outside SFO (big)
+ 0x8096f10000000000, // outside SFO (smaller)
+
+ 0x87c0000000000000, // Midwest very big
+ },
+ },
+ {
+ // CellUnion with cells at many levels:
+ cells: []CellID{
+ 0x8100000000000000, // starting around california
+ 0x8740000000000000, // adjacent cells at increasing
+ 0x8790000000000000, // levels, moving eastward.
+ 0x87f4000000000000,
+ 0x87f9000000000000, // going down across the midwest
+ 0x87ff400000000000,
+ 0x87ff900000000000,
+ 0x87fff40000000000,
+ 0x87fff90000000000,
+ 0x87ffff4000000000,
+ 0x87ffff9000000000,
+ 0x87fffff400000000,
+ 0x87fffff900000000,
+ 0x87ffffff40000000,
+ 0x87ffffff90000000,
+ 0x87fffffff4000000,
+ 0x87fffffff9000000,
+ 0x87ffffffff400000, // to a very small cell in Wisconsin
+ },
+ contained: []CellID{
+ 0x808f400000000000,
+ 0x80eb118b00000000,
+ 0x8136a7a11d000000,
+ 0x8136a7a11dac0000,
+ 0x876c7c0000000000,
+ 0x87f96d0000000000,
+ 0x87ffffffff400000,
+ },
+ overlaps: []CellID{
+ CellID(0x8100000000000000).immediateParent(),
+ CellID(0x8740000000000000).immediateParent(),
+ },
+ disjoint: []CellID{
+ 0x52aaaaaaab300000,
+ 0x52aaaaaaacd00000,
+ 0x87fffffffa100000,
+ 0x87ffffffed500000,
+ 0x87ffffffa0100000,
+ 0x87fffffed5540000,
+ 0x87fffffed6240000,
+ 0x52aaaacccb340000,
+ 0x87a0000400000000,
+ 0x87a000001f000000,
+ 0x87a0000029d00000,
+ 0x9500000000000000,
+ },
+ },
+ }
+ for _, test := range tests {
+ union := CellUnion(test.cells)
+ union.Normalize()
+
+ // Ensure self-containment tests are correct.
+ for _, id := range test.cells {
+ if !union.IntersectsCellID(id) {
+ t.Errorf("CellUnion %v should self-intersect %v but does not", union, id)
+ }
+ if !union.ContainsCellID(id) {
+ t.Errorf("CellUnion %v should self-contain %v but does not", union, id)
+ }
+ }
+ // Test for containment specified in test case.
+ for _, id := range test.contained {
+ if !union.IntersectsCellID(id) {
+ t.Errorf("CellUnion %v should intersect %v but does not", union, id)
+ }
+ if !union.ContainsCellID(id) {
+ t.Errorf("CellUnion %v should contain %v but does not", union, id)
+ }
+ }
+ // Make sure the CellUnion intersect these cells but do not contain.
+ for _, id := range test.overlaps {
+ if !union.IntersectsCellID(id) {
+ t.Errorf("CellUnion %v should intersect %v but does not", union, id)
+ }
+ if union.ContainsCellID(id) {
+ t.Errorf("CellUnion %v should not contain %v but does", union, id)
+ }
+ }
+ // Negative cases make sure the CellUnion neither contain nor intersect these cells
+ for _, id := range test.disjoint {
+ if union.IntersectsCellID(id) {
+ t.Errorf("CellUnion %v should not intersect %v but does", union, id)
+ }
+ if union.ContainsCellID(id) {
+ t.Errorf("CellUnion %v should not contain %v but does", union, id)
+ }
+ }
+ }
+}
+
+func addCells(id CellID, selected bool, input *[]CellID, expected *[]CellID, t *testing.T) {
+ // Decides whether to add "id" and/or some of its descendants to the test case. If "selected"
+ // is true, then the region covered by "id" *must* be added to the test case (either by adding
+ // "id" itself, or some combination of its descendants, or both). If cell ids are to the test
+ // case "input", then the corresponding expected result after simplification is added to
+ // "expected".
+
+ if id == 0 {
+ // Initial call: decide whether to add cell(s) from each face.
+ for face := 0; face < 6; face++ {
+ addCells(CellIDFromFace(face), false, input, expected, t)
+ }
+ return
+ }
+
+ if id.IsLeaf() {
+ // The oneIn() call below ensures that the parent of a leaf cell will always be selected (if
+ // we make it that far down the hierarchy).
+ if selected != true {
+ t.Errorf("id IsLeaf() and not selected")
+ }
+ *input = append(*input, id)
+ return
+ }
+
+ // The following code ensures that the probability of selecting a cell at each level is
+ // approximately the same, i.e. we test normalization of cells at all levels.
+ if !selected && oneIn(maxLevel-id.Level()) {
+ // Once a cell has been selected, the expected output is predetermined. We then make sure
+ // that cells are selected that will normalize to the desired output.
+ *expected = append(*expected, id)
+ selected = true
+
+ }
+
+ // With the rnd.OneIn() constants below, this function adds an average
+ // of 5/6 * (kMaxLevel - level) cells to "input" where "level" is the
+ // level at which the cell was first selected (level 15 on average).
+ // Therefore the average number of input cells in a test case is about
+ // (5/6 * 15 * 6) = 75. The average number of output cells is about 6.
+
+ // If a cell is selected, we add it to "input" with probability 5/6.
+ added := false
+ if selected && !oneIn(6) {
+ *input = append(*input, id)
+ added = true
+ }
+ numChildren := 0
+ for child := id.ChildBegin(); child != id.ChildEnd(); child = child.Next() {
+ // If the cell is selected, on average we recurse on 4/12 = 1/3 child.
+ // This intentionally may result in a cell and some of its children
+ // being included in the test case.
+ //
+ // If the cell is not selected, on average we recurse on one child.
+ // We also make sure that we do not recurse on all 4 children, since
+ // then we might include all 4 children in the input case by accident
+ // (in which case the expected output would not be correct).
+ recurse := false
+ if selected {
+ recurse = oneIn(12)
+ } else {
+ recurse = oneIn(4)
+ }
+ if recurse && numChildren < 3 {
+ addCells(child, selected, input, expected, t)
+ numChildren++
+ }
+ // If this cell was selected but the cell itself was not added, we
+ // must ensure that all 4 children (or some combination of their
+ // descendants) are added.
+
+ if selected && !added {
+ addCells(child, selected, input, expected, t)
+ }
+ }
+}
+
+func TestCellUnionNormalizePseudoRandom(t *testing.T) {
+ // Try a bunch of random test cases, and keep track of average statistics
+ // for normalization (to see if they agree with the analysis above).
+
+ inSum := 0
+ outSum := 0
+ iters := 2000
+
+ for i := 0; i < iters; i++ {
+ input := []CellID{}
+ expected := []CellID{}
+ addCells(CellID(0), false, &input, &expected, t)
+ inSum += len(input)
+ outSum += len(expected)
+ cellunion := CellUnion(input)
+ cellunion.Normalize()
+
+ if len(expected) != len(cellunion) {
+ t.Errorf("Expected size of union to be %d, but got %d.",
+ len(expected), len(cellunion))
+ }
+
+ // Test GetCapBound().
+ cb := cellunion.CapBound()
+ for _, ci := range cellunion {
+ if !cb.ContainsCell(CellFromCellID(ci)) {
+ t.Errorf("CapBound %v of union %v should contain cellID %v", cb, cellunion, ci)
+ }
+ }
+
+ for _, j := range input {
+ if !cellunion.ContainsCellID(j) {
+ t.Errorf("Expected containment of CellID %v", j)
+ }
+
+ if cellunion.IntersectsCellID(j) == false {
+ t.Errorf("Expected intersection with %v.", j)
+ }
+
+ if !j.isFace() {
+ if cellunion.IntersectsCellID(j.immediateParent()) == false {
+ t.Errorf("Expected intersection with parent cell %v.", j.immediateParent())
+ if j.Level() > 1 {
+ if cellunion.IntersectsCellID(j.immediateParent().immediateParent()) == false {
+ t.Errorf("Expected intersection with parent's parent %v.",
+ j.immediateParent().immediateParent())
+ }
+ if cellunion.IntersectsCellID(j.Parent(0)) == false {
+ t.Errorf("Expected intersection with parent %v at level 0.", j.Parent(0))
+ }
+ }
+ }
+ }
+
+ if !j.IsLeaf() {
+ if cellunion.ContainsCellID(j.ChildBegin()) == false {
+ t.Errorf("Expected containment of %v.", j.ChildBegin())
+ }
+ if cellunion.IntersectsCellID(j.ChildBegin()) == false {
+ t.Errorf("Expected intersection with %v.", j.ChildBegin())
+ }
+ if cellunion.ContainsCellID(j.ChildEnd().Prev()) == false {
+ t.Errorf("Expected containment of %v.", j.ChildEnd().Prev())
+ }
+ if cellunion.IntersectsCellID(j.ChildEnd().Prev()) == false {
+ t.Errorf("Expected intersection with %v.", j.ChildEnd().Prev())
+ }
+ if cellunion.ContainsCellID(j.ChildBeginAtLevel(maxLevel)) == false {
+ t.Errorf("Expected containment of %v.", j.ChildBeginAtLevel(maxLevel))
+ }
+ if cellunion.IntersectsCellID(j.ChildBeginAtLevel(maxLevel)) == false {
+ t.Errorf("Expected intersection with %v.", j.ChildBeginAtLevel(maxLevel))
+ }
+ }
+ }
+
+ for _, exp := range expected {
+ if !exp.isFace() {
+ if cellunion.ContainsCellID(exp.Parent(exp.Level() - 1)) {
+ t.Errorf("cellunion should not contain its parent %v", exp.Parent(exp.Level()-1))
+ }
+ if cellunion.ContainsCellID(exp.Parent(0)) {
+ t.Errorf("cellunion should not contain the top level parent %v", exp.Parent(0))
+ }
+ }
+ }
+
+ var test []CellID
+ var dummy []CellID
+ addCells(CellID(0), false, &test, &dummy, t)
+ for _, j := range test {
+ intersects := false
+ contains := false
+ for _, k := range expected {
+ if k.Contains(j) {
+ contains = true
+ }
+ if k.Intersects(j) {
+ intersects = true
+ }
+ }
+ if cellunion.ContainsCellID(j) != contains {
+ t.Errorf("Expected contains with %v.", (uint64)(j))
+ }
+ if cellunion.IntersectsCellID(j) != intersects {
+ t.Errorf("Expected intersection with %v.", (uint64)(j))
+ }
+ }
+ }
+ t.Logf("avg in %.2f, avg out %.2f\n", (float64)(inSum)/(float64)(iters), (float64)(outSum)/(float64)(iters))
+}
+
+func TestCellUnionDenormalize(t *testing.T) {
+ tests := []struct {
+ name string
+ minL int
+ lMod int
+ cu *CellUnion
+ exp *CellUnion
+ }{
+ {
+ "not expanded, level mod == 1",
+ 10,
+ 1,
+ &CellUnion{
+ CellIDFromFace(2).ChildBeginAtLevel(11),
+ CellIDFromFace(2).ChildBeginAtLevel(11),
+ CellIDFromFace(3).ChildBeginAtLevel(14),
+ CellIDFromFace(0).ChildBeginAtLevel(10),
+ },
+ &CellUnion{
+ CellIDFromFace(2).ChildBeginAtLevel(11),
+ CellIDFromFace(2).ChildBeginAtLevel(11),
+ CellIDFromFace(3).ChildBeginAtLevel(14),
+ CellIDFromFace(0).ChildBeginAtLevel(10),
+ },
+ },
+ {
+ "not expanded, level mod > 1",
+ 10,
+ 2,
+ &CellUnion{
+ CellIDFromFace(2).ChildBeginAtLevel(12),
+ CellIDFromFace(2).ChildBeginAtLevel(12),
+ CellIDFromFace(3).ChildBeginAtLevel(14),
+ CellIDFromFace(0).ChildBeginAtLevel(10),
+ },
+ &CellUnion{
+ CellIDFromFace(2).ChildBeginAtLevel(12),
+ CellIDFromFace(2).ChildBeginAtLevel(12),
+ CellIDFromFace(3).ChildBeginAtLevel(14),
+ CellIDFromFace(0).ChildBeginAtLevel(10),
+ },
+ },
+ {
+ "expended, (level - min_level) is not multiple of level mod",
+ 10,
+ 3,
+ &CellUnion{
+ CellIDFromFace(2).ChildBeginAtLevel(12),
+ CellIDFromFace(5).ChildBeginAtLevel(11),
+ },
+ &CellUnion{
+ CellIDFromFace(2).ChildBeginAtLevel(12).Children()[0],
+ CellIDFromFace(2).ChildBeginAtLevel(12).Children()[1],
+ CellIDFromFace(2).ChildBeginAtLevel(12).Children()[2],
+ CellIDFromFace(2).ChildBeginAtLevel(12).Children()[3],
+ CellIDFromFace(5).ChildBeginAtLevel(11).Children()[0].Children()[0],
+ CellIDFromFace(5).ChildBeginAtLevel(11).Children()[0].Children()[1],
+ CellIDFromFace(5).ChildBeginAtLevel(11).Children()[0].Children()[2],
+ CellIDFromFace(5).ChildBeginAtLevel(11).Children()[0].Children()[3],
+ CellIDFromFace(5).ChildBeginAtLevel(11).Children()[1].Children()[0],
+ CellIDFromFace(5).ChildBeginAtLevel(11).Children()[1].Children()[1],
+ CellIDFromFace(5).ChildBeginAtLevel(11).Children()[1].Children()[2],
+ CellIDFromFace(5).ChildBeginAtLevel(11).Children()[1].Children()[3],
+ CellIDFromFace(5).ChildBeginAtLevel(11).Children()[2].Children()[0],
+ CellIDFromFace(5).ChildBeginAtLevel(11).Children()[2].Children()[1],
+ CellIDFromFace(5).ChildBeginAtLevel(11).Children()[2].Children()[2],
+ CellIDFromFace(5).ChildBeginAtLevel(11).Children()[2].Children()[3],
+ CellIDFromFace(5).ChildBeginAtLevel(11).Children()[3].Children()[0],
+ CellIDFromFace(5).ChildBeginAtLevel(11).Children()[3].Children()[1],
+ CellIDFromFace(5).ChildBeginAtLevel(11).Children()[3].Children()[2],
+ CellIDFromFace(5).ChildBeginAtLevel(11).Children()[3].Children()[3],
+ },
+ },
+ {
+ "expended, level < min_level",
+ 10,
+ 3,
+ &CellUnion{
+ CellIDFromFace(2).ChildBeginAtLevel(9),
+ },
+ &CellUnion{
+ CellIDFromFace(2).ChildBeginAtLevel(9).Children()[0],
+ CellIDFromFace(2).ChildBeginAtLevel(9).Children()[1],
+ CellIDFromFace(2).ChildBeginAtLevel(9).Children()[2],
+ CellIDFromFace(2).ChildBeginAtLevel(9).Children()[3],
+ },
+ },
+ }
+ for _, test := range tests {
+ if test.cu.Denormalize(test.minL, test.lMod); !reflect.DeepEqual(test.cu, test.exp) {
+ t.Errorf("test: %s; got %v, want %v", test.name, test.cu, test.exp)
+ }
+ }
+}
+
+func TestCellUnionRectBound(t *testing.T) {
+ tests := []struct {
+ cu *CellUnion
+ want Rect
+ }{
+ {&CellUnion{}, EmptyRect()},
+ {
+ &CellUnion{CellIDFromFace(1)},
+ Rect{
+ r1.Interval{-math.Pi / 4, math.Pi / 4},
+ s1.Interval{math.Pi / 4, 3 * math.Pi / 4},
+ },
+ },
+ {
+ &CellUnion{
+ 0x808c000000000000, // Big SFO
+ },
+ Rect{
+ r1.Interval{
+ float64(s1.Degree * 34.644220547108482),
+ float64(s1.Degree * 38.011928357226651),
+ },
+ s1.Interval{
+ float64(s1.Degree * -124.508522987668428),
+ float64(s1.Degree * -121.628309835221216),
+ },
+ },
+ },
+ {
+ &CellUnion{
+ 0x89c4000000000000, // Big NYC
+ },
+ Rect{
+ r1.Interval{
+ float64(s1.Degree * 38.794595155857657),
+ float64(s1.Degree * 41.747046884651063),
+ },
+ s1.Interval{
+ float64(s1.Degree * -76.456308667788633),
+ float64(s1.Degree * -73.465162142654819),
+ },
+ },
+ },
+ {
+ &CellUnion{
+ 0x89c4000000000000, // Big NYC
+ 0x808c000000000000, // Big SFO
+ },
+ Rect{
+ r1.Interval{
+ float64(s1.Degree * 34.644220547108482),
+ float64(s1.Degree * 41.747046884651063),
+ },
+ s1.Interval{
+ float64(s1.Degree * -124.508522987668428),
+ float64(s1.Degree * -73.465162142654819),
+ },
+ },
+ },
+ }
+
+ for _, test := range tests {
+ if got := test.cu.RectBound(); !rectsApproxEqual(got, test.want, epsilon, epsilon) {
+ t.Errorf("%v.RectBound() = %v, want %v", test.cu, got, test.want)
+ }
+ }
+}
+
+func TestCellUnionLeafCellsCovered(t *testing.T) {
+ tests := []struct {
+ have []CellID
+ want int64
+ }{
+ {},
+ {
+ have: []CellID{},
+ want: 0,
+ },
+ {
+ // One leaf cell on face 0.
+ have: []CellID{
+ CellIDFromFace(0).ChildBeginAtLevel(maxLevel),
+ },
+ want: 1,
+ },
+ {
+ // Face 0 itself (which includes the previous leaf cell).
+ have: []CellID{
+ CellIDFromFace(0).ChildBeginAtLevel(maxLevel),
+ CellIDFromFace(0),
+ },
+ want: 1 << 60,
+ },
+ /*
+ TODO(roberts): Once Expand is implemented, add the two tests for these
+ // Five faces.
+ cell_union.Expand(0),
+ want: 5 << 60,
+ // Whole world.
+ cell_union.Expand(0),
+ want: 6 << 60,
+ */
+ {
+ // Add some disjoint cells.
+ have: []CellID{
+ CellIDFromFace(0).ChildBeginAtLevel(maxLevel),
+ CellIDFromFace(0),
+ CellIDFromFace(1).ChildBeginAtLevel(1),
+ CellIDFromFace(2).ChildBeginAtLevel(2),
+ CellIDFromFace(2).ChildEndAtLevel(2).Prev(),
+ CellIDFromFace(3).ChildBeginAtLevel(14),
+ CellIDFromFace(4).ChildBeginAtLevel(27),
+ CellIDFromFace(4).ChildEndAtLevel(15).Prev(),
+ CellIDFromFace(5).ChildBeginAtLevel(30),
+ },
+ want: 1 + (1 << 6) + (1 << 30) + (1 << 32) +
+ (2 << 56) + (1 << 58) + (1 << 60),
+ },
+ }
+
+ for _, test := range tests {
+ cu := CellUnion(test.have)
+ cu.Normalize()
+ if got := cu.LeafCellsCovered(); got != test.want {
+ t.Errorf("CellUnion(%v).LeafCellsCovered() = %v, want %v", cu, got, test.want)
+ }
+ }
+}
+
+func TestCellUnionFromRange(t *testing.T) {
+ for iter := 0; iter < 100; iter++ {
+ min := randomCellIDForLevel(maxLevel)
+ max := randomCellIDForLevel(maxLevel)
+ if min > max {
+ min, max = max, min
+ }
+
+ cu := CellUnionFromRange(min, max.Next())
+ if len(cu) <= 0 {
+ t.Errorf("len(CellUnionFromRange(%v, %v)) = %d, want > 0", min, max.Next(), len(cu))
+ }
+ if min != cu[0].RangeMin() {
+ t.Errorf("%v.RangeMin of CellUnion should not be below the minimum value it was created from %v", cu[0], min)
+ }
+ if max != cu[len(cu)-1].RangeMax() {
+ t.Errorf("%v.RangeMax of CellUnion should not be above the maximum value it was created from %v", cu[len(cu)-1], max)
+ }
+ for i := 1; i < len(cu); i++ {
+ if got, want := cu[i].RangeMin(), cu[i-1].RangeMax().Next(); got != want {
+ t.Errorf("%v.RangeMin() = %v, want %v", cu[i], got, want)
+ }
+ }
+ }
+
+ // Focus on test cases that generate an empty or full range.
+
+ // Test an empty range before the minimum CellID.
+ idBegin := CellIDFromFace(0).ChildBeginAtLevel(maxLevel)
+ cu := CellUnionFromRange(idBegin, idBegin)
+ if len(cu) != 0 {
+ t.Errorf("CellUnionFromRange with begin and end as the first CellID should be empty, got %d", len(cu))
+ }
+
+ // Test an empty range after the maximum CellID.
+ idEnd := CellIDFromFace(5).ChildEndAtLevel(maxLevel)
+ cu = CellUnionFromRange(idEnd, idEnd)
+ if len(cu) != 0 {
+ t.Errorf("CellUnionFromRange with begin and end as the last CellID should be empty, got %d", len(cu))
+ }
+
+ // Test the full sphere.
+ cu = CellUnionFromRange(idBegin, idEnd)
+ if len(cu) != 6 {
+ t.Errorf("CellUnionFromRange from first CellID to last CellID should have 6 cells, got %d", len(cu))
+ }
+
+ for i := 0; i < len(cu); i++ {
+ if !cu[i].isFace() {
+ t.Errorf("CellUnionFromRange for full sphere cu[%d].isFace() = %t, want %t", i, cu[i].isFace(), true)
+ }
+ }
+}
+
+func BenchmarkCellUnionFromRange(b *testing.B) {
+ x := CellIDFromFace(0).ChildBeginAtLevel(maxLevel)
+ y := CellIDFromFace(5).ChildEndAtLevel(maxLevel)
+ for i := 0; i < b.N; i++ {
+ CellUnionFromRange(x, y)
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2026-02-10 15:23:45 +0000