Awesome
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
npm install oid
Or grab the source and
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
npm test
Or
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.
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
oid.hash(value)
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.
idmap = oid.createMap()
See below.
idset = oid.createSet()
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.
idmap = oid.createMap()
This constructs and returns a new identity map.
idmap.get(key, ifNotFound) => value
Get the value associated with the given key. If there is no mapping
for the key, return the ifNotFound
argument (which defaults to
undefined
).
idmap.set(key, value, ifNotFound) => previousValue
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
).
idmap.has(key) => boolean
Return true
if there is a mapping for the given key or false
if not.
idmap.remove(key, ifNotFound) => previousValue
Remove the mapping for the given key, returning its formerly
associated value or the ifNotFound
value if the key wasn't formerly
mapped.
idmap.size() => int
Get the number of elements in the map.
idmap.forEach(callback)
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.
idset = oid.createSet()
This constructs and returns a new identity set.
idset.has(value) => boolean
Return true
if there the given value is in the set or false
if not.
idset.add(value) => boolean
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).
idset.remove(value) => boolean
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).
idset.size() => int
Get the number of elements in the set.
idset.forEach(callback)
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()
andisEqual()
.
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).