K
kj
I would like to write a function that recursively traverses an
arbitrary JavaScript data item. The challenge in this kind of
traversal problem is to avoid the infinite recursion when the
argument is a cyclical constructs, like, for example:
var x = []; x[ 0 ] = { y: [ x[ 0 ] ] };
Typically one solves this problem by setting up a hash whose keys
uniquely identify each item visited during the traversal. (The
traversal algorithm consults this hash every time it visits an
item, and if it finds that it has been visited already, it can take
steps to avoid the infinite recursion.)
In JavaScript, this strategy requires a (non-recursive, and hopefully
very fast) function that assigns a *unique* string to each JavaScript
object, to serve as its key in the hash. (I.e. something like Java's
very handy Object.hashCode method). Here's where I'm stuck.
Does anyone know of a function that fits the bill? (Portability
would be nice also, of course.)
TIA!
kynn
P.S. I realize that an alternative would be to store the visited
items in an array instead of a hash, and use a simple linear search
and === to determine whether an item has been visited before, but
linear searching is very slow, and without a unique string identifier,
I don't see how to make the search of this array any faster.
arbitrary JavaScript data item. The challenge in this kind of
traversal problem is to avoid the infinite recursion when the
argument is a cyclical constructs, like, for example:
var x = []; x[ 0 ] = { y: [ x[ 0 ] ] };
Typically one solves this problem by setting up a hash whose keys
uniquely identify each item visited during the traversal. (The
traversal algorithm consults this hash every time it visits an
item, and if it finds that it has been visited already, it can take
steps to avoid the infinite recursion.)
In JavaScript, this strategy requires a (non-recursive, and hopefully
very fast) function that assigns a *unique* string to each JavaScript
object, to serve as its key in the hash. (I.e. something like Java's
very handy Object.hashCode method). Here's where I'm stuck.
Does anyone know of a function that fits the bill? (Portability
would be nice also, of course.)
TIA!
kynn
P.S. I realize that an alternative would be to store the visited
items in an array instead of a hash, and use a simple linear search
and === to determine whether an item has been visited before, but
linear searching is very slow, and without a unique string identifier,
I don't see how to make the search of this array any faster.