001    package railo.commons.collections;
002    
003    import java.io.Serializable;
004    import java.util.AbstractList;
005    import java.util.AbstractMap;
006    import java.util.AbstractSet;
007    import java.util.ArrayList;
008    import java.util.Arrays;
009    import java.util.Collection;
010    import java.util.Comparator;
011    import java.util.Enumeration;
012    import java.util.Iterator;
013    import java.util.List;
014    import java.util.ListIterator;
015    import java.util.Map;
016    import java.util.NoSuchElementException;
017    import java.util.Random;
018    import java.util.RandomAccess;
019    import java.util.Set;
020    import java.util.SortedMap;
021    import java.util.SortedSet;
022    
023    public final class Collections {
024        // Suppresses default constructor, ensuring non-instantiability.
025        private Collections() {
026        }
027    
028        // Algorithms
029    
030        /*
031         * Tuning parameters for algorithms - Many of the List algorithms have
032         * two implementations, one of which is appropriate for RandomAccess
033         * lists, the other for "sequential."  Often, the random access variant
034         * yields better performance on small sequential access lists.  The
035         * tuning  parameters below determine the cutoff point for what constitutes
036         * a "small" sequential access list for each algorithm.  The values below
037         * were empirically determined to work well for LinkedList. Hopefully
038         * they should be reasonable for other sequential access List
039         * implementations.  Those doing performance work on this code would
040         * do well to validate the values of these parameters from time to time.
041         * (The first word of each tuning parameter name is the algorithm to which
042         * it applies.)
043         */
044        private static final int BINARYSEARCH_THRESHOLD   = 5000;
045        private static final int REVERSE_THRESHOLD        =   18;
046        private static final int SHUFFLE_THRESHOLD        =    5;
047        private static final int FILL_THRESHOLD           =   25;
048        private static final int ROTATE_THRESHOLD         =  100;
049        private static final int COPY_THRESHOLD           =   10;
050        private static final int REPLACEALL_THRESHOLD     =   11;
051        private static final int INDEXOFSUBLIST_THRESHOLD =   35;
052    
053        public static void sort(List list) {
054            Object a[] = list.toArray();
055            Arrays.sort(a);
056            ListIterator i = list.listIterator();
057            for (int j=0; j<a.length; j++) {
058                i.next();
059                i.set(a[j]);
060            }
061        }
062    
063        public static void sort(List list, Comparator c) {
064            Object a[] = list.toArray();
065            Arrays.sort(a, c);
066            ListIterator i = list.listIterator();
067            for (int j=0; j<a.length; j++) {
068                i.next();
069                i.set(a[j]);
070            }
071        }
072    
073    
074        public static int binarySearch(List list, Object key) {
075            if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
076                return indexedBinarySearch(list, key);
077            return iteratorBinarySearch(list, key);
078        }
079    
080        private static int indexedBinarySearch(List list, Object key) {
081            int low = 0;
082            int high = list.size()-1;
083    
084            while (low <= high) {
085                int mid = (low + high) >> 1;
086                Object midVal = list.get(mid);
087                int cmp = ((Comparable)midVal).compareTo(key);
088    
089                if (cmp < 0)
090                    low = mid + 1;
091                else if (cmp > 0)
092                    high = mid - 1;
093                else
094                    return mid; // key found
095            }
096            return -(low + 1);  // key not found
097        }
098    
099        private static int iteratorBinarySearch(List list, Object key) {
100            int low = 0;
101            int high = list.size()-1;
102            ListIterator i = list.listIterator();
103    
104            while (low <= high) {
105                int mid = (low + high) >> 1;
106                Object midVal = get(i, mid);
107                int cmp = ((Comparable)midVal).compareTo(key);
108    
109                if (cmp < 0)
110                    low = mid + 1;
111                else if (cmp > 0)
112                    high = mid - 1;
113                else
114                    return mid; // key found
115            }
116            return -(low + 1);  // key not found
117        }
118    
119        /**
120         * Gets the ith element from the given list by repositioning the specified
121         * list listIterator.
122         * @param i
123         * @param index
124         * @return Object
125         */
126        private static Object get(ListIterator i, int index) {
127            Object obj = null;
128            int pos = i.nextIndex();
129            if (pos <= index) {
130                do {
131                    obj = i.next();
132                } while (pos++ < index);
133            } else {
134                do {
135                    obj = i.previous();
136                } while (--pos > index);
137            }
138            return obj;
139        }
140    
141        public static int binarySearch(List list, Object key, Comparator c) {
142            if (c==null)
143                return binarySearch(list, key);
144    
145            if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
146                return indexedBinarySearch(list, key, c);
147            return iteratorBinarySearch(list, key, c);
148        }
149    
150        private static int indexedBinarySearch(List l, Object key, Comparator c) {
151            int low = 0;
152            int high = l.size()-1;
153    
154            while (low <= high) {
155                int mid = (low + high) >> 1;
156                Object midVal = l.get(mid);
157                int cmp = c.compare(midVal, key);
158    
159                if (cmp < 0)
160                    low = mid + 1;
161                else if (cmp > 0)
162                    high = mid - 1;
163                else
164                    return mid; // key found
165            }
166            return -(low + 1);  // key not found
167        }
168    
169        private static int iteratorBinarySearch(List l, Object key, Comparator c) {
170            int low = 0;
171            int high = l.size()-1;
172            ListIterator i = l.listIterator();
173    
174            while (low <= high) {
175                int mid = (low + high) >> 1;
176                Object midVal = get(i, mid);
177                int cmp = c.compare(midVal, key);
178    
179                if (cmp < 0)
180                    low = mid + 1;
181                else if (cmp > 0)
182                    high = mid - 1;
183                else
184                    return mid; // key found
185            }
186            return -(low + 1);  // key not found
187        }
188    
189        /**
190         * Reverses the order of the elements in the specified list.<p>
191         *
192         * This method runs in linear time.
193         *
194         * @param  list the list whose elements are to be reversed.
195         * @throws UnsupportedOperationException if the specified list or
196         *         its list-iterator does not support the <tt>set</tt> method.
197         */
198        public static void reverse(List list) {
199            int size = list.size();
200            if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {
201                for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--)
202                    swap(list, i, j);
203            } else {
204                ListIterator fwd = list.listIterator();
205                ListIterator rev = list.listIterator(size);
206                for (int i=0, mid=list.size()>>1; i<mid; i++) {
207                    Object tmp = fwd.next();
208                    fwd.set(rev.previous());
209                    rev.set(tmp);
210                }
211            }
212        }
213    
214        /**
215         * Randomly permutes the specified list using a default source of
216         * randomness.  All permutations occur with approximately equal
217         * likelihood.<p>
218         *
219         * The hedge "approximately" is used in the foregoing description because
220         * default source of randomenss is only approximately an unbiased source
221         * of independently chosen bits. If it were a perfect source of randomly
222         * chosen bits, then the algorithm would choose permutations with perfect
223         * uniformity.<p>
224         *
225         * This implementation traverses the list backwards, from the last element
226         * up to the second, repeatedly swapping a randomly selected element into
227         * the "current position".  Elements are randomly selected from the
228         * portion of the list that runs from the first element to the current
229         * position, inclusive.<p>
230         *
231         * This method runs in linear time.  If the specified list does not
232         * implement the {@link RandomAccess} interface and is large, this
233         * implementation dumps the specified list into an array before shuffling
234         * it, and dumps the shuffled array back into the list.  This avoids the
235         * quadratic behavior that would result from shuffling a "sequential
236         * access" list in place.
237         *
238         * @param  list the list to be shuffled.
239         * @throws UnsupportedOperationException if the specified list or
240         *         its list-iterator does not support the <tt>set</tt> method.
241         */
242        public static void shuffle(List list) {
243            shuffle(list, r);
244        }
245        private static Random r = new Random();
246    
247        /**
248         * Randomly permute the specified list using the specified source of
249         * randomness.  All permutations occur with equal likelihood
250         * assuming that the source of randomness is fair.<p>
251         *
252         * This implementation traverses the list backwards, from the last element
253         * up to the second, repeatedly swapping a randomly selected element into
254         * the "current position".  Elements are randomly selected from the
255         * portion of the list that runs from the first element to the current
256         * position, inclusive.<p>
257         *
258         * This method runs in linear time.  If the specified list does not
259         * implement the {@link RandomAccess} interface and is large, this
260         * implementation dumps the specified list into an array before shuffling
261         * it, and dumps the shuffled array back into the list.  This avoids the
262         * quadratic behavior that would result from shuffling a "sequential
263         * access" list in place.
264         *
265         * @param  list the list to be shuffled.
266         * @param  rnd the source of randomness to use to shuffle the list.
267         * @throws UnsupportedOperationException if the specified list or its
268         *         list-iterator does not support the <tt>set</tt> operation.
269         */
270        public static void shuffle(List list, Random rnd) {
271            int size = list.size();
272            if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
273                for (int i=size; i>1; i--)
274                    swap(list, i-1, rnd.nextInt(i));
275            } else {
276                Object arr[] = list.toArray();
277    
278                // Shuffle array
279                for (int i=size; i>1; i--)
280                    swap(arr, i-1, rnd.nextInt(i));
281    
282                // Dump array back into list
283                ListIterator it = list.listIterator();
284                for (int i=0; i<arr.length; i++) {
285                    it.next();
286                    it.set(arr[i]);
287                }
288            }
289        }
290    
291        /**
292         * Swaps the elements at the specified positions in the specified list.
293         * (If the specified positions are equal, invoking this method leaves
294         * the list unchanged.)
295         *
296         * @param list The list in which to swap elements.
297         * @param i the index of one element to be swapped.
298         * @param j the index of the other element to be swapped.
299         * @throws IndexOutOfBoundsException if either <tt>i</tt> or <tt>j</tt>
300         *         is out of range (i &lt; 0 || i &gt;= list.size()
301         *         || j &lt; 0 || j &gt;= list.size()).
302         */
303        public static void swap(List list, int i, int j) {
304            list.set(i, list.set(j, list.get(i)));
305        }
306    
307        /**
308         * Swaps the two specified elements in the specified array.
309         * @param arr
310         * @param i
311         * @param j
312         */
313        private static void swap(Object[] arr, int i, int j) {
314            Object tmp = arr[i];
315            arr[i] = arr[j];
316            arr[j] = tmp;
317        }
318    
319        /**
320         * Replaces all of the elements of the specified list with the specified
321         * element. <p>
322         *
323         * This method runs in linear time.
324         *
325         * @param  list the list to be filled with the specified element.
326         * @param  obj The element with which to fill the specified list.
327         * @throws UnsupportedOperationException if the specified list or its
328         *         list-iterator does not support the <tt>set</tt> operation.
329         */
330        public static void fill(List list, Object obj) {
331            int size = list.size();
332    
333            if (size < FILL_THRESHOLD || list instanceof RandomAccess) {
334                for (int i=0; i<size; i++)
335                    list.set(i, obj);
336            } else {
337                ListIterator itr = list.listIterator();
338                for (int i=0; i<size; i++) {
339                    itr.next();
340                    itr.set(obj);
341                }
342            }
343        }
344    
345        /**
346         * Copies all of the elements from one list into another.  After the
347         * operation, the index of each copied element in the destination list
348         * will be identical to its index in the source list.  The destination
349         * list must be at least as long as the source list.  If it is longer, the
350         * remaining elements in the destination list are unaffected. <p>
351         *
352         * This method runs in linear time.
353         *
354         * @param  dest The destination list.
355         * @param  src The source list.
356         * @throws IndexOutOfBoundsException if the destination list is too small
357         *         to contain the entire source List.
358         * @throws UnsupportedOperationException if the destination list's
359         *         list-iterator does not support the <tt>set</tt> operation.
360         */
361        public static void copy(List dest, List src) {
362            int srcSize = src.size();
363            if (srcSize > dest.size())
364                throw new IndexOutOfBoundsException("Source does not fit in dest");
365    
366            if (srcSize < COPY_THRESHOLD ||
367                (src instanceof RandomAccess && dest instanceof RandomAccess)) {
368                for (int i=0; i<srcSize; i++)
369                    dest.set(i, src.get(i));
370            } else {
371                ListIterator di=dest.listIterator(), si=src.listIterator();
372                for (int i=0; i<srcSize; i++) {
373                    di.next();
374                    di.set(si.next());
375                }
376            }
377        }
378    
379        public static Object min(Collection coll) {
380            Iterator i = coll.iterator();
381            Comparable candidate = (Comparable)(i.next());
382    
383            while(i.hasNext()) {
384                Comparable next = (Comparable)(i.next());
385                if (next.compareTo(candidate) < 0)
386                    candidate = next;
387            }
388            return candidate;
389        }
390    
391        public static Object min(Collection coll, Comparator comp) {
392            if (comp==null)
393                return min(coll);
394    
395            Iterator i = coll.iterator();
396            Object candidate = i.next();
397    
398            while(i.hasNext()) {
399                Object next = i.next();
400                if (comp.compare(next, candidate) < 0)
401                    candidate = next;
402            }
403            return candidate;
404        }
405    
406        public static Object max(Collection coll) {
407            Iterator i = coll.iterator();
408            Comparable candidate = (Comparable)(i.next());
409    
410            while(i.hasNext()) {
411                Comparable next = (Comparable)(i.next());
412                if (next.compareTo(candidate) > 0)
413                    candidate = next;
414            }
415            return candidate;
416        }
417    
418        public static Object max(Collection coll, Comparator comp) {
419            if (comp==null)
420                return max(coll);
421    
422            Iterator i = coll.iterator();
423            Object candidate = i.next();
424    
425            while(i.hasNext()) {
426                Object next = i.next();
427                if (comp.compare(next, candidate) > 0)
428                    candidate = next;
429            }
430            return candidate;
431        }
432    
433        /**
434         * Rotates the elements in the specified list by the specified distance.
435         * After calling this method, the element at index <tt>i</tt> will be
436         * the element previously at index <tt>(i - distance)</tt> mod
437         * <tt>list.size()</tt>, for all values of <tt>i</tt> between <tt>0</tt>
438         * and <tt>list.size()-1</tt>, inclusive.  (This method has no effect on
439         * the size of the list.)
440         *
441         * <p>For example, suppose <tt>list</tt> comprises<tt> [t, a, n, k, s]</tt>.
442         * After invoking <tt>Collections.rotate(list, 1)</tt> (or
443         * <tt>Collections.rotate(list, -4)</tt>), <tt>list</tt> will comprise
444         * <tt>[s, t, a, n, k]</tt>.
445         *
446         * <p>Note that this method can usefully be applied to sublists to
447         * move one or more elements within a list while preserving the
448         * order of the remaining elements.  For example, the following idiom
449         * moves the element at index <tt>j</tt> forward to position
450         * <tt>k</tt> (which must be greater than or equal to <tt>j</tt>):
451         * <pre>
452         *     Collections.rotate(list.subList(j, k+1), -1);
453         * </pre>
454         * To make this concrete, suppose <tt>list</tt> comprises
455         * <tt>[a, b, c, d, e]</tt>.  To move the element at index <tt>1</tt>
456         * (<tt>b</tt>) forward two positions, perform the following invocation:
457         * <pre>
458         *     Collections.rotate(l.subList(1, 4), -1);
459         * </pre>
460         * The resulting list is <tt>[a, c, d, b, e]</tt>.
461         * 
462         * <p>To move more than one element forward, increase the absolute value
463         * of the rotation distance.  To move elements backward, use a positive
464         * shift distance.
465         *
466         * <p>If the specified list is small or implements the {@link
467         * RandomAccess} interface, this implementation exchanges the first
468         * element into the location it should go, and then repeatedly exchanges
469         * the displaced element into the location it should go until a displaced
470         * element is swapped into the first element.  If necessary, the process
471         * is repeated on the second and successive elements, until the rotation
472         * is complete.  If the specified list is large and doesn't implement the
473         * <tt>RandomAccess</tt> interface, this implementation breaks the
474         * list into two sublist views around index <tt>-distance mod size</tt>.
475         * Then the {@link #reverse(List)} method is invoked on each sublist view,
476         * and finally it is invoked on the entire list.  For a more complete
477         * description of both algorithms, see Section 2.3 of Jon Bentley's
478         * <i>Programming Pearls</i> (Addison-Wesley, 1986).
479         *
480         * @param list the list to be rotated.
481         * @param distance the distance to rotate the list.  There are no
482         *        constraints on this value; it may be zero, negative, or
483         *        greater than <tt>list.size()</tt>.
484         * @throws UnsupportedOperationException if the specified list or
485         *         its list-iterator does not support the <tt>set</tt> method.
486         */
487        public static void rotate(List list, int distance) {
488            if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD)
489                rotate1(list, distance);
490            else
491                rotate2(list, distance);
492        }
493    
494        private static void rotate1(List list, int distance) {
495            int size = list.size();
496            if (size == 0)
497                return;
498            distance = distance % size;
499            if (distance < 0)
500                distance += size;
501            if (distance == 0)
502                return;
503    
504            for (int cycleStart = 0, nMoved = 0; nMoved != size; cycleStart++) {
505                Object displaced = list.get(cycleStart);
506                int i = cycleStart;
507                do {
508                    i += distance;
509                    if (i >= size)
510                        i -= size;
511                    displaced = list.set(i, displaced);
512                    nMoved ++;
513                } while(i != cycleStart);
514            }
515        }
516    
517        private static void rotate2(List list, int distance) {
518            int size = list.size();
519            if (size == 0)
520                return; 
521            int mid =  -distance % size;
522            if (mid < 0)
523                mid += size;
524            if (mid == 0)
525                return;
526    
527            Collections.reverse(list.subList(0, mid));
528            Collections.reverse(list.subList(mid, size));
529            Collections.reverse(list);
530        }
531    
532        /**
533         * Replaces all occurrences of one specified value in a list with another.
534         * More formally, replaces with <tt>newVal</tt> each element <tt>e</tt>
535         * in <tt>list</tt> such that
536         * <tt>(oldVal==null ? e==null : oldVal.equals(e))</tt>.
537         * (This method has no effect on the size of the list.)
538         *
539         * @param list the list in which replacement is to occur.
540         * @param oldVal the old value to be replaced.
541         * @param newVal the new value with which <tt>oldVal</tt> is to be
542         *        replaced.
543         * @return <tt>true</tt> if <tt>list</tt> contained one or more elements
544         *         <tt>e</tt> such that
545         *         <tt>(oldVal==null ?  e==null : oldVal.equals(e))</tt>.
546         * @throws UnsupportedOperationException if the specified list or
547         *         its list-iterator does not support the <tt>set</tt> method.
548         */
549        public static boolean replaceAll(List list, Object oldVal, Object newVal) {
550            boolean result = false;
551            int size = list.size();
552            if (size < REPLACEALL_THRESHOLD || list instanceof RandomAccess) {
553                if (oldVal==null) {
554                    for (int i=0; i<size; i++) {
555                        if (list.get(i)==null) {
556                            list.set(i, newVal);
557                            result = true;
558                        }
559                    }
560                } else {
561                    for (int i=0; i<size; i++) {
562                        if (oldVal.equals(list.get(i))) {
563                            list.set(i, newVal);
564                            result = true;
565                        }
566                    }
567                }
568            } else {
569                ListIterator itr=list.listIterator();
570                if (oldVal==null) {
571                    for (int i=0; i<size; i++) {
572                        if (itr.next()==null) {
573                            itr.set(newVal);
574                            result = true;
575                        }
576                    }
577                } else {
578                    for (int i=0; i<size; i++) {
579                        if (oldVal.equals(itr.next())) {
580                            itr.set(newVal);
581                            result = true;
582                        }
583                    }
584                }
585            }
586            return result;
587        }
588    
589        /**
590         * Returns the starting position of the first occurrence of the specified
591         * target list within the specified source list, or -1 if there is no
592         * such occurrence.  More formally, returns the the lowest index <tt>i</tt>
593         * such that <tt>source.subList(i, i+target.size()).equals(target)</tt>,
594         * or -1 if there is no such index.  (Returns -1 if
595         * <tt>target.size() > source.size()</tt>.)
596         *
597         * <p>This implementation uses the "brute force" technique of scanning
598         * over the source list, looking for a match with the target at each
599         * location in turn.
600         *
601         * @param source the list in which to search for the first occurrence
602         *        of <tt>target</tt>.
603         * @param target the list to search for as a subList of <tt>source</tt>.
604         * @return the starting position of the first occurrence of the specified
605         *         target list within the specified source list, or -1 if there
606         *         is no such occurrence.
607         */
608        public static int indexOfSubList(List source, List target) {
609            int sourceSize = source.size();
610            int targetSize = target.size();
611            int maxCandidate = sourceSize - targetSize;
612    
613            if (sourceSize < INDEXOFSUBLIST_THRESHOLD ||
614                (source instanceof RandomAccess&&target instanceof RandomAccess)) {
615            nextCand:
616                for (int candidate = 0; candidate <= maxCandidate; candidate++) {
617                    for (int i=0, j=candidate; i<targetSize; i++, j++)
618                        if (!eq(target.get(i), source.get(j)))
619                            continue nextCand;  // Element mismatch, try next cand
620                    return candidate;  // All elements of candidate matched target
621                }
622            } else {  // Iterator version of above algorithm
623                ListIterator si = source.listIterator();
624            nextCand:
625                for (int candidate = 0; candidate <= maxCandidate; candidate++) {
626                    ListIterator ti = target.listIterator();
627                    for (int i=0; i<targetSize; i++) {
628                        if (!eq(ti.next(), si.next())) {
629                            // Back up source iterator to next candidate
630                            for (int j=0; j<i; j++)
631                                si.previous();
632                            continue nextCand;
633                        }
634                    }
635                    return candidate;
636                }
637            }
638            return -1;  // No candidate matched the target
639        }
640    
641        /**
642         * Returns the starting position of the last occurrence of the specified
643         * target list within the specified source list, or -1 if there is no such
644         * occurrence.  More formally, returns the the highest index <tt>i</tt>
645         * such that <tt>source.subList(i, i+target.size()).equals(target)</tt>,
646         * or -1 if there is no such index.  (Returns -1 if
647         * <tt>target.size() > source.size()</tt>.)
648         *
649         * <p>This implementation uses the "brute force" technique of iterating
650         * over the source list, looking for a match with the target at each
651         * location in turn.
652         *
653         * @param source the list in which to search for the last occurrence
654         *        of <tt>target</tt>.
655         * @param target the list to search for as a subList of <tt>source</tt>.
656         * @return the starting position of the last occurrence of the specified
657         *         target list within the specified source list, or -1 if there
658         *         is no such occurrence.
659         */
660        public static int lastIndexOfSubList(List source, List target) {
661            int sourceSize = source.size();
662            int targetSize = target.size();
663            int maxCandidate = sourceSize - targetSize;
664    
665            if (sourceSize < INDEXOFSUBLIST_THRESHOLD ||
666                source instanceof RandomAccess) {   // Index access version
667            nextCand:
668                for (int candidate = maxCandidate; candidate >= 0; candidate--) {
669                    for (int i=0, j=candidate; i<targetSize; i++, j++)
670                        if (!eq(target.get(i), source.get(j)))
671                            continue nextCand;  // Element mismatch, try next cand
672                    return candidate;  // All elements of candidate matched target
673                }
674            } else {  // Iterator version of above algorithm
675                if (maxCandidate < 0)
676                    return -1;
677                ListIterator si = source.listIterator(maxCandidate);
678            nextCand:
679                for (int candidate = maxCandidate; candidate >= 0; candidate--) {
680                    ListIterator ti = target.listIterator();
681                    for (int i=0; i<targetSize; i++) {
682                        if (!eq(ti.next(), si.next())) {
683                            if (candidate != 0) {
684                                // Back up source iterator to next candidate
685                                for (int j=0; j<=i+1; j++)
686                                    si.previous();
687                            }
688                            continue nextCand;
689                        }
690                    }
691                    return candidate;
692                }
693            }
694            return -1;  // No candidate matched the target
695        }
696    
697    
698        // Unmodifiable Wrappers
699    
700        /**
701         * Returns an unmodifiable view of the specified collection.  This method
702         * allows modules to provide users with "read-only" access to internal
703         * collections.  Query operations on the returned collection "read through"
704         * to the specified collection, and attempts to modify the returned
705         * collection, whether direct or via its iterator, result in an
706         * <tt>UnsupportedOperationException</tt>.<p>
707         *
708         * The returned collection does <i>not</i> pass the hashCode and equals
709         * operations through to the backing collection, but relies on
710         * <tt>Object</tt>'s <tt>equals</tt> and <tt>hashCode</tt> methods.  This
711         * is necessary to preserve the contracts of these operations in the case
712         * that the backing collection is a set or a list.<p>
713         *
714         * The returned collection will be serializable if the specified collection
715         * is serializable. 
716         *
717         * @param  c the collection for which an unmodifiable view is to be
718         *         returned.
719         * @return an unmodifiable view of the specified collection.
720         */
721        public static Collection unmodifiableCollection(Collection c) {
722            return new UnmodifiableCollection(c);
723        }
724    
725        /**
726         * @serial include
727         */
728        static class UnmodifiableCollection implements Collection, Serializable {
729            // use serialVersionUID from JDK 1.2.2 for interoperability
730            private static final long serialVersionUID = 1820017752578914078L;
731    
732            Collection c;
733    
734            UnmodifiableCollection(Collection c) {
735                if (c==null)
736                    throw new NullPointerException();
737                this.c = c;
738            }
739    
740            @Override
741            public int size()                   {return c.size();}
742            @Override
743            public boolean isEmpty()            {return c.isEmpty();}
744            @Override
745            public boolean contains(Object o)   {return c.contains(o);}
746            @Override
747            public Object[] toArray()           {return c.toArray();}
748            @Override
749            public Object[] toArray(Object[] a) {return c.toArray(a);}
750            @Override
751            public String toString()            {return c.toString();}
752    
753            @Override
754            public Iterator iterator() {
755                return new Iterator() {
756                    Iterator i = c.iterator();
757    
758                    public boolean hasNext() {return i.hasNext();}
759                    public Object next()     {return i.next();}
760                    public void remove() {
761                        throw new UnsupportedOperationException();
762                    }
763                };
764            }
765    
766            @Override
767            public boolean add(Object o){
768                throw new UnsupportedOperationException();
769            }
770            @Override
771            public boolean remove(Object o) {
772                throw new UnsupportedOperationException();
773            }
774    
775            @Override
776            public boolean containsAll(Collection coll) {
777                return c.containsAll(coll);
778            }
779            @Override
780            public boolean addAll(Collection coll) {
781                throw new UnsupportedOperationException();
782            }
783            @Override
784            public boolean removeAll(Collection coll) {
785                throw new UnsupportedOperationException();
786            }
787            @Override
788            public boolean retainAll(Collection coll) {
789                throw new UnsupportedOperationException();
790            }
791            @Override
792            public void clear() {
793                throw new UnsupportedOperationException();
794            }
795        }
796    
797        /**
798         * Returns an unmodifiable view of the specified set.  This method allows
799         * modules to provide users with "read-only" access to internal sets.
800         * Query operations on the returned set "read through" to the specified
801         * set, and attempts to modify the returned set, whether direct or via its
802         * iterator, result in an <tt>UnsupportedOperationException</tt>.<p>
803         *
804         * The returned set will be serializable if the specified set
805         * is serializable. 
806         *
807         * @param  s the set for which an unmodifiable view is to be returned.
808         * @return an unmodifiable view of the specified set.
809         */
810    
811        public static Set unmodifiableSet(Set s) {
812            return new UnmodifiableSet(s);
813        }
814    
815        /**
816         * @serial include
817         */
818        static class UnmodifiableSet extends UnmodifiableCollection
819                                     implements Set, Serializable {
820            UnmodifiableSet(Set s)          {super(s);}
821    
822            @Override
823            public boolean equals(Object o) {return c.equals(o);}
824            @Override
825            public int hashCode()           {return c.hashCode();}
826        }
827    
828        /**
829         * Returns an unmodifiable view of the specified sorted set.  This method
830         * allows modules to provide users with "read-only" access to internal
831         * sorted sets.  Query operations on the returned sorted set "read
832         * through" to the specified sorted set.  Attempts to modify the returned
833         * sorted set, whether direct, via its iterator, or via its
834         * <tt>subSet</tt>, <tt>headSet</tt>, or <tt>tailSet</tt> views, result in
835         * an <tt>UnsupportedOperationException</tt>.<p>
836         *
837         * The returned sorted set will be serializable if the specified sorted set
838         * is serializable. 
839         *
840         * @param s the sorted set for which an unmodifiable view is to be
841         *        returned. 
842         * @return an unmodifiable view of the specified sorted set.
843         */
844        public static SortedSet unmodifiableSortedSet(SortedSet s) {
845            return new UnmodifiableSortedSet(s);
846        }
847    
848        /**
849         * @serial include
850         */
851        static class UnmodifiableSortedSet extends UnmodifiableSet
852                                     implements SortedSet, Serializable {
853            private SortedSet ss;
854    
855            UnmodifiableSortedSet(SortedSet s) {super(s); ss = s;}
856    
857            @Override
858            public Comparator comparator()     {return ss.comparator();}
859    
860            @Override
861            public SortedSet subSet(Object fromElement, Object toElement) {
862                return new UnmodifiableSortedSet(ss.subSet(fromElement,toElement));
863            }
864            @Override
865            public SortedSet headSet(Object toElement) {
866                return new UnmodifiableSortedSet(ss.headSet(toElement));
867            }
868            @Override
869            public SortedSet tailSet(Object fromElement) {
870                return new UnmodifiableSortedSet(ss.tailSet(fromElement));
871            }
872    
873            @Override
874            public Object first()              {return ss.first();}
875            @Override
876            public Object last()               {return ss.last();}
877        }
878    
879        /**
880         * Returns an unmodifiable view of the specified list.  This method allows
881         * modules to provide users with "read-only" access to internal
882         * lists.  Query operations on the returned list "read through" to the
883         * specified list, and attempts to modify the returned list, whether
884         * direct or via its iterator, result in an
885         * <tt>UnsupportedOperationException</tt>.<p>
886         *
887         * The returned list will be serializable if the specified list
888         * is serializable. Similarly, the returned list will implement
889         * {@link RandomAccess} if the specified list does.
890         * the 
891         *
892         * @param  list the list for which an unmodifiable view is to be returned.
893         * @return an unmodifiable view of the specified list.
894         */
895        public static List unmodifiableList(List list) {
896            return (list instanceof RandomAccess ?
897                    new UnmodifiableRandomAccessList(list) :
898                    new UnmodifiableList(list));
899        }
900    
901        /**
902         * @serial include
903         */
904        static class UnmodifiableList extends UnmodifiableCollection
905                                      implements List {
906            static final long serialVersionUID = -283967356065247728L;
907            List list;
908    
909            UnmodifiableList(List list) {
910                super(list);
911                this.list = list;
912            }
913    
914            @Override
915            public boolean equals(Object o) {return list.equals(o);}
916            @Override
917            public int hashCode()           {return list.hashCode();}
918    
919            @Override
920            public Object get(int index) {return list.get(index);}
921            @Override
922            public Object set(int index, Object element) {
923                throw new UnsupportedOperationException();
924            }
925            @Override
926            public void add(int index, Object element) {
927                throw new UnsupportedOperationException();
928            }
929            @Override
930            public Object remove(int index) {
931                throw new UnsupportedOperationException();
932            }
933            @Override
934            public int indexOf(Object o)            {return list.indexOf(o);}
935            @Override
936            public int lastIndexOf(Object o)        {return list.lastIndexOf(o);}
937            @Override
938            public boolean addAll(int index, Collection c) {
939                throw new UnsupportedOperationException();
940            }
941            @Override
942            public ListIterator listIterator()      {return listIterator(0);}
943    
944            @Override
945            public ListIterator listIterator(final int index) {
946                return new ListIterator() {
947                    ListIterator i = list.listIterator(index);
948    
949                    public boolean hasNext()     {return i.hasNext();}
950                    public Object next()         {return i.next();}
951                    public boolean hasPrevious() {return i.hasPrevious();}
952                    public Object previous()     {return i.previous();}
953                    public int nextIndex()       {return i.nextIndex();}
954                    public int previousIndex()   {return i.previousIndex();}
955    
956                    public void remove() {
957                        throw new UnsupportedOperationException();
958                    }
959                    public void set(Object o) {
960                        throw new UnsupportedOperationException();
961                    }
962                    public void add(Object o) {
963                        throw new UnsupportedOperationException();
964                    }
965                };
966            }
967    
968            @Override
969            public List subList(int fromIndex, int toIndex) {
970                return new UnmodifiableList(list.subList(fromIndex, toIndex));
971            }
972        }
973    
974        /**
975         * @serial include
976         */
977        static class UnmodifiableRandomAccessList extends UnmodifiableList
978                                                  implements RandomAccess
979        {
980            UnmodifiableRandomAccessList(List list) {
981                super(list);
982            }
983    
984            @Override
985            public List subList(int fromIndex, int toIndex) {
986                return new UnmodifiableRandomAccessList(
987                    list.subList(fromIndex, toIndex));
988            }
989        }
990    
991        /**
992         * Returns an unmodifiable view of the specified map.  This method
993         * allows modules to provide users with "read-only" access to internal
994         * maps.  Query operations on the returned map "read through"
995         * to the specified map, and attempts to modify the returned
996         * map, whether direct or via its collection views, result in an
997         * <tt>UnsupportedOperationException</tt>.<p>
998         *
999         * The returned map will be serializable if the specified map
1000         * is serializable. 
1001         *
1002         * @param  m the map for which an unmodifiable view is to be returned.
1003         * @return an unmodifiable view of the specified map.
1004         */
1005        public static Map unmodifiableMap(Map m) {
1006            return new UnmodifiableMap(m);
1007        }
1008    
1009        /**
1010         * @serial include
1011         */
1012        private static class UnmodifiableMap implements Map, Serializable {
1013            // use serialVersionUID from JDK 1.2.2 for interoperability
1014            private static final long serialVersionUID = -1034234728574286014L;
1015    
1016            private final Map m;
1017    
1018            UnmodifiableMap(Map m) {
1019                if (m==null)
1020                    throw new NullPointerException();
1021                this.m = m;
1022            }
1023    
1024            @Override
1025            public int size()                        {return m.size();}
1026            @Override
1027            public boolean isEmpty()                 {return m.isEmpty();}
1028            @Override
1029            public boolean containsKey(Object key)   {return m.containsKey(key);}
1030            @Override
1031            public boolean containsValue(Object val) {return m.containsValue(val);}
1032            @Override
1033            public Object get(Object key)            {return m.get(key);}
1034    
1035            @Override
1036            public Object put(Object key, Object value) {
1037                throw new UnsupportedOperationException();
1038            }
1039            @Override
1040            public Object remove(Object key) {
1041                throw new UnsupportedOperationException();
1042            }
1043            @Override
1044            public void putAll(Map t) {
1045                throw new UnsupportedOperationException();
1046            }
1047            @Override
1048            public void clear() {
1049                throw new UnsupportedOperationException();
1050            }
1051    
1052            private transient Set keySet = null;
1053            private transient Set entrySet = null;
1054            private transient Collection values = null;
1055    
1056            @Override
1057            public Set keySet() {
1058                if (keySet==null)
1059                    keySet = unmodifiableSet(m.keySet());
1060                return keySet;
1061            }
1062    
1063            @Override
1064            public Set entrySet() {
1065                if (entrySet==null)
1066                    entrySet = new UnmodifiableEntrySet(m.entrySet());
1067                return entrySet;
1068            }
1069    
1070            @Override
1071            public Collection values() {
1072                if (values==null)
1073                    values = unmodifiableCollection(m.values());
1074                return values;
1075            }
1076    
1077            @Override
1078            public boolean equals(Object o) {return m.equals(o);}
1079            @Override
1080            public int hashCode()           {return m.hashCode();}
1081            @Override
1082            public String toString()        {return m.toString();}
1083    
1084            /**
1085             * We need this class in addition to UnmodifiableSet as
1086             * Map.Entries themselves permit modification of the backing Map
1087             * via their setValue operation.  This class is subtle: there are
1088             * many possible attacks that must be thwarted.
1089             *
1090             * @serial include
1091             */
1092            static class UnmodifiableEntrySet extends UnmodifiableSet {
1093                UnmodifiableEntrySet(Set s) {
1094                    super(s);
1095                }
1096    
1097                @Override
1098                public Iterator iterator() {
1099                    return new Iterator() {
1100                        Iterator i = c.iterator();
1101    
1102                        public boolean hasNext() {
1103                            return i.hasNext();
1104                        }
1105                        public Object next()         {
1106                            return new UnmodifiableEntry((Map.Entry)i.next());
1107                        }
1108                        public void remove() {
1109                            throw new UnsupportedOperationException();
1110                        }
1111                    };
1112                }
1113    
1114                @Override
1115                public Object[] toArray() {
1116                    Object[] a = c.toArray();
1117                    for (int i=0; i<a.length; i++)
1118                        a[i] = new UnmodifiableEntry((Map.Entry)a[i]);
1119                    return a;
1120                }
1121    
1122                @Override
1123                public Object[] toArray(Object a[]) {
1124                    // We don't pass a to c.toArray, to avoid window of
1125                    // vulnerability wherein an unscrupulous multithreaded client
1126                    // could get his hands on raw (unwrapped) Entries from c.
1127                    Object[] arr = c.toArray(a.length==0 ? a :
1128                                (Object[])java.lang.reflect.Array.newInstance(
1129                                              a.getClass().getComponentType(), 0));
1130                    for (int i=0; i<arr.length; i++)
1131                        arr[i] = new UnmodifiableEntry((Map.Entry)arr[i]);
1132    
1133                    if (arr.length > a.length)
1134                        return arr;
1135    
1136                    System.arraycopy(arr, 0, a, 0, arr.length);
1137                    if (a.length > arr.length)
1138                        a[arr.length] = null;
1139                    return a;
1140                }
1141    
1142                /**
1143                 * This method is overridden to protect the backing set against
1144                 * an object with a nefarious equals function that senses
1145                 * that the equality-candidate is Map.Entry and calls its
1146                 * setValue method.
1147                 * @param o
1148                 * @return contains or not
1149                 */
1150                public boolean contains(Object o) {
1151                    if (!(o instanceof Map.Entry))
1152                        return false;
1153                    return c.contains(new UnmodifiableEntry((Map.Entry)o));
1154                }
1155    
1156                /**
1157                 * The next two methods are overridden to protect against
1158                 * an unscrupulous List whose contains(Object o) method senses
1159                 * when o is a Map.Entry, and calls o.setValue.
1160                 * @param coll
1161                 * @return boolean
1162                 */
1163                public boolean containsAll(Collection coll) {
1164                    Iterator e = coll.iterator();
1165                    while (e.hasNext())
1166                        if(!contains(e.next())) // Invokes safe contains() above
1167                            return false;
1168                    return true;
1169                }
1170                @Override
1171                public boolean equals(Object o) {
1172                    if (o == this)
1173                        return true;
1174    
1175                    if (!(o instanceof Set))
1176                        return false;
1177                    Set s = (Set) o;
1178                    if (s.size() != c.size())
1179                        return false;
1180                    return containsAll(s); // Invokes safe containsAll() above
1181                }
1182    
1183                /**
1184                 * This "wrapper class" serves two purposes: it prevents
1185                 * the client from modifying the backing Map, by short-circuiting
1186                 * the setValue method, and it protects the backing Map against
1187                 * an ill-behaved Map.Entry that attempts to modify another
1188                 * Map Entry when asked to perform an equality check.
1189                 */
1190                private static class UnmodifiableEntry implements Map.Entry {
1191                    private Map.Entry e;
1192    
1193                    UnmodifiableEntry(Map.Entry e) {this.e = e;}
1194    
1195                    @Override
1196                    public Object getKey()    {return e.getKey();}
1197                    @Override
1198                    public Object getValue()  {return e.getValue();}
1199                    @Override
1200                    public Object setValue(Object value) {
1201                        throw new UnsupportedOperationException();
1202                    }
1203                    @Override
1204                    public int hashCode()     {return e.hashCode();}
1205                    @Override
1206                    public boolean equals(Object o) {
1207                        if (!(o instanceof Map.Entry))
1208                            return false;
1209                        Map.Entry t = (Map.Entry)o;
1210                        return eq(e.getKey(),   t.getKey()) &&
1211                               eq(e.getValue(), t.getValue());
1212                    }
1213                    @Override
1214                    public String toString()  {return e.toString();}
1215                }
1216            }
1217        }
1218    
1219        /**
1220         * Returns an unmodifiable view of the specified sorted map.  This method
1221         * allows modules to provide users with "read-only" access to internal
1222         * sorted maps.  Query operations on the returned sorted map "read through"
1223         * to the specified sorted map.  Attempts to modify the returned
1224         * sorted map, whether direct, via its collection views, or via its
1225         * <tt>subMap</tt>, <tt>headMap</tt>, or <tt>tailMap</tt> views, result in
1226         * an <tt>UnsupportedOperationException</tt>.<p>
1227         *
1228         * The returned sorted map will be serializable if the specified sorted map
1229         * is serializable. 
1230         *
1231         * @param m the sorted map for which an unmodifiable view is to be
1232         *        returned. 
1233         * @return an unmodifiable view of the specified sorted map.
1234         */
1235        public static SortedMap unmodifiableSortedMap(SortedMap m) {
1236            return new UnmodifiableSortedMap(m);
1237        }
1238    
1239        /**
1240         * @serial include
1241         */
1242        static class UnmodifiableSortedMap extends UnmodifiableMap
1243                                     implements SortedMap, Serializable {
1244            private SortedMap sm;
1245    
1246            UnmodifiableSortedMap(SortedMap m) {super(m); sm = m;}
1247    
1248            @Override
1249            public Comparator comparator()     {return sm.comparator();}
1250    
1251            @Override
1252            public SortedMap subMap(Object fromKey, Object toKey) {
1253                return new UnmodifiableSortedMap(sm.subMap(fromKey, toKey));
1254            }
1255            @Override
1256            public SortedMap headMap(Object toKey) {
1257                return new UnmodifiableSortedMap(sm.headMap(toKey));
1258            }
1259            @Override
1260            public SortedMap tailMap(Object fromKey) {
1261                return new UnmodifiableSortedMap(sm.tailMap(fromKey));
1262            }
1263    
1264            @Override
1265            public Object firstKey()           {return sm.firstKey();}
1266            @Override
1267            public Object lastKey()            {return sm.lastKey();}
1268        }
1269    
1270    
1271        // Synch Wrappers
1272    
1273        /**
1274         * Returns a synchronized (thread-safe) collection backed by the specified
1275         * collection.  In order to guarantee serial access, it is critical that
1276         * <strong>all</strong> access to the backing collection is accomplished
1277         * through the returned collection.<p>
1278         *
1279         * It is imperative that the user manually synchronize on the returned
1280         * collection when iterating over it:
1281         * <pre>
1282         *  Collection c = Collections.synchronizedCollection(myCollection);
1283         *     ...
1284         *  synchronized(c) {
1285         *      Iterator i = c.iterator(); // Must be in the synchronized block
1286         *      while (i.hasNext())
1287         *         foo(i.next());
1288         *  }
1289         * </pre>
1290         * Failure to follow this advice may result in non-deterministic behavior.
1291         *
1292         * <p>The returned collection does <i>not</i> pass the <tt>hashCode</tt>
1293         * and <tt>equals</tt> operations through to the backing collection, but
1294         * relies on <tt>Object</tt>'s equals and hashCode methods.  This is
1295         * necessary to preserve the contracts of these operations in the case
1296         * that the backing collection is a set or a list.<p>
1297         *
1298         * The returned collection will be serializable if the specified collection
1299         * is serializable. 
1300         *
1301         * @param  c the collection to be "wrapped" in a synchronized collection.
1302         * @return a synchronized view of the specified collection.
1303         */
1304        public static Collection synchronizedCollection(Collection c) {
1305            return new SynchronizedCollection(c);
1306        }
1307    
1308        static Collection synchronizedCollection(Collection c, Object mutex) {
1309            return new SynchronizedCollection(c, mutex);
1310        }
1311    
1312        /**
1313         * @serial include
1314         */
1315        static class SynchronizedCollection implements Collection, Serializable {
1316            // use serialVersionUID from JDK 1.2.2 for interoperability
1317            private static final long serialVersionUID = 3053995032091335093L;
1318    
1319            Collection c;      // Backing Collection
1320            Object     mutex;  // Object on which to synchronize
1321    
1322            SynchronizedCollection(Collection c) {
1323                if (c==null)
1324                    throw new NullPointerException();
1325                this.c = c;
1326                mutex = this;
1327            }
1328            SynchronizedCollection(Collection c, Object mutex) {
1329                this.c = c;
1330                this.mutex = mutex;
1331            }
1332    
1333            @Override
1334            public int size() {
1335                synchronized(mutex) {return c.size();}
1336            }
1337            @Override
1338            public boolean isEmpty() {
1339                synchronized(mutex) {return c.isEmpty();}
1340            }
1341            @Override
1342            public boolean contains(Object o) {
1343                synchronized(mutex) {return c.contains(o);}
1344            }
1345            @Override
1346            public Object[] toArray() {
1347                synchronized(mutex) {return c.toArray();}
1348            }
1349            @Override
1350            public Object[] toArray(Object[] a) {
1351                synchronized(mutex) {return c.toArray(a);}
1352            }
1353    
1354            @Override
1355            public Iterator iterator() {
1356                return c.iterator(); // Must be manually synched by user!
1357            }
1358    
1359            @Override
1360            public boolean add(Object o) {
1361                synchronized(mutex) {return c.add(o);}
1362            }
1363            @Override
1364            public boolean remove(Object o) {
1365                synchronized(mutex) {return c.remove(o);}
1366            }
1367    
1368            @Override
1369            public boolean containsAll(Collection coll) {
1370                synchronized(mutex) {return c.containsAll(coll);}
1371            }
1372            @Override
1373            public boolean addAll(Collection coll) {
1374                synchronized(mutex) {return c.addAll(coll);}
1375            }
1376            @Override
1377            public boolean removeAll(Collection coll) {
1378                synchronized(mutex) {return c.removeAll(coll);}
1379            }
1380            @Override
1381            public boolean retainAll(Collection coll) {
1382                synchronized(mutex) {return c.retainAll(coll);}
1383            }
1384            @Override
1385            public void clear() {
1386                synchronized(mutex) {c.clear();}
1387            }
1388            @Override
1389            public String toString() {
1390                synchronized(mutex) {return c.toString();}
1391            }
1392        }
1393    
1394        /**
1395         * Returns a synchronized (thread-safe) set backed by the specified
1396         * set.  In order to guarantee serial access, it is critical that
1397         * <strong>all</strong> access to the backing set is accomplished
1398         * through the returned set.<p>
1399         *
1400         * It is imperative that the user manually synchronize on the returned
1401         * set when iterating over it:
1402         * <pre>
1403         *  Set s = Collections.synchronizedSet(new HashSet());
1404         *      ...
1405         *  synchronized(s) {
1406         *      Iterator i = s.iterator(); // Must be in the synchronized block
1407         *      while (i.hasNext())
1408         *          foo(i.next());
1409         *  }
1410         * </pre>
1411         * Failure to follow this advice may result in non-deterministic behavior.
1412         *
1413         * <p>The returned set will be serializable if the specified set is
1414         * serializable.
1415         *
1416         * @param  s the set to be "wrapped" in a synchronized set.
1417         * @return a synchronized view of the specified set.
1418         */
1419        public static Set synchronizedSet(Set s) {
1420            return new SynchronizedSet(s);
1421        }
1422    
1423        static Set synchronizedSet(Set s, Object mutex) {
1424            return new SynchronizedSet(s, mutex);
1425        }
1426    
1427        /**
1428         * @serial include
1429         */
1430        static class SynchronizedSet extends SynchronizedCollection
1431                                     implements Set {
1432            SynchronizedSet(Set s) {
1433                super(s);
1434            }
1435            SynchronizedSet(Set s, Object mutex) {
1436                super(s, mutex);
1437            }
1438    
1439            @Override
1440            public boolean equals(Object o) {
1441                synchronized(mutex) {return c.equals(o);}
1442            }
1443            @Override
1444            public int hashCode() {
1445                synchronized(mutex) {return c.hashCode();}
1446            }
1447        }
1448    
1449        /**
1450         * Returns a synchronized (thread-safe) sorted set backed by the specified
1451         * sorted set.  In order to guarantee serial access, it is critical that
1452         * <strong>all</strong> access to the backing sorted set is accomplished
1453         * through the returned sorted set (or its views).<p>
1454         *
1455         * It is imperative that the user manually synchronize on the returned
1456         * sorted set when iterating over it or any of its <tt>subSet</tt>,
1457         * <tt>headSet</tt>, or <tt>tailSet</tt> views.
1458         * <pre>
1459         *  SortedSet s = Collections.synchronizedSortedSet(new HashSortedSet());
1460         *      ...
1461         *  synchronized(s) {
1462         *      Iterator i = s.iterator(); // Must be in the synchronized block
1463         *      while (i.hasNext())
1464         *          foo(i.next());
1465         *  }
1466         * </pre>
1467         * or:
1468         * <pre>
1469         *  SortedSet s = Collections.synchronizedSortedSet(new HashSortedSet());
1470         *  SortedSet s2 = s.headSet(foo);
1471         *      ...
1472         *  synchronized(s) {  // Note: s, not s2!!!
1473         *      Iterator i = s2.iterator(); // Must be in the synchronized block
1474         *      while (i.hasNext())
1475         *          foo(i.next());
1476         *  }
1477         * </pre>
1478         * Failure to follow this advice may result in non-deterministic behavior.
1479         *
1480         * <p>The returned sorted set will be serializable if the specified
1481         * sorted set is serializable.
1482         *
1483         * @param  s the sorted set to be "wrapped" in a synchronized sorted set.
1484         * @return a synchronized view of the specified sorted set.
1485         */
1486        public static SortedSet synchronizedSortedSet(SortedSet s) {
1487            return new SynchronizedSortedSet(s);
1488        }
1489    
1490        /**
1491         * @serial include
1492         */
1493        static class SynchronizedSortedSet extends SynchronizedSet
1494                                     implements SortedSet
1495        {
1496            private SortedSet ss;
1497    
1498            SynchronizedSortedSet(SortedSet s) {
1499                super(s);
1500                ss = s;
1501            }
1502            SynchronizedSortedSet(SortedSet s, Object mutex) {
1503                super(s, mutex);
1504                ss = s;
1505            }
1506    
1507            @Override
1508            public Comparator comparator() {
1509                synchronized(mutex) {return ss.comparator();}
1510            }
1511    
1512            @Override
1513            public SortedSet subSet(Object fromElement, Object toElement) {
1514                synchronized(mutex) {
1515                    return new SynchronizedSortedSet(
1516                        ss.subSet(fromElement, toElement), mutex);
1517                }
1518            }
1519            @Override
1520            public SortedSet headSet(Object toElement) {
1521                synchronized(mutex) {
1522                    return new SynchronizedSortedSet(ss.headSet(toElement), mutex);
1523                }
1524            }
1525            @Override
1526            public SortedSet tailSet(Object fromElement) {
1527                synchronized(mutex) {
1528                   return new SynchronizedSortedSet(ss.tailSet(fromElement),mutex);
1529                }
1530            }
1531    
1532            @Override
1533            public Object first() {
1534                synchronized(mutex) {return ss.first();}
1535            }
1536            @Override
1537            public Object last() {
1538                synchronized(mutex) {return ss.last();}
1539            }
1540        }
1541    
1542        /**
1543         * Returns a synchronized (thread-safe) list backed by the specified
1544         * list.  In order to guarantee serial access, it is critical that
1545         * <strong>all</strong> access to the backing list is accomplished
1546         * through the returned list.<p>
1547         *
1548         * It is imperative that the user manually synchronize on the returned
1549         * list when iterating over it:
1550         * <pre>
1551         *  List list = Collections.synchronizedList(new ArrayList());
1552         *      ...
1553         *  synchronized(list) {
1554         *      Iterator i = list.iterator(); // Must be in synchronized block
1555         *      while (i.hasNext())
1556         *          foo(i.next());
1557         *  }
1558         * </pre>
1559         * Failure to follow this advice may result in non-deterministic behavior.
1560         *
1561         * <p>The returned list will be serializable if the specified list is
1562         * serializable.
1563         *
1564         * @param  list the list to be "wrapped" in a synchronized list.
1565         * @return a synchronized view of the specified list.
1566         */
1567        public static List synchronizedList(List list) {
1568            return (list instanceof RandomAccess ?
1569                    new SynchronizedRandomAccessList(list) :
1570                    new SynchronizedList(list));
1571        }
1572    
1573        static List synchronizedList(List list, Object mutex) {
1574            return (list instanceof RandomAccess ?
1575                    new SynchronizedRandomAccessList(list, mutex) :
1576                    new SynchronizedList(list, mutex));
1577        }
1578    
1579        /**
1580         * @serial include
1581         */
1582        static class SynchronizedList extends SynchronizedCollection
1583                                      implements List {
1584            static final long serialVersionUID = -7754090372962971524L;
1585    
1586            List list;
1587    
1588            SynchronizedList(List list) {
1589                super(list);
1590                this.list = list;
1591            }
1592            SynchronizedList(List list, Object mutex) {
1593                super(list, mutex);
1594                this.list = list;
1595            }
1596    
1597            @Override
1598            public boolean equals(Object o) {
1599                synchronized(mutex) {return list.equals(o);}
1600            }
1601            @Override
1602            public int hashCode() {
1603                synchronized(mutex) {return list.hashCode();}
1604            }
1605    
1606            @Override
1607            public Object get(int index) {
1608                synchronized(mutex) {return list.get(index);}
1609            }
1610            @Override
1611            public Object set(int index, Object element) {
1612                synchronized(mutex) {return list.set(index, element);}
1613            }
1614            @Override
1615            public void add(int index, Object element) {
1616                synchronized(mutex) {list.add(index, element);}
1617            }
1618            @Override
1619            public Object remove(int index) {
1620                synchronized(mutex) {return list.remove(index);}
1621            }
1622    
1623            @Override
1624            public int indexOf(Object o) {
1625                synchronized(mutex) {return list.indexOf(o);}
1626            }
1627            @Override
1628            public int lastIndexOf(Object o) {
1629                synchronized(mutex) {return list.lastIndexOf(o);}
1630            }
1631    
1632            @Override
1633            public boolean addAll(int index, Collection c) {
1634                synchronized(mutex) {return list.addAll(index, c);}
1635            }
1636    
1637            @Override
1638            public ListIterator listIterator() {
1639                return list.listIterator(); // Must be manually synched by user
1640            }
1641    
1642            @Override
1643            public ListIterator listIterator(int index) {
1644                return list.listIterator(index); // Must be manually synched by usr
1645            }
1646    
1647            @Override
1648            public List subList(int fromIndex, int toIndex) {
1649                synchronized(mutex) {
1650                    return new SynchronizedList(list.subList(fromIndex, toIndex),
1651                                                mutex);
1652                }
1653            }
1654        }
1655    
1656        /**
1657         * @serial include
1658         */
1659        static class SynchronizedRandomAccessList extends SynchronizedList
1660                                                  implements RandomAccess
1661        {
1662            SynchronizedRandomAccessList(List list) {
1663                super(list);
1664            }
1665    
1666            SynchronizedRandomAccessList(List list, Object mutex) {
1667                super(list, mutex);
1668            }
1669    
1670            @Override
1671            public List subList(int fromIndex, int toIndex) {
1672                synchronized(mutex) {
1673                    return new SynchronizedRandomAccessList(
1674                        list.subList(fromIndex, toIndex), mutex);
1675                }
1676            }
1677        }
1678    
1679        /**
1680         * Returns a synchronized (thread-safe) map backed by the specified
1681         * map.  In order to guarantee serial access, it is critical that
1682         * <strong>all</strong> access to the backing map is accomplished
1683         * through the returned map.<p>
1684         *
1685         * It is imperative that the user manually synchronize on the returned
1686         * map when iterating over any of its collection views:
1687         * <pre>
1688         *  Map m = Collections.synchronizedMap(new HashMap());
1689         *      ...
1690         *  Set s = m.keySet();  // Needn't be in synchronized block
1691         *      ...
1692         *  synchronized(m) {  // Synchronizing on m, not s!
1693         *      Iterator i = s.iterator(); // Must be in synchronized block
1694         *      while (i.hasNext())
1695         *          foo(i.next());
1696         *  }
1697         * </pre>
1698         * Failure to follow this advice may result in non-deterministic behavior.
1699         *
1700         * <p>The returned map will be serializable if the specified map is
1701         * serializable.
1702         *
1703         * @param  m the map to be "wrapped" in a synchronized map.
1704         * @return a synchronized view of the specified map.
1705         */
1706        public static Map synchronizedMap(Map m) {
1707            return new SynchronizedMap(m);
1708        }
1709    
1710        /**
1711         * @serial include
1712         */
1713        private static class SynchronizedMap implements Map, Serializable {
1714            // use serialVersionUID from JDK 1.2.2 for interoperability
1715            private static final long serialVersionUID = 1978198479659022715L;
1716    
1717            private Map m;          // Backing Map
1718            Object      mutex;      // Object on which to synchronize
1719    
1720            SynchronizedMap(Map m) {
1721                if (m==null)
1722                    throw new NullPointerException();
1723                this.m = m;
1724                mutex = this;
1725            }
1726    
1727            SynchronizedMap(Map m, Object mutex) {
1728                this.m = m;
1729                this.mutex = mutex;
1730            }
1731    
1732            @Override
1733            public int size() {
1734                synchronized(mutex) {return m.size();}
1735            }
1736            @Override
1737            public boolean isEmpty(){
1738                synchronized(mutex) {return m.isEmpty();}
1739            }
1740            @Override
1741            public boolean containsKey(Object key) {
1742                synchronized(mutex) {return m.containsKey(key);}
1743            }
1744            @Override
1745            public boolean containsValue(Object value){
1746                synchronized(mutex) {return m.containsValue(value);}
1747            }
1748            @Override
1749            public Object get(Object key) {
1750                synchronized(mutex) {return m.get(key);}
1751            }
1752    
1753            @Override
1754            public Object put(Object key, Object value) {
1755                synchronized(mutex) {return m.put(key, value);}
1756            }
1757            @Override
1758            public Object remove(Object key) {
1759                synchronized(mutex) {return m.remove(key);}
1760            }
1761            @Override
1762            public void putAll(Map map) {
1763                synchronized(mutex) {m.putAll(map);}
1764            }
1765            @Override
1766            public void clear() {
1767                synchronized(mutex) {m.clear();}
1768            }
1769    
1770            private transient Set keySet = null;
1771            private transient Set entrySet = null;
1772            private transient Collection values = null;
1773    
1774            @Override
1775            public Set keySet() {
1776                synchronized(mutex) {
1777                    if (keySet==null)
1778                        keySet = new SynchronizedSet(m.keySet(), mutex);
1779                    return keySet;
1780                }
1781            }
1782    
1783            @Override
1784            public Set entrySet() {
1785                synchronized(mutex) {
1786                    if (entrySet==null)
1787                        entrySet = new SynchronizedSet(m.entrySet(), mutex);
1788                    return entrySet;
1789                }
1790            }
1791    
1792            @Override
1793            public Collection values() {
1794                synchronized(mutex) {
1795                    if (values==null)
1796                        values = new SynchronizedCollection(m.values(), mutex);
1797                    return values;
1798                }
1799            }
1800    
1801            @Override
1802            public boolean equals(Object o) {
1803                synchronized(mutex) {return m.equals(o);}
1804            }
1805            @Override
1806            public int hashCode() {
1807                synchronized(mutex) {return m.hashCode();}
1808            }
1809            @Override
1810            public String toString() {
1811                synchronized(mutex) {return m.toString();}
1812            }
1813        }
1814    
1815        /**
1816         * Returns a synchronized (thread-safe) sorted map backed by the specified
1817         * sorted map.  In order to guarantee serial access, it is critical that
1818         * <strong>all</strong> access to the backing sorted map is accomplished
1819         * through the returned sorted map (or its views).<p>
1820         *
1821         * It is imperative that the user manually synchronize on the returned
1822         * sorted map when iterating over any of its collection views, or the
1823         * collections views of any of its <tt>subMap</tt>, <tt>headMap</tt> or
1824         * <tt>tailMap</tt> views.
1825         * <pre>
1826         *  SortedMap m = Collections.synchronizedSortedMap(new HashSortedMap());
1827         *      ...
1828         *  Set s = m.keySet();  // Needn't be in synchronized block
1829         *      ...
1830         *  synchronized(m) {  // Synchronizing on m, not s!
1831         *      Iterator i = s.iterator(); // Must be in synchronized block
1832         *      while (i.hasNext())
1833         *          foo(i.next());
1834         *  }
1835         * </pre>
1836         * or:
1837         * <pre>
1838         *  SortedMap m = Collections.synchronizedSortedMap(new HashSortedMap());
1839         *  SortedMap m2 = m.subMap(foo, bar);
1840         *      ...
1841         *  Set s2 = m2.keySet();  // Needn't be in synchronized block
1842         *      ...
1843         *  synchronized(m) {  // Synchronizing on m, not m2 or s2!
1844         *      Iterator i = s.iterator(); // Must be in synchronized block
1845         *      while (i.hasNext())
1846         *          foo(i.next());
1847         *  }
1848         * </pre>
1849         * Failure to follow this advice may result in non-deterministic behavior.
1850         *
1851         * <p>The returned sorted map will be serializable if the specified
1852         * sorted map is serializable.
1853         *
1854         * @param  m the sorted map to be "wrapped" in a synchronized sorted map.
1855         * @return a synchronized view of the specified sorted map.
1856         */
1857        public static SortedMap synchronizedSortedMap(SortedMap m) {
1858            return new SynchronizedSortedMap(m);
1859        }
1860    
1861    
1862        /**
1863         * @serial include
1864         */
1865        static class SynchronizedSortedMap extends SynchronizedMap
1866                                     implements SortedMap
1867        {
1868            private SortedMap sm;
1869    
1870            SynchronizedSortedMap(SortedMap m) {
1871                super(m);
1872                sm = m;
1873            }
1874            SynchronizedSortedMap(SortedMap m, Object mutex) {
1875                super(m, mutex);
1876                sm = m;
1877            }
1878    
1879            @Override
1880            public Comparator comparator() {
1881                synchronized(mutex) {return sm.comparator();}
1882            }
1883    
1884            @Override
1885            public SortedMap subMap(Object fromKey, Object toKey) {
1886                synchronized(mutex) {
1887                    return new SynchronizedSortedMap(
1888                        sm.subMap(fromKey, toKey), mutex);
1889                }
1890            }
1891            @Override
1892            public SortedMap headMap(Object toKey) {
1893                synchronized(mutex) {
1894                    return new SynchronizedSortedMap(sm.headMap(toKey), mutex);
1895                }
1896            }
1897            @Override
1898            public SortedMap tailMap(Object fromKey) {
1899                synchronized(mutex) {
1900                   return new SynchronizedSortedMap(sm.tailMap(fromKey),mutex);
1901                }
1902            }
1903    
1904            @Override
1905            public Object firstKey() {
1906                synchronized(mutex) {return sm.firstKey();}
1907            }
1908            @Override
1909            public Object lastKey() {
1910                synchronized(mutex) {return sm.lastKey();}
1911            }
1912        }
1913    
1914    
1915        // Miscellaneous
1916    
1917        /**
1918         * The empty set (immutable).  This set is serializable.
1919         */
1920        public static final Set EMPTY_SET = new EmptySet();
1921    
1922        /**
1923         * @serial include
1924         */
1925        private static class EmptySet extends AbstractSet implements Serializable {
1926            // use serialVersionUID from JDK 1.2.2 for interoperability
1927            private static final long serialVersionUID = 1582296315990362920L;
1928    
1929            @Override
1930            public Iterator iterator() {
1931                return new Iterator() {
1932                    public boolean hasNext() {
1933                        return false;
1934                    }
1935                    public Object next() {
1936                        throw new NoSuchElementException();
1937                    }
1938                    public void remove() {
1939                        throw new UnsupportedOperationException();
1940                    }
1941                };
1942            }
1943    
1944            @Override
1945            public int size() {return 0;}
1946    
1947            @Override
1948            public boolean contains(Object obj) {return false;}
1949        }
1950    
1951        /**
1952         * The empty list (immutable).  This list is serializable.
1953         */
1954        public static final List EMPTY_LIST = new EmptyList();
1955    
1956        /**
1957         * @serial include
1958         */
1959        private static class EmptyList extends AbstractList
1960                                       implements RandomAccess, Serializable {
1961            // use serialVersionUID from JDK 1.2.2 for interoperability
1962            private static final long serialVersionUID = 8842843931221139166L;
1963    
1964            @Override
1965            public int size() {return 0;}
1966    
1967            @Override
1968            public boolean contains(Object obj) {return false;}
1969    
1970            @Override
1971            public Object get(int index) {
1972                throw new IndexOutOfBoundsException("Index: "+index);
1973            }
1974        }
1975    
1976        /**
1977         * The empty map (immutable).  This map is serializable.
1978         */
1979        public static final Map EMPTY_MAP = new EmptyMap();
1980    
1981        private static class EmptyMap extends AbstractMap implements Serializable {
1982            @Override
1983            public int size()                          {return 0;}
1984    
1985            @Override
1986            public boolean isEmpty()                   {return true;}
1987    
1988            @Override
1989            public boolean containsKey(Object key)     {return false;}
1990    
1991            @Override
1992            public boolean containsValue(Object value) {return false;}
1993    
1994            @Override
1995            public Object get(Object key)              {return null;}
1996    
1997            @Override
1998            public Set keySet()                        {return EMPTY_SET;}
1999    
2000            @Override
2001            public Collection values()                 {return EMPTY_SET;}
2002    
2003            @Override
2004            public Set entrySet()                      {return EMPTY_SET;}
2005    
2006            @Override
2007            public boolean equals(Object o) {
2008                return (o instanceof Map) && ((Map)o).size()==0;
2009            }
2010    
2011            @Override
2012            public int hashCode()                      {return 0;}
2013        }
2014    
2015        /**
2016         * Returns an immutable set containing only the specified object.
2017         * The returned set is serializable.
2018         *
2019         * @param o the sole object to be stored in the returned set.
2020         * @return an immutable set containing only the specified object.
2021         */
2022        public static Set singleton(Object o) {
2023            return new SingletonSet(o);
2024        }
2025    
2026        /**
2027         * @serial include
2028         */
2029        private static class SingletonSet extends AbstractSet
2030                                          implements Serializable
2031        {
2032            // use serialVersionUID from JDK 1.2.2 for interoperability
2033            private static final long serialVersionUID = 3193687207550431679L;
2034    
2035            private Object element;
2036    
2037            SingletonSet(Object o) {element = o;}
2038    
2039            @Override
2040            public Iterator iterator() {
2041                return new Iterator() {
2042                    private boolean hasNext = true;
2043                    public boolean hasNext() {
2044                        return hasNext;
2045                    }
2046                    public Object next() {
2047                        if (hasNext) {
2048                            hasNext = false;
2049                            return element;
2050                        }
2051                        throw new NoSuchElementException();
2052                    }
2053                    public void remove() {
2054                        throw new UnsupportedOperationException();
2055                    }
2056                };
2057            }
2058    
2059            @Override
2060            public int size() {return 1;}
2061    
2062            @Override
2063            public boolean contains(Object o) {return eq(o, element);}
2064        }
2065    
2066        /**
2067         * Returns an immutable list containing only the specified object.
2068         * The returned list is serializable.
2069         *
2070         * @param o the sole object to be stored in the returned list.
2071         * @return an immutable list containing only the specified object.
2072         */
2073        public static List singletonList(Object o) {
2074            return new SingletonList(o);
2075        }
2076    
2077        private static class SingletonList extends AbstractList
2078                                           implements RandomAccess, Serializable {
2079            static final long serialVersionUID = 3093736618740652951L;
2080    
2081            private final Object element;
2082    
2083            SingletonList(Object obj)           {element = obj;}
2084    
2085            @Override
2086            public int size()                   {return 1;}
2087    
2088            @Override
2089            public boolean contains(Object obj) {return eq(obj, element);}
2090    
2091            @Override
2092            public Object get(int index) {
2093                if (index != 0)
2094                  throw new IndexOutOfBoundsException("Index: "+index+", Size: 1");
2095                return element;
2096            }
2097        }
2098    
2099        /**
2100         * Returns an immutable map, mapping only the specified key to the
2101         * specified value.  The returned map is serializable.
2102         *
2103         * @param key the sole key to be stored in the returned map.
2104         * @param value the value to which the returned map maps <tt>key</tt>.
2105         * @return an immutable map containing only the specified key-value
2106         *         mapping.
2107         */
2108        public static Map singletonMap(Object key, Object value) {
2109            return new SingletonMap(key, value);
2110        }
2111    
2112        private static class SingletonMap extends    AbstractMap
2113                                          implements Serializable {
2114            private final Object k, v;
2115    
2116            SingletonMap(Object key, Object value) {
2117                k = key;
2118                v = value;
2119            }
2120    
2121            @Override
2122            public int size()                          {return 1;}
2123    
2124            @Override
2125            public boolean isEmpty()                   {return false;}
2126    
2127            @Override
2128            public boolean containsKey(Object key)     {return eq(key, k);}
2129    
2130            @Override
2131            public boolean containsValue(Object value) {return eq(value, v);}
2132    
2133            @Override
2134            public Object get(Object key)        {return (eq(key, k) ? v : null);}
2135    
2136            private transient Set keySet = null;
2137            private transient Set entrySet = null;
2138            private transient Collection values = null;
2139    
2140            @Override
2141            public Set keySet() {
2142                if (keySet==null)
2143                    keySet = singleton(k);
2144                return keySet;
2145            }
2146    
2147            @Override
2148            public Set entrySet() {
2149                if (entrySet==null)
2150                    entrySet = singleton(new ImmutableEntry(k, v));
2151                return entrySet;
2152            }
2153    
2154            @Override
2155            public Collection values() {
2156                if (values==null)
2157                    values = singleton(v);
2158                return values;
2159            }
2160    
2161            private static class ImmutableEntry implements Map.Entry {
2162                final Object k;
2163                final Object v;
2164    
2165                ImmutableEntry(Object key, Object value) {
2166                    k = key;
2167                    v = value;
2168                }
2169    
2170                @Override
2171                public Object getKey()   {return k;}
2172    
2173                @Override
2174                public Object getValue() {return v;}
2175    
2176                @Override
2177                public Object setValue(Object value) {
2178                    throw new UnsupportedOperationException();
2179                }
2180    
2181                @Override
2182                public boolean equals(Object o) {
2183                    if (!(o instanceof Map.Entry))
2184                        return false;
2185                    Map.Entry e = (Map.Entry)o;
2186                    return eq(e.getKey(), k) && eq(e.getValue(), v);
2187                }
2188    
2189                @Override
2190                public int hashCode() {
2191                    return ((k==null ? 0 : k.hashCode()) ^
2192                            (v==null ? 0 : v.hashCode()));
2193                }
2194    
2195                @Override
2196                public String toString() {
2197                    return k+"="+v;
2198                }
2199            }
2200        }
2201    
2202        public static List nCopies(int n, Object o) {
2203            return new CopiesList(n, o);
2204        }
2205    
2206        /**
2207         * @serial include
2208         */
2209        private static class CopiesList extends AbstractList
2210                                        implements RandomAccess, Serializable
2211        {
2212            static final long serialVersionUID = 2739099268398711800L;
2213    
2214            int n;
2215            Object element;
2216    
2217            CopiesList(int n, Object o) {
2218                if (n < 0)
2219                    throw new IllegalArgumentException("List length = " + n);
2220                this.n = n;
2221                element = o;
2222            }
2223    
2224            @Override
2225            public int size() {
2226                return n;
2227            }
2228    
2229            @Override
2230            public boolean contains(Object obj) {
2231                return n != 0 && eq(obj, element);
2232            }
2233    
2234            @Override
2235            public Object get(int index) {
2236                if (index<0 || index>=n)
2237                    throw new IndexOutOfBoundsException("Index: "+index+
2238                                                        ", Size: "+n);
2239                return element;
2240            }
2241        }
2242    
2243        public static Comparator reverseOrder() {
2244            return REVERSE_ORDER;
2245        }
2246    
2247        private static final Comparator REVERSE_ORDER = new ReverseComparator();
2248    
2249        /**
2250         * @serial include
2251         */
2252        private static class ReverseComparator implements Comparator,Serializable {
2253            // use serialVersionUID from JDK 1.2.2 for interoperability
2254            private static final long serialVersionUID = 7207038068494060240L;
2255    
2256            @Override
2257            public int compare(Object o1, Object o2) {
2258                Comparable c1 = (Comparable)o1;
2259                Comparable c2 = (Comparable)o2;
2260                return -c1.compareTo(c2);
2261            }
2262        }
2263    
2264        public static Enumeration enumeration(final Collection c) {
2265            return new Enumeration() {
2266                Iterator i = c.iterator();
2267    
2268                public boolean hasMoreElements() {
2269                    return i.hasNext();
2270                }
2271    
2272                public Object nextElement() {
2273                    return i.next();
2274                }
2275            };
2276        }
2277    
2278        public static ArrayList list(Enumeration e) {
2279            ArrayList l = new ArrayList();
2280            while (e.hasMoreElements())
2281                l.add(e.nextElement());
2282            return l;
2283        }
2284    
2285        /**
2286         * Returns true if the specified arguments are equal, or both null.
2287         * @param o1
2288         * @param o2 
2289         * @return is equal
2290         */
2291        private static boolean eq(Object o1, Object o2) {
2292            return (o1==null ? o2==null : o1.equals(o2));
2293        }
2294    }