1/* 2 * Copyright (C) 2013 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 17package android.support.v4.util; 18 19import java.lang.reflect.Array; 20import java.util.Collection; 21import java.util.Iterator; 22import java.util.Map; 23import java.util.NoSuchElementException; 24import java.util.Set; 25 26/** 27 * Helper for writing standard Java collection interfaces to a data 28 * structure like {@link ArrayMap}. 29 */ 30abstract class MapCollections<K, V> { 31 EntrySet mEntrySet; 32 KeySet mKeySet; 33 ValuesCollection mValues; 34 35 final class ArrayIterator<T> implements Iterator<T> { 36 final int mOffset; 37 int mSize; 38 int mIndex; 39 boolean mCanRemove = false; 40 41 ArrayIterator(int offset) { 42 mOffset = offset; 43 mSize = colGetSize(); 44 } 45 46 @Override 47 public boolean hasNext() { 48 return mIndex < mSize; 49 } 50 51 @Override 52 public T next() { 53 if (!hasNext()) throw new NoSuchElementException(); 54 Object res = colGetEntry(mIndex, mOffset); 55 mIndex++; 56 mCanRemove = true; 57 return (T)res; 58 } 59 60 @Override 61 public void remove() { 62 if (!mCanRemove) { 63 throw new IllegalStateException(); 64 } 65 mIndex--; 66 mSize--; 67 mCanRemove = false; 68 colRemoveAt(mIndex); 69 } 70 } 71 72 final class MapIterator implements Iterator<Map.Entry<K, V>>, Map.Entry<K, V> { 73 int mEnd; 74 int mIndex; 75 boolean mEntryValid = false; 76 77 MapIterator() { 78 mEnd = colGetSize() - 1; 79 mIndex = -1; 80 } 81 82 @Override 83 public boolean hasNext() { 84 return mIndex < mEnd; 85 } 86 87 @Override 88 public Map.Entry<K, V> next() { 89 if (!hasNext()) throw new NoSuchElementException(); 90 mIndex++; 91 mEntryValid = true; 92 return this; 93 } 94 95 @Override 96 public void remove() { 97 if (!mEntryValid) { 98 throw new IllegalStateException(); 99 } 100 colRemoveAt(mIndex); 101 mIndex--; 102 mEnd--; 103 mEntryValid = false; 104 } 105 106 @Override 107 public K getKey() { 108 if (!mEntryValid) { 109 throw new IllegalStateException( 110 "This container does not support retaining Map.Entry objects"); 111 } 112 return (K)colGetEntry(mIndex, 0); 113 } 114 115 @Override 116 public V getValue() { 117 if (!mEntryValid) { 118 throw new IllegalStateException( 119 "This container does not support retaining Map.Entry objects"); 120 } 121 return (V)colGetEntry(mIndex, 1); 122 } 123 124 @Override 125 public V setValue(V object) { 126 if (!mEntryValid) { 127 throw new IllegalStateException( 128 "This container does not support retaining Map.Entry objects"); 129 } 130 return colSetValue(mIndex, object); 131 } 132 133 @Override 134 public final boolean equals(Object o) { 135 if (!mEntryValid) { 136 throw new IllegalStateException( 137 "This container does not support retaining Map.Entry objects"); 138 } 139 if (!(o instanceof Map.Entry)) { 140 return false; 141 } 142 Map.Entry<?, ?> e = (Map.Entry<?, ?>) o; 143 return ContainerHelpers.equal(e.getKey(), colGetEntry(mIndex, 0)) 144 && ContainerHelpers.equal(e.getValue(), colGetEntry(mIndex, 1)); 145 } 146 147 @Override 148 public final int hashCode() { 149 if (!mEntryValid) { 150 throw new IllegalStateException( 151 "This container does not support retaining Map.Entry objects"); 152 } 153 final Object key = colGetEntry(mIndex, 0); 154 final Object value = colGetEntry(mIndex, 1); 155 return (key == null ? 0 : key.hashCode()) ^ 156 (value == null ? 0 : value.hashCode()); 157 } 158 159 @Override 160 public final String toString() { 161 return getKey() + "=" + getValue(); 162 } 163 } 164 165 final class EntrySet implements Set<Map.Entry<K, V>> { 166 @Override 167 public boolean add(Map.Entry<K, V> object) { 168 throw new UnsupportedOperationException(); 169 } 170 171 @Override 172 public boolean addAll(Collection<? extends Map.Entry<K, V>> collection) { 173 int oldSize = colGetSize(); 174 for (Map.Entry<K, V> entry : collection) { 175 colPut(entry.getKey(), entry.getValue()); 176 } 177 return oldSize != colGetSize(); 178 } 179 180 @Override 181 public void clear() { 182 colClear(); 183 } 184 185 @Override 186 public boolean contains(Object o) { 187 if (!(o instanceof Map.Entry)) 188 return false; 189 Map.Entry<?, ?> e = (Map.Entry<?, ?>) o; 190 int index = colIndexOfKey(e.getKey()); 191 if (index < 0) { 192 return false; 193 } 194 Object foundVal = colGetEntry(index, 1); 195 return ContainerHelpers.equal(foundVal, e.getValue()); 196 } 197 198 @Override 199 public boolean containsAll(Collection<?> collection) { 200 Iterator<?> it = collection.iterator(); 201 while (it.hasNext()) { 202 if (!contains(it.next())) { 203 return false; 204 } 205 } 206 return true; 207 } 208 209 @Override 210 public boolean isEmpty() { 211 return colGetSize() == 0; 212 } 213 214 @Override 215 public Iterator<Map.Entry<K, V>> iterator() { 216 return new MapIterator(); 217 } 218 219 @Override 220 public boolean remove(Object object) { 221 throw new UnsupportedOperationException(); 222 } 223 224 @Override 225 public boolean removeAll(Collection<?> collection) { 226 throw new UnsupportedOperationException(); 227 } 228 229 @Override 230 public boolean retainAll(Collection<?> collection) { 231 throw new UnsupportedOperationException(); 232 } 233 234 @Override 235 public int size() { 236 return colGetSize(); 237 } 238 239 @Override 240 public Object[] toArray() { 241 throw new UnsupportedOperationException(); 242 } 243 244 @Override 245 public <T> T[] toArray(T[] array) { 246 throw new UnsupportedOperationException(); 247 } 248 249 @Override 250 public boolean equals(Object object) { 251 return equalsSetHelper(this, object); 252 } 253 254 @Override 255 public int hashCode() { 256 int result = 0; 257 for (int i=colGetSize()-1; i>=0; i--) { 258 final Object key = colGetEntry(i, 0); 259 final Object value = colGetEntry(i, 1); 260 result += ( (key == null ? 0 : key.hashCode()) ^ 261 (value == null ? 0 : value.hashCode()) ); 262 } 263 return result; 264 } 265 }; 266 267 final class KeySet implements Set<K> { 268 269 @Override 270 public boolean add(K object) { 271 throw new UnsupportedOperationException(); 272 } 273 274 @Override 275 public boolean addAll(Collection<? extends K> collection) { 276 throw new UnsupportedOperationException(); 277 } 278 279 @Override 280 public void clear() { 281 colClear(); 282 } 283 284 @Override 285 public boolean contains(Object object) { 286 return colIndexOfKey(object) >= 0; 287 } 288 289 @Override 290 public boolean containsAll(Collection<?> collection) { 291 return containsAllHelper(colGetMap(), collection); 292 } 293 294 @Override 295 public boolean isEmpty() { 296 return colGetSize() == 0; 297 } 298 299 @Override 300 public Iterator<K> iterator() { 301 return new ArrayIterator<K>(0); 302 } 303 304 @Override 305 public boolean remove(Object object) { 306 int index = colIndexOfKey(object); 307 if (index >= 0) { 308 colRemoveAt(index); 309 return true; 310 } 311 return false; 312 } 313 314 @Override 315 public boolean removeAll(Collection<?> collection) { 316 return removeAllHelper(colGetMap(), collection); 317 } 318 319 @Override 320 public boolean retainAll(Collection<?> collection) { 321 return retainAllHelper(colGetMap(), collection); 322 } 323 324 @Override 325 public int size() { 326 return colGetSize(); 327 } 328 329 @Override 330 public Object[] toArray() { 331 return toArrayHelper(0); 332 } 333 334 @Override 335 public <T> T[] toArray(T[] array) { 336 return toArrayHelper(array, 0); 337 } 338 339 @Override 340 public boolean equals(Object object) { 341 return equalsSetHelper(this, object); 342 } 343 344 @Override 345 public int hashCode() { 346 int result = 0; 347 for (int i=colGetSize()-1; i>=0; i--) { 348 Object obj = colGetEntry(i, 0); 349 result += obj == null ? 0 : obj.hashCode(); 350 } 351 return result; 352 } 353 }; 354 355 final class ValuesCollection implements Collection<V> { 356 357 @Override 358 public boolean add(V object) { 359 throw new UnsupportedOperationException(); 360 } 361 362 @Override 363 public boolean addAll(Collection<? extends V> collection) { 364 throw new UnsupportedOperationException(); 365 } 366 367 @Override 368 public void clear() { 369 colClear(); 370 } 371 372 @Override 373 public boolean contains(Object object) { 374 return colIndexOfValue(object) >= 0; 375 } 376 377 @Override 378 public boolean containsAll(Collection<?> collection) { 379 Iterator<?> it = collection.iterator(); 380 while (it.hasNext()) { 381 if (!contains(it.next())) { 382 return false; 383 } 384 } 385 return true; 386 } 387 388 @Override 389 public boolean isEmpty() { 390 return colGetSize() == 0; 391 } 392 393 @Override 394 public Iterator<V> iterator() { 395 return new ArrayIterator<V>(1); 396 } 397 398 @Override 399 public boolean remove(Object object) { 400 int index = colIndexOfValue(object); 401 if (index >= 0) { 402 colRemoveAt(index); 403 return true; 404 } 405 return false; 406 } 407 408 @Override 409 public boolean removeAll(Collection<?> collection) { 410 int N = colGetSize(); 411 boolean changed = false; 412 for (int i=0; i<N; i++) { 413 Object cur = colGetEntry(i, 1); 414 if (collection.contains(cur)) { 415 colRemoveAt(i); 416 i--; 417 N--; 418 changed = true; 419 } 420 } 421 return changed; 422 } 423 424 @Override 425 public boolean retainAll(Collection<?> collection) { 426 int N = colGetSize(); 427 boolean changed = false; 428 for (int i=0; i<N; i++) { 429 Object cur = colGetEntry(i, 1); 430 if (!collection.contains(cur)) { 431 colRemoveAt(i); 432 i--; 433 N--; 434 changed = true; 435 } 436 } 437 return changed; 438 } 439 440 @Override 441 public int size() { 442 return colGetSize(); 443 } 444 445 @Override 446 public Object[] toArray() { 447 return toArrayHelper(1); 448 } 449 450 @Override 451 public <T> T[] toArray(T[] array) { 452 return toArrayHelper(array, 1); 453 } 454 }; 455 456 public static <K, V> boolean containsAllHelper(Map<K, V> map, Collection<?> collection) { 457 Iterator<?> it = collection.iterator(); 458 while (it.hasNext()) { 459 if (!map.containsKey(it.next())) { 460 return false; 461 } 462 } 463 return true; 464 } 465 466 public static <K, V> boolean removeAllHelper(Map<K, V> map, Collection<?> collection) { 467 int oldSize = map.size(); 468 Iterator<?> it = collection.iterator(); 469 while (it.hasNext()) { 470 map.remove(it.next()); 471 } 472 return oldSize != map.size(); 473 } 474 475 public static <K, V> boolean retainAllHelper(Map<K, V> map, Collection<?> collection) { 476 int oldSize = map.size(); 477 Iterator<K> it = map.keySet().iterator(); 478 while (it.hasNext()) { 479 if (!collection.contains(it.next())) { 480 it.remove(); 481 } 482 } 483 return oldSize != map.size(); 484 } 485 486 487 public Object[] toArrayHelper(int offset) { 488 final int N = colGetSize(); 489 Object[] result = new Object[N]; 490 for (int i=0; i<N; i++) { 491 result[i] = colGetEntry(i, offset); 492 } 493 return result; 494 } 495 496 public <T> T[] toArrayHelper(T[] array, int offset) { 497 final int N = colGetSize(); 498 if (array.length < N) { 499 @SuppressWarnings("unchecked") T[] newArray 500 = (T[]) Array.newInstance(array.getClass().getComponentType(), N); 501 array = newArray; 502 } 503 for (int i=0; i<N; i++) { 504 array[i] = (T)colGetEntry(i, offset); 505 } 506 if (array.length > N) { 507 array[N] = null; 508 } 509 return array; 510 } 511 512 public static <T> boolean equalsSetHelper(Set<T> set, Object object) { 513 if (set == object) { 514 return true; 515 } 516 if (object instanceof Set) { 517 Set<?> s = (Set<?>) object; 518 519 try { 520 return set.size() == s.size() && set.containsAll(s); 521 } catch (NullPointerException ignored) { 522 return false; 523 } catch (ClassCastException ignored) { 524 return false; 525 } 526 } 527 return false; 528 } 529 530 public Set<Map.Entry<K, V>> getEntrySet() { 531 if (mEntrySet == null) { 532 mEntrySet = new EntrySet(); 533 } 534 return mEntrySet; 535 } 536 537 public Set<K> getKeySet() { 538 if (mKeySet == null) { 539 mKeySet = new KeySet(); 540 } 541 return mKeySet; 542 } 543 544 public Collection<V> getValues() { 545 if (mValues == null) { 546 mValues = new ValuesCollection(); 547 } 548 return mValues; 549 } 550 551 protected abstract int colGetSize(); 552 protected abstract Object colGetEntry(int index, int offset); 553 protected abstract int colIndexOfKey(Object key); 554 protected abstract int colIndexOfValue(Object key); 555 protected abstract Map<K, V> colGetMap(); 556 protected abstract void colPut(K key, V value); 557 protected abstract V colSetValue(int index, V value); 558 protected abstract void colRemoveAt(int index); 559 protected abstract void colClear(); 560} 561