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