Unique identification of JS objects? (Or hashCode for JS?)

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.
 
V

VK

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 ] ] };
Click to expand...

That is not a working example: for the moment of execution of
y: [ x[ 0 ] ]
x[0] is not initialized yet, so x[0].y[0] will be undefined and no
cross-reference.

What you mean I guess must be like:
var x = [];
x[0] = {};
x[0].y = [];
x[0].y[0] = 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.)
Click to expand...

In Javascript Object and Array instances are passed by reference and
not by value. So by simply assigning any extra property to the first
occurrence, you are getting it for all other references.

function f() {
var x = [];
x[0] = {};
x[0].y = [];
x[0].y[0] = x[0];

x[0].visited = true;

window.alert(x[0].y[0].visited); // true
}

Sorry if I'm out of loop of what you are really asking.
 
T

Thomas 'PointedEars' Lahn

VK said:
In Javascript Object and Array instances are passed by reference and
not by value.
Click to expand...

Nonsense. References are values, and all arguments are passed by value.


PointedEars
 
V

VK

Nonsense. References are values, and all arguments are passed by value.
Click to expand...

Normally I am visiting Germany to get some descent beer. This time it
may be with the purpose to cut someone's ears off...

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN">
<html><head>
<meta http-equiv="Content-Type"
content="text/html; charset=iso-8859-1">

<title>Demo</title>
<script type="text/javascript">
function f() {
var x = [];
x[0] = {};
x[1] = 'foo';
x[0].y = [];
x[0].y[0] = x[0];
x[0].y[1] = x[1];

x[0].visited = true;
x[1] += 'bar';

window.alert(x[0].y[0].visited); // true

window.alert(x[1]); // 'foobar'
window.alert(x[0].y[1]); // 'foo'

}
</script>
</head>
<body>
<h1>Demo</h1>
<p onclick="f();"><strong>Click here</strong></p>
</body>
</html>
 
T

Thomas 'PointedEars' Lahn

VK said:
Nonsense. References are values, and all arguments are passed by value.
Click to expand...

[...]
Click to expand...

As expected, your example proves nothing, let alone your own statement.
You should refrain from resorting to ad-hominem attacks, they only let
you look like more of an idiot than you already present yourself here with
your ridiculous "proofs" of your fantasies about the matters discussed.


PointedEars
 
D

Dr J R Stockton

In comp.lang.javascript message <[email protected]>, Sun,
3 Feb 2008 20:49:05 said:
VK said:
VK wrote:
In Javascript Object and Array instances are passed by reference and
not by value.
Nonsense. References are values, and all arguments are passed by value.
Click to expand...

[...]
Click to expand...

As expected, your example proves nothing, let alone your own statement.
You should refrain from resorting to ad-hominem attacks, they only let
you look like more of an idiot than you already present yourself here with
your ridiculous "proofs" of your fantasies about the matters discussed.
Click to expand...

It is rather stupid to make a truly /ad hominem/ attack in which you
falsely accuse someone of /ad hominem/.

Your real problem, or really ours, is that you were born about 80 years
too late.
 
V

VK

As expected, your example proves nothing, let alone your own statement.
Click to expand...

Arrrh... OK, one more time and this is the last one:

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN">
<html>
<head>
<meta http-equiv="Content-Type"
content="text/html; charset=iso-8859-1">

<title>Demo</title>
<script type="text/javascript">

var x, a, b, m, n;

function f() {

// Array
x = [];
x[0] = {};
x[0].y = [];
x[0].y[0] = x[0];
x[0].visited = true;
window.alert(x[0].y[0].visited); // true

// Object
a = new Object;
b = a;
a.visited = true;
window.alert(b.visited); // true

// string primitive
m = 'foo';
n = m;
m += 'bar';
window.alert(m); // 'foobar'
window.alert(n); // 'foo'

}

</script>
</head>
<body>
<h1>Demo</h1>
<p onclick="f();"><strong>Click here</strong></p>
</body>
You should refrain from resorting to ad-hominem attacks
Click to expand...

Do you consider posted working code as a kind of ad-hominem attack?
Whatever...
 
T

Thomas 'PointedEars' Lahn

VK said:
Arrrh... OK, one more time and this is the last one:
Click to expand...

Posting an irrelevant example over and over again does not make it more
relevant. Here it is for the intellectually challenged among us: In order
to post something relevant to this discussion, you have to prove your
statement which is:

| In Javascript Object and Array instances are passed by reference and
| not by value.

As you will not be able to do that, because it is objectively nonsense, you
could simply admit your error and be done with it. But I doubt you are
capable of that. Instead you are likely to provide this newsgroup with
another one of your fantasies.


PointedEars
 
V

VK

Posting an irrelevant example over and over again does not make it more
relevant. Here it is for the intellectually challenged among us: In order
to post something relevant to this discussion, you have to prove your
statement which is:

| In Javascript Object and Array instances are passed by reference and
| not by value.
Click to expand...

The cloudy way of your mind is too sophisticated for my humble mind to
understand what a hey are you talking about. At the same time it
puzzles me in some way so I'm responding once again. So the posted
code doesn't prove my quoted statement above? I will try: only try -
to get what internal picture did you create over the matter. The first
maybe "no function to function call - no pass of any kind, neither by
value nor by reference". Programmatically it is not true at all but it
is not hard to make sample more "visually acceptable", it is done in
the version below. The second maybe is that "Javascript doesn't have
access to memory address pointers, so there cannot be any by_reference
by definition". In the latter case I have nothing to propose but to
read the relevant literature, say by_reference explanations for C++
(not for C) or for Java. Any way, faced quod potui, faciant meliora
potentes.

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN">
<html>
<head>
<meta http-equiv="Content-Type"
content="text/html; charset=iso-8859-1">

<title>Demo</title>
<script type="text/javascript">

var x, a, b, m, n;

function f() {

// Array
x = [];
x[0] = {};
x[0].y = [];
x[0].y[0] = x[0];
foo(x[0]);
window.alert(x[0].y[0].visited); // true

// Object
a = new Object;
b = a;
foo(a);
window.alert(b.visited); // true

// string primitive
m = 'foo';
n = m;
bar(m);
window.alert(m); // 'foo'
window.alert(n); // 'foo'

}

function foo() {
arguments[0].visited = true;
}

function bar() {
arguments[0] += 'bar';
}

</script>
</head>
<body>
<h1>Demo</h1>
<p onclick="f();"><strong>Click here</strong></p>
</body>
</html>
 
T

Thomas 'PointedEars' Lahn

VK said:
Posting an irrelevant example over and over again does not make it more
relevant. Here it is for the intellectually challenged among us: In order
to post something relevant to this discussion, you have to prove your
statement which is:

| In Javascript Object and Array instances are passed by reference and
| not by value.
Click to expand...

The first maybe "no function to function call - no pass of any kind, neither
by value nor by reference". Programmatically it is not true at all but it
is not hard to make sample more "visually acceptable", it is done in
the version below.
[...]
function foo() {
arguments[0].visited = true;
}

function bar() {
arguments[0] += 'bar';
}
Click to expand...

Thanks for a good laugh. `arguments' is not even a reference to an Array
object (at least not per specification and so there is only one
implementation that does it), much less *an argument* of foo() or bar(),
and only the latter would be relevant here.

I could easily post an example that proves you wrong, but it is up to you
to prove you are right, and laughing is good for health.


PointedEars
 
V

VK

function bar() {
arguments[0] += 'bar';
}
Click to expand...
Click to expand...
Thanks for a good laugh.
Click to expand...

Glad I helped at least with that one. The rest is in the hands of
Mother Nature.

P.S.
`arguments' is not even a reference to an Array
object (at least not per specification and so there is only one
implementation that does it), much less *an argument* of foo() or
bar()
Click to expand...

Eh? Uhmm... OK... I better go, you know, get well and stuff...
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

How to check the validation of js files or html files including js? 6
My sliding panel in React Js with graphs on it renders nothing but a blank screen--need help 0
securing my software (unique computer identification number) 10
Strange problem in JS code 5
Get name or location of .js file - is it possible? 4
Trouble with prediction code, for the life of me I can't figure out why it isnt running properly. Help would be appreciated. 0
Reusable Image Cache in JS => NS_ERROR_DOM_HIERARCHY_REQUEST_ERR 2
can JS pick up LANG attrib's ..? 5

Members online

Total: 28 (members: 2, guests: 26)
Robots: 237

Forum statistics

Threads
473,768
Messages
2,569,574
Members
45,048
Latest member
verona

Latest Threads

Top