Jason House wrote:
> An earlier post showed stack with push and pop for an array.  How does one do a
> queue? a set?

A queue isn't easy because array-based queues generally need to track where the head of the queue is (that or move the rest of the queue on each pop operation), so queues really need an object wrapper to be done well.  However, storing the data in an array is still generally faster than using a linked list.  I ran a test not too long ago in Java, and an array-based queue was roughly 50% faster than a linked list-based queue for inserting and removing one million elements, and that was using a 'for' loop to copy elements during a resize operation (instead of a memcpy).  A free-list could improve average performance of a linked list implementation, but in a worst case scenario the array-based queue will still win (assuming a non-trivial allocation cost).  Sets are easily modeled as sorted arrays however.

But the real advantage of offering these algorithms apart from any specific container is that they can be applied to any sequence that supports the appropriate operations.  For example, the set intersection operation could be applied to two SQL result sets as easily as to arrays, and no copying to a Set container would be necessary.  My code currently only supports arrays, but that is mostly because there is no accepted iterator definition for D.  But this topic was discussed pretty heavily about a month ago and I may go ahead and just create one.  It's just lingering a bit low on my to-do list at the moment.

> Also, I haven't found a way to check if something is in an associative array or not.

    if( x in myAA ) {}

The 'in' operator actually returns a pointer to the value, or null if the value is not present, so a test and modify operation might do:

    if( auto t = x in myAA )
        *t = u;

> This may all boil down to me not being able to find a comprehensive list of array
> properties and/or quality documentation on the D language.

The array documentation is actually some of the best in the spec.  "in" is mentioned in the Associative Array section:

http://www.digitalmars.com/d/arrays.html#associative

But is also documented as an expression:

http://www.digitalmars.com/d/expression.html#InExpression


Sean

"Jason House" <jhouse@mitre.org> wrote in message news:elsctg$5ca$1@digitaldaemon.com...
> An earlier post showed stack with push and pop for an array.  How does one
> do a
> queue? a set?

You could also use an associative array to model a set.

bool[int] set;
set[4] = true;
set[6] = true;
set[10] = true;

if(4 in set)
    writefln("4 is in the set");

foreach(v, nothing; set)
    writefln(v);

set.remove(6);

The "nothing" in the foreach loop is because the values in the associative array are useless -- they're just there because they have to be.

In fact, why don't I just make a little set class to make it a little prettier.

class Set(T)
{
    protected bool[T] mData;

    public this()
    {

    }

    public void add(T value)
    {
        mData[value] = true;
    }

    public bool opIn_r(T value)
    {
        return ((value in mData) !is null);
    }

    public int opApply(int delegate(inout T value) dg)
    {
        int result = 0;

        foreach(value, n; mData)
        {
            result = dg(value);

            if(result)
                break;
        }

        return result;
    }

    public void remove(T value)
    {
        mData.remove(value);
    }
}

void main()
{
    auto scope set = new Set!(int);

    set.add(4);
    set.add(6);
    set.add(10);

    if(4 in set)
        writefln("4 is in the set");

    foreach(v; set)
        writefln(v);

    set.remove(6);
}

Jarrett Billingsley wrote:
> "Jason House" <jhouse@mitre.org> wrote in message news:elsctg$5ca$1@digitaldaemon.com...
>> An earlier post showed stack with push and pop for an array.  How does one do a
>> queue? a set?
> 
> You could also use an associative array to model a set.

That's the right way to go.  Using arrays for sets is going to be sllloooooow.

> bool[int] set;
> set[4] = true;
> set[6] = true;
> set[10] = true;
> 
> if(4 in set)
>     writefln("4 is in the set");
> 
> foreach(v, nothing; set)
>     writefln(v);

Or just use
foreach(v; set.keys)
   writefln(v);

> set.remove(6);
> 
> The "nothing" in the foreach loop is because the values in the associative array are useless -- they're just there because they have to be.
> 
> In fact, why don't I just make a little set class to make it a little prettier.

The only reason not would be because opApply is slower than the builtin foreach on an array.  At least for regular arrays.  Not sure if the same is true for AA's.

Also does anyone know if .keys and .values are O(1) operations?  Or do they have to allocate a new array and copy keys/values?  That could be an important thing to know.  Should be part of the spec, I think.

--bb

"Bill Baxter" <dnewsgroup@billbaxter.com> wrote in message news:elsr1j$lu0$1@digitaldaemon.com...

> Or just use
> foreach(v; set.keys)
>    writefln(v);

That prints "true true true".  :)

> The only reason not would be because opApply is slower than the builtin foreach on an array.  At least for regular arrays.  Not sure if the same is true for AA's.

I think it'd be slower for AAs too because in the class opApply function you have to use foreach on the AA that holds the data.  But really I guess it's only one method call, so it probably wouldn't be bad at all.  After all, custom implementations of opApply work virtually the same way as the built-in ones.

> Also does anyone know if .keys and .values are O(1) operations?  Or do they have to allocate a new array and copy keys/values?  That could be an important thing to know.  Should be part of the spec, I think.

They allocate new arrays.  But when you foreach an AA, it doesn't call them.

"Jarrett Billingsley" <kb3ctd2@yahoo.com> wrote in message news:elsu1f$pq5$1@digitaldaemon.com...
> "Bill Baxter" <dnewsgroup@billbaxter.com> wrote in message news:elsr1j$lu0$1@digitaldaemon.com...
>
>> Or just use
>> foreach(v; set.keys)
>>    writefln(v);
>
> That prints "true true true".  :)

Whoops, nevermind, that's right.  I missed the .keys.

Jarrett Billingsley wrote:
> "Bill Baxter" <dnewsgroup@billbaxter.com> wrote in message news:elsr1j$lu0$1@digitaldaemon.com...
> 
>> Or just use
>> foreach(v; set.keys)
>>    writefln(v);
> 
> That prints "true true true".  :)

I don't think so.   set.values would give you that.

>> The only reason not would be because opApply is slower than the builtin foreach on an array.  At least for regular arrays.  Not sure if the same is true for AA's.
> 
> I think it'd be slower for AAs too because in the class opApply function you have to use foreach on the AA that holds the data.  But really I guess it's only one method call, so it probably wouldn't be bad at all.  After all, custom implementations of opApply work virtually the same way as the built-in ones.
> 
>> Also does anyone know if .keys and .values are O(1) operations?  Or do they have to allocate a new array and copy keys/values?  That could be an important thing to know.  Should be part of the spec, I think.
> 
> They allocate new arrays.  But when you foreach an AA, it doesn't call them. 

Hmm.  Ok, so you really do want to use foreach(...; set) if at all possible.

Sure would be nice if there were a .keyiter that could be used with foreach that was efficient and didn't require allocations.

Too bad the iterator discussions fizzled out without anything getting decided.

--bb

"Bill Baxter" <dnewsgroup@billbaxter.com> wrote in message news:elsv06$r2e$1@digitaldaemon.com...

> Hmm.  Ok, so you really do want to use foreach(...; set) if at all possible.
>
> Sure would be nice if there were a .keyiter that could be used with foreach that was efficient and didn't require allocations.

Meh, I don't think the

foreach(key, ____; set)
    ...

Is that bad.  Maybe it's a little unclear, but as far as efficiency goes, it's just passing the extra unused value parameter.

> Too bad the iterator discussions fizzled out without anything getting decided.

Yeah.  We didn't start a three-week four-hundred-post thread about it, so I guess Walter didn't consider it important.

Jarrett Billingsley wrote:
> "Bill Baxter" <dnewsgroup@billbaxter.com> wrote in message news:elsv06$r2e$1@digitaldaemon.com...
> 
>> Hmm.  Ok, so you really do want to use foreach(...; set) if at all possible.
>>
>> Sure would be nice if there were a .keyiter that could be used with foreach that was efficient and didn't require allocations.
> 
> Meh, I don't think the
> 
> foreach(key, ____; set)
>     ...
> 
> Is that bad.  Maybe it's a little unclear, but as far as efficiency goes, it's just passing the extra unused value parameter.

I guess not.  Might be interesting if AA's allowed a void value type.

  void[int] myset;

Hmm... maybe not.


> 
>> Too bad the iterator discussions fizzled out without anything getting decided.
> 
> Yeah.  We didn't start a three-week four-hundred-post thread about it, so I guess Walter didn't consider it important. 

:-)  But it was almost that long wasn't it?  And Walter was one of the the ones that kicked it off, IIRC.  So I had high hopes something would come of it.

--bb

"Bill Baxter" <dnewsgroup@billbaxter.com> wrote in message news:elsvmo$rsb$1@digitaldaemon.com...

> I guess not.  Might be interesting if AA's allowed a void value type.
>
>   void[int] myset;
>
> Hmm... maybe not.

Actually, they used to, and people used them as sets :)  Of course, that was also before accessing a nonexistent AA element was an indexing error, so to add something to the set, you did

set[4] = set[4];

Which would add 4, or just be a no-op.  Now that's just plain illegal, so even if void were allowed as the value type, there'd be no way to add anything to the set.  Besides, what does void[int] mean?  (then again you can have a void[], which is also kind of weird, but..).

> :-)  But it was almost that long wasn't it?  And Walter was one of the the ones that kicked it off, IIRC.  So I had high hopes something would come of it.

I don't know.  Maybe we didn't say the right things.

Bill Baxter wrote:
> 
> Too bad the iterator discussions fizzled out without anything getting decided.

I think the design was pretty well settled when things ended.  The next step would be a sample implementation so folks could wrangle over syntax.  It's on my "to do" list, but I'm a bit short on free time at the moment.


Sean