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