[Project_owners] how to implement bounded stack in javascript?

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


Eric H. Jung wrote:
> Hi Axel,
> 
>> The next question to ask is, are you frequently going to hit 500 
>> messages? Or are you most of the time fine with 25? That determines how 
>> much of the array you want to allocate to boot with.
>>
> 
> Yes, 500 will be hit constantly and very rapidly.
> 
>> Then I'd recommend having a 'currentIndex' member, and cycle that 
>> around. That way, you never move the 499 items inside the array that you 
>> didn't intend to change.
>>
> 
> OK, I could even just push() the elements onto the end of the array but display elements in
> reverse order in the <tree/>; that is fine--the tree is only displayed when the user wants to see
> it, anyway. But how does a currentIndex prevent the Array from growing without bounds? I still
> need o shift() or splice() every time, no? Is splice() better than shift() to remove from the
> front?
> 
> 

function BoundedStack() {
   this._max = 500;
   this._buffer = new Array(this._max);
   this._current = 0;
   this._overflew = false;
}

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 ;-)

Axel


More information about the Project_owners mailing list