oid

oid
===


This Node module provides a simple utility for object identity hashing
and two related classes. This can be useful any time you need to do
triple-equals (===) style comparisons across arbitrary numbers of
objects. Instead of doing an O(N^2) set of comparisons, you can
instead get the identity hashes of the things you want to compare, and
use those in clever ways to whittle down the required comparisons,
often allowing O(1) implementations.

Building and Installing
-----------------------

``shell
npm install oid
`

Or grab the source and

`shell
node-waf configure build
`

Note: This module contains native code, and so you will have
to have a C compiler available. Consult your OS documentation for
details on setting that up.


Testing
-------

`shell
npm test
`

Or

`shell
node ./test/test.js
`

Example
-------

This example (also available in the example directory) deduplicates
the elements of an array in O(N) time (instead of O(N^2)), by taking
advantage of an identity set.

`javascript
function dedup(orig) {
var result = [];
var elements = oid.createSet();

for (var i = 0; i < orig.length; i++) {
var one = orig[i];
if (elements.add(one)) {
result.push(one);
}
}

return result;
}
`

Here's a transcript of a use of this function as well as the more
fundamental hash() function. Note that the literal syntax []
creates a new object with a distinct identity each time it is
executed.

`
> x = []
[]
> y = []
[]
> z = y
[]
> x === y
false
> oid.hash(x) === oid.hash(y)
false
> z === y
true
> oid.hash(z) === oid.hash(y)
true
> a = dedup([x, y, x, x, y, y, 1, 2, 3, 1, 2, 3, x, y, "yumminess"])
[ [], [], 1, 2, 3, 'yumminess' ]
> a[0] === x
true
> a[1] === y
true
`

Usage
-----

This library provides one regular function and two constructors.

Top-Level Functions
-------------------

$3

Return an identity hash of the given value or object. The return value
from two calls to this function are guaranteed to be the same when
given the same input, where "same" is the relationship defined by the
triple-equals (===) operator of JavaScript.

The return value is furthermore guaranteed to be a positive
(non-negative and non-zero) integer value.

The return value is never guaranteed to be unique across multiple
values. That is, there are many pairs of values or objects that are
not the same but which do have the same identity hash. Somewhat
more mathematically: hash(x) !== hash(y) implies that x !== y, but
hash(x) === hash(y) does not imply that x === y.

For normal objects (including arrays, functions, and regular
expressions), this returns an arbitrary internally-generated id
number.

For strings, this returns a hash based on the characters contained in
the string. The algorithm used is similar to (but not quite identical
to) that used by String.hashCode() in Java.

For numbers, this returns a hash based on the numeric value. More specifically,
it is produced by inspecting the underlying byte representation of the
value. As such, it is not guaranteed to be stable across different
implementations of JavaScript.

For booleans, null, and undefined, this returns a particular
predefined value (different for each), which are all prime numbers
representable with five digits in base ten.

$3

See below.

$3

See below.


Identity Maps
-------------

An identity map is a set of key-value associations, where the
keys are arbitrary objects or values, compared by identity.

$3

This constructs and returns a new identity map.

$3

Get the value associated with the given key. If there is no mapping
for the key, return the ifNotFound argument (which defaults to
undefined).

$3

Set the value associated with the given key to the given value, and
return the previously associated value. If there was no previous
mapping for the key, return the ifNotFound argument (which defaults
to undefined).

$3

Return true if there is a mapping for the given key or false
if not.

$3

Remove the mapping for the given key, returning its formerly
associated value or the ifNotFound value if the key wasn't formerly
mapped.

$3

Get the number of elements in the map.

$3

Call the given callback as callback(key, value) for each association
in the map. There is no guarantee about what order the callbacks will
be made in.

Identity Sets
-------------

An identity set is a set (unordered list of unique elements) of
objects / values, where set membership is determined by identity
comparison.

$3

This constructs and returns a new identity set.

$3

Return true if there the given value is in the set or false if not.

$3

Add the given value to the set. Returns true if this operation
actually changed the set (that is, true if the item wasn't already
in the set).

$3

Remove the given value from the set. Returns true if this operation
actually changed the set (that is, true if the item in fact was in
the set to begin with).

$3

Get the number of elements in the set.

$3

Call the given callback as callback(value) for each element
of the set. There is no guarantee about what order the callbacks will
be made in.

To Do
-----

* The two collection classes probably ought to have more iteration methods.

* A weak-key identity map class and a weak-contents identity set class
would probably be handy.

* It seems reasonable that this module provide efficient implementations
of deep variants of clone() and isEqual().


Contributing
------------

Questions, comments, bug reports, and pull requests are all welcome.
Submit them at the project on GitHub.

Bug reports that include steps-to-reproduce (including code) are the
best. Even better, make them in the form of pull requests that update
the test suite. Thanks!

Author
------

Dan Bornstein
(personal website), supported by
The Obvious Corporation.

License
-------

Copyright 2012 The Obvious Corporation.

Licensed under the Apache License, Version 2.0.
See the top-level file LICENSE.txt` and
(http://www.apache.org/licenses/LICENSE-2.0).