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 }