[Project_owners] how to implement bounded stack in javascript?

Eric H. Jung grimholtz at yahoo.com
Sat Apr 15 23:21:13 EDT 2006


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;
      
      else if (this._overfly) {
        aIndex += this._current + 1; //XXX check this logic
      }
      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