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