Add a QueueList class to the collection package.

Add a QueueList class to the collection package.

This class is based on the ListQueue implementation and implements both the
Queue and List interfaces.

R=lrn@google.com

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

[nweiz, 2014-10-28 21:53:53]

nweiz@google.com changed reviewers:
+ lrn@google.com

[Lasse Reichstein Nielsen, 2014-10-29 07:04:44]

lgtm

I'd consider implementing setRange, and possibly other *Range methods. The
setRange function is often used to make other operations efficient, and in some
cases it can be converted into a single setRange on the _buffer.

Also insert and removeAt could be more efficient by working towards the nearest
end.

LGTM.

https://codereview.chromium.org/660373002/diff/1/pkg/collection/lib/src/queue...
File pkg/collection/lib/src/queue_list.dart (right):

https://codereview.chromium.org/660373002/diff/1/pkg/collection/lib/src/queue...
pkg/collection/lib/src/queue_list.dart:125: }
This could probably be more efficient. Maybe:

int delta = value - length;
if (delta >= 0) {
  if (_table.length <= value) {
    _preGrow(value);
  }
  _head = (_head + delta) & (_table.length - 1)
} else {
  int newTail = _tail + delta;  // `delta` is negative.
  if (newTail >= 0) {
    _table.fillRange(newTail, _tail, null);
  } else { 
    int tableLength = _table.Length;
    newTail += tableLength;
    _table.fillRange(0, _tail, null);
    _table.fillRange(newTail, tableLength, null);
  }
  _tail = newTail;
}

https://codereview.chromium.org/660373002/diff/1/pkg/collection/lib/src/queue...
pkg/collection/lib/src/queue_list.dart:133: E operator [](int index) =>
_table[(_head + index) & (_table.length - 1)];
This, and []=, needs bounds checks.

https://codereview.chromium.org/660373002/diff/1/pkg/collection/lib/src/queue...
pkg/collection/lib/src/queue_list.dart:157: number = (number << 2) - 1;
I think it should only be "<< 1".

https://codereview.chromium.org/660373002/diff/1/pkg/collection/lib/src/queue...
pkg/collection/lib/src/queue_list.dart:162: }
Do we get a warning here for not returning a value?
If so, just change "return number" to "break" and put the return after the loop.

https://codereview.chromium.org/660373002/diff/1/pkg/collection/test/queue_li...
File pkg/collection/test/queue_list_test.dart (right):

https://codereview.chromium.org/660373002/diff/1/pkg/collection/test/queue_li...
pkg/collection/test/queue_list_test.dart:229: // capacity of 8.
The buffer grows when the 8th element is added, so technically it's not full any
more. It's designed to never be full (because _head==_tail means the buffer is
empty, and being full would be indistinguishable from that).

https://codereview.chromium.org/660373002/diff/1/pkg/collection/test/queue_li...
pkg/collection/test/queue_list_test.dart:249: "ConcurrentModificationError"));
Consider copying some tests from tests/corelib/list_test.dart to test the List
behavior thoroughly.

[Lasse Reichstein Nielsen, 2014-10-29 08:15:30]

https://codereview.chromium.org/660373002/diff/1/pkg/collection/lib/src/queue...
File pkg/collection/lib/src/queue_list.dart (right):

https://codereview.chromium.org/660373002/diff/1/pkg/collection/lib/src/queue...
pkg/collection/lib/src/queue_list.dart:125: }
(But warning: Not tested!)

https://codereview.chromium.org/660373002/diff/1/pkg/collection/lib/src/queue...
pkg/collection/lib/src/queue_list.dart:157: number = (number << 2) - 1;
Alternatively it is deliberate in order to not grow to buffer that will
immediately be filled anyway. I don't remember, and I haven't documented it.
That just makes the comment wrong.
I think this function should be changed to "<< 1", and the use in _preGrow
should add something to the element count.

https://codereview.chromium.org/660373002/diff/1/pkg/collection/lib/src/queue...
pkg/collection/lib/src/queue_list.dart:202: int newCapacity =
_nextPowerOf2(newElementCount);
newElementCount -> newElementCount + 1
to ensure we have capacity exceeding the expected number of elements, instead of
relying on nextPowerOf2 to double the result.
Maybe even ensure an overhead, so either:
 -> newElementCount * 2
or just * 1.5:
 -> newElementCount + newElementCount >> 1

[nweiz, 2014-10-29 20:43:25]

Code review changes

[nweiz, 2014-10-29 20:49:36]

> I'd consider implementing setRange, and possibly other *Range methods. The
setRange function is often used to make other operations efficient, and in some
cases it can be converted into a single setRange on the _buffer.
> 
> Also insert and removeAt could be more efficient by working towards the
nearest
end.

I'd like to get a baseline working version in for now so I can get myself
unblocked.

https://codereview.chromium.org/660373002/diff/1/pkg/collection/lib/src/queue...
File pkg/collection/lib/src/queue_list.dart (right):

https://codereview.chromium.org/660373002/diff/1/pkg/collection/lib/src/queue...
pkg/collection/lib/src/queue_list.dart:125: }
On 2014/10/29 07:04:44, Lasse Reichstein Nielsen wrote:
> This could probably be more efficient. Maybe:
> 
> int delta = value - length;
> if (delta >= 0) {
>   if (_table.length <= value) {
>     _preGrow(value);
>   }
>   _head = (_head + delta) & (_table.length - 1)
> } else {
>   int newTail = _tail + delta;  // `delta` is negative.
>   if (newTail >= 0) {
>     _table.fillRange(newTail, _tail, null);
>   } else { 
>     int tableLength = _table.Length;
>     newTail += tableLength;
>     _table.fillRange(0, _tail, null);
>     _table.fillRange(newTail, tableLength, null);
>   }
>   _tail = newTail;
> }
> 
>   

Done.

https://codereview.chromium.org/660373002/diff/1/pkg/collection/lib/src/queue...
pkg/collection/lib/src/queue_list.dart:133: E operator [](int index) =>
_table[(_head + index) & (_table.length - 1)];
On 2014/10/29 07:04:44, Lasse Reichstein Nielsen wrote:
> This, and []=, needs bounds checks.

Done.

https://codereview.chromium.org/660373002/diff/1/pkg/collection/lib/src/queue...
pkg/collection/lib/src/queue_list.dart:157: number = (number << 2) - 1;
On 2014/10/29 08:15:30, Lasse Reichstein Nielsen wrote:
> Alternatively it is deliberate in order to not grow to buffer that will
> immediately be filled anyway. I don't remember, and I haven't documented it.
> That just makes the comment wrong.
> I think this function should be changed to "<< 1", and the use in _preGrow
> should add something to the element count.

Done; also changed in Queue itself.

https://codereview.chromium.org/660373002/diff/1/pkg/collection/lib/src/queue...
pkg/collection/lib/src/queue_list.dart:162: }
On 2014/10/29 07:04:44, Lasse Reichstein Nielsen wrote:
> Do we get a warning here for not returning a value?
> If so, just change "return number" to "break" and put the return after the
loop.

It doesn't look like we do. Apparently the analyzer trusts that that return will
be reached.

https://codereview.chromium.org/660373002/diff/1/pkg/collection/lib/src/queue...
pkg/collection/lib/src/queue_list.dart:202: int newCapacity =
_nextPowerOf2(newElementCount);
On 2014/10/29 08:15:30, Lasse Reichstein Nielsen wrote:
> newElementCount -> newElementCount + 1
> to ensure we have capacity exceeding the expected number of elements, instead
of
> relying on nextPowerOf2 to double the result.
> Maybe even ensure an overhead, so either:
>  -> newElementCount * 2
> or just * 1.5:
>  -> newElementCount + newElementCount >> 1
>  

Done.

https://codereview.chromium.org/660373002/diff/1/pkg/collection/test/queue_li...
File pkg/collection/test/queue_list_test.dart (right):

https://codereview.chromium.org/660373002/diff/1/pkg/collection/test/queue_li...
pkg/collection/test/queue_list_test.dart:229: // capacity of 8.
On 2014/10/29 07:04:44, Lasse Reichstein Nielsen wrote:
> The buffer grows when the 8th element is added, so technically it's not full
any
> more. It's designed to never be full (because _head==_tail means the buffer is
> empty, and being full would be indistinguishable from that).

Done.

https://codereview.chromium.org/660373002/diff/1/pkg/collection/test/queue_li...
pkg/collection/test/queue_list_test.dart:249: "ConcurrentModificationError"));
On 2014/10/29 07:04:44, Lasse Reichstein Nielsen wrote:
> Consider copying some tests from tests/corelib/list_test.dart to test the List
> behavior thoroughly.

I think we can rely on the implementation of ListMixin to ensure that those are
correct given that the operations we implement are correct.

[Lasse Reichstein Nielsen, 2014-10-31 10:07:19]

LGTM!

https://codereview.chromium.org/660373002/diff/20001/pkg/collection/lib/src/q...
File pkg/collection/lib/src/queue_list.dart (right):

https://codereview.chromium.org/660373002/diff/20001/pkg/collection/lib/src/q...
pkg/collection/lib/src/queue_list.dart:144: throw new RangeError("Index $index
must be in the range [0..$length).");
You can use:
 new RangeError.range(index, 0, length - 1);

[nweiz, 2014-11-03 20:36:58]

https://codereview.chromium.org/660373002/diff/20001/pkg/collection/lib/src/q...
File pkg/collection/lib/src/queue_list.dart (right):

https://codereview.chromium.org/660373002/diff/20001/pkg/collection/lib/src/q...
pkg/collection/lib/src/queue_list.dart:144: throw new RangeError("Index $index
must be in the range [0..$length).");
On 2014/10/31 10:07:19, Lasse Reichstein Nielsen wrote:
> You can use:
>  new RangeError.range(index, 0, length - 1);

That doesn't produce a nice message when length is 0.

[nweiz, 2014-11-03 20:39:33]

Committed patchset #2 (id:20001) manually as 41467 (presubmit successful).

[Lasse Reichstein Nielsen, 2014-11-03 21:05:55]

https://codereview.chromium.org/660373002/diff/20001/pkg/collection/lib/src/q...
File pkg/collection/lib/src/queue_list.dart (right):

https://codereview.chromium.org/660373002/diff/20001/pkg/collection/lib/src/q...
pkg/collection/lib/src/queue_list.dart:144: throw new RangeError("Index $index
must be in the range [0..$length).");
Good point. I should improve the message in that case.

[sra1, 2014-11-03 21:33:50]

sra@google.com changed reviewers:
+ sra@google.com

[sra1, 2014-11-03 21:33:51]

https://codereview.chromium.org/660373002/diff/20001/pkg/collection/lib/src/q...
File pkg/collection/lib/src/queue_list.dart (right):

https://codereview.chromium.org/660373002/diff/20001/pkg/collection/lib/src/q...
pkg/collection/lib/src/queue_list.dart:144: throw new RangeError("Index $index
must be in the range [0..$length).");
On 2014/11/03 20:36:58, nweiz wrote:
> On 2014/10/31 10:07:19, Lasse Reichstein Nielsen wrote:
> > You can use:
> >  new RangeError.range(index, 0, length - 1);
> 
> That doesn't produce a nice message when length is 0.

Lasse: I have found this to be an issue as well.

Should we have a new constructor that supports this common case?

RangeError.range has historically been used inconsistently because many (but not
all) ranges are [start,end) (half-open indexes) but RangeError.range is tailored
to [start,end] ranges (closed positions).

It is irritating to have to do arithmetic at the throw site and more code
increases the chance that another error is thrown due to a mistake in calling or
execution of the constructor.

I also believe we have missed an opportunity to make various errors more
introspectable - a RangeError could have kept the bad element as a plain value
for inspecting in the debugger, rather than interpolated into a message.  In
this case, the indexable collection should be held by the Error too, even if it
is never part of the message.