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