Add ListQueue and make it the default Queue.

Add ListQueue and make it the default Queue.

ListQueue has a very low overhead for operations (low memory overhead, better memory locality) compared to a double-linked list solution, but at the cost of only amortized constant time adding.

Committed: https://code.google.com/p/dart/source/detail?r=18309

[floitsch, 2013-02-07 16:44:31]

LGTM.
Please add tests for the cases where I had comments.

https://codereview.chromium.org/12217061/diff/1/sdk/lib/collection/queue.dart
File sdk/lib/collection/queue.dart (right):

https://codereview.chromium.org/12217061/diff/1/sdk/lib/collection/queue.dart...
sdk/lib/collection/queue.dart:360: int length = source.length;
Since we still do a List check below, might as well avoid the length getter.
(I know: I'm inconsistent).

https://codereview.chromium.org/12217061/diff/1/sdk/lib/collection/queue.dart...
sdk/lib/collection/queue.dart:406: if (index < 0 || index > length) throw new
RangeError.range(index, 0, length);
80 chars.

https://codereview.chromium.org/12217061/diff/1/sdk/lib/collection/queue.dart...
sdk/lib/collection/queue.dart:442: _table.setRange(length, addCount, list, 0);
Add comment: After [_preGrow] all elements have been moved to the beginning of
the list.

https://codereview.chromium.org/12217061/diff/1/sdk/lib/collection/queue.dart...
sdk/lib/collection/queue.dart:488: void removeMatching(bool test(E element)) {
Share the code for remove and retainMatching.

https://codereview.chromium.org/12217061/diff/1/sdk/lib/collection/queue.dart...
sdk/lib/collection/queue.dart:584: static int _nextPowerOf2(int number) {
not doing the right thing. the result is never bigger than the input.

https://codereview.chromium.org/12217061/diff/1/sdk/lib/collection/queue.dart...
sdk/lib/collection/queue.dart:616: while (i != _head) {
setRange doesn't work on the same list?

https://codereview.chromium.org/12217061/diff/1/sdk/lib/collection/queue.dart...
sdk/lib/collection/queue.dart:622: _head++;
_head = _head + 1 & mask ?

https://codereview.chromium.org/12217061/diff/1/sdk/lib/collection/queue.dart...
sdk/lib/collection/queue.dart:623: return offset + 1;
(offset + 1) & mask

https://codereview.chromium.org/12217061/diff/1/sdk/lib/collection/queue.dart...
sdk/lib/collection/queue.dart:675: * Considers any add, remove operation a
concurrent modification
as

[sra1, 2013-02-07 19:48:49]

I'm wondering if there is a slightly different implementation that shares more
code with a list view?

This CL adds 29k to swarm:
 771831  r18226
 801126  r18226 + patch
  29295

Analysis: (bytes - file - reason)

960   sdk/lib/_internal/compiler/implementation/lib/js_array.dart
  JSArray.setRange not previously used

1581  sdk/lib/collection/arrays.dart
  Arrays.copy, not previously used, called from JSArray.setRange

2459  sdk/lib/html/dart2js/html_dart2js.dart
  Multiple List implementations define setRange

23666 sdk/lib/collection/queue.dart
  new classes

I think the 2.5k html_dart2js.dart increase can be fixed since all calls to
setRange have a known receiver type.  There *should* be typed selectors in play
here -Nicolas - perhaps you could see why this is not already happening?  All
calls are directly via the JSArray interceptor.

[sra1, 2013-02-07 20:07:23]

On 2013/02/07 19:48:49, sra1 wrote:
> I'm wondering if there is a slightly different implementation that shares more
> code with a list view?
> 
> This CL adds 29k to swarm:
>  771831  r18226
>  801126  r18226 + patch
>   29295
> 
> Analysis: (bytes - file - reason)
> 
> 960   sdk/lib/_internal/compiler/implementation/lib/js_array.dart
>   JSArray.setRange not previously used
> 
> 1581  sdk/lib/collection/arrays.dart
>   Arrays.copy, not previously used, called from JSArray.setRange
> 
> 2459  sdk/lib/html/dart2js/html_dart2js.dart
>   Multiple List implementations define setRange
> 
> 23666 sdk/lib/collection/queue.dart
>   new classes
> 
> I think the 2.5k html_dart2js.dart increase can be fixed since all calls to
> setRange have a known receiver type.  There *should* be typed selectors in
play
> here -Nicolas - perhaps you could see why this is not already happening?  All
> calls are directly via the JSArray interceptor.

I'm incorrect on this last point.  There calls with an unknown receiver that I
missed due to a one-shot interceptor.  Improved field type analysis could
recover the type.

[Lasse Reichstein Nielsen, 2013-02-11 15:02:32]

https://codereview.chromium.org/12217061/diff/1/sdk/lib/collection/queue.dart
File sdk/lib/collection/queue.dart (right):

https://codereview.chromium.org/12217061/diff/1/sdk/lib/collection/queue.dart...
sdk/lib/collection/queue.dart:360: int length = source.length;
Please elaborate. I need the length to find the necessary capacity. What do you
want omitted?

https://codereview.chromium.org/12217061/diff/1/sdk/lib/collection/queue.dart...
sdk/lib/collection/queue.dart:442: _table.setRange(length, addCount, list, 0);
On 2013/02/07 16:44:31, floitsch wrote:
> Add comment: After [_preGrow] all elements have been moved to the beginning of
> the list.

Done.

https://codereview.chromium.org/12217061/diff/1/sdk/lib/collection/queue.dart...
sdk/lib/collection/queue.dart:488: void removeMatching(bool test(E element)) {
On 2013/02/07 16:44:31, floitsch wrote:
> Share the code for remove and retainMatching.

Done.

https://codereview.chromium.org/12217061/diff/1/sdk/lib/collection/queue.dart...
sdk/lib/collection/queue.dart:584: static int _nextPowerOf2(int number) {
On 2013/02/07 16:44:31, floitsch wrote:
> not doing the right thing. the result is never bigger than the input.

Done.

https://codereview.chromium.org/12217061/diff/1/sdk/lib/collection/queue.dart...
sdk/lib/collection/queue.dart:616: while (i != _head) {
I assumed it doesn't.  
It actually seems that it does work (at least for the fixed arrays I'm using).
It would require handling wrapping indices though.

https://codereview.chromium.org/12217061/diff/1/sdk/lib/collection/queue.dart...
sdk/lib/collection/queue.dart:623: return offset + 1;
On 2013/02/07 16:44:31, floitsch wrote:
> (offset + 1) & mask

Done.

https://codereview.chromium.org/12217061/diff/1/sdk/lib/collection/queue.dart...
sdk/lib/collection/queue.dart:675: * Considers any add, remove operation a
concurrent modification
No "as" intended.

[floitsch, 2013-02-11 15:15:11]

https://codereview.chromium.org/12217061/diff/7001/sdk/lib/collection/queue.dart
File sdk/lib/collection/queue.dart (right):

https://codereview.chromium.org/12217061/diff/7001/sdk/lib/collection/queue.d...
sdk/lib/collection/queue.dart:566: number = (number << 2) - 1;
Still not correct. This returns 16 for 7.
First guess would be to just shift by 1.

[sra1, 2013-02-12 01:09:56]

https://chromiumcodereview.appspot.com/12217061/diff/7001/sdk/lib/collection/...
File sdk/lib/collection/queue.dart (right):

https://chromiumcodereview.appspot.com/12217061/diff/7001/sdk/lib/collection/...
sdk/lib/collection/queue.dart:564: static int _nextPowerOf2(int number) {
This function might be easier to write correctly if you could use int.bitLength,
defined to return the 0-based bit position of the most significant bit that is
different to the sign bit.

https://code.google.com/p/dart/issues/detail?id=5828

int guess = 1 << number.bitLength;
return (guess < number) ? 2 * guess : guess;