A new linked list module has been released at http://www.dprogramming.com/list.php
You may be wondering why another linked list; check out the FAQ to see!

Chris Miller schrieb:
> A new linked list module has been released at
> http://www.dprogramming.com/list.php
> You may be wondering why another linked list; check out the FAQ to see!

Chris, thanks for your work and that you give it to the community.

I see you use the mixin feature for this list.
Actually there is bug #106.
http://d.puremagic.com/bugzilla/show_bug.cgi?id=106

If the project grows, one will sooner or later get this error, which
will block your further development.
The mixin feature is only save, if you have the declaration and the
instantiation in the same file.

Chris Miller wrote:
> A new linked list module has been released at http://www.dprogramming.com/list.php
> You may be wondering why another linked list; check out the FAQ to see!

Very cool.  One thing... does this work:

    foreach( Person p; per.each )
    {
        if( p.age > 50 )
            p.listRemove();
    }

ie. can you remove elements within a foreach?


Sean

Sean Kelly wrote:
> Very cool.  One thing... does this work:
> 
>     foreach( Person p; per.each )
>     {
>         if( p.age > 50 )
>             p.listRemove();
>     }
> 
> ie. can you remove elements within a foreach?

It's undefined behavior. foreach is entitled to assume that the aggregate is a loop invariant, although the contents of the aggregate's elements can change. This precludes things like resizing an array inside a foreach, etc.

Walter Bright wrote:
> Sean Kelly wrote:
>> Very cool.  One thing... does this work:
>>
>>     foreach( Person p; per.each )
>>     {
>>         if( p.age > 50 )
>>             p.listRemove();
>>     }
>>
>> ie. can you remove elements within a foreach?
> 
> It's undefined behavior. foreach is entitled to assume that the aggregate is a loop invariant, although the contents of the aggregate's elements can change. This precludes things like resizing an array inside a foreach, etc.

Even for a class that defines an opApply?  What about an alternate syntax:

    foreach( Person p; personList )
    {
        if( p.age > 50 )
            personList.remove( p );
    }

Assuming the list code supports this operation (say the 'next' pointer isn't set to null when p is removed, and thus the iteration should continue without any problems), is the behavior still undefined?  If so, I assume it would be okay to store a list of 'removed' items until the iteration ends and them remove them all at once?


Sean

Sean Kelly wrote:
> Walter Bright wrote:
>> Sean Kelly wrote:
>>> Very cool.  One thing... does this work:
>>>
>>>     foreach( Person p; per.each )
>>>     {
>>>         if( p.age > 50 )
>>>             p.listRemove();
>>>     }
>>>
>>> ie. can you remove elements within a foreach?
>>
>> It's undefined behavior. foreach is entitled to assume that the aggregate is a loop invariant, although the contents of the aggregate's elements can change. This precludes things like resizing an array inside a foreach, etc.
> 
> Even for a class that defines an opApply?

Yes. The idea is to apply uniform semantics.

> What about an alternate syntax:
> 
>     foreach( Person p; personList )
>     {
>         if( p.age > 50 )
>             personList.remove( p );
>     }
> 
> Assuming the list code supports this operation (say the 'next' pointer isn't set to null when p is removed, and thus the iteration should continue without any problems), is the behavior still undefined?

Yes.

> If so, I assume it would be okay to store a list of 'removed' items until the iteration ends and them remove them all at once?

Yes.

It seems that this kind of use of mixins make the term "mixin" inappropriate: it looks like traits (as on http://www.iam.unibe.ch/~scg/Research/Traits/). A class has two competing role: being a mold to generate instances and being a mean of code reuse. The first goal lead to full featured classes, the second to small sized ones, wich turns to be paradoxal. Traits give a way to address this problem.

Not that in object engineering litterature, a mixin class is a parameterized
subclass. It can be used to implement some features of aspect oriented
programming.
Mixin classes semantics in D would be :

template MixinClass ( T )
{
class MyClass : T
{
this () { super (); }

void foo () { super (); doSomethingMore (); }

void doSomethingMore () { addFeatures (); }
}
}

Mixin classes can create conflicts ( methods having the same signatures ) when they are composed together. Using named mixins, we can select wich implementation to use but it would be more interesting to make mixins inherit from the other composed mixins. As the current scope has precedence over the mixin code we could do something like ( I never tested it ):

class MyMixedInClass
{
mixin MyClass first ;
mixin MyClass2 second ;

void doSomethingMore ()
{
second.doSomethingMore (); // Select the priority between mixins.
first.doSomethingMore ();
}
}

Or we could make a feature request to have built in mixin classes, something
like :
mixin class ToBeComposed ( S /* superclass */, /* template params */ ...  )
{
void feature () { ... }
}

class Composit
{
mixin !( T ) ToBeComposed ;
mixin OtherMixinClass ;

void feature ()
{ mixin ToBeComposed, OtherMixinClass ; // set mixin precedence.
}
}

The syntax has to be improved but it seems that D has all the features to make that kind of syntactic sugar.

BTW, this linked list is a great idea.

On Thu, 11 May 2006 15:06:23 -0400, Walter Bright <newshound@digitalmars.com> wrote:

> Sean Kelly wrote:
>> Walter Bright wrote:
>>> Sean Kelly wrote:
>>>> Very cool.  One thing... does this work:
>>>>
>>>>     foreach( Person p; per.each )
>>>>     {
>>>>         if( p.age > 50 )
>>>>             p.listRemove();
>>>>     }
>>>>
>>>> ie. can you remove elements within a foreach?
>>>
>>> It's undefined behavior. foreach is entitled to assume that the aggregate is a loop invariant, although the contents of the aggregate's elements can change. This precludes things like resizing an array inside a foreach, etc.
>>  Even for a class that defines an opApply?
>
> Yes. The idea is to apply uniform semantics.

Makes sense. Perhaps I should add a filter() function that calls back a delegate for each item and allows you to remove items safely.

Walter Bright wrote:
> Sean Kelly wrote:
>> Walter Bright wrote:
>>> Sean Kelly wrote:
>>>> Very cool.  One thing... does this work:
>>>>
>>>>     foreach( Person p; per.each )
>>>>     {
>>>>         if( p.age > 50 )
>>>>             p.listRemove();
>>>>     }
>>>>
>>>> ie. can you remove elements within a foreach?
>>>
>>> It's undefined behavior. foreach is entitled to assume that the aggregate is a loop invariant, although the contents of the aggregate's elements can change. This precludes things like resizing an array inside a foreach, etc.
>>
>> Even for a class that defines an opApply?
> 
> Yes. The idea is to apply uniform semantics.

Understandable.

>> What about an alternate syntax:
>>
>>     foreach( Person p; personList )
>>     {
>>         if( p.age > 50 )
>>             personList.remove( p );
>>     }
>>
>> Assuming the list code supports this operation (say the 'next' pointer isn't set to null when p is removed, and thus the iteration should continue without any problems), is the behavior still undefined?
> 
> Yes.

*sigh*  I can see the reason for this, but it dramatically reduces the utility of foreach for me, as it's a very common idiom to want to remove elements during an iteration.  In fact, I already use this technique quite a bit in Thread and ThreadGroup.  That aside, does this restriction also exist for processing AA elements?  I ask because this is done on a dynamically allocated list of references rather than against the AA itself, though I suppose that's implementation defined.

>> If so, I assume it would be okay to store a list of 'removed' items until the iteration ends and them remove them all at once?
> 
> Yes.

Thanks.  Assuming I did this, would it be technically legal to destroy this list after the iteration ends but before opApply returns? Otherwise, I'm not entirely certain how to go about processing the removals.


Sean

Sean Kelly wrote:
> *sigh*  I can see the reason for this, but it dramatically reduces the utility of foreach for me, as it's a very common idiom to want to remove elements during an iteration.  In fact, I already use this technique quite a bit in Thread and ThreadGroup.  That aside, does this restriction also exist for processing AA elements?

Yes - everything used as an aggregate in a foreach.

> I ask because this is done on a dynamically allocated list of references rather than against the AA itself, though I suppose that's implementation defined.

The idea is to enable the compiler to do aggressive loop optimizations, regardless of the aggregate type used, and regardless of whether it is user-defined or built-in.

>>> If so, I assume it would be okay to store a list of 'removed' items until the iteration ends and them remove them all at once?
>>
>> Yes.
> 
> Thanks.  Assuming I did this, would it be technically legal to destroy this list after the iteration ends but before opApply returns? Otherwise, I'm not entirely certain how to go about processing the removals.

I'm a bit reluctant to say yes on that, worrying that I'm forgetting something. What you can do is not use foreach, but just a for loop.