objective: a function for generating guids of unique entities

guid.js

// objective: a function for generating guids of unique entities
// usage: guid( obj ) => integer

// approach 1
// entities kept in a hash array, key id found by iteration

// pros:
// (1) unobtrusive; doesn't pollute objects with expandos
// (2) ids can't be accidentally deleted/changed
// (3) ids can be assigned to any type of object
// (4) id => entity lookup could be implemented for free

// cons:
// (1) id lookup is O(N), a pretty big deal
// (2) GC memory leaked unless "unset" is implemented

guid1 = function( guid, objs, i ) {
  return function( obj ) {
    for ( i = guid; i--; ) if ( objs[ i ] === obj ) return i
    return objs[ guid ] = obj, guid++  
  }
}( 1, [] )

// approach 2
// ids kept on each object as a property, a la jQuery

// pros:
// (1) id lookup is O(1)
// (2) no memory leaks, since only primitive integers are stored

// cons:
// (1) ids can be erased, may interfere with iteration
// (2) hacky expando string required

guid2 = function( guid, expando ) {
  return function( obj ) {
    if ( obj ) {
      if ( obj[ expando ] ) return obj[ expando ]
      
      obj[ expando ] = guid
  
      if ( obj[ expando ] ) return guid++
    }
  }
}( 1, Date.now().toString( 36 ) )

To improve performance of Approach 1 you can implement a hashtable-like structure by coercing the object to a string to use as the hash to "buckets". Also consider using indexOf() to search the arrays. This isn't perfect since toString() isn't an ideal hash function, but it's closer to O(1) than O(n) in many situations.

guid1 = function() {
  var guid = 1;
  var buckets = {};
  return function( obj ) {
    var bucket = buckets[obj] = buckets[obj] || { objs : [], guids : [] };
    var index = bucket.objs.indexOf(obj);
    if (index < 0) {
        index = bucket.objs.length;
        bucket.objs[index] = obj;
        bucket.guids[index] = guid++;
    }
    return bucket.guids[index];
  }
}()

To improve compatibility of Approach 2 you could use Object.defineProperty() to make the guid non-enumerable and non-writable/deletable.

guid2 = function( guid, expando ) {
  return function( obj ) {
    if ( obj ) {
      if ( obj[ expando ] ) return obj[ expando ]

      if (typeof Object.defineProperty === "function")
        Object.defineProperty(obj, expando, { value : guid })
      else
        obj[ expando ] = guid

      if ( obj[ expando ] ) return guid++
    }
  }
}( 1, Date.now().toString( 36 ) )

They're not exactly what you want, but see the set implementations in my "leakhelper" project for more details/ideas: https://github.com/tlrobinson/leakhelper/blob/master/lib/leakhelper.js#L155-263

holy cow, major assist by tlrobinson. thanks, tom!

Ooops noticed I'm missing a "return" on the last line of approach 1 example: "bucket.guids[index];"

yeah, i added it for ya.

i'm not to keen on relying on defineProperty or indexOf, so i'm thinking seriously about a variation on your guid1:

guid1 = function( guid, buckets, bucket, i, l, objs, guids ) {
  return function( obj ) {
    bucket = buckets[ obj ] || ( buckets[ obj ] = { objs: [], guids: [] } )
    objs = bucket.objs
    guids = bucket.guids
    i = l = objs.length

    while ( i-- ) if ( objs[ i ] === obj ) return guids[ i ]

    return objs[ l ] = obj, guids[ l ] = guid++
  }
}( 1, {} )

i like this a lot, but worry about how/when to invalidate the cache. also, id => obj is no longer O(1)...

and to remove some array overhead, and perform lookup by constructor name:

guid1 = function( guid, buckets, bucket, name, i, l ) {
  return function( obj ) {
    name = obj ? obj.constructor.name : obj
    bucket = buckets[ name ] || ( buckets[ name ] = [] )
    i = l = bucket.length

    while ( i-- ) if ( bucket[ i-- ] === obj ) return bucket[ i ]

    return bucket[ l + 1 ] = obj, bucket[ l ] = guid++
  }
}( 1, {} )

or if you're okay with unique strings in the style of constructor-name/id:

function guid( obj ) {
  for (
    var type = obj ? obj.constructor.name : obj
      , list = guid[ type ] || ( guid[ type ] = [] )
      , i = list.length
      ; i-- && list[ i ] !== obj;
  );

  return ++i || ( i = list.push( obj ) ), type + "/" + i
}

indexOf is significantly faster than manually iterating. I'd suggest checking for it's existence and falling back to manual iteration.

Also, you would win a JavaScript obfuscation contest. It took me a solid minute to figure out how that 7 line function worked.

i dunno, is indexOf really that much faster?

and yeah, my style is a bit, uh, terse i guess...