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

Side by Side Diff: lib/src/priority_queue.dart

Issue 1817463002: Finish @nex3's strong-mode fixes in package:collection and test it in Travis (Closed) Base URL: https://github.com/ochafik/collection.git@master
Patch Set: revert _throw (now generic) Created 4 years, 9 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 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file
2 // for details. All rights reserved. Use of this source code is governed by a 2 // for details. All rights reserved. Use of this source code is governed by a
3 // BSD-style license that can be found in the LICENSE file. 3 // BSD-style license that can be found in the LICENSE file.
4 4
5 import "dart:collection"; 5 import "dart:collection";
6 6
7 /// A priority queue is a priority based work-list of elements. 7 /// A priority queue is a priority based work-list of elements.
8 /// 8 ///
9 /// The queue allows adding elements, and removing them again in priority order. 9 /// The queue allows adding elements, and removing them again in priority order.
10 abstract class PriorityQueue<E> { 10 abstract class PriorityQueue<E> {
(...skipping 103 matching lines...) Expand 10 before | Expand all | Expand 10 after
114 /// an expected O(n*log(n)) time. 114 /// an expected O(n*log(n)) time.
115 class HeapPriorityQueue<E> implements PriorityQueue<E> { 115 class HeapPriorityQueue<E> implements PriorityQueue<E> {
116 /// Initial capacity of a queue when created, or when added to after a 116 /// Initial capacity of a queue when created, or when added to after a
117 /// [clear]. 117 /// [clear].
118 /// 118 ///
119 /// Number can be any positive value. Picking a size that gives a whole 119 /// Number can be any positive value. Picking a size that gives a whole
120 /// number of "tree levels" in the heap is only done for aesthetic reasons. 120 /// number of "tree levels" in the heap is only done for aesthetic reasons.
121 static const int _INITIAL_CAPACITY = 7; 121 static const int _INITIAL_CAPACITY = 7;
122 122
123 /// The comparison being used to compare the priority of elements. 123 /// The comparison being used to compare the priority of elements.
124 final Comparator comparison; 124 final Comparator<E> comparison;
125 125
126 /// List implementation of a heap. 126 /// List implementation of a heap.
127 List<E> _queue = new List<E>(_INITIAL_CAPACITY); 127 List<E> _queue = new List<E>(_INITIAL_CAPACITY);
128 128
129 /// Number of elements in queue. 129 /// Number of elements in queue.
130 /// 130 ///
131 /// The heap is implemented in the first [_length] entries of [_queue]. 131 /// The heap is implemented in the first [_length] entries of [_queue].
132 int _length = 0; 132 int _length = 0;
133 133
134 /// Create a new priority queue. 134 /// Create a new priority queue.
(...skipping 210 matching lines...) Expand 10 before | Expand all | Expand 10 after
345 /// 345 ///
346 /// Called when the list is full. 346 /// Called when the list is full.
347 void _grow() { 347 void _grow() {
348 int newCapacity = _queue.length * 2 + 1; 348 int newCapacity = _queue.length * 2 + 1;
349 if (newCapacity < _INITIAL_CAPACITY) newCapacity = _INITIAL_CAPACITY; 349 if (newCapacity < _INITIAL_CAPACITY) newCapacity = _INITIAL_CAPACITY;
350 List<E> newQueue = new List<E>(newCapacity); 350 List<E> newQueue = new List<E>(newCapacity);
351 newQueue.setRange(0, _length, _queue); 351 newQueue.setRange(0, _length, _queue);
352 _queue = newQueue; 352 _queue = newQueue;
353 } 353 }
354 } 354 }
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698