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