| OLD | NEW |
| 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 Loading... |
| 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 }); |
| OLD | NEW |