1 /* 2 * Copyright (C) 2020 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.android.timezone.location.storage.s2; 18 19 import static com.android.timezone.location.storage.s2.S2Support.getMaxCellId; 20 import static com.android.timezone.location.storage.s2.S2Support.getMinCellId; 21 22 /** A class that provides a natural ordering for S2 cell IDs. */ 23 public final class S2CellOrdering { 24 25 private static final long[] MIN_CELL_ID_NUMERIC; 26 27 private static final long[] MAX_CELL_ID_NUMERIC; 28 29 static { 30 MIN_CELL_ID_NUMERIC = new long[S2Support.MAX_S2_LEVEL + 1]; 31 MAX_CELL_ID_NUMERIC = new long[S2Support.MAX_S2_LEVEL + 1]; 32 for (int i = 0; i < MIN_CELL_ID_NUMERIC.length; i++) { 33 MIN_CELL_ID_NUMERIC[i] = asUnsignedNumeric(getMinCellId(i)); 34 MAX_CELL_ID_NUMERIC[i] = asUnsignedNumeric(getMaxCellId(i)); 35 } 36 } 37 38 S2CellOrdering()39 private S2CellOrdering() { 40 } 41 42 /** 43 * Turns a cell ID into a value that can be compared arithmetically to provide a natural order, 44 * i.e. ordered by face ID then index of the cell on that face. Necessary because face ID is 45 * stored in the top 3 MSB of a long and Java's longs are signed, leading to face 4 and 5 having 46 * negative cell IDs. 47 */ asUnsignedNumeric(long cellId)48 public static long asUnsignedNumeric(long cellId) { 49 // Convert to an unsigned integer. The LSB is only used for level 30 where it is always 1 so 50 // its always safe to do this on a valid cell ID: the value won't be meaningful, and is only 51 // good for comparing cell IDs of the same level, but ordering will be preserved. 52 return cellId >>> 1; 53 } 54 55 /** 56 * Returns the smallest value that could be returned by {@link #asUnsignedNumeric(long)} for 57 * a range of this level. 58 */ getMinCellIdNumeric(int s2Level)59 public static long getMinCellIdNumeric(int s2Level) { 60 return MIN_CELL_ID_NUMERIC[s2Level]; 61 } 62 63 /** 64 * Returns the largest value that could be returned by {@link #asUnsignedNumeric(long)} for 65 * a range of this level. 66 */ getMaxCellIdNumeric(int s2Level)67 public static long getMaxCellIdNumeric(int s2Level) { 68 return MAX_CELL_ID_NUMERIC[s2Level]; 69 } 70 } 71