From: Bob Hutchison <hutch@...>
Date: 2007-10-24T00:17:15+09:00
Subject: Re: pop/push, shift/unshift


On 23-Oct-07, at 10:52 AM, Jesús Gabriel y Galán wrote:

> On 10/23/07, Bob Hutchison <hutch@recursive.ca> wrote:
>> On 23-Oct-07, at 10:32 AM, Bob Hutchison wrote:
>>> On 23-Oct-07, at 10:02 AM, Jesús Gabriel y Galán wrote:
>>>> class Array
>>>>    alias :enqueue :push
>>>>    alias :dequeue :shift
>>>> end
>>>>
>>>> Then you get Queue semantics and the start of the queue is the  
>>>> first
>>>> element in the Array :-). (you could do enqueue --> unshift,  
>>>> dequeue
>>>> --> pop if you rather have the first element of the queue the  
>>>> last in
>>>> the array).
>>>>
>>>
>>> You have to be really careful here. Push/pop and shift/unshift are
>>> not the same functions working on opposite ends of the array, no
>>> matter what it sounds like from the documentation.
>>
>> Of course I forgot to mention the specific problem for your scheme.
>> My previous email outlines how un/shift works (see below, I left it
>> quoted).
>>
>> In your scheme you are using unshift to remove from the front, and
>> push to add to the back. As I mentioned shift moves the start point
>> of the array. Every time you use shift you 'loose' a cell of your
>> array before the start of the array. Unshift will re-use those lost
>> cells (Ruby might be doing something clever with these but I wouldn't
>> count on it). Push will never reuse them since it is adding to the
>> end of the array. Consequently the Array used for the queue will get
>> larger and larger.
>
> I understand your explanation, but this sounds like a bug to me. I
> understand the optimization part of not shifting everything in the
> shift method, but if that's a desired way of working I suppose it
> should be warned for the users of Array. In light of this then, the
> recommended approach for queue semantics would be to use unshift and
> pop?
>

I just did a quick test. It looks as though Ruby is now handling both  
the unshift/pop and push/shift properly. I know when I reported it in  
Ruby 1.8.4 there was a discussion about how to deal with this, and it  
looks as though 1.8.5 has it working (or I've patched my version of  
Ruby and have forgotten about it).

So maybe not a problem, or too big of a problem. Just don't forget  
about the cells holding references, that is definitely there in 1.8.5.

Cheers,
Bob

> Thanks,
>
> Jesus.
>

----
Bob Hutchison                  -- tumblelog at http:// 
www.recursive.ca/so/
Recursive Design Inc.          -- weblog at http://www.recursive.ca/ 
hutch
http://www.recursive.ca/       -- works on http://www.raconteur.info/ 
cms-for-static-content/home/