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