[Project_owners] how to implement bounded stack in javascript?

Axel Hecht axel at pike.org
Sun Apr 16 02:16:31 EDT 2006


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


More information about the Project_owners mailing list