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

Discussion in 'Javascript' started by kj, Feb 3, 2008.

  1. kj

    kj Guest

    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.
    --
    NOTE: In my address everything before the first period is backwards;
    and the last period, and everything after it, should be discarded.
    kj, Feb 3, 2008
    #1
    1. Advertising

  2. kj

    VK Guest

    On Feb 3, 7:40 pm, kj <> wrote:
    > 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 ] ] };


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


    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.
    VK, Feb 3, 2008
    #2
    1. Advertising

  3. kj

    kj Guest

    In <> VK <> writes:

    >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
    >}


    I like it! Thanks!

    kynn

    --
    NOTE: In my address everything before the first period is backwards;
    and the last period, and everything after it, should be discarded.
    kj, Feb 3, 2008
    #3
  4. 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.


    PointedEars
    --
    Use any version of Microsoft Frontpage to create your site.
    (This won't prevent people from viewing your source, but no one
    will want to steal it.)
    -- from <http://www.vortex-webdesign.com/help/hidesource.htm>
    Thomas 'PointedEars' Lahn, Feb 3, 2008
    #4
  5. kj

    VK Guest

    On Feb 3, 10:01 pm, Thomas 'PointedEars' Lahn <>
    wrote:
    > 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.


    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>
    VK, Feb 3, 2008
    #5
  6. VK wrote:
    > [...] Thomas 'PointedEars' Lahn [...] wrote:
    >> 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.

    >
    > [...]


    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
    --
    var bugRiddenCrashPronePieceOfJunk = (
    navigator.userAgent.indexOf('MSIE 5') != -1
    && navigator.userAgent.indexOf('Mac') != -1
    ) // Plone, register_function.js:16
    Thomas 'PointedEars' Lahn, Feb 3, 2008
    #6
  7. In comp.lang.javascript message <>, Sun,
    3 Feb 2008 20:49:05, Thomas 'PointedEars' Lahn <>
    posted:
    >VK wrote:
    >> [...] Thomas 'PointedEars' Lahn [...] wrote:
    >>> 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.

    >>
    >> [...]

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


    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.

    --
    (c) John Stockton, nr London UK. ???@merlyn.demon.co.uk Turnpike v6.05 MIME.
    Web <URL:http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms, & links.
    Check boilerplate spelling -- error is a public sign of incompetence.
    Never fully trust an article from a poster who gives no full real name.
    Dr J R Stockton, Feb 4, 2008
    #7
  8. kj

    VK Guest

    On Feb 3, 10:49 pm, Thomas 'PointedEars' Lahn <>
    wrote:
    > As expected, your example proves nothing, let alone your own statement.


    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>
    </html>

    > You should refrain from resorting to ad-hominem attacks


    Do you consider posted working code as a kind of ad-hominem attack?
    Whatever...
    VK, Feb 4, 2008
    #8
  9. VK wrote:
    > [...] Thomas 'PointedEars' Lahn [...] wrote:
    >> As expected, your example proves nothing, let alone your own statement.

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


    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
    --
    Anyone who slaps a 'this page is best viewed with Browser X' label on
    a Web page appears to be yearning for the bad old days, before the Web,
    when you had very little chance of reading a document written on another
    computer, another word processor, or another network. -- Tim Berners-Lee
    Thomas 'PointedEars' Lahn, Feb 4, 2008
    #9
  10. kj

    VK Guest

    On Feb 5, 12:30 am, Thomas 'PointedEars' Lahn <>
    wrote:
    > 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.


    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>
    VK, Feb 4, 2008
    #10
  11. VK wrote:
    > [...] Thomas 'PointedEars' Lahn [...] wrote:
    >> 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.

    >
    > 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';
    > }


    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
    --
    realism: HTML 4.01 Strict
    evangelism: XHTML 1.0 Strict
    madness: XHTML 1.1 as application/xhtml+xml
    -- Bjoern Hoehrmann
    Thomas 'PointedEars' Lahn, Feb 4, 2008
    #11
  12. kj

    VK Guest

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


    > Thanks for a good laugh.


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


    Eh? Uhmm... OK... I better go, you know, get well and stuff...
    VK, Feb 4, 2008
    #12
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. guy

    identification of NET objects

    guy, Sep 6, 2005, in forum: ASP .Net
    Replies:
    2
    Views:
    353
    Eliyahu Goldin
    Sep 6, 2005
  2. EP
    Replies:
    5
    Views:
    6,401
    Andrew McNamara
    Jun 27, 2006
  3. eastern_strider

    unique file identification id

    eastern_strider, May 2, 2006, in forum: C++
    Replies:
    1
    Views:
    447
    Jonathan Mcdougall
    May 2, 2006
  4. tiewknvc9
    Replies:
    10
    Views:
    791
    Gordon Beaton
    Mar 5, 2007
  5. Jimmy
    Replies:
    22
    Views:
    5,059
    Eric Sosman
    Aug 24, 2007
Loading...

Share This Page