| 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 |