Changeset 1698

Timestamp:

06/30/10 02:30:26 (14 years ago)

Author:

dsimcha

Message:

Improve unittests for higher order ranges in std.algorithm, fix some unlisted bugs.

Files:

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

trunk/docsrc/changelog.dd

@@ -2 +2 @@
-
-$(D_S D Change Log,
-
-
-$(VERSION 048, Jun 11, 2010, =================================================,
-
-    $(WHATSNEW
-    $(LI std.string: icmp() now works with all built-in string types.)
-    )
-    $(BUGSFIXED
-
+
+
+
+
-    $(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 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 4363): std.algorithm.Until is not a forward range)
-    $(LI $(BUGZILLA 4406): Typo (bug) in std.concurrency)
-    )
-)
-
-<div id=version>
-$(UL
-    $(NEW 048)
-    $(NEW 047)
-    $(NEW 046)

trunk/phobos/std/algorithm.d

@@ -46 +46 @@
-module std.algorithm;
-
-import std.c.string;
-import std.array, std.container, std.contracts, std.conv, std.date,
-    std.functional, std.math, std.metastrings, std.range, std.string,
-    std.traits, std.typecons, std.typetuple;
-
-version(unittest)
-{
-    import std.random, std.stdio, std.string;
+
+    mixin(dummyRanges);
-}
-
-/**
-Implements the homonym function (also known as $(D transform)) present
-in many languages of functional flavor. The call $(D map!(fun)(range))
-returns a range of which elements are obtained by applying $(D fun(x))
-left to right for all $(D x) in $(D range). The original ranges are
-not changed. Evaluation is done lazily. The range returned by $(D map)
-caches the last value such that evaluating $(D front) multiple times
-does not result in multiple calls to $(D fun).
@@ -121 +123 @@
-    // and wasted space when 99% of the time this range will only be iterated
-    // over in the forward direction.  Use a bool to determine whether cache
-    // is front or back instead.
-        bool cacheIsBack;
-
-        private void fillCacheBack() {
-            if (!_input.empty) _cache = fun(_input.back);
-            cacheIsBack = true;
-        }
-
-
+@property 
-            if(!cacheIsBack) {
-                fillCacheBack();
-            }
-            return _cache;
-        }
-
-        void popBack() {
-            _input.popBack;
-            fillCacheBack();
-        }
@@ -161 +163 @@
-        @property bool empty() {
-            return _input.empty;
-        }
-    }
-
-    void popFront() {
-        _input.popFront;
-        fillCache;
-    }
-
-
+@property 
-        static if(isBidirectionalRange!(Range)) {
-            if(cacheIsBack) {
-                fillCache();
-            }
-        }
-        return _cache;
-    }
-
-    static if(isRandomAccessRange!Range) {
-        ElementType opIndex(size_t index) {
-            return fun(_input[index]);
-        }
-    }
-
-    // hasLength is busted, Bug 2873
-ulong
-ulong
-
+size_t
+size_t
+@property 
-            return _input.length;
-        }
-    }
-
-    static if(hasSlicing!(Range)) {
-        typeof(this) opSlice(size_t lowerBound, size_t upperBound) {
-            return typeof(this)(_input[lowerBound..upperBound]);
-        }
-    }
-
@@ -259 +261 @@
-    fibsSquares.popFront;
-    assert(fibsSquares.front == 4);
-    fibsSquares.popFront;
-    assert(fibsSquares.front == 9);
-
-    auto repeatMap = map!"a"(repeat(1));
-    static assert(isInfinite!(typeof(repeatMap)));
-
-    auto intRange = map!"a"([1,2,3]);
-    static assert(isRandomAccessRange!(typeof(intRange)));
+
+    foreach(DummyType; AllDummyRanges) {
+        DummyType d;
+        auto m = map!"a * a"(d);
+        assert(equal(m, [1,4,9,16,25,36,49,64,81,100]));
+    }
-}
-
-// reduce
-/**
-Implements the homonym function (also known as $(D accumulate), $(D
-compress), $(D inject), or $(D foldl)) present in various programming
-languages of functional flavor. The call $(D reduce!(fun)(seed,
-range)) first assigns $(D seed) to an internal variable $(D result),
-also called the accumulator. Then, for each element $(D x) in $(D
-range), $(D result = fun(result, x)) gets evaluated. Finally, $(D
@@ -600 +608 @@
-    static assert(isForwardRange!(typeof(r)));
-
-    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)));
+
+    foreach(DummyType; AllDummyRanges) {
+        DummyType d;
+        auto f = filter!"a & 1"(d);
+        assert(equal(f, [1,3,5,7,9]));
+    }
-}
-
-// 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
-also $(XREF contracts, pointsTo).
@@ -886 +900 @@
-    // foreach (x; splitter(a, 0)) {
-    //     writeln("[", x, "]");
-    // }
-    assert(equal(splitter(a, 0), w));
-    a = null;
-    assert(equal(splitter(a, 0), [ (int[]).init ][]));
-    a = [ 0 ];
-    assert(equal(splitter(a, 0), [ (int[]).init, (int[]).init ][]));
-    a = [ 0, 1 ];
-    assert(equal(splitter(a, 0), [ [], [1] ][]));
+
+//    foreach(DummyType; AllDummyRanges) {  // Bug 4408
+//        DummyType d;
+//        auto s = splitter(d, 5);
+//        assert(equal(s, [[1,2,3,4], [6,7,8,9,10]]));
+//
+//        auto s2 = splitter(d, [4, 5]);
+//        assert(equal(s2, [[1,2,3], [6,7,8,9,10]]));
+//    }
-}
-
-/**
-Splits a range using another range as a separator. This can be used
-with any range type, but is most popular with string types.
- */
-struct Splitter(Range, Separator)
-    if (is(typeof(Range.init.front == Separator.init.front)))
-{
-private:
@@ -1196 +1219 @@
-    void popFront()
-    {
-        auto last = _input.front;
-        do
-        {
-            _input.popFront;
-        }
-        while (!_input.empty && binaryFun!(pred)(last, _input.front));
-    }
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
-    }
-
-    bool empty() { return _input.empty; }
-    ElementType!(R) front() { return _input.front; }
-
+
+
+
+
+
+
-}
-
-/// Ditto
-Uniq!(pred, Range) uniq(alias pred = "a == b", Range)(Range r)
-{
-    return typeof(return)(r);
-}
-
-unittest
-{
-    int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
-    auto r = uniq(arr);
-    assert(equal(r, [ 1, 2, 3, 4, 5 ][]));
+    assert(equal(retro(r), retro([ 1, 2, 3, 4, 5 ][])));
+
+    foreach(DummyType; AllDummyRanges) {
+        DummyType d;
+        auto u = uniq(d);
+        assert(equal(u, [1,2,3,4,5,6,7,8,9,10]));
+
+        static assert(d.rt == RangeType.Input || isForwardRange!(typeof(u)));
+
+        static if(d.rt >= RangeType.Bidirectional) {
+            assert(equal(retro(u), [10,9,8,7,6,5,4,3,2,1]));
+        }
+    }
-}
-
-// group
-/**
-Similarly to $(D uniq), $(D group) iterates unique consecutive
-elements of the given range. The element type is $(D
-Tuple!(ElementType!R, uint)) because it includes the count of
-equivalent elements seen. Equivalence of elements is assessed by using
-the predicate $(D pred), by default $(D "a == b").
-
@@ -1272 +1317 @@
-            _current = tuple(_input.front, 1u);
-            _input.popFront;
-            while (!_input.empty && comp(_current.field[0], _input.front))
-            {
-                ++_current.field[1];
-                _input.popFront;
-            }
-        }
-    }
-
-
+@property 
-    {
-        return _current.field[1] == 0;
-    }
-
-
+@property 
-    {
-        assert(!empty);
-        return _current;
+    }
+
+    static if(isForwardRange!R) {
+        @property typeof(this) save() {
+            typeof(this) ret;
+            ret._input = this._input.save;
+            ret._current = this._current;
+
+            return ret;
+        }
-    }
-}
-
-/// Ditto
-Group!(pred, Range) group(alias pred = "a == b", Range)(Range r)
-{
-    return typeof(return)(r);
-}
-
-unittest
-{
-    int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
-    assert(equal(group(arr), [ tuple(1, 1u), tuple(2, 4u), tuple(3, 1u),
-                            tuple(4, 3u), tuple(5, 1u) ][]));
+
+    foreach(DummyType; AllDummyRanges) {
+        DummyType d;
+        auto g = group(d);
+
+        static assert(d.rt == RangeType.Input || isForwardRange!(typeof(g)));
+
+        assert(equal(g, [tuple(1, 1u), tuple(2, 1u), tuple(3, 1u), tuple(4, 1u),
+            tuple(5, 1u), tuple(6, 1u), tuple(7, 1u), tuple(8, 1u),
+            tuple(9, 1u), tuple(10, 1u)]));
+    }
-}
-
-// overwriteAdjacent
-/*
-Reduces $(D r) by shifting it to the left until no adjacent elements
-$(D a), $(D b) remain in $(D r) such that $(D pred(a, b)). Shifting is
-performed by evaluating $(D move(source, target)) as a primitive. The
-algorithm is stable and runs in $(BIGOH r.length) time. Returns the
-reduced range.
-

trunk/phobos/std/range.d

@@ -21 +21 @@
-module std.range;
-
-public import std.array;
-import std.contracts;
-import std.traits;
-import std.typecons;
-import std.typetuple;
-import std.algorithm;
-import std.functional;
-import std.conv;
-
-
-
-
+
+
+
+
+
-    // Used with the dummy ranges for testing higher order ranges.
-    enum RangeType {
-        Input,
-        Forward,
-        Bidirectional,
-        Random
-    }
-
-    enum Length {
-        Yes,
@@ -139 +140 @@
-        DummyRange!(ReturnBy.Value, Length.Yes, RangeType.Input),
-        DummyRange!(ReturnBy.Value, Length.Yes, RangeType.Forward),
-        DummyRange!(ReturnBy.Value, Length.Yes, RangeType.Bidirectional),
-        DummyRange!(ReturnBy.Value, Length.Yes, RangeType.Random),
-        DummyRange!(ReturnBy.Value, Length.No, RangeType.Input),
-        DummyRange!(ReturnBy.Value, Length.No, RangeType.Forward),
-        DummyRange!(ReturnBy.Value, Length.No, RangeType.Bidirectional)
-    ) AllDummyRanges;
-
-    alias TypeTuple!(1,2,3,4,5,6,7,8,9,0,11,12,13,14,15,16) DummyIndices;
+};
+
+version(unittest)
+{
+    import std.container, std.conv, std.math, std.stdio;
+
+    mixin(dummyRanges);
-}
-
-/**
-Returns $(D true) if $(D R) is an input range. An input range must
-define the primitives $(D empty), $(D popFront), and $(D front). The
-following code should compile for any input range.
-
-----
-R r;             // can define a range object
-if (r.empty) {}  // can test for empty