www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - std.container: SList linearRemove confusion

reply Johannes Pfau <spam example.com> writes:
Hi,
I'm currently trying to replace the array in my signal implementation
with the SList from std.container. I need to remove elements from the
list, but I can't seem to get it right.
According to the documentation, I expect linearRemove to remove the
contents of the passed range, but linearRemove always removes all
elements in the range and _after the range_ .
For linearRemove(Range r) it seems to be expected? At least the code
obviously behaves like that:
http://www.dsource.org/projects/phobos/browser/trunk/phobos/std/container.d#L1251
-------------------------------------------------------------------------
auto n = findNode(_root, r._head); //find beginning of range in list
n._next = null;               //ignore all elements after that element
return Range(null);
-------------------------------------------------------------------------
Is this really the expected behavior for linearRemove?

The linearRemove(Take!Range r) version doesn't work either, but this
time I'm sure it's a bug: it seems to happen if I use a Take!Range with
the first element being the SList root node. looking at the code:
http://www.dsource.org/projects/phobos/browser/trunk/phobos/std/container.d#L1270
-------------------------------------------------------------------------
Range linearRemove(Take!Range r)
{
    auto orig = r.original;
    // We have something to remove here
    if (orig._head == _root)
    {
        // remove straight from the head of the list
        for (; !orig.empty; orig.popFront())          <----- _why
orig.empty and orig.popFront? should be r.empty and r.popFront_
        {
            removeFront();
        }
        return this[];
    }
    [...]
}
-------------------------------------------------------------------------
Testcase
-------------------------------------------------------------------------
import std.container;
import std.range;
import std.algorithm;

void main()
{
    auto s = SList!int(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
    auto r = s[];
    auto r1 = take(r, 4);
    assert(equal(r1, [1, 2, 3, 4]));
    auto r2 = s.linearRemove(r1);
    assert(s == SList!int()); //passes - should fail!
    assert(s == SList!int(5, 6, 7, 8, 9, 10)); //fails
}
-------------------------------------------------------------------------

I guess I should file a bug report, but this really is a showstopper for
me. Is there any way to get this fixed faster? The fix is really trivial.

-- 
Johannes Pfau
Oct 07 2010
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 07 Oct 2010 12:44:48 -0400, Johannes Pfau <spam example.com> wrote:


 Hi,
 I'm currently trying to replace the array in my signal implementation
 with the SList from std.container. I need to remove elements from the
 list, but I can't seem to get it right.
 According to the documentation, I expect linearRemove to remove the
 contents of the passed range, but linearRemove always removes all
 elements in the range and _after the range_ .
 For linearRemove(Range r) it seems to be expected? At least the code
 obviously behaves like that:
 http://www.dsource.org/projects/phobos/browser/trunk/phobos/std/container.d#L1251
 -------------------------------------------------------------------------
 auto n = findNode(_root, r._head); //find beginning of range in list
 n._next = null;               //ignore all elements after that element
 return Range(null);
 -------------------------------------------------------------------------
 Is this really the expected behavior for linearRemove?


Yes, an SList range is terminated by a null pointer, so there is no limit  
to how far it will iterate.

Try to construct an SList range (without using Take) that doesn't iterate  
the rest of the list.


 The linearRemove(Take!Range r) version doesn't work either, but this
 time I'm sure it's a bug: it seems to happen if I use a Take!Range with
 the first element being the SList root node. looking at the code:
 http://www.dsource.org/projects/phobos/browser/trunk/phobos/std/container.d#L1270
 -------------------------------------------------------------------------
 Range linearRemove(Take!Range r)
 {
     auto orig = r.original;
     // We have something to remove here
     if (orig._head == _root)
     {
         // remove straight from the head of the list
         for (; !orig.empty; orig.popFront())          <----- _why
 orig.empty and orig.popFront? should be r.empty and r.popFront_
         {
             removeFront();
         }
         return this[];
     }
     [...]
 }


Yes, I think you are right.


 I guess I should file a bug report, but this really is a showstopper for
 me. Is there any way to get this fixed faster? The fix is really trivial.


Yes, fix it in your local copy :)  It is a seldom used construct, so there  
should be no real compiled code in Phobos that will be affected.  Just  
change the source and everything will be good.

But do also file a bug please.

-Steve
Oct 07 2010
parent Johannes Pfau <spam example.com> writes:
On 07.10.2010 19:09, Steven Schveighoffer wrote:

 On Thu, 07 Oct 2010 12:44:48 -0400, Johannes Pfau <spam example.com> wrote:

 Is this really the expected behavior for linearRemove?


 
 Yes, an SList range is terminated by a null pointer, so there is no
 limit to how far it will iterate.
 
 Try to construct an SList range (without using Take) that doesn't
 iterate the rest of the list.


OK, that makes sense.

 
 Yes, fix it in your local copy :)  It is a seldom used construct, so
 there should be no real compiled code in Phobos that will be affected. 
 Just change the source and everything will be good.


OK I've done that. works great now.

 But do also file a bug please.


Done: http://d.puremagic.com/issues/show_bug.cgi?id=5011

 -Steve


Thanks for your help!
-- 
Johannes Pfau
Oct 07 2010