001    /*
002     * Written by Dawid Kurzyniec, on the basis of public specifications and
003     * public domain sources from JSR 166, and released to the public domain,
004     * as explained at http://creativecommons.org/licenses/publicdomain.
005     */
006    
007    /*
008     * Copied from backport-util-concurrent so that weaved code can also be used
009     * with 1.2 and 1.3 JVMs. Only 1.5+ methods are copied.
010     */
011    package net.sourceforge.retroweaver.runtime.java.util;
012    
013    import java.io.IOException;
014    import java.io.ObjectInputStream;
015    import java.io.Serializable;
016    import java.lang.reflect.Array;
017    import java.util.AbstractSet;
018    import java.util.Collection;
019    import java.util.Comparator;
020    import java.util.ConcurrentModificationException;
021    import java.util.Iterator;
022    import java.util.List;
023    import java.util.ListIterator;
024    import java.util.Map;
025    import java.util.Set;
026    import java.util.SortedMap;
027    import java.util.SortedSet;
028    
029    /**
030     * Augments {@link java.util.Collections} with methods added in Java 5.0
031     * and higher. Adds support for dynamically typesafe collection wrappers,
032     * and several utility methods.
033     *
034     * @see java.util.Collections
035     */
036    public class Collections_ {
037    
038        private Collections_() {}
039    
040        // checked views
041    
042        public static Collection checkedCollection(Collection c, Class type) {
043            return new CheckedCollection(c, type);
044        }
045    
046        public static Set checkedSet(Set s, Class type) {
047            return new CheckedSet(s, type);
048        }
049    
050        public static SortedSet checkedSortedSet(SortedSet s, Class type) {
051            return new CheckedSortedSet(s, type);
052        }
053    
054        public static List checkedList(List l, Class type) {
055            return new CheckedList(l, type);
056        }
057    
058        public static Map checkedMap(Map m, Class keyType, Class valueType) {
059            return new CheckedMap(m, keyType, valueType);
060        }
061    
062        public static SortedMap checkedSortedMap(SortedMap m, Class keyType, Class valueType) {
063            return new CheckedSortedMap(m, keyType, valueType);
064        }
065    
066        // empty views
067    
068        public static Set emptySet() {
069            return java.util.Collections.EMPTY_SET;
070        }
071    
072        public static List emptyList() {
073            return java.util.Collections.EMPTY_LIST;
074        }
075    
076        public static Map emptyMap() {
077            return java.util.Collections.EMPTY_MAP;
078        }
079    
080        // other utils
081    
082        public static Comparator reverseOrder(Comparator cmp) {
083            return (cmp instanceof ReverseComparator)
084                ? ((ReverseComparator)cmp).cmp
085                : cmp == null ? java.util.Collections.reverseOrder() : new ReverseComparator(cmp);
086        }
087    
088        public static int frequency(Collection c, Object o) {
089            int freq = 0;
090            if (o == null) {
091                for (Iterator itr = c.iterator(); itr.hasNext();) {
092                    if (itr.next() == null) freq++;
093                }
094            }
095            else {
096                for (Iterator itr = c.iterator(); itr.hasNext();) {
097                    if (o.equals(itr.next())) freq++;
098                }
099            }
100            return freq;
101        }
102    
103        public static boolean disjoint(Collection a, Collection b) { // NOPMD by xlv
104            // set.contains() is usually faster than for other collections
105            if (a instanceof Set && (!(b instanceof Set) || a.size() < b.size())) {
106                Collection tmp = a;
107                a = b;
108                b = tmp;
109            }
110            for (Iterator itr = a.iterator(); itr.hasNext();) {
111                if (b.contains(itr.next())) return false;
112            }
113            return true;
114        }
115    
116        public static boolean addAll(Collection c, Object[] a) {
117            boolean modified = false;
118            for (int i=0; i<a.length; i++) {
119                modified |= c.add(a[i]);
120            }
121            return modified;
122        }
123    
124        // Checked collections
125        private static class CheckedCollection implements Collection, Serializable {
126    
127            final Collection coll;
128            final Class type;
129            transient Object[] emptyArr;
130            CheckedCollection(Collection coll, Class type) {
131                if (coll == null || type == null) throw new NullPointerException(); // NOPMD by xlv
132                this.coll = coll;
133                this.type = type;
134            }
135    
136            void typeCheck(Object obj) {
137                if (!type.isInstance(obj)) {
138                    throw new ClassCastException(
139                        "Attempted to insert an element of type " + obj.getClass().getName() +
140                        " to a collection of type " + type.getName());
141                }
142            }
143    
144            public int size()                        { return coll.size(); }
145            public void clear()                      { coll.clear(); }
146            public boolean isEmpty()                 { return coll.isEmpty(); }
147            public Object[] toArray()                { return coll.toArray(); }
148            public Object[] toArray(Object[] a)      { return coll.toArray(a); }
149            public boolean contains(Object o)        { return coll.contains(o); }
150            public boolean remove(Object o)          { return coll.remove(o); }
151            public boolean containsAll(Collection c) { return coll.containsAll(c); }
152            public boolean removeAll(Collection c)   { return coll.removeAll(c); }
153            public boolean retainAll(Collection c)   { return coll.retainAll(c); }
154            public String toString()                 { return coll.toString(); }
155    
156            public boolean add(Object o) {
157                typeCheck(o);
158                return coll.add(o);
159            }
160    
161            public boolean addAll(Collection c) {
162                Object[] checked;
163                try {
164                    checked = c.toArray(getEmptyArr());
165                }
166                catch (ArrayStoreException e) {
167                    throw new ClassCastException(
168                        "Attempted to insert an element of invalid type " +
169                        " to a collection of type " + type.getName());
170                }
171                return coll.addAll(java.util.Arrays.asList(checked));
172            }
173    
174            public Iterator iterator() {
175                return new Itr(coll.iterator());
176            }
177    
178            protected Object[] getEmptyArr() {
179                if (emptyArr == null) emptyArr = (Object[])Array.newInstance(type, 0);
180                return emptyArr;
181            }
182    
183            class Itr implements Iterator {
184                final Iterator itr;
185                Itr(Iterator itr)            { this.itr = itr; }
186                public boolean hasNext()     { return itr.hasNext(); }
187                public Object next()         { return itr.next(); }
188                public void remove()         { itr.remove(); }
189            }
190        }
191    
192        private static class CheckedList extends CheckedCollection
193            implements List, Serializable
194        {
195            final List list;
196            CheckedList(List list, Class type) {
197                super(list, type);
198                this.list = list;
199            }
200            public Object get(int index)     { return list.get(index); }
201            public Object remove(int index)  { return list.remove(index); }
202            public int indexOf(Object o)     { return list.indexOf(o); }
203            public int lastIndexOf(Object o) { return list.lastIndexOf(o); }
204    
205            public int hashCode()            { return list.hashCode(); }
206            public boolean equals(Object o)  { return o == this || list.equals(o); }
207    
208            public Object set(int index, Object element) {
209                typeCheck(element);
210                return list.set(index, element);
211            }
212    
213            public void add(int index, Object element) {
214                typeCheck(element);
215                list.add(index, element);
216            }
217    
218            public boolean addAll(int index, Collection c) {
219                Object[] checked;
220                try {
221                    checked = c.toArray(getEmptyArr());
222                }
223                catch (ArrayStoreException e) {
224                    throw new ClassCastException(
225                        "Attempted to insert an element of invalid type " +
226                        " to a list of type " + type.getName());
227                }
228    
229                return list.addAll(index, java.util.Arrays.asList(checked));
230            }
231    
232            public List subList(int fromIndex, int toIndex) {
233                return new CheckedList(list.subList(fromIndex, toIndex), type);
234            }
235    
236            public ListIterator listIterator() {
237                return new ListItr(list.listIterator());
238            }
239    
240            public ListIterator listIterator(int index) {
241                return new ListItr(list.listIterator(index));
242            }
243    
244            private class ListItr implements ListIterator {
245                final ListIterator itr;
246                ListItr(ListIterator itr)    { this.itr = itr; }
247                public boolean hasNext()     { return itr.hasNext(); }
248                public boolean hasPrevious() { return itr.hasPrevious(); }
249                public int nextIndex()       { return itr.nextIndex(); }
250                public int previousIndex()   { return itr.previousIndex(); }
251                public Object next()         { return itr.next(); }
252                public Object previous()     { return itr.previous(); }
253                public void remove()         { itr.remove(); }
254    
255                public void set(Object element) {
256                    typeCheck(element);
257                    itr.set(element);
258                }
259    
260                public void add(Object element) {
261                    typeCheck(element);
262                    itr.add(element);
263                }
264            }
265        }
266    
267        private static class CheckedSet extends CheckedCollection
268            implements Set, Serializable
269        {
270            CheckedSet(Set set, Class type) {
271                super(set, type);
272            }
273    
274            public int hashCode()            { return coll.hashCode(); }
275            public boolean equals(Object o)  { return o == this || coll.equals(o); }
276        }
277    
278        private static class CheckedSortedSet extends CheckedSet
279            implements SortedSet, Serializable
280        {
281            final SortedSet set;
282            CheckedSortedSet(SortedSet set, Class type) {
283                super(set, type);
284                this.set = set;
285            }
286            public Object first()          { return set.first(); }
287            public Object last()           { return set.last(); }
288            public Comparator comparator() { return set.comparator(); }
289    
290            public SortedSet headSet(Object toElement) {
291                return new CheckedSortedSet(set.headSet(toElement), type);
292            }
293    
294            public SortedSet tailSet(Object fromElement) {
295                return new CheckedSortedSet(set.tailSet(fromElement), type);
296            }
297    
298            public SortedSet subSet(Object fromElement, Object toElement) {
299                return new CheckedSortedSet(set.subSet(fromElement, toElement), type);
300            }
301        }
302    
303    //    public static NavigableSet checkedNavigableSet(NavigableSet set, Class type) {
304    //        return new CheckedNavigableSet(set, type);
305    //    }
306    //
307    //    private static class CheckedNavigableSet extends CheckedSortedSet
308    //        implements NavigableSet, Serializable
309    //    {
310    //        final NavigableSet set;
311    //        CheckedNavigableSet(NavigableSet set, Class type) {
312    //            super(set, type);
313    //            this.set = set;
314    //        }
315    //        public Object lower(Object e)   { return set.lower(e); }
316    //        public Object floor(Object e)   { return set.floor(e); }
317    //        public Object ceiling(Object e) { return set.ceiling(e); }
318    //        public Object higher(Object e)  { return set.higher(e); }
319    //        public Object pollFirst()       { return set.pollFirst(); }
320    //        public Object pollLast()        { return set.pollLast(); }
321    //
322    //        public Iterator descendingIterator() {
323    //            return new Itr(set.descendingIterator());
324    //        }
325    //
326    //        public NavigableSet navigableSubSet(Object fromElement,
327    //                                            Object toElement) {
328    //            return new CheckedNavigableSet(
329    //                set.navigableSubSet(fromElement, toElement), type);
330    //        }
331    //
332    //        public NavigableSet navigableHeadSet(Object toElement) {
333    //            return new CheckedNavigableSet(set.navigableHeadSet(toElement), type);
334    //        }
335    //
336    //        public NavigableSet navigableTailSet(Object fromElement) {
337    //            return new CheckedNavigableSet(set.navigableTailSet(fromElement), type);
338    //        }
339    //    }
340    
341        private static class CheckedMap implements Map, Serializable {
342            final Map map;
343            final Class keyType, valueType;
344            transient Set entrySet;
345    
346            CheckedMap(Map map, Class keyType, Class valueType) {
347                if (map == null || keyType == null || valueType == null) {
348                    throw new NullPointerException(); // NOPMD by xlv
349                }
350                this.map = map;
351                this.keyType = keyType;
352                this.valueType = valueType;
353            }
354    
355            private void typeCheckKey(Object key) {
356                if (!keyType.isInstance(key)) {
357                    throw new ClassCastException(
358                        "Attempted to use a key of type " + key.getClass().getName() +
359                        " with a map with keys of type " + keyType.getName());
360                }
361            }
362    
363            private void typeCheckValue(Object value) {
364                if (!valueType.isInstance(value)) {
365                    throw new ClassCastException(
366                        "Attempted to use a value of type " + value.getClass().getName() +
367                        " with a map with values of type " + valueType.getName());
368                }
369            }
370    
371            public int hashCode()                  { return map.hashCode(); }
372            public boolean equals(Object o)        { return o == this || map.equals(o); }
373    
374            public int size()                      { return map.size(); }
375            public void clear()                    { map.clear(); }
376            public boolean isEmpty()               { return map.isEmpty(); }
377            public boolean containsKey(Object key) { return map.containsKey(key); }
378            public boolean containsValue(Object value)
379                                                   { return map.containsValue(value); }
380    
381            // key and value sets do not support additions
382            public Collection values()             { return map.values(); }
383            public Set keySet()                    { return map.keySet(); }
384    
385            private transient Object[] emptyKeyArray;
386            private transient Object[] emptyValueArray;
387    
388            public void putAll(Map m) {
389                // for compatibility with 5.0, all-or-nothing semantics
390                if (emptyKeyArray == null) {
391                    emptyKeyArray = (Object[])Array.newInstance(keyType, 0);
392                }
393                if (emptyValueArray == null) {
394                    emptyValueArray = (Object[])Array.newInstance(valueType, 0);
395                }
396    
397                Object[] keys, values;
398    
399                try {
400                    keys = m.keySet().toArray(emptyKeyArray);
401                }
402                catch (ArrayStoreException e) {
403                    throw new ClassCastException(
404                        "Attempted to use an invalid key type " +
405                        " with a map with keys of type " + keyType.getName());
406                }
407                try {
408                    values = m.keySet().toArray(emptyKeyArray);
409                }
410                catch (ArrayStoreException e) {
411                    throw new ClassCastException(
412                        "Attempted to use an invalid value type " +
413                        " with a map with values of type " + valueType.getName());
414                }
415                if (keys.length != values.length) {
416                    throw new ConcurrentModificationException();
417                }
418                for (int i=0; i<keys.length; i++) {
419                    map.put(keys[i], values[i]);
420                }
421            }
422    
423            public Set entrySet() {
424                if (entrySet == null) entrySet = new EntrySetView(map.entrySet());
425                return entrySet;
426            }
427    
428            public Object get(Object key)          { return map.get(key); }
429            public Object remove(Object key)       { return map.remove(key); }
430    
431            public Object put(Object key, Object value) {
432                typeCheckKey(key);
433                typeCheckValue(value);
434                return map.put(key, value);
435            }
436    
437            private class EntrySetView extends AbstractSet implements Set {
438                final Set entrySet;
439                EntrySetView(Set entrySet)        { this.entrySet = entrySet; }
440                public int size()                 { return entrySet.size(); }
441                public boolean isEmpty()          { return entrySet.isEmpty(); }
442                public boolean remove(Object o)   { return entrySet.remove(o); }
443                public void clear()               { entrySet.clear(); }
444    
445                public boolean contains(Object o) {
446                    if (!(o instanceof Map.Entry)) return false;
447                    return entrySet.contains(new EntryView((Map.Entry)o));
448                }
449    
450                public Iterator iterator() {
451                    final Iterator itr = entrySet.iterator();
452                    return new Iterator() {
453                        public boolean hasNext() { return itr.hasNext(); }
454                        public Object next()     { return new EntryView((Map.Entry)itr.next()); }
455                        public void remove()     { itr.remove(); }
456                    };
457                }
458    
459                public Object[] toArray() {
460                    Object[] a = entrySet.toArray();
461                    if (a.getClass().getComponentType().isAssignableFrom(EntryView.class)) {
462                        for (int i=0; i<a.length; i++) {
463                            a[i] = new EntryView( (Entry) a[i]);
464                        }
465                        return a;
466                    }
467                    else {
468                        Object[] newa = new Object[a.length];
469                        for (int i=0; i<a.length; i++) {
470                            newa[i] = new EntryView( (Entry) a[i]);
471                        }
472                        return newa;
473                    }
474                }
475    
476                 public Object[] toArray(Object[] a) {
477                     Object[] base;
478                     if (a.length == 0) {
479                         base = a;
480                     }
481                     else {
482                         base = (Object[])(Array.newInstance(a.getClass().getComponentType(), a.length));
483                     }
484                     base = entrySet.toArray(base);
485                     // if the returned array is type-incompatible with EntryView,
486                     // tough - we can't tolerate this anyway
487                     for (int i=0; i<base.length; i++) {
488                         base[i] = new EntryView((Map.Entry)base[i]);
489                     }
490                     if (base.length > a.length) {
491                         a = base;
492                     }
493                     else {
494                         // need to copy back to a
495                         System.arraycopy(base, 0, a, 0, base.length);
496                         if (base.length < a.length) a[base.length] = null;
497                     }
498                     return a;
499                }
500            }
501    
502            private class EntryView implements Map.Entry, Serializable {
503                final Map.Entry entry;
504                EntryView(Map.Entry entry) {
505                    this.entry = entry;
506                }
507                public Object getKey()          { return entry.getKey(); }
508                public Object getValue()        { return entry.getValue(); }
509                public int hashCode()           { return entry.hashCode(); }
510                public boolean equals(Object o) {
511                    if (o == this) return true;
512                    if (!(o instanceof Map.Entry)) return false;
513                    Map.Entry e = (Map.Entry)o;
514                    return eq(getKey(), e.getKey()) && eq(getValue(), e.getValue());
515                }
516    
517                public Object setValue(Object val) {
518                    typeCheckValue(val);
519                    return entry.setValue(val);
520                }
521            }
522        }
523    
524        private static boolean eq(Object o1, Object o2) {
525            return (o1 == null) ? o2 == null : o1.equals(o2);
526        }
527    
528        private static class CheckedSortedMap extends CheckedMap
529                                              implements SortedMap {
530            final SortedMap map;
531            CheckedSortedMap(SortedMap map, Class keyType, Class valueType) {
532                super(map, keyType, valueType);
533                this.map = map;
534            }
535            public Comparator comparator()  { return map.comparator(); }
536            public Object firstKey()        { return map.firstKey(); }
537            public Object lastKey()         { return map.lastKey(); }
538    
539            public SortedMap subMap(Object fromKey, Object toKey) {
540                return new CheckedSortedMap(map.subMap(fromKey, toKey), keyType, valueType);
541            }
542    
543            public SortedMap headMap(Object toKey) {
544                return new CheckedSortedMap(map.headMap(toKey), keyType, valueType);
545            }
546    
547            public SortedMap tailMap(Object fromKey) {
548                return new CheckedSortedMap(map.tailMap(fromKey), keyType, valueType);
549            }
550        }
551    
552        private static class SetFromMap extends AbstractSet implements Serializable {
553    
554            private final static Object PRESENT = Boolean.TRUE;
555    
556            final Map map;
557            transient Set keySet;
558    
559            SetFromMap(Map map) {
560                this.map = map;
561                this.keySet = map.keySet();
562            }
563    
564            public int hashCode()               { return keySet.hashCode(); }
565            public int size()                   { return map.size(); }
566            public void clear()                 { map.clear(); }
567            public boolean isEmpty()            { return map.isEmpty(); }
568            public boolean add(Object o)        { return map.put(o, PRESENT) == null; }
569            public boolean contains(Object o)   { return map.containsKey(o); }
570            public boolean equals(Object o)     { return o == this || keySet.equals(o); }
571            public boolean remove(Object o)     { return map.remove(o) == PRESENT; }
572    
573            public boolean removeAll(Collection c) { return keySet.removeAll(c); }
574            public boolean retainAll(Collection c) { return keySet.retainAll(c); }
575            public Iterator iterator()             { return keySet.iterator(); }
576            public Object[] toArray()              { return keySet.toArray(); }
577            public Object[] toArray(Object[] a)    { return keySet.toArray(a); }
578    
579            public boolean addAll(Collection c) {
580                boolean modified = false;
581                for (Iterator it = c.iterator(); it.hasNext();) {
582                    modified |= (map.put(it.next(), PRESENT) == null);
583                }
584                return modified;
585            }
586    
587            private void readObject(ObjectInputStream in)
588                throws IOException, ClassNotFoundException
589            {
590                in.defaultReadObject();
591                keySet = map.keySet();
592            }
593        }
594    
595        private static class ReverseComparator implements Comparator, Serializable {
596            final Comparator cmp;
597            ReverseComparator(Comparator cmp) {
598                this.cmp = cmp;
599            }
600            public int compare(Object o1, Object o2) {
601                return cmp.compare(o2, o1);
602            }
603        }
604    }