100 |
|
|
101 |
|
/** |
102 |
|
* Sorts the specified list into ascending order, according to the |
103 |
< |
* <i>natural ordering</i> of its elements. All elements in the list must |
104 |
< |
* implement the <tt>Comparable</tt> interface. Furthermore, all elements |
105 |
< |
* in the list must be <i>mutually comparable</i> (that is, |
106 |
< |
* <tt>e1.compareTo(e2)</tt> must not throw a <tt>ClassCastException</tt> |
107 |
< |
* for any elements <tt>e1</tt> and <tt>e2</tt> in the list).<p> |
108 |
< |
* |
109 |
< |
* This sort is guaranteed to be <i>stable</i>: equal elements will |
110 |
< |
* not be reordered as a result of the sort.<p> |
111 |
< |
* |
112 |
< |
* The specified list must be modifiable, but need not be resizable.<p> |
113 |
< |
* |
114 |
< |
* The sorting algorithm is a modified mergesort (in which the merge is |
115 |
< |
* omitted if the highest element in the low sublist is less than the |
116 |
< |
* lowest element in the high sublist). This algorithm offers guaranteed |
117 |
< |
* n log(n) performance. |
103 |
> |
* {@linkplain Comparable natural ordering} of its elements. |
104 |
> |
* All elements in the list must implement the {@link Comparable} |
105 |
> |
* interface. Furthermore, all elements in the list must be |
106 |
> |
* <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)} |
107 |
> |
* must not throw a {@code ClassCastException} for any elements |
108 |
> |
* {@code e1} and {@code e2} in the list). |
109 |
> |
* |
110 |
> |
* <p>This sort is guaranteed to be <i>stable</i>: equal elements will |
111 |
> |
* not be reordered as a result of the sort. |
112 |
> |
* |
113 |
> |
* <p>The specified list must be modifiable, but need not be resizable. |
114 |
> |
* |
115 |
> |
* <p>Implementation note: This implementation is a stable, adaptive, |
116 |
> |
* iterative mergesort that requires far fewer than n lg(n) comparisons |
117 |
> |
* when the input array is partially sorted, while offering the |
118 |
> |
* performance of a traditional mergesort when the input array is |
119 |
> |
* randomly ordered. If the input array is nearly sorted, the |
120 |
> |
* implementation requires approximately n comparisons. Temporary |
121 |
> |
* storage requirements vary from a small constant for nearly sorted |
122 |
> |
* input arrays to n/2 object references for randomly ordered input |
123 |
> |
* arrays. |
124 |
> |
* |
125 |
> |
* <p>The implementation takes equal advantage of ascending and |
126 |
> |
* descending order in its input array, and can take advantage of |
127 |
> |
* ascending and descending order in different parts of the same |
128 |
> |
* input array. It is well-suited to merging two or more sorted arrays: |
129 |
> |
* simply concatenate the arrays and sort the resulting array. |
130 |
> |
* |
131 |
> |
* <p>The implementation was adapted from Tim Peters's list sort for Python |
132 |
> |
* (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt"> |
133 |
> |
* TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic |
134 |
> |
* Sorting and Information Theoretic Complexity", in Proceedings of the |
135 |
> |
* Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, |
136 |
> |
* January 1993. |
137 |
|
* |
138 |
< |
* This implementation dumps the specified list into an array, sorts |
138 |
> |
* <p>This implementation dumps the specified list into an array, sorts |
139 |
|
* the array, and iterates over the list resetting each element |
140 |
|
* from the corresponding position in the array. This avoids the |
141 |
|
* n<sup>2</sup> log(n) performance that would result from attempting |
145 |
|
* @throws ClassCastException if the list contains elements that are not |
146 |
|
* <i>mutually comparable</i> (for example, strings and integers). |
147 |
|
* @throws UnsupportedOperationException if the specified list's |
148 |
< |
* list-iterator does not support the <tt>set</tt> operation. |
149 |
< |
* @see Comparable |
148 |
> |
* list-iterator does not support the {@code set} operation. |
149 |
> |
* @throws IllegalArgumentException (optional) if the implementation |
150 |
> |
* detects that the natural ordering of the list elements is |
151 |
> |
* found to violate the {@link Comparable} contract |
152 |
|
*/ |
153 |
|
public static <T extends Comparable<? super T>> void sort(List<T> list) { |
154 |
|
Object[] a = list.toArray(); |
164 |
|
* Sorts the specified list according to the order induced by the |
165 |
|
* specified comparator. All elements in the list must be <i>mutually |
166 |
|
* comparable</i> using the specified comparator (that is, |
167 |
< |
* <tt>c.compare(e1, e2)</tt> must not throw a <tt>ClassCastException</tt> |
168 |
< |
* for any elements <tt>e1</tt> and <tt>e2</tt> in the list).<p> |
167 |
> |
* {@code c.compare(e1, e2)} must not throw a {@code ClassCastException} |
168 |
> |
* for any elements {@code e1} and {@code e2} in the list). |
169 |
|
* |
170 |
< |
* This sort is guaranteed to be <i>stable</i>: equal elements will |
171 |
< |
* not be reordered as a result of the sort.<p> |
170 |
> |
* <p>This sort is guaranteed to be <i>stable</i>: equal elements will |
171 |
> |
* not be reordered as a result of the sort. |
172 |
|
* |
173 |
< |
* The sorting algorithm is a modified mergesort (in which the merge is |
153 |
< |
* omitted if the highest element in the low sublist is less than the |
154 |
< |
* lowest element in the high sublist). This algorithm offers guaranteed |
155 |
< |
* n log(n) performance. |
173 |
> |
* <p>The specified list must be modifiable, but need not be resizable. |
174 |
|
* |
175 |
< |
* The specified list must be modifiable, but need not be resizable. |
176 |
< |
* This implementation dumps the specified list into an array, sorts |
175 |
> |
* <p>Implementation note: This implementation is a stable, adaptive, |
176 |
> |
* iterative mergesort that requires far fewer than n lg(n) comparisons |
177 |
> |
* when the input array is partially sorted, while offering the |
178 |
> |
* performance of a traditional mergesort when the input array is |
179 |
> |
* randomly ordered. If the input array is nearly sorted, the |
180 |
> |
* implementation requires approximately n comparisons. Temporary |
181 |
> |
* storage requirements vary from a small constant for nearly sorted |
182 |
> |
* input arrays to n/2 object references for randomly ordered input |
183 |
> |
* arrays. |
184 |
> |
* |
185 |
> |
* <p>The implementation takes equal advantage of ascending and |
186 |
> |
* descending order in its input array, and can take advantage of |
187 |
> |
* ascending and descending order in different parts of the same |
188 |
> |
* input array. It is well-suited to merging two or more sorted arrays: |
189 |
> |
* simply concatenate the arrays and sort the resulting array. |
190 |
> |
* |
191 |
> |
* <p>The implementation was adapted from Tim Peters's list sort for Python |
192 |
> |
* (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt"> |
193 |
> |
* TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic |
194 |
> |
* Sorting and Information Theoretic Complexity", in Proceedings of the |
195 |
> |
* Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, |
196 |
> |
* January 1993. |
197 |
> |
* |
198 |
> |
* <p>This implementation dumps the specified list into an array, sorts |
199 |
|
* the array, and iterates over the list resetting each element |
200 |
|
* from the corresponding position in the array. This avoids the |
201 |
|
* n<sup>2</sup> log(n) performance that would result from attempting |
203 |
|
* |
204 |
|
* @param list the list to be sorted. |
205 |
|
* @param c the comparator to determine the order of the list. A |
206 |
< |
* <tt>null</tt> value indicates that the elements' <i>natural |
206 |
> |
* {@code null} value indicates that the elements' <i>natural |
207 |
|
* ordering</i> should be used. |
208 |
|
* @throws ClassCastException if the list contains elements that are not |
209 |
|
* <i>mutually comparable</i> using the specified comparator. |
210 |
|
* @throws UnsupportedOperationException if the specified list's |
211 |
< |
* list-iterator does not support the <tt>set</tt> operation. |
212 |
< |
* @see Comparator |
211 |
> |
* list-iterator does not support the {@code set} operation. |
212 |
> |
* @throws IllegalArgumentException (optional) if the comparator is |
213 |
> |
* found to violate the {@link Comparator} contract |
214 |
|
*/ |
215 |
|
public static <T> void sort(List<T> list, Comparator<? super T> c) { |
216 |
|
Object[] a = list.toArray(); |
823 |
|
i -= size; |
824 |
|
displaced = list.set(i, displaced); |
825 |
|
nMoved ++; |
826 |
< |
} while(i != cycleStart); |
826 |
> |
} while (i != cycleStart); |
827 |
|
} |
828 |
|
} |
829 |
|
|
1452 |
|
* when o is a Map.Entry, and calls o.setValue. |
1453 |
|
*/ |
1454 |
|
public boolean containsAll(Collection<?> coll) { |
1455 |
< |
Iterator<?> e = coll.iterator(); |
1456 |
< |
while (e.hasNext()) |
1457 |
< |
if (!contains(e.next())) // Invokes safe contains() above |
1455 |
> |
Iterator<?> it = coll.iterator(); |
1456 |
> |
while (it.hasNext()) |
1457 |
> |
if (!contains(it.next())) // Invokes safe contains() above |
1458 |
|
return false; |
1459 |
|
return true; |
1460 |
|
} |