Hi,

Anyone know of any existing template container classes for either a queue or a circular buffer? Basically I just want something with functions:

void put(T)
T get()

which get()s previously put() stuff in FIFO order. Circular buffers are usually
fixed size (so it's possible to overflow and throw an exception), queues tend to
grow as required (but they can still underflow if you give it more get()s than
put()s). Other than that they're the same thing.

It would be almost trivial to write such a beast, but there doesn't seem much point in my writing one if someone else has done it first and made it public. So, any pointers?

Arcane Jill

Arcane Jill wrote:

> Hi,
> 
> Anyone know of any existing template container classes for either a queue or a circular buffer? Basically I just want something with functions:
> 
> void put(T)
> T get()
> 
> which get()s previously put() stuff in FIFO order. Circular buffers are
> usually fixed size (so it's possible to overflow and throw an exception),
> queues tend to grow as required (but they can still underflow if you give
> it more get()s than put()s). Other than that they're the same thing.
> 
> It would be almost trivial to write such a beast, but there doesn't seem much point in my writing one if someone else has done it first and made it public. So, any pointers?
> 
> Arcane Jill

a while ago I wrote up one that resizes:
 http://home.comcast.net/~benhinkle/deque.d

There's one in DTL. It'll be available ~7th July

"Arcane Jill" <Arcane_member@pathlink.com> wrote in message news:camq4j$1s4l$1@digitaldaemon.com...
> Hi,
>
> Anyone know of any existing template container classes for either a queue or a circular buffer? Basically I just want something with functions:
>
> void put(T)
> T get()
>
> which get()s previously put() stuff in FIFO order. Circular buffers are usually
> fixed size (so it's possible to overflow and throw an exception), queues tend
to
> grow as required (but they can still underflow if you give it more get()s than
> put()s). Other than that they're the same thing.
>
> It would be almost trivial to write such a beast, but there doesn't seem much point in my writing one if someone else has done it first and made it public. So, any pointers?
>
> Arcane Jill
>
>

In article <camtn6$21fv$1@digitaldaemon.com>, Matthew says...
>
>There's one in DTL. It'll be available ~7th July


Excellent news!

Although I don't actually need one now, as I just wrote one. (I work fast). Trivially simple in D, of course.

But I am very glad to hear that D is about to get its own "standard template library", so that we don't have to keep reinventing the wheel. (Not that reinventing the wheel is particularly hard in D, of course). I look forward to release date, when I shall switch from my implementation to yours.

Arcane Jill


>class SimpleQueue(T)
>{
>    this(uint n=16)
>    {
>        q.length = avail = n;
>    }
> 
>    void put(T a)
>    {
>        if (avail == 0)
>        {
>            T[] t;
>            t.length = q.length + q.length;
>            t[0..q.length-getIndex] = q[getIndex..q.length];
>            if (getIndex != 0) t[q.length-getIndex..q.length] = q[0..getIndex];
>            getIndex = 0;
>            putIndex = avail = q.length;
>            q = t;
>        }
>        q[putIndex++] = a;
>        --avail;
>        if (putIndex == q.length) putIndex = 0;
>    }
> 
>    T get()
>    {
>        if (avail == q.length)
>        {
>            throw new Error("Queue underflow");
>        }
>        T t = q[getIndex++];
>        ++avail;
>        if (getIndex == q.length) getIndex = 0;
>        return t;
>    }
>
>    uint length()
>    {
>        return q.length - avail;
>    }
>
>    private T[] q;
>    private uint getIndex;
>    private uint putIndex;
>    private uint avail;
>}
>
>int main()
>{
>    SimpleQueue!(uint) q = new SimpleQueue!(uint)();
>    for (uint i=0; i<20; ++i)
>    {
>        q.put(i);
>    }
>    for (uint i=0; i<30; ++i)
>    {
>        printf("%d\n", q.get());
>    }
>    return 0;
>}

Arcane Jill wrote:

<snip>
> which get()s previously put() stuff in FIFO order. Circular buffers are usually
> fixed size (so it's possible to overflow and throw an exception), queues tend to
> grow as required (but they can still underflow if you give it more get()s than
> put()s). Other than that they're the same thing.

Circular buffers are one typical way of implementing queues.  They can be designed to grow as required, which would mean less moving data around than a linear queue imp while still having theoretically unlimited capacity.

Stewart.

-- 
My e-mail is valid but not my primary mailbox, aside from its being the unfortunate victim of intensive mail-bombing at the moment.  Please keep replies on the 'group where everyone may benefit.