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

sdk/lib/core/list.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.
 
 part of dart.core;
 
 /**
  * A [List] is an indexable collection with a length. It can be of
  * fixed size or extendable.
  */
@@ skipping 67 matching lines @@
   void addLast(E value);
 
   /**
    * Appends all elements of the [iterable] to the end of this list.
    * Extends the length of the list by the number of elements in [iterable].
    * Throws an [UnsupportedError] if this list is not extensible.
    */
   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].
    * The default [List] implementations use [Comparable.compare] if
    * [compare] is omitted.
    */
   void sort([int compare(E a, E b)]);
 
   /**
    * Returns the first index of [element] in the list.
@@ skipping 87 matching lines @@
    * If [start] is the length of the list, this method inserts the
    * range at the end of the list.
    * Throws an [ArgumentError] if [length] is negative.
    * Throws an [RangeError] if [start] is negative or if
    * [start] is greater than the length of the list.
    */
   void insertRange(int start, int length, [E fill]);
 }
 
 /**
- * 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)) {
     for (int i = 0; i < this.length; i++) f(this[i]);
   }
 
   bool contains(E value) {
     for (int i = 0; i < length; i++) {
       if (this[i] == value) return true;
     }
@@ skipping 61 matching lines @@
     throw new StateError("More than one element");
   }
 
   List<E> getRange(int start, int length) {
     List<E> result = <E>[];
     for (int i = 0; i < length; i++) {
       result.add(this[start + i]);
     }
     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(
         "Cannot modify an unmodifiable list");
   }
 
   void set length(int newLength) {
     throw new UnsupportedError(
         "Cannot change the length of an unmodifiable list");
   }
@@ skipping 87 matching lines @@
       return true;
     }
     _position = _list.length;
     _current = null;
     return false;
   }
 
   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
   final /* _Transformation<S, T> */ _f;
 
   MappedList(this._list, T this._f(S element));
 
   T operator[](int index) => _f(_list[index]);
   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;
 
   /**
    * If the given length is `null` then the ListView's length is bound by
    * the backed [list].
    */
   ListView(List<E> list, this._offset, this._length) : _list = list {
     if (_offset is! int || _offset < 0) {
@@ skipping 31 matching lines @@
   }
 
   ListView<E> take(int takeCount) {
     if (takeCount is! int || takeCount < 0) {
       throw new ArgumentError(takeCount);
     }
     int newLength = takeCount;
     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;
+}