pkg/dev_compiler/tool/input_sdk/lib/internal/sort.dart - Issue 2698353003: unfork DDC's copy of most SDK libraries

Side by Side Diff: pkg/dev_compiler/tool/input_sdk/lib/internal/sort.dart

Issue 2698353003: unfork DDC's copy of most SDK libraries (Closed)

Patch Set: revert core_patch Created 3 years, 9 months ago

Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.

Jump to:

OLD	NEW
	(Empty)
1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file

2 // for details. All rights reserved. Use of this source code is governed by a

3 // BSD-style license that can be found in the LICENSE file.

4

5 part of dart._internal;

6

7 /**

8 * Dual-Pivot Quicksort algorithm.

9 *

10 * This class implements the dual-pivot quicksort algorithm as presented in

11 * Vladimir Yaroslavskiy's paper.

12 *

13 * Some improvements have been copied from Android's implementation.

14 */

15 class Sort {

16 // When a list has less then [:_INSERTION_SORT_THRESHOLD:] elements it will

17 // be sorted by an insertion sort.

18 static const int _INSERTION_SORT_THRESHOLD = 32;

19

20 /**

21 * Sorts all elements of the given list [:a:] according to the given

22 * [:compare:] function.

23 *

24 * The [:compare:] function takes two arguments [:x:] and [:y:] and returns

25 * -1 if [:x < y:],

26 * 0 if [:x == y:], and

27 * 1 if [:x > y:].

28 *

29 * The function's behavior must be consistent. It must not return different

30 * results for the same values.

31 */

32 static void sort/<E>/(List/<E>/ a, int compare(dynamic /=E/ a, dynamic / =E/ b)) {

33 _doSort(a, 0, a.length - 1, compare);

34 }

35

36 /**

37 * Sorts all elements in the range [:from:] (inclusive) to [:to:] (exclusive)

38 * of the given list [:a:].

39 *

40 * If the given range is invalid an "OutOfRange" error is raised.

41 * TODO(floitsch): do we want an error?

42 *

43 * See [:sort:] for requirements of the [:compare:] function.

44 */

45 static void sortRange/<E>/(List/<E>/ a, int from, int to, int compare(dyna mic /=E/ a, dynamic /=E/ b)) {

46 if ((from < 0) \|\| (to > a.length) \|\| (to < from)) {

47 throw "OutOfRange";

48 }

49 _doSort(a, from, to - 1, compare);

50 }

51

52 /**

53 * Sorts the list in the interval [:left:] to [:right:] (both inclusive).

54 */

55 static void _doSort/<E>/(List/<E>/ a, int left, int right, int compare(dyn amic /=E/ a, dynamic /=E/ b)) {

56 if ((right - left) <= _INSERTION_SORT_THRESHOLD) {

57 _insertionSort(a, left, right, compare);

58 } else {

59 _dualPivotQuicksort(a, left, right, compare);

60 }

61 }

62

63 static void _insertionSort/<E>/(List/<E>/ a, int left, int right, int comp are(dynamic /=E/ a, dynamic /=E/ b)) {

64 for (int i = left + 1; i <= right; i++) {

65 var el = a[i];

66 int j = i;

67 while ((j > left) && (compare(a[j - 1], el) > 0)) {

68 a[j] = a[j - 1];

69 j--;

70 }

71 a[j] = el;

72 }

73 }

74

75 static void _dualPivotQuicksort/<E>/(List/<E>/ a,

76 int left, int right,

77 int compare(dynamic /=E/ a, dynamic /=E/ b )) {

78 assert(right - left > _INSERTION_SORT_THRESHOLD);

79

80 // Compute the two pivots by looking at 5 elements.

81 int sixth = (right - left + 1) ~/ 6;

82 int index1 = left + sixth;

83 int index5 = right - sixth;

84 int index3 = (left + right) ~/ 2; // The midpoint.

85 int index2 = index3 - sixth;

86 int index4 = index3 + sixth;

87

88 var el1 = a[index1];

89 var el2 = a[index2];

90 var el3 = a[index3];

91 var el4 = a[index4];

92 var el5 = a[index5];

93

94 // Sort the selected 5 elements using a sorting network.

95 if (compare(el1, el2) > 0) { var t = el1; el1 = el2; el2 = t; }

96 if (compare(el4, el5) > 0) { var t = el4; el4 = el5; el5 = t; }

97 if (compare(el1, el3) > 0) { var t = el1; el1 = el3; el3 = t; }

98 if (compare(el2, el3) > 0) { var t = el2; el2 = el3; el3 = t; }

99 if (compare(el1, el4) > 0) { var t = el1; el1 = el4; el4 = t; }

100 if (compare(el3, el4) > 0) { var t = el3; el3 = el4; el4 = t; }

101 if (compare(el2, el5) > 0) { var t = el2; el2 = el5; el5 = t; }

102 if (compare(el2, el3) > 0) { var t = el2; el2 = el3; el3 = t; }

103 if (compare(el4, el5) > 0) { var t = el4; el4 = el5; el5 = t; }

104

105 var pivot1 = el2;

106 var pivot2 = el4;

107

108 // el2 and el4 have been saved in the pivot variables. They will be written

109 // back, once the partioning is finished.

110 a[index1] = el1;

111 a[index3] = el3;

112 a[index5] = el5;

113

114 a[index2] = a[left];

115 a[index4] = a[right];

116

117 int less = left + 1; // First element in the middle partition.

118 int great = right - 1; // Last element in the middle partition.

119

120 bool pivots_are_equal = (compare(pivot1, pivot2) == 0);

121 if (pivots_are_equal) {

122 var pivot = pivot1;

123 // Degenerated case where the partioning becomes a dutch national flag

124 // problem.

125 //

126 // [ \| < pivot \| == pivot \| unpartitioned \| > pivot \| ]

127 // ^ ^ ^ ^ ^

128 // left less k great right

129 //

130 // a[left] and a[right] are undefined and are filled after the

131 // partitioning.

132 //

133 // Invariants:

134 // 1) for x in ]left, less[ : x < pivot.

135 // 2) for x in [less, k[ : x == pivot.

136 // 3) for x in ]great, right[ : x > pivot.

137 for (int k = less; k <= great; k++) {

138 var ak = a[k];

139 int comp = compare(ak, pivot);

140 if (comp == 0) continue;

141 if (comp < 0) {

142 if (k != less) {

143 a[k] = a[less];

144 a[less] = ak;

145 }

146 less++;

147 } else {

148 // comp > 0.

149 //

150 // Find the first element <= pivot in the range [k - 1, great] and

151 // put [:ak:] there. We know that such an element must exist:

152 // When k == less, then el3 (which is equal to pivot) lies in the

153 // interval. Otherwise a[k - 1] == pivot and the search stops at k-1.

154 // Note that in the latter case invariant 2 will be violated for a

155 // short amount of time. The invariant will be restored when the

156 // pivots are put into their final positions.

157 while (true) {

158 comp = compare(a[great], pivot);

159 if (comp > 0) {

160 great--;

161 // This is the only location in the while-loop where a new

162 // iteration is started.

163 continue;

164 } else if (comp < 0) {

165 // Triple exchange.

166 a[k] = a[less];

167 a[less++] = a[great];

168 a[great--] = ak;

169 break;

170 } else {

171 // comp == 0;

172 a[k] = a[great];

173 a[great--] = ak;

174 // Note: if great < k then we will exit the outer loop and fix

175 // invariant 2 (which we just violated).

176 break;

177 }

178 }

179 }

180 }

181 } else {

182 // We partition the list into three parts:

183 // 1. < pivot1

184 // 2. >= pivot1 && <= pivot2

185 // 3. > pivot2

186 //

187 // During the loop we have:

188 // [ \| < pivot1 \| >= pivot1 && <= pivot2 \| unpartitioned \| > pivot2 \| ]

189 // ^ ^ ^ ^ ^

190 // left less k great right

191 //

192 // a[left] and a[right] are undefined and are filled after the

193 // partitioning.

194 //

195 // Invariants:

196 // 1. for x in ]left, less[ : x < pivot1

197 // 2. for x in [less, k[ : pivot1 <= x && x <= pivot2

198 // 3. for x in ]great, right[ : x > pivot2

199 for (int k = less; k <= great; k++) {

200 var ak = a[k];

201 int comp_pivot1 = compare(ak, pivot1);

202 if (comp_pivot1 < 0) {

203 if (k != less) {

204 a[k] = a[less];

205 a[less] = ak;

206 }

207 less++;

208 } else {

209 int comp_pivot2 = compare(ak, pivot2);

210 if (comp_pivot2 > 0) {

211 while (true) {

212 int comp = compare(a[great], pivot2);

213 if (comp > 0) {

214 great--;

215 if (great < k) break;

216 // This is the only location inside the loop where a new

217 // iteration is started.

218 continue;

219 } else {

220 // a[great] <= pivot2.

221 comp = compare(a[great], pivot1);

222 if (comp < 0) {

223 // Triple exchange.

224 a[k] = a[less];

225 a[less++] = a[great];

226 a[great--] = ak;

227 } else {

228 // a[great] >= pivot1.

229 a[k] = a[great];

230 a[great--] = ak;

231 }

232 break;

233 }

234 }

235 }

236 }

237 }

238 }

239

240 // Move pivots into their final positions.

241 // We shrunk the list from both sides (a[left] and a[right] have

242 // meaningless values in them) and now we move elements from the first

243 // and third partition into these locations so that we can store the

244 // pivots.

245 a[left] = a[less - 1];

246 a[less - 1] = pivot1;

247 a[right] = a[great + 1];

248 a[great + 1] = pivot2;

249

250 // The list is now partitioned into three partitions:

251 // [ < pivot1 \| >= pivot1 && <= pivot2 \| > pivot2 ]

252 // ^ ^ ^ ^

253 // left less great right

254

255 // Recursive descent. (Don't include the pivot values.)

256 _doSort(a, left, less - 2, compare);

257 _doSort(a, great + 2, right, compare);

258

259 if (pivots_are_equal) {

260 // All elements in the second partition are equal to the pivot. No

261 // need to sort them.

262 return;

263 }

264

265 // In theory it should be enough to call _doSort recursively on the second

266 // partition.

267 // The Android source however removes the pivot elements from the recursive

268 // call if the second partition is too large (more than 2/3 of the list).

269 if (less < index1 && great > index5) {

270 while (compare(a[less], pivot1) == 0) { less++; }

271 while (compare(a[great], pivot2) == 0) { great--; }

272

273 // Copy paste of the previous 3-way partitioning with adaptions.

274 //

275 // We partition the list into three parts:

276 // 1. == pivot1

277 // 2. > pivot1 && < pivot2

278 // 3. == pivot2

279 //

280 // During the loop we have:

281 // [ == pivot1 \| > pivot1 && < pivot2 \| unpartitioned \| == pivot2 ]

282 // ^ ^ ^

283 // less k great

284 //

285 // Invariants:

286 // 1. for x in [ *, less[ : x == pivot1

287 // 2. for x in [less, k[ : pivot1 < x && x < pivot2

288 // 3. for x in ]great, * ] : x == pivot2

289 for (int k = less; k <= great; k++) {

290 var ak = a[k];

291 int comp_pivot1 = compare(ak, pivot1);

292 if (comp_pivot1 == 0) {

293 if (k != less) {

294 a[k] = a[less];

295 a[less] = ak;

296 }

297 less++;

298 } else {

299 int comp_pivot2 = compare(ak, pivot2);

300 if (comp_pivot2 == 0) {

301 while (true) {

302 int comp = compare(a[great], pivot2);

303 if (comp == 0) {

304 great--;

305 if (great < k) break;

306 // This is the only location inside the loop where a new

307 // iteration is started.

308 continue;

309 } else {

310 // a[great] < pivot2.

311 comp = compare(a[great], pivot1);

312 if (comp < 0) {

313 // Triple exchange.

314 a[k] = a[less];

315 a[less++] = a[great];

316 a[great--] = ak;

317 } else {

318 // a[great] == pivot1.

319 a[k] = a[great];

320 a[great--] = ak;

321 }

322 break;

323 }

324 }

325 }

326 }

327 }

328 // The second partition has now been cleared of pivot elements and looks

329 // as follows:

330 // [ * \| > pivot1 && < pivot2 \| * ]

331 // ^ ^

332 // less great

333 // Sort the second partition using recursive descent.

334 _doSort(a, less, great, compare);

335 } else {

336 // The second partition looks as follows:

337 // [ * \| >= pivot1 && <= pivot2 \| * ]

338 // ^ ^

339 // less great

340 // Simply sort it by recursive descent.

341 _doSort(a, less, great, compare);

342 }

343 }

344 }

OLD	NEW