1 /* 2 * Copyright (C) 2017 The Libphonenumber Authors. 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 package com.google.i18n.phonenumbers.metadata.table; 17 18 import static com.google.common.base.Preconditions.checkArgument; 19 import static com.google.common.base.Preconditions.checkNotNull; 20 import static com.google.common.collect.Maps.filterValues; 21 import static com.google.common.collect.Maps.transformValues; 22 23 import com.google.common.collect.ImmutableSet; 24 import com.google.common.collect.ImmutableSortedMap; 25 import com.google.i18n.phonenumbers.metadata.RangeTree; 26 import com.google.i18n.phonenumbers.metadata.table.RangeTable.OverwriteMode; 27 import java.util.Map.Entry; 28 import java.util.SortedMap; 29 import java.util.TreeMap; 30 import javax.annotation.Nullable; 31 32 /** 33 * A mapping from category values to a set of disjoint ranges. This is used only by the RangeTable 34 * class to represent a column of values. 35 */ 36 final class DisjointRangeMap<T extends Comparable<T>> { 37 38 static final class Builder<T extends Comparable<T>> { 39 private final Column<T> column; 40 private final SortedMap<T, RangeTree> map = new TreeMap<>(); 41 // Cache of all assigned ranges, used repeatedly by RangeTable . This could be recalculated 42 // every time it's needed, but it's just as easy to keep it cached here. 43 private RangeTree assignedRanges = RangeTree.empty(); 44 Builder(Column<T> column)45 Builder(Column<T> column) { 46 this.column = checkNotNull(column); 47 } 48 49 /** 50 * Returns the ranges assigned to the given value (returns the empty range if the given value 51 * is unassigned in this column). Note that unlike table operations, it makes no sense to allow 52 * {@code null} to be used to determine the unassigned ranges, since calculating that requires 53 * knowledge of the table in which this column exists. 54 */ getRanges(Object value)55 RangeTree getRanges(Object value) { 56 T checkedValue = column.cast(checkNotNull(value)); 57 return map.getOrDefault(checkedValue, RangeTree.empty()); 58 } 59 60 /** Returns the currently assigned ranges for this column. */ getAssignedRanges()61 RangeTree getAssignedRanges() { 62 return assignedRanges; 63 } 64 65 /** 66 * Checks whether the "proposed" assignment would succeed with the specified overwrite mode 67 * (assignments always succeed if the mode is {@link OverwriteMode#ALWAYS} ALWAYS). If the 68 * given value is {@code null} and the mode is not {@code ALWAYS}, this method ensures that 69 * none of the given ranges are assigned to any value in this column. 70 * <p> 71 * This is useful as a separate method when multiple changes are to be made which cannot be 72 * allowed to fail halfway through. 73 * 74 * @throws IllegalArgumentException if the value cannot be added to the column. 75 * @throws RangeException if the write is not possible with the given mode. 76 */ checkAssign(@ullable Object value, RangeTree ranges, OverwriteMode mode)77 T checkAssign(@Nullable Object value, RangeTree ranges, OverwriteMode mode) { 78 // Always check the proposed value (for consistency). 79 T checkedValue = column.cast(value); 80 if (mode != OverwriteMode.ALWAYS) { 81 checkArgument(checkedValue != null, 82 "Assigning a null value (unassignment) with mode other than ALWAYS makes no sense: %s", 83 mode); 84 if (mode == OverwriteMode.SAME) { 85 // Don't care about ranges that are already in the map. 86 ranges = ranges.subtract(map.getOrDefault(checkedValue, RangeTree.empty())); 87 } 88 RangeException.checkDisjoint(column, checkedValue, assignedRanges, ranges, mode); 89 } 90 return checkedValue; 91 } 92 93 /** 94 * Assigns the given ranges to the specified value in this column. After a call to 95 * {@code assign()} with a non-null value it is true that: 96 * <ul> 97 * <li>The result of {@code getRanges(value)} will contain at least the given ranges. 98 * <li>No ranges assigned to any other category value will intersect with the given ranges. 99 * </ul> 100 * If ranges are "assigned" to {@code null}, it has the effect of unassigning them. 101 * 102 * @param value the category value to assign ranges to, or {@code null} to unassign. 103 * @param ranges the ranges to assign to the category value with ID {@code id}. 104 * @param mode the overwrite mode describing how to handle existing assignments. 105 * @throws IllegalArgumentException if the assignment violates the given {@link OverwriteMode}. 106 */ assign(@ullable Object value, RangeTree ranges, OverwriteMode mode)107 void assign(@Nullable Object value, RangeTree ranges, OverwriteMode mode) { 108 T checkedValue = checkAssign(value, ranges, mode); 109 // Now unassign the ranges for all other values (only necessary if mode is "ALWAYS" since in 110 // other modes we've already ensured there's no intersection). 111 if (mode == OverwriteMode.ALWAYS) { 112 RangeTree overlap = assignedRanges.intersect(ranges); 113 if (!overlap.isEmpty()) { 114 for (Entry<T, RangeTree> e : map.entrySet()) { 115 // Skip needless extra work for the value we are about to assign. 116 if (!e.getKey().equals(checkedValue)) { 117 e.setValue(e.getValue().subtract(overlap)); 118 } 119 } 120 } 121 } 122 if (checkedValue != null) { 123 map.put(checkedValue, ranges.union(map.getOrDefault(checkedValue, RangeTree.empty()))); 124 assignedRanges = assignedRanges.union(ranges); 125 } else { 126 assignedRanges = assignedRanges.subtract(ranges); 127 } 128 } 129 130 /** Builds the range map. */ build()131 DisjointRangeMap<T> build() { 132 return new DisjointRangeMap<T>(column, map, assignedRanges); 133 } 134 } 135 136 private final Column<T> column; 137 private final ImmutableSortedMap<T, RangeTree> map; 138 private final RangeTree assignedRanges; 139 DisjointRangeMap( Column<T> column, SortedMap<T, RangeTree> map, RangeTree assignedRanges)140 private DisjointRangeMap( 141 Column<T> column, SortedMap<T, RangeTree> map, RangeTree assignedRanges) { 142 this.column = checkNotNull(column); 143 this.map = ImmutableSortedMap.copyOfSorted(filterValues(map, r -> !r.isEmpty())); 144 this.assignedRanges = assignedRanges; 145 } 146 147 /** 148 * Returns the ranges assigned to the given value. 149 * 150 * @throws IllegalArgumentException if {@code value} is not a value in this category. 151 */ getRanges(Object value)152 RangeTree getRanges(Object value) { 153 return map.get(column.cast(value)); 154 } 155 156 /** Returns all values assigned to non-empty ranges in this column. */ getAssignedValues()157 ImmutableSet<T> getAssignedValues() { 158 return map.keySet(); 159 } 160 161 /** Returns the union of all assigned ranges in this column. */ getAssignedRanges()162 RangeTree getAssignedRanges() { 163 return assignedRanges; 164 } 165 166 /** Intersects this column with the given bounds. */ intersect(RangeTree bounds)167 DisjointRangeMap<T> intersect(RangeTree bounds) { 168 return new DisjointRangeMap<T>( 169 column, transformValues(map, r -> r.intersect(bounds)), assignedRanges.intersect(bounds)); 170 } 171 172 @Override equals(Object obj)173 public boolean equals(Object obj) { 174 if (!(obj instanceof DisjointRangeMap<?>)) { 175 return false; 176 } 177 // No need to check "assignedRanges" since it's just a cache of other values anyway. 178 DisjointRangeMap<?> other = (DisjointRangeMap<?>) obj; 179 return this == other || (column.equals(other.column) && map.equals(other.map)); 180 } 181 182 @Override hashCode()183 public int hashCode() { 184 return column.hashCode() ^ map.hashCode(); 185 } 186 } 187