www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 3876] New: std.range.Take back/popBack methods don't work correctly

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=3876

           Summary: std.range.Take back/popBack methods don't work
                    correctly
           Product: D
           Version: 2.040
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Phobos
        AssignedTo: nobody puremagic.com
        ReportedBy: philippe.sigaud gmail.com


--- Comment #0 from Philippe Sigaud <philippe.sigaud gmail.com> 2010-03-04
15:24:27 CET ---
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; }
}
----

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Mar 04 2010
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=3876


Shin Fujishiro <rsinfu gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
                 CC|                            |rsinfu gmail.com
         AssignedTo|nobody puremagic.com        |rsinfu gmail.com


-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
May 29 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=3876


Shin Fujishiro <rsinfu gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED


--- Comment #1 from Shin Fujishiro <rsinfu gmail.com> 2010-05-29 06:52:12 PDT
---
Fixed in svn r1566.  Thanks for the code!  It was very helpful.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
May 29 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=3876


Andrei Alexandrescu <andrei metalanguage.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |REOPENED
                 CC|                            |andrei metalanguage.com
         Resolution|FIXED                       |


--- Comment #2 from Andrei Alexandrescu <andrei metalanguage.com> 2010-05-29
06:59:09 PDT ---
The constructor is now O(n), which is unacceptable.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
May 29 2010
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=3876


Shin Fujishiro <rsinfu gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|REOPENED                    |RESOLVED
         Resolution|                            |FIXED


--- Comment #3 from Shin Fujishiro <rsinfu gmail.com> 2010-06-13 15:48:47 PDT
---
The O(n) constructor was removed.  Fixed in the release 2.047.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jun 13 2010