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