Sergey Vasilinets | 62bb8a1 | 2017-01-25 15:24:19 -0800 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2017 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 | |
Yigit Boyar | 64db0cc | 2017-04-17 13:18:56 -0700 | [diff] [blame] | 17 | package android.arch.core.internal; |
Sergey Vasilinets | 62bb8a1 | 2017-01-25 15:24:19 -0800 | [diff] [blame] | 18 | |
| 19 | import android.support.annotation.NonNull; |
| 20 | import android.support.annotation.RestrictTo; |
| 21 | |
| 22 | import java.util.Iterator; |
| 23 | import java.util.Map; |
| 24 | import java.util.WeakHashMap; |
| 25 | |
| 26 | /** |
Sergey Vasilinets | b546e97 | 2017-07-21 12:40:50 -0700 | [diff] [blame] | 27 | * LinkedList, which pretends to be a map and supports modifications during iterations. |
Sergey Vasilinets | 62bb8a1 | 2017-01-25 15:24:19 -0800 | [diff] [blame] | 28 | * It is NOT thread safe. |
| 29 | * |
| 30 | * @param <K> Key type |
| 31 | * @param <V> Value type |
| 32 | * @hide |
| 33 | */ |
| 34 | @RestrictTo(RestrictTo.Scope.LIBRARY_GROUP) |
Sergey Vasilinets | 62bb8a1 | 2017-01-25 15:24:19 -0800 | [diff] [blame] | 35 | public class SafeIterableMap<K, V> implements Iterable<Map.Entry<K, V>> { |
| 36 | |
| 37 | private Entry<K, V> mStart; |
| 38 | private Entry<K, V> mEnd; |
| 39 | // using WeakHashMap over List<WeakReference>, so we don't have to manually remove |
| 40 | // WeakReferences that have null in them. |
Sergey Vasilinets | b546e97 | 2017-07-21 12:40:50 -0700 | [diff] [blame] | 41 | private WeakHashMap<SupportRemove<K, V>, Boolean> mIterators = new WeakHashMap<>(); |
Sergey Vasilinets | 62bb8a1 | 2017-01-25 15:24:19 -0800 | [diff] [blame] | 42 | private int mSize = 0; |
| 43 | |
Sergey Vasilinets | b546e97 | 2017-07-21 12:40:50 -0700 | [diff] [blame] | 44 | protected Entry<K, V> get(K k) { |
| 45 | Entry<K, V> currentNode = mStart; |
| 46 | while (currentNode != null) { |
| 47 | if (currentNode.mKey.equals(k)) { |
Sergey Vasilinets | 62bb8a1 | 2017-01-25 15:24:19 -0800 | [diff] [blame] | 48 | break; |
| 49 | } |
Sergey Vasilinets | b546e97 | 2017-07-21 12:40:50 -0700 | [diff] [blame] | 50 | currentNode = currentNode.mNext; |
Sergey Vasilinets | 62bb8a1 | 2017-01-25 15:24:19 -0800 | [diff] [blame] | 51 | } |
Sergey Vasilinets | b546e97 | 2017-07-21 12:40:50 -0700 | [diff] [blame] | 52 | return currentNode; |
Sergey Vasilinets | 62bb8a1 | 2017-01-25 15:24:19 -0800 | [diff] [blame] | 53 | } |
| 54 | |
| 55 | /** |
| 56 | * If the specified key is not already associated |
| 57 | * with a value, associates it with the given value. |
| 58 | * |
| 59 | * @param key key with which the specified value is to be associated |
| 60 | * @param v value to be associated with the specified key |
| 61 | * @return the previous value associated with the specified key, |
| 62 | * or {@code null} if there was no mapping for the key |
| 63 | */ |
| 64 | public V putIfAbsent(@NonNull K key, @NonNull V v) { |
Sergey Vasilinets | b546e97 | 2017-07-21 12:40:50 -0700 | [diff] [blame] | 65 | Entry<K, V> entry = get(key); |
Sergey Vasilinets | 62bb8a1 | 2017-01-25 15:24:19 -0800 | [diff] [blame] | 66 | if (entry != null) { |
| 67 | return entry.mValue; |
| 68 | } |
Sergey Vasilinets | b546e97 | 2017-07-21 12:40:50 -0700 | [diff] [blame] | 69 | put(key, v); |
| 70 | return null; |
| 71 | } |
| 72 | |
| 73 | protected Entry<K, V> put(@NonNull K key, @NonNull V v) { |
Sergey Vasilinets | 62bb8a1 | 2017-01-25 15:24:19 -0800 | [diff] [blame] | 74 | Entry<K, V> newEntry = new Entry<>(key, v); |
| 75 | mSize++; |
| 76 | if (mEnd == null) { |
| 77 | mStart = newEntry; |
| 78 | mEnd = mStart; |
Sergey Vasilinets | b546e97 | 2017-07-21 12:40:50 -0700 | [diff] [blame] | 79 | return newEntry; |
Sergey Vasilinets | 62bb8a1 | 2017-01-25 15:24:19 -0800 | [diff] [blame] | 80 | } |
| 81 | |
| 82 | mEnd.mNext = newEntry; |
| 83 | newEntry.mPrevious = mEnd; |
| 84 | mEnd = newEntry; |
Sergey Vasilinets | b546e97 | 2017-07-21 12:40:50 -0700 | [diff] [blame] | 85 | return newEntry; |
| 86 | |
Sergey Vasilinets | 62bb8a1 | 2017-01-25 15:24:19 -0800 | [diff] [blame] | 87 | } |
| 88 | |
| 89 | /** |
| 90 | * Removes the mapping for a key from this map if it is present. |
| 91 | * |
| 92 | * @param key key whose mapping is to be removed from the map |
| 93 | * @return the previous value associated with the specified key, |
| 94 | * or {@code null} if there was no mapping for the key |
| 95 | */ |
| 96 | public V remove(@NonNull K key) { |
Sergey Vasilinets | b546e97 | 2017-07-21 12:40:50 -0700 | [diff] [blame] | 97 | Entry<K, V> toRemove = get(key); |
Sergey Vasilinets | 62bb8a1 | 2017-01-25 15:24:19 -0800 | [diff] [blame] | 98 | if (toRemove == null) { |
| 99 | return null; |
| 100 | } |
| 101 | mSize--; |
| 102 | if (!mIterators.isEmpty()) { |
Sergey Vasilinets | b546e97 | 2017-07-21 12:40:50 -0700 | [diff] [blame] | 103 | for (SupportRemove<K, V> iter : mIterators.keySet()) { |
Sergey Vasilinets | 62bb8a1 | 2017-01-25 15:24:19 -0800 | [diff] [blame] | 104 | iter.supportRemove(toRemove); |
| 105 | } |
| 106 | } |
| 107 | |
| 108 | if (toRemove.mPrevious != null) { |
| 109 | toRemove.mPrevious.mNext = toRemove.mNext; |
| 110 | } else { |
| 111 | mStart = toRemove.mNext; |
| 112 | } |
| 113 | |
| 114 | if (toRemove.mNext != null) { |
| 115 | toRemove.mNext.mPrevious = toRemove.mPrevious; |
| 116 | } else { |
| 117 | mEnd = toRemove.mPrevious; |
| 118 | } |
| 119 | |
| 120 | toRemove.mNext = null; |
| 121 | toRemove.mPrevious = null; |
| 122 | return toRemove.mValue; |
| 123 | } |
| 124 | |
| 125 | /** |
| 126 | * @return the number of elements in this map |
| 127 | */ |
| 128 | public int size() { |
| 129 | return mSize; |
| 130 | } |
| 131 | |
Sergey Vasilinets | b546e97 | 2017-07-21 12:40:50 -0700 | [diff] [blame] | 132 | /** |
| 133 | * @return an ascending iterator, which doesn't include new elements added during an |
| 134 | * iteration. |
| 135 | */ |
| 136 | @NonNull |
Sergey Vasilinets | 62bb8a1 | 2017-01-25 15:24:19 -0800 | [diff] [blame] | 137 | @Override |
Sergey Vasilinets | b546e97 | 2017-07-21 12:40:50 -0700 | [diff] [blame] | 138 | public Iterator<Map.Entry<K, V>> iterator() { |
| 139 | ListIterator<K, V> iterator = new AscendingIterator<>(mStart, mEnd); |
Sergey Vasilinets | 62bb8a1 | 2017-01-25 15:24:19 -0800 | [diff] [blame] | 140 | mIterators.put(iterator, false); |
| 141 | return iterator; |
| 142 | } |
| 143 | |
Sergey Vasilinets | c43ce90 | 2017-02-15 18:45:00 -0800 | [diff] [blame] | 144 | /** |
Sergey Vasilinets | b546e97 | 2017-07-21 12:40:50 -0700 | [diff] [blame] | 145 | * @return an descending iterator, which doesn't include new elements added during an |
| 146 | * iteration. |
Sergey Vasilinets | c43ce90 | 2017-02-15 18:45:00 -0800 | [diff] [blame] | 147 | */ |
Sergey Vasilinets | b546e97 | 2017-07-21 12:40:50 -0700 | [diff] [blame] | 148 | public Iterator<Map.Entry<K, V>> descendingIterator() { |
| 149 | DescendingIterator<K, V> iterator = new DescendingIterator<>(mEnd, mStart); |
Sergey Vasilinets | c43ce90 | 2017-02-15 18:45:00 -0800 | [diff] [blame] | 150 | mIterators.put(iterator, false); |
| 151 | return iterator; |
| 152 | } |
| 153 | |
Sergey Vasilinets | b546e97 | 2017-07-21 12:40:50 -0700 | [diff] [blame] | 154 | /** |
| 155 | * return an iterator with additions. |
| 156 | */ |
| 157 | public IteratorWithAdditions iteratorWithAdditions() { |
| 158 | @SuppressWarnings("unchecked") |
| 159 | IteratorWithAdditions iterator = new IteratorWithAdditions(); |
| 160 | mIterators.put(iterator, false); |
| 161 | return iterator; |
| 162 | } |
Sergey Vasilinets | 62bb8a1 | 2017-01-25 15:24:19 -0800 | [diff] [blame] | 163 | |
Sergey Vasilinets | b546e97 | 2017-07-21 12:40:50 -0700 | [diff] [blame] | 164 | /** |
| 165 | * @return eldest added entry or null |
| 166 | */ |
| 167 | public Map.Entry<K, V> eldest() { |
| 168 | return mStart; |
| 169 | } |
Sergey Vasilinets | 62bb8a1 | 2017-01-25 15:24:19 -0800 | [diff] [blame] | 170 | |
Sergey Vasilinets | b546e97 | 2017-07-21 12:40:50 -0700 | [diff] [blame] | 171 | /** |
| 172 | * @return newest added entry or null |
| 173 | */ |
| 174 | public Map.Entry<K, V> newest() { |
| 175 | return mEnd; |
Sergey Vasilinets | 62bb8a1 | 2017-01-25 15:24:19 -0800 | [diff] [blame] | 176 | } |
| 177 | |
| 178 | @Override |
| 179 | public boolean equals(Object obj) { |
| 180 | if (obj == this) { |
| 181 | return true; |
| 182 | } |
| 183 | if (!(obj instanceof SafeIterableMap)) { |
| 184 | return false; |
| 185 | } |
| 186 | SafeIterableMap map = (SafeIterableMap) obj; |
| 187 | if (this.size() != map.size()) { |
| 188 | return false; |
| 189 | } |
Sergey Vasilinets | b546e97 | 2017-07-21 12:40:50 -0700 | [diff] [blame] | 190 | Iterator<Map.Entry<K, V>> iterator1 = iterator(); |
| 191 | Iterator iterator2 = map.iterator(); |
Sergey Vasilinets | 62bb8a1 | 2017-01-25 15:24:19 -0800 | [diff] [blame] | 192 | while (iterator1.hasNext() && iterator2.hasNext()) { |
| 193 | Map.Entry<K, V> next1 = iterator1.next(); |
| 194 | Object next2 = iterator2.next(); |
| 195 | if ((next1 == null && next2 != null) |
| 196 | || (next1 != null && !next1.equals(next2))) { |
| 197 | return false; |
| 198 | } |
| 199 | } |
| 200 | return !iterator1.hasNext() && !iterator2.hasNext(); |
| 201 | } |
| 202 | |
| 203 | @Override |
| 204 | public String toString() { |
| 205 | StringBuilder builder = new StringBuilder(); |
| 206 | builder.append("["); |
Sergey Vasilinets | b546e97 | 2017-07-21 12:40:50 -0700 | [diff] [blame] | 207 | Iterator<Map.Entry<K, V>> iterator = iterator(); |
Sergey Vasilinets | 62bb8a1 | 2017-01-25 15:24:19 -0800 | [diff] [blame] | 208 | while (iterator.hasNext()) { |
| 209 | builder.append(iterator.next().toString()); |
| 210 | if (iterator.hasNext()) { |
| 211 | builder.append(", "); |
| 212 | } |
| 213 | } |
| 214 | builder.append("]"); |
| 215 | return builder.toString(); |
| 216 | } |
| 217 | |
Sergey Vasilinets | b546e97 | 2017-07-21 12:40:50 -0700 | [diff] [blame] | 218 | private abstract static class ListIterator<K, V> implements Iterator<Map.Entry<K, V>>, |
| 219 | SupportRemove<K, V> { |
| 220 | Entry<K, V> mExpectedEnd; |
| 221 | Entry<K, V> mNext; |
| 222 | |
| 223 | ListIterator(Entry<K, V> start, Entry<K, V> expectedEnd) { |
| 224 | this.mExpectedEnd = expectedEnd; |
| 225 | this.mNext = start; |
| 226 | } |
| 227 | |
| 228 | @Override |
| 229 | public boolean hasNext() { |
| 230 | return mNext != null; |
| 231 | } |
| 232 | |
| 233 | @Override |
| 234 | public void supportRemove(@NonNull Entry<K, V> entry) { |
| 235 | if (mExpectedEnd == entry && entry == mNext) { |
| 236 | mNext = null; |
| 237 | mExpectedEnd = null; |
| 238 | } |
| 239 | |
| 240 | if (mExpectedEnd == entry) { |
| 241 | mExpectedEnd = backward(mExpectedEnd); |
| 242 | } |
| 243 | |
| 244 | if (mNext == entry) { |
| 245 | mNext = nextNode(); |
| 246 | } |
| 247 | } |
| 248 | |
| 249 | private Entry<K, V> nextNode() { |
| 250 | if (mNext == mExpectedEnd || mExpectedEnd == null) { |
| 251 | return null; |
| 252 | } |
| 253 | return forward(mNext); |
| 254 | } |
| 255 | |
| 256 | @Override |
| 257 | public Map.Entry<K, V> next() { |
| 258 | Map.Entry<K, V> result = mNext; |
| 259 | mNext = nextNode(); |
| 260 | return result; |
| 261 | } |
| 262 | |
| 263 | abstract Entry<K, V> forward(Entry<K, V> entry); |
| 264 | |
| 265 | abstract Entry<K, V> backward(Entry<K, V> entry); |
| 266 | } |
| 267 | |
| 268 | static class AscendingIterator<K, V> extends ListIterator<K, V> { |
| 269 | AscendingIterator(Entry<K, V> start, Entry<K, V> expectedEnd) { |
| 270 | super(start, expectedEnd); |
| 271 | } |
| 272 | |
| 273 | @Override |
| 274 | Entry<K, V> forward(Entry<K, V> entry) { |
| 275 | return entry.mNext; |
| 276 | } |
| 277 | |
| 278 | @Override |
| 279 | Entry<K, V> backward(Entry<K, V> entry) { |
| 280 | return entry.mPrevious; |
| 281 | } |
| 282 | } |
| 283 | |
| 284 | private static class DescendingIterator<K, V> extends ListIterator<K, V> { |
| 285 | |
| 286 | DescendingIterator(Entry<K, V> start, Entry<K, V> expectedEnd) { |
| 287 | super(start, expectedEnd); |
| 288 | } |
| 289 | |
| 290 | @Override |
| 291 | Entry<K, V> forward(Entry<K, V> entry) { |
| 292 | return entry.mPrevious; |
| 293 | } |
| 294 | |
| 295 | @Override |
| 296 | Entry<K, V> backward(Entry<K, V> entry) { |
| 297 | return entry.mNext; |
| 298 | } |
| 299 | } |
| 300 | |
| 301 | private class IteratorWithAdditions implements Iterator<Map.Entry<K, V>>, SupportRemove<K, V> { |
| 302 | private Entry<K, V> mCurrent; |
Sergey Vasilinets | 3facabd | 2017-08-02 18:14:36 +0300 | [diff] [blame] | 303 | private boolean mBeforeStart = true; |
Sergey Vasilinets | b546e97 | 2017-07-21 12:40:50 -0700 | [diff] [blame] | 304 | |
| 305 | @Override |
| 306 | public void supportRemove(@NonNull Entry<K, V> entry) { |
| 307 | if (entry == mCurrent) { |
| 308 | mCurrent = mCurrent.mPrevious; |
Sergey Vasilinets | 3facabd | 2017-08-02 18:14:36 +0300 | [diff] [blame] | 309 | mBeforeStart = mCurrent == null; |
Sergey Vasilinets | b546e97 | 2017-07-21 12:40:50 -0700 | [diff] [blame] | 310 | } |
| 311 | } |
| 312 | |
| 313 | @Override |
| 314 | public boolean hasNext() { |
Sergey Vasilinets | 3facabd | 2017-08-02 18:14:36 +0300 | [diff] [blame] | 315 | if (mBeforeStart) { |
Sergey Vasilinets | b546e97 | 2017-07-21 12:40:50 -0700 | [diff] [blame] | 316 | return mStart != null; |
| 317 | } |
| 318 | return mCurrent != null && mCurrent.mNext != null; |
| 319 | } |
| 320 | |
| 321 | @Override |
| 322 | public Map.Entry<K, V> next() { |
Sergey Vasilinets | 3facabd | 2017-08-02 18:14:36 +0300 | [diff] [blame] | 323 | if (mBeforeStart) { |
| 324 | mBeforeStart = false; |
Sergey Vasilinets | b546e97 | 2017-07-21 12:40:50 -0700 | [diff] [blame] | 325 | mCurrent = mStart; |
| 326 | } else { |
| 327 | mCurrent = mCurrent != null ? mCurrent.mNext : null; |
| 328 | } |
| 329 | return mCurrent; |
| 330 | } |
| 331 | } |
| 332 | |
| 333 | interface SupportRemove<K, V> { |
| 334 | void supportRemove(@NonNull Entry<K, V> entry); |
| 335 | } |
| 336 | |
| 337 | static class Entry<K, V> implements Map.Entry<K, V> { |
Sergey Vasilinets | 62bb8a1 | 2017-01-25 15:24:19 -0800 | [diff] [blame] | 338 | @NonNull |
| 339 | final K mKey; |
| 340 | @NonNull |
| 341 | final V mValue; |
| 342 | Entry<K, V> mNext; |
| 343 | Entry<K, V> mPrevious; |
| 344 | |
| 345 | Entry(@NonNull K key, @NonNull V value) { |
| 346 | mKey = key; |
| 347 | this.mValue = value; |
| 348 | } |
| 349 | |
| 350 | @NonNull |
| 351 | @Override |
| 352 | public K getKey() { |
| 353 | return mKey; |
| 354 | } |
| 355 | |
| 356 | @NonNull |
| 357 | @Override |
| 358 | public V getValue() { |
| 359 | return mValue; |
| 360 | } |
| 361 | |
| 362 | @Override |
| 363 | public V setValue(V value) { |
| 364 | throw new UnsupportedOperationException("An entry modification is not supported"); |
| 365 | } |
| 366 | |
| 367 | @Override |
| 368 | public String toString() { |
| 369 | return mKey + "=" + mValue; |
| 370 | } |
| 371 | |
| 372 | @Override |
| 373 | public boolean equals(Object obj) { |
| 374 | if (obj == this) { |
| 375 | return true; |
| 376 | } |
| 377 | if (!(obj instanceof Entry)) { |
| 378 | return false; |
| 379 | } |
| 380 | Entry entry = (Entry) obj; |
| 381 | return mKey.equals(entry.mKey) && mValue.equals(entry.mValue); |
| 382 | } |
| 383 | } |
| 384 | } |