ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/Collections.java
(Generate patch)

Comparing jsr166/src/main/java/util/Collections.java (file contents):
Revision 1.24 by jsr166, Thu Apr 20 07:24:42 2006 UTC vs.
Revision 1.28 by jsr166, Sun May 28 23:36:29 2006 UTC

# Line 38 | Line 38 | import java.lang.reflect.Array;
38   * already sorted may or may not throw <tt>UnsupportedOperationException</tt>.
39   *
40   * <p>This class is a member of the
41 < * <a href="{@docRoot}/../guide/collections/index.html">
41 > * <a href="{@docRoot}/../technotes/guides/collections/index.html">
42   * Java Collections Framework</a>.
43   *
44   * @author  Josh Bloch
# Line 168 | Line 168 | public class Collections {
168      /**
169       * Searches the specified list for the specified object using the binary
170       * search algorithm.  The list must be sorted into ascending order
171 <     * according to the <i>natural ordering</i> of its elements (as by the
172 <     * <tt>sort(List)</tt> method, above) prior to making this call.  If it is
173 <     * not sorted, the results are undefined.  If the list contains multiple
174 <     * elements equal to the specified object, there is no guarantee which one
175 <     * will be found.<p>
171 >     * according to the {@linkplain Comparable natural ordering} of its
172 >     * elements (as by the {@link #sort(List)} method) prior to making this
173 >     * call.  If it is not sorted, the results are undefined.  If the list
174 >     * contains multiple elements equal to the specified object, there is no
175 >     * guarantee which one will be found.
176       *
177 <     * This method runs in log(n) time for a "random access" list (which
177 >     * <p>This method runs in log(n) time for a "random access" list (which
178       * provides near-constant-time positional access).  If the specified list
179       * does not implement the {@link RandomAccess} interface and is large,
180       * this method will do an iterator-based binary search that performs
# Line 186 | Line 186 | public class Collections {
186       *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
187       *         <i>insertion point</i> is defined as the point at which the
188       *         key would be inserted into the list: the index of the first
189 <     *         element greater than the key, or <tt>list.size()</tt>, if all
189 >     *         element greater than the key, or <tt>list.size()</tt> if all
190       *         elements in the list are less than the specified key.  Note
191       *         that this guarantees that the return value will be &gt;= 0 if
192       *         and only if the key is found.
193       * @throws ClassCastException if the list contains elements that are not
194       *         <i>mutually comparable</i> (for example, strings and
195 <     *         integers), or the search key in not mutually comparable
195 >     *         integers), or the search key is not mutually comparable
196       *         with the elements of the list.
197 –     * @see    Comparable
198 –     * @see #sort(List)
197       */
198      public static <T>
199      int binarySearch(List<? extends Comparable<? super T>> list, T key) {
# Line 212 | Line 210 | public class Collections {
210          int high = list.size()-1;
211  
212          while (low <= high) {
213 <            int mid = (low + high) >> 1;
213 >            int mid = (low + high) >>> 1;
214              Comparable<? super T> midVal = list.get(mid);
215              int cmp = midVal.compareTo(key);
216  
# Line 234 | Line 232 | public class Collections {
232          ListIterator<? extends Comparable<? super T>> i = list.listIterator();
233  
234          while (low <= high) {
235 <            int mid = (low + high) >> 1;
235 >            int mid = (low + high) >>> 1;
236              Comparable<? super T> midVal = get(i, mid);
237              int cmp = midVal.compareTo(key);
238  
# Line 270 | Line 268 | public class Collections {
268      /**
269       * Searches the specified list for the specified object using the binary
270       * search algorithm.  The list must be sorted into ascending order
271 <     * according to the specified comparator (as by the <tt>Sort(List,
272 <     * Comparator)</tt> method, above), prior to making this call.  If it is
271 >     * according to the specified comparator (as by the
272 >     * {@link #sort(List, Comparator) sort(List, Comparator)}
273 >     * method), prior to making this call.  If it is
274       * not sorted, the results are undefined.  If the list contains multiple
275       * elements equal to the specified object, there is no guarantee which one
276 <     * will be found.<p>
276 >     * will be found.
277       *
278 <     * This method runs in log(n) time for a "random access" list (which
278 >     * <p>This method runs in log(n) time for a "random access" list (which
279       * provides near-constant-time positional access).  If the specified list
280       * does not implement the {@link RandomAccess} interface and is large,
281       * this method will do an iterator-based binary search that performs
# Line 284 | Line 283 | public class Collections {
283       *
284       * @param  list the list to be searched.
285       * @param  key the key to be searched for.
286 <     * @param  c the comparator by which the list is ordered.  A
287 <     *        <tt>null</tt> value indicates that the elements' <i>natural
288 <     *        ordering</i> should be used.
286 >     * @param  c the comparator by which the list is ordered.
287 >     *         A <tt>null</tt> value indicates that the elements'
288 >     *         {@linkplain Comparable natural ordering} should be used.
289       * @return the index of the search key, if it is contained in the list;
290       *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
291       *         <i>insertion point</i> is defined as the point at which the
292       *         key would be inserted into the list: the index of the first
293 <     *         element greater than the key, or <tt>list.size()</tt>, if all
293 >     *         element greater than the key, or <tt>list.size()</tt> if all
294       *         elements in the list are less than the specified key.  Note
295       *         that this guarantees that the return value will be &gt;= 0 if
296       *         and only if the key is found.
297       * @throws ClassCastException if the list contains elements that are not
298       *         <i>mutually comparable</i> using the specified comparator,
299 <     *         or the search key in not mutually comparable with the
299 >     *         or the search key is not mutually comparable with the
300       *         elements of the list using this comparator.
302 –     * @see    Comparable
303 –     * @see #sort(List, Comparator)
301       */
302      public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) {
303          if (c==null)
# Line 317 | Line 314 | public class Collections {
314          int high = l.size()-1;
315  
316          while (low <= high) {
317 <            int mid = (low + high) >> 1;
317 >            int mid = (low + high) >>> 1;
318              T midVal = l.get(mid);
319              int cmp = c.compare(midVal, key);
320  
# Line 337 | Line 334 | public class Collections {
334          ListIterator<? extends T> i = l.listIterator();
335  
336          while (low <= high) {
337 <            int mid = (low + high) >> 1;
337 >            int mid = (low + high) >>> 1;
338              T midVal = get(i, mid);
339              int cmp = c.compare(midVal, key);
340  

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines