1 | /* |
2 | * Written by Dawid Kurzyniec, on the basis of public specifications and |
3 | * public domain sources from JSR 166, and released to the public domain, |
4 | * as explained at http://creativecommons.org/licenses/publicdomain. |
5 | */ |
6 | |
7 | /* |
8 | * Copied from backport-util-concurrent so that weaved code can also be used |
9 | * with 1.2 and 1.3 JVMs. Only 1.5+ methods are copied. |
10 | */ |
11 | package net.sourceforge.retroweaver.runtime.java.util; |
12 | |
13 | import java.io.IOException; |
14 | import java.io.ObjectInputStream; |
15 | import java.io.Serializable; |
16 | import java.lang.reflect.Array; |
17 | import java.util.AbstractSet; |
18 | import java.util.Collection; |
19 | import java.util.Comparator; |
20 | import java.util.ConcurrentModificationException; |
21 | import java.util.Iterator; |
22 | import java.util.List; |
23 | import java.util.ListIterator; |
24 | import java.util.Map; |
25 | import java.util.Set; |
26 | import java.util.SortedMap; |
27 | import java.util.SortedSet; |
28 | |
29 | /** |
30 | * Augments {@link java.util.Collections} with methods added in Java 5.0 |
31 | * and higher. Adds support for dynamically typesafe collection wrappers, |
32 | * and several utility methods. |
33 | * |
34 | * @see java.util.Collections |
35 | */ |
36 | public class Collections_ { |
37 | |
38 | private Collections_() {} |
39 | |
40 | // checked views |
41 | |
42 | public static Collection checkedCollection(Collection c, Class type) { |
43 | return new CheckedCollection(c, type); |
44 | } |
45 | |
46 | public static Set checkedSet(Set s, Class type) { |
47 | return new CheckedSet(s, type); |
48 | } |
49 | |
50 | public static SortedSet checkedSortedSet(SortedSet s, Class type) { |
51 | return new CheckedSortedSet(s, type); |
52 | } |
53 | |
54 | public static List checkedList(List l, Class type) { |
55 | return new CheckedList(l, type); |
56 | } |
57 | |
58 | public static Map checkedMap(Map m, Class keyType, Class valueType) { |
59 | return new CheckedMap(m, keyType, valueType); |
60 | } |
61 | |
62 | public static SortedMap checkedSortedMap(SortedMap m, Class keyType, Class valueType) { |
63 | return new CheckedSortedMap(m, keyType, valueType); |
64 | } |
65 | |
66 | // empty views |
67 | |
68 | public static Set emptySet() { |
69 | return java.util.Collections.EMPTY_SET; |
70 | } |
71 | |
72 | public static List emptyList() { |
73 | return java.util.Collections.EMPTY_LIST; |
74 | } |
75 | |
76 | public static Map emptyMap() { |
77 | return java.util.Collections.EMPTY_MAP; |
78 | } |
79 | |
80 | // other utils |
81 | |
82 | public static Comparator reverseOrder(Comparator cmp) { |
83 | return (cmp instanceof ReverseComparator) |
84 | ? ((ReverseComparator)cmp).cmp |
85 | : cmp == null ? java.util.Collections.reverseOrder() : new ReverseComparator(cmp); |
86 | } |
87 | |
88 | public static int frequency(Collection c, Object o) { |
89 | int freq = 0; |
90 | if (o == null) { |
91 | for (Iterator itr = c.iterator(); itr.hasNext();) { |
92 | if (itr.next() == null) freq++; |
93 | } |
94 | } |
95 | else { |
96 | for (Iterator itr = c.iterator(); itr.hasNext();) { |
97 | if (o.equals(itr.next())) freq++; |
98 | } |
99 | } |
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 | } |