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 import "utils.dart"; |
| 8 |
7 /// A priority queue is a priority based work-list of elements. | 9 /// A priority queue is a priority based work-list of elements. |
8 /// | 10 /// |
9 /// The queue allows adding elements, and removing them again in priority order. | 11 /// The queue allows adding elements, and removing them again in priority order. |
10 abstract class PriorityQueue<E> { | 12 abstract class PriorityQueue<E> { |
11 /// Creates an empty [PriorityQueue]. | 13 /// Creates an empty [PriorityQueue]. |
12 /// | 14 /// |
13 /// The created [PriorityQueue] is a plain [HeapPriorityQueue]. | 15 /// The created [PriorityQueue] is a plain [HeapPriorityQueue]. |
14 /// | 16 /// |
15 /// The [comparison] is a [Comparator] used to compare the priority of | 17 /// The [comparison] is a [Comparator] used to compare the priority of |
16 /// elements. An element that compares as less than another element has | 18 /// elements. An element that compares as less than another element has |
(...skipping 119 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
136 /// Create a new priority queue. | 138 /// Create a new priority queue. |
137 /// | 139 /// |
138 /// The [comparison] is a [Comparator] used to compare the priority of | 140 /// The [comparison] is a [Comparator] used to compare the priority of |
139 /// elements. An element that compares as less than another element has | 141 /// elements. An element that compares as less than another element has |
140 /// a higher priority. | 142 /// a higher priority. |
141 /// | 143 /// |
142 /// If [comparison] is omitted, it defaults to [Comparable.compare]. If this | 144 /// If [comparison] is omitted, it defaults to [Comparable.compare]. If this |
143 /// is the case, `E` must implement [Comparable], and this is checked at | 145 /// is the case, `E` must implement [Comparable], and this is checked at |
144 /// runtime for every comparison. | 146 /// runtime for every comparison. |
145 HeapPriorityQueue([int comparison(E e1, E e2)]) | 147 HeapPriorityQueue([int comparison(E e1, E e2)]) |
146 : comparison = comparison ?? | 148 : comparison = comparison ?? defaultCompare/*<E>*/(); |
147 ((e1, e2) => (e1 as Comparable).compareTo(e2)); | |
148 | 149 |
149 void add(E element) { | 150 void add(E element) { |
150 _add(element); | 151 _add(element); |
151 } | 152 } |
152 | 153 |
153 void addAll(Iterable<E> elements) { | 154 void addAll(Iterable<E> elements) { |
154 for (E element in elements) { | 155 for (E element in elements) { |
155 _add(element); | 156 _add(element); |
156 } | 157 } |
157 } | 158 } |
(...skipping 192 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
350 /// | 351 /// |
351 /// Called when the list is full. | 352 /// Called when the list is full. |
352 void _grow() { | 353 void _grow() { |
353 int newCapacity = _queue.length * 2 + 1; | 354 int newCapacity = _queue.length * 2 + 1; |
354 if (newCapacity < _INITIAL_CAPACITY) newCapacity = _INITIAL_CAPACITY; | 355 if (newCapacity < _INITIAL_CAPACITY) newCapacity = _INITIAL_CAPACITY; |
355 List<E> newQueue = new List<E>(newCapacity); | 356 List<E> newQueue = new List<E>(newCapacity); |
356 newQueue.setRange(0, _length, _queue); | 357 newQueue.setRange(0, _length, _queue); |
357 _queue = newQueue; | 358 _queue = newQueue; |
358 } | 359 } |
359 } | 360 } |
OLD | NEW |