MapCollections.java revision 2290993eddf5262a8df7fc9478daed52401e325a 
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            mIndex--;
99            mEnd--;
100            mEntryValid = false;
101            colRemoveAt(mIndex);
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 object) {
185            throw new UnsupportedOperationException();
186        }
187
188        @Override
189        public boolean containsAll(Collection<?> collection) {
190            throw new UnsupportedOperationException();
191        }
192
193        @Override
194        public boolean isEmpty() {
195            return colGetSize() == 0;
196        }
197
198        @Override
199        public Iterator<Map.Entry<K, V>> iterator() {
200            return new MapIterator();
201        }
202
203        @Override
204        public boolean remove(Object object) {
205            throw new UnsupportedOperationException();
206        }
207
208        @Override
209        public boolean removeAll(Collection<?> collection) {
210            throw new UnsupportedOperationException();
211        }
212
213        @Override
214        public boolean retainAll(Collection<?> collection) {
215            throw new UnsupportedOperationException();
216        }
217
218        @Override
219        public int size() {
220            return colGetSize();
221        }
222
223        @Override
224        public Object[] toArray() {
225            throw new UnsupportedOperationException();
226        }
227
228        @Override
229        public <T> T[] toArray(T[] array) {
230            throw new UnsupportedOperationException();
231        }
232    };
233
234    final class KeySet implements Set<K> {
235
236        @Override
237        public boolean add(K object) {
238            throw new UnsupportedOperationException();
239        }
240
241        @Override
242        public boolean addAll(Collection<? extends K> collection) {
243            throw new UnsupportedOperationException();
244        }
245
246        @Override
247        public void clear() {
248            colClear();
249        }
250
251        @Override
252        public boolean contains(Object object) {
253            return colIndexOfKey(object) >= 0;
254        }
255
256        @Override
257        public boolean containsAll(Collection<?> collection) {
258            return removeAllHelper(colGetMap(), collection);
259        }
260
261        @Override
262        public boolean isEmpty() {
263            return colGetSize() == 0;
264        }
265
266        @Override
267        public Iterator<K> iterator() {
268            return new ArrayIterator<K>(0);
269        }
270
271        @Override
272        public boolean remove(Object object) {
273            int index = colIndexOfKey(object);
274            if (index >= 0) {
275                colRemoveAt(index);
276                return true;
277            }
278            return false;
279        }
280
281        @Override
282        public boolean removeAll(Collection<?> collection) {
283            return removeAllHelper(colGetMap(), collection);
284        }
285
286        @Override
287        public boolean retainAll(Collection<?> collection) {
288            return retainAllHelper(colGetMap(), collection);
289        }
290
291        @Override
292        public int size() {
293            return colGetSize();
294        }
295
296        @Override
297        public Object[] toArray() {
298            return toArrayHelper(1);
299        }
300
301        @Override
302        public <T> T[] toArray(T[] array) {
303            return toArrayHelper(array, 1);
304        }
305    };
306
307    final class ValuesCollection implements Collection<V> {
308
309        @Override
310        public boolean add(V object) {
311            throw new UnsupportedOperationException();
312        }
313
314        @Override
315        public boolean addAll(Collection<? extends V> collection) {
316            throw new UnsupportedOperationException();
317        }
318
319        @Override
320        public void clear() {
321            colClear();
322        }
323
324        @Override
325        public boolean contains(Object object) {
326            return colIndexOfValue(object) >= 0;
327        }
328
329        @Override
330        public boolean containsAll(Collection<?> collection) {
331            Iterator<?> it = collection.iterator();
332            while (it.hasNext()) {
333                if (!contains(it.next())) {
334                    return false;
335                }
336            }
337            return true;
338        }
339
340        @Override
341        public boolean isEmpty() {
342            return colGetSize() == 0;
343        }
344
345        @Override
346        public Iterator<V> iterator() {
347            return new ArrayIterator<V>(1);
348        }
349
350        @Override
351        public boolean remove(Object object) {
352            int index = colIndexOfValue(object);
353            if (index >= 0) {
354                colRemoveAt(index);
355                return true;
356            }
357            return false;
358        }
359
360        @Override
361        public boolean removeAll(Collection<?> collection) {
362            int N = colGetSize();
363            boolean changed = false;
364            for (int i=0; i<N; i++) {
365                Object cur = colGetEntry(i, 1);
366                if (collection.contains(cur)) {
367                    colRemoveAt(i);
368                    i--;
369                    N--;
370                    changed = true;
371                }
372            }
373            return changed;
374        }
375
376        @Override
377        public boolean retainAll(Collection<?> collection) {
378            int N = colGetSize();
379            boolean changed = false;
380            for (int i=0; i<N; i++) {
381                Object cur = colGetEntry(i, 1);
382                if (!collection.contains(cur)) {
383                    colRemoveAt(i);
384                    i--;
385                    N--;
386                    changed = true;
387                }
388            }
389            return changed;
390        }
391
392        @Override
393        public int size() {
394            return colGetSize();
395        }
396
397        @Override
398        public Object[] toArray() {
399            return toArrayHelper(1);
400        }
401
402        @Override
403        public <T> T[] toArray(T[] array) {
404            return toArrayHelper(array, 1);
405        }
406    };
407
408    public static <K, V> boolean containsAllHelper(Map<K, V> map, Collection<?> collection) {
409        Iterator<?> it = collection.iterator();
410        while (it.hasNext()) {
411            if (!map.containsKey(it.next())) {
412                return false;
413            }
414        }
415        return true;
416    }
417
418    public static <K, V> boolean removeAllHelper(Map<K, V> map, Collection<?> collection) {
419        int oldSize = map.size();
420        Iterator<?> it = collection.iterator();
421        while (it.hasNext()) {
422            map.remove(it.next());
423        }
424        return oldSize != map.size();
425    }
426
427    public static <K, V> boolean retainAllHelper(Map<K, V> map, Collection<?> collection) {
428        int oldSize = map.size();
429        Iterator<K> it = map.keySet().iterator();
430        while (it.hasNext()) {
431            if (!collection.contains(it.next())) {
432                it.remove();
433            }
434        }
435        return oldSize != map.size();
436    }
437
438
439    public Object[] toArrayHelper(int offset) {
440        final int N = colGetSize();
441        Object[] result = new Object[N];
442        for (int i=0; i<N; i++) {
443            result[i] = colGetEntry(i, offset);
444        }
445        return result;
446    }
447
448    public <T> T[] toArrayHelper(T[] array, int offset) {
449        final int N  = colGetSize();
450        if (array.length < N) {
451            @SuppressWarnings("unchecked") T[] newArray
452                = (T[]) Array.newInstance(array.getClass().getComponentType(), N);
453            array = newArray;
454        }
455        for (int i=0; i<N; i++) {
456            array[i] = (T)colGetEntry(i, offset);
457        }
458        if (array.length > N) {
459            array[N] = null;
460        }
461        return array;
462    }
463
464    public Set<Map.Entry<K, V>> getEntrySet() {
465        if (mEntrySet == null) {
466            mEntrySet = new EntrySet();
467        }
468        return mEntrySet;
469    }
470
471    public Set<K> getKeySet() {
472        if (mKeySet == null) {
473            mKeySet = new KeySet();
474        }
475        return mKeySet;
476    }
477
478    public Collection<V> getValues() {
479        if (mValues == null) {
480            mValues = new ValuesCollection();
481        }
482        return mValues;
483    }
484
485    protected abstract int colGetSize();
486    protected abstract Object colGetEntry(int index, int offset);
487    protected abstract int colIndexOfKey(Object key);
488    protected abstract int colIndexOfValue(Object key);
489    protected abstract Map<K, V> colGetMap();
490    protected abstract void colPut(K key, V value);
491    protected abstract V colSetValue(int index, V value);
492    protected abstract void colRemoveAt(int index);
493    protected abstract void colClear();
494}
495