Add List.reversed to give a reverse fixed-length view of a list.

sdk/lib/core/list.dart

Index: sdk/lib/core/list.dart
diff --git a/sdk/lib/core/list.dart b/sdk/lib/core/list.dart
index 062a0d9cfa7e947082ddd57d44ce5daa3ee54887..f5ef21867ffd56890486183934e08ad88821b21c 100644
--- a/sdk/lib/core/list.dart
+++ b/sdk/lib/core/list.dart
@@ -85,6 +85,15 @@ abstract class List<E> implements Collection<E> {
   void addAll(Iterable<E> iterable);
 
   /**
+   * Returns a reversed fixed-length view of this [List].
+   *
+   * The reversed list has elements in the opposite order of this list.
+   * It is backed by this list, but will stop working if this list
+   * becomes shorter than its current length.
+   */
+  List<T> get reversed => new ReversedList(this, 0, length);
+
+  /**
    * Sorts the list according to the order specified by the [compare] function.
    *
    * The [compare] function must act as a [Comparator].
@@ -192,11 +201,12 @@ abstract class List<E> implements Collection<E> {
 }
 
 /**
- * An unmodifiable [List].
+ * Class implementing the read-operations on [List].
+ *
+ * Implements all operations except [:operator[]:] and [:length:] that does not
+ * modify the list in terms of those two.
  */
-abstract class NonExtensibleListMixin<E>
-    extends Iterable<E> implements List<E> {
-
+abstract class BaseListMixin<E> extends Iterable<E> implements List<E> {

[floitsch, 2013/01/21 14:38:06]

These classes are no longer in core.

[Lasse Reichstein Nielsen, 2013/01/22 10:18:52]

Moved to collection-dev.

   Iterator<E> get iterator => new ListIterator(this);
 
   void forEach(f(E element)) {
@@ -278,6 +288,98 @@ abstract class NonExtensibleListMixin<E>
     }
     return result;
   }
+}
+
+/**
+ * Abstract class implementing the non-length changing operations of [List].
+ */
+abstract class FixedLengthListMixin<E> extends BaseListMixin<E> {

[floitsch, 2013/01/21 14:38:06]

Can't be a mixin, since it extends (or mixins) BaseListMixin.

[Lasse Reichstein Nielsen, 2013/01/22 10:18:52]

True, so it needs a better name.
Just FixedLengthList?
FixedLengthListBase? 
I think I'll go with the latter for now.

+  void operator[]=(int index, E value);
+
+  List<E> get reversed => new ReversedList<E>(this, 0, length);
+
+  void sort([Comparator<E> compare]) {
+    coreSort(this, compare);
+  }
+
+  void setRange(int start, int length, List<E> from, [int startFrom]) {
+    if (length < 0) throw new ArgumentError("length: $length");
+    if (startFrom == null) startFrom = 0;
+    for (int i = 0; i < length; i++) {
+      this[from + i] = from[startFrom + i];
+    }
+  }
+
+  void set length(int newLength) {
+    throw new UnsupportedError(
+        "Cannot change the length of a fixed-length list");
+  }
+
+  void add(E value) {
+    throw new UnsupportedError(
+        "Cannot add to a fixed-length list");
+  }
+
+  void addLast(E value) {
+    throw new UnsupportedError(
+        "Cannot add to a fixed-length list");
+  }
+
+  void addAll(Iterable<E> iterable) {
+    throw new UnsupportedError(
+        "Cannot add to a fixed-length list");
+  }
+
+  void remove(E element) {
+    throw new UnsupportedError(
+        "Cannot remove from a fixed-length list");
+  }
+
+  void removeAll(Iterable elements) {
+    throw new UnsupportedError(
+        "Cannot remove from a fixed-length list");
+  }
+
+  void retainAll(Iterable elements) {
+    throw new UnsupportedError(
+        "Cannot remove from a fixed-length list");
+  }
+
+  void removeMatching(bool test(E element)) {
+    throw new UnsupportedError(
+        "Cannot remove from a fixed-length list");
+  }
+
+  void clear() {
+    throw new UnsupportedError(
+        "Cannot clear a fixed-length list");
+  }
+
+  E removeAt(int index) {
+    throw new UnsupportedError(
+        "Cannot remove from a fixed-length list");
+  }
+
+  E removeLast() {
+    throw new UnsupportedError(
+        "Cannot remove from a fixed-length list");
+  }
+
+  void removeRange(int start, int length) {
+    throw new UnsupportedError(
+        "Cannot remove from a fixed-length list");
+  }
+
+  void insertRange(int start, int length, [E initialValue]) {
+    throw new UnsupportedError(
+        "Cannot insert range in a fixed-length list");
+  }
+}
+
+/**
+ * An unmodifiable [List].
+ */
+abstract class UnmodifiableListMixin<E> extends BaseListMixin<E> {
 
   void operator []=(int index, E value) {
     throw new UnsupportedError(
@@ -385,7 +487,7 @@ class ListIterator<E> implements Iterator<E> {
   E get current => _current;
 }
 
-class MappedList<S, T> extends NonExtensibleListMixin<T> {
+class MappedList<S, T> extends UnmodifiableListMixin<T> {
   final List<S> _list;
   // TODO(ahe): Restore type when feature is implemented in dart2js
   // checked mode. http://dartbug.com/7733
@@ -397,10 +499,17 @@ class MappedList<S, T> extends NonExtensibleListMixin<T> {
   int get length => _list.length;
 }
 
+/** An empty fixed-length list. */
+class EmptyList<E> extends FixedLengthListMixin<E> {
+  int get length => 0;
+  E operator[](int index) { throw new ArgumentError(index); }

[floitsch, 2013/01/21 14:38:06]

RangeError

[Lasse Reichstein Nielsen, 2013/01/22 10:18:52]

Done.

+  void operator[]=(int index, E value) { throw new ArgumentError(index); }
+}
+
 /**
- * An immutable view of a [List].
+ * An unmodifiable view of a [List].
  */
-class ListView<E> extends NonExtensibleListMixin<E> {
+class ListView<E> extends UnmodifiableListMixin<E> {
   final List<E> _list;
   final int _offset;
   final int _length;
@@ -452,4 +561,98 @@ class ListView<E> extends NonExtensibleListMixin<E> {
     if (_length != null && takeCount > _length) newLength = _length;
     return new ListView(_list, _offset, newLength);
   }
+
+  List<E> get reversed => new ReversedList(_list, _offset, _offset + _length);
+
+  String toString() => Collections.collectionToString(this);
+}
+
+/**
+ * Reversed view of a [List], or a slice of a list.
+ *
+ * The view is fixed-length and becomes invalid if the underlying
+ * list changes its length below the slice used by this reversed list.

[floitsch, 2013/01/21 14:38:06]

That's now how iterables work. And ReversedList (like MappedList) shouldn't
behave this way either.
The Iterator, on the other hand, should catch length changes.

[Lasse Reichstein Nielsen, 2013/01/21 14:43:40]

So what should it do?

+ */
+class ReversedList<E> extends FixedLengthListMixin<E> {
+  final List<E> _list;
+  final int _start;
+  final int _end;
+  ReversedList(List<E> list, int start, int end)
+      : _list = list, _start = start, _end = end;
+
+  int get length => _end - _start;
+
+  E operator[](int index) {
+    if (_list.length < _end) throw new StateError("Concurrent modification");
+    int length = _end - _start;
+    if (index < 0 || index > length) {
+      throw new RangeError("$index not in range 0..$length");
+    }
+    return _list[_end - index - 1];
+  }
+
+  void operator[]=(int index, E value) {
+    if (_list.length < _end) throw new StateError("Concurrent modification");
+    int length = _end - _start;
+    if (index < 0 || index > length) {
+      throw new RangeError("$index not in range 0..$length");
+    }
+    _list[_end - index - 1] = value;
+  }
+
+  Iterable<E> get iterator => new ReverseListIterator<E>(_list, _start, _end);
+
+  List<E> take(int count) {
+    if (count is! int || count < 0) {
+      throw new ArgumentError(count);
+    }
+    int length = _end - _start;
+    if (count > length) count = length;
+    return new ReversedList(_list, _end - count, _end);
+  }
+
+  List<E> skip(int count) {
+    if (count is! int || count < 0) {
+      throw new ArgumentError(count);
+    }
+    int length = _end - _start;
+    if (count >= length) return new EmptyList();
+    return new ReversedList(_list, _start, _end - count);
+  }
+
+  void sort([int compare(E first, E second)]) {
+    if (compare == null) compare = Comparable.compare;
+    // TODO(lrn): Make a way to sort a slice of a list using core sort.
+    List<E> slice = _list.getRange(_start, _end);
+    slice.sort((E a, E b) => compare(b, a));
+    _list.setRange(_start, slice.length, slice);
+  }
+
+  List<E> get reversed {
+    return new ListView(_list, _start, _end - _start);
+  }
+
+  String toString() => Collections.collectionToString(this);
+}
+
+/**
+ * An [Iterator] over a slice of a list that access elements in reverse order.
+ */
+class ReverseListIterator<E> implements Iterator<E> {
+  final List<E> _list;
+  final int _start;
+  int _index;
+  E _current;
+
+  ReverseListIterator(List<E> list, int start, int end)
+      : _list = list, _start = start, _index = end;
+
+  bool moveNext() {
+    if (_index <= _start) return false;
+    _index -= 1;
+    _current = _list[_index];
+    return true;
+  }
+
+  E get current => _current;
 }