0001: /*
0002: * @(#)Collections.java 1.52 06/10/10
0003: *
0004: * Copyright 1990-2006 Sun Microsystems, Inc. All Rights Reserved.
0005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
0006: *
0007: * This program is free software; you can redistribute it and/or
0008: * modify it under the terms of the GNU General Public License version
0009: * 2 only, as published by the Free Software Foundation.
0010: *
0011: * This program is distributed in the hope that it will be useful, but
0012: * WITHOUT ANY WARRANTY; without even the implied warranty of
0013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
0014: * General Public License version 2 for more details (a copy is
0015: * included at /legal/license.txt).
0016: *
0017: * You should have received a copy of the GNU General Public License
0018: * version 2 along with this work; if not, write to the Free Software
0019: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
0020: * 02110-1301 USA
0021: *
0022: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
0023: * Clara, CA 95054 or visit www.sun.com if you need additional
0024: * information or have any questions.
0025: *
0026: */
0027:
0028: package java.util;
0029:
0030: import java.io.Serializable;
0031:
0032: /**
0033: * This class consists exclusively of static methods that operate on or return
0034: * collections. It contains polymorphic algorithms that operate on
0035: * collections, "wrappers", which return a new collection backed by a
0036: * specified collection, and a few other odds and ends.
0037: *
0038: * <p>The methods of this class all throw a <tt>NullPointerException</tt>
0039: * if the collections provided to them are null.
0040: *
0041: * <p>The documentation for the polymorphic algorithms contained in this class
0042: * generally includes a brief description of the <i>implementation</i>. Such
0043: * descriptions should be regarded as <i>implementation notes</i>, rather than
0044: * parts of the <i>specification</i>. Implementors should feel free to
0045: * substitute other algorithms, so long as the specification itself is adhered
0046: * to. (For example, the algorithm used by <tt>sort</tt> does not have to be
0047: * a mergesort, but it does have to be <i>stable</i>.)
0048: *
0049: * <p>The "destructive" algorithms contained in this class, that is, the
0050: * algorithms that modify the collection on which they operate, are specified
0051: * to throw <tt>UnsupportedOperationException</tt> if the collection does not
0052: * support the appropriate mutation primitive(s), such as the <tt>set</tt>
0053: * method. These algorithms may, but are not required to, throw this
0054: * exception if an invocation would have no effect on the collection. For
0055: * example, invoking the <tt>sort</tt> method on an unmodifiable list that is
0056: * already sorted may or may not throw <tt>UnsupportedOperationException</tt>.
0057: *
0058: * <p>This class is a member of the
0059: * <a href="{@docRoot}/../guide/collections/index.html">
0060: * Java Collections Framework</a>.
0061: *
0062: * @author Josh Bloch
0063: * @version 1.45, 02/17/00
0064: * @see Collection
0065: * @see Set
0066: * @see List
0067: * @see Map
0068: * @since 1.2
0069: */
0070:
0071: public class Collections {
0072: // Suppresses default constructor, ensuring non-instantiability.
0073: private Collections() {
0074: }
0075:
0076: // Algorithms
0077:
0078: /*
0079: * Tuning parameters for algorithms - Many of the List algorithms have
0080: * two implementations, one of which is appropriate for RandomAccess
0081: * lists, the other for "sequential." Often, the random access variant
0082: * yields better performance on small sequential access lists. The
0083: * tuning parameters below determine the cutoff point for what constitutes
0084: * a "small" sequential access list for each algorithm. The values below
0085: * were empirically determined to work well for LinkedList. Hopefully
0086: * they should be reasonable for other sequential access List
0087: * implementations. Those doing performance work on this code would
0088: * do well to validate the values of these parameters from time to time.
0089: * (The first word of each tuning parameter name is the algorithm to which
0090: * it applies.)
0091: */
0092: private static final int BINARYSEARCH_THRESHOLD = 5000;
0093: private static final int REVERSE_THRESHOLD = 18;
0094: private static final int SHUFFLE_THRESHOLD = 5;
0095: private static final int FILL_THRESHOLD = 25;
0096: private static final int ROTATE_THRESHOLD = 100;
0097: private static final int COPY_THRESHOLD = 10;
0098: private static final int REPLACEALL_THRESHOLD = 11;
0099: private static final int INDEXOFSUBLIST_THRESHOLD = 35;
0100:
0101: /**
0102: * Sorts the specified list into ascending order, according to the
0103: * <i>natural ordering</i> of its elements. All elements in the list must
0104: * implement the <tt>Comparable</tt> interface. Furthermore, all elements
0105: * in the list must be <i>mutually comparable</i> (that is,
0106: * <tt>e1.compareTo(e2)</tt> must not throw a <tt>ClassCastException</tt>
0107: * for any elements <tt>e1</tt> and <tt>e2</tt> in the list).<p>
0108: *
0109: * This sort is guaranteed to be <i>stable</i>: equal elements will
0110: * not be reordered as a result of the sort.<p>
0111: *
0112: * The specified list must be modifiable, but need not be resizable.<p>
0113: *
0114: * The sorting algorithm is a modified mergesort (in which the merge is
0115: * omitted if the highest element in the low sublist is less than the
0116: * lowest element in the high sublist). This algorithm offers guaranteed
0117: * n log(n) performance.
0118: *
0119: * This implementation dumps the specified list into an array, sorts
0120: * the array, and iterates over the list resetting each element
0121: * from the corresponding position in the array. This avoids the
0122: * n<sup>2</sup> log(n) performance that would result from attempting
0123: * to sort a linked list in place.
0124: *
0125: * @param list the list to be sorted.
0126: * @throws ClassCastException if the list contains elements that are not
0127: * <i>mutually comparable</i> (for example, strings and integers).
0128: * @throws UnsupportedOperationException if the specified list's
0129: * list-iterator does not support the <tt>set</tt> operation.
0130: * @see Comparable
0131: */
0132: public static void sort(List list) {
0133: Object a[] = list.toArray();
0134: Arrays.sort(a);
0135: ListIterator i = list.listIterator();
0136: for (int j = 0; j < a.length; j++) {
0137: i.next();
0138: i.set(a[j]);
0139: }
0140: }
0141:
0142: /**
0143: * Sorts the specified list according to the order induced by the
0144: * specified comparator. All elements in the list must be <i>mutually
0145: * comparable</i> using the specified comparator (that is,
0146: * <tt>c.compare(e1, e2)</tt> must not throw a <tt>ClassCastException</tt>
0147: * for any elements <tt>e1</tt> and <tt>e2</tt> in the list).<p>
0148: *
0149: * This sort is guaranteed to be <i>stable</i>: equal elements will
0150: * not be reordered as a result of the sort.<p>
0151: *
0152: * The sorting algorithm is a modified mergesort (in which the merge is
0153: * omitted if the highest element in the low sublist is less than the
0154: * lowest element in the high sublist). This algorithm offers guaranteed
0155: * n log(n) performance.
0156: *
0157: * The specified list must be modifiable, but need not be resizable.
0158: * This implementation dumps the specified list into an array, sorts
0159: * the array, and iterates over the list resetting each element
0160: * from the corresponding position in the array. This avoids the
0161: * n<sup>2</sup> log(n) performance that would result from attempting
0162: * to sort a linked list in place.
0163: *
0164: * @param list the list to be sorted.
0165: * @param c the comparator to determine the order of the list. A
0166: * <tt>null</tt> value indicates that the elements' <i>natural
0167: * ordering</i> should be used.
0168: * @throws ClassCastException if the list contains elements that are not
0169: * <i>mutually comparable</i> using the specified comparator.
0170: * @throws UnsupportedOperationException if the specified list's
0171: * list-iterator does not support the <tt>set</tt> operation.
0172: * @see Comparator
0173: */
0174: public static void sort(List list, Comparator c) {
0175: Object a[] = list.toArray();
0176: Arrays.sort(a, c);
0177: ListIterator i = list.listIterator();
0178: for (int j = 0; j < a.length; j++) {
0179: i.next();
0180: i.set(a[j]);
0181: }
0182: }
0183:
0184: /**
0185: * Searches the specified list for the specified object using the binary
0186: * search algorithm. The list must be sorted into ascending order
0187: * according to the <i>natural ordering</i> of its elements (as by the
0188: * <tt>sort(List)</tt> method, above) prior to making this call. If it is
0189: * not sorted, the results are undefined. If the list contains multiple
0190: * elements equal to the specified object, there is no guarantee which one
0191: * will be found.<p>
0192: *
0193: * This method runs in log(n) time for a "random access" list (which
0194: * provides near-constant-time positional access). If the specified list
0195: * does not implement the {@link RandomAccess} and is large, this method
0196: * will do an iterator-based binary search that performs O(n) link
0197: * traversals and O(log n) element comparisons.
0198: *
0199: * @param list the list to be searched.
0200: * @param key the key to be searched for.
0201: * @return index of the search key, if it is contained in the list;
0202: * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
0203: * <i>insertion point</i> is defined as the point at which the
0204: * key would be inserted into the list: the index of the first
0205: * element greater than the key, or <tt>list.size()</tt>, if all
0206: * elements in the list are less than the specified key. Note
0207: * that this guarantees that the return value will be >= 0 if
0208: * and only if the key is found.
0209: * @throws ClassCastException if the list contains elements that are not
0210: * <i>mutually comparable</i> (for example, strings and
0211: * integers), or the search key in not mutually comparable
0212: * with the elements of the list.
0213: * @see Comparable
0214: * @see #sort(List)
0215: */
0216: public static int binarySearch(List list, Object key) {
0217: if (list instanceof RandomAccess
0218: || list.size() < BINARYSEARCH_THRESHOLD)
0219: return indexedBinarySearch(list, key);
0220: else
0221: return iteratorBinarySearch(list, key);
0222: }
0223:
0224: private static int indexedBinarySearch(List list, Object key) {
0225: int low = 0;
0226: int high = list.size() - 1;
0227:
0228: while (low <= high) {
0229: int mid = (low + high) >> 1;
0230: Object midVal = list.get(mid);
0231: int cmp = ((Comparable) midVal).compareTo(key);
0232:
0233: if (cmp < 0)
0234: low = mid + 1;
0235: else if (cmp > 0)
0236: high = mid - 1;
0237: else
0238: return mid; // key found
0239: }
0240: return -(low + 1); // key not found
0241: }
0242:
0243: private static int iteratorBinarySearch(List list, Object key) {
0244: int low = 0;
0245: int high = list.size() - 1;
0246: ListIterator i = list.listIterator();
0247:
0248: while (low <= high) {
0249: int mid = (low + high) >> 1;
0250: Object midVal = get(i, mid);
0251: int cmp = ((Comparable) midVal).compareTo(key);
0252:
0253: if (cmp < 0)
0254: low = mid + 1;
0255: else if (cmp > 0)
0256: high = mid - 1;
0257: else
0258: return mid; // key found
0259: }
0260: return -(low + 1); // key not found
0261: }
0262:
0263: /**
0264: * Gets the ith element from the given list by repositioning the specified
0265: * list listIterator.
0266: */
0267: private static Object get(ListIterator i, int index) {
0268: Object obj = null;
0269: int pos = i.nextIndex();
0270: if (pos <= index) {
0271: do {
0272: obj = i.next();
0273: } while (pos++ < index);
0274: } else {
0275: do {
0276: obj = i.previous();
0277: } while (--pos > index);
0278: }
0279: return obj;
0280: }
0281:
0282: /**
0283: * Searches the specified list for the specified object using the binary
0284: * search algorithm. The list must be sorted into ascending order
0285: * according to the specified comparator (as by the <tt>Sort(List,
0286: * Comparator)</tt> method, above), prior to making this call. If it is
0287: * not sorted, the results are undefined. If the list contains multiple
0288: * elements equal to the specified object, there is no guarantee which one
0289: * will be found.<p>
0290: *
0291: * This method runs in log(n) time for a "random access" list (which
0292: * provides near-constant-time positional access). If the specified list
0293: * does not implement the {@link RandomAccess} and is large, this
0294: * this method will do an iterator-based binary search that performs
0295: * O(n) link traversals and O(log n) element comparisons.
0296: *
0297: * @param list the list to be searched.
0298: * @param key the key to be searched for.
0299: * @param c the comparator by which the list is ordered. A
0300: * <tt>null</tt> value indicates that the elements' <i>natural
0301: * ordering</i> should be used.
0302: * @return index of the search key, if it is contained in the list;
0303: * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
0304: * <i>insertion point</i> is defined as the point at which the
0305: * key would be inserted into the list: the index of the first
0306: * element greater than the key, or <tt>list.size()</tt>, if all
0307: * elements in the list are less than the specified key. Note
0308: * that this guarantees that the return value will be >= 0 if
0309: * and only if the key is found.
0310: * @throws ClassCastException if the list contains elements that are not
0311: * <i>mutually comparable</i> using the specified comparator,
0312: * or the search key in not mutually comparable with the
0313: * elements of the list using this comparator.
0314: * @see Comparable
0315: * @see #sort(List, Comparator)
0316: */
0317: public static int binarySearch(List list, Object key, Comparator c) {
0318: if (c == null)
0319: return binarySearch(list, key);
0320:
0321: if (list instanceof RandomAccess
0322: || list.size() < BINARYSEARCH_THRESHOLD)
0323: return indexedBinarySearch(list, key, c);
0324: else
0325: return iteratorBinarySearch(list, key, c);
0326: }
0327:
0328: private static int indexedBinarySearch(List l, Object key,
0329: Comparator c) {
0330: int low = 0;
0331: int high = l.size() - 1;
0332:
0333: while (low <= high) {
0334: int mid = (low + high) >> 1;
0335: Object midVal = l.get(mid);
0336: int cmp = c.compare(midVal, key);
0337:
0338: if (cmp < 0)
0339: low = mid + 1;
0340: else if (cmp > 0)
0341: high = mid - 1;
0342: else
0343: return mid; // key found
0344: }
0345: return -(low + 1); // key not found
0346: }
0347:
0348: private static int iteratorBinarySearch(List l, Object key,
0349: Comparator c) {
0350: int low = 0;
0351: int high = l.size() - 1;
0352: ListIterator i = l.listIterator();
0353:
0354: while (low <= high) {
0355: int mid = (low + high) >> 1;
0356: Object midVal = get(i, mid);
0357: int cmp = c.compare(midVal, key);
0358:
0359: if (cmp < 0)
0360: low = mid + 1;
0361: else if (cmp > 0)
0362: high = mid - 1;
0363: else
0364: return mid; // key found
0365: }
0366: return -(low + 1); // key not found
0367: }
0368:
0369: /**
0370: * Reverses the order of the elements in the specified list.<p>
0371: *
0372: * This method runs in linear time.
0373: *
0374: * @param list the list whose elements are to be reversed.
0375: * @throws UnsupportedOperationException if the specified list or
0376: * its list-iterator does not support the <tt>set</tt> method.
0377: */
0378: public static void reverse(List list) {
0379: int size = list.size();
0380: if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {
0381: for (int i = 0, mid = size >> 1, j = size - 1; i < mid; i++, j--)
0382: swap(list, i, j);
0383: } else {
0384: ListIterator fwd = list.listIterator();
0385: ListIterator rev = list.listIterator(size);
0386: for (int i = 0, mid = list.size() >> 1; i < mid; i++) {
0387: Object tmp = fwd.next();
0388: fwd.set(rev.previous());
0389: rev.set(tmp);
0390: }
0391: }
0392: }
0393:
0394: /**
0395: * Randomly permutes the specified list using a default source of
0396: * randomness. All permutations occur with approximately equal
0397: * likelihood.<p>
0398: *
0399: * The hedge "approximately" is used in the foregoing description because
0400: * default source of randomenss is only approximately an unbiased source
0401: * of independently chosen bits. If it were a perfect source of randomly
0402: * chosen bits, then the algorithm would choose permutations with perfect
0403: * uniformity.<p>
0404: *
0405: * This implementation traverses the list backwards, from the last element
0406: * up to the second, repeatedly swapping a randomly selected element into
0407: * the "current position". Elements are randomly selected from the
0408: * portion of the list that runs from the first element to the current
0409: * position, inclusive.<p>
0410: *
0411: * This method runs in linear time. If the specified list does not
0412: * implement the {@link RandomAccess} interface and is large, this
0413: * implementation dumps the specified list into an array before shuffling
0414: * it, and dumps the shuffled array back into the list. This avoids the
0415: * quadratic behavior that would result from shuffling a "sequential
0416: * access" list in place.
0417: *
0418: * @param list the list to be shuffled.
0419: * @throws UnsupportedOperationException if the specified list or
0420: * its list-iterator does not support the <tt>set</tt> method.
0421: */
0422: public static void shuffle(List list) {
0423: shuffle(list, r);
0424: }
0425:
0426: private static Random r = new Random();
0427:
0428: /**
0429: * Randomly permute the specified list using the specified source of
0430: * randomness. All permutations occur with equal likelihood
0431: * assuming that the source of randomness is fair.<p>
0432: *
0433: * This implementation traverses the list backwards, from the last element
0434: * up to the second, repeatedly swapping a randomly selected element into
0435: * the "current position". Elements are randomly selected from the
0436: * portion of the list that runs from the first element to the current
0437: * position, inclusive.<p>
0438: *
0439: * This method runs in linear time. If the specified list does not
0440: * implement the {@link RandomAccess} interface and is large, this
0441: * implementation dumps the specified list into an array before shuffling
0442: * it, and dumps the shuffled array back into the list. This avoids the
0443: * quadratic behavior that would result from shuffling a "sequential
0444: * access" list in place.
0445: *
0446: * @param list the list to be shuffled.
0447: * @param rnd the source of randomness to use to shuffle the list.
0448: * @throws UnsupportedOperationException if the specified list or its
0449: * list-iterator does not support the <tt>set</tt> operation.
0450: */
0451: public static void shuffle(List list, Random rnd) {
0452: int size = list.size();
0453: if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
0454: for (int i = size; i > 1; i--)
0455: swap(list, i - 1, rnd.nextInt(i));
0456: } else {
0457: Object arr[] = list.toArray();
0458:
0459: // Shuffle array
0460: for (int i = size; i > 1; i--)
0461: swap(arr, i - 1, rnd.nextInt(i));
0462:
0463: // Dump array back into list
0464: ListIterator it = list.listIterator();
0465: for (int i = 0; i < arr.length; i++) {
0466: it.next();
0467: it.set(arr[i]);
0468: }
0469: }
0470: }
0471:
0472: /**
0473: * Swaps the elements at the specified positions in the specified list.
0474: * (If the specified positions are equal, invoking this method leaves
0475: * the list unchanged.)
0476: *
0477: * @param list The list in which to swap elements.
0478: * @param i the index of one element to be swapped.
0479: * @param j the index of the other element to be swapped.
0480: * @throws IndexOutOfBoundsException if either <tt>i</tt> or <tt>j</tt>
0481: * is out of range (i < 0 || i >= list.size()
0482: * || j < 0 || j >= list.size()).
0483: * @since 1.4
0484: */
0485: public static void swap(List list, int i, int j) {
0486: list.set(i, list.set(j, list.get(i)));
0487: }
0488:
0489: /**
0490: * Swaps the two specified elements in the specified array.
0491: */
0492: private static void swap(Object[] arr, int i, int j) {
0493: Object tmp = arr[i];
0494: arr[i] = arr[j];
0495: arr[j] = tmp;
0496: }
0497:
0498: /**
0499: * Replaces all of the elements of the specified list with the specified
0500: * element. <p>
0501: *
0502: * This method runs in linear time.
0503: *
0504: * @param list the list to be filled with the specified element.
0505: * @param obj The element with which to fill the specified list.
0506: * @throws UnsupportedOperationException if the specified list or its
0507: * list-iterator does not support the <tt>set</tt> operation.
0508: */
0509: public static void fill(List list, Object obj) {
0510: int size = list.size();
0511:
0512: if (size < FILL_THRESHOLD || list instanceof RandomAccess) {
0513: for (int i = 0; i < size; i++)
0514: list.set(i, obj);
0515: } else {
0516: ListIterator itr = list.listIterator();
0517: for (int i = 0; i < size; i++) {
0518: itr.next();
0519: itr.set(obj);
0520: }
0521: }
0522: }
0523:
0524: /**
0525: * Copies all of the elements from one list into another. After the
0526: * operation, the index of each copied element in the destination list
0527: * will be identical to its index in the source list. The destination
0528: * list must be at least as long as the source list. If it is longer, the
0529: * remaining elements in the destination list are unaffected. <p>
0530: *
0531: * This method runs in linear time.
0532: *
0533: * @param dest The destination list.
0534: * @param src The source list.
0535: * @throws IndexOutOfBoundsException if the destination list is too small
0536: * to contain the entire source List.
0537: * @throws UnsupportedOperationException if the destination list's
0538: * list-iterator does not support the <tt>set</tt> operation.
0539: */
0540: public static void copy(List dest, List src) {
0541: int srcSize = src.size();
0542: if (srcSize > dest.size())
0543: throw new IndexOutOfBoundsException(
0544: "Source does not fit in dest");
0545:
0546: if (srcSize < COPY_THRESHOLD
0547: || (src instanceof RandomAccess && dest instanceof RandomAccess)) {
0548: for (int i = 0; i < srcSize; i++)
0549: dest.set(i, src.get(i));
0550: } else {
0551: ListIterator di = dest.listIterator(), si = src
0552: .listIterator();
0553: for (int i = 0; i < srcSize; i++) {
0554: di.next();
0555: di.set(si.next());
0556: }
0557: }
0558: }
0559:
0560: /**
0561: * Returns the minimum element of the given collection, according to the
0562: * <i>natural ordering</i> of its elements. All elements in the
0563: * collection must implement the <tt>Comparable</tt> interface.
0564: * Furthermore, all elements in the collection must be <i>mutually
0565: * comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a
0566: * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
0567: * <tt>e2</tt> in the collection).<p>
0568: *
0569: * This method iterates over the entire collection, hence it requires
0570: * time proportional to the size of the collection.
0571: *
0572: * @param coll the collection whose minimum element is to be determined.
0573: * @return the minimum element of the given collection, according
0574: * to the <i>natural ordering</i> of its elements.
0575: * @throws ClassCastException if the collection contains elements that are
0576: * not <i>mutually comparable</i> (for example, strings and
0577: * integers).
0578: * @throws NoSuchElementException if the collection is empty.
0579: * @see Comparable
0580: */
0581: public static Object min(Collection coll) {
0582: Iterator i = coll.iterator();
0583: Comparable candidate = (Comparable) (i.next());
0584:
0585: while (i.hasNext()) {
0586: Comparable next = (Comparable) (i.next());
0587: if (next.compareTo(candidate) < 0)
0588: candidate = next;
0589: }
0590: return candidate;
0591: }
0592:
0593: /**
0594: * Returns the minimum element of the given collection, according to the
0595: * order induced by the specified comparator. All elements in the
0596: * collection must be <i>mutually comparable</i> by the specified
0597: * comparator (that is, <tt>comp.compare(e1, e2)</tt> must not throw a
0598: * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
0599: * <tt>e2</tt> in the collection).<p>
0600: *
0601: * This method iterates over the entire collection, hence it requires
0602: * time proportional to the size of the collection.
0603: *
0604: * @param coll the collection whose minimum element is to be determined.
0605: * @param comp the comparator with which to determine the minimum element.
0606: * A <tt>null</tt> value indicates that the elements' <i>natural
0607: * ordering</i> should be used.
0608: * @return the minimum element of the given collection, according
0609: * to the specified comparator.
0610: * @throws ClassCastException if the collection contains elements that are
0611: * not <i>mutually comparable</i> using the specified comparator.
0612: * @throws NoSuchElementException if the collection is empty.
0613: * @see Comparable
0614: */
0615: public static Object min(Collection coll, Comparator comp) {
0616: if (comp == null)
0617: return min(coll);
0618:
0619: Iterator i = coll.iterator();
0620: Object candidate = i.next();
0621:
0622: while (i.hasNext()) {
0623: Object next = i.next();
0624: if (comp.compare(next, candidate) < 0)
0625: candidate = next;
0626: }
0627: return candidate;
0628: }
0629:
0630: /**
0631: * Returns the maximum element of the given collection, according to the
0632: * <i>natural ordering</i> of its elements. All elements in the
0633: * collection must implement the <tt>Comparable</tt> interface.
0634: * Furthermore, all elements in the collection must be <i>mutually
0635: * comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a
0636: * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
0637: * <tt>e2</tt> in the collection).<p>
0638: *
0639: * This method iterates over the entire collection, hence it requires
0640: * time proportional to the size of the collection.
0641: *
0642: * @param coll the collection whose maximum element is to be determined.
0643: * @return the maximum element of the given collection, according
0644: * to the <i>natural ordering</i> of its elements.
0645: * @throws ClassCastException if the collection contains elements that are
0646: * not <i>mutually comparable</i> (for example, strings and
0647: * integers).
0648: * @throws NoSuchElementException if the collection is empty.
0649: * @see Comparable
0650: */
0651: public static Object max(Collection coll) {
0652: Iterator i = coll.iterator();
0653: Comparable candidate = (Comparable) (i.next());
0654:
0655: while (i.hasNext()) {
0656: Comparable next = (Comparable) (i.next());
0657: if (next.compareTo(candidate) > 0)
0658: candidate = next;
0659: }
0660: return candidate;
0661: }
0662:
0663: /**
0664: * Returns the maximum element of the given collection, according to the
0665: * order induced by the specified comparator. All elements in the
0666: * collection must be <i>mutually comparable</i> by the specified
0667: * comparator (that is, <tt>comp.compare(e1, e2)</tt> must not throw a
0668: * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
0669: * <tt>e2</tt> in the collection).<p>
0670: *
0671: * This method iterates over the entire collection, hence it requires
0672: * time proportional to the size of the collection.
0673: *
0674: * @param coll the collection whose maximum element is to be determined.
0675: * @param comp the comparator with which to determine the maximum element.
0676: * A <tt>null</tt> value indicates that the elements' <i>natural
0677: * ordering</i> should be used.
0678: * @return the maximum element of the given collection, according
0679: * to the specified comparator.
0680: * @throws ClassCastException if the collection contains elements that are
0681: * not <i>mutually comparable</i> using the specified comparator.
0682: * @throws NoSuchElementException if the collection is empty.
0683: * @see Comparable
0684: */
0685: public static Object max(Collection coll, Comparator comp) {
0686: if (comp == null)
0687: return max(coll);
0688:
0689: Iterator i = coll.iterator();
0690: Object candidate = i.next();
0691:
0692: while (i.hasNext()) {
0693: Object next = i.next();
0694: if (comp.compare(next, candidate) > 0)
0695: candidate = next;
0696: }
0697: return candidate;
0698: }
0699:
0700: /**
0701: * Rotates the elements in the specified list by the specified distance.
0702: * After calling this method, the element at index <tt>i</tt> will be
0703: * the element previously at index <tt>(i - distance)</tt> mod
0704: * <tt>list.size()</tt>, for all values of <tt>i</tt> between <tt>0</tt>
0705: * and <tt>list.size()-1</tt>, inclusive. (This method has no effect on
0706: * the size of the list.)
0707: *
0708: * <p>For example, suppose <tt>list</tt> comprises<tt> [t, a, n, k, s]</tt>.
0709: * After invoking <tt>Collections.rotate(list, 1)</tt> (or
0710: * <tt>Collections.rotate(list, -4)</tt>), <tt>list</tt> will comprise
0711: * <tt>[s, t, a, n, k]</tt>.
0712: *
0713: * <p>Note that this method can usefully be applied to sublists to
0714: * move one or more elements within a list while preserving the
0715: * order of the remaining elements. For example, the following idiom
0716: * moves the element at index <tt>j</tt> forward to position
0717: * <tt>k</tt> (which must be greater than or equal to <tt>j</tt>):
0718: * <pre>
0719: * Collections.rotate(list.subList(j, k+1), -1);
0720: * </pre>
0721: * To make this concrete, suppose <tt>list</tt> comprises
0722: * <tt>[a, b, c, d, e]</tt>. To move the element at index <tt>1</tt>
0723: * (<tt>b</tt>) forward two positions, perform the following invocation:
0724: * <pre>
0725: * Collections.rotate(l.subList(1, 4), -1);
0726: * </pre>
0727: * The resulting list is <tt>[a, c, d, b, e]</tt>.
0728: *
0729: * <p>To move more than one element forward, increase the absolute value
0730: * of the rotation distance. To move elements backward, use a positive
0731: * shift distance.
0732: *
0733: * <p>If the specified list is small or implements the {@link
0734: * RandomAccess} interface, this implementation exchanges the first
0735: * element into the location it should go, and then repeatedly exchanges
0736: * the displaced element into the location it should go until a displaced
0737: * element is swapped into the first element. If necessary, the process
0738: * is repeated on the second and successive elements, until the rotation
0739: * is complete. If the specified list is large and doesn't implement the
0740: * <tt>RandomAccess</tt> interface, this implementation breaks the
0741: * list into two sublist views around index <tt>-distance mod size</tt>.
0742: * Then the {@link #reverse(List)} method is invoked on each sublist view,
0743: * and finally it is invoked on the entire list. For a more complete
0744: * description of both algorithms, see Section 2.3 of Jon Bentley's
0745: * <i>Programming Pearls</i> (Addison-Wesley, 1986).
0746: *
0747: * @param list the list to be rotated.
0748: * @param distance the distance to rotate the list. There are no
0749: * constraints on this value; it may be zero, negative, or
0750: * greater than <tt>list.size()</tt>.
0751: * @throws UnsupportedOperationException if the specified list or
0752: * its list-iterator does not support the <tt>set</tt> method.
0753: * @since 1.4
0754: */
0755: public static void rotate(List list, int distance) {
0756: if (list instanceof RandomAccess
0757: || list.size() < ROTATE_THRESHOLD)
0758: rotate1(list, distance);
0759: else
0760: rotate2(list, distance);
0761: }
0762:
0763: private static void rotate1(List list, int distance) {
0764: int size = list.size();
0765: if (size == 0)
0766: return;
0767: distance = distance % size;
0768: if (distance < 0)
0769: distance += size;
0770: if (distance == 0)
0771: return;
0772:
0773: for (int cycleStart = 0, nMoved = 0; nMoved != size; cycleStart++) {
0774: Object displaced = list.get(cycleStart);
0775: int i = cycleStart;
0776: do {
0777: i += distance;
0778: if (i >= size)
0779: i -= size;
0780: displaced = list.set(i, displaced);
0781: nMoved++;
0782: } while (i != cycleStart);
0783: }
0784: }
0785:
0786: private static void rotate2(List list, int distance) {
0787: int size = list.size();
0788: if (size == 0)
0789: return;
0790: int mid = -distance % size;
0791: if (mid < 0)
0792: mid += size;
0793: if (mid == 0)
0794: return;
0795:
0796: Collections.reverse(list.subList(0, mid));
0797: Collections.reverse(list.subList(mid, size));
0798: Collections.reverse(list);
0799: }
0800:
0801: /**
0802: * Replaces all occurrences of one specified value in a list with another.
0803: * More formally, replaces with <tt>newVal</tt> each element <tt>e</tt>
0804: * in <tt>list</tt> such that
0805: * <tt>(oldVal==null ? e==null : oldVal.equals(e))</tt>.
0806: * (This method has no effect on the size of the list.)
0807: *
0808: * @param list the list in which replacement is to occur.
0809: * @param oldVal the old value to be replaced.
0810: * @param newVal the new value with which <tt>oldVal</tt> is to be
0811: * replaced.
0812: * @return <tt>true</tt> if <tt>list</tt> contained one or more elements
0813: * <tt>e</tt> such that
0814: * <tt>(oldVal==null ? e==null : oldVal.equals(e))</tt>.
0815: * @throws UnsupportedOperationException if the specified list or
0816: * its list-iterator does not support the <tt>set</tt> method.
0817: * @since 1.4
0818: */
0819: public static boolean replaceAll(List list, Object oldVal,
0820: Object newVal) {
0821: boolean result = false;
0822: int size = list.size();
0823: if (size < REPLACEALL_THRESHOLD || list instanceof RandomAccess) {
0824: if (oldVal == null) {
0825: for (int i = 0; i < size; i++) {
0826: if (list.get(i) == null) {
0827: list.set(i, newVal);
0828: result = true;
0829: }
0830: }
0831: } else {
0832: for (int i = 0; i < size; i++) {
0833: if (oldVal.equals(list.get(i))) {
0834: list.set(i, newVal);
0835: result = true;
0836: }
0837: }
0838: }
0839: } else {
0840: ListIterator itr = list.listIterator();
0841: if (oldVal == null) {
0842: for (int i = 0; i < size; i++) {
0843: if (itr.next() == null) {
0844: itr.set(newVal);
0845: result = true;
0846: }
0847: }
0848: } else {
0849: for (int i = 0; i < size; i++) {
0850: if (oldVal.equals(itr.next())) {
0851: itr.set(newVal);
0852: result = true;
0853: }
0854: }
0855: }
0856: }
0857: return result;
0858: }
0859:
0860: /**
0861: * Returns the starting position of the first occurrence of the specified
0862: * target list within the specified source list, or -1 if there is no
0863: * such occurrence. More formally, returns the the lowest index <tt>i</tt>
0864: * such that <tt>source.subList(i, i+target.size()).equals(target)</tt>,
0865: * or -1 if there is no such index. (Returns -1 if
0866: * <tt>target.size() > source.size()</tt>.)
0867: *
0868: * <p>This implementation uses the "brute force" technique of scanning
0869: * over the source list, looking for a match with the target at each
0870: * location in turn.
0871: *
0872: * @param source the list in which to search for the first occurrence
0873: * of <tt>target</tt>.
0874: * @param target the list to search for as a subList of <tt>source</tt>.
0875: * @return the starting position of the first occurrence of the specified
0876: * target list within the specified source list, or -1 if there
0877: * is no such occurrence.
0878: * @since 1.4
0879: */
0880: public static int indexOfSubList(List source, List target) {
0881: int sourceSize = source.size();
0882: int targetSize = target.size();
0883: int maxCandidate = sourceSize - targetSize;
0884:
0885: if (sourceSize < INDEXOFSUBLIST_THRESHOLD
0886: || (source instanceof RandomAccess && target instanceof RandomAccess)) {
0887: nextCand: for (int candidate = 0; candidate <= maxCandidate; candidate++) {
0888: for (int i = 0, j = candidate; i < targetSize; i++, j++)
0889: if (!eq(target.get(i), source.get(j)))
0890: continue nextCand; // Element mismatch, try next cand
0891: return candidate; // All elements of candidate matched target
0892: }
0893: } else { // Iterator version of above algorithm
0894: ListIterator si = source.listIterator();
0895: nextCand: for (int candidate = 0; candidate <= maxCandidate; candidate++) {
0896: ListIterator ti = target.listIterator();
0897: for (int i = 0; i < targetSize; i++) {
0898: if (!eq(ti.next(), si.next())) {
0899: // Back up source iterator to next candidate
0900: for (int j = 0; j < i; j++)
0901: si.previous();
0902: continue nextCand;
0903: }
0904: }
0905: return candidate;
0906: }
0907: }
0908: return -1; // No candidate matched the target
0909: }
0910:
0911: /**
0912: * Returns the starting position of the last occurrence of the specified
0913: * target list within the specified source list, or -1 if there is no such
0914: * occurrence. More formally, returns the the highest index <tt>i</tt>
0915: * such that <tt>source.subList(i, i+target.size()).equals(target)</tt>,
0916: * or -1 if there is no such index. (Returns -1 if
0917: * <tt>target.size() > source.size()</tt>.)
0918: *
0919: * <p>This implementation uses the "brute force" technique of iterating
0920: * over the source list, looking for a match with the target at each
0921: * location in turn.
0922: *
0923: * @param source the list in which to search for the last occurrence
0924: * of <tt>target</tt>.
0925: * @param target the list to search for as a subList of <tt>source</tt>.
0926: * @return the starting position of the last occurrence of the specified
0927: * target list within the specified source list, or -1 if there
0928: * is no such occurrence.
0929: * @since 1.4
0930: */
0931: public static int lastIndexOfSubList(List source, List target) {
0932: int sourceSize = source.size();
0933: int targetSize = target.size();
0934: int maxCandidate = sourceSize - targetSize;
0935:
0936: if (sourceSize < INDEXOFSUBLIST_THRESHOLD
0937: || source instanceof RandomAccess) { // Index access version
0938: nextCand: for (int candidate = maxCandidate; candidate >= 0; candidate--) {
0939: for (int i = 0, j = candidate; i < targetSize; i++, j++)
0940: if (!eq(target.get(i), source.get(j)))
0941: continue nextCand; // Element mismatch, try next cand
0942: return candidate; // All elements of candidate matched target
0943: }
0944: } else { // Iterator version of above algorithm
0945: if (maxCandidate < 0)
0946: return -1;
0947: ListIterator si = source.listIterator(maxCandidate);
0948: nextCand: for (int candidate = maxCandidate; candidate >= 0; candidate--) {
0949: ListIterator ti = target.listIterator();
0950: for (int i = 0; i < targetSize; i++) {
0951: if (!eq(ti.next(), si.next())) {
0952: if (candidate != 0) {
0953: // Back up source iterator to next candidate
0954: for (int j = 0; j <= i + 1; j++)
0955: si.previous();
0956: }
0957: continue nextCand;
0958: }
0959: }
0960: return candidate;
0961: }
0962: }
0963: return -1; // No candidate matched the target
0964: }
0965:
0966: // Unmodifiable Wrappers
0967:
0968: /**
0969: * Returns an unmodifiable view of the specified collection. This method
0970: * allows modules to provide users with "read-only" access to internal
0971: * collections. Query operations on the returned collection "read through"
0972: * to the specified collection, and attempts to modify the returned
0973: * collection, whether direct or via its iterator, result in an
0974: * <tt>UnsupportedOperationException</tt>.<p>
0975: *
0976: * The returned collection does <i>not</i> pass the hashCode and equals
0977: * operations through to the backing collection, but relies on
0978: * <tt>Object</tt>'s <tt>equals</tt> and <tt>hashCode</tt> methods. This
0979: * is necessary to preserve the contracts of these operations in the case
0980: * that the backing collection is a set or a list.<p>
0981: *
0982: * The returned collection will be serializable if the specified collection
0983: * is serializable.
0984: *
0985: * @param c the collection for which an unmodifiable view is to be
0986: * returned.
0987: * @return an unmodifiable view of the specified collection.
0988: */
0989: public static Collection unmodifiableCollection(Collection c) {
0990: return new UnmodifiableCollection(c);
0991: }
0992:
0993: /**
0994: * @serial include
0995: */
0996: static class UnmodifiableCollection implements Collection,
0997: Serializable {
0998: // use serialVersionUID from JDK 1.2.2 for interoperability
0999: private static final long serialVersionUID = 1820017752578914078L;
1000:
1001: Collection c;
1002:
1003: UnmodifiableCollection(Collection c) {
1004: if (c == null)
1005: throw new NullPointerException();
1006: this .c = c;
1007: }
1008:
1009: public int size() {
1010: return c.size();
1011: }
1012:
1013: public boolean isEmpty() {
1014: return c.isEmpty();
1015: }
1016:
1017: public boolean contains(Object o) {
1018: return c.contains(o);
1019: }
1020:
1021: public Object[] toArray() {
1022: return c.toArray();
1023: }
1024:
1025: public Object[] toArray(Object[] a) {
1026: return c.toArray(a);
1027: }
1028:
1029: public String toString() {
1030: return c.toString();
1031: }
1032:
1033: public Iterator iterator() {
1034: return new Iterator() {
1035: Iterator i = c.iterator();
1036:
1037: public boolean hasNext() {
1038: return i.hasNext();
1039: }
1040:
1041: public Object next() {
1042: return i.next();
1043: }
1044:
1045: public void remove() {
1046: throw new UnsupportedOperationException();
1047: }
1048: };
1049: }
1050:
1051: public boolean add(Object o) {
1052: throw new UnsupportedOperationException();
1053: }
1054:
1055: public boolean remove(Object o) {
1056: throw new UnsupportedOperationException();
1057: }
1058:
1059: public boolean containsAll(Collection coll) {
1060: return c.containsAll(coll);
1061: }
1062:
1063: public boolean addAll(Collection coll) {
1064: throw new UnsupportedOperationException();
1065: }
1066:
1067: public boolean removeAll(Collection coll) {
1068: throw new UnsupportedOperationException();
1069: }
1070:
1071: public boolean retainAll(Collection coll) {
1072: throw new UnsupportedOperationException();
1073: }
1074:
1075: public void clear() {
1076: throw new UnsupportedOperationException();
1077: }
1078: }
1079:
1080: /**
1081: * Returns an unmodifiable view of the specified set. This method allows
1082: * modules to provide users with "read-only" access to internal sets.
1083: * Query operations on the returned set "read through" to the specified
1084: * set, and attempts to modify the returned set, whether direct or via its
1085: * iterator, result in an <tt>UnsupportedOperationException</tt>.<p>
1086: *
1087: * The returned set will be serializable if the specified set
1088: * is serializable.
1089: *
1090: * @param s the set for which an unmodifiable view is to be returned.
1091: * @return an unmodifiable view of the specified set.
1092: */
1093:
1094: public static Set unmodifiableSet(Set s) {
1095: return new UnmodifiableSet(s);
1096: }
1097:
1098: /**
1099: * @serial include
1100: */
1101: static class UnmodifiableSet extends UnmodifiableCollection
1102: implements Set, Serializable {
1103: UnmodifiableSet(Set s) {
1104: super (s);
1105: }
1106:
1107: public boolean equals(Object o) {
1108: return c.equals(o);
1109: }
1110:
1111: public int hashCode() {
1112: return c.hashCode();
1113: }
1114: }
1115:
1116: /**
1117: * Returns an unmodifiable view of the specified sorted set. This method
1118: * allows modules to provide users with "read-only" access to internal
1119: * sorted sets. Query operations on the returned sorted set "read
1120: * through" to the specified sorted set. Attempts to modify the returned
1121: * sorted set, whether direct, via its iterator, or via its
1122: * <tt>subSet</tt>, <tt>headSet</tt>, or <tt>tailSet</tt> views, result in
1123: * an <tt>UnsupportedOperationException</tt>.<p>
1124: *
1125: * The returned sorted set will be serializable if the specified sorted set
1126: * is serializable.
1127: *
1128: * @param s the sorted set for which an unmodifiable view is to be
1129: * returned.
1130: * @return an unmodifiable view of the specified sorted set.
1131: */
1132: public static SortedSet unmodifiableSortedSet(SortedSet s) {
1133: return new UnmodifiableSortedSet(s);
1134: }
1135:
1136: /**
1137: * @serial include
1138: */
1139: static class UnmodifiableSortedSet extends UnmodifiableSet
1140: implements SortedSet, Serializable {
1141: private SortedSet ss;
1142:
1143: UnmodifiableSortedSet(SortedSet s) {
1144: super (s);
1145: ss = s;
1146: }
1147:
1148: public Comparator comparator() {
1149: return ss.comparator();
1150: }
1151:
1152: public SortedSet subSet(Object fromElement, Object toElement) {
1153: return new UnmodifiableSortedSet(ss.subSet(fromElement,
1154: toElement));
1155: }
1156:
1157: public SortedSet headSet(Object toElement) {
1158: return new UnmodifiableSortedSet(ss.headSet(toElement));
1159: }
1160:
1161: public SortedSet tailSet(Object fromElement) {
1162: return new UnmodifiableSortedSet(ss.tailSet(fromElement));
1163: }
1164:
1165: public Object first() {
1166: return ss.first();
1167: }
1168:
1169: public Object last() {
1170: return ss.last();
1171: }
1172: }
1173:
1174: /**
1175: * Returns an unmodifiable view of the specified list. This method allows
1176: * modules to provide users with "read-only" access to internal
1177: * lists. Query operations on the returned list "read through" to the
1178: * specified list, and attempts to modify the returned list, whether
1179: * direct or via its iterator, result in an
1180: * <tt>UnsupportedOperationException</tt>.<p>
1181: *
1182: * The returned list will be serializable if the specified list
1183: * is serializable. Similarly, the returned list will implement
1184: * {@link RandomAccess} if the specified list does.
1185: * the
1186: *
1187: * @param list the list for which an unmodifiable view is to be returned.
1188: * @return an unmodifiable view of the specified list.
1189: */
1190: public static List unmodifiableList(List list) {
1191: return (list instanceof RandomAccess ? new UnmodifiableRandomAccessList(
1192: list)
1193: : new UnmodifiableList(list));
1194: }
1195:
1196: /**
1197: * @serial include
1198: */
1199: static class UnmodifiableList extends UnmodifiableCollection
1200: implements List {
1201: static final long serialVersionUID = -283967356065247728L;
1202: List list;
1203:
1204: UnmodifiableList(List list) {
1205: super (list);
1206: this .list = list;
1207: }
1208:
1209: public boolean equals(Object o) {
1210: return list.equals(o);
1211: }
1212:
1213: public int hashCode() {
1214: return list.hashCode();
1215: }
1216:
1217: public Object get(int index) {
1218: return list.get(index);
1219: }
1220:
1221: public Object set(int index, Object element) {
1222: throw new UnsupportedOperationException();
1223: }
1224:
1225: public void add(int index, Object element) {
1226: throw new UnsupportedOperationException();
1227: }
1228:
1229: public Object remove(int index) {
1230: throw new UnsupportedOperationException();
1231: }
1232:
1233: public int indexOf(Object o) {
1234: return list.indexOf(o);
1235: }
1236:
1237: public int lastIndexOf(Object o) {
1238: return list.lastIndexOf(o);
1239: }
1240:
1241: public boolean addAll(int index, Collection c) {
1242: throw new UnsupportedOperationException();
1243: }
1244:
1245: public ListIterator listIterator() {
1246: return listIterator(0);
1247: }
1248:
1249: public ListIterator listIterator(final int index) {
1250: return new ListIterator() {
1251: ListIterator i = list.listIterator(index);
1252:
1253: public boolean hasNext() {
1254: return i.hasNext();
1255: }
1256:
1257: public Object next() {
1258: return i.next();
1259: }
1260:
1261: public boolean hasPrevious() {
1262: return i.hasPrevious();
1263: }
1264:
1265: public Object previous() {
1266: return i.previous();
1267: }
1268:
1269: public int nextIndex() {
1270: return i.nextIndex();
1271: }
1272:
1273: public int previousIndex() {
1274: return i.previousIndex();
1275: }
1276:
1277: public void remove() {
1278: throw new UnsupportedOperationException();
1279: }
1280:
1281: public void set(Object o) {
1282: throw new UnsupportedOperationException();
1283: }
1284:
1285: public void add(Object o) {
1286: throw new UnsupportedOperationException();
1287: }
1288: };
1289: }
1290:
1291: public List subList(int fromIndex, int toIndex) {
1292: return new UnmodifiableList(list
1293: .subList(fromIndex, toIndex));
1294: }
1295:
1296: /**
1297: * UnmodifiableRandomAccessList instances are serialized as
1298: * UnmodifiableList instances to allow them to be deserialized
1299: * in pre-1.4 JREs (which do not have UnmodifiableRandomAccessList).
1300: * This method inverts the transformation. As a beneficial
1301: * side-effect, it also grafts the RandomAccess marker onto
1302: * UnmodifiableList instances that were serialized in pre-1.4 JREs.
1303: *
1304: * Note: Unfortunately, UnmodifiableRandomAccessList instances
1305: * serialized in 1.4.1 and deserialized in 1.4 will become
1306: * UnmodifiableList instances, as this method was missing in 1.4.
1307: */
1308: private Object readResolve() {
1309: return (list instanceof RandomAccess ? new UnmodifiableRandomAccessList(
1310: list)
1311: : this );
1312: }
1313: }
1314:
1315: /**
1316: * @serial include
1317: */
1318: static class UnmodifiableRandomAccessList extends UnmodifiableList
1319: implements RandomAccess {
1320: UnmodifiableRandomAccessList(List list) {
1321: super (list);
1322: }
1323:
1324: public List subList(int fromIndex, int toIndex) {
1325: return new UnmodifiableRandomAccessList(list.subList(
1326: fromIndex, toIndex));
1327: }
1328:
1329: private static final long serialVersionUID = -2542308836966382001L;
1330:
1331: /**
1332: * Allows instances to be deserialized in pre-1.4 JREs (which do
1333: * not have UnmodifiableRandomAccessList). UnmodifiableList has
1334: * a readResolve method that inverts this transformation upon
1335: * deserialization.
1336: */
1337: private Object writeReplace() {
1338: return new UnmodifiableList(list);
1339: }
1340: }
1341:
1342: /**
1343: * Returns an unmodifiable view of the specified map. This method
1344: * allows modules to provide users with "read-only" access to internal
1345: * maps. Query operations on the returned map "read through"
1346: * to the specified map, and attempts to modify the returned
1347: * map, whether direct or via its collection views, result in an
1348: * <tt>UnsupportedOperationException</tt>.<p>
1349: *
1350: * The returned map will be serializable if the specified map
1351: * is serializable.
1352: *
1353: * @param m the map for which an unmodifiable view is to be returned.
1354: * @return an unmodifiable view of the specified map.
1355: */
1356: public static Map unmodifiableMap(Map m) {
1357: return new UnmodifiableMap(m);
1358: }
1359:
1360: /**
1361: * @serial include
1362: */
1363: private static class UnmodifiableMap implements Map, Serializable {
1364: // use serialVersionUID from JDK 1.2.2 for interoperability
1365: private static final long serialVersionUID = -1034234728574286014L;
1366:
1367: private final Map m;
1368:
1369: UnmodifiableMap(Map m) {
1370: if (m == null)
1371: throw new NullPointerException();
1372: this .m = m;
1373: }
1374:
1375: public int size() {
1376: return m.size();
1377: }
1378:
1379: public boolean isEmpty() {
1380: return m.isEmpty();
1381: }
1382:
1383: public boolean containsKey(Object key) {
1384: return m.containsKey(key);
1385: }
1386:
1387: public boolean containsValue(Object val) {
1388: return m.containsValue(val);
1389: }
1390:
1391: public Object get(Object key) {
1392: return m.get(key);
1393: }
1394:
1395: public Object put(Object key, Object value) {
1396: throw new UnsupportedOperationException();
1397: }
1398:
1399: public Object remove(Object key) {
1400: throw new UnsupportedOperationException();
1401: }
1402:
1403: public void putAll(Map t) {
1404: throw new UnsupportedOperationException();
1405: }
1406:
1407: public void clear() {
1408: throw new UnsupportedOperationException();
1409: }
1410:
1411: private transient Set keySet = null;
1412: private transient Set entrySet = null;
1413: private transient Collection values = null;
1414:
1415: public Set keySet() {
1416: if (keySet == null)
1417: keySet = unmodifiableSet(m.keySet());
1418: return keySet;
1419: }
1420:
1421: public Set entrySet() {
1422: if (entrySet == null)
1423: entrySet = new UnmodifiableEntrySet(m.entrySet());
1424: return entrySet;
1425: }
1426:
1427: public Collection values() {
1428: if (values == null)
1429: values = unmodifiableCollection(m.values());
1430: return values;
1431: }
1432:
1433: public boolean equals(Object o) {
1434: return m.equals(o);
1435: }
1436:
1437: public int hashCode() {
1438: return m.hashCode();
1439: }
1440:
1441: public String toString() {
1442: return m.toString();
1443: }
1444:
1445: /**
1446: * We need this class in addition to UnmodifiableSet as
1447: * Map.Entries themselves permit modification of the backing Map
1448: * via their setValue operation. This class is subtle: there are
1449: * many possible attacks that must be thwarted.
1450: *
1451: * @serial include
1452: */
1453: static class UnmodifiableEntrySet extends UnmodifiableSet {
1454: UnmodifiableEntrySet(Set s) {
1455: super (s);
1456: }
1457:
1458: public Iterator iterator() {
1459: return new Iterator() {
1460: Iterator i = c.iterator();
1461:
1462: public boolean hasNext() {
1463: return i.hasNext();
1464: }
1465:
1466: public Object next() {
1467: return new UnmodifiableEntry((Map.Entry) i
1468: .next());
1469: }
1470:
1471: public void remove() {
1472: throw new UnsupportedOperationException();
1473: }
1474: };
1475: }
1476:
1477: public Object[] toArray() {
1478: Object[] a = c.toArray();
1479: for (int i = 0; i < a.length; i++)
1480: a[i] = new UnmodifiableEntry((Map.Entry) a[i]);
1481: return a;
1482: }
1483:
1484: public Object[] toArray(Object a[]) {
1485: // We don't pass a to c.toArray, to avoid window of
1486: // vulnerability wherein an unscrupulous multithreaded client
1487: // could get his hands on raw (unwrapped) Entries from c.
1488: Object[] arr = c.toArray(a.length == 0 ? a
1489: : (Object[]) java.lang.reflect.Array
1490: .newInstance(a.getClass()
1491: .getComponentType(), 0));
1492: for (int i = 0; i < arr.length; i++)
1493: arr[i] = new UnmodifiableEntry((Map.Entry) arr[i]);
1494:
1495: if (arr.length > a.length)
1496: return arr;
1497:
1498: System.arraycopy(arr, 0, a, 0, arr.length);
1499: if (a.length > arr.length)
1500: a[arr.length] = null;
1501: return a;
1502: }
1503:
1504: /**
1505: * This method is overridden to protect the backing set against
1506: * an object with a nefarious equals function that senses
1507: * that the equality-candidate is Map.Entry and calls its
1508: * setValue method.
1509: */
1510: public boolean contains(Object o) {
1511: if (!(o instanceof Map.Entry))
1512: return false;
1513: return c.contains(new UnmodifiableEntry((Map.Entry) o));
1514: }
1515:
1516: /**
1517: * The next two methods are overridden to protect against
1518: * an unscrupulous List whose contains(Object o) method senses
1519: * when o is a Map.Entry, and calls o.setValue.
1520: */
1521: public boolean containsAll(Collection coll) {
1522: Iterator e = coll.iterator();
1523: while (e.hasNext())
1524: if (!contains(e.next())) // Invokes safe contains() above
1525: return false;
1526: return true;
1527: }
1528:
1529: public boolean equals(Object o) {
1530: if (o == this )
1531: return true;
1532:
1533: if (!(o instanceof Set))
1534: return false;
1535: Set s = (Set) o;
1536: if (s.size() != c.size())
1537: return false;
1538: return containsAll(s); // Invokes safe containsAll() above
1539: }
1540:
1541: /**
1542: * This "wrapper class" serves two purposes: it prevents
1543: * the client from modifying the backing Map, by short-circuiting
1544: * the setValue method, and it protects the backing Map against
1545: * an ill-behaved Map.Entry that attempts to modify another
1546: * Map Entry when asked to perform an equality check.
1547: */
1548: private static class UnmodifiableEntry implements Map.Entry {
1549: private Map.Entry e;
1550:
1551: UnmodifiableEntry(Map.Entry e) {
1552: this .e = e;
1553: }
1554:
1555: public Object getKey() {
1556: return e.getKey();
1557: }
1558:
1559: public Object getValue() {
1560: return e.getValue();
1561: }
1562:
1563: public Object setValue(Object value) {
1564: throw new UnsupportedOperationException();
1565: }
1566:
1567: public int hashCode() {
1568: return e.hashCode();
1569: }
1570:
1571: public boolean equals(Object o) {
1572: if (!(o instanceof Map.Entry))
1573: return false;
1574: Map.Entry t = (Map.Entry) o;
1575: return eq(e.getKey(), t.getKey())
1576: && eq(e.getValue(), t.getValue());
1577: }
1578:
1579: public String toString() {
1580: return e.toString();
1581: }
1582: }
1583: }
1584: }
1585:
1586: /**
1587: * Returns an unmodifiable view of the specified sorted map. This method
1588: * allows modules to provide users with "read-only" access to internal
1589: * sorted maps. Query operations on the returned sorted map "read through"
1590: * to the specified sorted map. Attempts to modify the returned
1591: * sorted map, whether direct, via its collection views, or via its
1592: * <tt>subMap</tt>, <tt>headMap</tt>, or <tt>tailMap</tt> views, result in
1593: * an <tt>UnsupportedOperationException</tt>.<p>
1594: *
1595: * The returned sorted map will be serializable if the specified sorted map
1596: * is serializable.
1597: *
1598: * @param m the sorted map for which an unmodifiable view is to be
1599: * returned.
1600: * @return an unmodifiable view of the specified sorted map.
1601: */
1602: public static SortedMap unmodifiableSortedMap(SortedMap m) {
1603: return new UnmodifiableSortedMap(m);
1604: }
1605:
1606: /**
1607: * @serial include
1608: */
1609: static class UnmodifiableSortedMap extends UnmodifiableMap
1610: implements SortedMap, Serializable {
1611: private SortedMap sm;
1612:
1613: UnmodifiableSortedMap(SortedMap m) {
1614: super (m);
1615: sm = m;
1616: }
1617:
1618: public Comparator comparator() {
1619: return sm.comparator();
1620: }
1621:
1622: public SortedMap subMap(Object fromKey, Object toKey) {
1623: return new UnmodifiableSortedMap(sm.subMap(fromKey, toKey));
1624: }
1625:
1626: public SortedMap headMap(Object toKey) {
1627: return new UnmodifiableSortedMap(sm.headMap(toKey));
1628: }
1629:
1630: public SortedMap tailMap(Object fromKey) {
1631: return new UnmodifiableSortedMap(sm.tailMap(fromKey));
1632: }
1633:
1634: public Object firstKey() {
1635: return sm.firstKey();
1636: }
1637:
1638: public Object lastKey() {
1639: return sm.lastKey();
1640: }
1641: }
1642:
1643: // Synch Wrappers
1644:
1645: /**
1646: * Returns a synchronized (thread-safe) collection backed by the specified
1647: * collection. In order to guarantee serial access, it is critical that
1648: * <strong>all</strong> access to the backing collection is accomplished
1649: * through the returned collection.<p>
1650: *
1651: * It is imperative that the user manually synchronize on the returned
1652: * collection when iterating over it:
1653: * <pre>
1654: * Collection c = Collections.synchronizedCollection(myCollection);
1655: * ...
1656: * synchronized(c) {
1657: * Iterator i = c.iterator(); // Must be in the synchronized block
1658: * while (i.hasNext())
1659: * foo(i.next());
1660: * }
1661: * </pre>
1662: * Failure to follow this advice may result in non-deterministic behavior.
1663: *
1664: * <p>The returned collection does <i>not</i> pass the <tt>hashCode</tt>
1665: * and <tt>equals</tt> operations through to the backing collection, but
1666: * relies on <tt>Object</tt>'s equals and hashCode methods. This is
1667: * necessary to preserve the contracts of these operations in the case
1668: * that the backing collection is a set or a list.<p>
1669: *
1670: * The returned collection will be serializable if the specified collection
1671: * is serializable.
1672: *
1673: * @param c the collection to be "wrapped" in a synchronized collection.
1674: * @return a synchronized view of the specified collection.
1675: */
1676: public static Collection synchronizedCollection(Collection c) {
1677: return new SynchronizedCollection(c);
1678: }
1679:
1680: static Collection synchronizedCollection(Collection c, Object mutex) {
1681: return new SynchronizedCollection(c, mutex);
1682: }
1683:
1684: /**
1685: * @serial include
1686: */
1687: static class SynchronizedCollection implements Collection,
1688: Serializable {
1689: // use serialVersionUID from JDK 1.2.2 for interoperability
1690: private static final long serialVersionUID = 3053995032091335093L;
1691:
1692: Collection c; // Backing Collection
1693: Object mutex; // Object on which to synchronize
1694:
1695: SynchronizedCollection(Collection c) {
1696: if (c == null)
1697: throw new NullPointerException();
1698: this .c = c;
1699: mutex = this ;
1700: }
1701:
1702: SynchronizedCollection(Collection c, Object mutex) {
1703: this .c = c;
1704: this .mutex = mutex;
1705: }
1706:
1707: public int size() {
1708: synchronized (mutex) {
1709: return c.size();
1710: }
1711: }
1712:
1713: public boolean isEmpty() {
1714: synchronized (mutex) {
1715: return c.isEmpty();
1716: }
1717: }
1718:
1719: public boolean contains(Object o) {
1720: synchronized (mutex) {
1721: return c.contains(o);
1722: }
1723: }
1724:
1725: public Object[] toArray() {
1726: synchronized (mutex) {
1727: return c.toArray();
1728: }
1729: }
1730:
1731: public Object[] toArray(Object[] a) {
1732: synchronized (mutex) {
1733: return c.toArray(a);
1734: }
1735: }
1736:
1737: public Iterator iterator() {
1738: return c.iterator(); // Must be manually synched by user!
1739: }
1740:
1741: public boolean add(Object o) {
1742: synchronized (mutex) {
1743: return c.add(o);
1744: }
1745: }
1746:
1747: public boolean remove(Object o) {
1748: synchronized (mutex) {
1749: return c.remove(o);
1750: }
1751: }
1752:
1753: public boolean containsAll(Collection coll) {
1754: synchronized (mutex) {
1755: return c.containsAll(coll);
1756: }
1757: }
1758:
1759: public boolean addAll(Collection coll) {
1760: synchronized (mutex) {
1761: return c.addAll(coll);
1762: }
1763: }
1764:
1765: public boolean removeAll(Collection coll) {
1766: synchronized (mutex) {
1767: return c.removeAll(coll);
1768: }
1769: }
1770:
1771: public boolean retainAll(Collection coll) {
1772: synchronized (mutex) {
1773: return c.retainAll(coll);
1774: }
1775: }
1776:
1777: public void clear() {
1778: synchronized (mutex) {
1779: c.clear();
1780: }
1781: }
1782:
1783: public String toString() {
1784: synchronized (mutex) {
1785: return c.toString();
1786: }
1787: }
1788: }
1789:
1790: /**
1791: * Returns a synchronized (thread-safe) set backed by the specified
1792: * set. In order to guarantee serial access, it is critical that
1793: * <strong>all</strong> access to the backing set is accomplished
1794: * through the returned set.<p>
1795: *
1796: * It is imperative that the user manually synchronize on the returned
1797: * set when iterating over it:
1798: * <pre>
1799: * Set s = Collections.synchronizedSet(new HashSet());
1800: * ...
1801: * synchronized(s) {
1802: * Iterator i = s.iterator(); // Must be in the synchronized block
1803: * while (i.hasNext())
1804: * foo(i.next());
1805: * }
1806: * </pre>
1807: * Failure to follow this advice may result in non-deterministic behavior.
1808: *
1809: * <p>The returned set will be serializable if the specified set is
1810: * serializable.
1811: *
1812: * @param s the set to be "wrapped" in a synchronized set.
1813: * @return a synchronized view of the specified set.
1814: */
1815: public static Set synchronizedSet(Set s) {
1816: return new SynchronizedSet(s);
1817: }
1818:
1819: static Set synchronizedSet(Set s, Object mutex) {
1820: return new SynchronizedSet(s, mutex);
1821: }
1822:
1823: /**
1824: * @serial include
1825: */
1826: static class SynchronizedSet extends SynchronizedCollection
1827: implements Set {
1828: SynchronizedSet(Set s) {
1829: super (s);
1830: }
1831:
1832: SynchronizedSet(Set s, Object mutex) {
1833: super (s, mutex);
1834: }
1835:
1836: public boolean equals(Object o) {
1837: synchronized (mutex) {
1838: return c.equals(o);
1839: }
1840: }
1841:
1842: public int hashCode() {
1843: synchronized (mutex) {
1844: return c.hashCode();
1845: }
1846: }
1847: }
1848:
1849: /**
1850: * Returns a synchronized (thread-safe) sorted set backed by the specified
1851: * sorted set. In order to guarantee serial access, it is critical that
1852: * <strong>all</strong> access to the backing sorted set is accomplished
1853: * through the returned sorted set (or its views).<p>
1854: *
1855: * It is imperative that the user manually synchronize on the returned
1856: * sorted set when iterating over it or any of its <tt>subSet</tt>,
1857: * <tt>headSet</tt>, or <tt>tailSet</tt> views.
1858: * <pre>
1859: * SortedSet s = Collections.synchronizedSortedSet(new HashSortedSet());
1860: * ...
1861: * synchronized(s) {
1862: * Iterator i = s.iterator(); // Must be in the synchronized block
1863: * while (i.hasNext())
1864: * foo(i.next());
1865: * }
1866: * </pre>
1867: * or:
1868: * <pre>
1869: * SortedSet s = Collections.synchronizedSortedSet(new HashSortedSet());
1870: * SortedSet s2 = s.headSet(foo);
1871: * ...
1872: * synchronized(s) { // Note: s, not s2!!!
1873: * Iterator i = s2.iterator(); // Must be in the synchronized block
1874: * while (i.hasNext())
1875: * foo(i.next());
1876: * }
1877: * </pre>
1878: * Failure to follow this advice may result in non-deterministic behavior.
1879: *
1880: * <p>The returned sorted set will be serializable if the specified
1881: * sorted set is serializable.
1882: *
1883: * @param s the sorted set to be "wrapped" in a synchronized sorted set.
1884: * @return a synchronized view of the specified sorted set.
1885: */
1886: public static SortedSet synchronizedSortedSet(SortedSet s) {
1887: return new SynchronizedSortedSet(s);
1888: }
1889:
1890: /**
1891: * @serial include
1892: */
1893: static class SynchronizedSortedSet extends SynchronizedSet
1894: implements SortedSet {
1895: private SortedSet ss;
1896:
1897: SynchronizedSortedSet(SortedSet s) {
1898: super (s);
1899: ss = s;
1900: }
1901:
1902: SynchronizedSortedSet(SortedSet s, Object mutex) {
1903: super (s, mutex);
1904: ss = s;
1905: }
1906:
1907: public Comparator comparator() {
1908: synchronized (mutex) {
1909: return ss.comparator();
1910: }
1911: }
1912:
1913: public SortedSet subSet(Object fromElement, Object toElement) {
1914: synchronized (mutex) {
1915: return new SynchronizedSortedSet(ss.subSet(fromElement,
1916: toElement), mutex);
1917: }
1918: }
1919:
1920: public SortedSet headSet(Object toElement) {
1921: synchronized (mutex) {
1922: return new SynchronizedSortedSet(ss.headSet(toElement),
1923: mutex);
1924: }
1925: }
1926:
1927: public SortedSet tailSet(Object fromElement) {
1928: synchronized (mutex) {
1929: return new SynchronizedSortedSet(ss
1930: .tailSet(fromElement), mutex);
1931: }
1932: }
1933:
1934: public Object first() {
1935: synchronized (mutex) {
1936: return ss.first();
1937: }
1938: }
1939:
1940: public Object last() {
1941: synchronized (mutex) {
1942: return ss.last();
1943: }
1944: }
1945: }
1946:
1947: /**
1948: * Returns a synchronized (thread-safe) list backed by the specified
1949: * list. In order to guarantee serial access, it is critical that
1950: * <strong>all</strong> access to the backing list is accomplished
1951: * through the returned list.<p>
1952: *
1953: * It is imperative that the user manually synchronize on the returned
1954: * list when iterating over it:
1955: * <pre>
1956: * List list = Collections.synchronizedList(new ArrayList());
1957: * ...
1958: * synchronized(list) {
1959: * Iterator i = list.iterator(); // Must be in synchronized block
1960: * while (i.hasNext())
1961: * foo(i.next());
1962: * }
1963: * </pre>
1964: * Failure to follow this advice may result in non-deterministic behavior.
1965: *
1966: * <p>The returned list will be serializable if the specified list is
1967: * serializable.
1968: *
1969: * @param list the list to be "wrapped" in a synchronized list.
1970: * @return a synchronized view of the specified list.
1971: */
1972: public static List synchronizedList(List list) {
1973: return (list instanceof RandomAccess ? new SynchronizedRandomAccessList(
1974: list)
1975: : new SynchronizedList(list));
1976: }
1977:
1978: static List synchronizedList(List list, Object mutex) {
1979: return (list instanceof RandomAccess ? new SynchronizedRandomAccessList(
1980: list, mutex)
1981: : new SynchronizedList(list, mutex));
1982: }
1983:
1984: /**
1985: * @serial include
1986: */
1987: static class SynchronizedList extends SynchronizedCollection
1988: implements List {
1989: static final long serialVersionUID = -7754090372962971524L;
1990:
1991: List list;
1992:
1993: SynchronizedList(List list) {
1994: super (list);
1995: this .list = list;
1996: }
1997:
1998: SynchronizedList(List list, Object mutex) {
1999: super (list, mutex);
2000: this .list = list;
2001: }
2002:
2003: public boolean equals(Object o) {
2004: synchronized (mutex) {
2005: return list.equals(o);
2006: }
2007: }
2008:
2009: public int hashCode() {
2010: synchronized (mutex) {
2011: return list.hashCode();
2012: }
2013: }
2014:
2015: public Object get(int index) {
2016: synchronized (mutex) {
2017: return list.get(index);
2018: }
2019: }
2020:
2021: public Object set(int index, Object element) {
2022: synchronized (mutex) {
2023: return list.set(index, element);
2024: }
2025: }
2026:
2027: public void add(int index, Object element) {
2028: synchronized (mutex) {
2029: list.add(index, element);
2030: }
2031: }
2032:
2033: public Object remove(int index) {
2034: synchronized (mutex) {
2035: return list.remove(index);
2036: }
2037: }
2038:
2039: public int indexOf(Object o) {
2040: synchronized (mutex) {
2041: return list.indexOf(o);
2042: }
2043: }
2044:
2045: public int lastIndexOf(Object o) {
2046: synchronized (mutex) {
2047: return list.lastIndexOf(o);
2048: }
2049: }
2050:
2051: public boolean addAll(int index, Collection c) {
2052: synchronized (mutex) {
2053: return list.addAll(index, c);
2054: }
2055: }
2056:
2057: public ListIterator listIterator() {
2058: return list.listIterator(); // Must be manually synched by user
2059: }
2060:
2061: public ListIterator listIterator(int index) {
2062: return list.listIterator(index); // Must be manually synched by usr
2063: }
2064:
2065: public List subList(int fromIndex, int toIndex) {
2066: synchronized (mutex) {
2067: return new SynchronizedList(list.subList(fromIndex,
2068: toIndex), mutex);
2069: }
2070: }
2071:
2072: /**
2073: * SynchronizedRandomAccessList instances are serialized as
2074: * SynchronizedList instances to allow them to be deserialized
2075: * in pre-1.4 JREs (which do not have SynchronizedRandomAccessList).
2076: * This method inverts the transformation. As a beneficial
2077: * side-effect, it also grafts the RandomAccess marker onto
2078: * SynchronizedList instances that were serialized in pre-1.4 JREs.
2079: *
2080: * Note: Unfortunately, SynchronizedRandomAccessList instances
2081: * serialized in 1.4.1 and deserialized in 1.4 will become
2082: * SynchronizedList instances, as this method was missing in 1.4.
2083: */
2084: private Object readResolve() {
2085: return (list instanceof RandomAccess ? new SynchronizedRandomAccessList(
2086: list)
2087: : this );
2088: }
2089: }
2090:
2091: /**
2092: * @serial include
2093: */
2094: static class SynchronizedRandomAccessList extends SynchronizedList
2095: implements RandomAccess {
2096: SynchronizedRandomAccessList(List list) {
2097: super (list);
2098: }
2099:
2100: SynchronizedRandomAccessList(List list, Object mutex) {
2101: super (list, mutex);
2102: }
2103:
2104: public List subList(int fromIndex, int toIndex) {
2105: synchronized (mutex) {
2106: return new SynchronizedRandomAccessList(list.subList(
2107: fromIndex, toIndex), mutex);
2108: }
2109: }
2110:
2111: static final long serialVersionUID = 1530674583602358482L;
2112:
2113: /**
2114: * Allows instances to be deserialized in pre-1.4 JREs (which do
2115: * not have SynchronizedRandomAccessList). SynchronizedList has
2116: * a readResolve method that inverts this transformation upon
2117: * deserialization.
2118: */
2119: private Object writeReplace() {
2120: return new SynchronizedList(list);
2121: }
2122: }
2123:
2124: /**
2125: * Returns a synchronized (thread-safe) map backed by the specified
2126: * map. In order to guarantee serial access, it is critical that
2127: * <strong>all</strong> access to the backing map is accomplished
2128: * through the returned map.<p>
2129: *
2130: * It is imperative that the user manually synchronize on the returned
2131: * map when iterating over any of its collection views:
2132: * <pre>
2133: * Map m = Collections.synchronizedMap(new HashMap());
2134: * ...
2135: * Set s = m.keySet(); // Needn't be in synchronized block
2136: * ...
2137: * synchronized(m) { // Synchronizing on m, not s!
2138: * Iterator i = s.iterator(); // Must be in synchronized block
2139: * while (i.hasNext())
2140: * foo(i.next());
2141: * }
2142: * </pre>
2143: * Failure to follow this advice may result in non-deterministic behavior.
2144: *
2145: * <p>The returned map will be serializable if the specified map is
2146: * serializable.
2147: *
2148: * @param m the map to be "wrapped" in a synchronized map.
2149: * @return a synchronized view of the specified map.
2150: */
2151: public static Map synchronizedMap(Map m) {
2152: return new SynchronizedMap(m);
2153: }
2154:
2155: /**
2156: * @serial include
2157: */
2158: private static class SynchronizedMap implements Map, Serializable {
2159: // use serialVersionUID from JDK 1.2.2 for interoperability
2160: private static final long serialVersionUID = 1978198479659022715L;
2161:
2162: private Map m; // Backing Map
2163: Object mutex; // Object on which to synchronize
2164:
2165: SynchronizedMap(Map m) {
2166: if (m == null)
2167: throw new NullPointerException();
2168: this .m = m;
2169: mutex = this ;
2170: }
2171:
2172: SynchronizedMap(Map m, Object mutex) {
2173: this .m = m;
2174: this .mutex = mutex;
2175: }
2176:
2177: public int size() {
2178: synchronized (mutex) {
2179: return m.size();
2180: }
2181: }
2182:
2183: public boolean isEmpty() {
2184: synchronized (mutex) {
2185: return m.isEmpty();
2186: }
2187: }
2188:
2189: public boolean containsKey(Object key) {
2190: synchronized (mutex) {
2191: return m.containsKey(key);
2192: }
2193: }
2194:
2195: public boolean containsValue(Object value) {
2196: synchronized (mutex) {
2197: return m.containsValue(value);
2198: }
2199: }
2200:
2201: public Object get(Object key) {
2202: synchronized (mutex) {
2203: return m.get(key);
2204: }
2205: }
2206:
2207: public Object put(Object key, Object value) {
2208: synchronized (mutex) {
2209: return m.put(key, value);
2210: }
2211: }
2212:
2213: public Object remove(Object key) {
2214: synchronized (mutex) {
2215: return m.remove(key);
2216: }
2217: }
2218:
2219: public void putAll(Map map) {
2220: synchronized (mutex) {
2221: m.putAll(map);
2222: }
2223: }
2224:
2225: public void clear() {
2226: synchronized (mutex) {
2227: m.clear();
2228: }
2229: }
2230:
2231: private transient Set keySet = null;
2232: private transient Set entrySet = null;
2233: private transient Collection values = null;
2234:
2235: public Set keySet() {
2236: synchronized (mutex) {
2237: if (keySet == null)
2238: keySet = new SynchronizedSet(m.keySet(), mutex);
2239: return keySet;
2240: }
2241: }
2242:
2243: public Set entrySet() {
2244: synchronized (mutex) {
2245: if (entrySet == null)
2246: entrySet = new SynchronizedSet(m.entrySet(), mutex);
2247: return entrySet;
2248: }
2249: }
2250:
2251: public Collection values() {
2252: synchronized (mutex) {
2253: if (values == null)
2254: values = new SynchronizedCollection(m.values(),
2255: mutex);
2256: return values;
2257: }
2258: }
2259:
2260: public boolean equals(Object o) {
2261: synchronized (mutex) {
2262: return m.equals(o);
2263: }
2264: }
2265:
2266: public int hashCode() {
2267: synchronized (mutex) {
2268: return m.hashCode();
2269: }
2270: }
2271:
2272: public String toString() {
2273: synchronized (mutex) {
2274: return m.toString();
2275: }
2276: }
2277: }
2278:
2279: /**
2280: * Returns a synchronized (thread-safe) sorted map backed by the specified
2281: * sorted map. In order to guarantee serial access, it is critical that
2282: * <strong>all</strong> access to the backing sorted map is accomplished
2283: * through the returned sorted map (or its views).<p>
2284: *
2285: * It is imperative that the user manually synchronize on the returned
2286: * sorted map when iterating over any of its collection views, or the
2287: * collections views of any of its <tt>subMap</tt>, <tt>headMap</tt> or
2288: * <tt>tailMap</tt> views.
2289: * <pre>
2290: * SortedMap m = Collections.synchronizedSortedMap(new HashSortedMap());
2291: * ...
2292: * Set s = m.keySet(); // Needn't be in synchronized block
2293: * ...
2294: * synchronized(m) { // Synchronizing on m, not s!
2295: * Iterator i = s.iterator(); // Must be in synchronized block
2296: * while (i.hasNext())
2297: * foo(i.next());
2298: * }
2299: * </pre>
2300: * or:
2301: * <pre>
2302: * SortedMap m = Collections.synchronizedSortedMap(new HashSortedMap());
2303: * SortedMap m2 = m.subMap(foo, bar);
2304: * ...
2305: * Set s2 = m2.keySet(); // Needn't be in synchronized block
2306: * ...
2307: * synchronized(m) { // Synchronizing on m, not m2 or s2!
2308: * Iterator i = s.iterator(); // Must be in synchronized block
2309: * while (i.hasNext())
2310: * foo(i.next());
2311: * }
2312: * </pre>
2313: * Failure to follow this advice may result in non-deterministic behavior.
2314: *
2315: * <p>The returned sorted map will be serializable if the specified
2316: * sorted map is serializable.
2317: *
2318: * @param m the sorted map to be "wrapped" in a synchronized sorted map.
2319: * @return a synchronized view of the specified sorted map.
2320: */
2321: public static SortedMap synchronizedSortedMap(SortedMap m) {
2322: return new SynchronizedSortedMap(m);
2323: }
2324:
2325: /**
2326: * @serial include
2327: */
2328: static class SynchronizedSortedMap extends SynchronizedMap
2329: implements SortedMap {
2330: private SortedMap sm;
2331:
2332: SynchronizedSortedMap(SortedMap m) {
2333: super (m);
2334: sm = m;
2335: }
2336:
2337: SynchronizedSortedMap(SortedMap m, Object mutex) {
2338: super (m, mutex);
2339: sm = m;
2340: }
2341:
2342: public Comparator comparator() {
2343: synchronized (mutex) {
2344: return sm.comparator();
2345: }
2346: }
2347:
2348: public SortedMap subMap(Object fromKey, Object toKey) {
2349: synchronized (mutex) {
2350: return new SynchronizedSortedMap(sm.subMap(fromKey,
2351: toKey), mutex);
2352: }
2353: }
2354:
2355: public SortedMap headMap(Object toKey) {
2356: synchronized (mutex) {
2357: return new SynchronizedSortedMap(sm.headMap(toKey),
2358: mutex);
2359: }
2360: }
2361:
2362: public SortedMap tailMap(Object fromKey) {
2363: synchronized (mutex) {
2364: return new SynchronizedSortedMap(sm.tailMap(fromKey),
2365: mutex);
2366: }
2367: }
2368:
2369: public Object firstKey() {
2370: synchronized (mutex) {
2371: return sm.firstKey();
2372: }
2373: }
2374:
2375: public Object lastKey() {
2376: synchronized (mutex) {
2377: return sm.lastKey();
2378: }
2379: }
2380: }
2381:
2382: // Miscellaneous
2383:
2384: /**
2385: * The empty set (immutable). This set is serializable.
2386: */
2387: public static final Set EMPTY_SET = new EmptySet();
2388:
2389: /**
2390: * @serial include
2391: */
2392: private static class EmptySet extends AbstractSet implements
2393: Serializable {
2394: // use serialVersionUID from JDK 1.2.2 for interoperability
2395: private static final long serialVersionUID = 1582296315990362920L;
2396:
2397: public Iterator iterator() {
2398: return new Iterator() {
2399: public boolean hasNext() {
2400: return false;
2401: }
2402:
2403: public Object next() {
2404: throw new NoSuchElementException();
2405: }
2406:
2407: public void remove() {
2408: throw new UnsupportedOperationException();
2409: }
2410: };
2411: }
2412:
2413: public int size() {
2414: return 0;
2415: }
2416:
2417: public boolean contains(Object obj) {
2418: return false;
2419: }
2420:
2421: // Preserves singleton property
2422: private Object readResolve() {
2423: return EMPTY_SET;
2424: }
2425: }
2426:
2427: /**
2428: * The empty list (immutable). This list is serializable.
2429: */
2430: public static final List EMPTY_LIST = new EmptyList();
2431:
2432: /**
2433: * @serial include
2434: */
2435: private static class EmptyList extends AbstractList implements
2436: RandomAccess, Serializable {
2437: // use serialVersionUID from JDK 1.2.2 for interoperability
2438: private static final long serialVersionUID = 8842843931221139166L;
2439:
2440: public int size() {
2441: return 0;
2442: }
2443:
2444: public boolean contains(Object obj) {
2445: return false;
2446: }
2447:
2448: public Object get(int index) {
2449: throw new IndexOutOfBoundsException("Index: " + index);
2450: }
2451:
2452: // Preserves singleton property
2453: private Object readResolve() {
2454: return EMPTY_LIST;
2455: }
2456: }
2457:
2458: /**
2459: * The empty map (immutable). This map is serializable.
2460: *
2461: * @since 1.3
2462: */
2463: public static final Map EMPTY_MAP = new EmptyMap();
2464:
2465: private static class EmptyMap extends AbstractMap implements
2466: Serializable {
2467: private static final long serialVersionUID = 6428348081105594320L;
2468:
2469: public int size() {
2470: return 0;
2471: }
2472:
2473: public boolean isEmpty() {
2474: return true;
2475: }
2476:
2477: public boolean containsKey(Object key) {
2478: return false;
2479: }
2480:
2481: public boolean containsValue(Object value) {
2482: return false;
2483: }
2484:
2485: public Object get(Object key) {
2486: return null;
2487: }
2488:
2489: public Set keySet() {
2490: return EMPTY_SET;
2491: }
2492:
2493: public Collection values() {
2494: return EMPTY_SET;
2495: }
2496:
2497: public Set entrySet() {
2498: return EMPTY_SET;
2499: }
2500:
2501: public boolean equals(Object o) {
2502: return (o instanceof Map) && ((Map) o).size() == 0;
2503: }
2504:
2505: public int hashCode() {
2506: return 0;
2507: }
2508:
2509: // Preserves singleton property
2510: private Object readResolve() {
2511: return EMPTY_MAP;
2512: }
2513: }
2514:
2515: /**
2516: * Returns an immutable set containing only the specified object.
2517: * The returned set is serializable.
2518: *
2519: * @param o the sole object to be stored in the returned set.
2520: * @return an immutable set containing only the specified object.
2521: */
2522: public static Set singleton(Object o) {
2523: return new SingletonSet(o);
2524: }
2525:
2526: /**
2527: * @serial include
2528: */
2529: private static class SingletonSet extends AbstractSet implements
2530: Serializable {
2531: // use serialVersionUID from JDK 1.2.2 for interoperability
2532: private static final long serialVersionUID = 3193687207550431679L;
2533:
2534: private Object element;
2535:
2536: SingletonSet(Object o) {
2537: element = o;
2538: }
2539:
2540: public Iterator iterator() {
2541: return new Iterator() {
2542: private boolean hasNext = true;
2543:
2544: public boolean hasNext() {
2545: return hasNext;
2546: }
2547:
2548: public Object next() {
2549: if (hasNext) {
2550: hasNext = false;
2551: return element;
2552: }
2553: throw new NoSuchElementException();
2554: }
2555:
2556: public void remove() {
2557: throw new UnsupportedOperationException();
2558: }
2559: };
2560: }
2561:
2562: public int size() {
2563: return 1;
2564: }
2565:
2566: public boolean contains(Object o) {
2567: return eq(o, element);
2568: }
2569: }
2570:
2571: /**
2572: * Returns an immutable list containing only the specified object.
2573: * The returned list is serializable.
2574: *
2575: * @param o the sole object to be stored in the returned list.
2576: * @return an immutable list containing only the specified object.
2577: * @since 1.3
2578: */
2579: public static List singletonList(Object o) {
2580: return new SingletonList(o);
2581: }
2582:
2583: private static class SingletonList extends AbstractList implements
2584: RandomAccess, Serializable {
2585: static final long serialVersionUID = 3093736618740652951L;
2586:
2587: private final Object element;
2588:
2589: SingletonList(Object obj) {
2590: element = obj;
2591: }
2592:
2593: public int size() {
2594: return 1;
2595: }
2596:
2597: public boolean contains(Object obj) {
2598: return eq(obj, element);
2599: }
2600:
2601: public Object get(int index) {
2602: if (index != 0)
2603: throw new IndexOutOfBoundsException("Index: " + index
2604: + ", Size: 1");
2605: return element;
2606: }
2607: }
2608:
2609: /**
2610: * Returns an immutable map, mapping only the specified key to the
2611: * specified value. The returned map is serializable.
2612: *
2613: * @param key the sole key to be stored in the returned map.
2614: * @param value the value to which the returned map maps <tt>key</tt>.
2615: * @return an immutable map containing only the specified key-value
2616: * mapping.
2617: * @since 1.3
2618: */
2619: public static Map singletonMap(Object key, Object value) {
2620: return new SingletonMap(key, value);
2621: }
2622:
2623: private static class SingletonMap extends AbstractMap implements
2624: Serializable {
2625: private final Object k, v;
2626:
2627: SingletonMap(Object key, Object value) {
2628: k = key;
2629: v = value;
2630: }
2631:
2632: public int size() {
2633: return 1;
2634: }
2635:
2636: public boolean isEmpty() {
2637: return false;
2638: }
2639:
2640: public boolean containsKey(Object key) {
2641: return eq(key, k);
2642: }
2643:
2644: public boolean containsValue(Object value) {
2645: return eq(value, v);
2646: }
2647:
2648: public Object get(Object key) {
2649: return (eq(key, k) ? v : null);
2650: }
2651:
2652: private transient Set keySet = null;
2653: private transient Set entrySet = null;
2654: private transient Collection values = null;
2655:
2656: public Set keySet() {
2657: if (keySet == null)
2658: keySet = singleton(k);
2659: return keySet;
2660: }
2661:
2662: public Set entrySet() {
2663: if (entrySet == null)
2664: entrySet = singleton(new ImmutableEntry(k, v));
2665: return entrySet;
2666: }
2667:
2668: public Collection values() {
2669: if (values == null)
2670: values = singleton(v);
2671: return values;
2672: }
2673:
2674: private static class ImmutableEntry implements Map.Entry {
2675: final Object k;
2676: final Object v;
2677:
2678: ImmutableEntry(Object key, Object value) {
2679: k = key;
2680: v = value;
2681: }
2682:
2683: public Object getKey() {
2684: return k;
2685: }
2686:
2687: public Object getValue() {
2688: return v;
2689: }
2690:
2691: public Object setValue(Object value) {
2692: throw new UnsupportedOperationException();
2693: }
2694:
2695: public boolean equals(Object o) {
2696: if (!(o instanceof Map.Entry))
2697: return false;
2698: Map.Entry e = (Map.Entry) o;
2699: return eq(e.getKey(), k) && eq(e.getValue(), v);
2700: }
2701:
2702: public int hashCode() {
2703: return ((k == null ? 0 : k.hashCode()) ^ (v == null ? 0
2704: : v.hashCode()));
2705: }
2706:
2707: public String toString() {
2708: return k + "=" + v;
2709: }
2710: }
2711: }
2712:
2713: /**
2714: * Returns an immutable list consisting of <tt>n</tt> copies of the
2715: * specified object. The newly allocated data object is tiny (it contains
2716: * a single reference to the data object). This method is useful in
2717: * combination with the <tt>List.addAll</tt> method to grow lists.
2718: * The returned list is serializable.
2719: *
2720: * @param n the number of elements in the returned list.
2721: * @param o the element to appear repeatedly in the returned list.
2722: * @return an immutable list consisting of <tt>n</tt> copies of the
2723: * specified object.
2724: * @throws IllegalArgumentException if n < 0.
2725: * @see List#addAll(Collection)
2726: * @see List#addAll(int, Collection)
2727: */
2728: public static List nCopies(int n, Object o) {
2729: return new CopiesList(n, o);
2730: }
2731:
2732: /**
2733: * @serial include
2734: */
2735: private static class CopiesList extends AbstractList implements
2736: RandomAccess, Serializable {
2737: static final long serialVersionUID = 2739099268398711800L;
2738:
2739: int n;
2740: Object element;
2741:
2742: CopiesList(int n, Object o) {
2743: if (n < 0)
2744: throw new IllegalArgumentException("List length = " + n);
2745: this .n = n;
2746: element = o;
2747: }
2748:
2749: public int size() {
2750: return n;
2751: }
2752:
2753: public boolean contains(Object obj) {
2754: return n != 0 && eq(obj, element);
2755: }
2756:
2757: public Object get(int index) {
2758: if (index < 0 || index >= n)
2759: throw new IndexOutOfBoundsException("Index: " + index
2760: + ", Size: " + n);
2761: return element;
2762: }
2763: }
2764:
2765: /**
2766: * Returns a comparator that imposes the reverse of the <i>natural
2767: * ordering</i> on a collection of objects that implement the
2768: * <tt>Comparable</tt> interface. (The natural ordering is the ordering
2769: * imposed by the objects' own <tt>compareTo</tt> method.) This enables a
2770: * simple idiom for sorting (or maintaining) collections (or arrays) of
2771: * objects that implement the <tt>Comparable</tt> interface in
2772: * reverse-natural-order. For example, suppose a is an array of
2773: * strings. Then: <pre>
2774: * Arrays.sort(a, Collections.reverseOrder());
2775: * </pre> sorts the array in reverse-lexicographic (alphabetical) order.<p>
2776: *
2777: * The returned comparator is serializable.
2778: *
2779: * @return a comparator that imposes the reverse of the <i>natural
2780: * ordering</i> on a collection of objects that implement
2781: * the <tt>Comparable</tt> interface.
2782: * @see Comparable
2783: */
2784: public static Comparator reverseOrder() {
2785: return REVERSE_ORDER;
2786: }
2787:
2788: private static final Comparator REVERSE_ORDER = new ReverseComparator();
2789:
2790: /**
2791: * @serial include
2792: */
2793: private static class ReverseComparator implements Comparator,
2794: Serializable {
2795: // use serialVersionUID from JDK 1.2.2 for interoperability
2796: private static final long serialVersionUID = 7207038068494060240L;
2797:
2798: public int compare(Object o1, Object o2) {
2799: Comparable c1 = (Comparable) o1;
2800: Comparable c2 = (Comparable) o2;
2801:
2802: int cmp = c1.compareTo(c2);
2803: /*
2804: * We can't simply return -cmp, as -Integer.MIN_VALUE ==
2805: * Integer.MIN_VALUE.
2806: */
2807: return -(cmp | (cmp >>> 1));
2808: }
2809: }
2810:
2811: /**
2812: * Returns an enumeration over the specified collection. This provides
2813: * interoperatbility with legacy APIs that require an enumeration
2814: * as input.
2815: *
2816: * @param c the collection for which an enumeration is to be returned.
2817: * @return an enumeration over the specified collection.
2818: * @see Enumeration
2819: */
2820: public static Enumeration enumeration(final Collection c) {
2821: return new Enumeration() {
2822: Iterator i = c.iterator();
2823:
2824: public boolean hasMoreElements() {
2825: return i.hasNext();
2826: }
2827:
2828: public Object nextElement() {
2829: return i.next();
2830: }
2831: };
2832: }
2833:
2834: /**
2835: * Returns an array list containing the elements returned by the
2836: * specified enumeration in the order they are returned by the
2837: * enumeration. This method provides interoperatbility between
2838: * legacy APIs that return enumerations and new APIs that require
2839: * collections.
2840: *
2841: * @param e enumeration providing elements for the returned
2842: * array list
2843: * @return an array list containing the elements returned
2844: * by the specified enumeration.
2845: * @since 1.4
2846: * @see Enumeration
2847: * @see ArrayList
2848: */
2849: public static ArrayList list(Enumeration e) {
2850: ArrayList l = new ArrayList();
2851: while (e.hasMoreElements())
2852: l.add(e.nextElement());
2853: return l;
2854: }
2855:
2856: /**
2857: * Returns true if the specified arguments are equal, or both null.
2858: */
2859: private static boolean eq(Object o1, Object o2) {
2860: return (o1 == null ? o2 == null : o1.equals(o2));
2861: }
2862: }
|