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 class that efficiently implements both [Queue] and [List]. | 7 /// A class that efficiently implements both [Queue] and [List]. |
8 // TODO(nweiz): Currently this code is copied almost verbatim from | 8 // TODO(nweiz): Currently this code is copied almost verbatim from |
9 // dart:collection. The only changes are to implement List and to remove methods | 9 // dart:collection. The only changes are to implement List and to remove methods |
10 // that are redundant with ListMixin. Remove or simplify it when issue 21330 is | 10 // that are redundant with ListMixin. Remove or simplify it when issue 21330 is |
(...skipping 17 matching lines...) Expand all Loading... |
28 assert(_isPowerOf2(initialCapacity)); | 28 assert(_isPowerOf2(initialCapacity)); |
29 _table = new List<E>(initialCapacity); | 29 _table = new List<E>(initialCapacity); |
30 } | 30 } |
31 | 31 |
32 /// Create a queue initially containing the elements of [source]. | 32 /// Create a queue initially containing the elements of [source]. |
33 factory QueueList.from(Iterable<E> source) { | 33 factory QueueList.from(Iterable<E> source) { |
34 if (source is List) { | 34 if (source is List) { |
35 int length = source.length; | 35 int length = source.length; |
36 QueueList<E> queue = new QueueList(length + 1); | 36 QueueList<E> queue = new QueueList(length + 1); |
37 assert(queue._table.length > length); | 37 assert(queue._table.length > length); |
38 List sourceList = source; | 38 var sourceList = source; |
39 queue._table.setRange(0, length, sourceList, 0); | 39 queue._table.setRange(0, length, sourceList, 0); |
40 queue._tail = length; | 40 queue._tail = length; |
41 return queue; | 41 return queue; |
42 } else { | 42 } else { |
43 return new QueueList<E>()..addAll(source); | 43 return new QueueList<E>()..addAll(source); |
44 } | 44 } |
45 } | 45 } |
46 | 46 |
47 // Collection interface. | 47 // Collection interface. |
48 | 48 |
49 void add(E element) { | 49 void add(E element) { |
50 _add(element); | 50 _add(element); |
51 } | 51 } |
52 | 52 |
53 void addAll(Iterable<E> elements) { | 53 void addAll(Iterable<E> elements) { |
54 if (elements is List) { | 54 if (elements is List) { |
55 List list = elements; | 55 var list = elements; |
56 int addCount = list.length; | 56 int addCount = list.length; |
57 int length = this.length; | 57 int length = this.length; |
58 if (length + addCount >= _table.length) { | 58 if (length + addCount >= _table.length) { |
59 _preGrow(length + addCount); | 59 _preGrow(length + addCount); |
60 // After preGrow, all elements are at the start of the list. | 60 // After preGrow, all elements are at the start of the list. |
61 _table.setRange(length, length + addCount, list, 0); | 61 _table.setRange(length, length + addCount, list, 0); |
62 _tail += addCount; | 62 _tail += addCount; |
63 } else { | 63 } else { |
64 // Adding addCount elements won't reach _head. | 64 // Adding addCount elements won't reach _head. |
65 int endSpace = _table.length - _tail; | 65 int endSpace = _table.length - _tail; |
(...skipping 144 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
210 // Add 1.5x extra room to ensure that there's room for more elements after | 210 // Add 1.5x extra room to ensure that there's room for more elements after |
211 // expansion. | 211 // expansion. |
212 newElementCount += newElementCount >> 1; | 212 newElementCount += newElementCount >> 1; |
213 int newCapacity = _nextPowerOf2(newElementCount); | 213 int newCapacity = _nextPowerOf2(newElementCount); |
214 List<E> newTable = new List<E>(newCapacity); | 214 List<E> newTable = new List<E>(newCapacity); |
215 _tail = _writeToList(newTable); | 215 _tail = _writeToList(newTable); |
216 _table = newTable; | 216 _table = newTable; |
217 _head = 0; | 217 _head = 0; |
218 } | 218 } |
219 } | 219 } |
OLD | NEW |