[Project_owners] how to implement bounded stack in javascript?

Axel Hecht axel at pike.org
Sun Apr 16 17:39:05 EDT 2006


Eric H. Jung wrote:
> Thanks for the help, Alex and Neil. I can't claim to understand the subleties of what's going on
> here. Based on your back-and-forth, I have the following. I did some testing, but not rigorously.
> Do you see any problems?
> 
>   _boundedStack : {
>     _max : 500,
>     push: function(aElem) {
>       this._current++;
>       if (this._current == this._max) {
>         this._current = 0;
>         this._overfly = true;
>       }
>       this._buffer[this._current] = aElem;
>     },
>     get length() {
>       return this._overfly ? this._max : this._current;
>     },
>     item : function(aIndex) {
>       if (aIndex == 0)
>         aIndex = 1;
>       
This is wrong, just try to get item(0).

Neil is right, if you want to reverse the order, you have to fiddle with 
the getter here.

>       else if (this._overfly) {
>         aIndex += this._current + 1; //XXX check this logic
>       }

if you increment _current at the end of push, you don't need the + 1 
here, but then you need to adjust legth().

I'd leave it as is and not be too picky about what current "usually is".

>       aIndex = aIndex % this._max;
>       return this._buffer[aIndex];
>     }
>   }
> 
> Thank you,
> Eric
> 
> --- Axel Hecht <axel at pike.org> wrote:
> 
>> Neil wrote:
>>> Axel Hecht wrote:
>>>
>>>> BoundedStack.prototype = {
>>>>   push: function(aElem) {
>>>>     this._current++;
>>>>     if (this._current == this._max)
>>>>       this._current = 0;
>>>>       this._overflew = true;
>>>>     }
>>>>     this._buffer[this._current] = aElem;
>>>>   },
>>>>   get length() {
>>>>     return this._overflew ? this._max : this._current;
>>>>   },
>>>>   get: function(aIndex) {
>>>>     if (this._overflew) {
>>>>       aIndex += this._current + 1; //XXX check this logic
>>>>     }
>>>>     aIndex = aIndex % this._max;
>>>>     return this._buffer[aIndex];
>>>>   }
>>>> }
>>>>
>>>> This is from the top of my head, without testing, all numbers in the 
>>>> getter could be off by one. Consider this to be devmo-style MIT 
>>>> License ;-)
>>>    * You don't need the +1.
>>>    * You only need the % in the overflow case.
>>>    * Your get function is 1-indexed, fix this by incrementing current
>>>      at the end of push, not at the beginning, or by starting with
>>>      current equal to max and decrementing at the 
>> I don't think so.
>>
>> 0 % 500 == 0 and 500 % 500 == 0. Sounds 0 based to me.
>>
>> Doing the mod afterwards is some half hearted out-of-bounds check, I 
>> should have checked aIndex > 0, too. Of course I should out-of-bounds 
>> check !this._overflown, too (<= this._current).
>>
>> this._current is the last written element, for aIndex == 0, it should 
>> return the next one as first element.
>>
>> I guess I had to actually test this code to be sure.
>>
>> beginning (in which
>>>      case, always add current to index, % max).
>>>    * Your get function should be named item. (Isn't get a keyword?)
>> probably, yes.
>>
>>>    * Overflew is actually the past participle of overfly.
>> oops ;-), I'm fly!
>>
>> Axel
>> _______________________________________________
>> Project_owners mailing list
>> Project_owners at mozdev.org
>> http://mozdev.org/mailman/listinfo/project_owners
>>
> 


More information about the Project_owners mailing list