Hi!
I'm looking for a queue class in squeak. The only class I found is SharedQueue. But I don't need synchronization. Sure, if there is really none I could write one in minutes. But I wonder if it makes sense to add such an elementary data structure to the base collection stuff.
Martin
An OrderedCollection with addLast/removeFirst will usually do just fine. If you're unsure about performance, LinkedList might help.
But it turns out in my experience, that everywhere I want a queue I want a separate process to munch through the queue anyway so I hardly ever use anything but SharedQueue (or SharedStream, Goran ;-)).
On 11/3/05, Martin Kuball martinkuball@web.de wrote:
I'm looking for a queue class in squeak. The only class I found is SharedQueue. But I don't need synchronization. Sure, if there is really none I could write one in minutes. But I wonder if it makes sense to add such an elementary data structure to the base collection stuff.
What about OrderedCollection? It has the methods #removeFirst and#addLast:, which should be all you need for a queue.
Or, if you prefer, #addFirst: and #removeLast :-)
Josh
On Nov 3, 2005, at 12:12 PM, Martin Kuball wrote:
Hi!
I'm looking for a queue class in squeak. The only class I found is SharedQueue. But I don't need synchronization. Sure, if there is really none I could write one in minutes. But I wonder if it makes sense to add such an elementary data structure to the base collection stuff.
Martin
It still doesn't have the right performance characteristics for a Queue: growing at one end and hopefully then shrinking at the other end isn't as useful as trying to hold on to the same size Array contents and shifting the contents around as needed or using loop- around first-index and last-index semantics. Slate has such a version in src/lib/queue.slate which could probably be ported back pretty easily. We also have a derived RingBuffer which "eats" one end when the other end expands too much - useful in some limited circumstances.
On Nov 3, 2005, at 12:24 PM, Josh Gargus wrote:
What about OrderedCollection? It has the methods #removeFirst and#addLast:, which should be all you need for a queue.
Or, if you prefer, #addFirst: and #removeLast :-)
Josh
On Nov 3, 2005, at 12:12 PM, Martin Kuball wrote:
Hi!
I'm looking for a queue class in squeak. The only class I found is SharedQueue. But I don't need synchronization. Sure, if there is really none I could write one in minutes. But I wonder if it makes sense to add such an elementary data structure to the base collection stuff.
Martin
-- -Brian
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
Martin Kuball wrote:
Hi!
I'm looking for a queue class in squeak. The only class I found is SharedQueue. But I don't need synchronization. Sure, if there is really none I could write one in minutes. But I wonder if it makes sense to add such an elementary data structure to the base collection stuff.
Martin
Hi,
Two years ago I needed a linked list whose operations for adding and removing elements have O(1) time complexity. LinkedList, unfortunatelly, is not the case.
I have implemented its bidirectional variant. It is package as `BidirectionalLinkedList' and available on SqueakMap.
I have tested it and used it a lot. It has similar disadvantages as LinkedList. Only elements subclassed from `BidirectionalLink' could be part of the list. This, in case of single inheritance, may be very uncomfortable. But in my cases it was no problem.
(of course, it is not "thread-safe")
Maybe you will find it useful.
Regards - -- Matej Košík
Am Thursday, 3. November 2005 22:15 schrieb Matej Košík:
Martin Kuball wrote:
Hi!
I'm looking for a queue class in squeak. The only class I found is SharedQueue. But I don't need synchronization. Sure, if there is really none I could write one in minutes. But I wonder if it makes sense to add such an elementary data structure to the base collection stuff.
Martin
Hi,
Two years ago I needed a linked list whose operations for adding and removing elements have O(1) time complexity. LinkedList, unfortunatelly, is not the case.
I have implemented its bidirectional variant. It is package as `BidirectionalLinkedList' and available on SqueakMap.
I have tested it and used it a lot. It has similar disadvantages as LinkedList. Only elements subclassed from `BidirectionalLink' could be part of the list. This, in case of single inheritance, may be very uncomfortable. But in my cases it was no problem.
(of course, it is not "thread-safe")
Maybe you will find it useful.
Thanks for your answers. I implementend a quick hack based on Linked List. But given the fact the performance ist not an issue for me, using OrderedCollection might be worth a try.
Martin
squeak-dev@lists.squeakfoundation.org
-
Brian Rice -
Cees De Groot -
Josh Gargus -
Martin Kuball -
Matej Košík