D issues are now tracked on GitHub. This Bugzilla instance remains as a read-only archive.
Issue 3876 - std.range.Take back/popBack methods don't work correctly
Summary: std.range.Take back/popBack methods don't work correctly
Status: RESOLVED FIXED
Alias: None
Product: D
Classification: Unclassified
Component: phobos (show other issues)
Version: D2
Hardware: All All
: P2 normal
Assignee: Shin Fujishiro
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2010-03-04 06:24 UTC by Philippe Sigaud
Modified: 2015-06-09 01:27 UTC (History)
2 users (show)

See Also:


Attachments

Note You need to log in before you can comment on or make changes to this issue.
Description Philippe Sigaud 2010-03-04 06:24:27 UTC
std.range.Take back and popBack methods do not work correctly:

----
import std.range;

void main() {
    auto r = [0,1,2,3,4];
    auto t = take(3,r);

    assert(equal(t, [0,1,2][])); // OK.

    assert(equal(retro(t), [4,3,2,1,1,0,0][])); // Something is wrong.
}
----


Here is a version that seems to work, though the code may not be as clean as it should (and Take's code wasn't pretty to begin with...)
It demands rather strict conditions on the input range: back/popBack need a random-access range with a length. 

----
struct Take(R) if (isInputRange!(R))
{
private:
    size_t _maxAvailable;
    R _input;
    enum bool byRef = is(typeof(&(R.init[0])));

public:
    alias R Source;

    static if (byRef)
        alias ref .ElementType!(R) ElementType;
    else
        alias .ElementType!(R) ElementType;

    bool empty()
    {
        return _maxAvailable == 0 || _input.empty;
    }

    void popFront()
    {
        enforce(_maxAvailable > 0);
        _input.popFront;
        --_maxAvailable;
    }

    // @@@@@@@@@@@ UGLY @@@@@@@@@@@@@@@
    mixin(
        (byRef ? "ref " : "")~
        q{ElementType front()
        {
            enforce(_maxAvailable > 0);
            return _input.front;
        }});

    static if (isInfinite!(R))
    {
        size_t length() const
        {
            return _maxAvailable;
        }

        void popBack()
        {
            enforce(_maxAvailable);
            --_maxAvailable;
        }
    }
    else static if (hasLength!(R))
    {
        size_t length()
        {
            return min(_maxAvailable, _input.length);
        }

        static if (isRandomAccessRange!(R))
        {
            void popBack()
            {
                if (_maxAvailable < _input.length) // changed from > to <
                {
                    --_maxAvailable;
                }
                else
                {
                    _input.popBack;
                }
            }
        }
    }

    static if (isRandomAccessRange!(R))
    {
        mixin(
            (byRef ? "ref " : "")~
            q{ElementType opIndex(uint index)
                {
                    enforce(_maxAvailable > index);
                    return _input[index];
                }
            });
    }

/+    static if (isBidirectionalRange!(R))
    {
        mixin(
            (byRef ? "ref " : "")~
            q{ElementType back()
                {
                    return _input[_maxAvailable];
                }
            });
    }
    else+/ static if (isRandomAccessRange!(R) /+&& isInfinite!(R)+/)
    {
        // Random access but not bidirectional could happen in the
        // case of e.g. some infinite ranges
        mixin(
            (byRef ? "ref " : "")~
            q{ElementType back()
                {
                    return _input[this.length() - 1];
                }
            });
    }

    Take opSlice() { return this; }
}
----
Comment 1 Shin Fujishiro 2010-05-29 06:52:12 UTC
Fixed in svn r1566.  Thanks for the code!  It was very helpful.
Comment 2 Andrei Alexandrescu 2010-05-29 06:59:09 UTC
The constructor is now O(n), which is unacceptable.
Comment 3 Shin Fujishiro 2010-06-13 15:48:47 UTC
The O(n) constructor was removed.  Fixed in the release 2.047.