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.cellIdToString; 20 21 import java.util.Comparator; 22 import java.util.Objects; 23 24 /** 25 * A range of S2 cell IDs consisting of a startCellId (inclusive) and an endCellId (exclusive). The 26 * start and end cell ID must have the same S2 level. This class can cope with ranges that wrap 27 * around (i.e. from face 5 to face 0), but the cell IDs provided must be valid. Subclasses may 28 * apply additional constraints. 29 */ 30 public class S2LevelRange { 31 32 /** 33 * Orders S2LevelRanges by startCellId then by endCellId. 34 */ 35 public static Comparator<? super S2LevelRange> COMPARATOR = (o1, o2) -> { 36 long diff = o2.mStartCellIdNumeric - o1.mStartCellIdNumeric; 37 if (diff < 0) { 38 return 1; 39 } else if (diff > 0) { 40 return -1; 41 } 42 long endDiff = o2.mEndCellIdNumeric - o1.mEndCellIdNumeric; 43 return endDiff < 0 ? 1 : (endDiff > 0 ? -1 : 0); 44 }; 45 46 // Inclusive 47 protected final long mStartCellId; 48 49 /** 50 * A modified value for mStartCellId that can be compared numerically against other cells of the 51 * same level to determine a natural ordering. See {@link 52 * S2CellOrdering#asUnsignedNumeric(long)}. 53 */ 54 protected final long mStartCellIdNumeric; 55 56 // Exclusive 57 protected final long mEndCellId; 58 59 /** 60 * A modified value for mEndCellId that can be compared numerically against other cells of the 61 * same level to determine ordering. See {@link S2CellOrdering#asUnsignedNumeric(long)}. 62 */ 63 protected final long mEndCellIdNumeric; 64 65 protected final int mS2Level; 66 67 /** 68 * Creates a range of S2 cell IDs from {@code startCellId} (inclusive) to {@code endCellId} 69 * (exclusive). Both values must have the same S2 level otherwise {@link 70 * IllegalArgumentException} will be thrown. 71 */ S2LevelRange(long startCellId, long endCellId)72 public S2LevelRange(long startCellId, long endCellId) { 73 S2Support.validateCellId(startCellId); 74 S2Support.validateCellId(endCellId); 75 int startS2Level = S2Support.getS2Level(startCellId); 76 int endS2Level = S2Support.getS2Level(endCellId); 77 // Validate the levels are the same. 78 if (startS2Level != endS2Level) { 79 throw new IllegalArgumentException("startCellId " + cellIdToString(startCellId) 80 + " level=" + startS2Level + " != endCellId " + cellIdToString(endCellId) 81 + " level=" + endS2Level); 82 } 83 84 // Rule out the empty range / complete range ambiguity case. 85 if (startCellId == endCellId) { 86 throw new IllegalArgumentException("A range cannot be zero length," 87 + " startCellId=" + startCellId + ", endCellId=" + endCellId); 88 } 89 long startCellIdNumeric = S2CellOrdering.asUnsignedNumeric(startCellId); 90 long endCellIdNumeric = S2CellOrdering.asUnsignedNumeric(endCellId); 91 92 mStartCellId = startCellId; 93 mStartCellIdNumeric = startCellIdNumeric; 94 mEndCellId = endCellId; 95 mEndCellIdNumeric = endCellIdNumeric; 96 mS2Level = startS2Level; 97 } 98 99 /** Returns the S2 level for this range. */ getS2Level()100 public int getS2Level() { 101 return mS2Level; 102 } 103 104 /** Returns the (inclusive) start cell ID. */ getStartCellId()105 public long getStartCellId() { 106 return mStartCellId; 107 } 108 109 /** Returns the (exclusive) end cell ID. */ getEndCellId()110 public long getEndCellId() { 111 return mEndCellId; 112 } 113 114 /** 115 * Returns {@code true} if the range contains the supplied cell ID. The cell ID must have the 116 * same S2 level as the range. 117 */ contains(long s2CellId)118 public boolean contains(long s2CellId) { 119 long level = S2Support.getS2Level(s2CellId); 120 if (level != mS2Level) { 121 throw new IllegalArgumentException(s2CellId + "(" 122 + S2Support.cellIdToString(s2CellId) + " is not at level " + mS2Level); 123 } 124 long s2CellIdNumeric = S2CellOrdering.asUnsignedNumeric(s2CellId); 125 if (mStartCellIdNumeric < mEndCellIdNumeric) { 126 return s2CellIdNumeric >= mStartCellIdNumeric && s2CellIdNumeric < mEndCellIdNumeric; 127 } else { 128 return s2CellIdNumeric >= mStartCellIdNumeric || s2CellIdNumeric < mEndCellIdNumeric; 129 } 130 } 131 132 /** 133 * Returns {@code true} if this range has a "lower" cell ID than the supplied range. The 134 * supplied range must be at the same level as this range otherwise an 135 * {@link IllegalArgumentException} is thrown. 136 */ startsBefore(S2LevelRange other)137 public boolean startsBefore(S2LevelRange other) { 138 checkSameLevel(other); 139 return this.mStartCellIdNumeric < other.mStartCellIdNumeric; 140 } 141 142 /** 143 * Returns {@code true} if the range overlaps with the supplied range. The supplied range must 144 * be at the same level as this range otherwise an {@link IllegalArgumentException} is thrown. 145 */ overlaps(S2LevelRange other)146 public boolean overlaps(S2LevelRange other) { 147 checkSameLevel(other); 148 149 // This could probably be reduced but it wouldn't make it clearer. 150 if (this.mStartCellIdNumeric < this.mEndCellIdNumeric) { 151 // "this" is a range that does not wrap around. 152 if (other.mStartCellIdNumeric < other.mEndCellIdNumeric) { 153 // "other"" is a range that does not wrap around. 154 return other.mStartCellIdNumeric < this.mEndCellIdNumeric 155 && other.mEndCellIdNumeric > this.mStartCellIdNumeric; 156 } else { 157 // "other" is a range that wraps around. 158 return other.mStartCellIdNumeric < this.mEndCellIdNumeric 159 || other.mEndCellIdNumeric > this.mStartCellIdNumeric; 160 } 161 } else { 162 // "this" is a range that wraps around. 163 if (other.mStartCellIdNumeric < other.mEndCellIdNumeric) { 164 // "other" is a range that does not wrap around. 165 return this.mStartCellIdNumeric < other.mEndCellIdNumeric 166 || this.mEndCellIdNumeric > other.mStartCellIdNumeric; 167 } else { 168 // "other" is a range that wraps around. 169 return true; 170 } 171 } 172 } 173 checkSameLevel(S2LevelRange other)174 private void checkSameLevel(S2LevelRange other) { 175 if (this.mS2Level != other.mS2Level) { 176 throw new IllegalArgumentException( 177 "Cannot compare ranges of different levels. this=" + this + ", other=" + other); 178 } 179 } 180 181 @Override equals(Object o)182 public boolean equals(Object o) { 183 if (this == o) { 184 return true; 185 } 186 if (o == null || getClass() != o.getClass()) { 187 return false; 188 } 189 S2LevelRange tzS2Range = (S2LevelRange) o; 190 return mStartCellId == tzS2Range.mStartCellId 191 && mEndCellId == tzS2Range.mEndCellId; 192 } 193 194 @Override hashCode()195 public int hashCode() { 196 return Objects.hash(mStartCellId, mEndCellId); 197 } 198 199 @Override toString()200 public String toString() { 201 return "S2LevelRange{" 202 + "mS2Level=" + mS2Level 203 + ", mStartCellId=" + cellIdToString(mStartCellId) 204 + ", mEndCellId=" + cellIdToString(mEndCellId) 205 + '}'; 206 } 207 } 208