001: /*
002: * Copyright 2007 Google Inc.
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License"); you may not
005: * use this file except in compliance with the License. You may obtain a copy of
006: * the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
012: * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
013: * License for the specific language governing permissions and limitations under
014: * the License.
015: */
016: package java.util;
017:
018: /**
019: * Utility methods that operate on collections. <a
020: * href="http://java.sun.com/j2se/1.5.0/docs/api/java/util/Collections.html">[Sun
021: * docs]</a>
022: */
023: public class Collections {
024:
025: /**
026: * Used to implement iterators on unmodifiable lists.
027: *
028: * @param <E> element type.
029: */
030: private static class UnmodifiableListIterator<E> implements
031: ListIterator<E> {
032:
033: final ListIterator<? extends E> it;
034:
035: public UnmodifiableListIterator(ListIterator<? extends E> it) {
036: this .it = it;
037: }
038:
039: public void add(E o) {
040: throw new UnsupportedOperationException(
041: "UnmodifiableListIterator: add not permitted");
042: }
043:
044: public boolean hasNext() {
045: return it.hasNext();
046: }
047:
048: public boolean hasPrevious() {
049: return it.hasPrevious();
050: }
051:
052: public E next() {
053: return it.next();
054: }
055:
056: public int nextIndex() {
057: return it.nextIndex();
058: }
059:
060: public E previous() {
061: return it.previous();
062: }
063:
064: public int previousIndex() {
065: return it.previousIndex();
066: }
067:
068: public void remove() {
069: throw new UnsupportedOperationException(
070: "UnmodifiableListIterator: remove not permitted");
071: }
072:
073: public void set(E o) {
074: throw new UnsupportedOperationException(
075: "UnmodifiableListIterator: set not permitted");
076: }
077: }
078:
079: public static final List<?> EMPTY_LIST = unmodifiableList(new ArrayList<Object>());
080: public static final Map<?, ?> EMPTY_MAP = unmodifiableMap(new HashMap<Object, Object>());
081: public static final Set<?> EMPTY_SET = unmodifiableSet(new HashSet<Object>());
082:
083: private static Comparator<Comparable<Object>> reverseComparator = new Comparator<Comparable<Object>>() {
084: public int compare(Comparable<Object> o1, Comparable<Object> o2) {
085: return o2.compareTo(o1);
086: }
087: };
088:
089: public static <T> boolean addAll(Collection<? super T> c, T... a) {
090: boolean result = false;
091: for (T e : a) {
092: result |= c.add(e);
093: }
094: return result;
095: }
096:
097: /**
098: * Perform a binary search on a sorted List, using natural ordering.
099: *
100: * <p>
101: * Note: The GWT implementation differs from the JDK implementation in that it
102: * does not do an iterator-based binary search for Lists that do not implement
103: * RandomAccess.
104: * </p>
105: *
106: * @param sortedList object array to search
107: * @param key value to search for
108: * @return the index of an element with a matching value, or a negative number
109: * which is the index of the next larger value (or just past the end
110: * of the array if the searched value is larger than all elements in
111: * the array) minus 1 (to ensure error returns are negative)
112: * @throws ClassCastException if <code>key</code> is not comparable to
113: * <code>sortedList</code>'s elements.
114: */
115: public static <T> int binarySearch(
116: final List<? extends Comparable<? super T>> sortedList,
117: final T key) {
118: return binarySearch(sortedList, key, null);
119: }
120:
121: /*
122: * These methods are commented out because they cannot currently be
123: * implemented in GWT. The signatures are included in case that changes.
124: */
125: // public static <E> Collection<E> checkedCollection(Collection<E> c, Class<E>
126: // type) {
127: // // FUTURE: implement
128: // return null;
129: // }
130: //
131: // static <E> List<E> checkedList(List<E> list, Class<E> type) {
132: // // FUTURE: implement
133: // return null;
134: // }
135: //
136: // public static <K,V> Map<K,V> checkedMap(Map<K,V> list, Class<K> keyType,
137: // Class<V> valueType) {
138: // // FUTURE: implement
139: // return null;
140: // }
141: //
142: // public static <E> Set<E> checkedSet(Set<E> list, Class<E> type) {
143: // // FUTURE: implement
144: // return null;
145: // }
146: //
147: // public static <K,V> SortedMap<K,V> checkedSortedMap(SortedMap<K,V> m,
148: // Class<K> keyType, Class<V> valueType) {
149: // // FUTURE: implement
150: // return null;
151: // }
152: //
153: // public static <E> SortedSet<E> checkedSortedSet(SortedSet<E> list, Class<E>
154: // type) {
155: // // FUTURE: implement
156: // return null;
157: // }
158: /**
159: * Perform a binary search on a sorted List, using a user-specified comparison
160: * function.
161: *
162: * <p>
163: * Note: The GWT implementation differs from the JDK implementation in that it
164: * does not do an iterator-based binary search for Lists that do not implement
165: * RandomAccess.
166: * </p>
167: *
168: * @param sortedList List to search
169: * @param key value to search for
170: * @param comparator comparision function, <code>null</code> indicates
171: * <i>natural ordering</i> should be used.
172: * @return the index of an element with a matching value, or a negative number
173: * which is the index of the next larger value (or just past the end
174: * of the array if the searched value is larger than all elements in
175: * the array) minus 1 (to ensure error returns are negative)
176: * @throws ClassCastException if <code>key</code> and
177: * <code>sortedList</code>'s elements cannot be compared by
178: * <code>comparator</code>.
179: */
180: public static <T> int binarySearch(
181: final List<? extends T> sortedList, final T key,
182: Comparator<? super T> comparator) {
183: /*
184: * TODO: This doesn't implement the "iterator-based binary search" described
185: * in the JDK docs for non-RandomAccess Lists. Until GWT provides a
186: * LinkedList, this shouldn't be an issue.
187: */
188: if (comparator == null) {
189: comparator = Comparators.natural();
190: }
191: int low = 0;
192: int high = sortedList.size() - 1;
193:
194: while (low <= high) {
195: final int mid = low + ((high - low) / 2);
196: final T midVal = sortedList.get(mid);
197: final int compareResult = comparator.compare(midVal, key);
198:
199: if (compareResult < 0) {
200: low = mid + 1;
201: } else if (compareResult > 0) {
202: high = mid - 1;
203: } else {
204: // key found
205: return mid;
206: }
207: }
208: // key not found.
209: return -low - 1;
210: }
211:
212: public static <T> void copy(List<? super T> dest,
213: List<? extends T> src) {
214: // TODO(jat): optimize
215: dest.addAll(src);
216: }
217:
218: public static boolean disjoint(Collection<?> c1, Collection<?> c2) {
219: Collection<?> iterating = c1;
220: Collection<?> testing = c2;
221:
222: // See if one of these objects possibly implements a fast contains.
223: if ((c1 instanceof Set) && !(c2 instanceof Set)) {
224: iterating = c2;
225: testing = c1;
226: }
227:
228: for (Object o : iterating) {
229: if (testing.contains(o)) {
230: return false;
231: }
232: }
233:
234: return true;
235: }
236:
237: @SuppressWarnings("unchecked")
238: public static <T> List<T> emptyList() {
239: return (List<T>) EMPTY_LIST;
240: }
241:
242: @SuppressWarnings("unchecked")
243: public static <K, V> Map<K, V> emptyMap() {
244: return (Map<K, V>) EMPTY_MAP;
245: }
246:
247: @SuppressWarnings("unchecked")
248: public static <T> Set<T> emptySet() {
249: return (Set<T>) EMPTY_SET;
250: }
251:
252: public static <T> Enumeration<T> enumeration(Collection<T> c) {
253: final Iterator<T> it = c.iterator();
254: return new Enumeration<T>() {
255: public boolean hasMoreElements() {
256: return it.hasNext();
257: }
258:
259: public T nextElement() {
260: return it.next();
261: }
262: };
263: }
264:
265: public static <T> void fill(List<? super T> list, T obj) {
266: for (ListIterator<? super T> it = list.listIterator(); it
267: .hasNext();) {
268: it.set(obj);
269: }
270: }
271:
272: public static int frequency(Collection<?> c, Object o) {
273: int count = 0;
274: for (Object e : c) {
275: if (o == null ? e == null : o.equals(e)) {
276: ++count;
277: }
278: }
279: return count;
280: }
281:
282: public static <T extends Object & Comparable<? super T>> T max(
283: Collection<? extends T> coll) {
284: return max(coll, null);
285: }
286:
287: public static <T> T max(Collection<? extends T> coll,
288: Comparator<? super T> comp) {
289:
290: if (comp == null) {
291: comp = Comparators.natural();
292: }
293:
294: Iterator<? extends T> it = coll.iterator();
295:
296: // Will throw NoSuchElementException if coll is empty.
297: T max = it.next();
298:
299: while (it.hasNext()) {
300: T t = it.next();
301: if (comp.compare(t, max) > 0) {
302: max = t;
303: }
304: }
305:
306: return max;
307: }
308:
309: public static <T extends Object & Comparable<? super T>> T min(
310: Collection<? extends T> coll) {
311: return min(coll, null);
312: }
313:
314: public static <T> T min(Collection<? extends T> coll,
315: Comparator<? super T> comp) {
316: return max(coll, reverseOrder(comp));
317: }
318:
319: public static <T> List<T> nCopies(int n, T o) {
320: ArrayList<T> list = new ArrayList<T>();
321: for (int i = 0; i < n; ++i) {
322: list.add(o);
323: }
324: return unmodifiableList(list);
325: }
326:
327: public static <T> boolean replaceAll(List<T> list, T oldVal,
328: T newVal) {
329: boolean modified = false;
330: for (ListIterator<T> it = list.listIterator(); it.hasNext();) {
331: T t = it.next();
332: if (t == null ? oldVal == null : t.equals(oldVal)) {
333: it.set(newVal);
334: modified = true;
335: }
336: }
337: return modified;
338: }
339:
340: public static <T> void reverse(List<T> l) {
341: if (l instanceof RandomAccess) {
342: for (int iFront = 0, iBack = l.size() - 1; iFront < iBack; ++iFront, --iBack) {
343: Collections.swap(l, iFront, iBack);
344: }
345: } else {
346: ListIterator<T> head = l.listIterator();
347: ListIterator<T> tail = l.listIterator(l.size());
348: while (head.nextIndex() < tail.previousIndex()) {
349: T headElem = head.next();
350: T tailElem = tail.previous();
351: head.set(tailElem);
352: tail.set(headElem);
353: }
354: }
355: }
356:
357: @SuppressWarnings("unchecked")
358: public static <T> Comparator<T> reverseOrder() {
359: return (Comparator<T>) reverseComparator;
360: }
361:
362: public static <T> Comparator<T> reverseOrder(final Comparator<T> cmp) {
363: if (cmp == null) {
364: return reverseOrder();
365: }
366: return new Comparator<T>() {
367: public int compare(T t1, T t2) {
368: return cmp.compare(t2, t1);
369: }
370: };
371: }
372:
373: // TODO(tobyr) Is it worth creating custom singleton sets, lists, and maps?
374: // More efficient at runtime, but more code bloat to download
375:
376: public static <T> Set<T> singleton(T o) {
377: HashSet<T> set = new HashSet<T>(1);
378: set.add(o);
379: return unmodifiableSet(set);
380: }
381:
382: public static <T> List<T> singletonList(T o) {
383: List<T> list = new ArrayList<T>(1);
384: list.add(o);
385: return unmodifiableList(list);
386: }
387:
388: public static <K, V> Map<K, V> singletonMap(K key, V value) {
389: Map<K, V> map = new HashMap<K, V>(1);
390: map.put(key, value);
391: return unmodifiableMap(map);
392: }
393:
394: public static <T> void sort(List<T> target) {
395: Object[] x = target.toArray();
396: Arrays.sort(x);
397: replaceContents(target, x);
398: }
399:
400: public static <T> void sort(List<T> target, Comparator<? super T> c) {
401: Object[] x = target.toArray();
402: Arrays.sort(x, (Comparator<Object>) c);
403: replaceContents(target, x);
404: }
405:
406: public static void swap(List<?> list, int i, int j) {
407: swapImpl(list, i, j);
408: }
409:
410: public static <T> Collection<T> unmodifiableCollection(
411: final Collection<? extends T> coll) {
412: return new Collection<T>() {
413:
414: public boolean add(T o) {
415: throw new UnsupportedOperationException(
416: "unmodifiableCollection: add not permitted");
417: }
418:
419: public boolean addAll(Collection<? extends T> c) {
420: throw new UnsupportedOperationException(
421: "unmodifiableCollection: addAll not permitted");
422: }
423:
424: public void clear() {
425: throw new UnsupportedOperationException(
426: "unmodifiableCollection: clear not permitted");
427: }
428:
429: public boolean contains(Object o) {
430: return coll.contains(o);
431: }
432:
433: public boolean containsAll(Collection<?> c) {
434: return coll.containsAll(c);
435: }
436:
437: public boolean isEmpty() {
438: return coll.isEmpty();
439: }
440:
441: public Iterator<T> iterator() {
442: final Iterator<? extends T> it = coll.iterator();
443: return new Iterator<T>() {
444:
445: public boolean hasNext() {
446: return it.hasNext();
447: }
448:
449: public T next() {
450: return it.next();
451: }
452:
453: public void remove() {
454: throw new UnsupportedOperationException(
455: "unmodifiableCollection.iterator: remove not permitted");
456: }
457: };
458: }
459:
460: public boolean remove(Object o) {
461: throw new UnsupportedOperationException(
462: "unmodifiableCollection: remove not permitted");
463: }
464:
465: public boolean removeAll(Collection<?> c) {
466: throw new UnsupportedOperationException(
467: "unmodifiableCollection: removeAll not permitted");
468: }
469:
470: public boolean retainAll(Collection<?> c) {
471: throw new UnsupportedOperationException(
472: "unmodifiableCollection: retainAll not permitted");
473: }
474:
475: public int size() {
476: return coll.size();
477: }
478:
479: public Object[] toArray() {
480: return coll.toArray();
481: }
482:
483: public <OT> OT[] toArray(OT[] a) {
484: return coll.toArray(a);
485: }
486: };
487: }
488:
489: public static <T> List<T> unmodifiableList(
490: final List<? extends T> list) {
491: return new List<T>() {
492: public void add(int index, T element) {
493: throw new UnsupportedOperationException(
494: "unmodifiableList: add not permitted");
495: }
496:
497: public boolean add(T o) {
498: throw new UnsupportedOperationException(
499: "unmodifiableList: add not permitted");
500: }
501:
502: public boolean addAll(Collection<? extends T> c) {
503: throw new UnsupportedOperationException(
504: "unmodifiableList: addAll not permitted");
505: }
506:
507: public boolean addAll(int index, Collection<? extends T> c) {
508: throw new UnsupportedOperationException(
509: "unmodifiableList: addAll not permitted");
510: }
511:
512: public void clear() {
513: throw new UnsupportedOperationException(
514: "unmodifiableList: clear not permitted");
515: }
516:
517: public boolean contains(Object o) {
518: return list.contains(o);
519: }
520:
521: public boolean containsAll(Collection<?> c) {
522: return list.containsAll(c);
523: }
524:
525: public T get(int index) {
526: return list.get(index);
527: }
528:
529: public int indexOf(Object o) {
530: return list.indexOf(o);
531: }
532:
533: public boolean isEmpty() {
534: return list.isEmpty();
535: }
536:
537: public Iterator<T> iterator() {
538: return listIterator();
539: }
540:
541: public int lastIndexOf(Object o) {
542: return list.lastIndexOf(o);
543: }
544:
545: public ListIterator<T> listIterator() {
546: return new UnmodifiableListIterator<T>(list
547: .listIterator());
548: }
549:
550: public ListIterator<T> listIterator(int from) {
551: return new UnmodifiableListIterator<T>(list
552: .listIterator(from));
553: }
554:
555: public T remove(int index) {
556: throw new UnsupportedOperationException(
557: "unmodifiableList: remove not permitted");
558: }
559:
560: public boolean remove(Object o) {
561: throw new UnsupportedOperationException(
562: "unmodifiableList: remove not permitted");
563: }
564:
565: public boolean removeAll(Collection<?> c) {
566: throw new UnsupportedOperationException(
567: "unmodifiableList: removeAll not permitted");
568: }
569:
570: public boolean retainAll(Collection<?> c) {
571: throw new UnsupportedOperationException(
572: "unmodifiableList: retainAll not permitted");
573: }
574:
575: public T set(int index, T element) {
576: throw new UnsupportedOperationException(
577: "unmodifiableList: set not permitted");
578: }
579:
580: public int size() {
581: return list.size();
582: }
583:
584: public List<T> subList(int fromIndex, int toIndex) {
585: throw new UnsupportedOperationException(
586: "unmodifiableList: subList not permitted");
587: }
588:
589: public Object[] toArray() {
590: return list.toArray();
591: }
592:
593: public <OT> OT[] toArray(OT[] array) {
594: return list.toArray(array);
595: }
596: };
597: };
598:
599: public static <K, V> Map<K, V> unmodifiableMap(
600: final Map<? extends K, ? extends V> map) {
601: return new Map<K, V>() {
602:
603: public void clear() {
604: throw new UnsupportedOperationException(
605: "unmodifiableMap: clear not permitted");
606: }
607:
608: public boolean containsKey(Object key) {
609: return map.containsKey(key);
610: }
611:
612: public boolean containsValue(Object value) {
613: return map.containsValue(value);
614: }
615:
616: public Set<Map.Entry<K, V>> entrySet() {
617: Set<? extends Map.Entry<? extends K, ? extends V>> entrySet = map
618: .entrySet();
619: return (Set<Map.Entry<K, V>>) entrySet;
620: }
621:
622: public V get(Object key) {
623: return map.get(key);
624: }
625:
626: public boolean isEmpty() {
627: return map.isEmpty();
628: }
629:
630: public Set<K> keySet() {
631: return (Set<K>) map.keySet();
632: }
633:
634: public V put(K key, V value) {
635: throw new UnsupportedOperationException(
636: "unmodifiableMap: put not permitted");
637: }
638:
639: public void putAll(Map<? extends K, ? extends V> t) {
640: throw new UnsupportedOperationException(
641: "unmodifiableMap: putAll not permitted");
642: }
643:
644: public V remove(Object key) {
645: throw new UnsupportedOperationException(
646: "unmodifiableMap: remove not permitted");
647: }
648:
649: public int size() {
650: return map.size();
651: }
652:
653: public Collection<V> values() {
654: return (Collection<V>) map.values();
655: }
656:
657: };
658: }
659:
660: public static <T> Set<T> unmodifiableSet(final Set<? extends T> set) {
661: return new Set<T>() {
662:
663: public boolean add(T o) {
664: throw new UnsupportedOperationException(
665: "unmodifiableSet: add not permitted");
666: }
667:
668: public boolean addAll(Collection<? extends T> c) {
669: throw new UnsupportedOperationException(
670: "unmodifiableSet: addAll not permitted");
671: }
672:
673: public void clear() {
674: throw new UnsupportedOperationException(
675: "unmodifiableSet: clear not permitted");
676: }
677:
678: public boolean contains(Object o) {
679: return set.contains(o);
680: }
681:
682: public boolean containsAll(Collection<?> c) {
683: return set.containsAll(c);
684: }
685:
686: public boolean isEmpty() {
687: return set.isEmpty();
688: }
689:
690: public Iterator<T> iterator() {
691: final Iterator<? extends T> it = set.iterator();
692: return new Iterator<T>() {
693:
694: public boolean hasNext() {
695: return it.hasNext();
696: }
697:
698: public T next() {
699: return it.next();
700: }
701:
702: public void remove() {
703: throw new UnsupportedOperationException(
704: "unmodifiableCollection.iterator: remove not permitted");
705: }
706: };
707: }
708:
709: public boolean remove(Object o) {
710: throw new UnsupportedOperationException(
711: "unmodifiableSet: remove not permitted");
712: }
713:
714: public boolean removeAll(Collection<?> c) {
715: throw new UnsupportedOperationException(
716: "unmodifiableSet: removeAll not permitted");
717: }
718:
719: public boolean retainAll(Collection<?> c) {
720: throw new UnsupportedOperationException(
721: "unmodifiableSet: retainAll not permitted");
722: }
723:
724: public int size() {
725: return set.size();
726: }
727:
728: public Object[] toArray() {
729: return set.toArray();
730: }
731:
732: public <OT> OT[] toArray(OT[] a) {
733: return set.toArray(a);
734: }
735:
736: };
737: }
738:
739: public static <K, V> SortedMap<K, V> unmodifiableSortedMap(
740: SortedMap<? extends K, ? extends V> map) {
741: throw new UnsupportedOperationException(
742: "unmodifiableSortedMap not implemented");
743: }
744:
745: public static <T> SortedSet<T> unmodifiableSortedSet(
746: SortedSet<? extends T> set) {
747: throw new UnsupportedOperationException(
748: "unmodifiableSortedSet not implemented");
749: }
750:
751: /**
752: * Replace contents of a list from an array.
753: *
754: * @param <T> element type
755: * @param target list to replace contents from an array
756: * @param x an Object array which can contain only T instances
757: */
758: @SuppressWarnings("unchecked")
759: private static <T> void replaceContents(List<T> target, Object[] x) {
760: int size = target.size();
761: assert (x.length == size);
762: for (int i = 0; i < size; i++) {
763: target.set(i, (T) x[i]);
764: }
765: }
766:
767: private static <T> void swapImpl(List<T> list, int i, int j) {
768: T t = list.get(i);
769: list.set(i, list.get(j));
770: list.set(j, t);
771: }
772: }
|