www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Need a queue - any out there or should I roll my own?

reply 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
Jun 15 2004
next sibling parent 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
Jun 15 2004
prev sibling next sibling parent reply "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

 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

Jun 15 2004
parent 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;
}

Jun 15 2004
prev sibling parent 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.
Jun 15 2004