/* * Copyright 2017-2018 Uber Technologies, Inc. * * 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. */ /** @file * @brief tests H3 function `kRing` and `kRingDistances` * * usage: `testKRing` */ #include #include "algos.h" #include "baseCells.h" #include "h3Index.h" #include "test.h" #include "utility.h" static void kRing_equals_kRingInternal_assertions(H3Index h3) { for (int k = 0; k < 3; k++) { int kSz = H3_EXPORT(maxKringSize)(k); H3Index *neighbors = calloc(kSz, sizeof(H3Index)); int *distances = calloc(kSz, sizeof(int)); H3_EXPORT(kRingDistances)(h3, k, neighbors, distances); H3Index *internalNeighbors = calloc(kSz, sizeof(H3Index)); int *internalDistances = calloc(kSz, sizeof(int)); _kRingInternal(h3, k, internalNeighbors, internalDistances, kSz, 0); int found = 0; int internalFound = 0; for (int iNeighbor = 0; iNeighbor < kSz; iNeighbor++) { if (neighbors[iNeighbor] != 0) { found++; for (int iInternal = 0; iInternal < kSz; iInternal++) { if (internalNeighbors[iInternal] == neighbors[iNeighbor]) { internalFound++; t_assert(distances[iNeighbor] == internalDistances[iInternal], "External and internal agree on " "distance"); break; } } t_assert(found == internalFound, "External and internal implementations " "produce same output"); } } free(internalDistances); free(internalNeighbors); free(distances); free(neighbors); } } SUITE(kRing) { TEST(kRing0) { GeoCoord sf = {0.659966917655, 2 * 3.14159 - 2.1364398519396}; H3Index sfHex0 = H3_EXPORT(geoToH3)(&sf, 0); H3Index k1[] = {0, 0, 0, 0, 0, 0, 0}; int k1Dist[] = {0, 0, 0, 0, 0, 0, 0}; H3Index expectedK1[] = {0x8029fffffffffff, 0x801dfffffffffff, 0x8013fffffffffff, 0x8027fffffffffff, 0x8049fffffffffff, 0x8051fffffffffff, 0x8037fffffffffff}; H3_EXPORT(kRingDistances)(sfHex0, 1, k1, k1Dist); for (int i = 0; i < 7; i++) { t_assert(k1[i] != 0, "index is populated"); int inList = 0; for (int j = 0; j < 7; j++) { if (k1[i] == expectedK1[j]) { t_assert(k1Dist[i] == (k1[i] == sfHex0 ? 0 : 1), "distance is as expected"); inList++; } } t_assert(inList == 1, "index found in expected set"); } } TEST(kRing0_PolarPentagon) { H3Index polar; setH3Index(&polar, 0, 4, 0); H3Index k2[] = {0, 0, 0, 0, 0, 0, 0}; int k2Dist[] = {0, 0, 0, 0, 0, 0, 0}; H3Index expectedK2[] = {0x8009fffffffffff, 0x8007fffffffffff, 0x8001fffffffffff, 0x8011fffffffffff, 0x801ffffffffffff, 0x8019fffffffffff, 0}; H3_EXPORT(kRingDistances)(polar, 1, k2, k2Dist); int k2present = 0; for (int i = 0; i < 7; i++) { if (k2[i] != 0) { k2present++; int inList = 0; for (int j = 0; j < 7; j++) { if (k2[i] == expectedK2[j]) { t_assert(k2Dist[i] == (k2[i] == polar ? 0 : 1), "distance is as expected"); inList++; } } t_assert(inList == 1, "index found in expected set"); } } t_assert(k2present == 6, "pentagon has 5 neighbors"); } TEST(kRing1_PolarPentagon) { H3Index polar; setH3Index(&polar, 1, 4, 0); H3Index k2[] = {0, 0, 0, 0, 0, 0, 0}; int k2Dist[] = {0, 0, 0, 0, 0, 0, 0}; H3Index expectedK2[] = {0x81083ffffffffff, 0x81093ffffffffff, 0x81097ffffffffff, 0x8108fffffffffff, 0x8108bffffffffff, 0x8109bffffffffff, 0}; H3_EXPORT(kRingDistances)(polar, 1, k2, k2Dist); int k2present = 0; for (int i = 0; i < 7; i++) { if (k2[i] != 0) { k2present++; int inList = 0; for (int j = 0; j < 7; j++) { if (k2[i] == expectedK2[j]) { t_assert(k2Dist[i] == (k2[i] == polar ? 0 : 1), "distance is as expected"); inList++; } } t_assert(inList == 1, "index found in expected set"); } } t_assert(k2present == 6, "pentagon has 5 neighbors"); } TEST(kRing1_PolarPentagon_k3) { H3Index polar; setH3Index(&polar, 1, 4, 0); H3Index k2[37] = {0}; int k2Dist[37] = {0}; H3Index expectedK2[37] = {0x81013ffffffffff, 0x811fbffffffffff, 0x81193ffffffffff, 0x81097ffffffffff, 0x81003ffffffffff, 0x81183ffffffffff, 0x8111bffffffffff, 0x81077ffffffffff, 0x811f7ffffffffff, 0x81067ffffffffff, 0x81093ffffffffff, 0x811e7ffffffffff, 0x81083ffffffffff, 0x81117ffffffffff, 0x8101bffffffffff, 0x81107ffffffffff, 0x81073ffffffffff, 0x811f3ffffffffff, 0x81063ffffffffff, 0x8108fffffffffff, 0x811e3ffffffffff, 0x8119bffffffffff, 0x81113ffffffffff, 0x81017ffffffffff, 0x81103ffffffffff, 0x8109bffffffffff, 0x81197ffffffffff, 0x81007ffffffffff, 0x8108bffffffffff, 0x81187ffffffffff, 0x8107bffffffffff, 0, 0, 0, 0, 0, 0}; int expectedK2Dist[37] = {2, 3, 2, 1, 3, 3, 3, 2, 2, 3, 1, 3, 0, 2, 3, 3, 2, 2, 3, 1, 3, 3, 2, 2, 3, 1, 2, 3, 1, 3, 3, 0, 0, 0, 0, 0, 0}; H3_EXPORT(kRingDistances)(polar, 3, k2, k2Dist); int k2present = 0; for (int i = 0; i < 37; i++) { if (k2[i] != 0) { k2present++; int inList = 0; for (int j = 0; j < 37; j++) { if (k2[i] == expectedK2[j]) { t_assert(k2Dist[i] == expectedK2Dist[j], "distance is as expected"); inList++; } } t_assert(inList == 1, "index found in expected set"); } } t_assert(k2present == 31, "pentagon has 30 neighbors"); } TEST(kRing1_Pentagon_k4) { H3Index pent; setH3Index(&pent, 1, 14, 0); H3Index k2[61] = {0}; int k2Dist[61] = {0}; H3Index expectedK2[61] = {0x811d7ffffffffff, 0x810c7ffffffffff, 0x81227ffffffffff, 0x81293ffffffffff, 0x81133ffffffffff, 0x8136bffffffffff, 0x81167ffffffffff, 0x811d3ffffffffff, 0x810c3ffffffffff, 0x81223ffffffffff, 0x81477ffffffffff, 0x8128fffffffffff, 0x81367ffffffffff, 0x8112fffffffffff, 0x811cfffffffffff, 0x8123bffffffffff, 0x810dbffffffffff, 0x8112bffffffffff, 0x81473ffffffffff, 0x8128bffffffffff, 0x81363ffffffffff, 0x811cbffffffffff, 0x81237ffffffffff, 0x810d7ffffffffff, 0x81127ffffffffff, 0x8137bffffffffff, 0x81287ffffffffff, 0x8126bffffffffff, 0x81177ffffffffff, 0x810d3ffffffffff, 0x81233ffffffffff, 0x8150fffffffffff, 0x81123ffffffffff, 0x81377ffffffffff, 0x81283ffffffffff, 0x8102fffffffffff, 0x811c3ffffffffff, 0x810cfffffffffff, 0x8122fffffffffff, 0x8113bffffffffff, 0x81373ffffffffff, 0x8129bffffffffff, 0x8102bffffffffff, 0x811dbffffffffff, 0x810cbffffffffff, 0x8122bffffffffff, 0x81297ffffffffff, 0x81507ffffffffff, 0x8136fffffffffff, 0x8127bffffffffff, 0x81137ffffffffff, 0, 0}; H3_EXPORT(kRingDistances)(pent, 4, k2, k2Dist); int k2present = 0; for (int i = 0; i < 61; i++) { if (k2[i] != 0) { k2present++; int inList = 0; for (int j = 0; j < 61; j++) { if (k2[i] == expectedK2[j]) { inList++; } } t_assert(inList == 1, "index found in expected set"); } } t_assert(k2present == 51, "pentagon has 50 neighbors"); } TEST(kRing_equals_kRingInternal) { // Check that kRingDistances output matches _kRingInternal, // since kRingDistances will sometimes use a different implementation. for (int res = 0; res < 2; res++) { iterateAllIndexesAtRes(res, kRing_equals_kRingInternal_assertions); } } TEST(h3NeighborRotations_identity) { // This is undefined behavior, but it's helpful for it to make sense. H3Index origin = 0x811d7ffffffffffL; int rotations = 0; t_assert( h3NeighborRotations(origin, CENTER_DIGIT, &rotations) == origin, "Moving to self goes to self"); } TEST(cwOffsetPent) { // Try to find a case where h3NeighborRotations would not pass the // cwOffsetPent check, and would hit a line marked as unreachable. // To do this, we need to find a case that would move from one // non-pentagon base cell into the deleted k-subsequence of a pentagon // base cell, and neither of the cwOffsetPent values are the original // base cell's face. for (int pentagon = 0; pentagon < NUM_BASE_CELLS; pentagon++) { if (!_isBaseCellPentagon(pentagon)) { continue; } for (int neighbor = 0; neighbor < NUM_BASE_CELLS; neighbor++) { FaceIJK homeFaceIjk; _baseCellToFaceIjk(neighbor, &homeFaceIjk); int neighborFace = homeFaceIjk.face; // Only direction 2 needs to be checked, because that is the // only direction where we can move from digit 2 to digit 1, and // into the deleted k subsequence. t_assert( _getBaseCellNeighbor(neighbor, J_AXES_DIGIT) != pentagon || _baseCellIsCwOffset(pentagon, neighborFace), "cwOffsetPent is reachable"); } } } }