Fun and games with EsQueue

[daswartz]

I needed a FIFO queue for an algorithm the other day. I was going to use a ReadWriteStream, but a ReadWriteStream doesn't know how many objects it contains, so a queue object of some sort seemed like the perfect choice.

So I used an EsQueue. Because the number of objects the queue would hold will vary, I used ##new: to instantiate the queue. And, I ran into a nasty little anomaly when I happened to create an instance with a size of 1.

(Yes, I know EsQueue isn't marked as a public class, but why would I want to write a queue class, when one already exists in the image?)

Try the following code:

Code: Select all

|q|
q := EsQueue new: 1.
q add: 1.
q remove.
q add: 2.
q remove.

You would expect the second ##remove to return the Integer 2, but instead it returns nil. In fact,

Code: Select all

|q|
q := EsQueue new: 1.
q add: 1.
q add: 2.
q remove.
q remove.
q remove.
q remove.

returns nil from the 2nd, 3rd, and fourth invocations of #remove.

Instantiating with "EsQueue new" or any other positive integer valued size returns the expected value
and raises a "queue is empty" exception when you try to remove more objects than were put on
the queue.

Commenting out the primitives in ##add: and ##remove and stepping through, the problem appears
to be that ##grow doesn't actually grow a queue instantiated as size one, and unlike the smalltalk
source, the primitives don't raise an exception when attempting to add an object past the end of the
contents variable.

The simplest fix appears to be to change EsQueue>>size:

Code: Select all

size: size

   "Initialize the instance variables of the receiver."

   head := tail := 1.
   contents := Array new: (size max: 2)

This problem exists in, at least, versions 7.0.1 through the version 8 beta.

Doug Swartz

[Bob Whitefield]

Doug, why not use OrderedCollection to implement queues and stacks? Use removeFirst to remove elements in FIFO order, removeLast for LIFO:

Code: Select all

queue := OrderedCollection new.
queue
   add: #first;
   add: #second;
   add: #third.

Transcript cr; show: queue removeFirst.
Transcript cr; show: queue removeFirst.
Transcript cr; show: queue removeFirst.


stack := OrderedCollection new.
stack
   add: #first;
   add: #second;
   add: #third.

Transcript cr; show: stack removeLast.
Transcript cr; show: stack removeLast.
Transcript cr; show: stack removeLast.

[marten]

Or SstSharedQueue ?

Marten

[daswartz]

Doug, why not use OrderedCollection to implement queues and stacks? Use removeFirst to remove elements in FIFO order, removeLast for LIFO:

Of course I could have used an OrderedCollection. I don't know why I didn't; My brain was probably just working wierdly that day. I wanted a queue, so I used a queue class. Silly me.

Marten, I didn't want this code to depend on the Server Smalltalk stuff, so couldn't use SstSharedQueue (which works fine, even though it is a subclass of EsQueue).

Regardless, it still looks like a defect in EsQueue to me.

Doug Swartz

[wembley]

I agree that EsQueue is broken. Further, any subclass of EsQueue is also broken if it is instantiated using new: 1. Now I'm not sure why anyone would want a queue with only one element, but that doesn't mean it shouldn't work

I think I prefer changing the grow method (I guess because it seems that if you asked for a queue of size one, you should get it):

Code: Select all

grow
   "Make the contents larger by adding space between tail and head."

   | newContents newHead |

   newContents := Array new: contents size + (contents size + 1 // 2).  "Grow by 50%, but at least by 1"
   tail >= head
      ifTrue: [
         "Case 1: Tail after head, so just add space and copy entire contents."
         newContents replaceFrom: head to: tail with: contents startingAt: head]
      ifFalse: [
         "Case 2: Tail before head, so make split larger and update head."
         newHead := newContents size - (contents size - head).
         newContents replaceFrom: 1 to: tail with: contents startingAt: 1.
         newContents replaceFrom: newHead to: newContents size with: contents startingAt: head.
         head := newHead].
   contents := newContents

I have opened case 39911 for this problem -- fixed in V8.0.0.