Changeset 1702

Timestamp:

07/01/10 02:24:58 (14 years ago)

Author:

dsimcha

Message:

Bug 3872: std.algorithm.filter could become bidirectional if its input range is bidir

Files:

• trunk/docsrc/changelog.dd (modified) (1 diff)
• trunk/phobos/std/algorithm.d (modified) (3 diffs)

trunk/docsrc/changelog.dd

@@ -16 +16 @@
-    $(LI $(BUGZILLA 978): std.utf's toUTF* functions accept some invalid and reject some valid UTF)
-    $(LI $(BUGZILLA 996): Error in doc on implicit conversion between pointer and array)
-    $(LI $(BUGZILLA 2275): std.utf.toUTF16z() should return const(wchar)*)
-    $(LI $(BUGZILLA 2872): Length, opIndex for Map)
-    $(LI $(BUGZILLA 3202): std.math.pow cause dead loop)
-    $(LI $(BUGZILLA 3355): std.string.cmp works incorrectly for mixed-type and different-length strings)
-    $(LI $(BUGZILLA 3386): to!bool(string) is not implemented)
-    $(LI $(BUGZILLA 3436): std.functional.compose with only one function)
-    $(LI $(BUGZILLA 3439): std.range.Sequence.opIndex not consistent after calling popFront().)
-    $(LI $(BUGZILLA 3447): std.file uses unconventional file permissions)
+    $(LI $(BUGZILLA 3872): std.algorithm.filter could become bidirectional if its input range is bidir)
-    $(LI $(BUGZILLA 3874): std.range.stride assumes a bidirectional input range)
-    $(LI $(BUGZILLA 3937): os.path.dirname fails on absolute path)
-    $(LI $(BUGZILLA 3961): Error with to!(somestruct))
-    $(LI $(BUGZILLA 4109): (reopened) writeln doesn't work with empty static array)
-    $(LI $(BUGZILLA 4171): std.random.uniform does not work for a range of characters)
-    $(LI $(BUGZILLA 4260): windows & basename)
-    $(LI $(BUGZILLA 4305): Take, Chain on top of ranges w/o moveFront() )
-    $(LI $(BUGZILLA 4327): std.container.Array.Range.~this() tries to call free(T[]))
-    $(LI $(BUGZILLA 4362): std.range.repeat and cycle do not have a .save() method)
-    $(LI $(BUGZILLA 4363): std.algorithm.Until is not a forward range)

trunk/phobos/std/algorithm.d

@@ -558 +558 @@
-}
-
-struct Filter(alias pred, Range) if (isInputRange!(Range))
-{
-    Range _input;
-
-    this(Range r)
-    {
-        _input = r;
-        while (!_input.empty && !pred(_input.front)) _input.popFront;
+        static if (isBidirectionalRange!Range) {
+            while (!_input.empty && !pred(_input.back)) _input.popBack;
+        }
+
-    }
-
-    ref Filter opSlice()
-    {
-        return this;
-    }
-
-    static if(isInfinite!Range) {
-        enum bool empty = false;
-    } else {
@@ -584 +588 @@
-        {
-            _input.popFront;
-        } while (!_input.empty && !pred(_input.front));
-    }
-
-    ElementType!(Range) front()
-    {
-        return _input.front;
-    }
-
+    static if (isBidirectionalRange!Range) {
+        void popBack()
+        {
+            do
+            {
+                _input.popBack;
+            } while (!_input.empty && !pred(_input.back));
+        }
+
+        ElementType!(Range) back() { return _input.back;}
+    }
+
+
-    static if(isForwardRange!Range)
-    {
-        @property typeof(this) save()
-        {
-            return typeof(this)(_input.save);
-        }
-    }
-}
-
-unittest
@@ -609 +626 @@
-
-    a = [ 1, 22, 3, 42, 5 ];
-    auto under10 = filter!("a < 10")(a);
-    assert(equal(under10, [1, 3, 5][]));
-    static assert(isForwardRange!(typeof(under10)));
-
-    auto infinite = filter!"a > 2"(repeat(3));
-    static assert(isInfinite!(typeof(infinite)));
-    static assert(isForwardRange!(typeof(infinite)));
-
+    auto nums = [0,1,2,3,4];
+    auto forward = filter!"a % 2 == 0"(nums);
+    assert(equal(retro(forward), [4,2,0][])); // f is a bidirectional range
+
+
-    foreach(DummyType; AllDummyRanges) {
-        DummyType d;
-        auto f = filter!"a & 1"(d);
-        assert(equal(f, [1,3,5,7,9]));
+
+        static if(isForwardRange!DummyType) {
+            static assert(isForwardRange!(typeof(f)));
+        }
+
+        static if(isBidirectionalRange!DummyType) {
+            static assert(isBidirectionalRange!(typeof(f)));
+            assert(equal(retro(f), [9,7,5,3,1]));
+        }
-    }
-}
-
-// move
-/**
-Moves $(D source) into $(D target) via a destructive
-copy. Specifically: $(UL $(LI If $(D hasAliasing!T) is true (see
-$(XREF traits, hasAliasing)), then the representation of $(D source)
-is bitwise copied into $(D target) and then $(D source = T.init) is
-evaluated.)  $(LI Otherwise, $(D target = source) is evaluated.)) See