001 /* Collections.java -- Utility class with methods to operate on collections
002 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005, 2006
003 Free Software Foundation, Inc.
004
005 This file is part of GNU Classpath.
006
007 GNU Classpath is free software; you can redistribute it and/or modify
008 it under the terms of the GNU General Public License as published by
009 the Free Software Foundation; either version 2, or (at your option)
010 any later version.
011
012 GNU Classpath is distributed in the hope that it will be useful, but
013 WITHOUT ANY WARRANTY; without even the implied warranty of
014 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
015 General Public License for more details.
016
017 You should have received a copy of the GNU General Public License
018 along with GNU Classpath; see the file COPYING. If not, write to the
019 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
020 02110-1301 USA.
021
022 Linking this library statically or dynamically with other modules is
023 making a combined work based on this library. Thus, the terms and
024 conditions of the GNU General Public License cover the whole
025 combination.
026
027 As a special exception, the copyright holders of this library give you
028 permission to link this library with independent modules to produce an
029 executable, regardless of the license terms of these independent
030 modules, and to copy and distribute the resulting executable under
031 terms of your choice, provided that you also meet, for each linked
032 independent module, the terms and conditions of the license of that
033 module. An independent module is a module which is not derived from
034 or based on this library. If you modify this library, you may extend
035 this exception to your version of the library, but you are not
036 obligated to do so. If you do not wish to do so, delete this
037 exception statement from your version. */
038
039
040 package java.util;
041
042 import java.io.Serializable;
043
044 /**
045 * Utility class consisting of static methods that operate on, or return
046 * Collections. Contains methods to sort, search, reverse, fill and shuffle
047 * Collections, methods to facilitate interoperability with legacy APIs that
048 * are unaware of collections, a method to return a list which consists of
049 * multiple copies of one element, and methods which "wrap" collections to give
050 * them extra properties, such as thread-safety and unmodifiability.
051 * <p>
052 *
053 * All methods which take a collection throw a {@link NullPointerException} if
054 * that collection is null. Algorithms which can change a collection may, but
055 * are not required, to throw the {@link UnsupportedOperationException} that
056 * the underlying collection would throw during an attempt at modification.
057 * For example,
058 * <code>Collections.singleton("").addAll(Collections.EMPTY_SET)</code>
059 * does not throw a exception, even though addAll is an unsupported operation
060 * on a singleton; the reason for this is that addAll did not attempt to
061 * modify the set.
062 *
063 * @author Original author unknown
064 * @author Eric Blake (ebb9@email.byu.edu)
065 * @author Tom Tromey (tromey@redhat.com)
066 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
067 * @see Collection
068 * @see Set
069 * @see List
070 * @see Map
071 * @see Arrays
072 * @since 1.2
073 * @status updated to 1.5
074 */
075 public class Collections
076 {
077 /**
078 * Constant used to decide cutoff for when a non-RandomAccess list should
079 * be treated as sequential-access. Basically, quadratic behavior is
080 * acceptable for small lists when the overhead is so small in the first
081 * place. I arbitrarily set it to 16, so it may need some tuning.
082 */
083 private static final int LARGE_LIST_SIZE = 16;
084
085 /**
086 * Determines if a list should be treated as a sequential-access one.
087 * Rather than the old method of JDK 1.3 of assuming only instanceof
088 * AbstractSequentialList should be sequential, this uses the new method
089 * of JDK 1.4 of assuming anything that does NOT implement RandomAccess
090 * and exceeds a large (unspecified) size should be sequential.
091 *
092 * @param l the list to check
093 * @return <code>true</code> if it should be treated as sequential-access
094 */
095 private static boolean isSequential(List<?> l)
096 {
097 return ! (l instanceof RandomAccess) && l.size() > LARGE_LIST_SIZE;
098 }
099
100 /**
101 * This class is non-instantiable.
102 */
103 private Collections()
104 {
105 }
106
107 /**
108 * An immutable, serializable, empty Set.
109 * @see Serializable
110 */
111 public static final Set EMPTY_SET = new EmptySet();
112
113 /**
114 * Returns an immutable, serializable parameterized empty set.
115 * Unlike the constant <code>EMPTY_SET</code>, the set returned by
116 * this method is type-safe.
117 *
118 * @return an empty parameterized set.
119 * @since 1.5
120 */
121 public static final <T> Set<T> emptySet()
122 {
123 /* FIXME: Could this be optimized? */
124 return new EmptySet<T>();
125 }
126
127 /**
128 * The implementation of {@link #EMPTY_SET}. This class name is required
129 * for compatibility with Sun's JDK serializability.
130 *
131 * @author Eric Blake (ebb9@email.byu.edu)
132 */
133 private static final class EmptySet<T> extends AbstractSet<T>
134 implements Serializable
135 {
136 /**
137 * Compatible with JDK 1.4.
138 */
139 private static final long serialVersionUID = 1582296315990362920L;
140
141 /**
142 * A private constructor adds overhead.
143 */
144 EmptySet()
145 {
146 }
147
148 /**
149 * The size: always 0!
150 * @return 0.
151 */
152 public int size()
153 {
154 return 0;
155 }
156
157 /**
158 * Returns an iterator that does not iterate.
159 * @return A non-iterating iterator.
160 */
161 // This is really cheating! I think it's perfectly valid, though.
162 public Iterator<T> iterator()
163 {
164 return (Iterator<T>) EMPTY_LIST.iterator();
165 }
166
167 // The remaining methods are optional, but provide a performance
168 // advantage by not allocating unnecessary iterators in AbstractSet.
169 /**
170 * The empty set never contains anything.
171 * @param o The object to search for.
172 * @return <code>false</code>.
173 */
174 public boolean contains(Object o)
175 {
176 return false;
177 }
178
179 /**
180 * This is true only if the given collection is also empty.
181 * @param c The collection of objects which are to be compared
182 * against the members of this set.
183 * @return <code>true</code> if c is empty.
184 */
185 public boolean containsAll(Collection<?> c)
186 {
187 return c.isEmpty();
188 }
189
190 /**
191 * Equal only if the other set is empty.
192 * @param o The object to compare with this set.
193 * @return <code>true</code> if o is an empty instance of <code>Set</code>.
194 */
195 public boolean equals(Object o)
196 {
197 return o instanceof Set && ((Set) o).isEmpty();
198 }
199
200 /**
201 * The hashcode is always 0.
202 * @return 0.
203 */
204 public int hashCode()
205 {
206 return 0;
207 }
208
209 /**
210 * Always succeeds with a <code>false</code> result.
211 * @param o The object to remove.
212 * @return <code>false</code>.
213 */
214 public boolean remove(Object o)
215 {
216 return false;
217 }
218
219 /**
220 * Always succeeds with a <code>false</code> result.
221 * @param c The collection of objects which should
222 * all be removed from this set.
223 * @return <code>false</code>.
224 */
225 public boolean removeAll(Collection<?> c)
226 {
227 return false;
228 }
229
230 /**
231 * Always succeeds with a <code>false</code> result.
232 * @param c The collection of objects which should
233 * all be retained within this set.
234 * @return <code>false</code>.
235 */
236 public boolean retainAll(Collection<?> c)
237 {
238 return false;
239 }
240
241 /**
242 * The array is always empty.
243 * @return A new array with a size of 0.
244 */
245 public Object[] toArray()
246 {
247 return new Object[0];
248 }
249
250 /**
251 * We don't even need to use reflection!
252 * @param a An existing array, which can be empty.
253 * @return The original array with any existing
254 * initial element set to null.
255 */
256 public <E> E[] toArray(E[] a)
257 {
258 if (a.length > 0)
259 a[0] = null;
260 return a;
261 }
262
263 /**
264 * The string never changes.
265 *
266 * @return the string "[]".
267 */
268 public String toString()
269 {
270 return "[]";
271 }
272 } // class EmptySet
273
274 /**
275 * An immutable, serializable, empty List, which implements RandomAccess.
276 * @see Serializable
277 * @see RandomAccess
278 */
279 public static final List EMPTY_LIST = new EmptyList();
280
281 /**
282 * Returns an immutable, serializable parameterized empty list.
283 * Unlike the constant <code>EMPTY_LIST</code>, the list returned by
284 * this method is type-safe.
285 *
286 * @return an empty parameterized list.
287 * @since 1.5
288 */
289 public static final <T> List<T> emptyList()
290 {
291 /* FIXME: Could this be optimized? */
292 return new EmptyList<T>();
293 }
294
295 /**
296 * The implementation of {@link #EMPTY_LIST}. This class name is required
297 * for compatibility with Sun's JDK serializability.
298 *
299 * @author Eric Blake (ebb9@email.byu.edu)
300 */
301 private static final class EmptyList<T> extends AbstractList<T>
302 implements Serializable, RandomAccess
303 {
304 /**
305 * Compatible with JDK 1.4.
306 */
307 private static final long serialVersionUID = 8842843931221139166L;
308
309 /**
310 * A private constructor adds overhead.
311 */
312 EmptyList()
313 {
314 }
315
316 /**
317 * The size is always 0.
318 * @return 0.
319 */
320 public int size()
321 {
322 return 0;
323 }
324
325 /**
326 * No matter the index, it is out of bounds. This
327 * method never returns, throwing an exception instead.
328 *
329 * @param index The index of the element to retrieve.
330 * @return the object at the specified index.
331 * @throws IndexOutOfBoundsException as any given index
332 * is outside the bounds of an empty array.
333 */
334 public T get(int index)
335 {
336 throw new IndexOutOfBoundsException();
337 }
338
339 // The remaining methods are optional, but provide a performance
340 // advantage by not allocating unnecessary iterators in AbstractList.
341 /**
342 * Never contains anything.
343 * @param o The object to search for.
344 * @return <code>false</code>.
345 */
346 public boolean contains(Object o)
347 {
348 return false;
349 }
350
351 /**
352 * This is true only if the given collection is also empty.
353 * @param c The collection of objects, which should be compared
354 * against the members of this list.
355 * @return <code>true</code> if c is also empty.
356 */
357 public boolean containsAll(Collection<?> c)
358 {
359 return c.isEmpty();
360 }
361
362 /**
363 * Equal only if the other list is empty.
364 * @param o The object to compare against this list.
365 * @return <code>true</code> if o is also an empty instance of
366 * <code>List</code>.
367 */
368 public boolean equals(Object o)
369 {
370 return o instanceof List && ((List) o).isEmpty();
371 }
372
373 /**
374 * The hashcode is always 1.
375 * @return 1.
376 */
377 public int hashCode()
378 {
379 return 1;
380 }
381
382 /**
383 * Returns -1.
384 * @param o The object to search for.
385 * @return -1.
386 */
387 public int indexOf(Object o)
388 {
389 return -1;
390 }
391
392 /**
393 * Returns -1.
394 * @param o The object to search for.
395 * @return -1.
396 */
397 public int lastIndexOf(Object o)
398 {
399 return -1;
400 }
401
402 /**
403 * Always succeeds with <code>false</code> result.
404 * @param o The object to remove.
405 * @return -1.
406 */
407 public boolean remove(Object o)
408 {
409 return false;
410 }
411
412 /**
413 * Always succeeds with <code>false</code> result.
414 * @param c The collection of objects which should
415 * all be removed from this list.
416 * @return <code>false</code>.
417 */
418 public boolean removeAll(Collection<?> c)
419 {
420 return false;
421 }
422
423 /**
424 * Always succeeds with <code>false</code> result.
425 * @param c The collection of objects which should
426 * all be retained within this list.
427 * @return <code>false</code>.
428 */
429 public boolean retainAll(Collection<?> c)
430 {
431 return false;
432 }
433
434 /**
435 * The array is always empty.
436 * @return A new array with a size of 0.
437 */
438 public Object[] toArray()
439 {
440 return new Object[0];
441 }
442
443 /**
444 * We don't even need to use reflection!
445 * @param a An existing array, which can be empty.
446 * @return The original array with any existing
447 * initial element set to null.
448 */
449 public <E> E[] toArray(E[] a)
450 {
451 if (a.length > 0)
452 a[0] = null;
453 return a;
454 }
455
456 /**
457 * The string never changes.
458 *
459 * @return the string "[]".
460 */
461 public String toString()
462 {
463 return "[]";
464 }
465 } // class EmptyList
466
467 /**
468 * An immutable, serializable, empty Map.
469 * @see Serializable
470 */
471 public static final Map EMPTY_MAP = new EmptyMap();
472
473 /**
474 * Returns an immutable, serializable parameterized empty map.
475 * Unlike the constant <code>EMPTY_MAP</code>, the map returned by
476 * this method is type-safe.
477 *
478 * @return an empty parameterized map.
479 * @since 1.5
480 */
481 public static final <K,V> Map<K,V> emptyMap()
482 {
483 /* FIXME: Could this be optimized? */
484 return new EmptyMap<K,V>();
485 }
486
487 /**
488 * The implementation of {@link #EMPTY_MAP}. This class name is required
489 * for compatibility with Sun's JDK serializability.
490 *
491 * @author Eric Blake (ebb9@email.byu.edu)
492 */
493 private static final class EmptyMap<K, V> extends AbstractMap<K, V>
494 implements Serializable
495 {
496 /**
497 * Compatible with JDK 1.4.
498 */
499 private static final long serialVersionUID = 6428348081105594320L;
500
501 /**
502 * A private constructor adds overhead.
503 */
504 EmptyMap()
505 {
506 }
507
508 /**
509 * There are no entries.
510 * @return The empty set.
511 */
512 public Set<Map.Entry<K, V>> entrySet()
513 {
514 return EMPTY_SET;
515 }
516
517 // The remaining methods are optional, but provide a performance
518 // advantage by not allocating unnecessary iterators in AbstractMap.
519 /**
520 * No entries!
521 * @param key The key to search for.
522 * @return <code>false</code>.
523 */
524 public boolean containsKey(Object key)
525 {
526 return false;
527 }
528
529 /**
530 * No entries!
531 * @param value The value to search for.
532 * @return <code>false</code>.
533 */
534 public boolean containsValue(Object value)
535 {
536 return false;
537 }
538
539 /**
540 * Equal to all empty maps.
541 * @param o The object o to compare against this map.
542 * @return <code>true</code> if o is also an empty instance of
543 * <code>Map</code>.
544 */
545 public boolean equals(Object o)
546 {
547 return o instanceof Map && ((Map) o).isEmpty();
548 }
549
550 /**
551 * No mappings, so this returns null.
552 * @param o The key of the object to retrieve.
553 * @return null.
554 */
555 public V get(Object o)
556 {
557 return null;
558 }
559
560 /**
561 * The hashcode is always 0.
562 * @return 0.
563 */
564 public int hashCode()
565 {
566 return 0;
567 }
568
569 /**
570 * No entries.
571 * @return The empty set.
572 */
573 public Set<K> keySet()
574 {
575 return EMPTY_SET;
576 }
577
578 /**
579 * Remove always succeeds, with null result.
580 * @param o The key of the mapping to remove.
581 * @return null, as there is never a mapping for o.
582 */
583 public V remove(Object o)
584 {
585 return null;
586 }
587
588 /**
589 * Size is always 0.
590 * @return 0.
591 */
592 public int size()
593 {
594 return 0;
595 }
596
597 /**
598 * No entries. Technically, EMPTY_SET, while more specific than a general
599 * Collection, will work. Besides, that's what the JDK uses!
600 * @return The empty set.
601 */
602 public Collection<V> values()
603 {
604 return EMPTY_SET;
605 }
606
607 /**
608 * The string never changes.
609 *
610 * @return the string "[]".
611 */
612 public String toString()
613 {
614 return "[]";
615 }
616 } // class EmptyMap
617
618
619 /**
620 * Compare two objects with or without a Comparator. If c is null, uses the
621 * natural ordering. Slightly slower than doing it inline if the JVM isn't
622 * clever, but worth it for removing a duplicate of the search code.
623 * Note: This code is also used in Arrays (for sort as well as search).
624 */
625 static final <T> int compare(T o1, T o2, Comparator<? super T> c)
626 {
627 return c == null ? ((Comparable) o1).compareTo(o2) : c.compare(o1, o2);
628 }
629
630 /**
631 * Perform a binary search of a List for a key, using the natural ordering of
632 * the elements. The list must be sorted (as by the sort() method) - if it is
633 * not, the behavior of this method is undefined, and may be an infinite
634 * loop. Further, the key must be comparable with every item in the list. If
635 * the list contains the key more than once, any one of them may be found.
636 * <p>
637 *
638 * This algorithm behaves in log(n) time for {@link RandomAccess} lists,
639 * and uses a linear search with O(n) link traversals and log(n) comparisons
640 * with {@link AbstractSequentialList} lists. Note: although the
641 * specification allows for an infinite loop if the list is unsorted, it will
642 * not happen in this (Classpath) implementation.
643 *
644 * @param l the list to search (must be sorted)
645 * @param key the value to search for
646 * @return the index at which the key was found, or -n-1 if it was not
647 * found, where n is the index of the first value higher than key or
648 * a.length if there is no such value
649 * @throws ClassCastException if key could not be compared with one of the
650 * elements of l
651 * @throws NullPointerException if a null element has compareTo called
652 * @see #sort(List)
653 */
654 public static <T> int binarySearch(List<? extends Comparable<? super T>> l,
655 T key)
656 {
657 return binarySearch(l, key, null);
658 }
659
660 /**
661 * Perform a binary search of a List for a key, using a supplied Comparator.
662 * The list must be sorted (as by the sort() method with the same Comparator)
663 * - if it is not, the behavior of this method is undefined, and may be an
664 * infinite loop. Further, the key must be comparable with every item in the
665 * list. If the list contains the key more than once, any one of them may be
666 * found. If the comparator is null, the elements' natural ordering is used.
667 * <p>
668 *
669 * This algorithm behaves in log(n) time for {@link RandomAccess} lists,
670 * and uses a linear search with O(n) link traversals and log(n) comparisons
671 * with {@link AbstractSequentialList} lists. Note: although the
672 * specification allows for an infinite loop if the list is unsorted, it will
673 * not happen in this (Classpath) implementation.
674 *
675 * @param l the list to search (must be sorted)
676 * @param key the value to search for
677 * @param c the comparator by which the list is sorted
678 * @return the index at which the key was found, or -n-1 if it was not
679 * found, where n is the index of the first value higher than key or
680 * a.length if there is no such value
681 * @throws ClassCastException if key could not be compared with one of the
682 * elements of l
683 * @throws NullPointerException if a null element is compared with natural
684 * ordering (only possible when c is null)
685 * @see #sort(List, Comparator)
686 */
687 public static <T> int binarySearch(List<? extends T> l, T key,
688 Comparator<? super T> c)
689 {
690 int pos = 0;
691 int low = 0;
692 int hi = l.size() - 1;
693
694 // We use a linear search with log(n) comparisons using an iterator
695 // if the list is sequential-access.
696 if (isSequential(l))
697 {
698 ListIterator<T> itr = ((List<T>) l).listIterator();
699 int i = 0;
700 T o = itr.next(); // Assumes list is not empty (see isSequential)
701 boolean forward = true;
702 while (low <= hi)
703 {
704 pos = (low + hi) >>> 1;
705 if (i < pos)
706 {
707 if (!forward)
708 itr.next(); // Changing direction first.
709 for ( ; i != pos; i++, o = itr.next())
710 ;
711 forward = true;
712 }
713 else
714 {
715 if (forward)
716 itr.previous(); // Changing direction first.
717 for ( ; i != pos; i--, o = itr.previous())
718 ;
719 forward = false;
720 }
721 final int d = compare(o, key, c);
722 if (d == 0)
723 return pos;
724 else if (d > 0)
725 hi = pos - 1;
726 else
727 // This gets the insertion point right on the last loop
728 low = ++pos;
729 }
730 }
731 else
732 {
733 while (low <= hi)
734 {
735 pos = (low + hi) >>> 1;
736 final int d = compare(((List<T>) l).get(pos), key, c);
737 if (d == 0)
738 return pos;
739 else if (d > 0)
740 hi = pos - 1;
741 else
742 // This gets the insertion point right on the last loop
743 low = ++pos;
744 }
745 }
746
747 // If we failed to find it, we do the same whichever search we did.
748 return -pos - 1;
749 }
750
751 /**
752 * Copy one list to another. If the destination list is longer than the
753 * source list, the remaining elements are unaffected. This method runs in
754 * linear time.
755 *
756 * @param dest the destination list
757 * @param source the source list
758 * @throws IndexOutOfBoundsException if the destination list is shorter
759 * than the source list (the destination will be unmodified)
760 * @throws UnsupportedOperationException if dest.listIterator() does not
761 * support the set operation
762 */
763 public static <T> void copy(List<? super T> dest, List<? extends T> source)
764 {
765 int pos = source.size();
766 if (dest.size() < pos)
767 throw new IndexOutOfBoundsException("Source does not fit in dest");
768
769 Iterator<? extends T> i1 = source.iterator();
770 ListIterator<? super T> i2 = dest.listIterator();
771
772 while (--pos >= 0)
773 {
774 i2.next();
775 i2.set(i1.next());
776 }
777 }
778
779 /**
780 * Returns an Enumeration over a collection. This allows interoperability
781 * with legacy APIs that require an Enumeration as input.
782 *
783 * @param c the Collection to iterate over
784 * @return an Enumeration backed by an Iterator over c
785 */
786 public static <T> Enumeration<T> enumeration(Collection<T> c)
787 {
788 final Iterator<T> i = c.iterator();
789 return new Enumeration<T>()
790 {
791 /**
792 * Returns <code>true</code> if there are more elements to
793 * be enumerated.
794 *
795 * @return The result of <code>hasNext()</code>
796 * called on the underlying iterator.
797 */
798 public final boolean hasMoreElements()
799 {
800 return i.hasNext();
801 }
802
803 /**
804 * Returns the next element to be enumerated.
805 *
806 * @return The result of <code>next()</code>
807 * called on the underlying iterator.
808 */
809 public final T nextElement()
810 {
811 return i.next();
812 }
813 };
814 }
815
816 /**
817 * Replace every element of a list with a given value. This method runs in
818 * linear time.
819 *
820 * @param l the list to fill.
821 * @param val the object to vill the list with.
822 * @throws UnsupportedOperationException if l.listIterator() does not
823 * support the set operation.
824 */
825 public static <T> void fill(List<? super T> l, T val)
826 {
827 ListIterator<? super T> itr = l.listIterator();
828 for (int i = l.size() - 1; i >= 0; --i)
829 {
830 itr.next();
831 itr.set(val);
832 }
833 }
834
835 /**
836 * Returns the starting index where the specified sublist first occurs
837 * in a larger list, or -1 if there is no matching position. If
838 * <code>target.size() > source.size()</code>, this returns -1,
839 * otherwise this implementation uses brute force, checking for
840 * <code>source.sublist(i, i + target.size()).equals(target)</code>
841 * for all possible i.
842 *
843 * @param source the list to search
844 * @param target the sublist to search for
845 * @return the index where found, or -1
846 * @since 1.4
847 */
848 public static int indexOfSubList(List<?> source, List<?> target)
849 {
850 int ssize = source.size();
851 for (int i = 0, j = target.size(); j <= ssize; i++, j++)
852 if (source.subList(i, j).equals(target))
853 return i;
854 return -1;
855 }
856
857 /**
858 * Returns the starting index where the specified sublist last occurs
859 * in a larger list, or -1 if there is no matching position. If
860 * <code>target.size() > source.size()</code>, this returns -1,
861 * otherwise this implementation uses brute force, checking for
862 * <code>source.sublist(i, i + target.size()).equals(target)</code>
863 * for all possible i.
864 *
865 * @param source the list to search
866 * @param target the sublist to search for
867 * @return the index where found, or -1
868 * @since 1.4
869 */
870 public static int lastIndexOfSubList(List<?> source, List<?> target)
871 {
872 int ssize = source.size();
873 for (int i = ssize - target.size(), j = ssize; i >= 0; i--, j--)
874 if (source.subList(i, j).equals(target))
875 return i;
876 return -1;
877 }
878
879 /**
880 * Returns an ArrayList holding the elements visited by a given
881 * Enumeration. This method exists for interoperability between legacy
882 * APIs and the new Collection API.
883 *
884 * @param e the enumeration to put in a list
885 * @return a list containing the enumeration elements
886 * @see ArrayList
887 * @since 1.4
888 */
889 public static <T> ArrayList<T> list(Enumeration<T> e)
890 {
891 ArrayList<T> l = new ArrayList<T>();
892 while (e.hasMoreElements())
893 l.add(e.nextElement());
894 return l;
895 }
896
897 /**
898 * Find the maximum element in a Collection, according to the natural
899 * ordering of the elements. This implementation iterates over the
900 * Collection, so it works in linear time.
901 *
902 * @param c the Collection to find the maximum element of
903 * @return the maximum element of c
904 * @exception NoSuchElementException if c is empty
905 * @exception ClassCastException if elements in c are not mutually comparable
906 * @exception NullPointerException if null.compareTo is called
907 */
908 public static <T extends Object & Comparable<? super T>>
909 T max(Collection<? extends T> c)
910 {
911 return max(c, null);
912 }
913
914 /**
915 * Find the maximum element in a Collection, according to a specified
916 * Comparator. This implementation iterates over the Collection, so it
917 * works in linear time.
918 *
919 * @param c the Collection to find the maximum element of
920 * @param order the Comparator to order the elements by, or null for natural
921 * ordering
922 * @return the maximum element of c
923 * @throws NoSuchElementException if c is empty
924 * @throws ClassCastException if elements in c are not mutually comparable
925 * @throws NullPointerException if null is compared by natural ordering
926 * (only possible when order is null)
927 */
928 public static <T> T max(Collection<? extends T> c,
929 Comparator<? super T> order)
930 {
931 Iterator<? extends T> itr = c.iterator();
932 T max = itr.next(); // throws NoSuchElementException
933 int csize = c.size();
934 for (int i = 1; i < csize; i++)
935 {
936 T o = itr.next();
937 if (compare(max, o, order) < 0)
938 max = o;
939 }
940 return max;
941 }
942
943 /**
944 * Find the minimum element in a Collection, according to the natural
945 * ordering of the elements. This implementation iterates over the
946 * Collection, so it works in linear time.
947 *
948 * @param c the Collection to find the minimum element of
949 * @return the minimum element of c
950 * @throws NoSuchElementException if c is empty
951 * @throws ClassCastException if elements in c are not mutually comparable
952 * @throws NullPointerException if null.compareTo is called
953 */
954 public static <T extends Object & Comparable<? super T>>
955 T min(Collection<? extends T> c)
956 {
957 return min(c, null);
958 }
959
960 /**
961 * Find the minimum element in a Collection, according to a specified
962 * Comparator. This implementation iterates over the Collection, so it
963 * works in linear time.
964 *
965 * @param c the Collection to find the minimum element of
966 * @param order the Comparator to order the elements by, or null for natural
967 * ordering
968 * @return the minimum element of c
969 * @throws NoSuchElementException if c is empty
970 * @throws ClassCastException if elements in c are not mutually comparable
971 * @throws NullPointerException if null is compared by natural ordering
972 * (only possible when order is null)
973 */
974 public static <T> T min(Collection<? extends T> c,
975 Comparator<? super T> order)
976 {
977 Iterator<? extends T> itr = c.iterator();
978 T min = itr.next(); // throws NoSuchElementExcception
979 int csize = c.size();
980 for (int i = 1; i < csize; i++)
981 {
982 T o = itr.next();
983 if (compare(min, o, order) > 0)
984 min = o;
985 }
986 return min;
987 }
988
989 /**
990 * Creates an immutable list consisting of the same object repeated n times.
991 * The returned object is tiny, consisting of only a single reference to the
992 * object and a count of the number of elements. It is Serializable, and
993 * implements RandomAccess. You can use it in tandem with List.addAll for
994 * fast list construction.
995 *
996 * @param n the number of times to repeat the object
997 * @param o the object to repeat
998 * @return a List consisting of n copies of o
999 * @throws IllegalArgumentException if n < 0
1000 * @see List#addAll(Collection)
1001 * @see Serializable
1002 * @see RandomAccess
1003 */
1004 public static <T> List<T> nCopies(final int n, final T o)
1005 {
1006 return new CopiesList<T>(n, o);
1007 }
1008
1009 /**
1010 * The implementation of {@link #nCopies(int, Object)}. This class name
1011 * is required for compatibility with Sun's JDK serializability.
1012 *
1013 * @author Eric Blake (ebb9@email.byu.edu)
1014 */
1015 private static final class CopiesList<T> extends AbstractList<T>
1016 implements Serializable, RandomAccess
1017 {
1018 /**
1019 * Compatible with JDK 1.4.
1020 */
1021 private static final long serialVersionUID = 2739099268398711800L;
1022
1023 /**
1024 * The count of elements in this list.
1025 * @serial the list size
1026 */
1027 private final int n;
1028
1029 /**
1030 * The repeated list element.
1031 * @serial the list contents
1032 */
1033 private final T element;
1034
1035 /**
1036 * Constructs the list.
1037 *
1038 * @param n the count
1039 * @param o the object
1040 * @throws IllegalArgumentException if n < 0
1041 */
1042 CopiesList(int n, T o)
1043 {
1044 if (n < 0)
1045 throw new IllegalArgumentException();
1046 this.n = n;
1047 element = o;
1048 }
1049
1050 /**
1051 * The size is fixed.
1052 * @return The size of the list.
1053 */
1054 public int size()
1055 {
1056 return n;
1057 }
1058
1059 /**
1060 * The same element is returned.
1061 * @param index The index of the element to be returned (irrelevant
1062 * as the list contains only copies of <code>element</code>).
1063 * @return The element used by this list.
1064 */
1065 public T get(int index)
1066 {
1067 if (index < 0 || index >= n)
1068 throw new IndexOutOfBoundsException();
1069 return element;
1070 }
1071
1072 // The remaining methods are optional, but provide a performance
1073 // advantage by not allocating unnecessary iterators in AbstractList.
1074 /**
1075 * This list only contains one element.
1076 * @param o The object to search for.
1077 * @return <code>true</code> if o is the element used by this list.
1078 */
1079 public boolean contains(Object o)
1080 {
1081 return n > 0 && equals(o, element);
1082 }
1083
1084 /**
1085 * The index is either 0 or -1.
1086 * @param o The object to find the index of.
1087 * @return 0 if <code>o == element</code>, -1 if not.
1088 */
1089 public int indexOf(Object o)
1090 {
1091 return (n > 0 && equals(o, element)) ? 0 : -1;
1092 }
1093
1094 /**
1095 * The index is either n-1 or -1.
1096 * @param o The object to find the last index of.
1097 * @return The last index in the list if <code>o == element</code>,
1098 * -1 if not.
1099 */
1100 public int lastIndexOf(Object o)
1101 {
1102 return equals(o, element) ? n - 1 : -1;
1103 }
1104
1105 /**
1106 * A subList is just another CopiesList.
1107 * @param from The starting bound of the sublist.
1108 * @param to The ending bound of the sublist.
1109 * @return A list of copies containing <code>from - to</code>
1110 * elements, all of which are equal to the element
1111 * used by this list.
1112 */
1113 public List<T> subList(int from, int to)
1114 {
1115 if (from < 0 || to > n)
1116 throw new IndexOutOfBoundsException();
1117 return new CopiesList<T>(to - from, element);
1118 }
1119
1120 /**
1121 * The array is easy.
1122 * @return An array of size n filled with copies of
1123 * the element used by this list.
1124 */
1125 public Object[] toArray()
1126 {
1127 Object[] a = new Object[n];
1128 Arrays.fill(a, element);
1129 return a;
1130 }
1131
1132 /**
1133 * The string is easy to generate.
1134 * @return A string representation of the list.
1135 */
1136 public String toString()
1137 {
1138 StringBuffer r = new StringBuffer("{");
1139 for (int i = n - 1; --i > 0; )
1140 r.append(element).append(", ");
1141 r.append(element).append("}");
1142 return r.toString();
1143 }
1144 } // class CopiesList
1145
1146 /**
1147 * Replace all instances of one object with another in the specified list.
1148 * The list does not change size. An element e is replaced if
1149 * <code>oldval == null ? e == null : oldval.equals(e)</code>.
1150 *
1151 * @param list the list to iterate over
1152 * @param oldval the element to replace
1153 * @param newval the new value for the element
1154 * @return <code>true</code> if a replacement occurred.
1155 * @throws UnsupportedOperationException if the list iterator does not allow
1156 * for the set operation
1157 * @throws ClassCastException if newval is of a type which cannot be added
1158 * to the list
1159 * @throws IllegalArgumentException if some other aspect of newval stops
1160 * it being added to the list
1161 * @since 1.4
1162 */
1163 public static <T> boolean replaceAll(List<T> list, T oldval, T newval)
1164 {
1165 ListIterator<T> itr = list.listIterator();
1166 boolean replace_occured = false;
1167 for (int i = list.size(); --i >= 0; )
1168 if (AbstractCollection.equals(oldval, itr.next()))
1169 {
1170 itr.set(newval);
1171 replace_occured = true;
1172 }
1173 return replace_occured;
1174 }
1175
1176 /**
1177 * Reverse a given list. This method works in linear time.
1178 *
1179 * @param l the list to reverse
1180 * @throws UnsupportedOperationException if l.listIterator() does not
1181 * support the set operation
1182 */
1183 public static void reverse(List<?> l)
1184 {
1185 ListIterator i1 = l.listIterator();
1186 int pos1 = 1;
1187 int pos2 = l.size();
1188 ListIterator i2 = l.listIterator(pos2);
1189 while (pos1 < pos2)
1190 {
1191 Object o1 = i1.next();
1192 Object o2 = i2.previous();
1193 i1.set(o2);
1194 i2.set(o1);
1195 ++pos1;
1196 --pos2;
1197 }
1198 }
1199
1200 /**
1201 * Get a comparator that implements the reverse of the ordering
1202 * specified by the given Comparator. If the Comparator is null,
1203 * this is equivalent to {@link #reverseOrder()}. The return value
1204 * of this method is Serializable, if the specified Comparator is
1205 * either Serializable or null.
1206 *
1207 * @param c the comparator to invert
1208 * @return a comparator that imposes reverse ordering
1209 * @see Comparable
1210 * @see Serializable
1211 *
1212 * @since 1.5
1213 */
1214 public static <T> Comparator<T> reverseOrder(final Comparator<T> c)
1215 {
1216 if (c == null)
1217 return (Comparator<T>) rcInstance;
1218 return new ReverseComparator<T> ()
1219 {
1220 public int compare(T a, T b)
1221 {
1222 return - c.compare(a, b);
1223 }
1224 };
1225 }
1226
1227 /**
1228 * Get a comparator that implements the reverse of natural ordering. In
1229 * other words, this sorts Comparable objects opposite of how their
1230 * compareTo method would sort. This makes it easy to sort into reverse
1231 * order, by simply passing Collections.reverseOrder() to the sort method.
1232 * The return value of this method is Serializable.
1233 *
1234 * @return a comparator that imposes reverse natural ordering
1235 * @see Comparable
1236 * @see Serializable
1237 */
1238 public static <T> Comparator<T> reverseOrder()
1239 {
1240 return (Comparator<T>) rcInstance;
1241 }
1242
1243 /**
1244 * The object for {@link #reverseOrder()}.
1245 */
1246 private static final ReverseComparator rcInstance = new ReverseComparator();
1247
1248 /**
1249 * The implementation of {@link #reverseOrder()}. This class name
1250 * is required for compatibility with Sun's JDK serializability.
1251 *
1252 * @author Eric Blake (ebb9@email.byu.edu)
1253 */
1254 private static class ReverseComparator<T>
1255 implements Comparator<T>, Serializable
1256 {
1257 /**
1258 * Compatible with JDK 1.4.
1259 */
1260 private static final long serialVersionUID = 7207038068494060240L;
1261
1262 /**
1263 * A private constructor adds overhead.
1264 */
1265 ReverseComparator()
1266 {
1267 }
1268
1269 /**
1270 * Compare two objects in reverse natural order.
1271 *
1272 * @param a the first object
1273 * @param b the second object
1274 * @return <, ==, or > 0 according to b.compareTo(a)
1275 */
1276 public int compare(T a, T b)
1277 {
1278 return ((Comparable) b).compareTo(a);
1279 }
1280 }
1281
1282 /**
1283 * Rotate the elements in a list by a specified distance. After calling this
1284 * method, the element now at index <code>i</code> was formerly at index
1285 * <code>(i - distance) mod list.size()</code>. The list size is unchanged.
1286 * <p>
1287 *
1288 * For example, suppose a list contains <code>[t, a, n, k, s]</code>. After
1289 * either <code>Collections.rotate(l, 4)</code> or
1290 * <code>Collections.rotate(l, -1)</code>, the new contents are
1291 * <code>[s, t, a, n, k]</code>. This can be applied to sublists to rotate
1292 * just a portion of the list. For example, to move element <code>a</code>
1293 * forward two positions in the original example, use
1294 * <code>Collections.rotate(l.subList(1, 3+1), -1)</code>, which will
1295 * result in <code>[t, n, k, a, s]</code>.
1296 * <p>
1297 *
1298 * If the list is small or implements {@link RandomAccess}, the
1299 * implementation exchanges the first element to its destination, then the
1300 * displaced element, and so on until a circuit has been completed. The
1301 * process is repeated if needed on the second element, and so forth, until
1302 * all elements have been swapped. For large non-random lists, the
1303 * implementation breaks the list into two sublists at index
1304 * <code>-distance mod size</code>, calls {@link #reverse(List)} on the
1305 * pieces, then reverses the overall list.
1306 *
1307 * @param list the list to rotate
1308 * @param distance the distance to rotate by; unrestricted in value
1309 * @throws UnsupportedOperationException if the list does not support set
1310 * @since 1.4
1311 */
1312 public static void rotate(List<?> list, int distance)
1313 {
1314 int size = list.size();
1315 if (size == 0)
1316 return;
1317 distance %= size;
1318 if (distance == 0)
1319 return;
1320 if (distance < 0)
1321 distance += size;
1322
1323 if (isSequential(list))
1324 {
1325 reverse(list);
1326 reverse(list.subList(0, distance));
1327 reverse(list.subList(distance, size));
1328 }
1329 else
1330 {
1331 // Determine the least common multiple of distance and size, as there
1332 // are (distance / LCM) loops to cycle through.
1333 int a = size;
1334 int lcm = distance;
1335 int b = a % lcm;
1336 while (b != 0)
1337 {
1338 a = lcm;
1339 lcm = b;
1340 b = a % lcm;
1341 }
1342
1343 // Now, make the swaps. We must take the remainder every time through
1344 // the inner loop so that we don't overflow i to negative values.
1345 List<Object> objList = (List<Object>) list;
1346 while (--lcm >= 0)
1347 {
1348 Object o = objList.get(lcm);
1349 for (int i = lcm + distance; i != lcm; i = (i + distance) % size)
1350 o = objList.set(i, o);
1351 objList.set(lcm, o);
1352 }
1353 }
1354 }
1355
1356 /**
1357 * Shuffle a list according to a default source of randomness. The algorithm
1358 * used iterates backwards over the list, swapping each element with an
1359 * element randomly selected from the elements in positions less than or
1360 * equal to it (using r.nextInt(int)).
1361 * <p>
1362 *
1363 * This algorithm would result in a perfectly fair shuffle (that is, each
1364 * element would have an equal chance of ending up in any position) if r were
1365 * a perfect source of randomness. In practice the results are merely very
1366 * close to perfect.
1367 * <p>
1368 *
1369 * This method operates in linear time. To do this on large lists which do
1370 * not implement {@link RandomAccess}, a temporary array is used to acheive
1371 * this speed, since it would be quadratic access otherwise.
1372 *
1373 * @param l the list to shuffle
1374 * @throws UnsupportedOperationException if l.listIterator() does not
1375 * support the set operation
1376 */
1377 public static void shuffle(List<?> l)
1378 {
1379 if (defaultRandom == null)
1380 {
1381 synchronized (Collections.class)
1382 {
1383 if (defaultRandom == null)
1384 defaultRandom = new Random();
1385 }
1386 }
1387 shuffle(l, defaultRandom);
1388 }
1389
1390 /**
1391 * Cache a single Random object for use by shuffle(List). This improves
1392 * performance as well as ensuring that sequential calls to shuffle() will
1393 * not result in the same shuffle order occurring: the resolution of
1394 * System.currentTimeMillis() is not sufficient to guarantee a unique seed.
1395 */
1396 private static Random defaultRandom = null;
1397
1398 /**
1399 * Shuffle a list according to a given source of randomness. The algorithm
1400 * used iterates backwards over the list, swapping each element with an
1401 * element randomly selected from the elements in positions less than or
1402 * equal to it (using r.nextInt(int)).
1403 * <p>
1404 *
1405 * This algorithm would result in a perfectly fair shuffle (that is, each
1406 * element would have an equal chance of ending up in any position) if r were
1407 * a perfect source of randomness. In practise (eg if r = new Random()) the
1408 * results are merely very close to perfect.
1409 * <p>
1410 *
1411 * This method operates in linear time. To do this on large lists which do
1412 * not implement {@link RandomAccess}, a temporary array is used to acheive
1413 * this speed, since it would be quadratic access otherwise.
1414 *
1415 * @param l the list to shuffle
1416 * @param r the source of randomness to use for the shuffle
1417 * @throws UnsupportedOperationException if l.listIterator() does not
1418 * support the set operation
1419 */
1420 public static void shuffle(List<?> l, Random r)
1421 {
1422 int lsize = l.size();
1423 List<Object> list = (List<Object>) l;
1424 ListIterator<Object> i = list.listIterator(lsize);
1425 boolean sequential = isSequential(l);
1426 Object[] a = null; // stores a copy of the list for the sequential case
1427
1428 if (sequential)
1429 a = list.toArray();
1430
1431 for (int pos = lsize - 1; pos > 0; --pos)
1432 {
1433 // Obtain a random position to swap with. pos + 1 is used so that the
1434 // range of the random number includes the current position.
1435 int swap = r.nextInt(pos + 1);
1436
1437 // Swap the desired element.
1438 Object o;
1439 if (sequential)
1440 {
1441 o = a[swap];
1442 a[swap] = i.previous();
1443 }
1444 else
1445 o = list.set(swap, i.previous());
1446
1447 i.set(o);
1448 }
1449 }
1450
1451 /**
1452 * Returns the frequency of the specified object within the supplied
1453 * collection. The frequency represents the number of occurrences of
1454 * elements within the collection which return <code>true</code> when
1455 * compared with the object using the <code>equals</code> method.
1456 *
1457 * @param c the collection to scan for occurrences of the object.
1458 * @param o the object to locate occurrances of within the collection.
1459 * @throws NullPointerException if the collection is <code>null</code>.
1460 * @since 1.5
1461 */
1462 public static int frequency (Collection<?> c, Object o)
1463 {
1464 int result = 0;
1465 final Iterator<?> it = c.iterator();
1466 while (it.hasNext())
1467 {
1468 Object v = it.next();
1469 if (AbstractCollection.equals(o, v))
1470 ++result;
1471 }
1472 return result;
1473 }
1474
1475 /**
1476 * Adds all the specified elements to the given collection, in a similar
1477 * way to the <code>addAll</code> method of the <code>Collection</code>.
1478 * However, this is a variable argument method which allows the new elements
1479 * to be specified individually or in array form, as opposed to the list
1480 * required by the collection's <code>addAll</code> method. This has
1481 * benefits in both simplicity (multiple elements can be added without
1482 * having to be wrapped inside a grouping structure) and efficiency
1483 * (as a redundant list doesn't have to be created to add an individual
1484 * set of elements or an array).
1485 *
1486 * @param c the collection to which the elements should be added.
1487 * @param a the elements to be added to the collection.
1488 * @return true if the collection changed its contents as a result.
1489 * @throws UnsupportedOperationException if the collection does not support
1490 * addition.
1491 * @throws NullPointerException if one or more elements in a are null,
1492 * and the collection does not allow null
1493 * elements. This exception is also thrown
1494 * if either <code>c</code> or <code>a</code>
1495 * are null.
1496 * @throws IllegalArgumentException if the collection won't allow an element
1497 * to be added for some other reason.
1498 * @since 1.5
1499 */
1500 public static <T> boolean addAll(Collection<? super T> c, T... a)
1501 {
1502 boolean overall = false;
1503
1504 for (T element : a)
1505 {
1506 boolean result = c.add(element);
1507 if (result)
1508 overall = true;
1509 }
1510 return overall;
1511 }
1512
1513 /**
1514 * Returns true if the two specified collections have no elements in
1515 * common. This method may give unusual results if one or both collections
1516 * use a non-standard equality test. In the trivial case of comparing
1517 * a collection with itself, this method returns true if, and only if,
1518 * the collection is empty.
1519 *
1520 * @param c1 the first collection to compare.
1521 * @param c2 the second collection to compare.
1522 * @return true if the collections are disjoint.
1523 * @throws NullPointerException if either collection is null.
1524 * @since 1.5
1525 */
1526 public static boolean disjoint(Collection<?> c1, Collection<?> c2)
1527 {
1528 Collection<Object> oc1 = (Collection<Object>) c1;
1529 final Iterator<Object> it = oc1.iterator();
1530 while (it.hasNext())
1531 if (c2.contains(it.next()))
1532 return false;
1533 return true;
1534 }
1535
1536
1537 /**
1538 * Obtain an immutable Set consisting of a single element. The return value
1539 * of this method is Serializable.
1540 *
1541 * @param o the single element
1542 * @return an immutable Set containing only o
1543 * @see Serializable
1544 */
1545 public static <T> Set<T> singleton(T o)
1546 {
1547 return new SingletonSet<T>(o);
1548 }
1549
1550 /**
1551 * The implementation of {@link #singleton(Object)}. This class name
1552 * is required for compatibility with Sun's JDK serializability.
1553 *
1554 * @author Eric Blake (ebb9@email.byu.edu)
1555 */
1556 private static final class SingletonSet<T> extends AbstractSet<T>
1557 implements Serializable
1558 {
1559 /**
1560 * Compatible with JDK 1.4.
1561 */
1562 private static final long serialVersionUID = 3193687207550431679L;
1563
1564
1565 /**
1566 * The single element; package visible for use in nested class.
1567 * @serial the singleton
1568 */
1569 final T element;
1570
1571 /**
1572 * Construct a singleton.
1573 * @param o the element
1574 */
1575 SingletonSet(T o)
1576 {
1577 element = o;
1578 }
1579
1580 /**
1581 * The size: always 1!
1582 * @return 1.
1583 */
1584 public int size()
1585 {
1586 return 1;
1587 }
1588
1589 /**
1590 * Returns an iterator over the lone element.
1591 */
1592 public Iterator<T> iterator()
1593 {
1594 return new Iterator<T>()
1595 {
1596 /**
1597 * Flag to indicate whether or not the element has
1598 * been retrieved.
1599 */
1600 private boolean hasNext = true;
1601
1602 /**
1603 * Returns <code>true</code> if elements still remain to be
1604 * iterated through.
1605 *
1606 * @return <code>true</code> if the element has not yet been returned.
1607 */
1608 public boolean hasNext()
1609 {
1610 return hasNext;
1611 }
1612
1613 /**
1614 * Returns the element.
1615 *
1616 * @return The element used by this singleton.
1617 * @throws NoSuchElementException if the object
1618 * has already been retrieved.
1619 */
1620 public T next()
1621 {
1622 if (hasNext)
1623 {
1624 hasNext = false;
1625 return element;
1626 }
1627 else
1628 throw new NoSuchElementException();
1629 }
1630
1631 /**
1632 * Removes the element from the singleton.
1633 * As this set is immutable, this will always
1634 * throw an exception.
1635 *
1636 * @throws UnsupportedOperationException as the
1637 * singleton set doesn't support
1638 * <code>remove()</code>.
1639 */
1640 public void remove()
1641 {
1642 throw new UnsupportedOperationException();
1643 }
1644 };
1645 }
1646
1647 // The remaining methods are optional, but provide a performance
1648 // advantage by not allocating unnecessary iterators in AbstractSet.
1649 /**
1650 * The set only contains one element.
1651 *
1652 * @param o The object to search for.
1653 * @return <code>true</code> if o == the element of the singleton.
1654 */
1655 public boolean contains(Object o)
1656 {
1657 return equals(o, element);
1658 }
1659
1660 /**
1661 * This is true if the other collection only contains the element.
1662 *
1663 * @param c A collection to compare against this singleton.
1664 * @return <code>true</code> if c only contains either no elements or
1665 * elements equal to the element in this singleton.
1666 */
1667 public boolean containsAll(Collection<?> c)
1668 {
1669 Iterator<?> i = c.iterator();
1670 int pos = c.size();
1671 while (--pos >= 0)
1672 if (! equals(i.next(), element))
1673 return false;
1674 return true;
1675 }
1676
1677 /**
1678 * The hash is just that of the element.
1679 *
1680 * @return The hashcode of the element.
1681 */
1682 public int hashCode()
1683 {
1684 return hashCode(element);
1685 }
1686
1687 /**
1688 * Returning an array is simple.
1689 *
1690 * @return An array containing the element.
1691 */
1692 public Object[] toArray()
1693 {
1694 return new Object[] {element};
1695 }
1696
1697 /**
1698 * Obvious string.
1699 *
1700 * @return The string surrounded by enclosing
1701 * square brackets.
1702 */
1703 public String toString()
1704 {
1705 return "[" + element + "]";
1706 }
1707 } // class SingletonSet
1708
1709 /**
1710 * Obtain an immutable List consisting of a single element. The return value
1711 * of this method is Serializable, and implements RandomAccess.
1712 *
1713 * @param o the single element
1714 * @return an immutable List containing only o
1715 * @see Serializable
1716 * @see RandomAccess
1717 * @since 1.3
1718 */
1719 public static <T> List<T> singletonList(T o)
1720 {
1721 return new SingletonList<T>(o);
1722 }
1723
1724 /**
1725 * The implementation of {@link #singletonList(Object)}. This class name
1726 * is required for compatibility with Sun's JDK serializability.
1727 *
1728 * @author Eric Blake (ebb9@email.byu.edu)
1729 */
1730 private static final class SingletonList<T> extends AbstractList<T>
1731 implements Serializable, RandomAccess
1732 {
1733 /**
1734 * Compatible with JDK 1.4.
1735 */
1736 private static final long serialVersionUID = 3093736618740652951L;
1737
1738 /**
1739 * The single element.
1740 * @serial the singleton
1741 */
1742 private final T element;
1743
1744 /**
1745 * Construct a singleton.
1746 * @param o the element
1747 */
1748 SingletonList(T o)
1749 {
1750 element = o;
1751 }
1752
1753 /**
1754 * The size: always 1!
1755 * @return 1.
1756 */
1757 public int size()
1758 {
1759 return 1;
1760 }
1761
1762 /**
1763 * Only index 0 is valid.
1764 * @param index The index of the element
1765 * to retrieve.
1766 * @return The singleton's element if the
1767 * index is 0.
1768 * @throws IndexOutOfBoundsException if
1769 * index is not 0.
1770 */
1771 public T get(int index)
1772 {
1773 if (index == 0)
1774 return element;
1775 throw new IndexOutOfBoundsException();
1776 }
1777
1778 // The remaining methods are optional, but provide a performance
1779 // advantage by not allocating unnecessary iterators in AbstractList.
1780 /**
1781 * The set only contains one element.
1782 *
1783 * @param o The object to search for.
1784 * @return <code>true</code> if o == the singleton element.
1785 */
1786 public boolean contains(Object o)
1787 {
1788 return equals(o, element);
1789 }
1790
1791 /**
1792 * This is true if the other collection only contains the element.
1793 *
1794 * @param c A collection to compare against this singleton.
1795 * @return <code>true</code> if c only contains either no elements or
1796 * elements equal to the element in this singleton.
1797 */
1798 public boolean containsAll(Collection<?> c)
1799 {
1800 Iterator<?> i = c.iterator();
1801 int pos = c.size();
1802 while (--pos >= 0)
1803 if (! equals(i.next(), element))
1804 return false;
1805 return true;
1806 }
1807
1808 /**
1809 * Speed up the hashcode computation.
1810 *
1811 * @return The hashcode of the list, based
1812 * on the hashcode of the singleton element.
1813 */
1814 public int hashCode()
1815 {
1816 return 31 + hashCode(element);
1817 }
1818
1819 /**
1820 * Either the list has it or not.
1821 *
1822 * @param o The object to find the first index of.
1823 * @return 0 if o is the singleton element, -1 if not.
1824 */
1825 public int indexOf(Object o)
1826 {
1827 return equals(o, element) ? 0 : -1;
1828 }
1829
1830 /**
1831 * Either the list has it or not.
1832 *
1833 * @param o The object to find the last index of.
1834 * @return 0 if o is the singleton element, -1 if not.
1835 */
1836 public int lastIndexOf(Object o)
1837 {
1838 return equals(o, element) ? 0 : -1;
1839 }
1840
1841 /**
1842 * Sublists are limited in scope.
1843 *
1844 * @param from The starting bound for the sublist.
1845 * @param to The ending bound for the sublist.
1846 * @return Either an empty list if both bounds are
1847 * 0 or 1, or this list if the bounds are 0 and 1.
1848 * @throws IllegalArgumentException if <code>from > to</code>
1849 * @throws IndexOutOfBoundsException if either bound is greater
1850 * than 1.
1851 */
1852 public List<T> subList(int from, int to)
1853 {
1854 if (from == to && (to == 0 || to == 1))
1855 return EMPTY_LIST;
1856 if (from == 0 && to == 1)
1857 return this;
1858 if (from > to)
1859 throw new IllegalArgumentException();
1860 throw new IndexOutOfBoundsException();
1861 }
1862
1863 /**
1864 * Returning an array is simple.
1865 *
1866 * @return An array containing the element.
1867 */
1868 public Object[] toArray()
1869 {
1870 return new Object[] {element};
1871 }
1872
1873 /**
1874 * Obvious string.
1875 *
1876 * @return The string surrounded by enclosing
1877 * square brackets.
1878 */
1879 public String toString()
1880 {
1881 return "[" + element + "]";
1882 }
1883 } // class SingletonList
1884
1885 /**
1886 * Obtain an immutable Map consisting of a single key-value pair.
1887 * The return value of this method is Serializable.
1888 *
1889 * @param key the single key
1890 * @param value the single value
1891 * @return an immutable Map containing only the single key-value pair
1892 * @see Serializable
1893 * @since 1.3
1894 */
1895 public static <K, V> Map<K, V> singletonMap(K key, V value)
1896 {
1897 return new SingletonMap<K, V>(key, value);
1898 }
1899
1900 /**
1901 * The implementation of {@link #singletonMap(Object, Object)}. This class
1902 * name is required for compatibility with Sun's JDK serializability.
1903 *
1904 * @author Eric Blake (ebb9@email.byu.edu)
1905 */
1906 private static final class SingletonMap<K, V> extends AbstractMap<K, V>
1907 implements Serializable
1908 {
1909 /**
1910 * Compatible with JDK 1.4.
1911 */
1912 private static final long serialVersionUID = -6979724477215052911L;
1913
1914 /**
1915 * The single key.
1916 * @serial the singleton key
1917 */
1918 private final K k;
1919
1920 /**
1921 * The corresponding value.
1922 * @serial the singleton value
1923 */
1924 private final V v;
1925
1926 /**
1927 * Cache the entry set.
1928 */
1929 private transient Set<Map.Entry<K, V>> entries;
1930
1931 /**
1932 * Construct a singleton.
1933 * @param key the key
1934 * @param value the value
1935 */
1936 SingletonMap(K key, V value)
1937 {
1938 k = key;
1939 v = value;
1940 }
1941
1942 /**
1943 * There is a single immutable entry.
1944 *
1945 * @return A singleton containing the map entry.
1946 */
1947 public Set<Map.Entry<K, V>> entrySet()
1948 {
1949 if (entries == null)
1950 {
1951 Map.Entry<K,V> entry = new AbstractMap.SimpleEntry<K, V>(k, v)
1952 {
1953 /**
1954 * Sets the value of the map entry to the supplied value.
1955 * An exception is always thrown, as the map is immutable.
1956 *
1957 * @param o The new value.
1958 * @return The old value.
1959 * @throws UnsupportedOperationException as setting the value
1960 * is not supported.
1961 */
1962 public V setValue(V o)
1963 {
1964 throw new UnsupportedOperationException();
1965 }
1966 };
1967 entries = singleton(entry);
1968 }
1969 return entries;
1970 }
1971
1972 // The remaining methods are optional, but provide a performance
1973 // advantage by not allocating unnecessary iterators in AbstractMap.
1974 /**
1975 * Single entry.
1976 *
1977 * @param key The key to look for.
1978 * @return <code>true</code> if the key is the same as the one used by
1979 * this map.
1980 */
1981 public boolean containsKey(Object key)
1982 {
1983 return equals(key, k);
1984 }
1985
1986 /**
1987 * Single entry.
1988 *
1989 * @param value The value to look for.
1990 * @return <code>true</code> if the value is the same as the one used by
1991 * this map.
1992 */
1993 public boolean containsValue(Object value)
1994 {
1995 return equals(value, v);
1996 }
1997
1998 /**
1999 * Single entry.
2000 *
2001 * @param key The key of the value to be retrieved.
2002 * @return The singleton value if the key is the same as the
2003 * singleton key, null otherwise.
2004 */
2005 public V get(Object key)
2006 {
2007 return equals(key, k) ? v : null;
2008 }
2009
2010 /**
2011 * Calculate the hashcode directly.
2012 *
2013 * @return The hashcode computed from the singleton key
2014 * and the singleton value.
2015 */
2016 public int hashCode()
2017 {
2018 return hashCode(k) ^ hashCode(v);
2019 }
2020
2021 /**
2022 * Return the keyset.
2023 *
2024 * @return A singleton containing the key.
2025 */
2026 public Set<K> keySet()
2027 {
2028 if (keys == null)
2029 keys = singleton(k);
2030 return keys;
2031 }
2032
2033 /**
2034 * The size: always 1!
2035 *
2036 * @return 1.
2037 */
2038 public int size()
2039 {
2040 return 1;
2041 }
2042
2043 /**
2044 * Return the values. Technically, a singleton, while more specific than
2045 * a general Collection, will work. Besides, that's what the JDK uses!
2046 *
2047 * @return A singleton containing the value.
2048 */
2049 public Collection<V> values()
2050 {
2051 if (values == null)
2052 values = singleton(v);
2053 return values;
2054 }
2055
2056 /**
2057 * Obvious string.
2058 *
2059 * @return A string containing the string representations of the key
2060 * and its associated value.
2061 */
2062 public String toString()
2063 {
2064 return "{" + k + "=" + v + "}";
2065 }
2066 } // class SingletonMap
2067
2068 /**
2069 * Sort a list according to the natural ordering of its elements. The list
2070 * must be modifiable, but can be of fixed size. The sort algorithm is
2071 * precisely that used by Arrays.sort(Object[]), which offers guaranteed
2072 * nlog(n) performance. This implementation dumps the list into an array,
2073 * sorts the array, and then iterates over the list setting each element from
2074 * the array.
2075 *
2076 * @param l the List to sort (<code>null</code> not permitted)
2077 * @throws ClassCastException if some items are not mutually comparable
2078 * @throws UnsupportedOperationException if the List is not modifiable
2079 * @throws NullPointerException if the list is <code>null</code>, or contains
2080 * some element that is <code>null</code>.
2081 * @see Arrays#sort(Object[])
2082 */
2083 public static <T extends Comparable<? super T>> void sort(List<T> l)
2084 {
2085 sort(l, null);
2086 }
2087
2088 /**
2089 * Sort a list according to a specified Comparator. The list must be
2090 * modifiable, but can be of fixed size. The sort algorithm is precisely that
2091 * used by Arrays.sort(Object[], Comparator), which offers guaranteed
2092 * nlog(n) performance. This implementation dumps the list into an array,
2093 * sorts the array, and then iterates over the list setting each element from
2094 * the array.
2095 *
2096 * @param l the List to sort (<code>null</code> not permitted)
2097 * @param c the Comparator specifying the ordering for the elements, or
2098 * <code>null</code> for natural ordering
2099 * @throws ClassCastException if c will not compare some pair of items
2100 * @throws UnsupportedOperationException if the List is not modifiable
2101 * @throws NullPointerException if the List is <code>null</code> or
2102 * <code>null</code> is compared by natural ordering (only possible
2103 * when c is <code>null</code>)
2104 *
2105 * @see Arrays#sort(Object[], Comparator)
2106 */
2107 public static <T> void sort(List<T> l, Comparator<? super T> c)
2108 {
2109 T[] a = (T[]) l.toArray();
2110 Arrays.sort(a, c);
2111 ListIterator<T> i = l.listIterator();
2112 for (int pos = 0, alen = a.length; pos < alen; pos++)
2113 {
2114 i.next();
2115 i.set(a[pos]);
2116 }
2117 }
2118
2119 /**
2120 * Swaps the elements at the specified positions within the list. Equal
2121 * positions have no effect.
2122 *
2123 * @param l the list to work on
2124 * @param i the first index to swap
2125 * @param j the second index
2126 * @throws UnsupportedOperationException if list.set is not supported
2127 * @throws IndexOutOfBoundsException if either i or j is < 0 or >=
2128 * list.size()
2129 * @since 1.4
2130 */
2131 public static void swap(List<?> l, int i, int j)
2132 {
2133 List<Object> list = (List<Object>) l;
2134 list.set(i, list.set(j, list.get(i)));
2135 }
2136
2137
2138 /**
2139 * Returns a synchronized (thread-safe) collection wrapper backed by the
2140 * given collection. Notice that element access through the iterators
2141 * is thread-safe, but if the collection can be structurally modified
2142 * (adding or removing elements) then you should synchronize around the
2143 * iteration to avoid non-deterministic behavior:<br>
2144 * <pre>
2145 * Collection c = Collections.synchronizedCollection(new Collection(...));
2146 * ...
2147 * synchronized (c)
2148 * {
2149 * Iterator i = c.iterator();
2150 * while (i.hasNext())
2151 * foo(i.next());
2152 * }
2153 * </pre><p>
2154 *
2155 * Since the collection might be a List or a Set, and those have incompatible
2156 * equals and hashCode requirements, this relies on Object's implementation
2157 * rather than passing those calls on to the wrapped collection. The returned
2158 * Collection implements Serializable, but can only be serialized if
2159 * the collection it wraps is likewise Serializable.
2160 *
2161 * @param c the collection to wrap
2162 * @return a synchronized view of the collection
2163 * @see Serializable
2164 */
2165 public static <T> Collection<T> synchronizedCollection(Collection<T> c)
2166 {
2167 return new SynchronizedCollection<T>(c);
2168 }
2169
2170 /**
2171 * The implementation of {@link #synchronizedCollection(Collection)}. This
2172 * class name is required for compatibility with Sun's JDK serializability.
2173 * Package visible, so that collections such as the one for
2174 * Hashtable.values() can specify which object to synchronize on.
2175 *
2176 * @author Eric Blake (ebb9@email.byu.edu)
2177 */
2178 static class SynchronizedCollection<T>
2179 implements Collection<T>, Serializable
2180 {
2181 /**
2182 * Compatible with JDK 1.4.
2183 */
2184 private static final long serialVersionUID = 3053995032091335093L;
2185
2186 /**
2187 * The wrapped collection. Package visible for use by subclasses.
2188 * @serial the real collection
2189 */
2190 final Collection<T> c;
2191
2192 /**
2193 * The object to synchronize on. When an instance is created via public
2194 * methods, it will be this; but other uses like SynchronizedMap.values()
2195 * must specify another mutex. Package visible for use by subclasses.
2196 * @serial the lock
2197 */
2198 final Object mutex;
2199
2200 /**
2201 * Wrap a given collection.
2202 * @param c the collection to wrap
2203 * @throws NullPointerException if c is null
2204 */
2205 SynchronizedCollection(Collection<T> c)
2206 {
2207 this.c = c;
2208 mutex = this;
2209 if (c == null)
2210 throw new NullPointerException();
2211 }
2212
2213 /**
2214 * Called only by trusted code to specify the mutex as well as the
2215 * collection.
2216 * @param sync the mutex
2217 * @param c the collection
2218 */
2219 SynchronizedCollection(Object sync, Collection<T> c)
2220 {
2221 this.c = c;
2222 mutex = sync;
2223 }
2224
2225 /**
2226 * Adds the object to the underlying collection, first
2227 * obtaining a lock on the mutex.
2228 *
2229 * @param o The object to add.
2230 * @return <code>true</code> if the collection was modified as a result
2231 * of this action.
2232 * @throws UnsupportedOperationException if this collection does not
2233 * support the add operation.
2234 * @throws ClassCastException if o cannot be added to this collection due
2235 * to its type.
2236 * @throws NullPointerException if o is null and this collection doesn't
2237 * support the addition of null values.
2238 * @throws IllegalArgumentException if o cannot be added to this
2239 * collection for some other reason.
2240 */
2241 public boolean add(T o)
2242 {
2243 synchronized (mutex)
2244 {
2245 return c.add(o);
2246 }
2247 }
2248
2249 /**
2250 * Adds the objects in col to the underlying collection, first
2251 * obtaining a lock on the mutex.
2252 *
2253 * @param col The collection to take the new objects from.
2254 * @return <code>true</code> if the collection was modified as a result
2255 * of this action.
2256 * @throws UnsupportedOperationException if this collection does not
2257 * support the addAll operation.
2258 * @throws ClassCastException if some element of col cannot be added to this
2259 * collection due to its type.
2260 * @throws NullPointerException if some element of col is null and this
2261 * collection does not support the addition of null values.
2262 * @throws NullPointerException if col itself is null.
2263 * @throws IllegalArgumentException if some element of col cannot be added
2264 * to this collection for some other reason.
2265 */
2266 public boolean addAll(Collection<? extends T> col)
2267 {
2268 synchronized (mutex)
2269 {
2270 return c.addAll(col);
2271 }
2272 }
2273
2274 /**
2275 * Removes all objects from the underlying collection,
2276 * first obtaining a lock on the mutex.
2277 *
2278 * @throws UnsupportedOperationException if this collection does not
2279 * support the clear operation.
2280 */
2281 public void clear()
2282 {
2283 synchronized (mutex)
2284 {
2285 c.clear();
2286 }
2287 }
2288
2289 /**
2290 * Checks for the existence of o within the underlying
2291 * collection, first obtaining a lock on the mutex.
2292 *
2293 * @param o the element to look for.
2294 * @return <code>true</code> if this collection contains at least one
2295 * element e such that <code>o == null ? e == null : o.equals(e)</code>.
2296 * @throws ClassCastException if the type of o is not a valid type for this
2297 * collection.
2298 * @throws NullPointerException if o is null and this collection doesn't
2299 * support null values.
2300 */
2301 public boolean contains(Object o)
2302 {
2303 synchronized (mutex)
2304 {
2305 return c.contains(o);
2306 }
2307 }
2308
2309 /**
2310 * Checks for the existence of each object in cl
2311 * within the underlying collection, first obtaining
2312 * a lock on the mutex.
2313 *
2314 * @param c1 the collection to test for.
2315 * @return <code>true</code> if for every element o in c, contains(o)
2316 * would return <code>true</code>.
2317 * @throws ClassCastException if the type of any element in cl is not a valid
2318 * type for this collection.
2319 * @throws NullPointerException if some element of cl is null and this
2320 * collection does not support null values.
2321 * @throws NullPointerException if cl itself is null.
2322 */
2323 public boolean containsAll(Collection<?> c1)
2324 {
2325 synchronized (mutex)
2326 {
2327 return c.containsAll(c1);
2328 }
2329 }
2330
2331 /**
2332 * Returns <code>true</code> if there are no objects in the underlying
2333 * collection. A lock on the mutex is obtained before the
2334 * check is performed.
2335 *
2336 * @return <code>true</code> if this collection contains no elements.
2337 */
2338 public boolean isEmpty()
2339 {
2340 synchronized (mutex)
2341 {
2342 return c.isEmpty();
2343 }
2344 }
2345
2346 /**
2347 * Returns a synchronized iterator wrapper around the underlying
2348 * collection's iterator. A lock on the mutex is obtained before
2349 * retrieving the collection's iterator.
2350 *
2351 * @return An iterator over the elements in the underlying collection,
2352 * which returns each element in any order.
2353 */
2354 public Iterator<T> iterator()
2355 {
2356 synchronized (mutex)
2357 {
2358 return new SynchronizedIterator<T>(mutex, c.iterator());
2359 }
2360 }
2361
2362 /**
2363 * Removes the specified object from the underlying collection,
2364 * first obtaining a lock on the mutex.
2365 *
2366 * @param o The object to remove.
2367 * @return <code>true</code> if the collection changed as a result of this call, that is,
2368 * if the collection contained at least one occurrence of o.
2369 * @throws UnsupportedOperationException if this collection does not
2370 * support the remove operation.
2371 * @throws ClassCastException if the type of o is not a valid type
2372 * for this collection.
2373 * @throws NullPointerException if o is null and the collection doesn't
2374 * support null values.
2375 */
2376 public boolean remove(Object o)
2377 {
2378 synchronized (mutex)
2379 {
2380 return c.remove(o);
2381 }
2382 }
2383
2384 /**
2385 * Removes all elements, e, of the underlying
2386 * collection for which <code>col.contains(e)</code>
2387 * returns <code>true</code>. A lock on the mutex is obtained
2388 * before the operation proceeds.
2389 *
2390 * @param col The collection of objects to be removed.
2391 * @return <code>true</code> if this collection was modified as a result of this call.
2392 * @throws UnsupportedOperationException if this collection does not
2393 * support the removeAll operation.
2394 * @throws ClassCastException if the type of any element in c is not a valid
2395 * type for this collection.
2396 * @throws NullPointerException if some element of c is null and this
2397 * collection does not support removing null values.
2398 * @throws NullPointerException if c itself is null.
2399 */
2400 public boolean removeAll(Collection<?> col)
2401 {
2402 synchronized (mutex)
2403 {
2404 return c.removeAll(col);
2405 }
2406 }
2407
2408 /**
2409 * Retains all elements, e, of the underlying
2410 * collection for which <code>col.contains(e)</code>
2411 * returns <code>true</code>. That is, every element that doesn't
2412 * exist in col is removed. A lock on the mutex is obtained
2413 * before the operation proceeds.
2414 *
2415 * @param col The collection of objects to be removed.
2416 * @return <code>true</code> if this collection was modified as a result of this call.
2417 * @throws UnsupportedOperationException if this collection does not
2418 * support the removeAll operation.
2419 * @throws ClassCastException if the type of any element in c is not a valid
2420 * type for this collection.
2421 * @throws NullPointerException if some element of c is null and this
2422 * collection does not support removing null values.
2423 * @throws NullPointerException if c itself is null.
2424 */
2425 public boolean retainAll(Collection<?> col)
2426 {
2427 synchronized (mutex)
2428 {
2429 return c.retainAll(col);
2430 }
2431 }
2432
2433 /**
2434 * Retrieves the size of the underlying collection.
2435 * A lock on the mutex is obtained before the collection
2436 * is accessed.
2437 *
2438 * @return The size of the collection.
2439 */
2440 public int size()
2441 {
2442 synchronized (mutex)
2443 {
2444 return c.size();
2445 }
2446 }
2447
2448 /**
2449 * Returns an array containing each object within the underlying
2450 * collection. A lock is obtained on the mutex before the collection
2451 * is accessed.
2452 *
2453 * @return An array of objects, matching the collection in size. The
2454 * elements occur in any order.
2455 */
2456 public Object[] toArray()
2457 {
2458 synchronized (mutex)
2459 {
2460 return c.toArray();
2461 }
2462 }
2463
2464 /**
2465 * Copies the elements in the underlying collection to the supplied
2466 * array. If <code>a.length < size()</code>, a new array of the
2467 * same run-time type is created, with a size equal to that of
2468 * the collection. If <code>a.length > size()</code>, then the
2469 * elements from 0 to <code>size() - 1</code> contain the elements
2470 * from this collection. The following element is set to null
2471 * to indicate the end of the collection objects. However, this
2472 * only makes a difference if null is not a permitted value within
2473 * the collection.
2474 * Before the copying takes place, a lock is obtained on the mutex.
2475 *
2476 * @param a An array to copy elements to.
2477 * @return An array containing the elements of the underlying collection.
2478 * @throws ArrayStoreException if the type of any element of the
2479 * collection is not a subtype of the element type of a.
2480 */
2481 public <T> T[] toArray(T[] a)
2482 {
2483 synchronized (mutex)
2484 {
2485 return c.toArray(a);
2486 }
2487 }
2488
2489 /**
2490 * Returns a string representation of the underlying collection.
2491 * A lock is obtained on the mutex before the string is created.
2492 *
2493 * @return A string representation of the collection.
2494 */
2495 public String toString()
2496 {
2497 synchronized (mutex)
2498 {
2499 return c.toString();
2500 }
2501 }
2502 } // class SynchronizedCollection
2503
2504 /**
2505 * The implementation of the various iterator methods in the
2506 * synchronized classes. These iterators must "sync" on the same object
2507 * as the collection they iterate over.
2508 *
2509 * @author Eric Blake (ebb9@email.byu.edu)
2510 */
2511 private static class SynchronizedIterator<T> implements Iterator<T>
2512 {
2513 /**
2514 * The object to synchronize on. Package visible for use by subclass.
2515 */
2516 final Object mutex;
2517
2518 /**
2519 * The wrapped iterator.
2520 */
2521 private final Iterator<T> i;
2522
2523 /**
2524 * Only trusted code creates a wrapper, with the specified sync.
2525 * @param sync the mutex
2526 * @param i the wrapped iterator
2527 */
2528 SynchronizedIterator(Object sync, Iterator<T> i)
2529 {
2530 this.i = i;
2531 mutex = sync;
2532 }
2533
2534 /**
2535 * Retrieves the next object in the underlying collection.
2536 * A lock is obtained on the mutex before the collection is accessed.
2537 *
2538 * @return The next object in the collection.
2539 * @throws NoSuchElementException if there are no more elements
2540 */
2541 public T next()
2542 {
2543 synchronized (mutex)
2544 {
2545 return i.next();
2546 }
2547 }
2548
2549 /**
2550 * Returns <code>true</code> if objects can still be retrieved from the iterator
2551 * using <code>next()</code>. A lock is obtained on the mutex before
2552 * the collection is accessed.
2553 *
2554 * @return <code>true</code> if at least one element is still to be returned by
2555 * <code>next()</code>.
2556 */
2557 public boolean hasNext()
2558 {
2559 synchronized (mutex)
2560 {
2561 return i.hasNext();
2562 }
2563 }
2564
2565 /**
2566 * Removes the object that was last returned by <code>next()</code>
2567 * from the underlying collection. Only one call to this method is
2568 * allowed per call to the <code>next()</code> method, and it does
2569 * not affect the value that will be returned by <code>next()</code>.
2570 * Thus, if element n was retrieved from the collection by
2571 * <code>next()</code>, it is this element that gets removed.
2572 * Regardless of whether this takes place or not, element n+1 is
2573 * still returned on the subsequent <code>next()</code> call.
2574 *
2575 * @throws IllegalStateException if next has not yet been called or remove
2576 * has already been called since the last call to next.
2577 * @throws UnsupportedOperationException if this Iterator does not support
2578 * the remove operation.
2579 */
2580 public void remove()
2581 {
2582 synchronized (mutex)
2583 {
2584 i.remove();
2585 }
2586 }
2587 } // class SynchronizedIterator
2588
2589 /**
2590 * Returns a synchronized (thread-safe) list wrapper backed by the
2591 * given list. Notice that element access through the iterators
2592 * is thread-safe, but if the list can be structurally modified
2593 * (adding or removing elements) then you should synchronize around the
2594 * iteration to avoid non-deterministic behavior:<br>
2595 * <pre>
2596 * List l = Collections.synchronizedList(new List(...));
2597 * ...
2598 * synchronized (l)
2599 * {
2600 * Iterator i = l.iterator();
2601 * while (i.hasNext())
2602 * foo(i.next());
2603 * }
2604 * </pre><p>
2605 *
2606 * The returned List implements Serializable, but can only be serialized if
2607 * the list it wraps is likewise Serializable. In addition, if the wrapped
2608 * list implements RandomAccess, this does too.
2609 *
2610 * @param l the list to wrap
2611 * @return a synchronized view of the list
2612 * @see Serializable
2613 * @see RandomAccess
2614 */
2615 public static <T> List<T> synchronizedList(List<T> l)
2616 {
2617 if (l instanceof RandomAccess)
2618 return new SynchronizedRandomAccessList<T>(l);
2619 return new SynchronizedList<T>(l);
2620 }
2621
2622 /**
2623 * The implementation of {@link #synchronizedList(List)} for sequential
2624 * lists. This class name is required for compatibility with Sun's JDK
2625 * serializability. Package visible, so that lists such as Vector.subList()
2626 * can specify which object to synchronize on.
2627 *
2628 * @author Eric Blake (ebb9@email.byu.edu)
2629 */
2630 static class SynchronizedList<T> extends SynchronizedCollection<T>
2631 implements List<T>
2632 {
2633 /**
2634 * Compatible with JDK 1.4.
2635 */
2636 private static final long serialVersionUID = -7754090372962971524L;
2637
2638 /**
2639 * The wrapped list; stored both here and in the superclass to avoid
2640 * excessive casting. Package visible for use by subclass.
2641 * @serial the wrapped list
2642 */
2643 final List<T> list;
2644
2645 /**
2646 * Wrap a given list.
2647 * @param l the list to wrap
2648 * @throws NullPointerException if l is null
2649 */
2650 SynchronizedList(List<T> l)
2651 {
2652 super(l);
2653 list = l;
2654 }
2655
2656 /**
2657 * Called only by trusted code to specify the mutex as well as the list.
2658 * @param sync the mutex
2659 * @param l the list
2660 */
2661 SynchronizedList(Object sync, List<T> l)
2662 {
2663 super(sync, l);
2664 list = l;
2665 }
2666
2667 /**
2668 * Insert an element into the underlying list at a given position (optional
2669 * operation). This shifts all existing elements from that position to the
2670 * end one index to the right. This version of add has no return, since it is
2671 * assumed to always succeed if there is no exception. Before the
2672 * addition takes place, a lock is obtained on the mutex.
2673 *
2674 * @param index the location to insert the item
2675 * @param o the object to insert
2676 * @throws UnsupportedOperationException if this list does not support the
2677 * add operation
2678 * @throws IndexOutOfBoundsException if index < 0 || index > size()
2679 * @throws ClassCastException if o cannot be added to this list due to its
2680 * type
2681 * @throws IllegalArgumentException if o cannot be added to this list for
2682 * some other reason
2683 * @throws NullPointerException if o is null and this list doesn't support
2684 * the addition of null values.
2685 */
2686 public void add(int index, T o)
2687 {
2688 synchronized (mutex)
2689 {
2690 list.add(index, o);
2691 }
2692 }
2693
2694 /**
2695 * Add the contents of a collection to the underlying list at the given
2696 * index (optional operation). If the list imposes restraints on what
2697 * can be inserted, such as no null elements, this should be documented.
2698 * A lock is obtained on the mutex before any of the elements are added.
2699 *
2700 * @param index the index at which to insert
2701 * @param c the collection to add
2702 * @return <code>true</code>, as defined by Collection for a modified list
2703 * @throws UnsupportedOperationException if this list does not support the
2704 * add operation
2705 * @throws ClassCastException if o cannot be added to this list due to its
2706 * type
2707 * @throws IllegalArgumentException if o cannot be added to this list for
2708 * some other reason
2709 * @throws NullPointerException if o is null and this list doesn't support
2710 * the addition of null values.
2711 */
2712 public boolean addAll(int index, Collection<? extends T> c)
2713 {
2714 synchronized (mutex)
2715 {
2716 return list.addAll(index, c);
2717 }
2718 }
2719
2720 /**
2721 * Tests whether the underlying list is equal to the supplied object.
2722 * The object is deemed to be equal if it is also a <code>List</code>
2723 * of equal size and with the same elements (i.e. each element, e1,
2724 * in list, l1, and each element, e2, in l2, must return <code>true</code> for
2725 * <code>e1 == null ? e2 == null : e1.equals(e2)</code>. Before the
2726 * comparison is made, a lock is obtained on the mutex.
2727 *
2728 * @param o The object to test for equality with the underlying list.
2729 * @return <code>true</code> if o is equal to the underlying list under the above
2730 * definition.
2731 */
2732 public boolean equals(Object o)
2733 {
2734 synchronized (mutex)
2735 {
2736 return list.equals(o);
2737 }
2738 }
2739
2740 /**
2741 * Retrieves the object at the specified index. A lock
2742 * is obtained on the mutex before the list is accessed.
2743 *
2744 * @param index the index of the element to be returned
2745 * @return the element at index index in this list
2746 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
2747 */
2748 public T get(int index)
2749 {
2750 synchronized (mutex)
2751 {
2752 return list.get(index);
2753 }
2754 }
2755
2756 /**
2757 * Obtains a hashcode for the underlying list, first obtaining
2758 * a lock on the mutex. The calculation of the hashcode is
2759 * detailed in the documentation for the <code>List</code>
2760 * interface.
2761 *
2762 * @return The hashcode of the underlying list.
2763 * @see List#hashCode()
2764 */
2765 public int hashCode()
2766 {
2767 synchronized (mutex)
2768 {
2769 return list.hashCode();
2770 }
2771 }
2772
2773 /**
2774 * Obtain the first index at which a given object is to be found in the
2775 * underlying list. A lock is obtained on the mutex before the list is
2776 * accessed.
2777 *
2778 * @param o the object to search for
2779 * @return the least integer n such that <code>o == null ? get(n) == null :
2780 * o.equals(get(n))</code>, or -1 if there is no such index.
2781 * @throws ClassCastException if the type of o is not a valid
2782 * type for this list.
2783 * @throws NullPointerException if o is null and this
2784 * list does not support null values.
2785 */
2786
2787 public int indexOf(Object o)
2788 {
2789 synchronized (mutex)
2790 {
2791 return list.indexOf(o);
2792 }
2793 }
2794
2795 /**
2796 * Obtain the last index at which a given object is to be found in this
2797 * underlying list. A lock is obtained on the mutex before the list
2798 * is accessed.
2799 *
2800 * @return the greatest integer n such that <code>o == null ? get(n) == null
2801 * : o.equals(get(n))</code>, or -1 if there is no such index.
2802 * @throws ClassCastException if the type of o is not a valid
2803 * type for this list.
2804 * @throws NullPointerException if o is null and this
2805 * list does not support null values.
2806 */
2807 public int lastIndexOf(Object o)
2808 {
2809 synchronized (mutex)
2810 {
2811 return list.lastIndexOf(o);
2812 }
2813 }
2814
2815 /**
2816 * Retrieves a synchronized wrapper around the underlying list's
2817 * list iterator. A lock is obtained on the mutex before the
2818 * list iterator is retrieved.
2819 *
2820 * @return A list iterator over the elements in the underlying list.
2821 * The list iterator allows additional list-specific operations
2822 * to be performed, in addition to those supplied by the
2823 * standard iterator.
2824 */
2825 public ListIterator<T> listIterator()
2826 {
2827 synchronized (mutex)
2828 {
2829 return new SynchronizedListIterator<T>(mutex, list.listIterator());
2830 }
2831 }
2832
2833 /**
2834 * Retrieves a synchronized wrapper around the underlying list's
2835 * list iterator. A lock is obtained on the mutex before the
2836 * list iterator is retrieved. The iterator starts at the
2837 * index supplied, leading to the element at that index being
2838 * the first one returned by <code>next()</code>. Calling
2839 * <code>previous()</code> from this initial position returns
2840 * index - 1.
2841 *
2842 * @param index the position, between 0 and size() inclusive, to begin the
2843 * iteration from
2844 * @return A list iterator over the elements in the underlying list.
2845 * The list iterator allows additional list-specific operations
2846 * to be performed, in addition to those supplied by the
2847 * standard iterator.
2848 * @throws IndexOutOfBoundsException if index < 0 || index > size()
2849 */
2850 public ListIterator<T> listIterator(int index)
2851 {
2852 synchronized (mutex)
2853 {
2854 return new SynchronizedListIterator<T>(mutex,
2855 list.listIterator(index));
2856 }
2857 }
2858
2859 /**
2860 * Remove the element at a given position in the underlying list (optional
2861 * operation). All remaining elements are shifted to the left to fill the gap.
2862 * A lock on the mutex is obtained before the element is removed.
2863 *
2864 * @param index the position within the list of the object to remove
2865 * @return the object that was removed
2866 * @throws UnsupportedOperationException if this list does not support the
2867 * remove operation
2868 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
2869 */
2870 public T remove(int index)
2871 {
2872 synchronized (mutex)
2873 {
2874 return list.remove(index);
2875 }
2876 }
2877
2878 /**
2879 * Replace an element of the underlying list with another object (optional
2880 * operation). A lock is obtained on the mutex before the element is
2881 * replaced.
2882 *
2883 * @param index the position within this list of the element to be replaced
2884 * @param o the object to replace it with
2885 * @return the object that was replaced
2886 * @throws UnsupportedOperationException if this list does not support the
2887 * set operation.
2888 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
2889 * @throws ClassCastException if o cannot be added to this list due to its
2890 * type
2891 * @throws IllegalArgumentException if o cannot be added to this list for
2892 * some other reason
2893 * @throws NullPointerException if o is null and this
2894 * list does not support null values.
2895 */
2896 public T set(int index, T o)
2897 {
2898 synchronized (mutex)
2899 {
2900 return list.set(index, o);
2901 }
2902 }
2903
2904 /**
2905 * Obtain a List view of a subsection of the underlying list, from fromIndex
2906 * (inclusive) to toIndex (exclusive). If the two indices are equal, the
2907 * sublist is empty. The returned list should be modifiable if and only
2908 * if this list is modifiable. Changes to the returned list should be
2909 * reflected in this list. If this list is structurally modified in
2910 * any way other than through the returned list, the result of any subsequent
2911 * operations on the returned list is undefined. A lock is obtained
2912 * on the mutex before the creation of the sublist. The returned list
2913 * is also synchronized, using the same mutex.
2914 *
2915 * @param fromIndex the index that the returned list should start from
2916 * (inclusive)
2917 * @param toIndex the index that the returned list should go to (exclusive)
2918 * @return a List backed by a subsection of this list
2919 * @throws IndexOutOfBoundsException if fromIndex < 0
2920 * || toIndex > size() || fromIndex > toIndex
2921 */
2922 public List<T> subList(int fromIndex, int toIndex)
2923 {
2924 synchronized (mutex)
2925 {
2926 return new SynchronizedList<T>(mutex,
2927 list.subList(fromIndex, toIndex));
2928 }
2929 }
2930 } // class SynchronizedList
2931
2932 /**
2933 * The implementation of {@link #synchronizedList(List)} for random-access
2934 * lists. This class name is required for compatibility with Sun's JDK
2935 * serializability.
2936 *
2937 * @author Eric Blake (ebb9@email.byu.edu)
2938 */
2939 private static final class SynchronizedRandomAccessList<T>
2940 extends SynchronizedList<T> implements RandomAccess
2941 {
2942 /**
2943 * Compatible with JDK 1.4.
2944 */
2945 private static final long serialVersionUID = 1530674583602358482L;
2946
2947 /**
2948 * Wrap a given list.
2949 * @param l the list to wrap
2950 * @throws NullPointerException if l is null
2951 */
2952 SynchronizedRandomAccessList(List<T> l)
2953 {
2954 super(l);
2955 }
2956
2957 /**
2958 * Called only by trusted code to specify the mutex as well as the
2959 * collection.
2960 * @param sync the mutex
2961 * @param l the list
2962 */
2963 SynchronizedRandomAccessList(Object sync, List<T> l)
2964 {
2965 super(sync, l);
2966 }
2967
2968 /**
2969 * Obtain a List view of a subsection of the underlying list, from fromIndex
2970 * (inclusive) to toIndex (exclusive). If the two indices are equal, the
2971 * sublist is empty. The returned list should be modifiable if and only
2972 * if this list is modifiable. Changes to the returned list should be
2973 * reflected in this list. If this list is structurally modified in
2974 * any way other than through the returned list, the result of any subsequent
2975 * operations on the returned list is undefined. A lock is obtained
2976 * on the mutex before the creation of the sublist. The returned list
2977 * is also synchronized, using the same mutex. Random accessibility
2978 * is also extended to the new list.
2979 *
2980 * @param fromIndex the index that the returned list should start from
2981 * (inclusive)
2982 * @param toIndex the index that the returned list should go to (exclusive)
2983 * @return a List backed by a subsection of this list
2984 * @throws IndexOutOfBoundsException if fromIndex < 0
2985 * || toIndex > size() || fromIndex > toIndex
2986 */
2987 public List<T> subList(int fromIndex, int toIndex)
2988 {
2989 synchronized (mutex)
2990 {
2991 return new SynchronizedRandomAccessList<T>(mutex,
2992 list.subList(fromIndex,
2993 toIndex));
2994 }
2995 }
2996 } // class SynchronizedRandomAccessList
2997
2998 /**
2999 * The implementation of {@link SynchronizedList#listIterator()}. This
3000 * iterator must "sync" on the same object as the list it iterates over.
3001 *
3002 * @author Eric Blake (ebb9@email.byu.edu)
3003 */
3004 private static final class SynchronizedListIterator<T>
3005 extends SynchronizedIterator<T> implements ListIterator<T>
3006 {
3007 /**
3008 * The wrapped iterator, stored both here and in the superclass to
3009 * avoid excessive casting.
3010 */
3011 private final ListIterator<T> li;
3012
3013 /**
3014 * Only trusted code creates a wrapper, with the specified sync.
3015 * @param sync the mutex
3016 * @param li the wrapped iterator
3017 */
3018 SynchronizedListIterator(Object sync, ListIterator<T> li)
3019 {
3020 super(sync, li);
3021 this.li = li;
3022 }
3023
3024 /**
3025 * Insert an element into the underlying list at the current position of
3026 * the iterator (optional operation). The element is inserted in between
3027 * the element that would be returned by <code>previous()</code> and the
3028 * element that would be returned by <code>next()</code>. After the
3029 * insertion, a subsequent call to next is unaffected, but
3030 * a call to previous returns the item that was added. The values returned
3031 * by nextIndex() and previousIndex() are incremented. A lock is obtained
3032 * on the mutex before the addition takes place.
3033 *
3034 * @param o the object to insert into the list
3035 * @throws ClassCastException if the object is of a type which cannot be added
3036 * to this list.
3037 * @throws IllegalArgumentException if some other aspect of the object stops
3038 * it being added to this list.
3039 * @throws UnsupportedOperationException if this ListIterator does not
3040 * support the add operation.
3041 */
3042 public void add(T o)
3043 {
3044 synchronized (mutex)
3045 {
3046 li.add(o);
3047 }
3048 }
3049
3050 /**
3051 * Tests whether there are elements remaining in the underlying list
3052 * in the reverse direction. In other words, <code>previous()</code>
3053 * will not fail with a NoSuchElementException. A lock is obtained
3054 * on the mutex before the check takes place.
3055 *
3056 * @return <code>true</code> if the list continues in the reverse direction
3057 */
3058 public boolean hasPrevious()
3059 {
3060 synchronized (mutex)
3061 {
3062 return li.hasPrevious();
3063 }
3064 }
3065
3066 /**
3067 * Find the index of the element that would be returned by a call to
3068 * <code>next()</code>. If hasNext() returns <code>false</code>, this
3069 * returns the list size. A lock is obtained on the mutex before the
3070 * query takes place.
3071 *
3072 * @return the index of the element that would be returned by next()
3073 */
3074 public int nextIndex()
3075 {
3076 synchronized (mutex)
3077 {
3078 return li.nextIndex();
3079 }
3080 }
3081
3082 /**
3083 * Obtain the previous element from the underlying list. Repeated
3084 * calls to previous may be used to iterate backwards over the entire list,
3085 * or calls to next and previous may be used together to go forwards and
3086 * backwards. Alternating calls to next and previous will return the same
3087 * element. A lock is obtained on the mutex before the object is retrieved.
3088 *
3089 * @return the next element in the list in the reverse direction
3090 * @throws NoSuchElementException if there are no more elements
3091 */
3092 public T previous()
3093 {
3094 synchronized (mutex)
3095 {
3096 return li.previous();
3097 }
3098 }
3099
3100 /**
3101 * Find the index of the element that would be returned by a call to
3102 * previous. If hasPrevious() returns <code>false</code>, this returns -1.
3103 * A lock is obtained on the mutex before the query takes place.
3104 *
3105 * @return the index of the element that would be returned by previous()
3106 */
3107 public int previousIndex()
3108 {
3109 synchronized (mutex)
3110 {
3111 return li.previousIndex();
3112 }
3113 }
3114
3115 /**
3116 * Replace the element last returned by a call to <code>next()</code> or
3117 * <code>previous()</code> with a given object (optional operation). This
3118 * method may only be called if neither <code>add()</code> nor
3119 * <code>remove()</code> have been called since the last call to
3120 * <code>next()</code> or <code>previous</code>. A lock is obtained
3121 * on the mutex before the list is modified.
3122 *
3123 * @param o the object to replace the element with
3124 * @throws ClassCastException the object is of a type which cannot be added
3125 * to this list
3126 * @throws IllegalArgumentException some other aspect of the object stops
3127 * it being added to this list
3128 * @throws IllegalStateException if neither next or previous have been
3129 * called, or if add or remove has been called since the last call
3130 * to next or previous
3131 * @throws UnsupportedOperationException if this ListIterator does not
3132 * support the set operation
3133 */
3134 public void set(T o)
3135 {
3136 synchronized (mutex)
3137 {
3138 li.set(o);
3139 }
3140 }
3141 } // class SynchronizedListIterator
3142
3143 /**
3144 * Returns a synchronized (thread-safe) map wrapper backed by the given
3145 * map. Notice that element access through the collection views and their
3146 * iterators are thread-safe, but if the map can be structurally modified
3147 * (adding or removing elements) then you should synchronize around the
3148 * iteration to avoid non-deterministic behavior:<br>
3149 * <pre>
3150 * Map m = Collections.synchronizedMap(new Map(...));
3151 * ...
3152 * Set s = m.keySet(); // safe outside a synchronized block
3153 * synchronized (m) // synch on m, not s
3154 * {
3155 * Iterator i = s.iterator();
3156 * while (i.hasNext())
3157 * foo(i.next());
3158 * }
3159 * </pre><p>
3160 *
3161 * The returned Map implements Serializable, but can only be serialized if
3162 * the map it wraps is likewise Serializable.
3163 *
3164 * @param m the map to wrap
3165 * @return a synchronized view of the map
3166 * @see Serializable
3167 */
3168 public static <K, V> Map<K, V> synchronizedMap(Map<K, V> m)
3169 {
3170 return new SynchronizedMap<K, V>(m);
3171 }
3172
3173 /**
3174 * The implementation of {@link #synchronizedMap(Map)}. This
3175 * class name is required for compatibility with Sun's JDK serializability.
3176 *
3177 * @author Eric Blake (ebb9@email.byu.edu)
3178 */
3179 private static class SynchronizedMap<K, V> implements Map<K, V>, Serializable
3180 {
3181 /**
3182 * Compatible with JDK 1.4.
3183 */
3184 private static final long serialVersionUID = 1978198479659022715L;
3185
3186 /**
3187 * The wrapped map.
3188 * @serial the real map
3189 */
3190 private final Map<K, V> m;
3191
3192 /**
3193 * The object to synchronize on. When an instance is created via public
3194 * methods, it will be this; but other uses like
3195 * SynchronizedSortedMap.subMap() must specify another mutex. Package
3196 * visible for use by subclass.
3197 * @serial the lock
3198 */
3199 final Object mutex;
3200
3201 /**
3202 * Cache the entry set.
3203 */
3204 private transient Set<Map.Entry<K, V>> entries;
3205
3206 /**
3207 * Cache the key set.
3208 */
3209 private transient Set<K> keys;
3210
3211 /**
3212 * Cache the value collection.
3213 */
3214 private transient Collection<V> values;
3215
3216 /**
3217 * Wrap a given map.
3218 * @param m the map to wrap
3219 * @throws NullPointerException if m is null
3220 */
3221 SynchronizedMap(Map<K, V> m)
3222 {
3223 this.m = m;
3224 mutex = this;
3225 if (m == null)
3226 throw new NullPointerException();
3227 }
3228
3229 /**
3230 * Called only by trusted code to specify the mutex as well as the map.
3231 * @param sync the mutex
3232 * @param m the map
3233 */
3234 SynchronizedMap(Object sync, Map<K, V> m)
3235 {
3236 this.m = m;
3237 mutex = sync;
3238 }
3239
3240 /**
3241 * Clears all the entries from the underlying map. A lock is obtained
3242 * on the mutex before the map is cleared.
3243 *
3244 * @throws UnsupportedOperationException if clear is not supported
3245 */
3246 public void clear()
3247 {
3248 synchronized (mutex)
3249 {
3250 m.clear();
3251 }
3252 }
3253
3254 /**
3255 * Returns <code>true</code> if the underlying map contains a entry for the given key.
3256 * A lock is obtained on the mutex before the map is queried.
3257 *
3258 * @param key the key to search for.
3259 * @return <code>true</code> if the underlying map contains the key.
3260 * @throws ClassCastException if the key is of an inappropriate type.
3261 * @throws NullPointerException if key is <code>null</code> but the map
3262 * does not permit null keys.
3263 */
3264 public boolean containsKey(Object key)
3265 {
3266 synchronized (mutex)
3267 {
3268 return m.containsKey(key);
3269 }
3270 }
3271
3272 /**
3273 * Returns <code>true</code> if the underlying map contains at least one entry with the
3274 * given value. In other words, returns <code>true</code> if a value v exists where
3275 * <code>(value == null ? v == null : value.equals(v))</code>. This usually
3276 * requires linear time. A lock is obtained on the mutex before the map
3277 * is queried.
3278 *
3279 * @param value the value to search for
3280 * @return <code>true</code> if the map contains the value
3281 * @throws ClassCastException if the type of the value is not a valid type
3282 * for this map.
3283 * @throws NullPointerException if the value is null and the map doesn't
3284 * support null values.
3285 */
3286 public boolean containsValue(Object value)
3287 {
3288 synchronized (mutex)
3289 {
3290 return m.containsValue(value);
3291 }
3292 }
3293
3294 // This is one of the ickiest cases of nesting I've ever seen. It just
3295 // means "return a SynchronizedSet, except that the iterator() method
3296 // returns an SynchronizedIterator whose next() method returns a
3297 // synchronized wrapper around its normal return value".
3298 public Set<Map.Entry<K, V>> entrySet()
3299 {
3300 // Define this here to spare some nesting.
3301 class SynchronizedMapEntry<K, V> implements Map.Entry<K, V>
3302 {
3303 final Map.Entry<K, V> e;
3304 SynchronizedMapEntry(Map.Entry<K, V> o)
3305 {
3306 e = o;
3307 }
3308
3309 /**
3310 * Returns <code>true</code> if the object, o, implements <code>Map.Entry</code>
3311 * with the same key and value as the underlying entry. A lock is
3312 * obtained on the mutex before the comparison takes place.
3313 *
3314 * @param o The object to compare with this entry.
3315 * @return <code>true</code> if o is equivalent to the underlying map entry.
3316 */
3317 public boolean equals(Object o)
3318 {
3319 synchronized (mutex)
3320 {
3321 return e.equals(o);
3322 }
3323 }
3324
3325 /**
3326 * Returns the key used in the underlying map entry. A lock is obtained
3327 * on the mutex before the key is retrieved.
3328 *
3329 * @return The key of the underlying map entry.
3330 */
3331 public K getKey()
3332 {
3333 synchronized (mutex)
3334 {
3335 return e.getKey();
3336 }
3337 }
3338
3339 /**
3340 * Returns the value used in the underlying map entry. A lock is obtained
3341 * on the mutex before the value is retrieved.
3342 *
3343 * @return The value of the underlying map entry.
3344 */
3345 public V getValue()
3346 {
3347 synchronized (mutex)
3348 {
3349 return e.getValue();
3350 }
3351 }
3352
3353 /**
3354 * Computes the hash code for the underlying map entry.
3355 * This computation is described in the documentation for the
3356 * <code>Map</code> interface. A lock is obtained on the mutex
3357 * before the underlying map is accessed.
3358 *
3359 * @return The hash code of the underlying map entry.
3360 * @see Map#hashCode()
3361 */
3362 public int hashCode()
3363 {
3364 synchronized (mutex)
3365 {
3366 return e.hashCode();
3367 }
3368 }
3369
3370 /**
3371 * Replaces the value in the underlying map entry with the specified
3372 * object (optional operation). A lock is obtained on the mutex
3373 * before the map is altered. The map entry, in turn, will alter
3374 * the underlying map object. The operation is undefined if the
3375 * <code>remove()</code> method of the iterator has been called
3376 * beforehand.
3377 *
3378 * @param value the new value to store
3379 * @return the old value
3380 * @throws UnsupportedOperationException if the operation is not supported.
3381 * @throws ClassCastException if the value is of the wrong type.
3382 * @throws IllegalArgumentException if something about the value
3383 * prevents it from existing in this map.
3384 * @throws NullPointerException if the map forbids null values.
3385 */
3386 public V setValue(V value)
3387 {
3388 synchronized (mutex)
3389 {
3390 return e.setValue(value);
3391 }
3392 }
3393
3394 /**
3395 * Returns a textual representation of the underlying map entry.
3396 * A lock is obtained on the mutex before the entry is accessed.
3397 *
3398 * @return The contents of the map entry in <code>String</code> form.
3399 */
3400 public String toString()
3401 {
3402 synchronized (mutex)
3403 {
3404 return e.toString();
3405 }
3406 }
3407 } // class SynchronizedMapEntry
3408
3409 // Now the actual code.
3410 if (entries == null)
3411 synchronized (mutex)
3412 {
3413 entries = new SynchronizedSet<Map.Entry<K, V>>(mutex, m.entrySet())
3414 {
3415 /**
3416 * Returns an iterator over the set. The iterator has no specific order,
3417 * unless further specified. A lock is obtained on the set's mutex
3418 * before the iterator is created. The created iterator is also
3419 * thread-safe.
3420 *
3421 * @return A synchronized set iterator.
3422 */
3423 public Iterator<Map.Entry<K, V>> iterator()
3424 {
3425 synchronized (super.mutex)
3426 {
3427 return new SynchronizedIterator<Map.Entry<K, V>>(super.mutex,
3428 c.iterator())
3429 {
3430 /**
3431 * Retrieves the next map entry from the iterator.
3432 * A lock is obtained on the iterator's mutex before
3433 * the entry is created. The new map entry is enclosed in
3434 * a thread-safe wrapper.
3435 *
3436 * @return A synchronized map entry.
3437 */
3438 public Map.Entry<K, V> next()
3439 {
3440 synchronized (super.mutex)
3441 {
3442 return new SynchronizedMapEntry<K, V>(super.next());
3443 }
3444 }
3445 };
3446 }
3447 }
3448 };
3449 }
3450 return entries;
3451 }
3452
3453 /**
3454 * Returns <code>true</code> if the object, o, is also an instance
3455 * of <code>Map</code> and contains an equivalent
3456 * entry set to that of the underlying map. A lock
3457 * is obtained on the mutex before the objects are
3458 * compared.
3459 *
3460 * @param o The object to compare.
3461 * @return <code>true</code> if o and the underlying map are equivalent.
3462 */
3463 public boolean equals(Object o)
3464 {
3465 synchronized (mutex)
3466 {
3467 return m.equals(o);
3468 }
3469 }
3470
3471 /**
3472 * Returns the value associated with the given key, or null
3473 * if no such mapping exists. An ambiguity exists with maps
3474 * that accept null values as a return value of null could
3475 * be due to a non-existent mapping or simply a null value
3476 * for that key. To resolve this, <code>containsKey</code>
3477 * should be used. A lock is obtained on the mutex before
3478 * the value is retrieved from the underlying map.
3479 *
3480 * @param key The key of the required mapping.
3481 * @return The value associated with the given key, or
3482 * null if no such mapping exists.
3483 * @throws ClassCastException if the key is an inappropriate type.
3484 * @throws NullPointerException if this map does not accept null keys.
3485 */
3486 public V get(Object key)
3487 {
3488 synchronized (mutex)
3489 {
3490 return m.get(key);
3491 }
3492 }
3493
3494 /**
3495 * Calculates the hash code of the underlying map as the
3496 * sum of the hash codes of all entries. A lock is obtained
3497 * on the mutex before the hash code is computed.
3498 *
3499 * @return The hash code of the underlying map.
3500 */
3501 public int hashCode()
3502 {
3503 synchronized (mutex)
3504 {
3505 return m.hashCode();
3506 }
3507 }
3508
3509 /**
3510 * Returns <code>true</code> if the underlying map contains no entries.
3511 * A lock is obtained on the mutex before the map is examined.
3512 *
3513 * @return <code>true</code> if the map is empty.
3514 */
3515 public boolean isEmpty()
3516 {
3517 synchronized (mutex)
3518 {
3519 return m.isEmpty();
3520 }
3521 }
3522
3523 /**
3524 * Returns a thread-safe set view of the keys in the underlying map. The
3525 * set is backed by the map, so that changes in one show up in the other.
3526 * Modifications made while an iterator is in progress cause undefined
3527 * behavior. If the set supports removal, these methods remove the
3528 * underlying mapping from the map: <code>Iterator.remove</code>,
3529 * <code>Set.remove</code>, <code>removeAll</code>, <code>retainAll</code>,
3530 * and <code>clear</code>. Element addition, via <code>add</code> or
3531 * <code>addAll</code>, is not supported via this set. A lock is obtained
3532 * on the mutex before the set is created.
3533 *
3534 * @return A synchronized set containing the keys of the underlying map.
3535 */
3536 public Set<K> keySet()
3537 {
3538 if (keys == null)
3539 synchronized (mutex)
3540 {
3541 keys = new SynchronizedSet<K>(mutex, m.keySet());
3542 }
3543 return keys;
3544 }
3545
3546 /**
3547 * Associates the given key to the given value (optional operation). If the
3548 * underlying map already contains the key, its value is replaced. Be aware
3549 * that in a map that permits <code>null</code> values, a null return does not
3550 * always imply that the mapping was created. A lock is obtained on the mutex
3551 * before the modification is made.
3552 *
3553 * @param key the key to map.
3554 * @param value the value to be mapped.
3555 * @return the previous value of the key, or null if there was no mapping
3556 * @throws UnsupportedOperationException if the operation is not supported
3557 * @throws ClassCastException if the key or value is of the wrong type
3558 * @throws IllegalArgumentException if something about this key or value
3559 * prevents it from existing in this map
3560 * @throws NullPointerException if either the key or the value is null,
3561 * and the map forbids null keys or values
3562 * @see #containsKey(Object)
3563 */
3564 public V put(K key, V value)
3565 {
3566 synchronized (mutex)
3567 {
3568 return m.put(key, value);
3569 }
3570 }
3571
3572 /**
3573 * Copies all entries of the given map to the underlying one (optional
3574 * operation). If the map already contains a key, its value is replaced.
3575 * A lock is obtained on the mutex before the operation proceeds.
3576 *
3577 * @param map the mapping to load into this map
3578 * @throws UnsupportedOperationException if the operation is not supported
3579 * @throws ClassCastException if a key or value is of the wrong type
3580 * @throws IllegalArgumentException if something about a key or value
3581 * prevents it from existing in this map
3582 * @throws NullPointerException if the map forbids null keys or values, or
3583 * if <code>m</code> is null.
3584 * @see #put(Object, Object)
3585 */
3586 public void putAll(Map<? extends K, ? extends V> map)
3587 {
3588 synchronized (mutex)
3589 {
3590 m.putAll(map);
3591 }
3592 }
3593
3594 /**
3595 * Removes the mapping for the key, o, if present (optional operation). If
3596 * the key is not present, this returns null. Note that maps which permit
3597 * null values may also return null if the key was removed. A prior
3598 * <code>containsKey()</code> check is required to avoid this ambiguity.
3599 * Before the mapping is removed, a lock is obtained on the mutex.
3600 *
3601 * @param o the key to remove
3602 * @return the value the key mapped to, or null if not present
3603 * @throws UnsupportedOperationException if deletion is unsupported
3604 * @throws NullPointerException if the key is null and this map doesn't
3605 * support null keys.
3606 * @throws ClassCastException if the type of the key is not a valid type
3607 * for this map.
3608 */
3609 public V remove(Object o)
3610 {
3611 synchronized (mutex)
3612 {
3613 return m.remove(o);
3614 }
3615 }
3616
3617 /**
3618 * Retrieves the size of the underlying map. A lock
3619 * is obtained on the mutex before access takes place.
3620 * Maps with a size greater than <code>Integer.MAX_VALUE</code>
3621 * return <code>Integer.MAX_VALUE</code> instead.
3622 *
3623 * @return The size of the underlying map.
3624 */
3625 public int size()
3626 {
3627 synchronized (mutex)
3628 {
3629 return m.size();
3630 }
3631 }
3632
3633 /**
3634 * Returns a textual representation of the underlying
3635 * map. A lock is obtained on the mutex before the map
3636 * is accessed.
3637 *
3638 * @return The map in <code>String</code> form.
3639 */
3640 public String toString()
3641 {
3642 synchronized (mutex)
3643 {
3644 return m.toString();
3645 }
3646 }
3647
3648 /**
3649 * Returns a synchronized collection view of the values in the underlying
3650 * map. The collection is backed by the map, so that changes in one show up in
3651 * the other. Modifications made while an iterator is in progress cause
3652 * undefined behavior. If the collection supports removal, these methods
3653 * remove the underlying mapping from the map: <code>Iterator.remove</code>,
3654 * <code>Collection.remove</code>, <code>removeAll</code>,
3655 * <code>retainAll</code>, and <code>clear</code>. Element addition, via
3656 * <code>add</code> or <code>addAll</code>, is not supported via this
3657 * collection. A lock is obtained on the mutex before the collection
3658 * is created.
3659 *
3660 * @return the collection of all values in the underlying map.
3661 */
3662 public Collection<V> values()
3663 {
3664 if (values == null)
3665 synchronized (mutex)
3666 {
3667 values = new SynchronizedCollection<V>(mutex, m.values());
3668 }
3669 return values;
3670 }
3671 } // class SynchronizedMap
3672
3673 /**
3674 * Returns a synchronized (thread-safe) set wrapper backed by the given
3675 * set. Notice that element access through the iterator is thread-safe, but
3676 * if the set can be structurally modified (adding or removing elements)
3677 * then you should synchronize around the iteration to avoid
3678 * non-deterministic behavior:<br>
3679 * <pre>
3680 * Set s = Collections.synchronizedSet(new Set(...));
3681 * ...
3682 * synchronized (s)
3683 * {
3684 * Iterator i = s.iterator();
3685 * while (i.hasNext())
3686 * foo(i.next());
3687 * }
3688 * </pre><p>
3689 *
3690 * The returned Set implements Serializable, but can only be serialized if
3691 * the set it wraps is likewise Serializable.
3692 *
3693 * @param s the set to wrap
3694 * @return a synchronized view of the set
3695 * @see Serializable
3696 */
3697 public static <T> Set<T> synchronizedSet(Set<T> s)
3698 {
3699 return new SynchronizedSet<T>(s);
3700 }
3701
3702 /**
3703 * The implementation of {@link #synchronizedSet(Set)}. This class
3704 * name is required for compatibility with Sun's JDK serializability.
3705 * Package visible, so that sets such as Hashtable.keySet()
3706 * can specify which object to synchronize on.
3707 *
3708 * @author Eric Blake (ebb9@email.byu.edu)
3709 */
3710 static class SynchronizedSet<T> extends SynchronizedCollection<T>
3711 implements Set<T>
3712 {
3713 /**
3714 * Compatible with JDK 1.4.
3715 */
3716 private static final long serialVersionUID = 487447009682186044L;
3717
3718 /**
3719 * Wrap a given set.
3720 * @param s the set to wrap
3721 * @throws NullPointerException if s is null
3722 */
3723 SynchronizedSet(Set<T> s)
3724 {
3725 super(s);
3726 }
3727
3728 /**
3729 * Called only by trusted code to specify the mutex as well as the set.
3730 * @param sync the mutex
3731 * @param s the set
3732 */
3733 SynchronizedSet(Object sync, Set<T> s)
3734 {
3735 super(sync, s);
3736 }
3737
3738 /**
3739 * Returns <code>true</code> if the object, o, is a <code>Set</code>
3740 * of the same size as the underlying set, and contains
3741 * each element, e, which occurs in the underlying set.
3742 * A lock is obtained on the mutex before the comparison
3743 * takes place.
3744 *
3745 * @param o The object to compare against.
3746 * @return <code>true</code> if o is an equivalent set.
3747 */
3748 public boolean equals(Object o)
3749 {
3750 synchronized (mutex)
3751 {
3752 return c.equals(o);
3753 }
3754 }
3755
3756 /**
3757 * Computes the hash code for the underlying set as the
3758 * sum of the hash code of all elements within the set.
3759 * A lock is obtained on the mutex before the computation
3760 * occurs.
3761 *
3762 * @return The hash code for the underlying set.
3763 */
3764 public int hashCode()
3765 {
3766 synchronized (mutex)
3767 {
3768 return c.hashCode();
3769 }
3770 }
3771 } // class SynchronizedSet
3772
3773 /**
3774 * Returns a synchronized (thread-safe) sorted map wrapper backed by the
3775 * given map. Notice that element access through the collection views,
3776 * subviews, and their iterators are thread-safe, but if the map can be
3777 * structurally modified (adding or removing elements) then you should
3778 * synchronize around the iteration to avoid non-deterministic behavior:<br>
3779 * <pre>
3780 * SortedMap m = Collections.synchronizedSortedMap(new SortedMap(...));
3781 * ...
3782 * Set s = m.keySet(); // safe outside a synchronized block
3783 * SortedMap m2 = m.headMap(foo); // safe outside a synchronized block
3784 * Set s2 = m2.keySet(); // safe outside a synchronized block
3785 * synchronized (m) // synch on m, not m2, s or s2
3786 * {
3787 * Iterator i = s.iterator();
3788 * while (i.hasNext())
3789 * foo(i.next());
3790 * i = s2.iterator();
3791 * while (i.hasNext())
3792 * bar(i.next());
3793 * }
3794 * </pre><p>
3795 *
3796 * The returned SortedMap implements Serializable, but can only be
3797 * serialized if the map it wraps is likewise Serializable.
3798 *
3799 * @param m the sorted map to wrap
3800 * @return a synchronized view of the sorted map
3801 * @see Serializable
3802 */
3803 public static <K, V> SortedMap<K, V> synchronizedSortedMap(SortedMap<K, V> m)
3804 {
3805 return new SynchronizedSortedMap<K, V>(m);
3806 }
3807
3808 /**
3809 * The implementation of {@link #synchronizedSortedMap(SortedMap)}. This
3810 * class name is required for compatibility with Sun's JDK serializability.
3811 *
3812 * @author Eric Blake (ebb9@email.byu.edu)
3813 */
3814 private static final class SynchronizedSortedMap<K, V>
3815 extends SynchronizedMap<K, V>
3816 implements SortedMap<K, V>
3817 {
3818 /**
3819 * Compatible with JDK 1.4.
3820 */
3821 private static final long serialVersionUID = -8798146769416483793L;
3822
3823 /**
3824 * The wrapped map; stored both here and in the superclass to avoid
3825 * excessive casting.
3826 * @serial the wrapped map
3827 */
3828 private final SortedMap<K, V> sm;
3829
3830 /**
3831 * Wrap a given map.
3832 * @param sm the map to wrap
3833 * @throws NullPointerException if sm is null
3834 */
3835 SynchronizedSortedMap(SortedMap<K, V> sm)
3836 {
3837 super(sm);
3838 this.sm = sm;
3839 }
3840
3841 /**
3842 * Called only by trusted code to specify the mutex as well as the map.
3843 * @param sync the mutex
3844 * @param sm the map
3845 */
3846 SynchronizedSortedMap(Object sync, SortedMap<K, V> sm)
3847 {
3848 super(sync, sm);
3849 this.sm = sm;
3850 }
3851
3852 /**
3853 * Returns the comparator used in sorting the underlying map, or null if
3854 * it is the keys' natural ordering. A lock is obtained on the mutex
3855 * before the comparator is retrieved.
3856 *
3857 * @return the sorting comparator.
3858 */
3859 public Comparator<? super K> comparator()
3860 {
3861 synchronized (mutex)
3862 {
3863 return sm.comparator();
3864 }
3865 }
3866
3867 /**
3868 * Returns the first, lowest sorted, key from the underlying map.
3869 * A lock is obtained on the mutex before the map is accessed.
3870 *
3871 * @return the first key.
3872 * @throws NoSuchElementException if this map is empty.
3873 */
3874 public K firstKey()
3875 {
3876 synchronized (mutex)
3877 {
3878 return sm.firstKey();
3879 }
3880 }
3881
3882 /**
3883 * Returns a submap containing the keys from the first
3884 * key (as returned by <code>firstKey()</code>) to
3885 * the key before that specified. The submap supports all
3886 * operations supported by the underlying map and all actions
3887 * taking place on the submap are also reflected in the underlying
3888 * map. A lock is obtained on the mutex prior to submap creation.
3889 * This operation is equivalent to <code>subMap(firstKey(), toKey)</code>.
3890 * The submap retains the thread-safe status of this map.
3891 *
3892 * @param toKey the exclusive upper range of the submap.
3893 * @return a submap from <code>firstKey()</code> to the
3894 * the key preceding toKey.
3895 * @throws ClassCastException if toKey is not comparable to the underlying
3896 * map's contents.
3897 * @throws IllegalArgumentException if toKey is outside the map's range.
3898 * @throws NullPointerException if toKey is null. but the map does not allow
3899 * null keys.
3900 */
3901 public SortedMap<K, V> headMap(K toKey)
3902 {
3903 synchronized (mutex)
3904 {
3905 return new SynchronizedSortedMap<K, V>(mutex, sm.headMap(toKey));
3906 }
3907 }
3908
3909 /**
3910 * Returns the last, highest sorted, key from the underlying map.
3911 * A lock is obtained on the mutex before the map is accessed.
3912 *
3913 * @return the last key.
3914 * @throws NoSuchElementException if this map is empty.
3915 */
3916 public K lastKey()
3917 {
3918 synchronized (mutex)
3919 {
3920 return sm.lastKey();
3921 }
3922 }
3923
3924 /**
3925 * Returns a submap containing the keys from fromKey to
3926 * the key before toKey. The submap supports all
3927 * operations supported by the underlying map and all actions
3928 * taking place on the submap are also reflected in the underlying
3929 * map. A lock is obtained on the mutex prior to submap creation.
3930 * The submap retains the thread-safe status of this map.
3931 *
3932 * @param fromKey the inclusive lower range of the submap.
3933 * @param toKey the exclusive upper range of the submap.
3934 * @return a submap from fromKey to the key preceding toKey.
3935 * @throws ClassCastException if fromKey or toKey is not comparable
3936 * to the underlying map's contents.
3937 * @throws IllegalArgumentException if fromKey or toKey is outside the map's
3938 * range.
3939 * @throws NullPointerException if fromKey or toKey is null. but the map does
3940 * not allow null keys.
3941 */
3942 public SortedMap<K, V> subMap(K fromKey, K toKey)
3943 {
3944 synchronized (mutex)
3945 {
3946 return new SynchronizedSortedMap<K, V>(mutex,
3947 sm.subMap(fromKey, toKey));
3948 }
3949 }
3950
3951 /**
3952 * Returns a submap containing all the keys from fromKey onwards.
3953 * The submap supports all operations supported by the underlying
3954 * map and all actions taking place on the submap are also reflected
3955 * in the underlying map. A lock is obtained on the mutex prior to
3956 * submap creation. The submap retains the thread-safe status of
3957 * this map.
3958 *
3959 * @param fromKey the inclusive lower range of the submap.
3960 * @return a submap from fromKey to <code>lastKey()</code>.
3961 * @throws ClassCastException if fromKey is not comparable to the underlying
3962 * map's contents.
3963 * @throws IllegalArgumentException if fromKey is outside the map's range.
3964 * @throws NullPointerException if fromKey is null. but the map does not allow
3965 * null keys.
3966 */
3967 public SortedMap<K, V> tailMap(K fromKey)
3968 {
3969 synchronized (mutex)
3970 {
3971 return new SynchronizedSortedMap<K, V>(mutex, sm.tailMap(fromKey));
3972 }
3973 }
3974 } // class SynchronizedSortedMap
3975
3976 /**
3977 * Returns a synchronized (thread-safe) sorted set wrapper backed by the
3978 * given set. Notice that element access through the iterator and through
3979 * subviews are thread-safe, but if the set can be structurally modified
3980 * (adding or removing elements) then you should synchronize around the
3981 * iteration to avoid non-deterministic behavior:<br>
3982 * <pre>
3983 * SortedSet s = Collections.synchronizedSortedSet(new SortedSet(...));
3984 * ...
3985 * SortedSet s2 = s.headSet(foo); // safe outside a synchronized block
3986 * synchronized (s) // synch on s, not s2
3987 * {
3988 * Iterator i = s2.iterator();
3989 * while (i.hasNext())
3990 * foo(i.next());
3991 * }
3992 * </pre><p>
3993 *
3994 * The returned SortedSet implements Serializable, but can only be
3995 * serialized if the set it wraps is likewise Serializable.
3996 *
3997 * @param s the sorted set to wrap
3998 * @return a synchronized view of the sorted set
3999 * @see Serializable
4000 */
4001 public static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s)
4002 {
4003 return new SynchronizedSortedSet<T>(s);
4004 }
4005
4006 /**
4007 * The implementation of {@link #synchronizedSortedSet(SortedSet)}. This
4008 * class name is required for compatibility with Sun's JDK serializability.
4009 *
4010 * @author Eric Blake (ebb9@email.byu.edu)
4011 */
4012 private static final class SynchronizedSortedSet<T>
4013 extends SynchronizedSet<T>
4014 implements SortedSet<T>
4015 {
4016 /**
4017 * Compatible with JDK 1.4.
4018 */
4019 private static final long serialVersionUID = 8695801310862127406L;
4020
4021 /**
4022 * The wrapped set; stored both here and in the superclass to avoid
4023 * excessive casting.
4024 * @serial the wrapped set
4025 */
4026 private final SortedSet<T> ss;
4027
4028 /**
4029 * Wrap a given set.
4030 * @param ss the set to wrap
4031 * @throws NullPointerException if ss is null
4032 */
4033 SynchronizedSortedSet(SortedSet<T> ss)
4034 {
4035 super(ss);
4036 this.ss = ss;
4037 }
4038
4039 /**
4040 * Called only by trusted code to specify the mutex as well as the set.
4041 * @param sync the mutex
4042 * @param ss the set
4043 */
4044 SynchronizedSortedSet(Object sync, SortedSet<T> ss)
4045 {
4046 super(sync, ss);
4047 this.ss = ss;
4048 }
4049
4050 /**
4051 * Returns the comparator used in sorting the underlying set, or null if
4052 * it is the elements' natural ordering. A lock is obtained on the mutex
4053 * before the comparator is retrieved.
4054 *
4055 * @return the sorting comparator.
4056 */
4057 public Comparator<? super T> comparator()
4058 {
4059 synchronized (mutex)
4060 {
4061 return ss.comparator();
4062 }
4063 }
4064
4065 /**
4066 * Returns the first, lowest sorted, element from the underlying set.
4067 * A lock is obtained on the mutex before the set is accessed.
4068 *
4069 * @return the first element.
4070 * @throws NoSuchElementException if this set is empty.
4071 */
4072 public T first()
4073 {
4074 synchronized (mutex)
4075 {
4076 return ss.first();
4077 }
4078 }
4079
4080 /**
4081 * Returns a subset containing the element from the first
4082 * element (as returned by <code>first()</code>) to
4083 * the element before that specified. The subset supports all
4084 * operations supported by the underlying set and all actions
4085 * taking place on the subset are also reflected in the underlying
4086 * set. A lock is obtained on the mutex prior to subset creation.
4087 * This operation is equivalent to <code>subSet(first(), toElement)</code>.
4088 * The subset retains the thread-safe status of this set.
4089 *
4090 * @param toElement the exclusive upper range of the subset.
4091 * @return a subset from <code>first()</code> to the
4092 * the element preceding toElement.
4093 * @throws ClassCastException if toElement is not comparable to the underlying
4094 * set's contents.
4095 * @throws IllegalArgumentException if toElement is outside the set's range.
4096 * @throws NullPointerException if toElement is null. but the set does not allow
4097 * null elements.
4098 */
4099 public SortedSet<T> headSet(T toElement)
4100 {
4101 synchronized (mutex)
4102 {
4103 return new SynchronizedSortedSet<T>(mutex, ss.headSet(toElement));
4104 }
4105 }
4106
4107 /**
4108 * Returns the last, highest sorted, element from the underlying set.
4109 * A lock is obtained on the mutex before the set is accessed.
4110 *
4111 * @return the last element.
4112 * @throws NoSuchElementException if this set is empty.
4113 */
4114 public T last()
4115 {
4116 synchronized (mutex)
4117 {
4118 return ss.last();
4119 }
4120 }
4121
4122 /**
4123 * Returns a subset containing the elements from fromElement to
4124 * the element before toElement. The subset supports all
4125 * operations supported by the underlying set and all actions
4126 * taking place on the subset are also reflected in the underlying
4127 * set. A lock is obtained on the mutex prior to subset creation.
4128 * The subset retains the thread-safe status of this set.
4129 *
4130 * @param fromElement the inclusive lower range of the subset.
4131 * @param toElement the exclusive upper range of the subset.
4132 * @return a subset from fromElement to the element preceding toElement.
4133 * @throws ClassCastException if fromElement or toElement is not comparable
4134 * to the underlying set's contents.
4135 * @throws IllegalArgumentException if fromElement or toElement is outside the set's
4136 * range.
4137 * @throws NullPointerException if fromElement or toElement is null. but the set does
4138 * not allow null elements.
4139 */
4140 public SortedSet<T> subSet(T fromElement, T toElement)
4141 {
4142 synchronized (mutex)
4143 {
4144 return new SynchronizedSortedSet<T>(mutex,
4145 ss.subSet(fromElement,
4146 toElement));
4147 }
4148 }
4149
4150 /**
4151 * Returns a subset containing all the elements from fromElement onwards.
4152 * The subset supports all operations supported by the underlying
4153 * set and all actions taking place on the subset are also reflected
4154 * in the underlying set. A lock is obtained on the mutex prior to
4155 * subset creation. The subset retains the thread-safe status of
4156 * this set.
4157 *
4158 * @param fromElement the inclusive lower range of the subset.
4159 * @return a subset from fromElement to <code>last()</code>.
4160 * @throws ClassCastException if fromElement is not comparable to the underlying
4161 * set's contents.
4162 * @throws IllegalArgumentException if fromElement is outside the set's range.
4163 * @throws NullPointerException if fromElement is null. but the set does not allow
4164 * null elements.
4165 */
4166 public SortedSet<T> tailSet(T fromElement)
4167 {
4168 synchronized (mutex)
4169 {
4170 return new SynchronizedSortedSet<T>(mutex, ss.tailSet(fromElement));
4171 }
4172 }
4173 } // class SynchronizedSortedSet
4174
4175
4176 /**
4177 * Returns an unmodifiable view of the given collection. This allows
4178 * "read-only" access, although changes in the backing collection show up
4179 * in this view. Attempts to modify the collection directly or via iterators
4180 * will fail with {@link UnsupportedOperationException}. Although this view
4181 * prevents changes to the structure of the collection and its elements, the values
4182 * referenced by the objects in the collection can still be modified.
4183 * <p>
4184 *
4185 * Since the collection might be a List or a Set, and those have incompatible
4186 * equals and hashCode requirements, this relies on Object's implementation
4187 * rather than passing those calls on to the wrapped collection. The returned
4188 * Collection implements Serializable, but can only be serialized if
4189 * the collection it wraps is likewise Serializable.
4190 *
4191 * @param c the collection to wrap
4192 * @return a read-only view of the collection
4193 * @see Serializable
4194 */
4195 public static <T> Collection<T> unmodifiableCollection(Collection<? extends T> c)
4196 {
4197 return new UnmodifiableCollection<T>(c);
4198 }
4199
4200 /**
4201 * The implementation of {@link #unmodifiableCollection(Collection)}. This
4202 * class name is required for compatibility with Sun's JDK serializability.
4203 *
4204 * @author Eric Blake (ebb9@email.byu.edu)
4205 */
4206 private static class UnmodifiableCollection<T>
4207 implements Collection<T>, Serializable
4208 {
4209 /**
4210 * Compatible with JDK 1.4.
4211 */
4212 private static final long serialVersionUID = 1820017752578914078L;
4213
4214 /**
4215 * The wrapped collection. Package visible for use by subclasses.
4216 * @serial the real collection
4217 */
4218 final Collection<? extends T> c;
4219
4220 /**
4221 * Wrap a given collection.
4222 * @param c the collection to wrap
4223 * @throws NullPointerException if c is null
4224 */
4225 UnmodifiableCollection(Collection<? extends T> c)
4226 {
4227 this.c = c;
4228 if (c == null)
4229 throw new NullPointerException();
4230 }
4231
4232 /**
4233 * Blocks the addition of elements to the underlying collection.
4234 * This method never returns, throwing an exception instead.
4235 *
4236 * @param o the object to add.
4237 * @return <code>true</code> if the collection was modified as a result of this action.
4238 * @throws UnsupportedOperationException as an unmodifiable collection does not
4239 * support the add operation.
4240 */
4241 public boolean add(T o)
4242 {
4243 throw new UnsupportedOperationException();
4244 }
4245
4246 /**
4247 * Blocks the addition of a collection of elements to the underlying
4248 * collection. This method never returns, throwing an exception instead.
4249 *
4250 * @param c the collection to add.
4251 * @return <code>true</code> if the collection was modified as a result of this action.
4252 * @throws UnsupportedOperationException as an unmodifiable collection does not
4253 * support the <code>addAll</code> operation.
4254 */
4255 public boolean addAll(Collection<? extends T> c)
4256 {
4257 throw new UnsupportedOperationException();
4258 }
4259
4260 /**
4261 * Blocks the clearing of the underlying collection. This method never
4262 * returns, throwing an exception instead.
4263 *
4264 * @throws UnsupportedOperationException as an unmodifiable collection does
4265 * not support the <code>clear()</code> operation.
4266 */
4267 public void clear()
4268 {
4269 throw new UnsupportedOperationException();
4270 }
4271
4272 /**
4273 * Test whether the underlying collection contains a given object as one of its
4274 * elements.
4275 *
4276 * @param o the element to look for.
4277 * @return <code>true</code> if the underlying collection contains at least
4278 * one element e such that
4279 * <code>o == null ? e == null : o.equals(e)</code>.
4280 * @throws ClassCastException if the type of o is not a valid type for the
4281 * underlying collection.
4282 * @throws NullPointerException if o is null and the underlying collection
4283 * doesn't support null values.
4284 */
4285 public boolean contains(Object o)
4286 {
4287 return c.contains(o);
4288 }
4289
4290 /**
4291 * Test whether the underlying collection contains every element in a given
4292 * collection.
4293 *
4294 * @param c1 the collection to test for.
4295 * @return <code>true</code> if for every element o in c, contains(o) would
4296 * return <code>true</code>.
4297 * @throws ClassCastException if the type of any element in c is not a valid
4298 * type for the underlying collection.
4299 * @throws NullPointerException if some element of c is null and the underlying
4300 * collection does not support null values.
4301 * @throws NullPointerException if c itself is null.
4302 */
4303 public boolean containsAll(Collection<?> c1)
4304 {
4305 return c.containsAll(c1);
4306 }
4307
4308 /**
4309 * Tests whether the underlying collection is empty, that is,
4310 * if size() == 0.
4311 *
4312 * @return <code>true</code> if this collection contains no elements.
4313 */
4314 public boolean isEmpty()
4315 {
4316 return c.isEmpty();
4317 }
4318
4319 /**
4320 * Obtain an Iterator over the underlying collection, which maintains
4321 * its unmodifiable nature.
4322 *
4323 * @return an UnmodifiableIterator over the elements of the underlying
4324 * collection, in any order.
4325 */
4326 public Iterator<T> iterator()
4327 {
4328 return new UnmodifiableIterator<T>(c.iterator());
4329 }
4330
4331 /**
4332 * Blocks the removal of an object from the underlying collection.
4333 * This method never returns, throwing an exception instead.
4334 *
4335 * @param o The object to remove.
4336 * @return <code>true</code> if the object was removed (i.e. the underlying
4337 * collection returned 1 or more instances of o).
4338 * @throws UnsupportedOperationException as an unmodifiable collection
4339 * does not support the <code>remove()</code> operation.
4340 */
4341 public boolean remove(Object o)
4342 {
4343 throw new UnsupportedOperationException();
4344 }
4345
4346 /**
4347 * Blocks the removal of a collection of objects from the underlying
4348 * collection. This method never returns, throwing an exception
4349 * instead.
4350 *
4351 * @param c The collection of objects to remove.
4352 * @return <code>true</code> if the collection was modified.
4353 * @throws UnsupportedOperationException as an unmodifiable collection
4354 * does not support the <code>removeAll()</code> operation.
4355 */
4356 public boolean removeAll(Collection<?> c)
4357 {
4358 throw new UnsupportedOperationException();
4359 }
4360
4361 /**
4362 * Blocks the removal of all elements from the underlying collection,
4363 * except those in the supplied collection. This method never returns,
4364 * throwing an exception instead.
4365 *
4366 * @param c The collection of objects to retain.
4367 * @return <code>true</code> if the collection was modified.
4368 * @throws UnsupportedOperationException as an unmodifiable collection
4369 * does not support the <code>retainAll()</code> operation.
4370 */
4371 public boolean retainAll(Collection<?> c)
4372 {
4373 throw new UnsupportedOperationException();
4374 }
4375
4376 /**
4377 * Retrieves the number of elements in the underlying collection.
4378 *
4379 * @return the number of elements in the collection.
4380 */
4381 public int size()
4382 {
4383 return c.size();
4384 }
4385
4386 /**
4387 * Copy the current contents of the underlying collection into an array.
4388 *
4389 * @return an array of type Object[] with a length equal to the size of the
4390 * underlying collection and containing the elements currently in
4391 * the underlying collection, in any order.
4392 */
4393 public Object[] toArray()
4394 {
4395 return c.toArray();
4396 }
4397
4398 /**
4399 * Copy the current contents of the underlying collection into an array. If
4400 * the array passed as an argument has length less than the size of the
4401 * underlying collection, an array of the same run-time type as a, with a length
4402 * equal to the size of the underlying collection, is allocated using reflection.
4403 * Otherwise, a itself is used. The elements of the underlying collection are
4404 * copied into it, and if there is space in the array, the following element is
4405 * set to null. The resultant array is returned.
4406 * Note: The fact that the following element is set to null is only useful
4407 * if it is known that this collection does not contain any null elements.
4408 *
4409 * @param a the array to copy this collection into.
4410 * @return an array containing the elements currently in the underlying
4411 * collection, in any order.
4412 * @throws ArrayStoreException if the type of any element of the
4413 * collection is not a subtype of the element type of a.
4414 */
4415 public <S> S[] toArray(S[] a)
4416 {
4417 return c.toArray(a);
4418 }
4419
4420 /**
4421 * A textual representation of the unmodifiable collection.
4422 *
4423 * @return The unmodifiable collection in the form of a <code>String</code>.
4424 */
4425 public String toString()
4426 {
4427 return c.toString();
4428 }
4429 } // class UnmodifiableCollection
4430
4431 /**
4432 * The implementation of the various iterator methods in the
4433 * unmodifiable classes.
4434 *
4435 * @author Eric Blake (ebb9@email.byu.edu)
4436 */
4437 private static class UnmodifiableIterator<T> implements Iterator<T>
4438 {
4439 /**
4440 * The wrapped iterator.
4441 */
4442 private final Iterator<? extends T> i;
4443
4444 /**
4445 * Only trusted code creates a wrapper.
4446 * @param i the wrapped iterator
4447 */
4448 UnmodifiableIterator(Iterator<? extends T> i)
4449 {
4450 this.i = i;
4451 }
4452
4453 /**
4454 * Obtains the next element in the underlying collection.
4455 *
4456 * @return the next element in the collection.
4457 * @throws NoSuchElementException if there are no more elements.
4458 */
4459 public T next()
4460 {
4461 return i.next();
4462 }
4463
4464 /**
4465 * Tests whether there are still elements to be retrieved from the
4466 * underlying collection by <code>next()</code>. When this method
4467 * returns <code>true</code>, an exception will not be thrown on calling
4468 * <code>next()</code>.
4469 *
4470 * @return <code>true</code> if there is at least one more element in the underlying
4471 * collection.
4472 */
4473 public boolean hasNext()
4474 {
4475 return i.hasNext();
4476 }
4477
4478 /**
4479 * Blocks the removal of elements from the underlying collection by the
4480 * iterator.
4481 *
4482 * @throws UnsupportedOperationException as an unmodifiable collection
4483 * does not support the removal of elements by its iterator.
4484 */
4485 public void remove()
4486 {
4487 throw new UnsupportedOperationException();
4488 }
4489 } // class UnmodifiableIterator
4490
4491 /**
4492 * Returns an unmodifiable view of the given list. This allows
4493 * "read-only" access, although changes in the backing list show up
4494 * in this view. Attempts to modify the list directly, via iterators, or
4495 * via sublists, will fail with {@link UnsupportedOperationException}.
4496 * Although this view prevents changes to the structure of the list and
4497 * its elements, the values referenced by the objects in the list can
4498 * still be modified.
4499 * <p>
4500 *
4501 * The returned List implements Serializable, but can only be serialized if
4502 * the list it wraps is likewise Serializable. In addition, if the wrapped
4503 * list implements RandomAccess, this does too.
4504 *
4505 * @param l the list to wrap
4506 * @return a read-only view of the list
4507 * @see Serializable
4508 * @see RandomAccess
4509 */
4510 public static <T> List<T> unmodifiableList(List<? extends T> l)
4511 {
4512 if (l instanceof RandomAccess)
4513 return new UnmodifiableRandomAccessList<T>(l);
4514 return new UnmodifiableList<T>(l);
4515 }
4516
4517 /**
4518 * The implementation of {@link #unmodifiableList(List)} for sequential
4519 * lists. This class name is required for compatibility with Sun's JDK
4520 * serializability.
4521 *
4522 * @author Eric Blake (ebb9@email.byu.edu)
4523 */
4524 private static class UnmodifiableList<T> extends UnmodifiableCollection<T>
4525 implements List<T>
4526 {
4527 /**
4528 * Compatible with JDK 1.4.
4529 */
4530 private static final long serialVersionUID = -283967356065247728L;
4531
4532
4533 /**
4534 * The wrapped list; stored both here and in the superclass to avoid
4535 * excessive casting. Package visible for use by subclass.
4536 * @serial the wrapped list
4537 */
4538 final List<T> list;
4539
4540 /**
4541 * Wrap a given list.
4542 * @param l the list to wrap
4543 * @throws NullPointerException if l is null
4544 */
4545 UnmodifiableList(List<? extends T> l)
4546 {
4547 super(l);
4548 list = (List<T>) l;
4549 }
4550
4551 /**
4552 * Blocks the addition of an element to the underlying
4553 * list at a specific index. This method never returns,
4554 * throwing an exception instead.
4555 *
4556 * @param index The index at which to place the new element.
4557 * @param o the object to add.
4558 * @throws UnsupportedOperationException as an unmodifiable
4559 * list doesn't support the <code>add()</code> operation.
4560 */
4561 public void add(int index, T o)
4562 {
4563 throw new UnsupportedOperationException();
4564 }
4565
4566 /**
4567 * Blocks the addition of a collection of elements to the
4568 * underlying list at a specific index. This method never
4569 * returns, throwing an exception instead.
4570 *
4571 * @param index The index at which to place the new element.
4572 * @param c the collections of objects to add.
4573 * @throws UnsupportedOperationException as an unmodifiable
4574 * list doesn't support the <code>addAll()</code> operation.
4575 */
4576 public boolean addAll(int index, Collection<? extends T> c)
4577 {
4578 throw new UnsupportedOperationException();
4579 }
4580
4581 /**
4582 * Returns <code>true</code> if the object, o, is an instance of
4583 * <code>List</code> with the same size and elements
4584 * as the underlying list.
4585 *
4586 * @param o The object to compare.
4587 * @return <code>true</code> if o is equivalent to the underlying list.
4588 */
4589 public boolean equals(Object o)
4590 {
4591 return list.equals(o);
4592 }
4593
4594 /**
4595 * Retrieves the element at a given index in the underlying list.
4596 *
4597 * @param index the index of the element to be returned
4598 * @return the element at index index in this list
4599 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
4600 */
4601 public T get(int index)
4602 {
4603 return list.get(index);
4604 }
4605
4606 /**
4607 * Computes the hash code for the underlying list.
4608 * The exact computation is described in the documentation
4609 * of the <code>List</code> interface.
4610 *
4611 * @return The hash code of the underlying list.
4612 * @see List#hashCode()
4613 */
4614 public int hashCode()
4615 {
4616 return list.hashCode();
4617 }
4618
4619 /**
4620 * Obtain the first index at which a given object is to be found in the
4621 * underlying list.
4622 *
4623 * @param o the object to search for
4624 * @return the least integer n such that <code>o == null ? get(n) == null :
4625 * o.equals(get(n))</code>, or -1 if there is no such index.
4626 * @throws ClassCastException if the type of o is not a valid
4627 * type for the underlying list.
4628 * @throws NullPointerException if o is null and the underlying
4629 * list does not support null values.
4630 */
4631 public int indexOf(Object o)
4632 {
4633 return list.indexOf(o);
4634 }
4635
4636 /**
4637 * Obtain the last index at which a given object is to be found in the
4638 * underlying list.
4639 *
4640 * @return the greatest integer n such that <code>o == null ? get(n) == null
4641 * : o.equals(get(n))</code>, or -1 if there is no such index.
4642 * @throws ClassCastException if the type of o is not a valid
4643 * type for the underlying list.
4644 * @throws NullPointerException if o is null and the underlying
4645 * list does not support null values.
4646 */
4647 public int lastIndexOf(Object o)
4648 {
4649 return list.lastIndexOf(o);
4650 }
4651
4652 /**
4653 * Obtains a list iterator over the underlying list, starting at the beginning
4654 * and maintaining the unmodifiable nature of this list.
4655 *
4656 * @return a <code>UnmodifiableListIterator</code> over the elements of the
4657 * underlying list, in order, starting at the beginning.
4658 */
4659 public ListIterator<T> listIterator()
4660 {
4661 return new UnmodifiableListIterator<T>(list.listIterator());
4662 }
4663
4664 /**
4665 * Obtains a list iterator over the underlying list, starting at the specified
4666 * index and maintaining the unmodifiable nature of this list. An initial call
4667 * to <code>next()</code> will retrieve the element at the specified index,
4668 * and an initial call to <code>previous()</code> will retrieve the element
4669 * at index - 1.
4670 *
4671 *
4672 * @param index the position, between 0 and size() inclusive, to begin the
4673 * iteration from.
4674 * @return a <code>UnmodifiableListIterator</code> over the elements of the
4675 * underlying list, in order, starting at the specified index.
4676 * @throws IndexOutOfBoundsException if index < 0 || index > size()
4677 */
4678 public ListIterator<T> listIterator(int index)
4679 {
4680 return new UnmodifiableListIterator<T>(list.listIterator(index));
4681 }
4682
4683 /**
4684 * Blocks the removal of the element at the specified index.
4685 * This method never returns, throwing an exception instead.
4686 *
4687 * @param index The index of the element to remove.
4688 * @return the removed element.
4689 * @throws UnsupportedOperationException as an unmodifiable
4690 * list does not support the <code>remove()</code>
4691 * operation.
4692 */
4693 public T remove(int index)
4694 {
4695 throw new UnsupportedOperationException();
4696 }
4697
4698 /**
4699 * Blocks the replacement of the element at the specified index.
4700 * This method never returns, throwing an exception instead.
4701 *
4702 * @param index The index of the element to replace.
4703 * @param o The new object to place at the specified index.
4704 * @return the replaced element.
4705 * @throws UnsupportedOperationException as an unmodifiable
4706 * list does not support the <code>set()</code>
4707 * operation.
4708 */
4709 public T set(int index, T o)
4710 {
4711 throw new UnsupportedOperationException();
4712 }
4713
4714 /**
4715 * Obtain a List view of a subsection of the underlying list, from
4716 * fromIndex (inclusive) to toIndex (exclusive). If the two indices
4717 * are equal, the sublist is empty. The returned list will be
4718 * unmodifiable, like this list. Changes to the elements of the
4719 * returned list will be reflected in the underlying list. No structural
4720 * modifications can take place in either list.
4721 *
4722 * @param fromIndex the index that the returned list should start from
4723 * (inclusive).
4724 * @param toIndex the index that the returned list should go to (exclusive).
4725 * @return a List backed by a subsection of the underlying list.
4726 * @throws IndexOutOfBoundsException if fromIndex < 0
4727 * || toIndex > size() || fromIndex > toIndex.
4728 */
4729 public List<T> subList(int fromIndex, int toIndex)
4730 {
4731 return unmodifiableList(list.subList(fromIndex, toIndex));
4732 }
4733 } // class UnmodifiableList
4734
4735 /**
4736 * The implementation of {@link #unmodifiableList(List)} for random-access
4737 * lists. This class name is required for compatibility with Sun's JDK
4738 * serializability.
4739 *
4740 * @author Eric Blake (ebb9@email.byu.edu)
4741 */
4742 private static final class UnmodifiableRandomAccessList<T>
4743 extends UnmodifiableList<T> implements RandomAccess
4744 {
4745 /**
4746 * Compatible with JDK 1.4.
4747 */
4748 private static final long serialVersionUID = -2542308836966382001L;
4749
4750 /**
4751 * Wrap a given list.
4752 * @param l the list to wrap
4753 * @throws NullPointerException if l is null
4754 */
4755 UnmodifiableRandomAccessList(List<? extends T> l)
4756 {
4757 super(l);
4758 }
4759 } // class UnmodifiableRandomAccessList
4760
4761 /**
4762 * The implementation of {@link UnmodifiableList#listIterator()}.
4763 *
4764 * @author Eric Blake (ebb9@email.byu.edu)
4765 */
4766 private static final class UnmodifiableListIterator<T>
4767 extends UnmodifiableIterator<T> implements ListIterator<T>
4768 {
4769 /**
4770 * The wrapped iterator, stored both here and in the superclass to
4771 * avoid excessive casting.
4772 */
4773 private final ListIterator<T> li;
4774
4775 /**
4776 * Only trusted code creates a wrapper.
4777 * @param li the wrapped iterator
4778 */
4779 UnmodifiableListIterator(ListIterator<T> li)
4780 {
4781 super(li);
4782 this.li = li;
4783 }
4784
4785 /**
4786 * Blocks the addition of an object to the list underlying this iterator.
4787 * This method never returns, throwing an exception instead.
4788 *
4789 * @param o The object to add.
4790 * @throws UnsupportedOperationException as the iterator of an unmodifiable
4791 * list does not support the <code>add()</code> operation.
4792 */
4793 public void add(T o)
4794 {
4795 throw new UnsupportedOperationException();
4796 }
4797
4798 /**
4799 * Tests whether there are still elements to be retrieved from the
4800 * underlying collection by <code>previous()</code>. When this method
4801 * returns <code>true</code>, an exception will not be thrown on calling
4802 * <code>previous()</code>.
4803 *
4804 * @return <code>true</code> if there is at least one more element prior to the
4805 * current position in the underlying list.
4806 */
4807 public boolean hasPrevious()
4808 {
4809 return li.hasPrevious();
4810 }
4811
4812 /**
4813 * Find the index of the element that would be returned by a call to next.
4814 * If <code>hasNext()</code> returns <code>false</code>, this returns the list size.
4815 *
4816 * @return the index of the element that would be returned by
4817 * <code>next()</code>.
4818 */
4819 public int nextIndex()
4820 {
4821 return li.nextIndex();
4822 }
4823
4824 /**
4825 * Obtains the previous element in the underlying list.
4826 *
4827 * @return the previous element in the list.
4828 * @throws NoSuchElementException if there are no more prior elements.
4829 */
4830 public T previous()
4831 {
4832 return li.previous();
4833 }
4834
4835 /**
4836 * Find the index of the element that would be returned by a call to
4837 * previous. If <code>hasPrevious()</code> returns <code>false</code>,
4838 * this returns -1.
4839 *
4840 * @return the index of the element that would be returned by
4841 * <code>previous()</code>.
4842 */
4843 public int previousIndex()
4844 {
4845 return li.previousIndex();
4846 }
4847
4848 /**
4849 * Blocks the replacement of an element in the list underlying this
4850 * iterator. This method never returns, throwing an exception instead.
4851 *
4852 * @param o The new object to replace the existing one.
4853 * @throws UnsupportedOperationException as the iterator of an unmodifiable
4854 * list does not support the <code>set()</code> operation.
4855 */
4856 public void set(T o)
4857 {
4858 throw new UnsupportedOperationException();
4859 }
4860 } // class UnmodifiableListIterator
4861
4862 /**
4863 * Returns an unmodifiable view of the given map. This allows "read-only"
4864 * access, although changes in the backing map show up in this view.
4865 * Attempts to modify the map directly, or via collection views or their
4866 * iterators will fail with {@link UnsupportedOperationException}.
4867 * Although this view prevents changes to the structure of the map and its
4868 * entries, the values referenced by the objects in the map can still be
4869 * modified.
4870 * <p>
4871 *
4872 * The returned Map implements Serializable, but can only be serialized if
4873 * the map it wraps is likewise Serializable.
4874 *
4875 * @param m the map to wrap
4876 * @return a read-only view of the map
4877 * @see Serializable
4878 */
4879 public static <K, V> Map<K, V> unmodifiableMap(Map<? extends K,
4880 ? extends V> m)
4881 {
4882 return new UnmodifiableMap<K, V>(m);
4883 }
4884
4885 /**
4886 * The implementation of {@link #unmodifiableMap(Map)}. This
4887 * class name is required for compatibility with Sun's JDK serializability.
4888 *
4889 * @author Eric Blake (ebb9@email.byu.edu)
4890 */
4891 private static class UnmodifiableMap<K, V> implements Map<K, V>, Serializable
4892 {
4893 /**
4894 * Compatible with JDK 1.4.
4895 */
4896 private static final long serialVersionUID = -1034234728574286014L;
4897
4898 /**
4899 * The wrapped map.
4900 * @serial the real map
4901 */
4902 private final Map<K, V> m;
4903
4904 /**
4905 * Cache the entry set.
4906 */
4907 private transient Set<Map.Entry<K, V>> entries;
4908
4909 /**
4910 * Cache the key set.
4911 */
4912 private transient Set<K> keys;
4913
4914 /**
4915 * Cache the value collection.
4916 */
4917 private transient Collection<V> values;
4918
4919 /**
4920 * Wrap a given map.
4921 * @param m the map to wrap
4922 * @throws NullPointerException if m is null
4923 */
4924 UnmodifiableMap(Map<? extends K, ? extends V> m)
4925 {
4926 this.m = (Map<K,V>) m;
4927 if (m == null)
4928 throw new NullPointerException();
4929 }
4930
4931 /**
4932 * Blocks the clearing of entries from the underlying map.
4933 * This method never returns, throwing an exception instead.
4934 *
4935 * @throws UnsupportedOperationException as an unmodifiable
4936 * map does not support the <code>clear()</code> operation.
4937 */
4938 public void clear()
4939 {
4940 throw new UnsupportedOperationException();
4941 }
4942
4943 /**
4944 * Returns <code>true</code> if the underlying map contains a mapping for
4945 * the given key.
4946 *
4947 * @param key the key to search for
4948 * @return <code>true</code> if the map contains the key
4949 * @throws ClassCastException if the key is of an inappropriate type
4950 * @throws NullPointerException if key is <code>null</code> but the map
4951 * does not permit null keys
4952 */
4953 public boolean containsKey(Object key)
4954 {
4955 return m.containsKey(key);
4956 }
4957
4958 /**
4959 * Returns <code>true</code> if the underlying map contains at least one mapping with
4960 * the given value. In other words, it returns <code>true</code> if a value v exists where
4961 * <code>(value == null ? v == null : value.equals(v))</code>. This usually
4962 * requires linear time.
4963 *
4964 * @param value the value to search for
4965 * @return <code>true</code> if the map contains the value
4966 * @throws ClassCastException if the type of the value is not a valid type
4967 * for this map.
4968 * @throws NullPointerException if the value is null and the map doesn't
4969 * support null values.
4970 */
4971 public boolean containsValue(Object value)
4972 {
4973 return m.containsValue(value);
4974 }
4975
4976 /**
4977 * Returns a unmodifiable set view of the entries in the underlying map.
4978 * Each element in the set is a unmodifiable variant of <code>Map.Entry</code>.
4979 * The set is backed by the map, so that changes in one show up in the other.
4980 * Modifications made while an iterator is in progress cause undefined
4981 * behavior. These modifications are again limited to the values of
4982 * the objects.
4983 *
4984 * @return the unmodifiable set view of all mapping entries.
4985 * @see Map.Entry
4986 */
4987 public Set<Map.Entry<K, V>> entrySet()
4988 {
4989 if (entries == null)
4990 entries = new UnmodifiableEntrySet<K,V>(m.entrySet());
4991 return entries;
4992 }
4993
4994 /**
4995 * The implementation of {@link UnmodifiableMap#entrySet()}. This class
4996 * name is required for compatibility with Sun's JDK serializability.
4997 *
4998 * @author Eric Blake (ebb9@email.byu.edu)
4999 */
5000 private static final class UnmodifiableEntrySet<K,V>
5001 extends UnmodifiableSet<Map.Entry<K,V>>
5002 implements Serializable
5003 {
5004 // Unmodifiable implementation of Map.Entry used as return value for
5005 // UnmodifiableEntrySet accessors (iterator, toArray, toArray(Object[]))
5006 private static final class UnmodifiableMapEntry<K,V>
5007 implements Map.Entry<K,V>
5008 {
5009 private final Map.Entry<K,V> e;
5010
5011 private UnmodifiableMapEntry(Map.Entry<K,V> e)
5012 {
5013 super();
5014 this.e = e;
5015 }
5016
5017 /**
5018 * Returns <code>true</code> if the object, o, is also a map entry
5019 * with an identical key and value.
5020 *
5021 * @param o the object to compare.
5022 * @return <code>true</code> if o is an equivalent map entry.
5023 */
5024 public boolean equals(Object o)
5025 {
5026 return e.equals(o);
5027 }
5028
5029 /**
5030 * Returns the key of this map entry.
5031 *
5032 * @return the key.
5033 */
5034 public K getKey()
5035 {
5036 return e.getKey();
5037 }
5038
5039 /**
5040 * Returns the value of this map entry.
5041 *
5042 * @return the value.
5043 */
5044 public V getValue()
5045 {
5046 return e.getValue();
5047 }
5048
5049 /**
5050 * Computes the hash code of this map entry. The computation is
5051 * described in the <code>Map</code> interface documentation.
5052 *
5053 * @return the hash code of this entry.
5054 * @see Map#hashCode()
5055 */
5056 public int hashCode()
5057 {
5058 return e.hashCode();
5059 }
5060
5061 /**
5062 * Blocks the alteration of the value of this map entry. This method
5063 * never returns, throwing an exception instead.
5064 *
5065 * @param value The new value.
5066 * @throws UnsupportedOperationException as an unmodifiable map entry
5067 * does not support the <code>setValue()</code> operation.
5068 */
5069 public V setValue(V value)
5070 {
5071 throw new UnsupportedOperationException();
5072 }
5073
5074 /**
5075 * Returns a textual representation of the map entry.
5076 *
5077 * @return The map entry as a <code>String</code>.
5078 */
5079 public String toString()
5080 {
5081 return e.toString();
5082 }
5083 }
5084
5085 /**
5086 * Compatible with JDK 1.4.
5087 */
5088 private static final long serialVersionUID = 7854390611657943733L;
5089
5090 /**
5091 * Wrap a given set.
5092 * @param s the set to wrap
5093 */
5094 UnmodifiableEntrySet(Set<Map.Entry<K,V>> s)
5095 {
5096 super(s);
5097 }
5098
5099 // The iterator must return unmodifiable map entries.
5100 public Iterator<Map.Entry<K,V>> iterator()
5101 {
5102 return new UnmodifiableIterator<Map.Entry<K,V>>(c.iterator())
5103 {
5104 /**
5105 * Obtains the next element from the underlying set of
5106 * map entries.
5107 *
5108 * @return the next element in the collection.
5109 * @throws NoSuchElementException if there are no more elements.
5110 */
5111 public Map.Entry<K,V> next()
5112 {
5113 final Map.Entry<K,V> e = super.next();
5114 return new UnmodifiableMapEntry<K,V>(e);
5115 }
5116 };
5117 }
5118
5119 // The array returned is an array of UnmodifiableMapEntry instead of
5120 // Map.Entry
5121 public Object[] toArray()
5122 {
5123 Object[] mapEntryResult = super.toArray();
5124 UnmodifiableMapEntry<K,V> result[] = null;
5125
5126 if (mapEntryResult != null)
5127 {
5128 result = (UnmodifiableMapEntry<K,V>[])
5129 new UnmodifiableMapEntry[mapEntryResult.length];
5130 for (int i = 0; i < mapEntryResult.length; ++i)
5131 result[i] = new UnmodifiableMapEntry<K,V>((Map.Entry<K,V>)mapEntryResult[i]);
5132 }
5133 return result;
5134 }
5135
5136 // The array returned is an array of UnmodifiableMapEntry instead of
5137 // Map.Entry
5138 public <S> S[] toArray(S[] array)
5139 {
5140 S[] result = super.toArray(array);
5141
5142 if (result != null)
5143 for (int i = 0; i < result.length; i++)
5144 array[i] =
5145 (S) new UnmodifiableMapEntry<K,V>((Map.Entry<K,V>) result[i]);
5146 return array;
5147 }
5148
5149
5150 } // class UnmodifiableEntrySet
5151
5152 /**
5153 * Returns <code>true</code> if the object, o, is also an instance
5154 * of <code>Map</code> with an equal set of map entries.
5155 *
5156 * @param o The object to compare.
5157 * @return <code>true</code> if o is an equivalent map.
5158 */
5159 public boolean equals(Object o)
5160 {
5161 return m.equals(o);
5162 }
5163
5164 /**
5165 * Returns the value associated with the supplied key or
5166 * null if no such mapping exists. An ambiguity can occur
5167 * if null values are accepted by the underlying map.
5168 * In this case, <code>containsKey()</code> can be used
5169 * to separate the two possible cases of a null result.
5170 *
5171 * @param key The key to look up.
5172 * @return the value associated with the key, or null if key not in map.
5173 * @throws ClassCastException if the key is an inappropriate type.
5174 * @throws NullPointerException if this map does not accept null keys.
5175 * @see #containsKey(Object)
5176 */
5177 public V get(Object key)
5178 {
5179 return m.get(key);
5180 }
5181
5182 /**
5183 * Blocks the addition of a new entry to the underlying map.
5184 * This method never returns, throwing an exception instead.
5185 *
5186 * @param key The new key.
5187 * @param value The new value.
5188 * @return the previous value of the key, or null if there was no mapping.
5189 * @throws UnsupportedOperationException as an unmodifiable
5190 * map does not support the <code>put()</code> operation.
5191 */
5192 public V put(K key, V value)
5193 {
5194 throw new UnsupportedOperationException();
5195 }
5196
5197 /**
5198 * Computes the hash code for the underlying map, as the sum
5199 * of the hash codes of all entries.
5200 *
5201 * @return The hash code of the underlying map.
5202 * @see Map.Entry#hashCode()
5203 */
5204 public int hashCode()
5205 {
5206 return m.hashCode();
5207 }
5208
5209 /**
5210 * Returns <code>true</code> if the underlying map contains no entries.
5211 *
5212 * @return <code>true</code> if the map is empty.
5213 */
5214 public boolean isEmpty()
5215 {
5216 return m.isEmpty();
5217 }
5218
5219 /**
5220 * Returns a unmodifiable set view of the keys in the underlying map.
5221 * The set is backed by the map, so that changes in one show up in the other.
5222 * Modifications made while an iterator is in progress cause undefined
5223 * behavior. These modifications are again limited to the values of
5224 * the keys.
5225 *
5226 * @return the set view of all keys.
5227 */
5228 public Set<K> keySet()
5229 {
5230 if (keys == null)
5231 keys = new UnmodifiableSet<K>(m.keySet());
5232 return keys;
5233 }
5234
5235 /**
5236 * Blocks the addition of the entries in the supplied map.
5237 * This method never returns, throwing an exception instead.
5238 *
5239 * @param m The map, the entries of which should be added
5240 * to the underlying map.
5241 * @throws UnsupportedOperationException as an unmodifiable
5242 * map does not support the <code>putAll</code> operation.
5243 */
5244 public void putAll(Map<? extends K, ? extends V> m)
5245 {
5246 throw new UnsupportedOperationException();
5247 }
5248
5249 /**
5250 * Blocks the removal of an entry from the map.
5251 * This method never returns, throwing an exception instead.
5252 *
5253 * @param o The key of the entry to remove.
5254 * @return The value the key was associated with, or null
5255 * if no such mapping existed. Null is also returned
5256 * if the removed entry had a null key.
5257 * @throws UnsupportedOperationException as an unmodifiable
5258 * map does not support the <code>remove</code> operation.
5259 */
5260 public V remove(Object o)
5261 {
5262 throw new UnsupportedOperationException();
5263 }
5264
5265
5266 /**
5267 * Returns the number of key-value mappings in the underlying map.
5268 * If there are more than Integer.MAX_VALUE mappings, Integer.MAX_VALUE
5269 * is returned.
5270 *
5271 * @return the number of mappings.
5272 */
5273 public int size()
5274 {
5275 return m.size();
5276 }
5277
5278 /**
5279 * Returns a textual representation of the map.
5280 *
5281 * @return The map in the form of a <code>String</code>.
5282 */
5283 public String toString()
5284 {
5285 return m.toString();
5286 }
5287
5288 /**
5289 * Returns a unmodifiable collection view of the values in the underlying map.
5290 * The collection is backed by the map, so that changes in one show up in the other.
5291 * Modifications made while an iterator is in progress cause undefined
5292 * behavior. These modifications are again limited to the values of
5293 * the keys.
5294 *
5295 * @return the collection view of all values.
5296 */
5297 public Collection<V> values()
5298 {
5299 if (values == null)
5300 values = new UnmodifiableCollection<V>(m.values());
5301 return values;
5302 }
5303 } // class UnmodifiableMap
5304
5305 /**
5306 * Returns an unmodifiable view of the given set. This allows
5307 * "read-only" access, although changes in the backing set show up
5308 * in this view. Attempts to modify the set directly or via iterators
5309 * will fail with {@link UnsupportedOperationException}.
5310 * Although this view prevents changes to the structure of the set and its
5311 * entries, the values referenced by the objects in the set can still be
5312 * modified.
5313 * <p>
5314 *
5315 * The returned Set implements Serializable, but can only be serialized if
5316 * the set it wraps is likewise Serializable.
5317 *
5318 * @param s the set to wrap
5319 * @return a read-only view of the set
5320 * @see Serializable
5321 */
5322 public static <T> Set<T> unmodifiableSet(Set<? extends T> s)
5323 {
5324 return new UnmodifiableSet<T>(s);
5325 }
5326
5327 /**
5328 * The implementation of {@link #unmodifiableSet(Set)}. This class
5329 * name is required for compatibility with Sun's JDK serializability.
5330 *
5331 * @author Eric Blake (ebb9@email.byu.edu)
5332 */
5333 private static class UnmodifiableSet<T> extends UnmodifiableCollection<T>
5334 implements Set<T>
5335 {
5336 /**
5337 * Compatible with JDK 1.4.
5338 */
5339 private static final long serialVersionUID = -9215047833775013803L;
5340
5341 /**
5342 * Wrap a given set.
5343 * @param s the set to wrap
5344 * @throws NullPointerException if s is null
5345 */
5346 UnmodifiableSet(Set<? extends T> s)
5347 {
5348 super(s);
5349 }
5350
5351 /**
5352 * Returns <code>true</code> if the object, o, is also an instance of
5353 * <code>Set</code> of the same size and with the same entries.
5354 *
5355 * @return <code>true</code> if o is an equivalent set.
5356 */
5357 public boolean equals(Object o)
5358 {
5359 return c.equals(o);
5360 }
5361
5362 /**
5363 * Computes the hash code of this set, as the sum of the
5364 * hash codes of all elements within the set.
5365 *
5366 * @return the hash code of the set.
5367 */
5368 public int hashCode()
5369 {
5370 return c.hashCode();
5371 }
5372 } // class UnmodifiableSet
5373
5374 /**
5375 * Returns an unmodifiable view of the given sorted map. This allows
5376 * "read-only" access, although changes in the backing map show up in this
5377 * view. Attempts to modify the map directly, via subviews, via collection
5378 * views, or iterators, will fail with {@link UnsupportedOperationException}.
5379 * Although this view prevents changes to the structure of the map and its
5380 * entries, the values referenced by the objects in the map can still be
5381 * modified.
5382 * <p>
5383 *
5384 * The returned SortedMap implements Serializable, but can only be
5385 * serialized if the map it wraps is likewise Serializable.
5386 *
5387 * @param m the map to wrap
5388 * @return a read-only view of the map
5389 * @see Serializable
5390 */
5391 public static <K, V> SortedMap<K, V> unmodifiableSortedMap(SortedMap<K,
5392 ? extends V> m)
5393 {
5394 return new UnmodifiableSortedMap<K, V>(m);
5395 }
5396
5397 /**
5398 * The implementation of {@link #unmodifiableSortedMap(SortedMap)}. This
5399 * class name is required for compatibility with Sun's JDK serializability.
5400 *
5401 * @author Eric Blake (ebb9@email.byu.edu)
5402 */
5403 private static class UnmodifiableSortedMap<K, V>
5404 extends UnmodifiableMap<K, V>
5405 implements SortedMap<K, V>
5406 {
5407 /**
5408 * Compatible with JDK 1.4.
5409 */
5410 private static final long serialVersionUID = -8806743815996713206L;
5411
5412 /**
5413 * The wrapped map; stored both here and in the superclass to avoid
5414 * excessive casting.
5415 * @serial the wrapped map
5416 */
5417 private final SortedMap<K, V> sm;
5418
5419 /**
5420 * Wrap a given map.
5421 * @param sm the map to wrap
5422 * @throws NullPointerException if sm is null
5423 */
5424 UnmodifiableSortedMap(SortedMap<K, ? extends V> sm)
5425 {
5426 super(sm);
5427 this.sm = (SortedMap<K,V>) sm;
5428 }
5429
5430 /**
5431 * Returns the comparator used in sorting the underlying map,
5432 * or null if it is the keys' natural ordering.
5433 *
5434 * @return the sorting comparator.
5435 */
5436 public Comparator<? super K> comparator()
5437 {
5438 return sm.comparator();
5439 }
5440
5441 /**
5442 * Returns the first (lowest sorted) key in the map.
5443 *
5444 * @return the first key.
5445 * @throws NoSuchElementException if this map is empty.
5446 */
5447 public K firstKey()
5448 {
5449 return sm.firstKey();
5450 }
5451
5452 /**
5453 * Returns a unmodifiable view of the portion of the map strictly less
5454 * than toKey. The view is backed by the underlying map, so changes in
5455 * one show up in the other. The submap supports all optional operations
5456 * of the original. This operation is equivalent to
5457 * <code>subMap(firstKey(), toKey)</code>.
5458 * <p>
5459 *
5460 * The returned map throws an IllegalArgumentException any time a key is
5461 * used which is out of the range of toKey. Note that the endpoint, toKey,
5462 * is not included; if you want this value to be included, pass its successor
5463 * object in to toKey. For example, for Integers, you could request
5464 * <code>headMap(new Integer(limit.intValue() + 1))</code>.
5465 *
5466 * @param toKey the exclusive upper range of the submap.
5467 * @return the submap.
5468 * @throws ClassCastException if toKey is not comparable to the map contents.
5469 * @throws IllegalArgumentException if this is a subMap, and toKey is out
5470 * of range.
5471 * @throws NullPointerException if toKey is null but the map does not allow
5472 * null keys.
5473 */
5474 public SortedMap<K, V> headMap(K toKey)
5475 {
5476 return new UnmodifiableSortedMap<K, V>(sm.headMap(toKey));
5477 }
5478
5479 /**
5480 * Returns the last (highest sorted) key in the map.
5481 *
5482 * @return the last key.
5483 * @throws NoSuchElementException if this map is empty.
5484 */
5485 public K lastKey()
5486 {
5487 return sm.lastKey();
5488 }
5489
5490 /**
5491 * Returns a unmodifiable view of the portion of the map greater than or
5492 * equal to fromKey, and strictly less than toKey. The view is backed by
5493 * the underlying map, so changes in one show up in the other. The submap
5494 * supports all optional operations of the original.
5495 * <p>
5496 *
5497 * The returned map throws an IllegalArgumentException any time a key is
5498 * used which is out of the range of fromKey and toKey. Note that the
5499 * lower endpoint is included, but the upper is not; if you want to
5500 * change the inclusion or exclusion of an endpoint, pass its successor
5501 * object in instead. For example, for Integers, you could request
5502 * <code>subMap(new Integer(lowlimit.intValue() + 1),
5503 * new Integer(highlimit.intValue() + 1))</code> to reverse
5504 * the inclusiveness of both endpoints.
5505 *
5506 * @param fromKey the inclusive lower range of the submap.
5507 * @param toKey the exclusive upper range of the submap.
5508 * @return the submap.
5509 * @throws ClassCastException if fromKey or toKey is not comparable to
5510 * the map contents.
5511 * @throws IllegalArgumentException if this is a subMap, and fromKey or
5512 * toKey is out of range.
5513 * @throws NullPointerException if fromKey or toKey is null but the map
5514 * does not allow null keys.
5515 */
5516 public SortedMap<K, V> subMap(K fromKey, K toKey)
5517 {
5518 return new UnmodifiableSortedMap<K, V>(sm.subMap(fromKey, toKey));
5519 }
5520
5521 /**
5522 * Returns a unmodifiable view of the portion of the map greater than or
5523 * equal to fromKey. The view is backed by the underlying map, so changes
5524 * in one show up in the other. The submap supports all optional operations
5525 * of the original.
5526 * <p>
5527 *
5528 * The returned map throws an IllegalArgumentException any time a key is
5529 * used which is out of the range of fromKey. Note that the endpoint, fromKey, is
5530 * included; if you do not want this value to be included, pass its successor object in
5531 * to fromKey. For example, for Integers, you could request
5532 * <code>tailMap(new Integer(limit.intValue() + 1))</code>.
5533 *
5534 * @param fromKey the inclusive lower range of the submap
5535 * @return the submap
5536 * @throws ClassCastException if fromKey is not comparable to the map
5537 * contents
5538 * @throws IllegalArgumentException if this is a subMap, and fromKey is out
5539 * of range
5540 * @throws NullPointerException if fromKey is null but the map does not allow
5541 * null keys
5542 */
5543 public SortedMap<K, V> tailMap(K fromKey)
5544 {
5545 return new UnmodifiableSortedMap<K, V>(sm.tailMap(fromKey));
5546 }
5547 } // class UnmodifiableSortedMap
5548
5549 /**
5550 * Returns an unmodifiable view of the given sorted set. This allows
5551 * "read-only" access, although changes in the backing set show up
5552 * in this view. Attempts to modify the set directly, via subsets, or via
5553 * iterators, will fail with {@link UnsupportedOperationException}.
5554 * Although this view prevents changes to the structure of the set and its
5555 * entries, the values referenced by the objects in the set can still be
5556 * modified.
5557 * <p>
5558 *
5559 * The returns SortedSet implements Serializable, but can only be
5560 * serialized if the set it wraps is likewise Serializable.
5561 *
5562 * @param s the set to wrap
5563 * @return a read-only view of the set
5564 * @see Serializable
5565 */
5566 public static <T> SortedSet<T> unmodifiableSortedSet(SortedSet<T> s)
5567 {
5568 return new UnmodifiableSortedSet<T>(s);
5569 }
5570
5571 /**
5572 * The implementation of {@link #synchronizedSortedMap(SortedMap)}. This
5573 * class name is required for compatibility with Sun's JDK serializability.
5574 *
5575 * @author Eric Blake (ebb9@email.byu.edu)
5576 */
5577 private static class UnmodifiableSortedSet<T> extends UnmodifiableSet<T>
5578 implements SortedSet<T>
5579 {
5580 /**
5581 * Compatible with JDK 1.4.
5582 */
5583 private static final long serialVersionUID = -4929149591599911165L;
5584
5585 /**
5586 * The wrapped set; stored both here and in the superclass to avoid
5587 * excessive casting.
5588 * @serial the wrapped set
5589 */
5590 private SortedSet<T> ss;
5591
5592 /**
5593 * Wrap a given set.
5594 * @param ss the set to wrap
5595 * @throws NullPointerException if ss is null
5596 */
5597 UnmodifiableSortedSet(SortedSet<T> ss)
5598 {
5599 super(ss);
5600 this.ss = ss;
5601 }
5602
5603 /**
5604 * Returns the comparator used in sorting the underlying set,
5605 * or null if it is the elements' natural ordering.
5606 *
5607 * @return the sorting comparator
5608 */
5609 public Comparator<? super T> comparator()
5610 {
5611 return ss.comparator();
5612 }
5613
5614 /**
5615 * Returns the first (lowest sorted) element in the underlying
5616 * set.
5617 *
5618 * @return the first element.
5619 * @throws NoSuchElementException if the set is empty.
5620 */
5621 public T first()
5622 {
5623 return ss.first();
5624 }
5625
5626 /**
5627 * Returns a unmodifiable view of the portion of the set strictly
5628 * less than toElement. The view is backed by the underlying set,
5629 * so changes in one show up in the other. The subset supports
5630 * all optional operations of the original. This operation
5631 * is equivalent to <code>subSet(first(), toElement)</code>.
5632 * <p>
5633 *
5634 * The returned set throws an IllegalArgumentException any time an element is
5635 * used which is out of the range of toElement. Note that the endpoint, toElement,
5636 * is not included; if you want this value included, pass its successor object in to
5637 * toElement. For example, for Integers, you could request
5638 * <code>headSet(new Integer(limit.intValue() + 1))</code>.
5639 *
5640 * @param toElement the exclusive upper range of the subset
5641 * @return the subset.
5642 * @throws ClassCastException if toElement is not comparable to the set
5643 * contents.
5644 * @throws IllegalArgumentException if this is a subSet, and toElement is out
5645 * of range.
5646 * @throws NullPointerException if toElement is null but the set does not
5647 * allow null elements.
5648 */
5649 public SortedSet<T> headSet(T toElement)
5650 {
5651 return new UnmodifiableSortedSet<T>(ss.headSet(toElement));
5652 }
5653
5654 /**
5655 * Returns the last (highest sorted) element in the underlying
5656 * set.
5657 *
5658 * @return the last element.
5659 * @throws NoSuchElementException if the set is empty.
5660 */
5661 public T last()
5662 {
5663 return ss.last();
5664 }
5665
5666 /**
5667 * Returns a unmodifiable view of the portion of the set greater than or
5668 * equal to fromElement, and strictly less than toElement. The view is backed by
5669 * the underlying set, so changes in one show up in the other. The subset
5670 * supports all optional operations of the original.
5671 * <p>
5672 *
5673 * The returned set throws an IllegalArgumentException any time an element is
5674 * used which is out of the range of fromElement and toElement. Note that the
5675 * lower endpoint is included, but the upper is not; if you want to
5676 * change the inclusion or exclusion of an endpoint, pass its successor
5677 * object in instead. For example, for Integers, you can request
5678 * <code>subSet(new Integer(lowlimit.intValue() + 1),
5679 * new Integer(highlimit.intValue() + 1))</code> to reverse
5680 * the inclusiveness of both endpoints.
5681 *
5682 * @param fromElement the inclusive lower range of the subset.
5683 * @param toElement the exclusive upper range of the subset.
5684 * @return the subset.
5685 * @throws ClassCastException if fromElement or toElement is not comparable
5686 * to the set contents.
5687 * @throws IllegalArgumentException if this is a subSet, and fromElement or
5688 * toElement is out of range.
5689 * @throws NullPointerException if fromElement or toElement is null but the
5690 * set does not allow null elements.
5691 */
5692 public SortedSet<T> subSet(T fromElement, T toElement)
5693 {
5694 return new UnmodifiableSortedSet<T>(ss.subSet(fromElement, toElement));
5695 }
5696
5697 /**
5698 * Returns a unmodifiable view of the portion of the set greater than or equal to
5699 * fromElement. The view is backed by the underlying set, so changes in one show up
5700 * in the other. The subset supports all optional operations of the original.
5701 * <p>
5702 *
5703 * The returned set throws an IllegalArgumentException any time an element is
5704 * used which is out of the range of fromElement. Note that the endpoint,
5705 * fromElement, is included; if you do not want this value to be included, pass its
5706 * successor object in to fromElement. For example, for Integers, you could request
5707 * <code>tailSet(new Integer(limit.intValue() + 1))</code>.
5708 *
5709 * @param fromElement the inclusive lower range of the subset
5710 * @return the subset.
5711 * @throws ClassCastException if fromElement is not comparable to the set
5712 * contents.
5713 * @throws IllegalArgumentException if this is a subSet, and fromElement is
5714 * out of range.
5715 * @throws NullPointerException if fromElement is null but the set does not
5716 * allow null elements.
5717 */
5718 public SortedSet<T> tailSet(T fromElement)
5719 {
5720 return new UnmodifiableSortedSet<T>(ss.tailSet(fromElement));
5721 }
5722 } // class UnmodifiableSortedSet
5723
5724 /**
5725 * <p>
5726 * Returns a dynamically typesafe view of the given collection,
5727 * where any modification is first checked to ensure that the type
5728 * of the new data is appropriate. Although the addition of
5729 * generics and parametrically-typed collections prevents an
5730 * incorrect type of element being added to a collection at
5731 * compile-time, via static type checking, this can be overridden by
5732 * casting. In contrast, wrapping the collection within a
5733 * dynamically-typesafe wrapper, using this and associated methods,
5734 * <emph>guarantees</emph> that the collection will only contain
5735 * elements of an appropriate type (provided it only contains such
5736 * at the type of wrapping, and all subsequent access is via the
5737 * wrapper). This can be useful for debugging the cause of a
5738 * <code>ClassCastException</code> caused by erroneous casting, or
5739 * for protecting collections from corruption by external libraries.
5740 * </p>
5741 * <p>
5742 * Since the collection might be a List or a Set, and those
5743 * have incompatible equals and hashCode requirements, this relies
5744 * on Object's implementation rather than passing those calls on to
5745 * the wrapped collection. The returned Collection implements
5746 * Serializable, but can only be serialized if the collection it
5747 * wraps is likewise Serializable.
5748 * </p>
5749 *
5750 * @param c the collection to wrap in a dynamically typesafe wrapper
5751 * @param type the type of elements the collection should hold.
5752 * @return a dynamically typesafe view of the collection.
5753 * @see Serializable
5754 * @since 1.5
5755 */
5756 public static <E> Collection<E> checkedCollection(Collection<E> c,
5757 Class<E> type)
5758 {
5759 return new CheckedCollection<E>(c, type);
5760 }
5761
5762 /**
5763 * The implementation of {@link #checkedCollection(Collection,Class)}. This
5764 * class name is required for compatibility with Sun's JDK serializability.
5765 *
5766 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
5767 * @since 1.5
5768 */
5769 private static class CheckedCollection<E>
5770 implements Collection<E>, Serializable
5771 {
5772 /**
5773 * Compatible with JDK 1.5.
5774 */
5775 private static final long serialVersionUID = 1578914078182001775L;
5776
5777 /**
5778 * The wrapped collection. Package visible for use by subclasses.
5779 * @serial the real collection
5780 */
5781 final Collection<E> c;
5782
5783 /**
5784 * The type of the elements of this collection.
5785 * @serial the element type.
5786 */
5787 final Class<E> type;
5788
5789 /**
5790 * Wrap a given collection.
5791 * @param c the collection to wrap
5792 * @param type the type to wrap
5793 * @throws NullPointerException if c is null
5794 */
5795 CheckedCollection(Collection<E> c, Class<E> type)
5796 {
5797 this.c = c;
5798 this.type = type;
5799 if (c == null)
5800 throw new NullPointerException();
5801 }
5802
5803 /**
5804 * Adds the supplied object to the collection, on the condition that
5805 * it is of the correct type.
5806 *
5807 * @param o the object to add.
5808 * @return <code>true</code> if the collection was modified as a result
5809 * of this action.
5810 * @throws ClassCastException if the object is not of the correct type.
5811 */
5812 public boolean add(E o)
5813 {
5814 if (type.isInstance(o))
5815 return c.add(o);
5816 else
5817 throw new ClassCastException("The element is of the incorrect type.");
5818 }
5819
5820 /**
5821 * Adds the elements of the specified collection to the backing collection,
5822 * provided they are all of the correct type.
5823 *
5824 * @param coll the collection to add.
5825 * @return <code>true</code> if the collection was modified as a result
5826 * of this action.
5827 * @throws ClassCastException if <code>c</code> contained elements of an
5828 * incorrect type.
5829 */
5830 public boolean addAll(Collection<? extends E> coll)
5831 {
5832 Collection<E> typedColl = (Collection<E>) c;
5833 final Iterator<E> it = typedColl.iterator();
5834 while (it.hasNext())
5835 {
5836 final E element = it.next();
5837 if (!type.isInstance(element))
5838 throw new ClassCastException("A member of the collection is not of the correct type.");
5839 }
5840 return c.addAll(typedColl);
5841 }
5842
5843 /**
5844 * Removes all elements from the underlying collection.
5845 */
5846 public void clear()
5847 {
5848 c.clear();
5849 }
5850
5851 /**
5852 * Test whether the underlying collection contains a given object as one
5853 * of its elements.
5854 *
5855 * @param o the element to look for.
5856 * @return <code>true</code> if the underlying collection contains at least
5857 * one element e such that
5858 * <code>o == null ? e == null : o.equals(e)</code>.
5859 * @throws ClassCastException if the type of o is not a valid type for the
5860 * underlying collection.
5861 * @throws NullPointerException if o is null and the underlying collection
5862 * doesn't support null values.
5863 */
5864 public boolean contains(Object o)
5865 {
5866 return c.contains(o);
5867 }
5868
5869 /**
5870 * Test whether the underlying collection contains every element in a given
5871 * collection.
5872 *
5873 * @param coll the collection to test for.
5874 * @return <code>true</code> if for every element o in c, contains(o) would
5875 * return <code>true</code>.
5876 * @throws ClassCastException if the type of any element in c is not a
5877 * valid type for the underlying collection.
5878 * @throws NullPointerException if some element of c is null and the
5879 * underlying collection does not support
5880 * null values.
5881 * @throws NullPointerException if c itself is null.
5882 */
5883 public boolean containsAll(Collection<?> coll)
5884 {
5885 return c.containsAll(coll);
5886 }
5887
5888 /**
5889 * Tests whether the underlying collection is empty, that is,
5890 * if size() == 0.
5891 *
5892 * @return <code>true</code> if this collection contains no elements.
5893 */
5894 public boolean isEmpty()
5895 {
5896 return c.isEmpty();
5897 }
5898
5899 /**
5900 * Obtain an Iterator over the underlying collection, which maintains
5901 * its checked nature.
5902 *
5903 * @return a Iterator over the elements of the underlying
5904 * collection, in any order.
5905 */
5906 public Iterator<E> iterator()
5907 {
5908 return new CheckedIterator<E>(c.iterator(), type);
5909 }
5910
5911 /**
5912 * Removes the supplied object from the collection, if it exists.
5913 *
5914 * @param o The object to remove.
5915 * @return <code>true</code> if the object was removed (i.e. the underlying
5916 * collection returned 1 or more instances of o).
5917 */
5918 public boolean remove(Object o)
5919 {
5920 return c.remove(o);
5921 }
5922
5923 /**
5924 * Removes all objects in the supplied collection from the backing
5925 * collection, if they exist within it.
5926 *
5927 * @param coll the collection of objects to remove.
5928 * @return <code>true</code> if the collection was modified.
5929 */
5930 public boolean removeAll(Collection<?> coll)
5931 {
5932 return c.removeAll(coll);
5933 }
5934
5935 /**
5936 * Retains all objects specified by the supplied collection which exist
5937 * within the backing collection, and removes all others.
5938 *
5939 * @param coll the collection of objects to retain.
5940 * @return <code>true</code> if the collection was modified.
5941 */
5942 public boolean retainAll(Collection<?> coll)
5943 {
5944 return c.retainAll(coll);
5945 }
5946
5947 /**
5948 * Retrieves the number of elements in the underlying collection.
5949 *
5950 * @return the number of elements in the collection.
5951 */
5952 public int size()
5953 {
5954 return c.size();
5955 }
5956
5957 /**
5958 * Copy the current contents of the underlying collection into an array.
5959 *
5960 * @return an array of type Object[] with a length equal to the size of the
5961 * underlying collection and containing the elements currently in
5962 * the underlying collection, in any order.
5963 */
5964 public Object[] toArray()
5965 {
5966 return c.toArray();
5967 }
5968
5969 /**
5970 * <p>
5971 * Copy the current contents of the underlying collection into an array. If
5972 * the array passed as an argument has length less than the size of the
5973 * underlying collection, an array of the same run-time type as a, with a
5974 * length equal to the size of the underlying collection, is allocated
5975 * using reflection.
5976 * </p>
5977 * <p>
5978 * Otherwise, a itself is used. The elements of the underlying collection
5979 * are copied into it, and if there is space in the array, the following
5980 * element is set to null. The resultant array is returned.
5981 * </p>
5982 * <p>
5983 * <emph>Note</emph>: The fact that the following element is set to null
5984 * is only useful if it is known that this collection does not contain
5985 * any null elements.
5986 *
5987 * @param a the array to copy this collection into.
5988 * @return an array containing the elements currently in the underlying
5989 * collection, in any order.
5990 * @throws ArrayStoreException if the type of any element of the
5991 * collection is not a subtype of the element type of a.
5992 */
5993 public <S> S[] toArray(S[] a)
5994 {
5995 return c.toArray(a);
5996 }
5997
5998 /**
5999 * A textual representation of the unmodifiable collection.
6000 *
6001 * @return The checked collection in the form of a <code>String</code>.
6002 */
6003 public String toString()
6004 {
6005 return c.toString();
6006 }
6007 } // class CheckedCollection
6008
6009 /**
6010 * The implementation of the various iterator methods in the
6011 * checked classes.
6012 *
6013 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
6014 * @since 1.5
6015 */
6016 private static class CheckedIterator<E>
6017 implements Iterator<E>
6018 {
6019 /**
6020 * The wrapped iterator.
6021 */
6022 private final Iterator<E> i;
6023
6024 /**
6025 * The type of the elements of this collection.
6026 * @serial the element type.
6027 */
6028 final Class<E> type;
6029
6030 /**
6031 * Only trusted code creates a wrapper.
6032 * @param i the wrapped iterator
6033 * @param type the type of the elements within the checked list.
6034 */
6035 CheckedIterator(Iterator<E> i, Class<E> type)
6036 {
6037 this.i = i;
6038 this.type = type;
6039 }
6040
6041 /**
6042 * Obtains the next element in the underlying collection.
6043 *
6044 * @return the next element in the collection.
6045 * @throws NoSuchElementException if there are no more elements.
6046 */
6047 public E next()
6048 {
6049 return i.next();
6050 }
6051
6052 /**
6053 * Tests whether there are still elements to be retrieved from the
6054 * underlying collection by <code>next()</code>. When this method
6055 * returns <code>true</code>, an exception will not be thrown on calling
6056 * <code>next()</code>.
6057 *
6058 * @return <code>true</code> if there is at least one more element in the
6059 * underlying collection.
6060 */
6061 public boolean hasNext()
6062 {
6063 return i.hasNext();
6064 }
6065
6066 /**
6067 * Removes the next element from the collection.
6068 */
6069 public void remove()
6070 {
6071 i.remove();
6072 }
6073 } // class CheckedIterator
6074
6075 /**
6076 * <p>
6077 * Returns a dynamically typesafe view of the given list,
6078 * where any modification is first checked to ensure that the type
6079 * of the new data is appropriate. Although the addition of
6080 * generics and parametrically-typed collections prevents an
6081 * incorrect type of element being added to a collection at
6082 * compile-time, via static type checking, this can be overridden by
6083 * casting. In contrast, wrapping the collection within a
6084 * dynamically-typesafe wrapper, using this and associated methods,
6085 * <emph>guarantees</emph> that the collection will only contain
6086 * elements of an appropriate type (provided it only contains such
6087 * at the type of wrapping, and all subsequent access is via the
6088 * wrapper). This can be useful for debugging the cause of a
6089 * <code>ClassCastException</code> caused by erroneous casting, or
6090 * for protecting collections from corruption by external libraries.
6091 * </p>
6092 * <p>
6093 * The returned List implements Serializable, but can only be serialized if
6094 * the list it wraps is likewise Serializable. In addition, if the wrapped
6095 * list implements RandomAccess, this does too.
6096 * </p>
6097 *
6098 * @param l the list to wrap
6099 * @param type the type of the elements within the checked list.
6100 * @return a dynamically typesafe view of the list
6101 * @see Serializable
6102 * @see RandomAccess
6103 */
6104 public static <E> List<E> checkedList(List<E> l, Class<E> type)
6105 {
6106 if (l instanceof RandomAccess)
6107 return new CheckedRandomAccessList<E>(l, type);
6108 return new CheckedList<E>(l, type);
6109 }
6110
6111 /**
6112 * The implementation of {@link #checkedList(List,Class)} for sequential
6113 * lists. This class name is required for compatibility with Sun's JDK
6114 * serializability.
6115 *
6116 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
6117 * @since 1.5
6118 */
6119 private static class CheckedList<E>
6120 extends CheckedCollection<E>
6121 implements List<E>
6122 {
6123 /**
6124 * Compatible with JDK 1.5.
6125 */
6126 private static final long serialVersionUID = 65247728283967356L;
6127
6128 /**
6129 * The wrapped list; stored both here and in the superclass to avoid
6130 * excessive casting. Package visible for use by subclass.
6131 * @serial the wrapped list
6132 */
6133 final List<E> list;
6134
6135 /**
6136 * Wrap a given list.
6137 * @param l the list to wrap
6138 * @param type the type of the elements within the checked list.
6139 * @throws NullPointerException if l is null
6140 */
6141 CheckedList(List<E> l, Class<E> type)
6142 {
6143 super(l, type);
6144 list = l;
6145 }
6146
6147 /**
6148 * Adds the supplied element to the underlying list at the specified
6149 * index, provided it is of the right type.
6150 *
6151 * @param index The index at which to place the new element.
6152 * @param o the object to add.
6153 * @throws ClassCastException if the type of the object is not a
6154 * valid type for the underlying collection.
6155 */
6156 public void add(int index, E o)
6157 {
6158 if (type.isInstance(o))
6159 list.add(index, o);
6160 else
6161 throw new ClassCastException("The object is of the wrong type.");
6162 }
6163
6164 /**
6165 * Adds the members of the supplied collection to the underlying
6166 * collection at the specified index, provided they are all of the
6167 * correct type.
6168 *
6169 * @param index the index at which to place the new element.
6170 * @param c the collections of objects to add.
6171 * @throws ClassCastException if the type of any element in c is not a
6172 * valid type for the underlying collection.
6173 */
6174 public boolean addAll(int index, Collection<? extends E> coll)
6175 {
6176 Collection<E> typedColl = (Collection<E>) coll;
6177 final Iterator<E> it = typedColl.iterator();
6178 while (it.hasNext())
6179 {
6180 if (!type.isInstance(it.next()))
6181 throw new ClassCastException("A member of the collection is not of the correct type.");
6182 }
6183 return list.addAll(index, coll);
6184 }
6185
6186 /**
6187 * Returns <code>true</code> if the object, o, is an instance of
6188 * <code>List</code> with the same size and elements
6189 * as the underlying list.
6190 *
6191 * @param o The object to compare.
6192 * @return <code>true</code> if o is equivalent to the underlying list.
6193 */
6194 public boolean equals(Object o)
6195 {
6196 return list.equals(o);
6197 }
6198
6199 /**
6200 * Retrieves the element at a given index in the underlying list.
6201 *
6202 * @param index the index of the element to be returned
6203 * @return the element at the specified index in the underlying list
6204 * @throws IndexOutOfBoundsException if index < 0 || index >= size()
6205 */
6206 public E get(int index)
6207 {
6208 return list.get(index);
6209 }
6210
6211 /**
6212 * Computes the hash code for the underlying list.
6213 * The exact computation is described in the documentation
6214 * of the <code>List</code> interface.
6215 *
6216 * @return The hash code of the underlying list.
6217 * @see List#hashCode()
6218 */
6219 public int hashCode()
6220 {
6221 return list.hashCode();
6222 }
6223
6224 /**
6225 * Obtain the first index at which a given object is to be found in the
6226 * underlying list.
6227 *
6228 * @param o the object to search for
6229 * @return the least integer n such that <code>o == null ? get(n) == null :
6230 * o.equals(get(n))</code>, or -1 if there is no such index.
6231 * @throws ClassCastException if the type of o is not a valid
6232 * type for the underlying list.
6233 * @throws NullPointerException if o is null and the underlying
6234 * list does not support null values.
6235 */
6236 public int indexOf(Object o)
6237 {
6238 return list.indexOf(o);
6239 }
6240
6241 /**
6242 * Obtain the last index at which a given object is to be found in the
6243 * underlying list.
6244 *
6245 * @return the greatest integer n such that
6246 * <code>o == null ? get(n) == null : o.equals(get(n))</code>,
6247 * or -1 if there is no such index.
6248 * @throws ClassCastException if the type of o is not a valid
6249 * type for the underlying list.
6250 * @throws NullPointerException if o is null and the underlying
6251 * list does not support null values.
6252 */
6253 public int lastIndexOf(Object o)
6254 {
6255 return list.lastIndexOf(o);
6256 }
6257
6258 /**
6259 * Obtains a list iterator over the underlying list, starting at the
6260 * beginning and maintaining the checked nature of this list.
6261 *
6262 * @return a <code>CheckedListIterator</code> over the elements of the
6263 * underlying list, in order, starting at the beginning.
6264 */
6265 public ListIterator<E> listIterator()
6266 {
6267 return new CheckedListIterator<E>(list.listIterator(), type);
6268 }
6269
6270 /**
6271 * Obtains a list iterator over the underlying list, starting at the
6272 * specified index and maintaining the checked nature of this list. An
6273 * initial call to <code>next()</code> will retrieve the element at the
6274 * specified index, and an initial call to <code>previous()</code> will
6275 * retrieve the element at index - 1.
6276 *
6277 * @param index the position, between 0 and size() inclusive, to begin the
6278 * iteration from.
6279 * @return a <code>CheckedListIterator</code> over the elements of the
6280 * underlying list, in order, starting at the specified index.
6281 * @throws IndexOutOfBoundsException if index < 0 || index > size()
6282 */
6283 public ListIterator<E> listIterator(int index)
6284 {
6285 return new CheckedListIterator<E>(list.listIterator(index), type);
6286 }
6287
6288 /**
6289 * Removes the element at the specified index.
6290 *
6291 * @param index The index of the element to remove.
6292 * @return the removed element.
6293 */
6294 public E remove(int index)
6295 {
6296 return list.remove(index);
6297 }
6298
6299 /**
6300 * Replaces the element at the specified index in the underlying list
6301 * with that supplied.
6302 *
6303 * @param index the index of the element to replace.
6304 * @param o the new object to place at the specified index.
6305 * @return the replaced element.
6306 */
6307 public E set(int index, E o)
6308 {
6309 return list.set(index, o);
6310 }
6311
6312 /**
6313 * Obtain a List view of a subsection of the underlying list, from
6314 * fromIndex (inclusive) to toIndex (exclusive). If the two indices
6315 * are equal, the sublist is empty. The returned list will be
6316 * checked, like this list. Changes to the elements of the
6317 * returned list will be reflected in the underlying list. The effect
6318 * of structural modifications is undefined.
6319 *
6320 * @param fromIndex the index that the returned list should start from
6321 * (inclusive).
6322 * @param toIndex the index that the returned list should go
6323 * to (exclusive).
6324 * @return a List backed by a subsection of the underlying list.
6325 * @throws IndexOutOfBoundsException if fromIndex < 0
6326 * || toIndex > size() || fromIndex > toIndex.
6327 */
6328 public List<E> subList(int fromIndex, int toIndex)
6329 {
6330 return checkedList(list.subList(fromIndex, toIndex), type);
6331 }
6332 } // class CheckedList
6333
6334 /**
6335 * The implementation of {@link #checkedList(List)} for random-access
6336 * lists. This class name is required for compatibility with Sun's JDK
6337 * serializability.
6338 *
6339 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
6340 * @since 1.5
6341 */
6342 private static final class CheckedRandomAccessList<E>
6343 extends CheckedList<E>
6344 implements RandomAccess
6345 {
6346 /**
6347 * Compatible with JDK 1.5.
6348 */
6349 private static final long serialVersionUID = 1638200125423088369L;
6350
6351 /**
6352 * Wrap a given list.
6353 * @param l the list to wrap
6354 * @param type the type of the elements within the checked list.
6355 * @throws NullPointerException if l is null
6356 */
6357 CheckedRandomAccessList(List<E> l, Class<E> type)
6358 {
6359 super(l, type);
6360 }
6361 } // class CheckedRandomAccessList
6362
6363 /**
6364 * The implementation of {@link CheckedList#listIterator()}.
6365 *
6366 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
6367 * @since 1.5
6368 */
6369 private static final class CheckedListIterator<E>
6370 extends CheckedIterator<E>
6371 implements ListIterator<E>
6372 {
6373 /**
6374 * The wrapped iterator, stored both here and in the superclass to
6375 * avoid excessive casting.
6376 */
6377 private final ListIterator<E> li;
6378
6379 /**
6380 * Only trusted code creates a wrapper.
6381 * @param li the wrapped iterator
6382 */
6383 CheckedListIterator(ListIterator<E> li, Class<E> type)
6384 {
6385 super(li, type);
6386 this.li = li;
6387 }
6388
6389 /**
6390 * Adds the supplied object at the current iterator position, provided
6391 * it is of the correct type.
6392 *
6393 * @param o the object to add.
6394 * @throws ClassCastException if the type of the object is not a
6395 * valid type for the underlying collection.
6396 */
6397 public void add(E o)
6398 {
6399 if (type.isInstance(o))
6400 li.add(o);
6401 else
6402 throw new ClassCastException("The object is of the wrong type.");
6403 }
6404
6405 /**
6406 * Tests whether there are still elements to be retrieved from the
6407 * underlying collection by <code>previous()</code>. When this method
6408 * returns <code>true</code>, an exception will not be thrown on calling
6409 * <code>previous()</code>.
6410 *
6411 * @return <code>true</code> if there is at least one more element prior
6412 * to the current position in the underlying list.
6413 */
6414 public boolean hasPrevious()
6415 {
6416 return li.hasPrevious();
6417 }
6418
6419 /**
6420 * Find the index of the element that would be returned by a call to next.
6421 * If <code>hasNext()</code> returns <code>false</code>, this returns the
6422 * list size.
6423 *
6424 * @return the index of the element that would be returned by
6425 * <code>next()</code>.
6426 */
6427 public int nextIndex()
6428 {
6429 return li.nextIndex();
6430 }
6431
6432 /**
6433 * Obtains the previous element in the underlying list.
6434 *
6435 * @return the previous element in the list.
6436 * @throws NoSuchElementException if there are no more prior elements.
6437 */
6438 public E previous()
6439 {
6440 return li.previous();
6441 }
6442
6443 /**
6444 * Find the index of the element that would be returned by a call to
6445 * previous. If <code>hasPrevious()</code> returns <code>false</code>,
6446 * this returns -1.
6447 *
6448 * @return the index of the element that would be returned by
6449 * <code>previous()</code>.
6450 */
6451 public int previousIndex()
6452 {
6453 return li.previousIndex();
6454 }
6455
6456 /**
6457 * Sets the next element to that supplied, provided that it is of the
6458 * correct type.
6459 *
6460 * @param o The new object to replace the existing one.
6461 * @throws ClassCastException if the type of the object is not a
6462 * valid type for the underlying collection.
6463 */
6464 public void set(E o)
6465 {
6466 if (type.isInstance(o))
6467 li.set(o);
6468 else
6469 throw new ClassCastException("The object is of the wrong type.");
6470 }
6471 } // class CheckedListIterator
6472
6473 /**
6474 * <p>
6475 * Returns a dynamically typesafe view of the given map,
6476 * where any modification is first checked to ensure that the type
6477 * of the new data is appropriate. Although the addition of
6478 * generics and parametrically-typed collections prevents an
6479 * incorrect type of element being added to a collection at
6480 * compile-time, via static type checking, this can be overridden by
6481 * casting. In contrast, wrapping the collection within a
6482 * dynamically-typesafe wrapper, using this and associated methods,
6483 * <emph>guarantees</emph> that the collection will only contain
6484 * elements of an appropriate type (provided it only contains such
6485 * at the type of wrapping, and all subsequent access is via the
6486 * wrapper). This can be useful for debugging the cause of a
6487 * <code>ClassCastException</code> caused by erroneous casting, or
6488 * for protecting collections from corruption by external libraries.
6489 * </p>
6490 * <p>
6491 * The returned Map implements Serializable, but can only be serialized if
6492 * the map it wraps is likewise Serializable.
6493 * </p>
6494 *
6495 * @param m the map to wrap
6496 * @param keyType the dynamic type of the map's keys.
6497 * @param valueType the dynamic type of the map's values.
6498 * @return a dynamically typesafe view of the map
6499 * @see Serializable
6500 */
6501 public static <K, V> Map<K, V> checkedMap(Map<K, V> m, Class<K> keyType,
6502 Class<V> valueType)
6503 {
6504 return new CheckedMap<K, V>(m, keyType, valueType);
6505 }
6506
6507 /**
6508 * The implementation of {@link #checkedMap(Map)}. This
6509 * class name is required for compatibility with Sun's JDK serializability.
6510 *
6511 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
6512 * @since 1.5
6513 */
6514 private static class CheckedMap<K, V>
6515 implements Map<K, V>, Serializable
6516 {
6517 /**
6518 * Compatible with JDK 1.5.
6519 */
6520 private static final long serialVersionUID = 5742860141034234728L;
6521
6522 /**
6523 * The wrapped map.
6524 * @serial the real map
6525 */
6526 private final Map<K, V> m;
6527
6528 /**
6529 * The type of the map's keys.
6530 * @serial the key type.
6531 */
6532 final Class<K> keyType;
6533
6534 /**
6535 * The type of the map's values.
6536 * @serial the value type.
6537 */
6538 final Class<V> valueType;
6539
6540 /**
6541 * Cache the entry set.
6542 */
6543 private transient Set<Map.Entry<K, V>> entries;
6544
6545 /**
6546 * Cache the key set.
6547 */
6548 private transient Set<K> keys;
6549
6550 /**
6551 * Cache the value collection.
6552 */
6553 private transient Collection<V> values;
6554
6555 /**
6556 * Wrap a given map.
6557 * @param m the map to wrap
6558 * @param keyType the dynamic type of the map's keys.
6559 * @param valueType the dynamic type of the map's values.
6560 * @throws NullPointerException if m is null
6561 */
6562 CheckedMap(Map<K, V> m, Class<K> keyType, Class<V> valueType)
6563 {
6564 this.m = m;
6565 this.keyType = keyType;
6566 this.valueType = valueType;
6567 if (m == null)
6568 throw new NullPointerException();
6569 }
6570
6571 /**
6572 * Clears all pairs from the map.
6573 */
6574 public void clear()
6575 {
6576 m.clear();
6577 }
6578
6579 /**
6580 * Returns <code>true</code> if the underlying map contains a mapping for
6581 * the given key.
6582 *
6583 * @param key the key to search for
6584 * @return <code>true</code> if the map contains the key
6585 * @throws ClassCastException if the key is of an inappropriate type
6586 * @throws NullPointerException if key is <code>null</code> but the map
6587 * does not permit null keys
6588 */
6589 public boolean containsKey(Object key)
6590 {
6591 return m.containsKey(key);
6592 }
6593
6594 /**
6595 * Returns <code>true</code> if the underlying map contains at least one
6596 * mapping with the given value. In other words, it returns
6597 * <code>true</code> if a value v exists where
6598 * <code>(value == null ? v == null : value.equals(v))</code>.
6599 * This usually requires linear time.
6600 *
6601 * @param value the value to search for
6602 * @return <code>true</code> if the map contains the value
6603 * @throws ClassCastException if the type of the value is not a valid type
6604 * for this map.
6605 * @throws NullPointerException if the value is null and the map doesn't
6606 * support null values.
6607 */
6608 public boolean containsValue(Object value)
6609 {
6610 return m.containsValue(value);
6611 }
6612
6613 /**
6614 * <p>
6615 * Returns a checked set view of the entries in the underlying map.
6616 * Each element in the set is a unmodifiable variant of
6617 * <code>Map.Entry</code>.
6618 * </p>
6619 * <p>
6620 * The set is backed by the map, so that changes in one show up in the
6621 * other. Modifications made while an iterator is in progress cause
6622 * undefined behavior.
6623 * </p>
6624 *
6625 * @return the checked set view of all mapping entries.
6626 * @see Map.Entry
6627 */
6628 public Set<Map.Entry<K, V>> entrySet()
6629 {
6630 if (entries == null)
6631 {
6632 Class<Map.Entry<K,V>> klass =
6633 (Class<Map.Entry<K,V>>) (Class) Map.Entry.class;
6634 entries = new CheckedEntrySet<Map.Entry<K,V>,K,V>(m.entrySet(),
6635 klass,
6636 keyType,
6637 valueType);
6638 }
6639 return entries;
6640 }
6641
6642 /**
6643 * The implementation of {@link CheckedMap#entrySet()}. This class
6644 * is <emph>not</emph> serializable.
6645 *
6646 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
6647 * @since 1.5
6648 */
6649 private static final class CheckedEntrySet<E,SK,SV>
6650 extends CheckedSet<E>
6651 {
6652 /**
6653 * The type of the map's keys.
6654 * @serial the key type.
6655 */
6656 private final Class<SK> keyType;
6657
6658 /**
6659 * The type of the map's values.
6660 * @serial the value type.
6661 */
6662 private final Class<SV> valueType;
6663
6664 /**
6665 * Wrap a given set of map entries.
6666 *
6667 * @param s the set to wrap.
6668 * @param type the type of the set's entries.
6669 * @param keyType the type of the map's keys.
6670 * @param valueType the type of the map's values.
6671 */
6672 CheckedEntrySet(Set<E> s, Class<E> type, Class<SK> keyType,
6673 Class<SV> valueType)
6674 {
6675 super(s, type);
6676 this.keyType = keyType;
6677 this.valueType = valueType;
6678 }
6679
6680 // The iterator must return checked map entries.
6681 public Iterator<E> iterator()
6682 {
6683 return new CheckedIterator<E>(c.iterator(), type)
6684 {
6685 /**
6686 * Obtains the next element from the underlying set of
6687 * map entries.
6688 *
6689 * @return the next element in the collection.
6690 * @throws NoSuchElementException if there are no more elements.
6691 */
6692 public E next()
6693 {
6694 final Map.Entry e = (Map.Entry) super.next();
6695 return (E) new Map.Entry()
6696 {
6697 /**
6698 * Returns <code>true</code> if the object, o, is also a map
6699 * entry with an identical key and value.
6700 *
6701 * @param o the object to compare.
6702 * @return <code>true</code> if o is an equivalent map entry.
6703 */
6704 public boolean equals(Object o)
6705 {
6706 return e.equals(o);
6707 }
6708
6709 /**
6710 * Returns the key of this map entry.
6711 *
6712 * @return the key.
6713 */
6714 public Object getKey()
6715 {
6716 return e.getKey();
6717 }
6718
6719 /**
6720 * Returns the value of this map entry.
6721 *
6722 * @return the value.
6723 */
6724 public Object getValue()
6725 {
6726 return e.getValue();
6727 }
6728
6729 /**
6730 * Computes the hash code of this map entry.
6731 * The computation is described in the <code>Map</code>
6732 * interface documentation.
6733 *
6734 * @return the hash code of this entry.
6735 * @see Map#hashCode()
6736 */
6737 public int hashCode()
6738 {
6739 return e.hashCode();
6740 }
6741
6742 /**
6743 * Sets the value of this map entry, provided it is of the
6744 * right type.
6745 *
6746 * @param value The new value.
6747 * @throws ClassCastException if the type of the value is not
6748 * a valid type for the underlying
6749 * map.
6750 */
6751 public Object setValue(Object value)
6752 {
6753 if (valueType.isInstance(value))
6754 return e.setValue(value);
6755 else
6756 throw new ClassCastException("The value is of the wrong type.");
6757 }
6758
6759 /**
6760 * Returns a textual representation of the map entry.
6761 *
6762 * @return The map entry as a <code>String</code>.
6763 */
6764 public String toString()
6765 {
6766 return e.toString();
6767 }
6768 };
6769 }
6770 };
6771 }
6772 } // class CheckedEntrySet
6773
6774 /**
6775 * Returns <code>true</code> if the object, o, is also an instance
6776 * of <code>Map</code> with an equal set of map entries.
6777 *
6778 * @param o The object to compare.
6779 * @return <code>true</code> if o is an equivalent map.
6780 */
6781 public boolean equals(Object o)
6782 {
6783 return m.equals(o);
6784 }
6785
6786 /**
6787 * Returns the value associated with the supplied key or
6788 * null if no such mapping exists. An ambiguity can occur
6789 * if null values are accepted by the underlying map.
6790 * In this case, <code>containsKey()</code> can be used
6791 * to separate the two possible cases of a null result.
6792 *
6793 * @param key The key to look up.
6794 * @return the value associated with the key, or null if key not in map.
6795 * @throws ClassCastException if the key is an inappropriate type.
6796 * @throws NullPointerException if this map does not accept null keys.
6797 * @see #containsKey(Object)
6798 */
6799 public V get(Object key)
6800 {
6801 return m.get(key);
6802 }
6803
6804 /**
6805 * Adds a new pair to the map, provided both the key and the value are
6806 * of the correct types.
6807 *
6808 * @param key The new key.
6809 * @param value The new value.
6810 * @return the previous value of the key, or null if there was no mapping.
6811 * @throws ClassCastException if the type of the key or the value is
6812 * not a valid type for the underlying map.
6813 */
6814 public V put(K key, V value)
6815 {
6816 if (keyType.isInstance(key))
6817 {
6818 if (valueType.isInstance(value))
6819 return m.put(key,value);
6820 else
6821 throw new ClassCastException("The value is of the wrong type.");
6822 }
6823 throw new ClassCastException("The key is of the wrong type.");
6824 }
6825
6826 /**
6827 * Computes the hash code for the underlying map, as the sum
6828 * of the hash codes of all entries.
6829 *
6830 * @return The hash code of the underlying map.
6831 * @see Map.Entry#hashCode()
6832 */
6833 public int hashCode()
6834 {
6835 return m.hashCode();
6836 }
6837
6838 /**
6839 * Returns <code>true</code> if the underlying map contains no entries.
6840 *
6841 * @return <code>true</code> if the map is empty.
6842 */
6843 public boolean isEmpty()
6844 {
6845 return m.isEmpty();
6846 }
6847
6848 /**
6849 * <p>
6850 * Returns a checked set view of the keys in the underlying map.
6851 * The set is backed by the map, so that changes in one show up in the
6852 * other.
6853 * </p>
6854 * <p>
6855 * Modifications made while an iterator is in progress cause undefined
6856 * behavior. These modifications are again limited to the values of
6857 * the keys.
6858 * </p>
6859 *
6860 * @return the set view of all keys.
6861 */
6862 public Set<K> keySet()
6863 {
6864 if (keys == null)
6865 keys = new CheckedSet<K>(m.keySet(), keyType);
6866 return keys;
6867 }
6868
6869 /**
6870 * Adds all pairs within the supplied map to the underlying map,
6871 * provided they are all have the correct key and value types.
6872 *
6873 * @param m the map, the entries of which should be added
6874 * to the underlying map.
6875 * @throws ClassCastException if the type of a key or value is
6876 * not a valid type for the underlying map.
6877 */
6878 public void putAll(Map<? extends K, ? extends V> map)
6879 {
6880 Map<K,V> typedMap = (Map<K,V>) map;
6881 final Iterator<Map.Entry<K,V>> it = typedMap.entrySet().iterator();
6882 while (it.hasNext())
6883 {
6884 final Map.Entry<K,V> entry = it.next();
6885 if (!keyType.isInstance(entry.getKey()))
6886 throw new ClassCastException("A key is of the wrong type.");
6887 if (!valueType.isInstance(entry.getValue()))
6888 throw new ClassCastException("A value is of the wrong type.");
6889 }
6890 m.putAll(typedMap);
6891 }
6892
6893 /**
6894 * Removes a pair from the map.
6895 *
6896 * @param o The key of the entry to remove.
6897 * @return The value the key was associated with, or null
6898 * if no such mapping existed. Null is also returned
6899 * if the removed entry had a null key.
6900 * @throws UnsupportedOperationException as an unmodifiable
6901 * map does not support the <code>remove</code> operation.
6902 */
6903 public V remove(Object o)
6904 {
6905 return m.remove(o);
6906 }
6907
6908
6909 /**
6910 * Returns the number of key-value mappings in the underlying map.
6911 * If there are more than Integer.MAX_VALUE mappings, Integer.MAX_VALUE
6912 * is returned.
6913 *
6914 * @return the number of mappings.
6915 */
6916 public int size()
6917 {
6918 return m.size();
6919 }
6920
6921 /**
6922 * Returns a textual representation of the map.
6923 *
6924 * @return The map in the form of a <code>String</code>.
6925 */
6926 public String toString()
6927 {
6928 return m.toString();
6929 }
6930
6931 /**
6932 * <p>
6933 * Returns a unmodifiable collection view of the values in the underlying
6934 * map. The collection is backed by the map, so that changes in one show
6935 * up in the other.
6936 * </p>
6937 * <p>
6938 * Modifications made while an iterator is in progress cause undefined
6939 * behavior. These modifications are again limited to the values of
6940 * the keys.
6941 * </p>
6942 *
6943 * @return the collection view of all values.
6944 */
6945 public Collection<V> values()
6946 {
6947 if (values == null)
6948 values = new CheckedCollection<V>(m.values(), valueType);
6949 return values;
6950 }
6951 } // class CheckedMap
6952
6953 /**
6954 * <p>
6955 * Returns a dynamically typesafe view of the given set,
6956 * where any modification is first checked to ensure that the type
6957 * of the new data is appropriate. Although the addition of
6958 * generics and parametrically-typed collections prevents an
6959 * incorrect type of element being added to a collection at
6960 * compile-time, via static type checking, this can be overridden by
6961 * casting. In contrast, wrapping the collection within a
6962 * dynamically-typesafe wrapper, using this and associated methods,
6963 * <emph>guarantees</emph> that the collection will only contain
6964 * elements of an appropriate type (provided it only contains such
6965 * at the type of wrapping, and all subsequent access is via the
6966 * wrapper). This can be useful for debugging the cause of a
6967 * <code>ClassCastException</code> caused by erroneous casting, or
6968 * for protecting collections from corruption by external libraries.
6969 * </p>
6970 * <p>
6971 * The returned Set implements Serializable, but can only be serialized if
6972 * the set it wraps is likewise Serializable.
6973 * </p>
6974 *
6975 * @param s the set to wrap.
6976 * @param type the type of the elements within the checked list.
6977 * @return a dynamically typesafe view of the set
6978 * @see Serializable
6979 */
6980 public static <E> Set<E> checkedSet(Set<E> s, Class<E> type)
6981 {
6982 return new CheckedSet<E>(s, type);
6983 }
6984
6985 /**
6986 * The implementation of {@link #checkedSet(Set)}. This class
6987 * name is required for compatibility with Sun's JDK serializability.
6988 *
6989 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
6990 * @since 1.5
6991 */
6992 private static class CheckedSet<E>
6993 extends CheckedCollection<E>
6994 implements Set<E>
6995 {
6996 /**
6997 * Compatible with JDK 1.5.
6998 */
6999 private static final long serialVersionUID = 4694047833775013803L;
7000
7001 /**
7002 * Wrap a given set.
7003 *
7004 * @param s the set to wrap
7005 * @throws NullPointerException if s is null
7006 */
7007 CheckedSet(Set<E> s, Class<E> type)
7008 {
7009 super(s, type);
7010 }
7011
7012 /**
7013 * Returns <code>true</code> if the object, o, is also an instance of
7014 * <code>Set</code> of the same size and with the same entries.
7015 *
7016 * @return <code>true</code> if o is an equivalent set.
7017 */
7018 public boolean equals(Object o)
7019 {
7020 return c.equals(o);
7021 }
7022
7023 /**
7024 * Computes the hash code of this set, as the sum of the
7025 * hash codes of all elements within the set.
7026 *
7027 * @return the hash code of the set.
7028 */
7029 public int hashCode()
7030 {
7031 return c.hashCode();
7032 }
7033 } // class CheckedSet
7034
7035 /**
7036 * <p>
7037 * Returns a dynamically typesafe view of the given sorted map,
7038 * where any modification is first checked to ensure that the type
7039 * of the new data is appropriate. Although the addition of
7040 * generics and parametrically-typed collections prevents an
7041 * incorrect type of element being added to a collection at
7042 * compile-time, via static type checking, this can be overridden by
7043 * casting. In contrast, wrapping the collection within a
7044 * dynamically-typesafe wrapper, using this and associated methods,
7045 * <emph>guarantees</emph> that the collection will only contain
7046 * elements of an appropriate type (provided it only contains such
7047 * at the type of wrapping, and all subsequent access is via the
7048 * wrapper). This can be useful for debugging the cause of a
7049 * <code>ClassCastException</code> caused by erroneous casting, or
7050 * for protecting collections from corruption by external libraries.
7051 * </p>
7052 * <p>
7053 * The returned SortedMap implements Serializable, but can only be
7054 * serialized if the map it wraps is likewise Serializable.
7055 * </p>
7056 *
7057 * @param m the map to wrap.
7058 * @param keyType the dynamic type of the map's keys.
7059 * @param valueType the dynamic type of the map's values.
7060 * @return a dynamically typesafe view of the map
7061 * @see Serializable
7062 */
7063 public static <K, V> SortedMap<K, V> checkedSortedMap(SortedMap<K, V> m,
7064 Class<K> keyType,
7065 Class<V> valueType)
7066 {
7067 return new CheckedSortedMap<K, V>(m, keyType, valueType);
7068 }
7069
7070 /**
7071 * The implementation of {@link #checkedSortedMap(SortedMap,Class,Class)}.
7072 * This class name is required for compatibility with Sun's JDK
7073 * serializability.
7074 *
7075 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
7076 */
7077 private static class CheckedSortedMap<K, V>
7078 extends CheckedMap<K, V>
7079 implements SortedMap<K, V>
7080 {
7081 /**
7082 * Compatible with JDK 1.5.
7083 */
7084 private static final long serialVersionUID = 1599671320688067438L;
7085
7086 /**
7087 * The wrapped map; stored both here and in the superclass to avoid
7088 * excessive casting.
7089 * @serial the wrapped map
7090 */
7091 private final SortedMap<K, V> sm;
7092
7093 /**
7094 * Wrap a given map.
7095 *
7096 * @param sm the map to wrap
7097 * @param keyType the dynamic type of the map's keys.
7098 * @param valueType the dynamic type of the map's values.
7099 * @throws NullPointerException if sm is null
7100 */
7101 CheckedSortedMap(SortedMap<K, V> sm, Class<K> keyType, Class<V> valueType)
7102 {
7103 super(sm, keyType, valueType);
7104 this.sm = sm;
7105 }
7106
7107 /**
7108 * Returns the comparator used in sorting the underlying map,
7109 * or null if it is the keys' natural ordering.
7110 *
7111 * @return the sorting comparator.
7112 */
7113 public Comparator<? super K> comparator()
7114 {
7115 return sm.comparator();
7116 }
7117
7118 /**
7119 * Returns the first (lowest sorted) key in the map.
7120 *
7121 * @return the first key.
7122 * @throws NoSuchElementException if this map is empty.
7123 */
7124 public K firstKey()
7125 {
7126 return sm.firstKey();
7127 }
7128
7129 /**
7130 * <p>
7131 * Returns a checked view of the portion of the map strictly less
7132 * than toKey. The view is backed by the underlying map, so changes in
7133 * one show up in the other. The submap supports all optional operations
7134 * of the original. This operation is equivalent to
7135 * <code>subMap(firstKey(), toKey)</code>.
7136 * </p>
7137 * <p>
7138 * The returned map throws an IllegalArgumentException any time a key is
7139 * used which is out of the range of toKey. Note that the endpoint, toKey,
7140 * is not included; if you want this value to be included, pass its
7141 * successor object in to toKey. For example, for Integers, you could
7142 * request <code>headMap(new Integer(limit.intValue() + 1))</code>.
7143 * </p>
7144 *
7145 * @param toKey the exclusive upper range of the submap.
7146 * @return the submap.
7147 * @throws ClassCastException if toKey is not comparable to the map
7148 * contents.
7149 * @throws IllegalArgumentException if this is a subMap, and toKey is out
7150 * of range.
7151 * @throws NullPointerException if toKey is null but the map does not allow
7152 * null keys.
7153 */
7154 public SortedMap<K, V> headMap(K toKey)
7155 {
7156 return new CheckedSortedMap<K, V>(sm.headMap(toKey), keyType, valueType);
7157 }
7158
7159 /**
7160 * Returns the last (highest sorted) key in the map.
7161 *
7162 * @return the last key.
7163 * @throws NoSuchElementException if this map is empty.
7164 */
7165 public K lastKey()
7166 {
7167 return sm.lastKey();
7168 }
7169
7170 /**
7171 * <p>
7172 * Returns a checked view of the portion of the map greater than or
7173 * equal to fromKey, and strictly less than toKey. The view is backed by
7174 * the underlying map, so changes in one show up in the other. The submap
7175 * supports all optional operations of the original.
7176 * </p>
7177 * <p>
7178 * The returned map throws an IllegalArgumentException any time a key is
7179 * used which is out of the range of fromKey and toKey. Note that the
7180 * lower endpoint is included, but the upper is not; if you want to
7181 * change the inclusion or exclusion of an endpoint, pass its successor
7182 * object in instead. For example, for Integers, you could request
7183 * <code>subMap(new Integer(lowlimit.intValue() + 1),
7184 * new Integer(highlimit.intValue() + 1))</code> to reverse
7185 * the inclusiveness of both endpoints.
7186 * </p>
7187 *
7188 * @param fromKey the inclusive lower range of the submap.
7189 * @param toKey the exclusive upper range of the submap.
7190 * @return the submap.
7191 * @throws ClassCastException if fromKey or toKey is not comparable to
7192 * the map contents.
7193 * @throws IllegalArgumentException if this is a subMap, and fromKey or
7194 * toKey is out of range.
7195 * @throws NullPointerException if fromKey or toKey is null but the map
7196 * does not allow null keys.
7197 */
7198 public SortedMap<K, V> subMap(K fromKey, K toKey)
7199 {
7200 return new CheckedSortedMap<K, V>(sm.subMap(fromKey, toKey), keyType,
7201 valueType);
7202 }
7203
7204 /**
7205 * <p>
7206 * Returns a checked view of the portion of the map greater than or
7207 * equal to fromKey. The view is backed by the underlying map, so changes
7208 * in one show up in the other. The submap supports all optional operations
7209 * of the original.
7210 * </p>
7211 * <p>
7212 * The returned map throws an IllegalArgumentException any time a key is
7213 * used which is out of the range of fromKey. Note that the endpoint,
7214 * fromKey, is included; if you do not want this value to be included,
7215 * pass its successor object in to fromKey. For example, for Integers,
7216 * you could request
7217 * <code>tailMap(new Integer(limit.intValue() + 1))</code>.
7218 * </p>
7219 *
7220 * @param fromKey the inclusive lower range of the submap
7221 * @return the submap
7222 * @throws ClassCastException if fromKey is not comparable to the map
7223 * contents
7224 * @throws IllegalArgumentException if this is a subMap, and fromKey is out
7225 * of range
7226 * @throws NullPointerException if fromKey is null but the map does not
7227 * allow null keys
7228 */
7229 public SortedMap<K, V> tailMap(K fromKey)
7230 {
7231 return new CheckedSortedMap<K, V>(sm.tailMap(fromKey), keyType,
7232 valueType);
7233 }
7234 } // class CheckedSortedMap
7235
7236 /**
7237 * <p>
7238 * Returns a dynamically typesafe view of the given sorted set,
7239 * where any modification is first checked to ensure that the type
7240 * of the new data is appropriate. Although the addition of
7241 * generics and parametrically-typed collections prevents an
7242 * incorrect type of element being added to a collection at
7243 * compile-time, via static type checking, this can be overridden by
7244 * casting. In contrast, wrapping the collection within a
7245 * dynamically-typesafe wrapper, using this and associated methods,
7246 * <emph>guarantees</emph> that the collection will only contain
7247 * elements of an appropriate type (provided it only contains such
7248 * at the type of wrapping, and all subsequent access is via the
7249 * wrapper). This can be useful for debugging the cause of a
7250 * <code>ClassCastException</code> caused by erroneous casting, or
7251 * for protecting collections from corruption by external libraries.
7252 * </p>
7253 * <p>
7254 * The returned SortedSet implements Serializable, but can only be
7255 * serialized if the set it wraps is likewise Serializable.
7256 * </p>
7257 *
7258 * @param s the set to wrap.
7259 * @param type the type of the set's elements.
7260 * @return a dynamically typesafe view of the set
7261 * @see Serializable
7262 */
7263 public static <E> SortedSet<E> checkedSortedSet(SortedSet<E> s,
7264 Class<E> type)
7265 {
7266 return new CheckedSortedSet<E>(s, type);
7267 }
7268
7269 /**
7270 * The implementation of {@link #checkedSortedSet(SortedSet,Class)}. This
7271 * class name is required for compatibility with Sun's JDK serializability.
7272 *
7273 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
7274 * @since 1.5
7275 */
7276 private static class CheckedSortedSet<E>
7277 extends CheckedSet<E>
7278 implements SortedSet<E>
7279 {
7280 /**
7281 * Compatible with JDK 1.4.
7282 */
7283 private static final long serialVersionUID = 1599911165492914959L;
7284
7285 /**
7286 * The wrapped set; stored both here and in the superclass to avoid
7287 * excessive casting.
7288 *
7289 * @serial the wrapped set
7290 */
7291 private SortedSet<E> ss;
7292
7293 /**
7294 * Wrap a given set.
7295 *
7296 * @param ss the set to wrap.
7297 * @param type the type of the set's elements.
7298 * @throws NullPointerException if ss is null
7299 */
7300 CheckedSortedSet(SortedSet<E> ss, Class<E> type)
7301 {
7302 super(ss, type);
7303 this.ss = ss;
7304 }
7305
7306 /**
7307 * Returns the comparator used in sorting the underlying set,
7308 * or null if it is the elements' natural ordering.
7309 *
7310 * @return the sorting comparator
7311 */
7312 public Comparator<? super E> comparator()
7313 {
7314 return ss.comparator();
7315 }
7316
7317 /**
7318 * Returns the first (lowest sorted) element in the underlying
7319 * set.
7320 *
7321 * @return the first element.
7322 * @throws NoSuchElementException if the set is empty.
7323 */
7324 public E first()
7325 {
7326 return ss.first();
7327 }
7328
7329 /**
7330 * <p>
7331 * Returns a checked view of the portion of the set strictly
7332 * less than toElement. The view is backed by the underlying set,
7333 * so changes in one show up in the other. The subset supports
7334 * all optional operations of the original. This operation
7335 * is equivalent to <code>subSet(first(), toElement)</code>.
7336 * </p>
7337 * <p>
7338 * The returned set throws an IllegalArgumentException any time an
7339 * element is used which is out of the range of toElement. Note that
7340 * the endpoint, toElement, is not included; if you want this value
7341 * included, pass its successor object in to toElement. For example,
7342 * for Integers, you could request
7343 * <code>headSet(new Integer(limit.intValue() + 1))</code>.
7344 * </p>
7345 *
7346 * @param toElement the exclusive upper range of the subset
7347 * @return the subset.
7348 * @throws ClassCastException if toElement is not comparable to the set
7349 * contents.
7350 * @throws IllegalArgumentException if this is a subSet, and toElement is
7351 * out of range.
7352 * @throws NullPointerException if toElement is null but the set does not
7353 * allow null elements.
7354 */
7355 public SortedSet<E> headSet(E toElement)
7356 {
7357 return new CheckedSortedSet<E>(ss.headSet(toElement), type);
7358 }
7359
7360 /**
7361 * Returns the last (highest sorted) element in the underlying
7362 * set.
7363 *
7364 * @return the last element.
7365 * @throws NoSuchElementException if the set is empty.
7366 */
7367 public E last()
7368 {
7369 return ss.last();
7370 }
7371
7372 /**
7373 * <p>
7374 * Returns a checked view of the portion of the set greater than or
7375 * equal to fromElement, and strictly less than toElement. The view is
7376 * backed by the underlying set, so changes in one show up in the other.
7377 * The subset supports all optional operations of the original.
7378 * </p>
7379 * <p>
7380 * The returned set throws an IllegalArgumentException any time an
7381 * element is used which is out of the range of fromElement and toElement.
7382 * Note that the lower endpoint is included, but the upper is not; if you
7383 * want to change the inclusion or exclusion of an endpoint, pass its
7384 * successor object in instead. For example, for Integers, you can request
7385 * <code>subSet(new Integer(lowlimit.intValue() + 1),
7386 * new Integer(highlimit.intValue() + 1))</code> to reverse
7387 * the inclusiveness of both endpoints.
7388 * </p>
7389 *
7390 * @param fromElement the inclusive lower range of the subset.
7391 * @param toElement the exclusive upper range of the subset.
7392 * @return the subset.
7393 * @throws ClassCastException if fromElement or toElement is not comparable
7394 * to the set contents.
7395 * @throws IllegalArgumentException if this is a subSet, and fromElement or
7396 * toElement is out of range.
7397 * @throws NullPointerException if fromElement or toElement is null but the
7398 * set does not allow null elements.
7399 */
7400 public SortedSet<E> subSet(E fromElement, E toElement)
7401 {
7402 return new CheckedSortedSet<E>(ss.subSet(fromElement, toElement), type);
7403 }
7404
7405 /**
7406 * <p>
7407 * Returns a checked view of the portion of the set greater than or equal
7408 * to fromElement. The view is backed by the underlying set, so changes in
7409 * one show up in the other. The subset supports all optional operations
7410 * of the original.
7411 * </p>
7412 * <p>
7413 * The returned set throws an IllegalArgumentException any time an
7414 * element is used which is out of the range of fromElement. Note that
7415 * the endpoint, fromElement, is included; if you do not want this value
7416 * to be included, pass its successor object in to fromElement. For
7417 * example, for Integers, you could request
7418 * <code>tailSet(new Integer(limit.intValue() + 1))</code>.
7419 * </p>
7420 *
7421 * @param fromElement the inclusive lower range of the subset
7422 * @return the subset.
7423 * @throws ClassCastException if fromElement is not comparable to the set
7424 * contents.
7425 * @throws IllegalArgumentException if this is a subSet, and fromElement is
7426 * out of range.
7427 * @throws NullPointerException if fromElement is null but the set does not
7428 * allow null elements.
7429 */
7430 public SortedSet<E> tailSet(E fromElement)
7431 {
7432 return new CheckedSortedSet<E>(ss.tailSet(fromElement), type);
7433 }
7434 } // class CheckedSortedSet
7435
7436 /**
7437 * Returns a view of a {@link Deque} as a stack or LIFO (Last-In-First-Out)
7438 * {@link Queue}. Each call to the LIFO queue corresponds to one
7439 * equivalent method call to the underlying deque, with the exception
7440 * of {@link Collection#addAll(Collection)}, which is emulated by a series
7441 * of {@link Deque#push(E)} calls.
7442 *
7443 * @param deque the deque to convert to a LIFO queue.
7444 * @return a LIFO queue.
7445 * @since 1.6
7446 */
7447 public static <T> Queue<T> asLifoQueue(Deque<T> deque)
7448 {
7449 return new LIFOQueue<T>(deque);
7450 }
7451
7452 /**
7453 * Returns a set backed by the supplied map. The resulting set
7454 * has the same performance, concurrency and ordering characteristics
7455 * as the original map. The supplied map must be empty and should not
7456 * be used after the set is created. Each call to the set corresponds
7457 * to one equivalent method call to the underlying map, with the exception
7458 * of {@link Set#addAll(Collection)} which is emulated by a series of
7459 * calls to <code>put</code>.
7460 *
7461 * @param map the map to convert to a set.
7462 * @return a set backed by the supplied map.
7463 * @throws IllegalArgumentException if the map is not empty.
7464 * @since 1.6
7465 */
7466 public static <E> Set<E> newSetFromMap(Map<E,Boolean> map)
7467 {
7468 return new MapSet<E>(map);
7469 }
7470
7471 /**
7472 * The implementation of {@link #asLIFOQueue(Deque)}.
7473 *
7474 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
7475 * @since 1.6
7476 */
7477 private static class LIFOQueue<T>
7478 extends AbstractQueue<T>
7479 {
7480
7481 /**
7482 * The backing deque.
7483 */
7484 private Deque<T> deque;
7485
7486 /**
7487 * Constructs a new {@link LIFOQueue} with the specified
7488 * backing {@link Deque}.
7489 *
7490 * @param deque the backing deque.
7491 */
7492 public LIFOQueue(Deque<T> deque)
7493 {
7494 this.deque = deque;
7495 }
7496
7497 public boolean add(T e)
7498 {
7499 return deque.offerFirst(e);
7500 }
7501
7502 public boolean addAll(Collection<? extends T> c)
7503 {
7504 boolean result = false;
7505 final Iterator<? extends T> it = c.iterator();
7506 while (it.hasNext())
7507 result |= deque.offerFirst(it.next());
7508 return result;
7509 }
7510
7511 public void clear()
7512 {
7513 deque.clear();
7514 }
7515
7516 public boolean isEmpty()
7517 {
7518 return deque.isEmpty();
7519 }
7520
7521 public Iterator<T> iterator()
7522 {
7523 return deque.iterator();
7524 }
7525
7526 public boolean offer(T e)
7527 {
7528 return deque.offerFirst(e);
7529 }
7530
7531 public T peek()
7532 {
7533 return deque.peek();
7534 }
7535
7536 public T poll()
7537 {
7538 return deque.poll();
7539 }
7540
7541 public int size()
7542 {
7543 return deque.size();
7544 }
7545 } // class LIFOQueue
7546
7547 /**
7548 * The implementation of {@link #newSetFromMap(Map)}.
7549 *
7550 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
7551 * @since 1.6
7552 */
7553 private static class MapSet<E>
7554 extends AbstractSet<E>
7555 {
7556
7557 /**
7558 * The backing map.
7559 */
7560 private Map<E,Boolean> map;
7561
7562 /**
7563 * Constructs a new {@link MapSet} using the specified
7564 * backing {@link Map}.
7565 *
7566 * @param map the backing map.
7567 * @throws IllegalArgumentException if the map is not empty.
7568 */
7569 public MapSet(Map<E,Boolean> map)
7570 {
7571 if (!map.isEmpty())
7572 throw new IllegalArgumentException("The map must be empty.");
7573 this.map = map;
7574 }
7575
7576 public boolean add(E e)
7577 {
7578 return map.put(e, true) == null;
7579 }
7580
7581 public boolean addAll(Collection<? extends E> c)
7582 {
7583 boolean result = false;
7584 final Iterator<? extends E> it = c.iterator();
7585 while (it.hasNext())
7586 result |= (map.put(it.next(), true) == null);
7587 return result;
7588 }
7589
7590 public void clear()
7591 {
7592 map.clear();
7593 }
7594
7595 public boolean contains(Object o)
7596 {
7597 return map.containsKey(o);
7598 }
7599
7600 public boolean isEmpty()
7601 {
7602 return map.isEmpty();
7603 }
7604
7605 public Iterator<E> iterator()
7606 {
7607 return map.keySet().iterator();
7608 }
7609
7610 public boolean remove(Object o)
7611 {
7612 return map.remove(o) != null;
7613 }
7614
7615 public int size()
7616 {
7617 return map.size();
7618 }
7619 } // class MapSet
7620
7621 } // class Collections