cell_index_test.go

Documentation: github.com/golang/geo/s2

     1  // Copyright 2020 Google Inc. All rights reserved.
     2  //
     3  // Licensed under the Apache License, Version 2.0 (the "License");
     4  // you may not use this file except in compliance with the License.
     5  // You may obtain a copy of the License at
     6  //
     7  //     http://www.apache.org/licenses/LICENSE-2.0
     8  //
     9  // Unless required by applicable law or agreed to in writing, software
    10  // distributed under the License is distributed on an "AS IS" BASIS,
    11  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    12  // See the License for the specific language governing permissions and
    13  // limitations under the License.
    14  
    15  package s2
    16  
    17  import (
    18  	"reflect"
    19  	"sort"
    20  	"testing"
    21  )
    22  
    23  func cellIndexQuadraticValidate(t *testing.T, desc string, index *CellIndex, contents []cellIndexNode) {
    24  	// Verifies that the index computes the correct set of (cell_id, label) pairs
    25  	// for every possible leaf cell.  The running time of this function is
    26  	// quadratic in the size of the index.
    27  	index.Build()
    28  	verifyCellIndexCellIterator(t, desc, index)
    29  	verifyCellIndexRangeIterators(t, desc, index)
    30  	verifyCellIndexContents(t, desc, index)
    31  }
    32  
    33  // less reports whether this node is less than the other.
    34  func (c cellIndexNode) less(other cellIndexNode) bool {
    35  	if c.cellID != other.cellID {
    36  		return c.cellID < other.cellID
    37  	}
    38  	if c.label != other.label {
    39  		return c.label < other.label
    40  	}
    41  	return c.parent < other.parent
    42  }
    43  
    44  func cellIndexNodesEqual(a, b []cellIndexNode) bool {
    45  	sort.Slice(a, func(i, j int) bool {
    46  		return a[i].less(a[j])
    47  	})
    48  	sort.Slice(b, func(i, j int) bool {
    49  		return b[i].less(b[j])
    50  	})
    51  	return reflect.DeepEqual(a, b)
    52  
    53  }
    54  
    55  // copyCellIndexNodes creates a copy of the nodes so that sorting and other tests
    56  // don't alter the instance in a given CellIndex.
    57  func copyCellIndexNodes(in []cellIndexNode) []cellIndexNode {
    58  	out := make([]cellIndexNode, len(in))
    59  	copy(out, in)
    60  	return out
    61  }
    62  
    63  func verifyCellIndexCellIterator(t *testing.T, desc string, index *CellIndex) {
    64  	// TODO(roberts): Once the plain iterator is implemented, add this check.
    65  	/*
    66  		var actual []cellIndexNode
    67  		iter := NewCellIndexIterator(index)
    68  		for iter.Begin(); !iter.Done(); iter.Next() {
    69  			actual = append(actual, cellIndexNode{iter.StartID(), iter.Label())
    70  		}
    71  
    72  		want := copyCellIndexNodes(index.cellTree)
    73  		if !cellIndexNodesEqual(actual, want) {
    74  			t.Errorf("%s: cellIndexNodes not equal but should be.  %v != %v", desc, actual, want)
    75  		}
    76  	*/
    77  }
    78  
    79  func verifyCellIndexRangeIterators(t *testing.T, desc string, index *CellIndex) {
    80  	// tests Finish(), which is not otherwise tested below.
    81  	it := NewCellIndexRangeIterator(index)
    82  	it.Begin()
    83  	it.Finish()
    84  	if !it.Done() {
    85  		t.Errorf("%s: positioning iterator to finished should be done, but was not", desc)
    86  	}
    87  
    88  	// And also for non-empty ranges.
    89  	nonEmpty := NewCellIndexNonEmptyRangeIterator(index)
    90  	nonEmpty.Begin()
    91  	nonEmpty.Finish()
    92  	if !nonEmpty.Done() {
    93  		t.Errorf("%s: positioning non-empty iterator to finished should be done, but was not", desc)
    94  	}
    95  
    96  	// Iterate through all the ranges in the index.  We simultaneously iterate
    97  	// through the non-empty ranges and check that the correct ranges are found.
    98  	prevStart := CellID(0)
    99  	nonEmptyPrevStart := CellID(0)
   100  
   101  	it.Begin()
   102  	nonEmpty.Begin()
   103  	for ; !it.Done(); it.Next() {
   104  		// Check that seeking in the current range takes us to this range.
   105  		it2 := NewCellIndexRangeIterator(index)
   106  		start := it.StartID()
   107  		it2.Seek(it.StartID())
   108  		if start != it2.StartID() {
   109  			t.Errorf("%s: id: %v. id2 start: %v\nit: %+v\nit2: %+v", desc, start, it2.StartID(), it, it2)
   110  		}
   111  		it2.Seek(it.LimitID().Prev())
   112  		if start != it2.StartID() {
   113  			t.Errorf("%s: it2.Seek(%v) = %v, want %v", desc, it.LimitID().Prev(), it2.StartID(), start)
   114  		}
   115  
   116  		// And also for non-empty ranges.
   117  		nonEmpty2 := NewCellIndexNonEmptyRangeIterator(index)
   118  		nonEmptyStart := nonEmpty.StartID()
   119  		nonEmpty2.Seek(it.StartID())
   120  		if nonEmptyStart != nonEmpty2.StartID() {
   121  			t.Errorf("%s: nonEmpty2.StartID() = %v, want %v", desc, nonEmpty2.StartID(), nonEmptyStart)
   122  		}
   123  		nonEmpty2.Seek(it.LimitID().Prev())
   124  		if nonEmptyStart != nonEmpty2.StartID() {
   125  			t.Errorf("%s: nonEmpty2.StartID() = %v, want %v", desc, nonEmpty2.StartID(), nonEmptyStart)
   126  		}
   127  
   128  		// Test Prev() and Next().
   129  		if it2.Prev() {
   130  			if prevStart != it2.StartID() {
   131  				t.Errorf("%s: it2.StartID() = %v, want %v", desc, it2.StartID(), prevStart)
   132  			}
   133  			it2.Next()
   134  			if start != it2.StartID() {
   135  				t.Errorf("%s: it2.StartID() = %v, want %v", desc, it2.StartID(), start)
   136  			}
   137  		} else {
   138  			if start != it2.StartID() {
   139  				t.Errorf("%s: it2.StartID() = %v, want %v", desc, it2.StartID(), start)
   140  			}
   141  			if 0 != prevStart {
   142  				t.Errorf("%s: prevStart = %v, want %v", desc, prevStart, 0)
   143  			}
   144  		}
   145  
   146  		// And also for non-empty ranges.
   147  		if nonEmpty2.Prev() {
   148  			if nonEmptyPrevStart != nonEmpty2.StartID() {
   149  				t.Errorf("%s: nonEmpty2.StartID() = %v, want %v", desc, nonEmpty2.StartID(), nonEmptyPrevStart)
   150  			}
   151  			nonEmpty2.Next()
   152  			if nonEmptyStart != nonEmpty2.StartID() {
   153  				t.Errorf("%s: nonEmpty2.StartID() = %v, want %v", desc, nonEmpty2.StartID(), nonEmptyStart)
   154  			}
   155  		} else {
   156  			if nonEmptyStart != nonEmpty2.StartID() {
   157  				t.Errorf("%s: nonEmpty2.StartID() = %v, want %v", desc, nonEmpty2.StartID(), nonEmptyStart)
   158  			}
   159  			if nonEmptyPrevStart != 0 {
   160  				t.Errorf("%s: nonEmptyPrevStart = %v, want 0", desc, nonEmptyPrevStart)
   161  			}
   162  		}
   163  
   164  		// Keep the non-empty iterator synchronized with the regular one.
   165  		if !it.IsEmpty() {
   166  			if it.StartID() != nonEmpty.StartID() {
   167  				t.Errorf("%s: it.StartID = %v, want %v", desc, it.StartID(), nonEmpty.StartID())
   168  			}
   169  			if it.LimitID() != nonEmpty.LimitID() {
   170  				t.Errorf("%s: it.LimitID = %v, want %v", desc, it.LimitID(), nonEmpty.LimitID())
   171  			}
   172  			if nonEmpty.Done() {
   173  				t.Errorf("%s: nonEmpty iterator should not be done but was", desc)
   174  			}
   175  			nonEmptyPrevStart = nonEmptyStart
   176  			nonEmpty.Next()
   177  		}
   178  		prevStart = start
   179  	}
   180  
   181  	// Verify that the NonEmptyRangeIterator is also finished.
   182  	if !nonEmpty.Done() {
   183  		t.Errorf("%s: non empty iterator should have also finished", desc)
   184  	}
   185  }
   186  
   187  // verifies that RangeIterator and ContentsIterator can be used to determine
   188  // the exact set of (s2cell_id, label) pairs that contain any leaf cell.
   189  func verifyCellIndexContents(t *testing.T, desc string, index *CellIndex) {
   190  	// "minCellID" is the first CellID that has not been validated yet.
   191  	minCellID := CellIDFromFace(0).ChildBeginAtLevel(MaxLevel)
   192  	r := NewCellIndexRangeIterator(index)
   193  	for r.Begin(); !r.Done(); r.Next() {
   194  		if minCellID != r.StartID() {
   195  			t.Errorf("%s: minCellID should match the previous ending cellID. got %v, want %v", desc, r.StartID(), minCellID)
   196  		}
   197  		if minCellID >= r.LimitID() {
   198  			t.Errorf("%s: minCellID should be >= the end of the current range. got %v, want %v", desc, r.LimitID(), minCellID)
   199  		}
   200  		if !r.LimitID().IsLeaf() {
   201  			t.Errorf("%s: ending range cell ID should not be a leaf, but was", desc)
   202  		}
   203  
   204  		minCellID = r.LimitID()
   205  
   206  		// Build a list of expected (CellID, label) for this range.
   207  		var expected []cellIndexNode
   208  		for _, x := range index.cellTree {
   209  			// The cell contains the entire range.
   210  			if x.cellID.RangeMin() <= r.StartID() &&
   211  				x.cellID.RangeMax().Next() >= r.LimitID() {
   212  				expected = append(expected, x)
   213  			} else {
   214  				// Verify that the cell does not intersect the range.
   215  				if x.cellID.RangeMin() <= r.LimitID().Prev() &&
   216  					x.cellID.RangeMax() >= r.StartID() {
   217  					t.Errorf("%s: CellID does not interect the current range: %v <= %v && %v >= %v", desc, x.cellID.RangeMin(), r.LimitID().Prev(), x.cellID.RangeMax(), r.StartID())
   218  				}
   219  			}
   220  		}
   221  		var actual []cellIndexNode
   222  		cIter := NewCellIndexContentsIterator(index)
   223  		for cIter.StartUnion(r); !cIter.Done(); cIter.Next() {
   224  			actual = append(actual, cIter.node)
   225  		}
   226  
   227  		if !cellIndexNodesEqual(expected, actual) {
   228  			t.Errorf("%s: comparing contents iterator contents to this range: got %+v, want %+v", desc, actual, expected)
   229  		}
   230  	}
   231  
   232  	if CellIDFromFace(5).ChildEndAtLevel(MaxLevel) != minCellID {
   233  		t.Errorf("%s: the final cell should be the sentinel value, got %v", desc, minCellID)
   234  	}
   235  }
   236  
   237  func TestCellIndex(t *testing.T) {
   238  	type cellIndexTestInput struct {
   239  		cellID string
   240  		label  int32
   241  	}
   242  	tests := []struct {
   243  		label string
   244  		have  []cellIndexTestInput
   245  	}{
   246  		{
   247  			label: "Empty",
   248  		},
   249  		{
   250  			label: "One face cell",
   251  			have: []cellIndexTestInput{
   252  				{"0/", 0},
   253  			},
   254  		},
   255  
   256  		{
   257  			label: "One Leaf Cell",
   258  			have: []cellIndexTestInput{
   259  				{"1/012301230123012301230123012301", 12},
   260  			},
   261  		},
   262  		{
   263  			label: "Duplicate Values",
   264  			have: []cellIndexTestInput{
   265  				{"0/", 0},
   266  				{"0/", 0},
   267  				{"0/", 1},
   268  				{"0/", 17},
   269  			},
   270  		},
   271  		{
   272  			label: "Disjoint Cells",
   273  			have: []cellIndexTestInput{
   274  				{"0/", 0},
   275  				{"3/", 0},
   276  			},
   277  		},
   278  		{
   279  			// Tests nested cells, including cases where several cells have the same
   280  			// RangeMin or RangeMax and with randomly ordered labels.
   281  			label: "Nested Cells",
   282  			have: []cellIndexTestInput{
   283  				{"1/", 3},
   284  				{"1/0", 15},
   285  				{"1/000", 9},
   286  				{"1/00000", 11},
   287  				{"1/012", 6},
   288  				{"1/01212", 5},
   289  				{"1/312", 17},
   290  				{"1/31200", 4},
   291  				{"1/3120000", 10},
   292  				{"1/333", 20},
   293  				{"1/333333", 18},
   294  				{"5/", 3},
   295  				{"5/3", 31},
   296  				{"5/3333", 27},
   297  			},
   298  		},
   299  		{
   300  			// Checks that the contents iterator stops reporting values
   301  			// once it reaches a node of the cell tree that was visited
   302  			// by the previous call to Begin().
   303  			label: "Contents Iterator Suppresses Duplicates",
   304  			have: []cellIndexTestInput{
   305  				{"2/1", 1},
   306  				{"2/1", 2},
   307  				{"2/10", 3},
   308  				{"2/100", 4},
   309  				{"2/102", 5},
   310  				{"2/1023", 6},
   311  				{"2/31", 7},
   312  				{"2/313", 8},
   313  				{"2/3132", 9},
   314  				{"3/1", 10},
   315  				{"3/12", 11},
   316  				{"3/13", 12},
   317  			},
   318  		},
   319  	}
   320  
   321  	for _, test := range tests {
   322  		index := &CellIndex{}
   323  		for _, v := range test.have {
   324  			index.Add(CellIDFromString(v.cellID), v.label)
   325  		}
   326  		cellIndexQuadraticValidate(t, test.label, index, nil)
   327  	}
   328  }
   329  
   330  func TestCellIndexRandomCellUnions(t *testing.T) {
   331  	// Construct cell unions from random CellIDs at random levels. Note that
   332  	// because the cell level is chosen uniformly, there is a very high
   333  	// likelihood that the cell unions will overlap.
   334  	index := &CellIndex{}
   335  	for i := int32(0); i < 100; i++ {
   336  		index.AddCellUnion(randomCellUnion(10), i)
   337  	}
   338  	cellIndexQuadraticValidate(t, "Random Cell Unions", index, nil)
   339  }
   340  
   341  // TODO(roberts): Differences from C++
   342  //
   343  // Add remainder of TestCellIndexContentsIteratorSuppressesDuplicates
   344  //
   345  // additional Iterator related parts
   346  // Intersections related
   347
View as plain text