Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(183)

Issues Search
    My Issues | Starred     Open | Closed | All

Side by Side Diff: test/codegen/expect/collection/algorithms.js

Issue 1642903004: Regen tests (Closed) Base URL: https://github.com/dart-lang/dev_compiler.git@master
Patch Set: Created 4 years, 10 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:
View unified diff | Download patch
« no previous file with comments | « no previous file | test/codegen/expect/collection/algorithms.txt » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(Empty)
1 dart_library.library('collection/algorithms', null, /* Imports */[
2 'dart/_runtime',
3 'dart/core',
4 'dart/math'
5 ], /* Lazy imports */[
6 ], function(exports, dart, core, math) {
7 'use strict';
8 let dartx = dart.dartx;
9 function _comparableBinarySearch(list, key) {
10 let min = 0;
11 let max = list[dartx.length];
12 while (min < dart.notNull(max)) {
13 let mid = min + (dart.notNull(max) - min >> 1);
14 let element = list[dartx.get](mid);
15 let comp = element[dartx.compareTo](key);
16 if (comp == 0) return mid;
17 if (dart.notNull(comp) < 0) {
18 min = mid + 1;
19 } else {
20 max = mid;
21 }
22 }
23 return -1;
24 }
25 dart.fn(_comparableBinarySearch, core.int, [core.List$(core.Comparable), core. Comparable]);
26 function binarySearch(sortedList, key, opts) {
27 let compare = opts && 'compare' in opts ? opts.compare : null;
28 if (compare == null) {
29 return _comparableBinarySearch(dart.as(sortedList, core.List$(core.Compara ble)), dart.as(key, core.Comparable));
30 }
31 let min = 0;
32 let max = sortedList[dartx.length];
33 while (min < dart.notNull(max)) {
34 let mid = min + (dart.notNull(max) - min >> 1);
35 let element = sortedList[dartx.get](mid);
36 let comp = dart.dcall(compare, element, key);
37 if (comp == 0) return mid;
38 if (dart.notNull(comp) < 0) {
39 min = mid + 1;
40 } else {
41 max = mid;
42 }
43 }
44 return -1;
45 }
46 dart.fn(binarySearch, core.int, [core.List, dart.dynamic], {compare: dart.func tionType(core.int, [dart.dynamic, dart.dynamic])});
47 function shuffle(list, start, end) {
48 if (start === void 0) start = 0;
49 if (end === void 0) end = null;
50 let random = math.Random.new();
51 if (end == null) end = list[dartx.length];
52 let length = dart.notNull(end) - dart.notNull(start);
53 while (length > 1) {
54 let pos = random.nextInt(length);
55 length--;
56 let tmp1 = list[dartx.get](dart.notNull(start) + dart.notNull(pos));
57 list[dartx.set](dart.notNull(start) + dart.notNull(pos), list[dartx.get](d art.notNull(start) + length));
58 list[dartx.set](dart.notNull(start) + length, tmp1);
59 }
60 }
61 dart.fn(shuffle, dart.void, [core.List], [core.int, core.int]);
62 function reverse(list, start, end) {
63 if (start === void 0) start = 0;
64 if (end === void 0) end = null;
65 if (end == null) end = list[dartx.length];
66 _reverse(list, start, end);
67 }
68 dart.fn(reverse, dart.void, [core.List], [core.int, core.int]);
69 function _reverse(list, start, end) {
70 for (let i = start, j = dart.notNull(end) - 1; dart.notNull(i) < j; i = dart .notNull(i) + 1, j--) {
71 let tmp = list[dartx.get](i);
72 list[dartx.set](i, list[dartx.get](j));
73 list[dartx.set](j, tmp);
74 }
75 }
76 dart.fn(_reverse, dart.void, [core.List, core.int, core.int]);
77 function insertionSort(list, opts) {
78 let compare = opts && 'compare' in opts ? opts.compare : null;
79 let start = opts && 'start' in opts ? opts.start : 0;
80 let end = opts && 'end' in opts ? opts.end : null;
81 if (end == null) end = list[dartx.length];
82 if (compare == null) compare = core.Comparable.compare;
83 _insertionSort(list, compare, start, end, dart.notNull(start) + 1);
84 }
85 dart.fn(insertionSort, dart.void, [core.List], {compare: dart.functionType(cor e.int, [dart.dynamic, dart.dynamic]), start: core.int, end: core.int});
86 function _insertionSort(list, compare, start, end, sortedUntil) {
87 for (let pos = sortedUntil; dart.notNull(pos) < dart.notNull(end); pos = dar t.notNull(pos) + 1) {
88 let min = start;
89 let max = pos;
90 let element = list[dartx.get](pos);
91 while (dart.notNull(min) < dart.notNull(max)) {
92 let mid = dart.notNull(min) + (dart.notNull(max) - dart.notNull(min) >> 1);
93 let comparison = dart.dcall(compare, element, list[dartx.get](mid));
94 if (dart.notNull(comparison) < 0) {
95 max = mid;
96 } else {
97 min = mid + 1;
98 }
99 }
100 list[dartx.setRange](dart.notNull(min) + 1, dart.notNull(pos) + 1, list, m in);
101 list[dartx.set](min, element);
102 }
103 }
104 dart.fn(_insertionSort, dart.void, [core.List, dart.functionType(core.int, [da rt.dynamic, dart.dynamic]), core.int, core.int, core.int]);
105 const _MERGE_SORT_LIMIT = 32;
106 function mergeSort(list, opts) {
107 let start = opts && 'start' in opts ? opts.start : 0;
108 let end = opts && 'end' in opts ? opts.end : null;
109 let compare = opts && 'compare' in opts ? opts.compare : null;
110 if (end == null) end = list[dartx.length];
111 if (compare == null) compare = core.Comparable.compare;
112 let length = dart.notNull(end) - dart.notNull(start);
113 if (length < 2) return;
114 if (length < dart.notNull(_MERGE_SORT_LIMIT)) {
115 _insertionSort(list, compare, start, end, dart.notNull(start) + 1);
116 return;
117 }
118 let middle = dart.notNull(start) + (dart.notNull(end) - dart.notNull(start) >> 1);
119 let firstLength = middle - dart.notNull(start);
120 let secondLength = dart.notNull(end) - middle;
121 let scratchSpace = core.List.new(secondLength);
122 _mergeSort(list, compare, middle, end, scratchSpace, 0);
123 let firstTarget = dart.notNull(end) - firstLength;
124 _mergeSort(list, compare, start, middle, list, firstTarget);
125 _merge(compare, list, firstTarget, end, scratchSpace, 0, secondLength, list, start);
126 }
127 dart.fn(mergeSort, dart.void, [core.List], {start: core.int, end: core.int, co mpare: dart.functionType(core.int, [dart.dynamic, dart.dynamic])});
128 function _movingInsertionSort(list, compare, start, end, target, targetOffset) {
129 let length = dart.notNull(end) - dart.notNull(start);
130 if (length == 0) return;
131 target[dartx.set](targetOffset, list[dartx.get](start));
132 for (let i = 1; i < length; i++) {
133 let element = list[dartx.get](dart.notNull(start) + i);
134 let min = targetOffset;
135 let max = dart.notNull(targetOffset) + i;
136 while (dart.notNull(min) < max) {
137 let mid = dart.notNull(min) + (max - dart.notNull(min) >> 1);
138 if (dart.notNull(dart.dcall(compare, element, target[dartx.get](mid))) < 0) {
139 max = mid;
140 } else {
141 min = mid + 1;
142 }
143 }
144 target[dartx.setRange](dart.notNull(min) + 1, dart.notNull(targetOffset) + i + 1, target, min);
145 target[dartx.set](min, element);
146 }
147 }
148 dart.fn(_movingInsertionSort, dart.void, [core.List, dart.functionType(core.in t, [dart.dynamic, dart.dynamic]), core.int, core.int, core.List, core.int]);
149 function _mergeSort(list, compare, start, end, target, targetOffset) {
150 let length = dart.notNull(end) - dart.notNull(start);
151 if (length < dart.notNull(_MERGE_SORT_LIMIT)) {
152 _movingInsertionSort(list, compare, start, end, target, targetOffset);
153 return;
154 }
155 let middle = dart.notNull(start) + (length >> 1);
156 let firstLength = middle - dart.notNull(start);
157 let secondLength = dart.notNull(end) - middle;
158 let targetMiddle = dart.notNull(targetOffset) + firstLength;
159 _mergeSort(list, compare, middle, end, target, targetMiddle);
160 _mergeSort(list, compare, start, middle, list, middle);
161 _merge(compare, list, middle, middle + firstLength, target, targetMiddle, ta rgetMiddle + secondLength, target, targetOffset);
162 }
163 dart.fn(_mergeSort, dart.void, [core.List, dart.functionType(core.int, [dart.d ynamic, dart.dynamic]), core.int, core.int, core.List, core.int]);
164 function _merge(compare, firstList, firstStart, firstEnd, secondList, secondSt art, secondEnd, target, targetOffset) {
165 dart.assert(dart.notNull(firstStart) < dart.notNull(firstEnd));
166 dart.assert(dart.notNull(secondStart) < dart.notNull(secondEnd));
167 let cursor1 = firstStart;
168 let cursor2 = secondStart;
169 let firstElement = firstList[dartx.get]((() => {
170 let x = cursor1;
171 cursor1 = dart.notNull(x) + 1;
172 return x;
173 })());
174 let secondElement = secondList[dartx.get]((() => {
175 let x = cursor2;
176 cursor2 = dart.notNull(x) + 1;
177 return x;
178 })());
179 while (true) {
180 if (dart.notNull(dart.dcall(compare, firstElement, secondElement)) <= 0) {
181 target[dartx.set]((() => {
182 let x = targetOffset;
183 targetOffset = dart.notNull(x) + 1;
184 return x;
185 })(), firstElement);
186 if (cursor1 == firstEnd) break;
187 firstElement = firstList[dartx.get]((() => {
188 let x = cursor1;
189 cursor1 = dart.notNull(x) + 1;
190 return x;
191 })());
192 } else {
193 target[dartx.set]((() => {
194 let x = targetOffset;
195 targetOffset = dart.notNull(x) + 1;
196 return x;
197 })(), secondElement);
198 if (cursor2 != secondEnd) {
199 secondElement = secondList[dartx.get]((() => {
200 let x = cursor2;
201 cursor2 = dart.notNull(x) + 1;
202 return x;
203 })());
204 continue;
205 }
206 target[dartx.set]((() => {
207 let x = targetOffset;
208 targetOffset = dart.notNull(x) + 1;
209 return x;
210 })(), firstElement);
211 target[dartx.setRange](targetOffset, dart.notNull(targetOffset) + (dart. notNull(firstEnd) - dart.notNull(cursor1)), firstList, cursor1);
212 return;
213 }
214 }
215 target[dartx.set]((() => {
216 let x = targetOffset;
217 targetOffset = dart.notNull(x) + 1;
218 return x;
219 })(), secondElement);
220 target[dartx.setRange](targetOffset, dart.notNull(targetOffset) + (dart.notN ull(secondEnd) - dart.notNull(cursor2)), secondList, cursor2);
221 }
222 dart.fn(_merge, dart.void, [dart.functionType(core.int, [dart.dynamic, dart.dy namic]), core.List, core.int, core.int, core.List, core.int, core.int, core.List , core.int]);
223 // Exports:
224 exports.binarySearch = binarySearch;
225 exports.shuffle = shuffle;
226 exports.reverse = reverse;
227 exports.insertionSort = insertionSort;
228 exports.mergeSort = mergeSort;
229 });
OLDNEW
« no previous file with comments | « no previous file | test/codegen/expect/collection/algorithms.txt » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698