Add EfficientLength marker interface to some iterabels.

sdk/lib/collection/queue.dart

 // Copyright (c) 2011, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 part of dart.collection;
 
 /**
  * A [Queue] is a collection that can be manipulated at both ends. One
  * can iterate over the elements of a queue through [forEach] or with
  * an [Iterator].
  */
-abstract class Queue<E> implements Iterable<E> {
+abstract class Queue<E> implements Iterable<E>, EfficientLength {

[sra1, 2013/10/09 21:16:53]

This is what is scary about tag interfaces.
They are irrevocable.
I can't "implement Queue" unless my implementation also guarantees
EfficientLength.
The implicit interface is polluted with implementation details.

A "get hasEfficientLength" method would allow subclasses to revoke the
attribute, but a method becomes an mandatory burden on each implementation.

To void this problem tag interfaces should be used only on private classes.

[floitsch, 2013/10/10 13:04:53]

I partially agree. However we already did "is Queue" checks and simply assumed
that it had an efficient length.
We should add documentation that 'length' of a Queue should be efficient.

And even then: if the length is not efficient the complexity of our operations
don't change. We just run through the elements twice (which is really only bad
when they have side-effects).
We could rename the TagInterface to something else.

@Lasse: add documentation for "length". ?

[sra1, 2013/10/10 17:02:41]

There are many interesting queue algorithms that do not have this property; to
require an efficient length would forego their use.

Can we at least move closer to the ideal of implementing EfficientLength only on
private classes?

What I propose:
'EfficientLength' is a statement about the behaviour of get:length, so it must
only be implemented by the classes that implement get:length.

Then at least you can visually check, and a programmable static analysis tool
might be able to enforce the style.

You can still screw up by overriding get:length, but that is a smaller problem
than polluting an abstract interface.

[floitsch, 2013/10/10 17:12:05]

The List interface specifies that its length must be efficient. There is no
reason not to add it there.
I'm willing to discuss its usefulness on other interfaces.

 
   /**
    * Creates a queue.
    */
   factory Queue() => new ListQueue<E>();
 
   /**
    * Creates a queue with the elements of [other]. The order in
    * the queue will be the order provided by the iterator of [other].
    */
@@ skipping 673 matching lines @@
     _queue._checkModification(_modificationCount);
     if (_position == _end) {
       _current = null;
       return false;
     }
     _current = _queue._table[_position];
     _position = (_position + 1) & (_queue._table.length - 1);
     return true;
   }
 }