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