KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > java > util > Collections


1 /*
2  * Copyright 2007 Google Inc.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License"); you may not
5  * use this file except in compliance with the License. You may obtain a copy of
6  * the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
12  * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
13  * License for the specific language governing permissions and limitations under
14  * the License.
15  */
16 package java.util;
17
18 /**
19  * Utility methods that operate on collections.
20  */
21 public class Collections {
22
23   public static final Set JavaDoc EMPTY_SET = new HashSet JavaDoc();
24   public static final Map JavaDoc EMPTY_MAP = new HashMap JavaDoc();
25   public static final List JavaDoc EMPTY_LIST = new ArrayList JavaDoc();
26
27   /**
28    * Perform a binary search on a sorted List, using natural ordering.
29    *
30    * <p>
31    * Note: The GWT implementation differs from the JDK implementation in that it
32    * does not do an iterator-based binary search for Lists that do not implement
33    * RandomAccess.
34    * </p>
35    *
36    * @param sortedList object array to search
37    * @param key value to search for
38    * @return the index of an element with a matching value, or a negative number
39    * which is the index of the next larger value (or just past the end
40    * of the array if the searched value is larger than all elements in
41    * the array) minus 1 (to ensure error returns are negative)
42    * @throws ClassCastException if <code>key</code> is not comparable to
43    * <code>sortedList</code>'s elements.
44    */
45   public static int binarySearch(final List JavaDoc sortedList, final Object JavaDoc key) {
46     return binarySearch(sortedList, key, Comparators.natural());
47   }
48
49   /**
50    * Perform a binary search on a sorted List, using a user-specified comparison
51    * function.
52    *
53    * <p>
54    * Note: The GWT implementation differs from the JDK implementation in that it
55    * does not do an iterator-based binary search for Lists that do not implement
56    * RandomAccess.
57    * </p>
58    *
59    * @param sortedList List to search
60    * @param key value to search for
61    * @param comparator comparision function, <code>null</code> indicates
62    * <i>natural ordering</i> should be used.
63    * @return the index of an element with a matching value, or a negative number
64    * which is the index of the next larger value (or just past the end
65    * of the array if the searched value is larger than all elements in
66    * the array) minus 1 (to ensure error returns are negative)
67    * @throws ClassCastException if <code>key</code> and
68    * <code>sortedList</code>'s elements cannot be compared by
69    * <code>comparator</code>.
70    */
71   public static int binarySearch(final List JavaDoc sortedList, final Object JavaDoc key,
72       Comparator JavaDoc comparator) {
73     /*
74      * TODO: This doesn't implement the "iterator-based binary search" described
75      * in the JDK docs for non-RandomAccess Lists. Until GWT provides a
76      * LinkedList, this shouldn't be an issue.
77      */
78     comparator = comparator != null ? comparator : Comparators.natural();
79     int low = 0;
80     int high = sortedList.size() - 1;
81
82     while (low <= high) {
83       final int mid = low + ((high - low) / 2);
84       final Object JavaDoc midVal = sortedList.get(mid);
85       final int compareResult = comparator.compare(midVal, key);
86
87       if (compareResult < 0) {
88         low = mid + 1;
89       } else if (compareResult > 0) {
90         high = mid - 1;
91       } else {
92         // key found
93 return mid;
94       }
95     }
96     // key not found.
97 return -low - 1;
98   }
99
100   public static void reverse(List JavaDoc l) {
101     int lastPos = l.size() - 1;
102     for (int i = 0; i < l.size() / 2; i++) {
103       Object JavaDoc element = l.get(i);
104       int swapPos = lastPos - i;
105       assert (swapPos > i);
106       Object JavaDoc swappedWith = l.get(swapPos);
107       l.set(i, swappedWith);
108       l.set(swapPos, element);
109     }
110   }
111
112   public static void sort(List JavaDoc target) {
113     Object JavaDoc[] x = target.toArray();
114     Arrays.sort(x);
115     replaceContents(target, x);
116   }
117
118   public static void sort(List JavaDoc target, Comparator JavaDoc y) {
119     Object JavaDoc[] x = target.toArray();
120     Arrays.sort(x, y);
121     replaceContents(target, x);
122   }
123
124   private static void replaceContents(List JavaDoc target, Object JavaDoc[] x) {
125     int size = target.size();
126     assert (x.length == size);
127     for (int i = 0; i < size; i++) {
128       target.set(i, x[i]);
129     }
130   }
131 }
132
Popular Tags