| OLD | NEW |
| 1 dart_library.library('collection/algorithms', null, /* Imports */[ | 1 dart_library.library('collection/algorithms', null, /* Imports */[ |
| 2 "dart/_runtime", | 2 "dart/_runtime", |
| 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 = 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, {compare = null} = {}) { |
| 28 let compare = opts && 'compare' in opts ? opts.compare : null; | |
| 29 if (compare == null) { | 28 if (compare == null) { |
| 30 return _comparableBinarySearch(dart.as(sortedList, core.List$(core.Compara
ble)), dart.as(key, core.Comparable)); | 29 return _comparableBinarySearch(dart.as(sortedList, core.List$(core.Compara
ble)), dart.as(key, core.Comparable)); |
| 31 } | 30 } |
| 32 let min = 0; | 31 let min = 0; |
| 33 let max = sortedList[dartx.length]; | 32 let max = sortedList[dartx.length]; |
| 34 while (dart.notNull(min) < dart.notNull(max)) { | 33 while (dart.notNull(min) < dart.notNull(max)) { |
| 35 let mid = dart.notNull(min) + (dart.notNull(max) - dart.notNull(min) >> 1)
; | 34 let mid = dart.notNull(min) + (dart.notNull(max) - dart.notNull(min) >> 1)
; |
| 36 let element = sortedList[dartx.get](mid); | 35 let element = sortedList[dartx.get](mid); |
| 37 let comp = dart.dcall(compare, element, key); | 36 let comp = dart.dcall(compare, element, key); |
| 38 if (comp == 0) | 37 if (comp == 0) |
| (...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 75 } | 74 } |
| 76 dart.fn(reverse, dart.void, [core.List], [core.int, core.int]); | 75 dart.fn(reverse, dart.void, [core.List], [core.int, core.int]); |
| 77 function _reverse(list, start, end) { | 76 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) { | 77 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); | 78 let tmp = list[dartx.get](i); |
| 80 list[dartx.set](i, list[dartx.get](j)); | 79 list[dartx.set](i, list[dartx.get](j)); |
| 81 list[dartx.set](j, tmp); | 80 list[dartx.set](j, tmp); |
| 82 } | 81 } |
| 83 } | 82 } |
| 84 dart.fn(_reverse, dart.void, [core.List, core.int, core.int]); | 83 dart.fn(_reverse, dart.void, [core.List, core.int, core.int]); |
| 85 function insertionSort(list, opts) { | 84 function insertionSort(list, {compare = null, start = 0, end = null} = {}) { |
| 86 let compare = opts && 'compare' in opts ? opts.compare : null; | |
| 87 let start = opts && 'start' in opts ? opts.start : 0; | |
| 88 let end = opts && 'end' in opts ? opts.end : null; | |
| 89 if (end == null) | 85 if (end == null) |
| 90 end = list[dartx.length]; | 86 end = list[dartx.length]; |
| 91 if (compare == null) | 87 if (compare == null) |
| 92 compare = core.Comparable.compare; | 88 compare = core.Comparable.compare; |
| 93 _insertionSort(list, compare, start, end, dart.notNull(start) + 1); | 89 _insertionSort(list, compare, start, end, dart.notNull(start) + 1); |
| 94 } | 90 } |
| 95 dart.fn(insertionSort, dart.void, [core.List], {compare: dart.functionType(cor
e.int, [dart.dynamic, dart.dynamic]), start: core.int, end: core.int}); | 91 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) { | 92 function _insertionSort(list, compare, start, end, sortedUntil) { |
| 97 for (let pos = sortedUntil; dart.notNull(pos) < dart.notNull(end); pos = dar
t.notNull(pos) + 1) { | 93 for (let pos = sortedUntil; dart.notNull(pos) < dart.notNull(end); pos = dar
t.notNull(pos) + 1) { |
| 98 let min = start; | 94 let min = start; |
| 99 let max = pos; | 95 let max = pos; |
| 100 let element = list[dartx.get](pos); | 96 let element = list[dartx.get](pos); |
| 101 while (dart.notNull(min) < dart.notNull(max)) { | 97 while (dart.notNull(min) < dart.notNull(max)) { |
| 102 let mid = dart.notNull(min) + (dart.notNull(max) - dart.notNull(min) >>
1); | 98 let mid = dart.notNull(min) + (dart.notNull(max) - dart.notNull(min) >>
1); |
| 103 let comparison = dart.dcall(compare, element, list[dartx.get](mid)); | 99 let comparison = dart.dcall(compare, element, list[dartx.get](mid)); |
| 104 if (dart.notNull(comparison) < 0) { | 100 if (dart.notNull(comparison) < 0) { |
| 105 max = mid; | 101 max = mid; |
| 106 } else { | 102 } else { |
| 107 min = dart.notNull(mid) + 1; | 103 min = dart.notNull(mid) + 1; |
| 108 } | 104 } |
| 109 } | 105 } |
| 110 list[dartx.setRange](dart.notNull(min) + 1, dart.notNull(pos) + 1, list, m
in); | 106 list[dartx.setRange](dart.notNull(min) + 1, dart.notNull(pos) + 1, list, m
in); |
| 111 list[dartx.set](min, element); | 107 list[dartx.set](min, element); |
| 112 } | 108 } |
| 113 } | 109 } |
| 114 dart.fn(_insertionSort, dart.void, [core.List, dart.functionType(core.int, [da
rt.dynamic, dart.dynamic]), core.int, core.int, core.int]); | 110 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; | 111 let _MERGE_SORT_LIMIT = 32; |
| 116 function mergeSort(list, opts) { | 112 function mergeSort(list, {start = 0, end = null, compare = null} = {}) { |
| 117 let start = opts && 'start' in opts ? opts.start : 0; | |
| 118 let end = opts && 'end' in opts ? opts.end : null; | |
| 119 let compare = opts && 'compare' in opts ? opts.compare : null; | |
| 120 if (end == null) | 113 if (end == null) |
| 121 end = list[dartx.length]; | 114 end = list[dartx.length]; |
| 122 if (compare == null) | 115 if (compare == null) |
| 123 compare = core.Comparable.compare; | 116 compare = core.Comparable.compare; |
| 124 let length = dart.notNull(end) - dart.notNull(start); | 117 let length = dart.notNull(end) - dart.notNull(start); |
| 125 if (dart.notNull(length) < 2) | 118 if (dart.notNull(length) < 2) |
| 126 return; | 119 return; |
| 127 if (dart.notNull(length) < dart.notNull(_MERGE_SORT_LIMIT)) { | 120 if (dart.notNull(length) < dart.notNull(_MERGE_SORT_LIMIT)) { |
| 128 _insertionSort(list, compare, start, end, dart.notNull(start) + 1); | 121 _insertionSort(list, compare, start, end, dart.notNull(start) + 1); |
| 129 return; | 122 return; |
| (...skipping 105 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 235 target[dartx.setRange](targetOffset, dart.notNull(targetOffset) + (dart.notN
ull(secondEnd) - dart.notNull(cursor2)), secondList, cursor2); | 228 target[dartx.setRange](targetOffset, dart.notNull(targetOffset) + (dart.notN
ull(secondEnd) - dart.notNull(cursor2)), secondList, cursor2); |
| 236 } | 229 } |
| 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]); | 230 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: | 231 // Exports: |
| 239 exports.binarySearch = binarySearch; | 232 exports.binarySearch = binarySearch; |
| 240 exports.shuffle = shuffle; | 233 exports.shuffle = shuffle; |
| 241 exports.reverse = reverse; | 234 exports.reverse = reverse; |
| 242 exports.insertionSort = insertionSort; | 235 exports.insertionSort = insertionSort; |
| 243 exports.mergeSort = mergeSort; | 236 exports.mergeSort = mergeSort; |
| 244 }); | 237 }); |
| OLD | NEW |