| OLD | NEW |
| 1 dart_library.library('collection/priority_queue', null, /* Imports */[ | 1 dart_library.library('collection/priority_queue', null, /* Imports */[ |
| 2 "dart/_runtime", | 2 "dart/_runtime", |
| 3 'dart/core', | 3 'dart/core', |
| 4 'dart/collection' | 4 'dart/collection' |
| 5 ], /* Lazy imports */[ | 5 ], /* Lazy imports */[ |
| 6 ], function(exports, dart, core, collection) { | 6 ], function(exports, dart, core, collection) { |
| 7 'use strict'; | 7 'use strict'; |
| 8 let dartx = dart.dartx; | 8 let dartx = dart.dartx; |
| 9 const PriorityQueue$ = dart.generic(function(E) { | 9 const PriorityQueue$ = dart.generic(function(E) { |
| 10 class PriorityQueue extends core.Object {} | 10 class PriorityQueue extends core.Object {} |
| 11 return PriorityQueue; | 11 return PriorityQueue; |
| 12 }); | 12 }); |
| 13 let PriorityQueue = PriorityQueue$(); | 13 let PriorityQueue = PriorityQueue$(); |
| 14 const _queue = Symbol('_queue'); | 14 const _queue = Symbol('_queue'); |
| 15 const _length = Symbol('_length'); | 15 const _length = Symbol('_length'); |
| 16 const _add = Symbol('_add'); | 16 const _add = Symbol('_add'); |
| 17 const _locate = Symbol('_locate'); | 17 const _locate = Symbol('_locate'); |
| 18 const _removeLast = Symbol('_removeLast'); | 18 const _removeLast = Symbol('_removeLast'); |
| 19 const _bubbleUp = Symbol('_bubbleUp'); | 19 const _bubbleUp = Symbol('_bubbleUp'); |
| 20 const _bubbleDown = Symbol('_bubbleDown'); | 20 const _bubbleDown = Symbol('_bubbleDown'); |
| 21 const _grow = Symbol('_grow'); | 21 const _grow = Symbol('_grow'); |
| 22 const HeapPriorityQueue$ = dart.generic(function(E) { | 22 const HeapPriorityQueue$ = dart.generic(function(E) { |
| 23 class HeapPriorityQueue extends core.Object { | 23 class HeapPriorityQueue extends core.Object { |
| 24 HeapPriorityQueue(comparison) { | 24 HeapPriorityQueue(comparison) { |
| 25 if (comparison === void 0) | 25 if (comparison === void 0) comparison = null; |
| 26 comparison = null; | |
| 27 this[_queue] = core.List$(E).new(HeapPriorityQueue$()._INITIAL_CAPACITY)
; | 26 this[_queue] = core.List$(E).new(HeapPriorityQueue$()._INITIAL_CAPACITY)
; |
| 28 this.comparison = comparison != null ? comparison : core.Comparable.comp
are; | 27 this.comparison = comparison != null ? comparison : core.Comparable.comp
are; |
| 29 this[_length] = 0; | 28 this[_length] = 0; |
| 30 } | 29 } |
| 31 add(element) { | 30 add(element) { |
| 32 dart.as(element, E); | 31 dart.as(element, E); |
| 33 this[_add](element); | 32 this[_add](element); |
| 34 } | 33 } |
| 35 addAll(elements) { | 34 addAll(elements) { |
| 36 dart.as(elements, core.Iterable$(E)); | 35 dart.as(elements, core.Iterable$(E)); |
| 37 for (let element of elements) { | 36 for (let element of elements) { |
| 38 this[_add](element); | 37 this[_add](element); |
| 39 } | 38 } |
| 40 } | 39 } |
| 41 clear() { | 40 clear() { |
| 42 this[_queue] = dart.const(dart.list([], E)); | 41 this[_queue] = dart.const(dart.list([], E)); |
| 43 this[_length] = 0; | 42 this[_length] = 0; |
| 44 } | 43 } |
| 45 contains(object) { | 44 contains(object) { |
| 46 dart.as(object, E); | 45 dart.as(object, E); |
| 47 return dart.notNull(this[_locate](object)) >= 0; | 46 return dart.notNull(this[_locate](object)) >= 0; |
| 48 } | 47 } |
| 49 get first() { | 48 get first() { |
| 50 if (this[_length] == 0) | 49 if (this[_length] == 0) dart.throw(new core.StateError("No such element"
)); |
| 51 dart.throw(new core.StateError("No such element")); | |
| 52 return this[_queue][dartx.get](0); | 50 return this[_queue][dartx.get](0); |
| 53 } | 51 } |
| 54 get isEmpty() { | 52 get isEmpty() { |
| 55 return this[_length] == 0; | 53 return this[_length] == 0; |
| 56 } | 54 } |
| 57 get isNotEmpty() { | 55 get isNotEmpty() { |
| 58 return this[_length] != 0; | 56 return this[_length] != 0; |
| 59 } | 57 } |
| 60 get length() { | 58 get length() { |
| 61 return this[_length]; | 59 return this[_length]; |
| 62 } | 60 } |
| 63 remove(element) { | 61 remove(element) { |
| 64 dart.as(element, E); | 62 dart.as(element, E); |
| 65 let index = this[_locate](element); | 63 let index = this[_locate](element); |
| 66 if (dart.notNull(index) < 0) | 64 if (dart.notNull(index) < 0) return false; |
| 67 return false; | |
| 68 let last = this[_removeLast](); | 65 let last = this[_removeLast](); |
| 69 if (dart.notNull(index) < dart.notNull(this[_length])) { | 66 if (dart.notNull(index) < dart.notNull(this[_length])) { |
| 70 let comp = dart.dcall(this.comparison, last, element); | 67 let comp = dart.dcall(this.comparison, last, element); |
| 71 if (dart.notNull(comp) <= 0) { | 68 if (dart.notNull(comp) <= 0) { |
| 72 this[_bubbleUp](last, index); | 69 this[_bubbleUp](last, index); |
| 73 } else { | 70 } else { |
| 74 this[_bubbleDown](last, index); | 71 this[_bubbleDown](last, index); |
| 75 } | 72 } |
| 76 } | 73 } |
| 77 return true; | 74 return true; |
| 78 } | 75 } |
| 79 removeAll() { | 76 removeAll() { |
| 80 let result = this[_queue]; | 77 let result = this[_queue]; |
| 81 let length = this[_length]; | 78 let length = this[_length]; |
| 82 this[_queue] = dart.const(dart.list([], E)); | 79 this[_queue] = dart.const(dart.list([], E)); |
| 83 this[_length] = 0; | 80 this[_length] = 0; |
| 84 return result[dartx.take](length); | 81 return result[dartx.take](length); |
| 85 } | 82 } |
| 86 removeFirst() { | 83 removeFirst() { |
| 87 if (this[_length] == 0) | 84 if (this[_length] == 0) dart.throw(new core.StateError("No such element"
)); |
| 88 dart.throw(new core.StateError("No such element")); | |
| 89 let result = this[_queue][dartx.get](0); | 85 let result = this[_queue][dartx.get](0); |
| 90 let last = this[_removeLast](); | 86 let last = this[_removeLast](); |
| 91 if (dart.notNull(this[_length]) > 0) { | 87 if (dart.notNull(this[_length]) > 0) { |
| 92 this[_bubbleDown](last, 0); | 88 this[_bubbleDown](last, 0); |
| 93 } | 89 } |
| 94 return result; | 90 return result; |
| 95 } | 91 } |
| 96 toList() { | 92 toList() { |
| 97 let list = core.List$(E).new(); | 93 let list = core.List$(E).new(); |
| 98 list[dartx.length] = this[_length]; | 94 list[dartx.length] = this[_length]; |
| 99 list[dartx.setRange](0, this[_length], this[_queue]); | 95 list[dartx.setRange](0, this[_length], this[_queue]); |
| 100 list[dartx.sort](dart.as(this.comparison, __CastType0)); | 96 list[dartx.sort](dart.as(this.comparison, __CastType0)); |
| 101 return list; | 97 return list; |
| 102 } | 98 } |
| 103 toSet() { | 99 toSet() { |
| 104 let set = new (collection.SplayTreeSet$(E))(dart.as(this.comparison, dar
t.functionType(core.int, [E, E]))); | 100 let set = new (collection.SplayTreeSet$(E))(dart.as(this.comparison, dar
t.functionType(core.int, [E, E]))); |
| 105 for (let i = 0; dart.notNull(i) < dart.notNull(this[_length]); i = dart.
notNull(i) + 1) { | 101 for (let i = 0; dart.notNull(i) < dart.notNull(this[_length]); i = dart.
notNull(i) + 1) { |
| 106 set.add(this[_queue][dartx.get](i)); | 102 set.add(this[_queue][dartx.get](i)); |
| 107 } | 103 } |
| 108 return set; | 104 return set; |
| 109 } | 105 } |
| 110 toString() { | 106 toString() { |
| 111 return dart.toString(this[_queue][dartx.take](this[_length])); | 107 return dart.toString(this[_queue][dartx.take](this[_length])); |
| 112 } | 108 } |
| 113 [_add](element) { | 109 [_add](element) { |
| 114 dart.as(element, E); | 110 dart.as(element, E); |
| 115 if (this[_length] == this[_queue][dartx.length]) | 111 if (this[_length] == this[_queue][dartx.length]) this[_grow](); |
| 116 this[_grow](); | |
| 117 this[_bubbleUp](element, (() => { | 112 this[_bubbleUp](element, (() => { |
| 118 let x = this[_length]; | 113 let x = this[_length]; |
| 119 this[_length] = dart.notNull(x) + 1; | 114 this[_length] = dart.notNull(x) + 1; |
| 120 return x; | 115 return x; |
| 121 })()); | 116 })()); |
| 122 } | 117 } |
| 123 [_locate](object) { | 118 [_locate](object) { |
| 124 dart.as(object, E); | 119 dart.as(object, E); |
| 125 if (this[_length] == 0) | 120 if (this[_length] == 0) return -1; |
| 126 return -1; | |
| 127 let position = 1; | 121 let position = 1; |
| 128 do { | 122 do { |
| 129 let index = dart.notNull(position) - 1; | 123 let index = dart.notNull(position) - 1; |
| 130 let element = this[_queue][dartx.get](index); | 124 let element = this[_queue][dartx.get](index); |
| 131 let comp = dart.dcall(this.comparison, element, object); | 125 let comp = dart.dcall(this.comparison, element, object); |
| 132 if (comp == 0) | 126 if (comp == 0) return index; |
| 133 return index; | |
| 134 if (dart.notNull(comp) < 0) { | 127 if (dart.notNull(comp) < 0) { |
| 135 let leftChildPosition = dart.notNull(position) * 2; | 128 let leftChildPosition = dart.notNull(position) * 2; |
| 136 if (dart.notNull(leftChildPosition) <= dart.notNull(this[_length]))
{ | 129 if (dart.notNull(leftChildPosition) <= dart.notNull(this[_length]))
{ |
| 137 position = leftChildPosition; | 130 position = leftChildPosition; |
| 138 continue; | 131 continue; |
| 139 } | 132 } |
| 140 } | 133 } |
| 141 do { | 134 do { |
| 142 while (dart.notNull(position[dartx.isOdd])) { | 135 while (dart.notNull(position[dartx.isOdd])) { |
| 143 position = dart.notNull(position) >> 1; | 136 position = dart.notNull(position) >> 1; |
| 144 } | 137 } |
| 145 position = dart.notNull(position) + 1; | 138 position = dart.notNull(position) + 1; |
| 146 } while (dart.notNull(position) > dart.notNull(this[_length])); | 139 } while (dart.notNull(position) > dart.notNull(this[_length])); |
| 147 } while (position != 1); | 140 } while (position != 1); |
| 148 return -1; | 141 return -1; |
| 149 } | 142 } |
| 150 [_removeLast]() { | 143 [_removeLast]() { |
| 151 let newLength = dart.notNull(this[_length]) - 1; | 144 let newLength = dart.notNull(this[_length]) - 1; |
| 152 let last = this[_queue][dartx.get](newLength); | 145 let last = this[_queue][dartx.get](newLength); |
| 153 this[_queue][dartx.set](newLength, null); | 146 this[_queue][dartx.set](newLength, null); |
| 154 this[_length] = newLength; | 147 this[_length] = newLength; |
| 155 return last; | 148 return last; |
| 156 } | 149 } |
| 157 [_bubbleUp](element, index) { | 150 [_bubbleUp](element, index) { |
| 158 dart.as(element, E); | 151 dart.as(element, E); |
| 159 while (dart.notNull(index) > 0) { | 152 while (dart.notNull(index) > 0) { |
| 160 let parentIndex = ((dart.notNull(index) - 1) / 2)[dartx.truncate](); | 153 let parentIndex = ((dart.notNull(index) - 1) / 2)[dartx.truncate](); |
| 161 let parent = this[_queue][dartx.get](parentIndex); | 154 let parent = this[_queue][dartx.get](parentIndex); |
| 162 if (dart.notNull(dart.dcall(this.comparison, element, parent)) > 0) | 155 if (dart.notNull(dart.dcall(this.comparison, element, parent)) > 0) br
eak; |
| 163 break; | |
| 164 this[_queue][dartx.set](index, parent); | 156 this[_queue][dartx.set](index, parent); |
| 165 index = parentIndex; | 157 index = parentIndex; |
| 166 } | 158 } |
| 167 this[_queue][dartx.set](index, element); | 159 this[_queue][dartx.set](index, element); |
| 168 } | 160 } |
| 169 [_bubbleDown](element, index) { | 161 [_bubbleDown](element, index) { |
| 170 dart.as(element, E); | 162 dart.as(element, E); |
| 171 let rightChildIndex = dart.notNull(index) * 2 + 2; | 163 let rightChildIndex = dart.notNull(index) * 2 + 2; |
| 172 while (dart.notNull(rightChildIndex) < dart.notNull(this[_length])) { | 164 while (dart.notNull(rightChildIndex) < dart.notNull(this[_length])) { |
| 173 let leftChildIndex = dart.notNull(rightChildIndex) - 1; | 165 let leftChildIndex = dart.notNull(rightChildIndex) - 1; |
| (...skipping 24 matching lines...) Expand all Loading... |
| 198 let comp = dart.dcall(this.comparison, element, child); | 190 let comp = dart.dcall(this.comparison, element, child); |
| 199 if (dart.notNull(comp) > 0) { | 191 if (dart.notNull(comp) > 0) { |
| 200 this[_queue][dartx.set](index, child); | 192 this[_queue][dartx.set](index, child); |
| 201 index = leftChildIndex; | 193 index = leftChildIndex; |
| 202 } | 194 } |
| 203 } | 195 } |
| 204 this[_queue][dartx.set](index, element); | 196 this[_queue][dartx.set](index, element); |
| 205 } | 197 } |
| 206 [_grow]() { | 198 [_grow]() { |
| 207 let newCapacity = dart.notNull(this[_queue][dartx.length]) * 2 + 1; | 199 let newCapacity = dart.notNull(this[_queue][dartx.length]) * 2 + 1; |
| 208 if (dart.notNull(newCapacity) < dart.notNull(HeapPriorityQueue$()._INITI
AL_CAPACITY)) | 200 if (dart.notNull(newCapacity) < dart.notNull(HeapPriorityQueue$()._INITI
AL_CAPACITY)) newCapacity = HeapPriorityQueue$()._INITIAL_CAPACITY; |
| 209 newCapacity = HeapPriorityQueue$()._INITIAL_CAPACITY; | |
| 210 let newQueue = core.List$(E).new(newCapacity); | 201 let newQueue = core.List$(E).new(newCapacity); |
| 211 newQueue[dartx.setRange](0, this[_length], this[_queue]); | 202 newQueue[dartx.setRange](0, this[_length], this[_queue]); |
| 212 this[_queue] = newQueue; | 203 this[_queue] = newQueue; |
| 213 } | 204 } |
| 214 } | 205 } |
| 215 HeapPriorityQueue[dart.implements] = () => [PriorityQueue$(E)]; | 206 HeapPriorityQueue[dart.implements] = () => [PriorityQueue$(E)]; |
| 216 dart.setSignature(HeapPriorityQueue, { | 207 dart.setSignature(HeapPriorityQueue, { |
| 217 constructors: () => ({HeapPriorityQueue: [HeapPriorityQueue$(E), [], [dart
.functionType(core.int, [E, E])]]}), | 208 constructors: () => ({HeapPriorityQueue: [HeapPriorityQueue$(E), [], [dart
.functionType(core.int, [E, E])]]}), |
| 218 methods: () => ({ | 209 methods: () => ({ |
| 219 add: [dart.void, [E]], | 210 add: [dart.void, [E]], |
| (...skipping 21 matching lines...) Expand all Loading... |
| 241 const __CastType0 = dart.typedef('__CastType0', () => dart.functionType(core
.int, [E, E])); | 232 const __CastType0 = dart.typedef('__CastType0', () => dart.functionType(core
.int, [E, E])); |
| 242 return __CastType0; | 233 return __CastType0; |
| 243 }); | 234 }); |
| 244 let __CastType0 = __CastType0$(); | 235 let __CastType0 = __CastType0$(); |
| 245 // Exports: | 236 // Exports: |
| 246 exports.PriorityQueue$ = PriorityQueue$; | 237 exports.PriorityQueue$ = PriorityQueue$; |
| 247 exports.PriorityQueue = PriorityQueue; | 238 exports.PriorityQueue = PriorityQueue; |
| 248 exports.HeapPriorityQueue$ = HeapPriorityQueue$; | 239 exports.HeapPriorityQueue$ = HeapPriorityQueue$; |
| 249 exports.HeapPriorityQueue = HeapPriorityQueue; | 240 exports.HeapPriorityQueue = HeapPriorityQueue; |
| 250 }); | 241 }); |
| OLD | NEW |