• Arcane Jill (13/13) Jun 15 2004 Hi,
• Ben Hinkle (3/21) Jun 15 2004 a while ago I wrote up one that resizes:
• Matthew (4/17) Jun 15 2004 There's one in DTL. It'll be available ~7th July
• Arcane Jill (9/67) Jun 15 2004 Excellent news!
• Stewart Gordon (11/15) Jun 15 2004 Circular buffers are one typical way of implementing queues. They can

Arcane Jill <Arcane_member pathlink.com> writes:

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

Ben Hinkle <bhinkle4 juno.com> writes:

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

"Matthew" <admin stlsoft.dot.dot.dot.dot.org> writes:

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

Arcane Jill <Arcane_member pathlink.com> writes:

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;
}

Stewart Gordon <smjg_1998 yahoo.com> writes:

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.