Add "contains" method to Collection.

lib/core/sequences.dart

+// Copyright (c) 2012, 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.
+
+/**
+ * An indexed sequence of elements of the same type.
+ *
+ * This is a primitive interface that any finite integer-indexable
+ * sequences can implement.

[floitsch, 2012/10/16 14:03:19]

sequence (-s)

[Lasse Reichstein Nielsen, 2012/10/17 11:06:45]

Done.

+ */
+abstract class Sequence<T> {
+  int get length;
+  T operator[](int index);
+}
+
+/**
+ * A skeleton class for a [Collection] that is also a [Sequence].

[sra1, 2012/10/16 18:52:52]

The assumption is that length is efficient, otherwise overriding the operators
like reduce is a bad idea.

[Lasse Reichstein Nielsen, 2012/10/17 11:06:45]

True. I'm adding this as comments on the methods of Sequence.

+ */
+abstract class SequenceCollection<E> implements Collection<E>, Sequence<E> {
+  // The class is intended for use as a mixin as well.
+
+  Iterator<E> iterator() => new SequenceIterator(sequence);
+
+  void forEach(f(E element)) {
+    for (int i = 0; i < this.length; i++) f(this[i]);
+  }
+
+  Collection map(f(E element)) {
+    List result = new List(this.length);

[floitsch, 2012/10/16 14:03:19]

This violates the specification of 'map' which specifies that the return type
should be the same as the type of 'this'.

[sra1, 2012/10/16 18:52:52]

Dont make the returned value fixed length, since it then you might be forced to
copy the result, e.g this won't work:

var s = myThings.map(stringify)..add('end')

[Lasse Reichstein Nielsen, 2012/10/17 11:06:45]

That specification can't be followed exactly. There are no concrete classes that
are only SequenceCollection, so we don't have one to return. A List is a
SequenceCollection, so it's not entirely wrong. It would be preferable to return
a SequenceCollection view of the list. We don't have a List.asCollection yet
(and I hope we will). I think this is the best we can do at this time.

Good point on the fixed-length-ness of the result. I keep forgetting that new
List(4) generates a fixed length list.
That *really* needs to be fixed!

[floitsch, 2012/10/17 13:19:32]

That was not my point: from what I can see this class should serve as template
(super-class) of other SequenceCollections. But that doesn't work since it
always returns a List.

+    for (int i = 0; i < this.length; i++) {
+      result[i] = f(this[i]);
+    }
+    return result;
+  }
+
+  bool contains(E value) {
+    for (int i = 0; i < sequence.length; i++) {

[floitsch, 2012/10/16 14:03:19]

I would store the length in a variable, but that's nit-picking.

[Lasse Reichstein Nielsen, 2012/10/17 11:06:45]

I try to avoid that when I don't know whether the length of the sequence might
change between accesses. It's defensive programming (and not really safe if the
sequence is being deliberately malicious and changes between calls to "length").

Fixing length at the start will prevent an infinite loop if the list is, e.g.,
"list of the calls of '==' on my class".

+      if (sequence[i] == value) return true;
+    }
+    return false;
+  }
+
+  reduce(initialValue, combine(previousValue, E element)) {
+    var value = initialValue;
+    for (int i = 0; i < this.length; i++) {
+      value = combine(value, this[i]);
+    }
+    return value;
+  }
+
+  Collection<E> filter(bool f(E element)) {
+    List<E> result = <E>[];

[floitsch, 2012/10/16 14:03:19]

Ditto: violates the contract.

[Lasse Reichstein Nielsen, 2012/10/17 11:06:45]

Arguably.

+    for (int i = 0; i < this.length; i++) {
+      E element = this[i];
+      if (f(element)) result.add(element);
+    }
+    return result;
+  }
+
+  bool every(bool f(E element)) {
+    for (int i = 0; i < this.length; i++) {
+      if (!f(this[i])) return false;
+    }
+    return true;
+  }
+
+  bool some(bool f(E element)) {
+    for (int i = 0; i < this.length; i++) {
+      if (f(this[i])) return true;
+    }
+    return false;
+  }
+
+  bool isEmpty() {
+    return this.length == 0;
+  }
+}
+
+
+/**
+ * An unmodifiable [List] backed by a [Sequence].
+ */
+class SequenceList<E> extends SequenceCollection<E> implements List<E> {
+  Sequence<E> sequence;
+  SequenceList(this.sequence);
+
+  int get length => sequence.length;
+
+  T operator[](int index) => sequence[index];
+
+  int indexOf(E value, [int start = 0]) {
+    for (int i = start; i < sequence.length; i++) {
+      if (sequence[i] == value) return i;
+    }
+    return -1;
+  }
+
+  int lastIndexOf(E value, [int start]) {
+    if (start == null) start = sequence.length - 1;
+    for (int i = start; i >= 0; i--) {
+      if (sequence[i] == value) return i;
+    }
+    return -1;
+  }
+
+  E last() => sequence[sequence.length - 1];
+
+  List<E> getRange(int start, int length) {
+    List<E> result = <E>[];
+    for (int i = 0; i < length; i++) {
+      result.add(sequence[start + i]);
+    }
+    return result;
+  }
+
+  void operator []=(int index, E value) {
+    throw new IllegalAccessException();
+  }
+
+  void set length(int newLength) {
+    throw new IllegalAccessException();
+  }
+
+  void add(E value) {
+    throw new IllegalAccessException();
+  }
+
+  void addLast(E value) {
+    throw new IllegalAccessException();
+  }
+
+  void addAll(Collection<E> collection) {
+    throw new IllegalAccessException();
+  }
+
+  void sort(Comparator<E> compare) {
+    throw new IllegalAccessException();

[ngeoffray, 2012/10/16 15:08:18]

Access? Should it be UnsupportedOperationException instead? (and same for all
others)

[Lasse Reichstein Nielsen, 2012/10/17 11:06:45]

You are right - the VM's implementation mostly uses
UnsupportedOperationException (I must have been looking at immutable_map.dart).
Fixing.

This is another exception that should be a StateError with a suitable message.

+  }
+
+  void clear() {
+    throw new IllegalAccessException();
+  }
+
+  E removeAt(int index) {
+    throw new IllegalAccessException();
+  }
+
+  E removeLast() {
+    throw new IllegalAccessException();
+  }
+
+  void setRange(int start, int length, List<E> from, [int startFrom]) {
+    throw new IllegalAccessException();
+  }
+
+  void removeRange(int start, int length) {
+    throw new IllegalAccessException();
+  }
+
+  void insertRange(int start, int length, [E initialValue]) {
+    throw new IllegalAccessException();
+  }
+}
+
+/**
+ * Iterates over a [Sequence] in growing index order.
+ */
+class SequenceIterator<E> implements Iterator<E> {
+  Sequence<E> _sequence;
+  int _position;
+  SequenceIterator(this._sequence) : _position = 0;
+  bool hasNext() => _position < _sequence.length;
+  E next() {
+    if (hasNext()) return _sequence[_position++];
+    throw new NoMoreElementsException();
+  }
+}
+