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 }