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        /**
054         * Sorts the specified list into ascending order, according to the
055         * <i>natural ordering</i> of its elements.  All elements in the list must
056         * implement the <tt>Comparable</tt> interface.  Furthermore, all elements
057         * in the list must be <i>mutually comparable</i> (that is,
058         * <tt>e1.compareTo(e2)</tt> must not throw a <tt>ClassCastException</tt>
059         * for any elements <tt>e1</tt> and <tt>e2</tt> in the list).<p>
060         *
061         * This sort is guaranteed to be <i>stable</i>:  equal elements will
062         * not be reordered as a result of the sort.<p>
063         *
064         * The specified list must be modifiable, but need not be resizable.<p>
065         *
066         * The sorting algorithm is a modified mergesort (in which the merge is
067         * omitted if the highest element in the low sublist is less than the
068         * lowest element in the high sublist).  This algorithm offers guaranteed
069         * n log(n) performance, and can approach linear performance on nearly
070         * sorted lists.<p>
071         *
072         * This implementation dumps the specified list into an array, sorts
073         * the array, and iterates over the list resetting each element
074         * from the corresponding position in the array.  This avoids the
075         * n<sup>2</sup> log(n) performance that would result from attempting
076         * to sort a linked list in place.
077         *
078         * @param  list the list to be sorted.
079         * @throws ClassCastException if the list contains elements that are not
080         *         <i>mutually comparable</i> (for example, strings and integers).
081         * @throws UnsupportedOperationException if the specified list's
082         *         list-iterator does not support the <tt>set</tt> operation.
083         * @see Comparable
084         */
085        public static void sort(List list) {
086            Object a[] = list.toArray();
087            Arrays.sort(a);
088            ListIterator i = list.listIterator();
089            for (int j=0; j<a.length; j++) {
090                i.next();
091                i.set(a[j]);
092            }
093        }
094    
095        /**
096         * Sorts the specified list according to the order induced by the
097         * specified comparator.  All elements in the list must be <i>mutually
098         * comparable</i> using the specified comparator (that is,
099         * <tt>c.compare(e1, e2)</tt> must not throw a <tt>ClassCastException</tt>
100         * for any elements <tt>e1</tt> and <tt>e2</tt> in the list).<p>
101         *
102         * This sort is guaranteed to be <i>stable</i>:  equal elements will
103         * not be reordered as a result of the sort.<p>
104         *
105         * The sorting algorithm is a modified mergesort (in which the merge is
106         * omitted if the highest element in the low sublist is less than the
107         * lowest element in the high sublist).  This algorithm offers guaranteed
108         * n log(n) performance, and can approach linear performance on nearly
109         * sorted lists.<p>
110         *
111         * The specified list must be modifiable, but need not be resizable.
112         * This implementation dumps the specified list into an array, sorts
113         * the array, and iterates over the list resetting each element
114         * from the corresponding position in the array.  This avoids the
115         * n<sup>2</sup> log(n) performance that would result from attempting
116         * to sort a linked list in place.
117         *
118         * @param  list the list to be sorted.
119         * @param  c the comparator to determine the order of the list.  A
120         *        <tt>null</tt> value indicates that the elements' <i>natural
121         *        ordering</i> should be used.
122         * @throws ClassCastException if the list contains elements that are not
123         *         <i>mutually comparable</i> using the specified comparator.
124         * @throws UnsupportedOperationException if the specified list's
125         *         list-iterator does not support the <tt>set</tt> operation.
126         * @see Comparator
127         */
128        public static void sort(List list, Comparator c) {
129            Object a[] = list.toArray();
130            Arrays.sort(a, c);
131            ListIterator i = list.listIterator();
132            for (int j=0; j<a.length; j++) {
133                i.next();
134                i.set(a[j]);
135            }
136        }
137    
138    
139        /**
140         * Searches the specified list for the specified object using the binary
141         * search algorithm.  The list must be sorted into ascending order
142         * according to the <i>natural ordering</i> of its elements (as by the
143         * <tt>sort(List)</tt> method, above) prior to making this call.  If it is
144         * not sorted, the results are undefined.  If the list contains multiple
145         * elements equal to the specified object, there is no guarantee which one
146         * will be found.<p>
147         *
148         * This method runs in log(n) time for a "random access" list (which
149         * provides near-constant-time positional access).  If the specified list
150         * does not implement the {@link RandomAccess} and is large, this method
151         * will do an iterator-based binary search that performs O(n) link
152         * traversals and O(log n) element comparisons.
153         *
154         * @param  list the list to be searched.
155         * @param  key the key to be searched for.
156         * @return index of the search key, if it is contained in the list;
157         *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
158         *         <i>insertion point</i> is defined as the point at which the
159         *         key would be inserted into the list: the index of the first
160         *         element greater than the key, or <tt>list.size()</tt>, if all
161         *         elements in the list are less than the specified key.  Note
162         *         that this guarantees that the return value will be &gt;= 0 if
163         *         and only if the key is found.
164         * @throws ClassCastException if the list contains elements that are not
165         *         <i>mutually comparable</i> (for example, strings and
166         *         integers), or the search key in not mutually comparable
167         *         with the elements of the list.
168         * @see    Comparable
169         * @see #sort(List)
170         */
171        public static int binarySearch(List list, Object key) {
172            if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
173                return indexedBinarySearch(list, key);
174            return iteratorBinarySearch(list, key);
175        }
176    
177        private static int indexedBinarySearch(List list, Object key) {
178            int low = 0;
179            int high = list.size()-1;
180    
181            while (low <= high) {
182                int mid = (low + high) >> 1;
183                Object midVal = list.get(mid);
184                int cmp = ((Comparable)midVal).compareTo(key);
185    
186                if (cmp < 0)
187                    low = mid + 1;
188                else if (cmp > 0)
189                    high = mid - 1;
190                else
191                    return mid; // key found
192            }
193            return -(low + 1);  // key not found
194        }
195    
196        private static int iteratorBinarySearch(List list, Object key) {
197            int low = 0;
198            int high = list.size()-1;
199            ListIterator i = list.listIterator();
200    
201            while (low <= high) {
202                int mid = (low + high) >> 1;
203                Object midVal = get(i, mid);
204                int cmp = ((Comparable)midVal).compareTo(key);
205    
206                if (cmp < 0)
207                    low = mid + 1;
208                else if (cmp > 0)
209                    high = mid - 1;
210                else
211                    return mid; // key found
212            }
213            return -(low + 1);  // key not found
214        }
215    
216        /**
217         * Gets the ith element from the given list by repositioning the specified
218         * list listIterator.
219         * @param i
220         * @param index
221         * @return Object
222         */
223        private static Object get(ListIterator i, int index) {
224            Object obj = null;
225            int pos = i.nextIndex();
226            if (pos <= index) {
227                do {
228                    obj = i.next();
229                } while (pos++ < index);
230            } else {
231                do {
232                    obj = i.previous();
233                } while (--pos > index);
234            }
235            return obj;
236        }
237    
238        /**
239         * Searches the specified list for the specified object using the binary
240         * search algorithm.  The list must be sorted into ascending order
241         * according to the specified comparator (as by the <tt>Sort(List,
242         * Comparator)</tt> method, above), prior to making this call.  If it is
243         * not sorted, the results are undefined.  If the list contains multiple
244         * elements equal to the specified object, there is no guarantee which one
245         * will be found.<p>
246         *
247         * This method runs in log(n) time for a "random access" list (which
248         * provides near-constant-time positional access).  If the specified list
249         * does not implement the {@link RandomAccess} and is large, this
250         * this method will do an iterator-based binary search that performs
251         * O(n) link traversals and O(log n) element comparisons.
252         *
253         * @param  list the list to be searched.
254         * @param  key the key to be searched for.
255         * @param  c the comparator by which the list is ordered.  A
256         *        <tt>null</tt> value indicates that the elements' <i>natural
257         *        ordering</i> should be used.
258         * @return index of the search key, if it is contained in the list;
259         *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
260         *         <i>insertion point</i> is defined as the point at which the
261         *         key would be inserted into the list: the index of the first
262         *         element greater than the key, or <tt>list.size()</tt>, if all
263         *         elements in the list are less than the specified key.  Note
264         *         that this guarantees that the return value will be &gt;= 0 if
265         *         and only if the key is found.
266         * @throws ClassCastException if the list contains elements that are not
267         *         <i>mutually comparable</i> using the specified comparator,
268         *         or the search key in not mutually comparable with the
269         *         elements of the list using this comparator.
270         * @see    Comparable
271         * @see #sort(List, Comparator)
272         */
273        public static int binarySearch(List list, Object key, Comparator c) {
274            if (c==null)
275                return binarySearch(list, key);
276    
277            if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
278                return indexedBinarySearch(list, key, c);
279            return iteratorBinarySearch(list, key, c);
280        }
281    
282        private static int indexedBinarySearch(List l, Object key, Comparator c) {
283            int low = 0;
284            int high = l.size()-1;
285    
286            while (low <= high) {
287                int mid = (low + high) >> 1;
288                Object midVal = l.get(mid);
289                int cmp = c.compare(midVal, key);
290    
291                if (cmp < 0)
292                    low = mid + 1;
293                else if (cmp > 0)
294                    high = mid - 1;
295                else
296                    return mid; // key found
297            }
298            return -(low + 1);  // key not found
299        }
300    
301        private static int iteratorBinarySearch(List l, Object key, Comparator c) {
302            int low = 0;
303            int high = l.size()-1;
304            ListIterator i = l.listIterator();
305    
306            while (low <= high) {
307                int mid = (low + high) >> 1;
308                Object midVal = get(i, mid);
309                int cmp = c.compare(midVal, key);
310    
311                if (cmp < 0)
312                    low = mid + 1;
313                else if (cmp > 0)
314                    high = mid - 1;
315                else
316                    return mid; // key found
317            }
318            return -(low + 1);  // key not found
319        }
320    
321        /**
322         * Reverses the order of the elements in the specified list.<p>
323         *
324         * This method runs in linear time.
325         *
326         * @param  list the list whose elements are to be reversed.
327         * @throws UnsupportedOperationException if the specified list or
328         *         its list-iterator does not support the <tt>set</tt> method.
329         */
330        public static void reverse(List list) {
331            int size = list.size();
332            if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {
333                for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--)
334                    swap(list, i, j);
335            } else {
336                ListIterator fwd = list.listIterator();
337                ListIterator rev = list.listIterator(size);
338                for (int i=0, mid=list.size()>>1; i<mid; i++) {
339                    Object tmp = fwd.next();
340                    fwd.set(rev.previous());
341                    rev.set(tmp);
342                }
343            }
344        }
345    
346        /**
347         * Randomly permutes the specified list using a default source of
348         * randomness.  All permutations occur with approximately equal
349         * likelihood.<p>
350         *
351         * The hedge "approximately" is used in the foregoing description because
352         * default source of randomenss is only approximately an unbiased source
353         * of independently chosen bits. If it were a perfect source of randomly
354         * chosen bits, then the algorithm would choose permutations with perfect
355         * uniformity.<p>
356         *
357         * This implementation traverses the list backwards, from the last element
358         * up to the second, repeatedly swapping a randomly selected element into
359         * the "current position".  Elements are randomly selected from the
360         * portion of the list that runs from the first element to the current
361         * position, inclusive.<p>
362         *
363         * This method runs in linear time.  If the specified list does not
364         * implement the {@link RandomAccess} interface and is large, this
365         * implementation dumps the specified list into an array before shuffling
366         * it, and dumps the shuffled array back into the list.  This avoids the
367         * quadratic behavior that would result from shuffling a "sequential
368         * access" list in place.
369         *
370         * @param  list the list to be shuffled.
371         * @throws UnsupportedOperationException if the specified list or
372         *         its list-iterator does not support the <tt>set</tt> method.
373         */
374        public static void shuffle(List list) {
375            shuffle(list, r);
376        }
377        private static Random r = new Random();
378    
379        /**
380         * Randomly permute the specified list using the specified source of
381         * randomness.  All permutations occur with equal likelihood
382         * assuming that the source of randomness is fair.<p>
383         *
384         * This implementation traverses the list backwards, from the last element
385         * up to the second, repeatedly swapping a randomly selected element into
386         * the "current position".  Elements are randomly selected from the
387         * portion of the list that runs from the first element to the current
388         * position, inclusive.<p>
389         *
390         * This method runs in linear time.  If the specified list does not
391         * implement the {@link RandomAccess} interface and is large, this
392         * implementation dumps the specified list into an array before shuffling
393         * it, and dumps the shuffled array back into the list.  This avoids the
394         * quadratic behavior that would result from shuffling a "sequential
395         * access" list in place.
396         *
397         * @param  list the list to be shuffled.
398         * @param  rnd the source of randomness to use to shuffle the list.
399         * @throws UnsupportedOperationException if the specified list or its
400         *         list-iterator does not support the <tt>set</tt> operation.
401         */
402        public static void shuffle(List list, Random rnd) {
403            int size = list.size();
404            if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
405                for (int i=size; i>1; i--)
406                    swap(list, i-1, rnd.nextInt(i));
407            } else {
408                Object arr[] = list.toArray();
409    
410                // Shuffle array
411                for (int i=size; i>1; i--)
412                    swap(arr, i-1, rnd.nextInt(i));
413    
414                // Dump array back into list
415                ListIterator it = list.listIterator();
416                for (int i=0; i<arr.length; i++) {
417                    it.next();
418                    it.set(arr[i]);
419                }
420            }
421        }
422    
423        /**
424         * Swaps the elements at the specified positions in the specified list.
425         * (If the specified positions are equal, invoking this method leaves
426         * the list unchanged.)
427         *
428         * @param list The list in which to swap elements.
429         * @param i the index of one element to be swapped.
430         * @param j the index of the other element to be swapped.
431         * @throws IndexOutOfBoundsException if either <tt>i</tt> or <tt>j</tt>
432         *         is out of range (i &lt; 0 || i &gt;= list.size()
433         *         || j &lt; 0 || j &gt;= list.size()).
434         */
435        public static void swap(List list, int i, int j) {
436            list.set(i, list.set(j, list.get(i)));
437        }
438    
439        /**
440         * Swaps the two specified elements in the specified array.
441         * @param arr
442         * @param i
443         * @param j
444         */
445        private static void swap(Object[] arr, int i, int j) {
446            Object tmp = arr[i];
447            arr[i] = arr[j];
448            arr[j] = tmp;
449        }
450    
451        /**
452         * Replaces all of the elements of the specified list with the specified
453         * element. <p>
454         *
455         * This method runs in linear time.
456         *
457         * @param  list the list to be filled with the specified element.
458         * @param  obj The element with which to fill the specified list.
459         * @throws UnsupportedOperationException if the specified list or its
460         *         list-iterator does not support the <tt>set</tt> operation.
461         */
462        public static void fill(List list, Object obj) {
463            int size = list.size();
464    
465            if (size < FILL_THRESHOLD || list instanceof RandomAccess) {
466                for (int i=0; i<size; i++)
467                    list.set(i, obj);
468            } else {
469                ListIterator itr = list.listIterator();
470                for (int i=0; i<size; i++) {
471                    itr.next();
472                    itr.set(obj);
473                }
474            }
475        }
476    
477        /**
478         * Copies all of the elements from one list into another.  After the
479         * operation, the index of each copied element in the destination list
480         * will be identical to its index in the source list.  The destination
481         * list must be at least as long as the source list.  If it is longer, the
482         * remaining elements in the destination list are unaffected. <p>
483         *
484         * This method runs in linear time.
485         *
486         * @param  dest The destination list.
487         * @param  src The source list.
488         * @throws IndexOutOfBoundsException if the destination list is too small
489         *         to contain the entire source List.
490         * @throws UnsupportedOperationException if the destination list's
491         *         list-iterator does not support the <tt>set</tt> operation.
492         */
493        public static void copy(List dest, List src) {
494            int srcSize = src.size();
495            if (srcSize > dest.size())
496                throw new IndexOutOfBoundsException("Source does not fit in dest");
497    
498            if (srcSize < COPY_THRESHOLD ||
499                (src instanceof RandomAccess && dest instanceof RandomAccess)) {
500                for (int i=0; i<srcSize; i++)
501                    dest.set(i, src.get(i));
502            } else {
503                ListIterator di=dest.listIterator(), si=src.listIterator();
504                for (int i=0; i<srcSize; i++) {
505                    di.next();
506                    di.set(si.next());
507                }
508            }
509        }
510    
511        /**
512         * Returns the minimum element of the given collection, according to the
513         * <i>natural ordering</i> of its elements.  All elements in the
514         * collection must implement the <tt>Comparable</tt> interface.
515         * Furthermore, all elements in the collection must be <i>mutually
516         * comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a
517         * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
518         * <tt>e2</tt> in the collection).<p>
519         *
520         * This method iterates over the entire collection, hence it requires
521         * time proportional to the size of the collection.
522         *
523         * @param  coll the collection whose minimum element is to be determined.
524         * @return the minimum element of the given collection, according
525         *         to the <i>natural ordering</i> of its elements.
526         * @throws ClassCastException if the collection contains elements that are
527         *         not <i>mutually comparable</i> (for example, strings and
528         *         integers).
529         * @throws NoSuchElementException if the collection is empty.
530         * @see Comparable
531         */
532        public static Object min(Collection coll) {
533            Iterator i = coll.iterator();
534            Comparable candidate = (Comparable)(i.next());
535    
536            while(i.hasNext()) {
537                Comparable next = (Comparable)(i.next());
538                if (next.compareTo(candidate) < 0)
539                    candidate = next;
540            }
541            return candidate;
542        }
543    
544        /**
545         * Returns the minimum element of the given collection, according to the
546         * order induced by the specified comparator.  All elements in the
547         * collection must be <i>mutually comparable</i> by the specified
548         * comparator (that is, <tt>comp.compare(e1, e2)</tt> must not throw a
549         * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
550         * <tt>e2</tt> in the collection).<p>
551         *
552         * This method iterates over the entire collection, hence it requires
553         * time proportional to the size of the collection.
554         *
555         * @param  coll the collection whose minimum element is to be determined.
556         * @param  comp the comparator with which to determine the minimum element.
557         *         A <tt>null</tt> value indicates that the elements' <i>natural
558         *         ordering</i> should be used.
559         * @return the minimum element of the given collection, according
560         *         to the specified comparator.
561         * @throws ClassCastException if the collection contains elements that are
562         *         not <i>mutually comparable</i> using the specified comparator.
563         * @throws NoSuchElementException if the collection is empty.
564         * @see Comparable
565         */
566        public static Object min(Collection coll, Comparator comp) {
567            if (comp==null)
568                return min(coll);
569    
570            Iterator i = coll.iterator();
571            Object candidate = i.next();
572    
573            while(i.hasNext()) {
574                Object next = i.next();
575                if (comp.compare(next, candidate) < 0)
576                    candidate = next;
577            }
578            return candidate;
579        }
580    
581        /**
582         * Returns the maximum element of the given collection, according to the
583         * <i>natural ordering</i> of its elements.  All elements in the
584         * collection must implement the <tt>Comparable</tt> interface.
585         * Furthermore, all elements in the collection must be <i>mutually
586         * comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a
587         * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
588         * <tt>e2</tt> in the collection).<p>
589         *
590         * This method iterates over the entire collection, hence it requires
591         * time proportional to the size of the collection.
592         *
593         * @param  coll the collection whose maximum element is to be determined.
594         * @return the maximum element of the given collection, according
595         *         to the <i>natural ordering</i> of its elements.
596         * @throws ClassCastException if the collection contains elements that are
597         *         not <i>mutually comparable</i> (for example, strings and
598         *         integers).
599         * @throws NoSuchElementException if the collection is empty.
600         * @see Comparable
601         */
602        public static Object max(Collection coll) {
603            Iterator i = coll.iterator();
604            Comparable candidate = (Comparable)(i.next());
605    
606            while(i.hasNext()) {
607                Comparable next = (Comparable)(i.next());
608                if (next.compareTo(candidate) > 0)
609                    candidate = next;
610            }
611            return candidate;
612        }
613    
614        /**
615         * Returns the maximum element of the given collection, according to the
616         * order induced by the specified comparator.  All elements in the
617         * collection must be <i>mutually comparable</i> by the specified
618         * comparator (that is, <tt>comp.compare(e1, e2)</tt> must not throw a
619         * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
620         * <tt>e2</tt> in the collection).<p>
621         *
622         * This method iterates over the entire collection, hence it requires
623         * time proportional to the size of the collection.
624         *
625         * @param  coll the collection whose maximum element is to be determined.
626         * @param  comp the comparator with which to determine the maximum element.
627         *         A <tt>null</tt> value indicates that the elements' <i>natural
628         *        ordering</i> should be used.
629         * @return the maximum element of the given collection, according
630         *         to the specified comparator.
631         * @throws ClassCastException if the collection contains elements that are
632         *         not <i>mutually comparable</i> using the specified comparator.
633         * @throws NoSuchElementException if the collection is empty.
634         * @see Comparable
635         */
636        public static Object max(Collection coll, Comparator comp) {
637            if (comp==null)
638                return max(coll);
639    
640            Iterator i = coll.iterator();
641            Object candidate = i.next();
642    
643            while(i.hasNext()) {
644                Object next = i.next();
645                if (comp.compare(next, candidate) > 0)
646                    candidate = next;
647            }
648            return candidate;
649        }
650    
651        /**
652         * Rotates the elements in the specified list by the specified distance.
653         * After calling this method, the element at index <tt>i</tt> will be
654         * the element previously at index <tt>(i - distance)</tt> mod
655         * <tt>list.size()</tt>, for all values of <tt>i</tt> between <tt>0</tt>
656         * and <tt>list.size()-1</tt>, inclusive.  (This method has no effect on
657         * the size of the list.)
658         *
659         * <p>For example, suppose <tt>list</tt> comprises<tt> [t, a, n, k, s]</tt>.
660         * After invoking <tt>Collections.rotate(list, 1)</tt> (or
661         * <tt>Collections.rotate(list, -4)</tt>), <tt>list</tt> will comprise
662         * <tt>[s, t, a, n, k]</tt>.
663         *
664         * <p>Note that this method can usefully be applied to sublists to
665         * move one or more elements within a list while preserving the
666         * order of the remaining elements.  For example, the following idiom
667         * moves the element at index <tt>j</tt> forward to position
668         * <tt>k</tt> (which must be greater than or equal to <tt>j</tt>):
669         * <pre>
670         *     Collections.rotate(list.subList(j, k+1), -1);
671         * </pre>
672         * To make this concrete, suppose <tt>list</tt> comprises
673         * <tt>[a, b, c, d, e]</tt>.  To move the element at index <tt>1</tt>
674         * (<tt>b</tt>) forward two positions, perform the following invocation:
675         * <pre>
676         *     Collections.rotate(l.subList(1, 4), -1);
677         * </pre>
678         * The resulting list is <tt>[a, c, d, b, e]</tt>.
679         * 
680         * <p>To move more than one element forward, increase the absolute value
681         * of the rotation distance.  To move elements backward, use a positive
682         * shift distance.
683         *
684         * <p>If the specified list is small or implements the {@link
685         * RandomAccess} interface, this implementation exchanges the first
686         * element into the location it should go, and then repeatedly exchanges
687         * the displaced element into the location it should go until a displaced
688         * element is swapped into the first element.  If necessary, the process
689         * is repeated on the second and successive elements, until the rotation
690         * is complete.  If the specified list is large and doesn't implement the
691         * <tt>RandomAccess</tt> interface, this implementation breaks the
692         * list into two sublist views around index <tt>-distance mod size</tt>.
693         * Then the {@link #reverse(List)} method is invoked on each sublist view,
694         * and finally it is invoked on the entire list.  For a more complete
695         * description of both algorithms, see Section 2.3 of Jon Bentley's
696         * <i>Programming Pearls</i> (Addison-Wesley, 1986).
697         *
698         * @param list the list to be rotated.
699         * @param distance the distance to rotate the list.  There are no
700         *        constraints on this value; it may be zero, negative, or
701         *        greater than <tt>list.size()</tt>.
702         * @throws UnsupportedOperationException if the specified list or
703         *         its list-iterator does not support the <tt>set</tt> method.
704         */
705        public static void rotate(List list, int distance) {
706            if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD)
707                rotate1(list, distance);
708            else
709                rotate2(list, distance);
710        }
711    
712        private static void rotate1(List list, int distance) {
713            int size = list.size();
714            if (size == 0)
715                return;
716            distance = distance % size;
717            if (distance < 0)
718                distance += size;
719            if (distance == 0)
720                return;
721    
722            for (int cycleStart = 0, nMoved = 0; nMoved != size; cycleStart++) {
723                Object displaced = list.get(cycleStart);
724                int i = cycleStart;
725                do {
726                    i += distance;
727                    if (i >= size)
728                        i -= size;
729                    displaced = list.set(i, displaced);
730                    nMoved ++;
731                } while(i != cycleStart);
732            }
733        }
734    
735        private static void rotate2(List list, int distance) {
736            int size = list.size();
737            if (size == 0)
738                return; 
739            int mid =  -distance % size;
740            if (mid < 0)
741                mid += size;
742            if (mid == 0)
743                return;
744    
745            Collections.reverse(list.subList(0, mid));
746            Collections.reverse(list.subList(mid, size));
747            Collections.reverse(list);
748        }
749    
750        /**
751         * Replaces all occurrences of one specified value in a list with another.
752         * More formally, replaces with <tt>newVal</tt> each element <tt>e</tt>
753         * in <tt>list</tt> such that
754         * <tt>(oldVal==null ? e==null : oldVal.equals(e))</tt>.
755         * (This method has no effect on the size of the list.)
756         *
757         * @param list the list in which replacement is to occur.
758         * @param oldVal the old value to be replaced.
759         * @param newVal the new value with which <tt>oldVal</tt> is to be
760         *        replaced.
761         * @return <tt>true</tt> if <tt>list</tt> contained one or more elements
762         *         <tt>e</tt> such that
763         *         <tt>(oldVal==null ?  e==null : oldVal.equals(e))</tt>.
764         * @throws UnsupportedOperationException if the specified list or
765         *         its list-iterator does not support the <tt>set</tt> method.
766         */
767        public static boolean replaceAll(List list, Object oldVal, Object newVal) {
768            boolean result = false;
769            int size = list.size();
770            if (size < REPLACEALL_THRESHOLD || list instanceof RandomAccess) {
771                if (oldVal==null) {
772                    for (int i=0; i<size; i++) {
773                        if (list.get(i)==null) {
774                            list.set(i, newVal);
775                            result = true;
776                        }
777                    }
778                } else {
779                    for (int i=0; i<size; i++) {
780                        if (oldVal.equals(list.get(i))) {
781                            list.set(i, newVal);
782                            result = true;
783                        }
784                    }
785                }
786            } else {
787                ListIterator itr=list.listIterator();
788                if (oldVal==null) {
789                    for (int i=0; i<size; i++) {
790                        if (itr.next()==null) {
791                            itr.set(newVal);
792                            result = true;
793                        }
794                    }
795                } else {
796                    for (int i=0; i<size; i++) {
797                        if (oldVal.equals(itr.next())) {
798                            itr.set(newVal);
799                            result = true;
800                        }
801                    }
802                }
803            }
804            return result;
805        }
806    
807        /**
808         * Returns the starting position of the first occurrence of the specified
809         * target list within the specified source list, or -1 if there is no
810         * such occurrence.  More formally, returns the the lowest index <tt>i</tt>
811         * such that <tt>source.subList(i, i+target.size()).equals(target)</tt>,
812         * or -1 if there is no such index.  (Returns -1 if
813         * <tt>target.size() > source.size()</tt>.)
814         *
815         * <p>This implementation uses the "brute force" technique of scanning
816         * over the source list, looking for a match with the target at each
817         * location in turn.
818         *
819         * @param source the list in which to search for the first occurrence
820         *        of <tt>target</tt>.
821         * @param target the list to search for as a subList of <tt>source</tt>.
822         * @return the starting position of the first occurrence of the specified
823         *         target list within the specified source list, or -1 if there
824         *         is no such occurrence.
825         */
826        public static int indexOfSubList(List source, List target) {
827            int sourceSize = source.size();
828            int targetSize = target.size();
829            int maxCandidate = sourceSize - targetSize;
830    
831            if (sourceSize < INDEXOFSUBLIST_THRESHOLD ||
832                (source instanceof RandomAccess&&target instanceof RandomAccess)) {
833            nextCand:
834                for (int candidate = 0; candidate <= maxCandidate; candidate++) {
835                    for (int i=0, j=candidate; i<targetSize; i++, j++)
836                        if (!eq(target.get(i), source.get(j)))
837                            continue nextCand;  // Element mismatch, try next cand
838                    return candidate;  // All elements of candidate matched target
839                }
840            } else {  // Iterator version of above algorithm
841                ListIterator si = source.listIterator();
842            nextCand:
843                for (int candidate = 0; candidate <= maxCandidate; candidate++) {
844                    ListIterator ti = target.listIterator();
845                    for (int i=0; i<targetSize; i++) {
846                        if (!eq(ti.next(), si.next())) {
847                            // Back up source iterator to next candidate
848                            for (int j=0; j<i; j++)
849                                si.previous();
850                            continue nextCand;
851                        }
852                    }
853                    return candidate;
854                }
855            }
856            return -1;  // No candidate matched the target
857        }
858    
859        /**
860         * Returns the starting position of the last occurrence of the specified
861         * target list within the specified source list, or -1 if there is no such
862         * occurrence.  More formally, returns the the highest index <tt>i</tt>
863         * such that <tt>source.subList(i, i+target.size()).equals(target)</tt>,
864         * or -1 if there is no such index.  (Returns -1 if
865         * <tt>target.size() > source.size()</tt>.)
866         *
867         * <p>This implementation uses the "brute force" technique of iterating
868         * over the source list, looking for a match with the target at each
869         * location in turn.
870         *
871         * @param source the list in which to search for the last occurrence
872         *        of <tt>target</tt>.
873         * @param target the list to search for as a subList of <tt>source</tt>.
874         * @return the starting position of the last occurrence of the specified
875         *         target list within the specified source list, or -1 if there
876         *         is no such occurrence.
877         */
878        public static int lastIndexOfSubList(List source, List target) {
879            int sourceSize = source.size();
880            int targetSize = target.size();
881            int maxCandidate = sourceSize - targetSize;
882    
883            if (sourceSize < INDEXOFSUBLIST_THRESHOLD ||
884                source instanceof RandomAccess) {   // Index access version
885            nextCand:
886                for (int candidate = maxCandidate; candidate >= 0; candidate--) {
887                    for (int i=0, j=candidate; i<targetSize; i++, j++)
888                        if (!eq(target.get(i), source.get(j)))
889                            continue nextCand;  // Element mismatch, try next cand
890                    return candidate;  // All elements of candidate matched target
891                }
892            } else {  // Iterator version of above algorithm
893                if (maxCandidate < 0)
894                    return -1;
895                ListIterator si = source.listIterator(maxCandidate);
896            nextCand:
897                for (int candidate = maxCandidate; candidate >= 0; candidate--) {
898                    ListIterator ti = target.listIterator();
899                    for (int i=0; i<targetSize; i++) {
900                        if (!eq(ti.next(), si.next())) {
901                            if (candidate != 0) {
902                                // Back up source iterator to next candidate
903                                for (int j=0; j<=i+1; j++)
904                                    si.previous();
905                            }
906                            continue nextCand;
907                        }
908                    }
909                    return candidate;
910                }
911            }
912            return -1;  // No candidate matched the target
913        }
914    
915    
916        // Unmodifiable Wrappers
917    
918        /**
919         * Returns an unmodifiable view of the specified collection.  This method
920         * allows modules to provide users with "read-only" access to internal
921         * collections.  Query operations on the returned collection "read through"
922         * to the specified collection, and attempts to modify the returned
923         * collection, whether direct or via its iterator, result in an
924         * <tt>UnsupportedOperationException</tt>.<p>
925         *
926         * The returned collection does <i>not</i> pass the hashCode and equals
927         * operations through to the backing collection, but relies on
928         * <tt>Object</tt>'s <tt>equals</tt> and <tt>hashCode</tt> methods.  This
929         * is necessary to preserve the contracts of these operations in the case
930         * that the backing collection is a set or a list.<p>
931         *
932         * The returned collection will be serializable if the specified collection
933         * is serializable. 
934         *
935         * @param  c the collection for which an unmodifiable view is to be
936         *         returned.
937         * @return an unmodifiable view of the specified collection.
938         */
939        public static Collection unmodifiableCollection(Collection c) {
940            return new UnmodifiableCollection(c);
941        }
942    
943        /**
944         * @serial include
945         */
946        static class UnmodifiableCollection implements Collection, Serializable {
947            // use serialVersionUID from JDK 1.2.2 for interoperability
948            private static final long serialVersionUID = 1820017752578914078L;
949    
950            Collection c;
951    
952            UnmodifiableCollection(Collection c) {
953                if (c==null)
954                    throw new NullPointerException();
955                this.c = c;
956            }
957    
958            /**
959             * @see java.util.Collection#size()
960             */
961            public int size()                   {return c.size();}
962            /**
963             * @see java.util.Collection#isEmpty()
964             */
965            public boolean isEmpty()            {return c.isEmpty();}
966            /**
967             * @see java.util.Collection#contains(java.lang.Object)
968             */
969            public boolean contains(Object o)   {return c.contains(o);}
970            /**
971             * @see java.util.Collection#toArray()
972             */
973            public Object[] toArray()           {return c.toArray();}
974            /**
975             * @see java.util.Collection#toArray(java.lang.Object[])
976             */
977            public Object[] toArray(Object[] a) {return c.toArray(a);}
978            /**
979             * @see java.lang.Object#toString()
980             */
981            public String toString()            {return c.toString();}
982    
983            /**
984             * @see java.util.Collection#iterator()
985             */
986            public Iterator iterator() {
987                return new Iterator() {
988                    Iterator i = c.iterator();
989    
990                    public boolean hasNext() {return i.hasNext();}
991                    public Object next()     {return i.next();}
992                    public void remove() {
993                        throw new UnsupportedOperationException();
994                    }
995                };
996            }
997    
998            /**
999             * @see java.util.Collection#add(java.lang.Object)
1000             */
1001            public boolean add(Object o){
1002                throw new UnsupportedOperationException();
1003            }
1004            /**
1005             * @see java.util.Collection#remove(java.lang.Object)
1006             */
1007            public boolean remove(Object o) {
1008                throw new UnsupportedOperationException();
1009            }
1010    
1011            /**
1012             * @see java.util.Collection#containsAll(java.util.Collection)
1013             */
1014            public boolean containsAll(Collection coll) {
1015                return c.containsAll(coll);
1016            }
1017            /**
1018             * @see java.util.Collection#addAll(java.util.Collection)
1019             */
1020            public boolean addAll(Collection coll) {
1021                throw new UnsupportedOperationException();
1022            }
1023            /**
1024             * @see java.util.Collection#removeAll(java.util.Collection)
1025             */
1026            public boolean removeAll(Collection coll) {
1027                throw new UnsupportedOperationException();
1028            }
1029            /**
1030             * @see java.util.Collection#retainAll(java.util.Collection)
1031             */
1032            public boolean retainAll(Collection coll) {
1033                throw new UnsupportedOperationException();
1034            }
1035            /**
1036             * @see java.util.Collection#clear()
1037             */
1038            public void clear() {
1039                throw new UnsupportedOperationException();
1040            }
1041        }
1042    
1043        /**
1044         * Returns an unmodifiable view of the specified set.  This method allows
1045         * modules to provide users with "read-only" access to internal sets.
1046         * Query operations on the returned set "read through" to the specified
1047         * set, and attempts to modify the returned set, whether direct or via its
1048         * iterator, result in an <tt>UnsupportedOperationException</tt>.<p>
1049         *
1050         * The returned set will be serializable if the specified set
1051         * is serializable. 
1052         *
1053         * @param  s the set for which an unmodifiable view is to be returned.
1054         * @return an unmodifiable view of the specified set.
1055         */
1056    
1057        public static Set unmodifiableSet(Set s) {
1058            return new UnmodifiableSet(s);
1059        }
1060    
1061        /**
1062         * @serial include
1063         */
1064        static class UnmodifiableSet extends UnmodifiableCollection
1065                                     implements Set, Serializable {
1066            UnmodifiableSet(Set s)          {super(s);}
1067    
1068            /**
1069             * @see java.util.Set#equals(java.lang.Object)
1070             */
1071            public boolean equals(Object o) {return c.equals(o);}
1072            /**
1073             * @see java.util.Set#hashCode()
1074             */
1075            public int hashCode()           {return c.hashCode();}
1076        }
1077    
1078        /**
1079         * Returns an unmodifiable view of the specified sorted set.  This method
1080         * allows modules to provide users with "read-only" access to internal
1081         * sorted sets.  Query operations on the returned sorted set "read
1082         * through" to the specified sorted set.  Attempts to modify the returned
1083         * sorted set, whether direct, via its iterator, or via its
1084         * <tt>subSet</tt>, <tt>headSet</tt>, or <tt>tailSet</tt> views, result in
1085         * an <tt>UnsupportedOperationException</tt>.<p>
1086         *
1087         * The returned sorted set will be serializable if the specified sorted set
1088         * is serializable. 
1089         *
1090         * @param s the sorted set for which an unmodifiable view is to be
1091         *        returned. 
1092         * @return an unmodifiable view of the specified sorted set.
1093         */
1094        public static SortedSet unmodifiableSortedSet(SortedSet s) {
1095            return new UnmodifiableSortedSet(s);
1096        }
1097    
1098        /**
1099         * @serial include
1100         */
1101        static class UnmodifiableSortedSet extends UnmodifiableSet
1102                                     implements SortedSet, Serializable {
1103            private SortedSet ss;
1104    
1105            UnmodifiableSortedSet(SortedSet s) {super(s); ss = s;}
1106    
1107            /**
1108             * @see java.util.SortedSet#comparator()
1109             */
1110            public Comparator comparator()     {return ss.comparator();}
1111    
1112            /**
1113             * @see java.util.SortedSet#subSet(java.lang.Object, java.lang.Object)
1114             */
1115            public SortedSet subSet(Object fromElement, Object toElement) {
1116                return new UnmodifiableSortedSet(ss.subSet(fromElement,toElement));
1117            }
1118            /**
1119             * @see java.util.SortedSet#headSet(java.lang.Object)
1120             */
1121            public SortedSet headSet(Object toElement) {
1122                return new UnmodifiableSortedSet(ss.headSet(toElement));
1123            }
1124            /**
1125             * @see java.util.SortedSet#tailSet(java.lang.Object)
1126             */
1127            public SortedSet tailSet(Object fromElement) {
1128                return new UnmodifiableSortedSet(ss.tailSet(fromElement));
1129            }
1130    
1131            /**
1132             * @see java.util.SortedSet#first()
1133             */
1134            public Object first()              {return ss.first();}
1135            /**
1136             * @see java.util.SortedSet#last()
1137             */
1138            public Object last()               {return ss.last();}
1139        }
1140    
1141        /**
1142         * Returns an unmodifiable view of the specified list.  This method allows
1143         * modules to provide users with "read-only" access to internal
1144         * lists.  Query operations on the returned list "read through" to the
1145         * specified list, and attempts to modify the returned list, whether
1146         * direct or via its iterator, result in an
1147         * <tt>UnsupportedOperationException</tt>.<p>
1148         *
1149         * The returned list will be serializable if the specified list
1150         * is serializable. Similarly, the returned list will implement
1151         * {@link RandomAccess} if the specified list does.
1152         * the 
1153         *
1154         * @param  list the list for which an unmodifiable view is to be returned.
1155         * @return an unmodifiable view of the specified list.
1156         */
1157        public static List unmodifiableList(List list) {
1158            return (list instanceof RandomAccess ?
1159                    new UnmodifiableRandomAccessList(list) :
1160                    new UnmodifiableList(list));
1161        }
1162    
1163        /**
1164         * @serial include
1165         */
1166        static class UnmodifiableList extends UnmodifiableCollection
1167                                      implements List {
1168            static final long serialVersionUID = -283967356065247728L;
1169            List list;
1170    
1171            UnmodifiableList(List list) {
1172                super(list);
1173                this.list = list;
1174            }
1175    
1176            /**
1177             * @see java.util.List#equals(java.lang.Object)
1178             */
1179            public boolean equals(Object o) {return list.equals(o);}
1180            /**
1181             * @see java.util.List#hashCode()
1182             */
1183            public int hashCode()           {return list.hashCode();}
1184    
1185            /**
1186             * @see java.util.List#get(int)
1187             */
1188            public Object get(int index) {return list.get(index);}
1189            /**
1190             * @see java.util.List#set(int, java.lang.Object)
1191             */
1192            public Object set(int index, Object element) {
1193                throw new UnsupportedOperationException();
1194            }
1195            /**
1196             * @see java.util.List#add(int, java.lang.Object)
1197             */
1198            public void add(int index, Object element) {
1199                throw new UnsupportedOperationException();
1200            }
1201            /**
1202             * @see java.util.List#remove(int)
1203             */
1204            public Object remove(int index) {
1205                throw new UnsupportedOperationException();
1206            }
1207            /**
1208             * @see java.util.List#indexOf(java.lang.Object)
1209             */
1210            public int indexOf(Object o)            {return list.indexOf(o);}
1211            /**
1212             * @see java.util.List#lastIndexOf(java.lang.Object)
1213             */
1214            public int lastIndexOf(Object o)        {return list.lastIndexOf(o);}
1215            /**
1216             * @see java.util.List#addAll(int, java.util.Collection)
1217             */
1218            public boolean addAll(int index, Collection c) {
1219                throw new UnsupportedOperationException();
1220            }
1221            /**
1222             * @see java.util.List#listIterator()
1223             */
1224            public ListIterator listIterator()      {return listIterator(0);}
1225    
1226            /**
1227             * @see java.util.List#listIterator(int)
1228             */
1229            public ListIterator listIterator(final int index) {
1230                return new ListIterator() {
1231                    ListIterator i = list.listIterator(index);
1232    
1233                    public boolean hasNext()     {return i.hasNext();}
1234                    public Object next()         {return i.next();}
1235                    public boolean hasPrevious() {return i.hasPrevious();}
1236                    public Object previous()     {return i.previous();}
1237                    public int nextIndex()       {return i.nextIndex();}
1238                    public int previousIndex()   {return i.previousIndex();}
1239    
1240                    public void remove() {
1241                        throw new UnsupportedOperationException();
1242                    }
1243                    public void set(Object o) {
1244                        throw new UnsupportedOperationException();
1245                    }
1246                    public void add(Object o) {
1247                        throw new UnsupportedOperationException();
1248                    }
1249                };
1250            }
1251    
1252            /**
1253             * @see java.util.List#subList(int, int)
1254             */
1255            public List subList(int fromIndex, int toIndex) {
1256                return new UnmodifiableList(list.subList(fromIndex, toIndex));
1257            }
1258        }
1259    
1260        /**
1261         * @serial include
1262         */
1263        static class UnmodifiableRandomAccessList extends UnmodifiableList
1264                                                  implements RandomAccess
1265        {
1266            UnmodifiableRandomAccessList(List list) {
1267                super(list);
1268            }
1269    
1270            /**
1271             * @see railo.commons.collections.Collections.UnmodifiableList#subList(int, int)
1272             */
1273            public List subList(int fromIndex, int toIndex) {
1274                return new UnmodifiableRandomAccessList(
1275                    list.subList(fromIndex, toIndex));
1276            }
1277        }
1278    
1279        /**
1280         * Returns an unmodifiable view of the specified map.  This method
1281         * allows modules to provide users with "read-only" access to internal
1282         * maps.  Query operations on the returned map "read through"
1283         * to the specified map, and attempts to modify the returned
1284         * map, whether direct or via its collection views, result in an
1285         * <tt>UnsupportedOperationException</tt>.<p>
1286         *
1287         * The returned map will be serializable if the specified map
1288         * is serializable. 
1289         *
1290         * @param  m the map for which an unmodifiable view is to be returned.
1291         * @return an unmodifiable view of the specified map.
1292         */
1293        public static Map unmodifiableMap(Map m) {
1294            return new UnmodifiableMap(m);
1295        }
1296    
1297        /**
1298         * @serial include
1299         */
1300        private static class UnmodifiableMap implements Map, Serializable {
1301            // use serialVersionUID from JDK 1.2.2 for interoperability
1302            private static final long serialVersionUID = -1034234728574286014L;
1303    
1304            private final Map m;
1305    
1306            UnmodifiableMap(Map m) {
1307                if (m==null)
1308                    throw new NullPointerException();
1309                this.m = m;
1310            }
1311    
1312            /**
1313             * @see java.util.Map#size()
1314             */
1315            public int size()                        {return m.size();}
1316            /**
1317             * @see java.util.Map#isEmpty()
1318             */
1319            public boolean isEmpty()                 {return m.isEmpty();}
1320            /**
1321             * @see java.util.Map#containsKey(java.lang.Object)
1322             */
1323            public boolean containsKey(Object key)   {return m.containsKey(key);}
1324            /**
1325             * @see java.util.Map#containsValue(java.lang.Object)
1326             */
1327            public boolean containsValue(Object val) {return m.containsValue(val);}
1328            /**
1329             * @see java.util.Map#get(java.lang.Object)
1330             */
1331            public Object get(Object key)            {return m.get(key);}
1332    
1333            /**
1334             * @see java.util.Map#put(java.lang.Object, java.lang.Object)
1335             */
1336            public Object put(Object key, Object value) {
1337                throw new UnsupportedOperationException();
1338            }
1339            /**
1340             * @see java.util.Map#remove(java.lang.Object)
1341             */
1342            public Object remove(Object key) {
1343                throw new UnsupportedOperationException();
1344            }
1345            /**
1346             * @see java.util.Map#putAll(java.util.Map)
1347             */
1348            public void putAll(Map t) {
1349                throw new UnsupportedOperationException();
1350            }
1351            /**
1352             * @see java.util.Map#clear()
1353             */
1354            public void clear() {
1355                throw new UnsupportedOperationException();
1356            }
1357    
1358            private transient Set keySet = null;
1359            private transient Set entrySet = null;
1360            private transient Collection values = null;
1361    
1362            /**
1363             * @see java.util.Map#keySet()
1364             */
1365            public Set keySet() {
1366                if (keySet==null)
1367                    keySet = unmodifiableSet(m.keySet());
1368                return keySet;
1369            }
1370    
1371            /**
1372             * @see java.util.Map#entrySet()
1373             */
1374            public Set entrySet() {
1375                if (entrySet==null)
1376                    entrySet = new UnmodifiableEntrySet(m.entrySet());
1377                return entrySet;
1378            }
1379    
1380            /**
1381             * @see java.util.Map#values()
1382             */
1383            public Collection values() {
1384                if (values==null)
1385                    values = unmodifiableCollection(m.values());
1386                return values;
1387            }
1388    
1389            /**
1390             * @see java.util.Map#equals(java.lang.Object)
1391             */
1392            public boolean equals(Object o) {return m.equals(o);}
1393            /**
1394             * @see java.util.Map#hashCode()
1395             */
1396            public int hashCode()           {return m.hashCode();}
1397            /**
1398             * @see java.lang.Object#toString()
1399             */
1400            public String toString()        {return m.toString();}
1401    
1402            /**
1403             * We need this class in addition to UnmodifiableSet as
1404             * Map.Entries themselves permit modification of the backing Map
1405             * via their setValue operation.  This class is subtle: there are
1406             * many possible attacks that must be thwarted.
1407             *
1408             * @serial include
1409             */
1410            static class UnmodifiableEntrySet extends UnmodifiableSet {
1411                UnmodifiableEntrySet(Set s) {
1412                    super(s);
1413                }
1414    
1415                /**
1416                 * @see java.util.Set#iterator()
1417                 */
1418                public Iterator iterator() {
1419                    return new Iterator() {
1420                        Iterator i = c.iterator();
1421    
1422                        public boolean hasNext() {
1423                            return i.hasNext();
1424                        }
1425                        public Object next()         {
1426                            return new UnmodifiableEntry((Map.Entry)i.next());
1427                        }
1428                        public void remove() {
1429                            throw new UnsupportedOperationException();
1430                        }
1431                    };
1432                }
1433    
1434                /**
1435                 * @see java.util.Set#toArray()
1436                 */
1437                public Object[] toArray() {
1438                    Object[] a = c.toArray();
1439                    for (int i=0; i<a.length; i++)
1440                        a[i] = new UnmodifiableEntry((Map.Entry)a[i]);
1441                    return a;
1442                }
1443    
1444                /**
1445                 * @see java.util.Set#toArray(java.lang.Object[])
1446                 */
1447                public Object[] toArray(Object a[]) {
1448                    // We don't pass a to c.toArray, to avoid window of
1449                    // vulnerability wherein an unscrupulous multithreaded client
1450                    // could get his hands on raw (unwrapped) Entries from c.
1451                    Object[] arr = c.toArray(a.length==0 ? a :
1452                                (Object[])java.lang.reflect.Array.newInstance(
1453                                              a.getClass().getComponentType(), 0));
1454                    for (int i=0; i<arr.length; i++)
1455                        arr[i] = new UnmodifiableEntry((Map.Entry)arr[i]);
1456    
1457                    if (arr.length > a.length)
1458                        return arr;
1459    
1460                    System.arraycopy(arr, 0, a, 0, arr.length);
1461                    if (a.length > arr.length)
1462                        a[arr.length] = null;
1463                    return a;
1464                }
1465    
1466                /**
1467                 * This method is overridden to protect the backing set against
1468                 * an object with a nefarious equals function that senses
1469                 * that the equality-candidate is Map.Entry and calls its
1470                 * setValue method.
1471                 * @param o
1472                 * @return contains or not
1473                 */
1474                public boolean contains(Object o) {
1475                    if (!(o instanceof Map.Entry))
1476                        return false;
1477                    return c.contains(new UnmodifiableEntry((Map.Entry)o));
1478                }
1479    
1480                /**
1481                 * The next two methods are overridden to protect against
1482                 * an unscrupulous List whose contains(Object o) method senses
1483                 * when o is a Map.Entry, and calls o.setValue.
1484                 * @param coll
1485                 * @return boolean
1486                 */
1487                public boolean containsAll(Collection coll) {
1488                    Iterator e = coll.iterator();
1489                    while (e.hasNext())
1490                        if(!contains(e.next())) // Invokes safe contains() above
1491                            return false;
1492                    return true;
1493                }
1494                /**
1495                 * @see railo.commons.collections.Collections.UnmodifiableSet#equals(java.lang.Object)
1496                 */
1497                public boolean equals(Object o) {
1498                    if (o == this)
1499                        return true;
1500    
1501                    if (!(o instanceof Set))
1502                        return false;
1503                    Set s = (Set) o;
1504                    if (s.size() != c.size())
1505                        return false;
1506                    return containsAll(s); // Invokes safe containsAll() above
1507                }
1508    
1509                /**
1510                 * This "wrapper class" serves two purposes: it prevents
1511                 * the client from modifying the backing Map, by short-circuiting
1512                 * the setValue method, and it protects the backing Map against
1513                 * an ill-behaved Map.Entry that attempts to modify another
1514                 * Map Entry when asked to perform an equality check.
1515                 */
1516                private static class UnmodifiableEntry implements Map.Entry {
1517                    private Map.Entry e;
1518    
1519                    UnmodifiableEntry(Map.Entry e) {this.e = e;}
1520    
1521                    /**
1522                     * @see java.util.Map.Entry#getKey()
1523                     */
1524                    public Object getKey()    {return e.getKey();}
1525                    /**
1526                     * @see java.util.Map.Entry#getValue()
1527                     */
1528                    public Object getValue()  {return e.getValue();}
1529                    /**
1530                     * @see java.util.Map.Entry#setValue(java.lang.Object)
1531                     */
1532                    public Object setValue(Object value) {
1533                        throw new UnsupportedOperationException();
1534                    }
1535                    /**
1536                     * @see java.util.Map.Entry#hashCode()
1537                     */
1538                    public int hashCode()     {return e.hashCode();}
1539                    /**
1540                     * @see java.util.Map.Entry#equals(java.lang.Object)
1541                     */
1542                    public boolean equals(Object o) {
1543                        if (!(o instanceof Map.Entry))
1544                            return false;
1545                        Map.Entry t = (Map.Entry)o;
1546                        return eq(e.getKey(),   t.getKey()) &&
1547                               eq(e.getValue(), t.getValue());
1548                    }
1549                    /**
1550                     * @see java.lang.Object#toString()
1551                     */
1552                    public String toString()  {return e.toString();}
1553                }
1554            }
1555        }
1556    
1557        /**
1558         * Returns an unmodifiable view of the specified sorted map.  This method
1559         * allows modules to provide users with "read-only" access to internal
1560         * sorted maps.  Query operations on the returned sorted map "read through"
1561         * to the specified sorted map.  Attempts to modify the returned
1562         * sorted map, whether direct, via its collection views, or via its
1563         * <tt>subMap</tt>, <tt>headMap</tt>, or <tt>tailMap</tt> views, result in
1564         * an <tt>UnsupportedOperationException</tt>.<p>
1565         *
1566         * The returned sorted map will be serializable if the specified sorted map
1567         * is serializable. 
1568         *
1569         * @param m the sorted map for which an unmodifiable view is to be
1570         *        returned. 
1571         * @return an unmodifiable view of the specified sorted map.
1572         */
1573        public static SortedMap unmodifiableSortedMap(SortedMap m) {
1574            return new UnmodifiableSortedMap(m);
1575        }
1576    
1577        /**
1578         * @serial include
1579         */
1580        static class UnmodifiableSortedMap extends UnmodifiableMap
1581                                     implements SortedMap, Serializable {
1582            private SortedMap sm;
1583    
1584            UnmodifiableSortedMap(SortedMap m) {super(m); sm = m;}
1585    
1586            /**
1587             * @see java.util.SortedMap#comparator()
1588             */
1589            public Comparator comparator()     {return sm.comparator();}
1590    
1591            /**
1592             * @see java.util.SortedMap#subMap(java.lang.Object, java.lang.Object)
1593             */
1594            public SortedMap subMap(Object fromKey, Object toKey) {
1595                return new UnmodifiableSortedMap(sm.subMap(fromKey, toKey));
1596            }
1597            /**
1598             * @see java.util.SortedMap#headMap(java.lang.Object)
1599             */
1600            public SortedMap headMap(Object toKey) {
1601                return new UnmodifiableSortedMap(sm.headMap(toKey));
1602            }
1603            /**
1604             * @see java.util.SortedMap#tailMap(java.lang.Object)
1605             */
1606            public SortedMap tailMap(Object fromKey) {
1607                return new UnmodifiableSortedMap(sm.tailMap(fromKey));
1608            }
1609    
1610            /**
1611             * @see java.util.SortedMap#firstKey()
1612             */
1613            public Object firstKey()           {return sm.firstKey();}
1614            /**
1615             * @see java.util.SortedMap#lastKey()
1616             */
1617            public Object lastKey()            {return sm.lastKey();}
1618        }
1619    
1620    
1621        // Synch Wrappers
1622    
1623        /**
1624         * Returns a synchronized (thread-safe) collection backed by the specified
1625         * collection.  In order to guarantee serial access, it is critical that
1626         * <strong>all</strong> access to the backing collection is accomplished
1627         * through the returned collection.<p>
1628         *
1629         * It is imperative that the user manually synchronize on the returned
1630         * collection when iterating over it:
1631         * <pre>
1632         *  Collection c = Collections.synchronizedCollection(myCollection);
1633         *     ...
1634         *  synchronized(c) {
1635         *      Iterator i = c.iterator(); // Must be in the synchronized block
1636         *      while (i.hasNext())
1637         *         foo(i.next());
1638         *  }
1639         * </pre>
1640         * Failure to follow this advice may result in non-deterministic behavior.
1641         *
1642         * <p>The returned collection does <i>not</i> pass the <tt>hashCode</tt>
1643         * and <tt>equals</tt> operations through to the backing collection, but
1644         * relies on <tt>Object</tt>'s equals and hashCode methods.  This is
1645         * necessary to preserve the contracts of these operations in the case
1646         * that the backing collection is a set or a list.<p>
1647         *
1648         * The returned collection will be serializable if the specified collection
1649         * is serializable. 
1650         *
1651         * @param  c the collection to be "wrapped" in a synchronized collection.
1652         * @return a synchronized view of the specified collection.
1653         */
1654        public static Collection synchronizedCollection(Collection c) {
1655            return new SynchronizedCollection(c);
1656        }
1657    
1658        static Collection synchronizedCollection(Collection c, Object mutex) {
1659            return new SynchronizedCollection(c, mutex);
1660        }
1661    
1662        /**
1663         * @serial include
1664         */
1665        static class SynchronizedCollection implements Collection, Serializable {
1666            // use serialVersionUID from JDK 1.2.2 for interoperability
1667            private static final long serialVersionUID = 3053995032091335093L;
1668    
1669            Collection c;      // Backing Collection
1670            Object     mutex;  // Object on which to synchronize
1671    
1672            SynchronizedCollection(Collection c) {
1673                if (c==null)
1674                    throw new NullPointerException();
1675                this.c = c;
1676                mutex = this;
1677            }
1678            SynchronizedCollection(Collection c, Object mutex) {
1679                this.c = c;
1680                this.mutex = mutex;
1681            }
1682    
1683            /**
1684             * @see java.util.Collection#size()
1685             */
1686            public int size() {
1687                synchronized(mutex) {return c.size();}
1688            }
1689            /**
1690             * @see java.util.Collection#isEmpty()
1691             */
1692            public boolean isEmpty() {
1693                synchronized(mutex) {return c.isEmpty();}
1694            }
1695            /**
1696             * @see java.util.Collection#contains(java.lang.Object)
1697             */
1698            public boolean contains(Object o) {
1699                synchronized(mutex) {return c.contains(o);}
1700            }
1701            /**
1702             * @see java.util.Collection#toArray()
1703             */
1704            public Object[] toArray() {
1705                synchronized(mutex) {return c.toArray();}
1706            }
1707            /**
1708             * @see java.util.Collection#toArray(java.lang.Object[])
1709             */
1710            public Object[] toArray(Object[] a) {
1711                synchronized(mutex) {return c.toArray(a);}
1712            }
1713    
1714            /**
1715             * @see java.util.Collection#iterator()
1716             */
1717            public Iterator iterator() {
1718                return c.iterator(); // Must be manually synched by user!
1719            }
1720    
1721            /**
1722             * @see java.util.Collection#add(java.lang.Object)
1723             */
1724            public boolean add(Object o) {
1725                synchronized(mutex) {return c.add(o);}
1726            }
1727            /**
1728             * @see java.util.Collection#remove(java.lang.Object)
1729             */
1730            public boolean remove(Object o) {
1731                synchronized(mutex) {return c.remove(o);}
1732            }
1733    
1734            /**
1735             * @see java.util.Collection#containsAll(java.util.Collection)
1736             */
1737            public boolean containsAll(Collection coll) {
1738                synchronized(mutex) {return c.containsAll(coll);}
1739            }
1740            /**
1741             * @see java.util.Collection#addAll(java.util.Collection)
1742             */
1743            public boolean addAll(Collection coll) {
1744                synchronized(mutex) {return c.addAll(coll);}
1745            }
1746            /**
1747             * @see java.util.Collection#removeAll(java.util.Collection)
1748             */
1749            public boolean removeAll(Collection coll) {
1750                synchronized(mutex) {return c.removeAll(coll);}
1751            }
1752            /**
1753             * @see java.util.Collection#retainAll(java.util.Collection)
1754             */
1755            public boolean retainAll(Collection coll) {
1756                synchronized(mutex) {return c.retainAll(coll);}
1757            }
1758            /**
1759             * @see java.util.Collection#clear()
1760             */
1761            public void clear() {
1762                synchronized(mutex) {c.clear();}
1763            }
1764            /**
1765             * @see java.lang.Object#toString()
1766             */
1767            public String toString() {
1768                synchronized(mutex) {return c.toString();}
1769            }
1770        }
1771    
1772        /**
1773         * Returns a synchronized (thread-safe) set backed by the specified
1774         * set.  In order to guarantee serial access, it is critical that
1775         * <strong>all</strong> access to the backing set is accomplished
1776         * through the returned set.<p>
1777         *
1778         * It is imperative that the user manually synchronize on the returned
1779         * set when iterating over it:
1780         * <pre>
1781         *  Set s = Collections.synchronizedSet(new HashSet());
1782         *      ...
1783         *  synchronized(s) {
1784         *      Iterator i = s.iterator(); // Must be in the synchronized block
1785         *      while (i.hasNext())
1786         *          foo(i.next());
1787         *  }
1788         * </pre>
1789         * Failure to follow this advice may result in non-deterministic behavior.
1790         *
1791         * <p>The returned set will be serializable if the specified set is
1792         * serializable.
1793         *
1794         * @param  s the set to be "wrapped" in a synchronized set.
1795         * @return a synchronized view of the specified set.
1796         */
1797        public static Set synchronizedSet(Set s) {
1798            return new SynchronizedSet(s);
1799        }
1800    
1801        static Set synchronizedSet(Set s, Object mutex) {
1802            return new SynchronizedSet(s, mutex);
1803        }
1804    
1805        /**
1806         * @serial include
1807         */
1808        static class SynchronizedSet extends SynchronizedCollection
1809                                     implements Set {
1810            SynchronizedSet(Set s) {
1811                super(s);
1812            }
1813            SynchronizedSet(Set s, Object mutex) {
1814                super(s, mutex);
1815            }
1816    
1817            /**
1818             * @see java.util.Set#equals(java.lang.Object)
1819             */
1820            public boolean equals(Object o) {
1821                synchronized(mutex) {return c.equals(o);}
1822            }
1823            /**
1824             * @see java.util.Set#hashCode()
1825             */
1826            public int hashCode() {
1827                synchronized(mutex) {return c.hashCode();}
1828            }
1829        }
1830    
1831        /**
1832         * Returns a synchronized (thread-safe) sorted set backed by the specified
1833         * sorted set.  In order to guarantee serial access, it is critical that
1834         * <strong>all</strong> access to the backing sorted set is accomplished
1835         * through the returned sorted set (or its views).<p>
1836         *
1837         * It is imperative that the user manually synchronize on the returned
1838         * sorted set when iterating over it or any of its <tt>subSet</tt>,
1839         * <tt>headSet</tt>, or <tt>tailSet</tt> views.
1840         * <pre>
1841         *  SortedSet s = Collections.synchronizedSortedSet(new HashSortedSet());
1842         *      ...
1843         *  synchronized(s) {
1844         *      Iterator i = s.iterator(); // Must be in the synchronized block
1845         *      while (i.hasNext())
1846         *          foo(i.next());
1847         *  }
1848         * </pre>
1849         * or:
1850         * <pre>
1851         *  SortedSet s = Collections.synchronizedSortedSet(new HashSortedSet());
1852         *  SortedSet s2 = s.headSet(foo);
1853         *      ...
1854         *  synchronized(s) {  // Note: s, not s2!!!
1855         *      Iterator i = s2.iterator(); // Must be in the synchronized block
1856         *      while (i.hasNext())
1857         *          foo(i.next());
1858         *  }
1859         * </pre>
1860         * Failure to follow this advice may result in non-deterministic behavior.
1861         *
1862         * <p>The returned sorted set will be serializable if the specified
1863         * sorted set is serializable.
1864         *
1865         * @param  s the sorted set to be "wrapped" in a synchronized sorted set.
1866         * @return a synchronized view of the specified sorted set.
1867         */
1868        public static SortedSet synchronizedSortedSet(SortedSet s) {
1869            return new SynchronizedSortedSet(s);
1870        }
1871    
1872        /**
1873         * @serial include
1874         */
1875        static class SynchronizedSortedSet extends SynchronizedSet
1876                                     implements SortedSet
1877        {
1878            private SortedSet ss;
1879    
1880            SynchronizedSortedSet(SortedSet s) {
1881                super(s);
1882                ss = s;
1883            }
1884            SynchronizedSortedSet(SortedSet s, Object mutex) {
1885                super(s, mutex);
1886                ss = s;
1887            }
1888    
1889            /**
1890             * @see java.util.SortedSet#comparator()
1891             */
1892            public Comparator comparator() {
1893                synchronized(mutex) {return ss.comparator();}
1894            }
1895    
1896            /**
1897             * @see java.util.SortedSet#subSet(java.lang.Object, java.lang.Object)
1898             */
1899            public SortedSet subSet(Object fromElement, Object toElement) {
1900                synchronized(mutex) {
1901                    return new SynchronizedSortedSet(
1902                        ss.subSet(fromElement, toElement), mutex);
1903                }
1904            }
1905            /**
1906             * @see java.util.SortedSet#headSet(java.lang.Object)
1907             */
1908            public SortedSet headSet(Object toElement) {
1909                synchronized(mutex) {
1910                    return new SynchronizedSortedSet(ss.headSet(toElement), mutex);
1911                }
1912            }
1913            /**
1914             * @see java.util.SortedSet#tailSet(java.lang.Object)
1915             */
1916            public SortedSet tailSet(Object fromElement) {
1917                synchronized(mutex) {
1918                   return new SynchronizedSortedSet(ss.tailSet(fromElement),mutex);
1919                }
1920            }
1921    
1922            /**
1923             * @see java.util.SortedSet#first()
1924             */
1925            public Object first() {
1926                synchronized(mutex) {return ss.first();}
1927            }
1928            /**
1929             * @see java.util.SortedSet#last()
1930             */
1931            public Object last() {
1932                synchronized(mutex) {return ss.last();}
1933            }
1934        }
1935    
1936        /**
1937         * Returns a synchronized (thread-safe) list backed by the specified
1938         * list.  In order to guarantee serial access, it is critical that
1939         * <strong>all</strong> access to the backing list is accomplished
1940         * through the returned list.<p>
1941         *
1942         * It is imperative that the user manually synchronize on the returned
1943         * list when iterating over it:
1944         * <pre>
1945         *  List list = Collections.synchronizedList(new ArrayList());
1946         *      ...
1947         *  synchronized(list) {
1948         *      Iterator i = list.iterator(); // Must be in synchronized block
1949         *      while (i.hasNext())
1950         *          foo(i.next());
1951         *  }
1952         * </pre>
1953         * Failure to follow this advice may result in non-deterministic behavior.
1954         *
1955         * <p>The returned list will be serializable if the specified list is
1956         * serializable.
1957         *
1958         * @param  list the list to be "wrapped" in a synchronized list.
1959         * @return a synchronized view of the specified list.
1960         */
1961        public static List synchronizedList(List list) {
1962            return (list instanceof RandomAccess ?
1963                    new SynchronizedRandomAccessList(list) :
1964                    new SynchronizedList(list));
1965        }
1966    
1967        static List synchronizedList(List list, Object mutex) {
1968            return (list instanceof RandomAccess ?
1969                    new SynchronizedRandomAccessList(list, mutex) :
1970                    new SynchronizedList(list, mutex));
1971        }
1972    
1973        /**
1974         * @serial include
1975         */
1976        static class SynchronizedList extends SynchronizedCollection
1977                                      implements List {
1978            static final long serialVersionUID = -7754090372962971524L;
1979    
1980            List list;
1981    
1982            SynchronizedList(List list) {
1983                super(list);
1984                this.list = list;
1985            }
1986            SynchronizedList(List list, Object mutex) {
1987                super(list, mutex);
1988                this.list = list;
1989            }
1990    
1991            /**
1992             * @see java.util.List#equals(java.lang.Object)
1993             */
1994            public boolean equals(Object o) {
1995                synchronized(mutex) {return list.equals(o);}
1996            }
1997            /**
1998             * @see java.util.List#hashCode()
1999             */
2000            public int hashCode() {
2001                synchronized(mutex) {return list.hashCode();}
2002            }
2003    
2004            /**
2005             * @see java.util.List#get(int)
2006             */
2007            public Object get(int index) {
2008                synchronized(mutex) {return list.get(index);}
2009            }
2010            /**
2011             * @see java.util.List#set(int, java.lang.Object)
2012             */
2013            public Object set(int index, Object element) {
2014                synchronized(mutex) {return list.set(index, element);}
2015            }
2016            /**
2017             * @see java.util.List#add(int, java.lang.Object)
2018             */
2019            public void add(int index, Object element) {
2020                synchronized(mutex) {list.add(index, element);}
2021            }
2022            /**
2023             * @see java.util.List#remove(int)
2024             */
2025            public Object remove(int index) {
2026                synchronized(mutex) {return list.remove(index);}
2027            }
2028    
2029            /**
2030             * @see java.util.List#indexOf(java.lang.Object)
2031             */
2032            public int indexOf(Object o) {
2033                synchronized(mutex) {return list.indexOf(o);}
2034            }
2035            /**
2036             * @see java.util.List#lastIndexOf(java.lang.Object)
2037             */
2038            public int lastIndexOf(Object o) {
2039                synchronized(mutex) {return list.lastIndexOf(o);}
2040            }
2041    
2042            /**
2043             * @see java.util.List#addAll(int, java.util.Collection)
2044             */
2045            public boolean addAll(int index, Collection c) {
2046                synchronized(mutex) {return list.addAll(index, c);}
2047            }
2048    
2049            /**
2050             * @see java.util.List#listIterator()
2051             */
2052            public ListIterator listIterator() {
2053                return list.listIterator(); // Must be manually synched by user
2054            }
2055    
2056            /**
2057             * @see java.util.List#listIterator(int)
2058             */
2059            public ListIterator listIterator(int index) {
2060                return list.listIterator(index); // Must be manually synched by usr
2061            }
2062    
2063            /**
2064             * @see java.util.List#subList(int, int)
2065             */
2066            public List subList(int fromIndex, int toIndex) {
2067                synchronized(mutex) {
2068                    return new SynchronizedList(list.subList(fromIndex, toIndex),
2069                                                mutex);
2070                }
2071            }
2072        }
2073    
2074        /**
2075         * @serial include
2076         */
2077        static class SynchronizedRandomAccessList extends SynchronizedList
2078                                                  implements RandomAccess
2079        {
2080            SynchronizedRandomAccessList(List list) {
2081                super(list);
2082            }
2083    
2084            SynchronizedRandomAccessList(List list, Object mutex) {
2085                super(list, mutex);
2086            }
2087    
2088            /**
2089             * @see railo.commons.collections.Collections.SynchronizedList#subList(int, int)
2090             */
2091            public List subList(int fromIndex, int toIndex) {
2092                synchronized(mutex) {
2093                    return new SynchronizedRandomAccessList(
2094                        list.subList(fromIndex, toIndex), mutex);
2095                }
2096            }
2097        }
2098    
2099        /**
2100         * Returns a synchronized (thread-safe) map backed by the specified
2101         * map.  In order to guarantee serial access, it is critical that
2102         * <strong>all</strong> access to the backing map is accomplished
2103         * through the returned map.<p>
2104         *
2105         * It is imperative that the user manually synchronize on the returned
2106         * map when iterating over any of its collection views:
2107         * <pre>
2108         *  Map m = Collections.synchronizedMap(new HashMap());
2109         *      ...
2110         *  Set s = m.keySet();  // Needn't be in synchronized block
2111         *      ...
2112         *  synchronized(m) {  // Synchronizing on m, not s!
2113         *      Iterator i = s.iterator(); // Must be in synchronized block
2114         *      while (i.hasNext())
2115         *          foo(i.next());
2116         *  }
2117         * </pre>
2118         * Failure to follow this advice may result in non-deterministic behavior.
2119         *
2120         * <p>The returned map will be serializable if the specified map is
2121         * serializable.
2122         *
2123         * @param  m the map to be "wrapped" in a synchronized map.
2124         * @return a synchronized view of the specified map.
2125         */
2126        public static Map synchronizedMap(Map m) {
2127            return new SynchronizedMap(m);
2128        }
2129    
2130        /**
2131         * @serial include
2132         */
2133        private static class SynchronizedMap implements Map, Serializable {
2134            // use serialVersionUID from JDK 1.2.2 for interoperability
2135            private static final long serialVersionUID = 1978198479659022715L;
2136    
2137            private Map m;          // Backing Map
2138            Object      mutex;      // Object on which to synchronize
2139    
2140            SynchronizedMap(Map m) {
2141                if (m==null)
2142                    throw new NullPointerException();
2143                this.m = m;
2144                mutex = this;
2145            }
2146    
2147            SynchronizedMap(Map m, Object mutex) {
2148                this.m = m;
2149                this.mutex = mutex;
2150            }
2151    
2152            /**
2153             * @see java.util.Map#size()
2154             */
2155            public int size() {
2156                synchronized(mutex) {return m.size();}
2157            }
2158            /**
2159             * @see java.util.Map#isEmpty()
2160             */
2161            public boolean isEmpty(){
2162                synchronized(mutex) {return m.isEmpty();}
2163            }
2164            /**
2165             * @see java.util.Map#containsKey(java.lang.Object)
2166             */
2167            public boolean containsKey(Object key) {
2168                synchronized(mutex) {return m.containsKey(key);}
2169            }
2170            /**
2171             * @see java.util.Map#containsValue(java.lang.Object)
2172             */
2173            public boolean containsValue(Object value){
2174                synchronized(mutex) {return m.containsValue(value);}
2175            }
2176            /**
2177             * @see java.util.Map#get(java.lang.Object)
2178             */
2179            public Object get(Object key) {
2180                synchronized(mutex) {return m.get(key);}
2181            }
2182    
2183            /**
2184             * @see java.util.Map#put(java.lang.Object, java.lang.Object)
2185             */
2186            public Object put(Object key, Object value) {
2187                synchronized(mutex) {return m.put(key, value);}
2188            }
2189            /**
2190             * @see java.util.Map#remove(java.lang.Object)
2191             */
2192            public Object remove(Object key) {
2193                synchronized(mutex) {return m.remove(key);}
2194            }
2195            /**
2196             * @see java.util.Map#putAll(java.util.Map)
2197             */
2198            public void putAll(Map map) {
2199                synchronized(mutex) {m.putAll(map);}
2200            }
2201            /**
2202             * @see java.util.Map#clear()
2203             */
2204            public void clear() {
2205                synchronized(mutex) {m.clear();}
2206            }
2207    
2208            private transient Set keySet = null;
2209            private transient Set entrySet = null;
2210            private transient Collection values = null;
2211    
2212            /**
2213             * @see java.util.Map#keySet()
2214             */
2215            public Set keySet() {
2216                synchronized(mutex) {
2217                    if (keySet==null)
2218                        keySet = new SynchronizedSet(m.keySet(), mutex);
2219                    return keySet;
2220                }
2221            }
2222    
2223            /**
2224             * @see java.util.Map#entrySet()
2225             */
2226            public Set entrySet() {
2227                synchronized(mutex) {
2228                    if (entrySet==null)
2229                        entrySet = new SynchronizedSet(m.entrySet(), mutex);
2230                    return entrySet;
2231                }
2232            }
2233    
2234            /**
2235             * @see java.util.Map#values()
2236             */
2237            public Collection values() {
2238                synchronized(mutex) {
2239                    if (values==null)
2240                        values = new SynchronizedCollection(m.values(), mutex);
2241                    return values;
2242                }
2243            }
2244    
2245            /**
2246             * @see java.util.Map#equals(java.lang.Object)
2247             */
2248            public boolean equals(Object o) {
2249                synchronized(mutex) {return m.equals(o);}
2250            }
2251            /**
2252             * @see java.util.Map#hashCode()
2253             */
2254            public int hashCode() {
2255                synchronized(mutex) {return m.hashCode();}
2256            }
2257            /**
2258             * @see java.lang.Object#toString()
2259             */
2260            public String toString() {
2261                synchronized(mutex) {return m.toString();}
2262            }
2263        }
2264    
2265        /**
2266         * Returns a synchronized (thread-safe) sorted map backed by the specified
2267         * sorted map.  In order to guarantee serial access, it is critical that
2268         * <strong>all</strong> access to the backing sorted map is accomplished
2269         * through the returned sorted map (or its views).<p>
2270         *
2271         * It is imperative that the user manually synchronize on the returned
2272         * sorted map when iterating over any of its collection views, or the
2273         * collections views of any of its <tt>subMap</tt>, <tt>headMap</tt> or
2274         * <tt>tailMap</tt> views.
2275         * <pre>
2276         *  SortedMap m = Collections.synchronizedSortedMap(new HashSortedMap());
2277         *      ...
2278         *  Set s = m.keySet();  // Needn't be in synchronized block
2279         *      ...
2280         *  synchronized(m) {  // Synchronizing on m, not s!
2281         *      Iterator i = s.iterator(); // Must be in synchronized block
2282         *      while (i.hasNext())
2283         *          foo(i.next());
2284         *  }
2285         * </pre>
2286         * or:
2287         * <pre>
2288         *  SortedMap m = Collections.synchronizedSortedMap(new HashSortedMap());
2289         *  SortedMap m2 = m.subMap(foo, bar);
2290         *      ...
2291         *  Set s2 = m2.keySet();  // Needn't be in synchronized block
2292         *      ...
2293         *  synchronized(m) {  // Synchronizing on m, not m2 or s2!
2294         *      Iterator i = s.iterator(); // Must be in synchronized block
2295         *      while (i.hasNext())
2296         *          foo(i.next());
2297         *  }
2298         * </pre>
2299         * Failure to follow this advice may result in non-deterministic behavior.
2300         *
2301         * <p>The returned sorted map will be serializable if the specified
2302         * sorted map is serializable.
2303         *
2304         * @param  m the sorted map to be "wrapped" in a synchronized sorted map.
2305         * @return a synchronized view of the specified sorted map.
2306         */
2307        public static SortedMap synchronizedSortedMap(SortedMap m) {
2308            return new SynchronizedSortedMap(m);
2309        }
2310    
2311    
2312        /**
2313         * @serial include
2314         */
2315        static class SynchronizedSortedMap extends SynchronizedMap
2316                                     implements SortedMap
2317        {
2318            private SortedMap sm;
2319    
2320            SynchronizedSortedMap(SortedMap m) {
2321                super(m);
2322                sm = m;
2323            }
2324            SynchronizedSortedMap(SortedMap m, Object mutex) {
2325                super(m, mutex);
2326                sm = m;
2327            }
2328    
2329            /**
2330             * @see java.util.SortedMap#comparator()
2331             */
2332            public Comparator comparator() {
2333                synchronized(mutex) {return sm.comparator();}
2334            }
2335    
2336            /**
2337             * @see java.util.SortedMap#subMap(java.lang.Object, java.lang.Object)
2338             */
2339            public SortedMap subMap(Object fromKey, Object toKey) {
2340                synchronized(mutex) {
2341                    return new SynchronizedSortedMap(
2342                        sm.subMap(fromKey, toKey), mutex);
2343                }
2344            }
2345            /**
2346             * @see java.util.SortedMap#headMap(java.lang.Object)
2347             */
2348            public SortedMap headMap(Object toKey) {
2349                synchronized(mutex) {
2350                    return new SynchronizedSortedMap(sm.headMap(toKey), mutex);
2351                }
2352            }
2353            /**
2354             * @see java.util.SortedMap#tailMap(java.lang.Object)
2355             */
2356            public SortedMap tailMap(Object fromKey) {
2357                synchronized(mutex) {
2358                   return new SynchronizedSortedMap(sm.tailMap(fromKey),mutex);
2359                }
2360            }
2361    
2362            /**
2363             * @see java.util.SortedMap#firstKey()
2364             */
2365            public Object firstKey() {
2366                synchronized(mutex) {return sm.firstKey();}
2367            }
2368            /**
2369             * @see java.util.SortedMap#lastKey()
2370             */
2371            public Object lastKey() {
2372                synchronized(mutex) {return sm.lastKey();}
2373            }
2374        }
2375    
2376    
2377        // Miscellaneous
2378    
2379        /**
2380         * The empty set (immutable).  This set is serializable.
2381         */
2382        public static final Set EMPTY_SET = new EmptySet();
2383    
2384        /**
2385         * @serial include
2386         */
2387        private static class EmptySet extends AbstractSet implements Serializable {
2388            // use serialVersionUID from JDK 1.2.2 for interoperability
2389            private static final long serialVersionUID = 1582296315990362920L;
2390    
2391            /**
2392             * @see java.util.Set#iterator()
2393             */
2394            public Iterator iterator() {
2395                return new Iterator() {
2396                    public boolean hasNext() {
2397                        return false;
2398                    }
2399                    public Object next() {
2400                        throw new NoSuchElementException();
2401                    }
2402                    public void remove() {
2403                        throw new UnsupportedOperationException();
2404                    }
2405                };
2406            }
2407    
2408            /**
2409             * @see java.util.Set#size()
2410             */
2411            public int size() {return 0;}
2412    
2413            /**
2414             * @see java.util.Set#contains(java.lang.Object)
2415             */
2416            public boolean contains(Object obj) {return false;}
2417        }
2418    
2419        /**
2420         * The empty list (immutable).  This list is serializable.
2421         */
2422        public static final List EMPTY_LIST = new EmptyList();
2423    
2424        /**
2425         * @serial include
2426         */
2427        private static class EmptyList extends AbstractList
2428                                       implements RandomAccess, Serializable {
2429            // use serialVersionUID from JDK 1.2.2 for interoperability
2430            private static final long serialVersionUID = 8842843931221139166L;
2431    
2432            /**
2433             * @see java.util.List#size()
2434             */
2435            public int size() {return 0;}
2436    
2437            /**
2438             * @see java.util.List#contains(java.lang.Object)
2439             */
2440            public boolean contains(Object obj) {return false;}
2441    
2442            /**
2443             * @see java.util.AbstractList#get(int)
2444             */
2445            public Object get(int index) {
2446                throw new IndexOutOfBoundsException("Index: "+index);
2447            }
2448        }
2449    
2450        /**
2451         * The empty map (immutable).  This map is serializable.
2452         */
2453        public static final Map EMPTY_MAP = new EmptyMap();
2454    
2455        private static class EmptyMap extends AbstractMap implements Serializable {
2456            /**
2457             * @see java.util.AbstractMap#size()
2458             */
2459            public int size()                          {return 0;}
2460    
2461            /**
2462             * @see java.util.AbstractMap#isEmpty()
2463             */
2464            public boolean isEmpty()                   {return true;}
2465    
2466            /**
2467             * @see java.util.AbstractMap#containsKey(java.lang.Object)
2468             */
2469            public boolean containsKey(Object key)     {return false;}
2470    
2471            /**
2472             * @see java.util.AbstractMap#containsValue(java.lang.Object)
2473             */
2474            public boolean containsValue(Object value) {return false;}
2475    
2476            /**
2477             * @see java.util.AbstractMap#get(java.lang.Object)
2478             */
2479            public Object get(Object key)              {return null;}
2480    
2481            /**
2482             * @see java.util.AbstractMap#keySet()
2483             */
2484            public Set keySet()                        {return EMPTY_SET;}
2485    
2486            /**
2487             * @see java.util.AbstractMap#values()
2488             */
2489            public Collection values()                 {return EMPTY_SET;}
2490    
2491            /**
2492             * @see java.util.AbstractMap#entrySet()
2493             */
2494            public Set entrySet()                      {return EMPTY_SET;}
2495    
2496            /**
2497             * @see java.util.AbstractMap#equals(java.lang.Object)
2498             */
2499            public boolean equals(Object o) {
2500                return (o instanceof Map) && ((Map)o).size()==0;
2501            }
2502    
2503            /**
2504             * @see java.util.AbstractMap#hashCode()
2505             */
2506            public int hashCode()                      {return 0;}
2507        }
2508    
2509        /**
2510         * Returns an immutable set containing only the specified object.
2511         * The returned set is serializable.
2512         *
2513         * @param o the sole object to be stored in the returned set.
2514         * @return an immutable set containing only the specified object.
2515         */
2516        public static Set singleton(Object o) {
2517            return new SingletonSet(o);
2518        }
2519    
2520        /**
2521         * @serial include
2522         */
2523        private static class SingletonSet extends AbstractSet
2524                                          implements Serializable
2525        {
2526            // use serialVersionUID from JDK 1.2.2 for interoperability
2527            private static final long serialVersionUID = 3193687207550431679L;
2528    
2529            private Object element;
2530    
2531            SingletonSet(Object o) {element = o;}
2532    
2533            /**
2534             * @see java.util.Set#iterator()
2535             */
2536            public Iterator iterator() {
2537                return new Iterator() {
2538                    private boolean hasNext = true;
2539                    public boolean hasNext() {
2540                        return hasNext;
2541                    }
2542                    public Object next() {
2543                        if (hasNext) {
2544                            hasNext = false;
2545                            return element;
2546                        }
2547                        throw new NoSuchElementException();
2548                    }
2549                    public void remove() {
2550                        throw new UnsupportedOperationException();
2551                    }
2552                };
2553            }
2554    
2555            /**
2556             * @see java.util.Set#size()
2557             */
2558            public int size() {return 1;}
2559    
2560            /**
2561             * @see java.util.Set#contains(java.lang.Object)
2562             */
2563            public boolean contains(Object o) {return eq(o, element);}
2564        }
2565    
2566        /**
2567         * Returns an immutable list containing only the specified object.
2568         * The returned list is serializable.
2569         *
2570         * @param o the sole object to be stored in the returned list.
2571         * @return an immutable list containing only the specified object.
2572         */
2573        public static List singletonList(Object o) {
2574            return new SingletonList(o);
2575        }
2576    
2577        private static class SingletonList extends AbstractList
2578                                           implements RandomAccess, Serializable {
2579            static final long serialVersionUID = 3093736618740652951L;
2580    
2581            private final Object element;
2582    
2583            SingletonList(Object obj)           {element = obj;}
2584    
2585            /**
2586             * @see java.util.List#size()
2587             */
2588            public int size()                   {return 1;}
2589    
2590            /**
2591             * @see java.util.List#contains(java.lang.Object)
2592             */
2593            public boolean contains(Object obj) {return eq(obj, element);}
2594    
2595            /**
2596             * @see java.util.AbstractList#get(int)
2597             */
2598            public Object get(int index) {
2599                if (index != 0)
2600                  throw new IndexOutOfBoundsException("Index: "+index+", Size: 1");
2601                return element;
2602            }
2603        }
2604    
2605        /**
2606         * Returns an immutable map, mapping only the specified key to the
2607         * specified value.  The returned map is serializable.
2608         *
2609         * @param key the sole key to be stored in the returned map.
2610         * @param value the value to which the returned map maps <tt>key</tt>.
2611         * @return an immutable map containing only the specified key-value
2612         *         mapping.
2613         */
2614        public static Map singletonMap(Object key, Object value) {
2615            return new SingletonMap(key, value);
2616        }
2617    
2618        private static class SingletonMap extends    AbstractMap
2619                                          implements Serializable {
2620            private final Object k, v;
2621    
2622            SingletonMap(Object key, Object value) {
2623                k = key;
2624                v = value;
2625            }
2626    
2627            /**
2628             * @see java.util.AbstractMap#size()
2629             */
2630            public int size()                          {return 1;}
2631    
2632            /**
2633             * @see java.util.AbstractMap#isEmpty()
2634             */
2635            public boolean isEmpty()                   {return false;}
2636    
2637            /**
2638             * @see java.util.AbstractMap#containsKey(java.lang.Object)
2639             */
2640            public boolean containsKey(Object key)     {return eq(key, k);}
2641    
2642            /**
2643             * @see java.util.AbstractMap#containsValue(java.lang.Object)
2644             */
2645            public boolean containsValue(Object value) {return eq(value, v);}
2646    
2647            /**
2648             * @see java.util.AbstractMap#get(java.lang.Object)
2649             */
2650            public Object get(Object key)        {return (eq(key, k) ? v : null);}
2651    
2652            private transient Set keySet = null;
2653            private transient Set entrySet = null;
2654            private transient Collection values = null;
2655    
2656            /**
2657             * @see java.util.AbstractMap#keySet()
2658             */
2659            public Set keySet() {
2660                if (keySet==null)
2661                    keySet = singleton(k);
2662                return keySet;
2663            }
2664    
2665            /**
2666             * @see java.util.AbstractMap#entrySet()
2667             */
2668            public Set entrySet() {
2669                if (entrySet==null)
2670                    entrySet = singleton(new ImmutableEntry(k, v));
2671                return entrySet;
2672            }
2673    
2674            /**
2675             * @see java.util.AbstractMap#values()
2676             */
2677            public Collection values() {
2678                if (values==null)
2679                    values = singleton(v);
2680                return values;
2681            }
2682    
2683            private static class ImmutableEntry implements Map.Entry {
2684                final Object k;
2685                final Object v;
2686    
2687                ImmutableEntry(Object key, Object value) {
2688                    k = key;
2689                    v = value;
2690                }
2691    
2692                /**
2693                 * @see java.util.Map.Entry#getKey()
2694                 */
2695                public Object getKey()   {return k;}
2696    
2697                /**
2698                 * @see java.util.Map.Entry#getValue()
2699                 */
2700                public Object getValue() {return v;}
2701    
2702                /**
2703                 * @see java.util.Map.Entry#setValue(java.lang.Object)
2704                 */
2705                public Object setValue(Object value) {
2706                    throw new UnsupportedOperationException();
2707                }
2708    
2709                /**
2710                 * @see java.util.Map.Entry#equals(java.lang.Object)
2711                 */
2712                public boolean equals(Object o) {
2713                    if (!(o instanceof Map.Entry))
2714                        return false;
2715                    Map.Entry e = (Map.Entry)o;
2716                    return eq(e.getKey(), k) && eq(e.getValue(), v);
2717                }
2718    
2719                /**
2720                 * @see java.util.Map.Entry#hashCode()
2721                 */
2722                public int hashCode() {
2723                    return ((k==null ? 0 : k.hashCode()) ^
2724                            (v==null ? 0 : v.hashCode()));
2725                }
2726    
2727                /**
2728                 * @see java.lang.Object#toString()
2729                 */
2730                public String toString() {
2731                    return k+"="+v;
2732                }
2733            }
2734        }
2735    
2736        /**
2737         * Returns an immutable list consisting of <tt>n</tt> copies of the
2738         * specified object.  The newly allocated data object is tiny (it contains
2739         * a single reference to the data object).  This method is useful in
2740         * combination with the <tt>List.addAll</tt> method to grow lists.
2741         * The returned list is serializable.
2742         *
2743         * @param  n the number of elements in the returned list.
2744         * @param  o the element to appear repeatedly in the returned list.
2745         * @return an immutable list consisting of <tt>n</tt> copies of the
2746         *         specified object.
2747         * @throws IllegalArgumentException if n &lt; 0.
2748         * @see    List#addAll(Collection)
2749         * @see    List#addAll(int, Collection)
2750         */
2751        public static List nCopies(int n, Object o) {
2752            return new CopiesList(n, o);
2753        }
2754    
2755        /**
2756         * @serial include
2757         */
2758        private static class CopiesList extends AbstractList
2759                                        implements RandomAccess, Serializable
2760        {
2761            static final long serialVersionUID = 2739099268398711800L;
2762    
2763            int n;
2764            Object element;
2765    
2766            CopiesList(int n, Object o) {
2767                if (n < 0)
2768                    throw new IllegalArgumentException("List length = " + n);
2769                this.n = n;
2770                element = o;
2771            }
2772    
2773            /**
2774             * @see java.util.List#size()
2775             */
2776            public int size() {
2777                return n;
2778            }
2779    
2780            /**
2781             * @see java.util.List#contains(java.lang.Object)
2782             */
2783            public boolean contains(Object obj) {
2784                return n != 0 && eq(obj, element);
2785            }
2786    
2787            /**
2788             * @see java.util.AbstractList#get(int)
2789             */
2790            public Object get(int index) {
2791                if (index<0 || index>=n)
2792                    throw new IndexOutOfBoundsException("Index: "+index+
2793                                                        ", Size: "+n);
2794                return element;
2795            }
2796        }
2797    
2798        /**
2799         * Returns a comparator that imposes the reverse of the <i>natural
2800         * ordering</i> on a collection of objects that implement the
2801         * <tt>Comparable</tt> interface.  (The natural ordering is the ordering
2802         * imposed by the objects' own <tt>compareTo</tt> method.)  This enables a
2803         * simple idiom for sorting (or maintaining) collections (or arrays) of
2804         * objects that implement the <tt>Comparable</tt> interface in
2805         * reverse-natural-order.  For example, suppose a is an array of
2806         * strings. Then: <pre>
2807         *          Arrays.sort(a, Collections.reverseOrder());
2808         * </pre> sorts the array in reverse-lexicographic (alphabetical) order.<p>
2809         *
2810         * The returned comparator is serializable.
2811         *
2812         * @return a comparator that imposes the reverse of the <i>natural
2813         *         ordering</i> on a collection of objects that implement
2814         *         the <tt>Comparable</tt> interface.
2815         * @see Comparable
2816         */
2817        public static Comparator reverseOrder() {
2818            return REVERSE_ORDER;
2819        }
2820    
2821        private static final Comparator REVERSE_ORDER = new ReverseComparator();
2822    
2823        /**
2824         * @serial include
2825         */
2826        private static class ReverseComparator implements Comparator,Serializable {
2827            // use serialVersionUID from JDK 1.2.2 for interoperability
2828            private static final long serialVersionUID = 7207038068494060240L;
2829    
2830            /**
2831             * @see java.util.Comparator#compare(java.lang.Object, java.lang.Object)
2832             */
2833            public int compare(Object o1, Object o2) {
2834                Comparable c1 = (Comparable)o1;
2835                Comparable c2 = (Comparable)o2;
2836                return -c1.compareTo(c2);
2837            }
2838        }
2839    
2840        /**
2841         * Returns an enumeration over the specified collection.  This provides
2842         * interoperatbility with legacy APIs that require an enumeration
2843         * as input.
2844         *
2845         * @param c the collection for which an enumeration is to be returned.
2846         * @return an enumeration over the specified collection.
2847         * @see Enumeration
2848         */
2849        public static Enumeration enumeration(final Collection c) {
2850            return new Enumeration() {
2851                Iterator i = c.iterator();
2852    
2853                public boolean hasMoreElements() {
2854                    return i.hasNext();
2855                }
2856    
2857                public Object nextElement() {
2858                    return i.next();
2859                }
2860            };
2861        }
2862    
2863        /**
2864         * Returns an array list containing the elements returned by the
2865         * specified enumeration in the order they are returned by the
2866         * enumeration.  This method provides interoperatbility between
2867         * legacy APIs that return enumerations and new APIs that require
2868         * collections.
2869         *
2870         * @param e enumeration providing elements for the returned
2871         *          array list
2872         * @return an array list containing the elements returned
2873         *         by the specified enumeration.
2874         * @see Enumeration
2875         * @see ArrayList
2876         */
2877        public static ArrayList list(Enumeration e) {
2878            ArrayList l = new ArrayList();
2879            while (e.hasMoreElements())
2880                l.add(e.nextElement());
2881            return l;
2882        }
2883    
2884        /**
2885         * Returns true if the specified arguments are equal, or both null.
2886         * @param o1
2887         * @param o2 
2888         * @return is equal
2889         */
2890        private static boolean eq(Object o1, Object o2) {
2891            return (o1==null ? o2==null : o1.equals(o2));
2892        }
2893    }