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