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

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

Issue 1355893003: Rewire DDC to use the analyzer task model (Closed) Base URL: https://github.com/dart-lang/dev_compiler.git@master
Patch Set: Created 5 years, 3 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
OLDNEW
1 dart_library.library('collection/algorithms', null, /* Imports */[ 1 dart_library.library('collection/algorithms', null, /* Imports */[
2 "dart_runtime/dart", 2 "dart_runtime/dart",
3 'dart/core', 3 'dart/core',
4 'dart/math' 4 'dart/math'
5 ], /* Lazy imports */[ 5 ], /* Lazy imports */[
6 ], function(exports, dart, core, math) { 6 ], function(exports, dart, core, math) {
7 'use strict'; 7 'use strict';
8 let dartx = dart.dartx; 8 let dartx = dart.dartx;
9 function _comparableBinarySearch(list, key) { 9 function _comparableBinarySearch(list, key) {
10 let min = 0; 10 let min = 0;
11 let max = list[dartx.length]; 11 let max = list[dartx.length];
12 while (dart.notNull(min) < dart.notNull(max)) { 12 while (dart.notNull(min) < dart.notNull(max)) {
13 let mid = dart.notNull(min) + (dart.notNull(max) - dart.notNull(min) >> 1) ; 13 let mid = dart.notNull(min) + (dart.notNull(max) - dart.notNull(min) >> 1) ;
14 let element = list[dartx.get](mid); 14 let element = list[dartx.get](mid);
15 let comp = element[dartx.compareTo](key); 15 let comp = dart.dcall(element[dartx.compareTo], key);
16 if (comp == 0) 16 if (comp == 0)
17 return mid; 17 return mid;
18 if (dart.notNull(comp) < 0) { 18 if (dart.notNull(comp) < 0) {
19 min = dart.notNull(mid) + 1; 19 min = dart.notNull(mid) + 1;
20 } else { 20 } else {
21 max = mid; 21 max = mid;
22 } 22 }
23 } 23 }
24 return -1; 24 return -1;
25 } 25 }
26 dart.fn(_comparableBinarySearch, core.int, [core.List$(core.Comparable), core. Comparable]); 26 dart.fn(_comparableBinarySearch, core.int, [core.List$(core.Comparable), core. Comparable]);
27 function binarySearch(sortedList, key, opts) { 27 function binarySearch(sortedList, key, opts) {
28 let compare = opts && 'compare' in opts ? opts.compare : null; 28 let compare = opts && 'compare' in opts ? opts.compare : null;
29 if (compare == null) { 29 if (compare == null) {
30 return _comparableBinarySearch(dart.as(sortedList, core.List$(core.Compara ble)), dart.as(key, core.Comparable)); 30 return dart.dcall(_comparableBinarySearch, sortedList, key);
31 } 31 }
32 let min = 0; 32 let min = 0;
33 let max = sortedList[dartx.length]; 33 let max = sortedList[dartx.length];
34 while (dart.notNull(min) < dart.notNull(max)) { 34 while (dart.notNull(min) < dart.notNull(max)) {
35 let mid = dart.notNull(min) + (dart.notNull(max) - dart.notNull(min) >> 1) ; 35 let mid = dart.notNull(min) + (dart.notNull(max) - dart.notNull(min) >> 1) ;
36 let element = sortedList[dartx.get](mid); 36 let element = sortedList[dartx.get](mid);
37 let comp = dart.dcall(compare, element, key); 37 let comp = dart.dcall(compare, element, key);
38 if (comp == 0) 38 if (comp == 0)
39 return mid; 39 return mid;
40 if (dart.notNull(comp) < 0) { 40 if (dart.notNull(comp) < 0) {
41 min = dart.notNull(mid) + 1; 41 min = dart.notNull(mid) + 1;
42 } else { 42 } else {
43 max = mid; 43 max = mid;
44 } 44 }
45 } 45 }
46 return -1; 46 return -1;
47 } 47 }
48 dart.fn(binarySearch, core.int, [core.List, dart.dynamic], {compare: dart.func tionType(core.int, [dart.dynamic, dart.dynamic])}); 48 dart.fn(binarySearch, core.int, [core.List, dart.dynamic], {compare: dart.func tionType(core.int, [dart.dynamic, dart.dynamic])});
49 function shuffle(list, start, end) { 49 function shuffle(list, start, end) {
50 if (start === void 0) 50 if (start === void 0)
51 start = 0; 51 start = 0;
52 if (end === void 0) 52 if (end === void 0)
53 end = null; 53 end = null;
54 let random = math.Random.new(); 54 let random = math.Random.new();
55 if (end == null) 55 if (end == null)
56 end = list[dartx.length]; 56 end = list[dartx.length];
57 let length = dart.notNull(end) - dart.notNull(start); 57 let length = dart.notNull(end) - dart.notNull(start);
58 while (dart.notNull(length) > 1) { 58 while (dart.notNull(length) > 1) {
59 let pos = random.nextInt(length); 59 let pos = dart.dcall(random.nextInt, length);
60 length = dart.notNull(length) - 1; 60 length = dart.notNull(length) - 1;
61 let tmp1 = list[dartx.get](dart.notNull(start) + dart.notNull(pos)); 61 let tmp1 = list[dartx.get](dart.notNull(start) + dart.notNull(pos));
62 list[dartx.set](dart.notNull(start) + dart.notNull(pos), list[dartx.get](d art.notNull(start) + dart.notNull(length))); 62 list[dartx.set](dart.notNull(start) + dart.notNull(pos), list[dartx.get](d art.notNull(start) + dart.notNull(length)));
63 list[dartx.set](dart.notNull(start) + dart.notNull(length), tmp1); 63 list[dartx.set](dart.notNull(start) + dart.notNull(length), tmp1);
64 } 64 }
65 } 65 }
66 dart.fn(shuffle, dart.void, [core.List], [core.int, core.int]); 66 dart.fn(shuffle, dart.void, [core.List], [core.int, core.int]);
67 function reverse(list, start, end) { 67 function reverse(list, start, end) {
68 if (start === void 0) 68 if (start === void 0)
69 start = 0; 69 start = 0;
70 if (end === void 0) 70 if (end === void 0)
71 end = null; 71 end = null;
72 if (end == null) 72 if (end == null)
73 end = list[dartx.length]; 73 end = list[dartx.length];
74 _reverse(list, start, end); 74 dart.dcall(_reverse, list, start, end);
75 } 75 }
76 dart.fn(reverse, dart.void, [core.List], [core.int, core.int]); 76 dart.fn(reverse, dart.void, [core.List], [core.int, core.int]);
77 function _reverse(list, start, end) { 77 function _reverse(list, start, end) {
78 for (let i = start, j = dart.notNull(end) - 1; dart.notNull(i) < dart.notNul l(j); i = dart.notNull(i) + 1, j = dart.notNull(j) - 1) { 78 for (let i = start, j = dart.notNull(end) - 1; dart.notNull(i) < dart.notNul l(j); i = dart.notNull(i) + 1, j = dart.notNull(j) - 1) {
79 let tmp = list[dartx.get](i); 79 let tmp = list[dartx.get](i);
80 list[dartx.set](i, list[dartx.get](j)); 80 list[dartx.set](i, list[dartx.get](j));
81 list[dartx.set](j, tmp); 81 list[dartx.set](j, tmp);
82 } 82 }
83 } 83 }
84 dart.fn(_reverse, dart.void, [core.List, core.int, core.int]); 84 dart.fn(_reverse, dart.void, [core.List, core.int, core.int]);
85 function insertionSort(list, opts) { 85 function insertionSort(list, opts) {
86 let compare = opts && 'compare' in opts ? opts.compare : null; 86 let compare = opts && 'compare' in opts ? opts.compare : null;
87 let start = opts && 'start' in opts ? opts.start : 0; 87 let start = opts && 'start' in opts ? opts.start : 0;
88 let end = opts && 'end' in opts ? opts.end : null; 88 let end = opts && 'end' in opts ? opts.end : null;
89 if (end == null) 89 if (end == null)
90 end = list[dartx.length]; 90 end = list[dartx.length];
91 if (compare == null) 91 if (compare == null)
92 compare = core.Comparable.compare; 92 compare = core.Comparable.compare;
93 _insertionSort(list, compare, start, end, dart.notNull(start) + 1); 93 dart.dcall(_insertionSort, list, compare, start, end, dart.notNull(start) + 1);
94 } 94 }
95 dart.fn(insertionSort, dart.void, [core.List], {compare: dart.functionType(cor e.int, [dart.dynamic, dart.dynamic]), start: core.int, end: core.int}); 95 dart.fn(insertionSort, dart.void, [core.List], {compare: dart.functionType(cor e.int, [dart.dynamic, dart.dynamic]), start: core.int, end: core.int});
96 function _insertionSort(list, compare, start, end, sortedUntil) { 96 function _insertionSort(list, compare, start, end, sortedUntil) {
97 for (let pos = sortedUntil; dart.notNull(pos) < dart.notNull(end); pos = dar t.notNull(pos) + 1) { 97 for (let pos = sortedUntil; dart.notNull(pos) < dart.notNull(end); pos = dar t.notNull(pos) + 1) {
98 let min = start; 98 let min = start;
99 let max = pos; 99 let max = pos;
100 let element = list[dartx.get](pos); 100 let element = list[dartx.get](pos);
101 while (dart.notNull(min) < dart.notNull(max)) { 101 while (dart.notNull(min) < dart.notNull(max)) {
102 let mid = dart.notNull(min) + (dart.notNull(max) - dart.notNull(min) >> 1); 102 let mid = dart.notNull(min) + (dart.notNull(max) - dart.notNull(min) >> 1);
103 let comparison = dart.dcall(compare, element, list[dartx.get](mid)); 103 let comparison = dart.dcall(compare, element, list[dartx.get](mid));
104 if (dart.notNull(comparison) < 0) { 104 if (dart.notNull(comparison) < 0) {
105 max = mid; 105 max = mid;
106 } else { 106 } else {
107 min = dart.notNull(mid) + 1; 107 min = dart.notNull(mid) + 1;
108 } 108 }
109 } 109 }
110 list[dartx.setRange](dart.notNull(min) + 1, dart.notNull(pos) + 1, list, m in); 110 dart.dcall(list[dartx.setRange], dart.notNull(min) + 1, dart.notNull(pos) + 1, list, min);
111 list[dartx.set](min, element); 111 list[dartx.set](min, element);
112 } 112 }
113 } 113 }
114 dart.fn(_insertionSort, dart.void, [core.List, dart.functionType(core.int, [da rt.dynamic, dart.dynamic]), core.int, core.int, core.int]); 114 dart.fn(_insertionSort, dart.void, [core.List, dart.functionType(core.int, [da rt.dynamic, dart.dynamic]), core.int, core.int, core.int]);
115 let _MERGE_SORT_LIMIT = 32; 115 let _MERGE_SORT_LIMIT = 32;
116 function mergeSort(list, opts) { 116 function mergeSort(list, opts) {
117 let start = opts && 'start' in opts ? opts.start : 0; 117 let start = opts && 'start' in opts ? opts.start : 0;
118 let end = opts && 'end' in opts ? opts.end : null; 118 let end = opts && 'end' in opts ? opts.end : null;
119 let compare = opts && 'compare' in opts ? opts.compare : null; 119 let compare = opts && 'compare' in opts ? opts.compare : null;
120 if (end == null) 120 if (end == null)
121 end = list[dartx.length]; 121 end = list[dartx.length];
122 if (compare == null) 122 if (compare == null)
123 compare = core.Comparable.compare; 123 compare = core.Comparable.compare;
124 let length = dart.notNull(end) - dart.notNull(start); 124 let length = dart.notNull(end) - dart.notNull(start);
125 if (dart.notNull(length) < 2) 125 if (dart.notNull(length) < 2)
126 return; 126 return;
127 if (dart.notNull(length) < dart.notNull(_MERGE_SORT_LIMIT)) { 127 if (dart.notNull(length) < dart.notNull(_MERGE_SORT_LIMIT)) {
128 _insertionSort(list, compare, start, end, dart.notNull(start) + 1); 128 dart.dcall(_insertionSort, list, compare, start, end, dart.notNull(start) + 1);
129 return; 129 return;
130 } 130 }
131 let middle = dart.notNull(start) + (dart.notNull(end) - dart.notNull(start) >> 1); 131 let middle = dart.notNull(start) + (dart.notNull(end) - dart.notNull(start) >> 1);
132 let firstLength = dart.notNull(middle) - dart.notNull(start); 132 let firstLength = dart.notNull(middle) - dart.notNull(start);
133 let secondLength = dart.notNull(end) - dart.notNull(middle); 133 let secondLength = dart.notNull(end) - dart.notNull(middle);
134 let scratchSpace = core.List.new(secondLength); 134 let scratchSpace = core.List.new(secondLength);
135 _mergeSort(list, compare, middle, end, scratchSpace, 0); 135 dart.dcall(_mergeSort, list, compare, middle, end, scratchSpace, 0);
136 let firstTarget = dart.notNull(end) - dart.notNull(firstLength); 136 let firstTarget = dart.notNull(end) - dart.notNull(firstLength);
137 _mergeSort(list, compare, start, middle, list, firstTarget); 137 dart.dcall(_mergeSort, list, compare, start, middle, list, firstTarget);
138 _merge(compare, list, firstTarget, end, scratchSpace, 0, secondLength, list, start); 138 dart.dcall(_merge, compare, list, firstTarget, end, scratchSpace, 0, secondL ength, list, start);
139 } 139 }
140 dart.fn(mergeSort, dart.void, [core.List], {start: core.int, end: core.int, co mpare: dart.functionType(core.int, [dart.dynamic, dart.dynamic])}); 140 dart.fn(mergeSort, dart.void, [core.List], {start: core.int, end: core.int, co mpare: dart.functionType(core.int, [dart.dynamic, dart.dynamic])});
141 function _movingInsertionSort(list, compare, start, end, target, targetOffset) { 141 function _movingInsertionSort(list, compare, start, end, target, targetOffset) {
142 let length = dart.notNull(end) - dart.notNull(start); 142 let length = dart.notNull(end) - dart.notNull(start);
143 if (length == 0) 143 if (length == 0)
144 return; 144 return;
145 target[dartx.set](targetOffset, list[dartx.get](start)); 145 target[dartx.set](targetOffset, list[dartx.get](start));
146 for (let i = 1; dart.notNull(i) < dart.notNull(length); i = dart.notNull(i) + 1) { 146 for (let i = 1; dart.notNull(i) < dart.notNull(length); i = dart.notNull(i) + 1) {
147 let element = list[dartx.get](dart.notNull(start) + dart.notNull(i)); 147 let element = list[dartx.get](dart.notNull(start) + dart.notNull(i));
148 let min = targetOffset; 148 let min = targetOffset;
149 let max = dart.notNull(targetOffset) + dart.notNull(i); 149 let max = dart.notNull(targetOffset) + dart.notNull(i);
150 while (dart.notNull(min) < dart.notNull(max)) { 150 while (dart.notNull(min) < dart.notNull(max)) {
151 let mid = dart.notNull(min) + (dart.notNull(max) - dart.notNull(min) >> 1); 151 let mid = dart.notNull(min) + (dart.notNull(max) - dart.notNull(min) >> 1);
152 if (dart.notNull(dart.dcall(compare, element, target[dartx.get](mid))) < 0) { 152 if (dart.notNull(dart.dcall(compare, element, target[dartx.get](mid))) < 0) {
153 max = mid; 153 max = mid;
154 } else { 154 } else {
155 min = dart.notNull(mid) + 1; 155 min = dart.notNull(mid) + 1;
156 } 156 }
157 } 157 }
158 target[dartx.setRange](dart.notNull(min) + 1, dart.notNull(targetOffset) + dart.notNull(i) + 1, target, min); 158 dart.dcall(target[dartx.setRange], dart.notNull(min) + 1, dart.notNull(tar getOffset) + dart.notNull(i) + 1, target, min);
159 target[dartx.set](min, element); 159 target[dartx.set](min, element);
160 } 160 }
161 } 161 }
162 dart.fn(_movingInsertionSort, dart.void, [core.List, dart.functionType(core.in t, [dart.dynamic, dart.dynamic]), core.int, core.int, core.List, core.int]); 162 dart.fn(_movingInsertionSort, dart.void, [core.List, dart.functionType(core.in t, [dart.dynamic, dart.dynamic]), core.int, core.int, core.List, core.int]);
163 function _mergeSort(list, compare, start, end, target, targetOffset) { 163 function _mergeSort(list, compare, start, end, target, targetOffset) {
164 let length = dart.notNull(end) - dart.notNull(start); 164 let length = dart.notNull(end) - dart.notNull(start);
165 if (dart.notNull(length) < dart.notNull(_MERGE_SORT_LIMIT)) { 165 if (dart.notNull(length) < dart.notNull(_MERGE_SORT_LIMIT)) {
166 _movingInsertionSort(list, compare, start, end, target, targetOffset); 166 dart.dcall(_movingInsertionSort, list, compare, start, end, target, target Offset);
167 return; 167 return;
168 } 168 }
169 let middle = dart.notNull(start) + (dart.notNull(length) >> 1); 169 let middle = dart.notNull(start) + (dart.notNull(length) >> 1);
170 let firstLength = dart.notNull(middle) - dart.notNull(start); 170 let firstLength = dart.notNull(middle) - dart.notNull(start);
171 let secondLength = dart.notNull(end) - dart.notNull(middle); 171 let secondLength = dart.notNull(end) - dart.notNull(middle);
172 let targetMiddle = dart.notNull(targetOffset) + dart.notNull(firstLength); 172 let targetMiddle = dart.notNull(targetOffset) + dart.notNull(firstLength);
173 _mergeSort(list, compare, middle, end, target, targetMiddle); 173 dart.dcall(_mergeSort, list, compare, middle, end, target, targetMiddle);
174 _mergeSort(list, compare, start, middle, list, middle); 174 dart.dcall(_mergeSort, list, compare, start, middle, list, middle);
175 _merge(compare, list, middle, dart.notNull(middle) + dart.notNull(firstLengt h), target, targetMiddle, dart.notNull(targetMiddle) + dart.notNull(secondLength ), target, targetOffset); 175 dart.dcall(_merge, compare, list, middle, dart.notNull(middle) + dart.notNul l(firstLength), target, targetMiddle, dart.notNull(targetMiddle) + dart.notNull( secondLength), target, targetOffset);
176 } 176 }
177 dart.fn(_mergeSort, dart.void, [core.List, dart.functionType(core.int, [dart.d ynamic, dart.dynamic]), core.int, core.int, core.List, core.int]); 177 dart.fn(_mergeSort, dart.void, [core.List, dart.functionType(core.int, [dart.d ynamic, dart.dynamic]), core.int, core.int, core.List, core.int]);
178 function _merge(compare, firstList, firstStart, firstEnd, secondList, secondSt art, secondEnd, target, targetOffset) { 178 function _merge(compare, firstList, firstStart, firstEnd, secondList, secondSt art, secondEnd, target, targetOffset) {
179 dart.assert(dart.notNull(firstStart) < dart.notNull(firstEnd)); 179 dart.assert(dart.notNull(firstStart) < dart.notNull(firstEnd));
180 dart.assert(dart.notNull(secondStart) < dart.notNull(secondEnd)); 180 dart.assert(dart.notNull(secondStart) < dart.notNull(secondEnd));
181 let cursor1 = firstStart; 181 let cursor1 = firstStart;
182 let cursor2 = secondStart; 182 let cursor2 = secondStart;
183 let firstElement = firstList[dartx.get]((() => { 183 let firstElement = firstList[dartx.get]((() => {
184 let x = cursor1; 184 let x = cursor1;
185 cursor1 = dart.notNull(x) + 1; 185 cursor1 = dart.notNull(x) + 1;
(...skipping 30 matching lines...) Expand all
216 cursor2 = dart.notNull(x) + 1; 216 cursor2 = dart.notNull(x) + 1;
217 return x; 217 return x;
218 })()); 218 })());
219 continue; 219 continue;
220 } 220 }
221 target[dartx.set]((() => { 221 target[dartx.set]((() => {
222 let x = targetOffset; 222 let x = targetOffset;
223 targetOffset = dart.notNull(x) + 1; 223 targetOffset = dart.notNull(x) + 1;
224 return x; 224 return x;
225 })(), firstElement); 225 })(), firstElement);
226 target[dartx.setRange](targetOffset, dart.notNull(targetOffset) + (dart. notNull(firstEnd) - dart.notNull(cursor1)), firstList, cursor1); 226 dart.dcall(target[dartx.setRange], targetOffset, dart.notNull(targetOffs et) + (dart.notNull(firstEnd) - dart.notNull(cursor1)), firstList, cursor1);
227 return; 227 return;
228 } 228 }
229 } 229 }
230 target[dartx.set]((() => { 230 target[dartx.set]((() => {
231 let x = targetOffset; 231 let x = targetOffset;
232 targetOffset = dart.notNull(x) + 1; 232 targetOffset = dart.notNull(x) + 1;
233 return x; 233 return x;
234 })(), secondElement); 234 })(), secondElement);
235 target[dartx.setRange](targetOffset, dart.notNull(targetOffset) + (dart.notN ull(secondEnd) - dart.notNull(cursor2)), secondList, cursor2); 235 dart.dcall(target[dartx.setRange], targetOffset, dart.notNull(targetOffset) + (dart.notNull(secondEnd) - dart.notNull(cursor2)), secondList, cursor2);
236 } 236 }
237 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]); 237 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]);
238 // Exports: 238 // Exports:
239 exports.binarySearch = binarySearch; 239 exports.binarySearch = binarySearch;
240 exports.shuffle = shuffle; 240 exports.shuffle = shuffle;
241 exports.reverse = reverse; 241 exports.reverse = reverse;
242 exports.insertionSort = insertionSort; 242 exports.insertionSort = insertionSort;
243 exports.mergeSort = mergeSort; 243 exports.mergeSort = mergeSort;
244 }); 244 });
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698