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) return mid; |
17 return mid; | |
18 if (dart.notNull(comp) < 0) { | 17 if (dart.notNull(comp) < 0) { |
19 min = dart.notNull(mid) + 1; | 18 min = dart.notNull(mid) + 1; |
20 } else { | 19 } else { |
21 max = mid; | 20 max = mid; |
22 } | 21 } |
23 } | 22 } |
24 return -1; | 23 return -1; |
25 } | 24 } |
26 dart.fn(_comparableBinarySearch, core.int, [core.List$(core.Comparable), core.
Comparable]); | 25 dart.fn(_comparableBinarySearch, core.int, [core.List$(core.Comparable), core.
Comparable]); |
27 function binarySearch(sortedList, key, opts) { | 26 function binarySearch(sortedList, key, opts) { |
28 let compare = opts && 'compare' in opts ? opts.compare : null; | 27 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) return mid; |
39 return mid; | |
40 if (dart.notNull(comp) < 0) { | 38 if (dart.notNull(comp) < 0) { |
41 min = dart.notNull(mid) + 1; | 39 min = dart.notNull(mid) + 1; |
42 } else { | 40 } else { |
43 max = mid; | 41 max = mid; |
44 } | 42 } |
45 } | 43 } |
46 return -1; | 44 return -1; |
47 } | 45 } |
48 dart.fn(binarySearch, core.int, [core.List, dart.dynamic], {compare: dart.func
tionType(core.int, [dart.dynamic, dart.dynamic])}); | 46 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) { | 47 function shuffle(list, start, end) { |
50 if (start === void 0) | 48 if (start === void 0) start = 0; |
51 start = 0; | 49 if (end === void 0) end = null; |
52 if (end === void 0) | |
53 end = null; | |
54 let random = math.Random.new(); | 50 let random = math.Random.new(); |
55 if (end == null) | 51 if (end == null) end = list[dartx.length]; |
56 end = list[dartx.length]; | |
57 let length = dart.notNull(end) - dart.notNull(start); | 52 let length = dart.notNull(end) - dart.notNull(start); |
58 while (dart.notNull(length) > 1) { | 53 while (dart.notNull(length) > 1) { |
59 let pos = random.nextInt(length); | 54 let pos = random.nextInt(length); |
60 length = dart.notNull(length) - 1; | 55 length = dart.notNull(length) - 1; |
61 let tmp1 = list[dartx.get](dart.notNull(start) + dart.notNull(pos)); | 56 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))); | 57 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); | 58 list[dartx.set](dart.notNull(start) + dart.notNull(length), tmp1); |
64 } | 59 } |
65 } | 60 } |
66 dart.fn(shuffle, dart.void, [core.List], [core.int, core.int]); | 61 dart.fn(shuffle, dart.void, [core.List], [core.int, core.int]); |
67 function reverse(list, start, end) { | 62 function reverse(list, start, end) { |
68 if (start === void 0) | 63 if (start === void 0) start = 0; |
69 start = 0; | 64 if (end === void 0) end = null; |
70 if (end === void 0) | 65 if (end == null) end = list[dartx.length]; |
71 end = null; | |
72 if (end == null) | |
73 end = list[dartx.length]; | |
74 _reverse(list, start, end); | 66 _reverse(list, start, end); |
75 } | 67 } |
76 dart.fn(reverse, dart.void, [core.List], [core.int, core.int]); | 68 dart.fn(reverse, dart.void, [core.List], [core.int, core.int]); |
77 function _reverse(list, start, end) { | 69 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) { | 70 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); | 71 let tmp = list[dartx.get](i); |
80 list[dartx.set](i, list[dartx.get](j)); | 72 list[dartx.set](i, list[dartx.get](j)); |
81 list[dartx.set](j, tmp); | 73 list[dartx.set](j, tmp); |
82 } | 74 } |
83 } | 75 } |
84 dart.fn(_reverse, dart.void, [core.List, core.int, core.int]); | 76 dart.fn(_reverse, dart.void, [core.List, core.int, core.int]); |
85 function insertionSort(list, opts) { | 77 function insertionSort(list, opts) { |
86 let compare = opts && 'compare' in opts ? opts.compare : null; | 78 let compare = opts && 'compare' in opts ? opts.compare : null; |
87 let start = opts && 'start' in opts ? opts.start : 0; | 79 let start = opts && 'start' in opts ? opts.start : 0; |
88 let end = opts && 'end' in opts ? opts.end : null; | 80 let end = opts && 'end' in opts ? opts.end : null; |
89 if (end == null) | 81 if (end == null) end = list[dartx.length]; |
90 end = list[dartx.length]; | 82 if (compare == null) compare = core.Comparable.compare; |
91 if (compare == null) | |
92 compare = core.Comparable.compare; | |
93 _insertionSort(list, compare, start, end, dart.notNull(start) + 1); | 83 _insertionSort(list, compare, start, end, dart.notNull(start) + 1); |
94 } | 84 } |
95 dart.fn(insertionSort, dart.void, [core.List], {compare: dart.functionType(cor
e.int, [dart.dynamic, dart.dynamic]), start: core.int, end: core.int}); | 85 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) { | 86 function _insertionSort(list, compare, start, end, sortedUntil) { |
97 for (let pos = sortedUntil; dart.notNull(pos) < dart.notNull(end); pos = dar
t.notNull(pos) + 1) { | 87 for (let pos = sortedUntil; dart.notNull(pos) < dart.notNull(end); pos = dar
t.notNull(pos) + 1) { |
98 let min = start; | 88 let min = start; |
99 let max = pos; | 89 let max = pos; |
100 let element = list[dartx.get](pos); | 90 let element = list[dartx.get](pos); |
101 while (dart.notNull(min) < dart.notNull(max)) { | 91 while (dart.notNull(min) < dart.notNull(max)) { |
102 let mid = dart.notNull(min) + (dart.notNull(max) - dart.notNull(min) >>
1); | 92 let mid = dart.notNull(min) + (dart.notNull(max) - dart.notNull(min) >>
1); |
103 let comparison = dart.dcall(compare, element, list[dartx.get](mid)); | 93 let comparison = dart.dcall(compare, element, list[dartx.get](mid)); |
104 if (dart.notNull(comparison) < 0) { | 94 if (dart.notNull(comparison) < 0) { |
105 max = mid; | 95 max = mid; |
106 } else { | 96 } else { |
107 min = dart.notNull(mid) + 1; | 97 min = dart.notNull(mid) + 1; |
108 } | 98 } |
109 } | 99 } |
110 list[dartx.setRange](dart.notNull(min) + 1, dart.notNull(pos) + 1, list, m
in); | 100 list[dartx.setRange](dart.notNull(min) + 1, dart.notNull(pos) + 1, list, m
in); |
111 list[dartx.set](min, element); | 101 list[dartx.set](min, element); |
112 } | 102 } |
113 } | 103 } |
114 dart.fn(_insertionSort, dart.void, [core.List, dart.functionType(core.int, [da
rt.dynamic, dart.dynamic]), core.int, core.int, core.int]); | 104 dart.fn(_insertionSort, dart.void, [core.List, dart.functionType(core.int, [da
rt.dynamic, dart.dynamic]), core.int, core.int, core.int]); |
115 const _MERGE_SORT_LIMIT = 32; | 105 const _MERGE_SORT_LIMIT = 32; |
116 function mergeSort(list, opts) { | 106 function mergeSort(list, opts) { |
117 let start = opts && 'start' in opts ? opts.start : 0; | 107 let start = opts && 'start' in opts ? opts.start : 0; |
118 let end = opts && 'end' in opts ? opts.end : null; | 108 let end = opts && 'end' in opts ? opts.end : null; |
119 let compare = opts && 'compare' in opts ? opts.compare : null; | 109 let compare = opts && 'compare' in opts ? opts.compare : null; |
120 if (end == null) | 110 if (end == null) end = list[dartx.length]; |
121 end = list[dartx.length]; | 111 if (compare == null) compare = core.Comparable.compare; |
122 if (compare == null) | |
123 compare = core.Comparable.compare; | |
124 let length = dart.notNull(end) - dart.notNull(start); | 112 let length = dart.notNull(end) - dart.notNull(start); |
125 if (dart.notNull(length) < 2) | 113 if (dart.notNull(length) < 2) return; |
126 return; | |
127 if (dart.notNull(length) < dart.notNull(_MERGE_SORT_LIMIT)) { | 114 if (dart.notNull(length) < dart.notNull(_MERGE_SORT_LIMIT)) { |
128 _insertionSort(list, compare, start, end, dart.notNull(start) + 1); | 115 _insertionSort(list, compare, start, end, dart.notNull(start) + 1); |
129 return; | 116 return; |
130 } | 117 } |
131 let middle = dart.notNull(start) + (dart.notNull(end) - dart.notNull(start)
>> 1); | 118 let middle = dart.notNull(start) + (dart.notNull(end) - dart.notNull(start)
>> 1); |
132 let firstLength = dart.notNull(middle) - dart.notNull(start); | 119 let firstLength = dart.notNull(middle) - dart.notNull(start); |
133 let secondLength = dart.notNull(end) - dart.notNull(middle); | 120 let secondLength = dart.notNull(end) - dart.notNull(middle); |
134 let scratchSpace = core.List.new(secondLength); | 121 let scratchSpace = core.List.new(secondLength); |
135 _mergeSort(list, compare, middle, end, scratchSpace, 0); | 122 _mergeSort(list, compare, middle, end, scratchSpace, 0); |
136 let firstTarget = dart.notNull(end) - dart.notNull(firstLength); | 123 let firstTarget = dart.notNull(end) - dart.notNull(firstLength); |
137 _mergeSort(list, compare, start, middle, list, firstTarget); | 124 _mergeSort(list, compare, start, middle, list, firstTarget); |
138 _merge(compare, list, firstTarget, end, scratchSpace, 0, secondLength, list,
start); | 125 _merge(compare, list, firstTarget, end, scratchSpace, 0, secondLength, list,
start); |
139 } | 126 } |
140 dart.fn(mergeSort, dart.void, [core.List], {start: core.int, end: core.int, co
mpare: dart.functionType(core.int, [dart.dynamic, dart.dynamic])}); | 127 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)
{ | 128 function _movingInsertionSort(list, compare, start, end, target, targetOffset)
{ |
142 let length = dart.notNull(end) - dart.notNull(start); | 129 let length = dart.notNull(end) - dart.notNull(start); |
143 if (length == 0) | 130 if (length == 0) return; |
144 return; | |
145 target[dartx.set](targetOffset, list[dartx.get](start)); | 131 target[dartx.set](targetOffset, list[dartx.get](start)); |
146 for (let i = 1; dart.notNull(i) < dart.notNull(length); i = dart.notNull(i)
+ 1) { | 132 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)); | 133 let element = list[dartx.get](dart.notNull(start) + dart.notNull(i)); |
148 let min = targetOffset; | 134 let min = targetOffset; |
149 let max = dart.notNull(targetOffset) + dart.notNull(i); | 135 let max = dart.notNull(targetOffset) + dart.notNull(i); |
150 while (dart.notNull(min) < dart.notNull(max)) { | 136 while (dart.notNull(min) < dart.notNull(max)) { |
151 let mid = dart.notNull(min) + (dart.notNull(max) - dart.notNull(min) >>
1); | 137 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) { | 138 if (dart.notNull(dart.dcall(compare, element, target[dartx.get](mid))) <
0) { |
153 max = mid; | 139 max = mid; |
154 } else { | 140 } else { |
(...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
190 cursor2 = dart.notNull(x) + 1; | 176 cursor2 = dart.notNull(x) + 1; |
191 return x; | 177 return x; |
192 })()); | 178 })()); |
193 while (true) { | 179 while (true) { |
194 if (dart.notNull(dart.dcall(compare, firstElement, secondElement)) <= 0) { | 180 if (dart.notNull(dart.dcall(compare, firstElement, secondElement)) <= 0) { |
195 target[dartx.set]((() => { | 181 target[dartx.set]((() => { |
196 let x = targetOffset; | 182 let x = targetOffset; |
197 targetOffset = dart.notNull(x) + 1; | 183 targetOffset = dart.notNull(x) + 1; |
198 return x; | 184 return x; |
199 })(), firstElement); | 185 })(), firstElement); |
200 if (cursor1 == firstEnd) | 186 if (cursor1 == firstEnd) break; |
201 break; | |
202 firstElement = firstList[dartx.get]((() => { | 187 firstElement = firstList[dartx.get]((() => { |
203 let x = cursor1; | 188 let x = cursor1; |
204 cursor1 = dart.notNull(x) + 1; | 189 cursor1 = dart.notNull(x) + 1; |
205 return x; | 190 return x; |
206 })()); | 191 })()); |
207 } else { | 192 } else { |
208 target[dartx.set]((() => { | 193 target[dartx.set]((() => { |
209 let x = targetOffset; | 194 let x = targetOffset; |
210 targetOffset = dart.notNull(x) + 1; | 195 targetOffset = dart.notNull(x) + 1; |
211 return x; | 196 return x; |
(...skipping 23 matching lines...) Expand all Loading... |
235 target[dartx.setRange](targetOffset, dart.notNull(targetOffset) + (dart.notN
ull(secondEnd) - dart.notNull(cursor2)), secondList, cursor2); | 220 target[dartx.setRange](targetOffset, dart.notNull(targetOffset) + (dart.notN
ull(secondEnd) - dart.notNull(cursor2)), secondList, cursor2); |
236 } | 221 } |
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]); | 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]); |
238 // Exports: | 223 // Exports: |
239 exports.binarySearch = binarySearch; | 224 exports.binarySearch = binarySearch; |
240 exports.shuffle = shuffle; | 225 exports.shuffle = shuffle; |
241 exports.reverse = reverse; | 226 exports.reverse = reverse; |
242 exports.insertionSort = insertionSort; | 227 exports.insertionSort = insertionSort; |
243 exports.mergeSort = mergeSort; | 228 exports.mergeSort = mergeSort; |
244 }); | 229 }); |
OLD | NEW |