I'm trying to demonstrate some search algorithms on a webpage. DFS, BFS, and A*. The end goal is to have the user click a grid box and watch the search function light up the grid tiles as it searches them. I'm having issues getting my data structures to work properly in Javascript though. So this is my Stack prototype.
function Stack()
{
this._size = 0;
this._stack = {};
}
Stack.prototype.push = function(node)
{
var size = this._size++;
this._stack[size] = node;
}
Stack.prototype.pop = function()
{
var size = this._size;
if(size > 0)
{
var popped = this._stack[size];
delete this._stack[size];
this._size--;
return popped;
}
}
Stack.prototype.isEmpty = function()
{
var size = this._size;
return size <= 0;
}
Stack.prototype.stringify = function()
{
var size = this._size
var str = "Stack:"+ this._size + ":{";
if(size > 0)
{
for(var i = 0; i < size; i++)
{
str = str + this._stack[i].stringify();
if(i+1 < size)
{
str = str + ", ";
}
else
{
str = str + "}";
}
}
}
else
{
str = str + "Empty}";
}
return str;
}
Here is the prototype I am pushing and popping to test with
function TILE(x, y, w, h, id)
{
this._x = x;
this._y = y;
this._w = w;
this._h = h;
this._id = id;
}
TILE.prototype.X = function(){return this._x;}
TILE.prototype.Y = function(){return this._y;}
TILE.prototype.WIDTH = function(){return this._w;}
TILE.prototype.HEIGHT = function(){return this._h;}
TILE.prototype.ID = function(){return this._id;}
TILE.prototype.stringify = function()
{
var str = "Tile:"+this._id;
return str;
};
Here is my test function.
function testStack()
{
var s = new Stack();
console.log(s.stringify());
s.push(new TILE(10, 10, 15, 15, 69));
console.log(s.stringify());
s.push(new TILE(10, 10, 15, 15, 70));
console.log(s.stringify());
var thing = s.pop();
console.log(s.stringify());
console.log(thing.stringify());
}
And here is my console output
Stack:0:{Empty}
Stack:1:{Tile:69}
Stack:2:{Tile:69, Tile:70}
Stack:1:{Tile:69}
TypeError: thing is undefined
I'm somewhat new to Javascript. I understand its not really an object oriented language but it looks to me like the stack working properly up until I try to set 'popped' in TILE.js. Can anyone maybe enlighten me on what's happening here? Can Javascript prototypes be used like this?
The problem is the way you increment your "pointer" size
(or rather, it's how you later use that "pointer" as we'll see shortly):
var size = this._size++;
this._stack[size] = node;
You are using a postfix increment operator (++
) which means in this case size
gets the value of this._size
before it increments. After pushing something onto your stack this._size
will be 1
and the object backing your stack will have a single property 0
.
When you then attempt to pop from your stack this is what you do:
var size = this._size;
if(size > 0)
{
var popped = this._stack[size];
delete this._stack[size];
this._size--;
return popped;
}
Remember we just established that this._size
is 1
? There's the problem. The this._stack
object doesn't have a key of 1
. You could subtract one from the size in the pop
method to fix it:
var size = this._size - 1;
if(size > 0)
{
var popped = this._stack[size];
delete this._stack[size];
this._size--;
return popped;
}
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments