Map using tuples or objects

Question

I'm trying to use the new (ES6) Map objects in order to represent a map between properties and a value.

I have objects in a form similar to:

 {key1:value1_1,key2:value2_1},..... {key1:value1_N,key2:value2_N}

I want to group them based on both their key1 and key2 value.

For example, I want to be able to group the following by x and y:

[{x:3,y:5,z:3},{x:3,y:4,z:4},{x:3,y:4,z:7},{x:3,y:1,z:1},{x:3,y:5,z:4}]

And obtain a Map containing:

{x:3,y:5} ==>  {x:3,y:5,z:3},{x:3,y:5,z:4}
{x:3,y:4} ==>  {x:3,y:4,z:4},{x:3,y:4,z:7}
{x:3,y:1} ==>  {x:3,y:1,z:1}

In Python, I'd use tuples as dictionary keys. ES6 map allow arbitrary objects as keys but use the standard equality algorithm (===) so objects are only equal by reference from what I can tell.

How can I accomplish this sort of grouping using ES6 maps? Alternatively, a solution using normal JS objects if there is an elegant way I overlooked.

I'd rather not use an external collections library - but if there is a better solution using one I'm interested in learning about it too.

Answer 1

Ok, I've raised the issue on esdiscuss now and I got an answer from Mozilla's Jason Orendorff:

1. This is a problem with ES6 maps.
2. The solution will come in the form of ES7 value objects for keys instead of objects.
3. It was considered before to let people specify .equals and .hashCode but it was rejected in favor of value objects. (for good reasons in my opinion).
4. The only solution as of now is to roll your own collection.

A basic such collection (concept, don't use in production code) was offered by Bradley on the ESDiscuss thread and might look something like this:

function HashMap(hash) {
  var map = new Map;
  var _set = map.set;
  var _get = map.get;
  var _has = map.has;
  var _delete = map.delete;
  map.set = function (k,v) {
    return _set.call(map, hash(k), v);
  }
  map.get = function (k) {
    return _get.call(map, hash(k));
  }
  map.has = function (k) {
    return _has.call(map, hash(k));
  }
  map.delete = function (k) {
    return _delete.call(map, hash(k));
  }
  return map;
}

function TupleMap() {
  return new HashMap(function (tuple) {
    var keys = Object.keys(tuple).sort();
    return keys.map(function (tupleKey) { // hash based on JSON stringification
               return JSON.stringify(tupleKey) + JSON.stringify(tuple[tupleKey]);
    }).join('\n');
    return hashed;
  });
}

A better solution is to use something like MontageJS/Collections which allows for specification of hash/equals functions.

You can see the API docs here.

Answer 2

Benjamin's answer doesn't work for all objects, as it relies on JSON.stringify, which cannot handle circular objects and can map different objects to the same string. Minitech's answer can create huge trees of nested maps, which I suspect are both memory and CPU inefficient, especially for long tuples, as it has to create a map for each element in the tuple.

If you know that your tuples only contain numbers, then the best solution is to use [x,y].join(',') as the key. If you want to use tuples containing arbitrary objects as keys, you can still use this method, but have to map the objects to unique identifiers first. In the code below I generate these identifiers lazily using get_object_id, which stores the generated ids in an internal map. I can then generate keys for tuples by concatenating those ids. (See code at the bottom of this answer.)

The tuple method can then be used to hash tuples of objects to a string that can be used as the key in a map. This uses object equivalence:

x={}; y={}; 
tuple(x,y) == tuple(x,y) // yields true
tuple(x,x) == tuple(y,y) // yields false
tuple(x,y) == tuple(y,x) // yields false

If you're certain that your tuples will only contain objects (i.e. not null, numbers or strings), then you can use a WeakMap in get_object_id, such that get_object_id and tuple won't leak objects that are passed as argument to them.

var get_object_id = (function() {
  var generated_ids = 1;
  var map = new Map();
  return get_object_id;
  function get_object_id(obj) {
    if (map.has(obj)) {
      return map.get(obj);
    } else {
      var r = generated_ids++;
      map.set(obj, r);
      return r;
    }
  }
})();

function tuple() {
  return Array.prototype.map.call(arguments, get_object_id).join(',');
}

// Test
var data = [{x:3,y:5,z:3},{x:3,y:4,z:4},{x:3,y:4,z:7},
            {x:3,y:1,z:1},{x:3,y:5,z:4}];
var map = new Map();
for (var i=0; i<data.length; i++) {
  var p = data[i];
  var t = tuple(p.x,p.y);
  if (!map.has(t)) map.set(t,[]);
  map.get(t).push(p);
}

function test(p) {
  document.writeln((JSON.stringify(p)+' ==> ' + 
    JSON.stringify(map.get(tuple(p.x,p.y)))).replace(/"/g,''));
}

document.writeln('<pre>');
test({x:3,y:5});
test({x:3,y:4});
test({x:3,y:1});
document.writeln('</pre>');

Answer 3

While this question is quite old, value objects are still not an existing thing in JavaScript (so people might still be interested) so I decided to write a simple library to accomplish similar behaviour for arrays as keys in maps (repo here: https://github.com/Jamesernator/es6-array-map). The library is designed to be basically identical to map in usage except arrays are compared element-wise instead of by identity.

Usage:

var map = new ArrayMap();
map.set([1,2,3], 12);
map.get([1,2,3]); // 12

map.set(['cats', 'hats'], {potatoes: 20});
map.get(['cats', 'hats']); // {potatoes: 20}

Warning: The library however treats key elements by identity so the following doesn't work:

var map = new ArrayMap();
map.set([{x: 3, y: 5}], {x:3, y:5, z:10});
map.get([{x: 3, y: 5}]); // undefined as objects within the list are
                         // treated by identity

But as long as you can serialize the data into arrays of primitives you can use ArrayMap as follows:

var serialize = function(point) {
    return [point.x, point.y];
};
var map = new ArrayMap(null, serialize);
map.set({x: 10, y: 20}, {x: 10, y: 20, z: 30});
map.get({x: 10, y: 20}); // {x: 10, y: 20, z: 30}

Answer 4

It doesn’t seem conveniently possible. What can you do? Something horrible, as always.

let tuple = (function() {
    let map = new Map();

    function tuple() {
        let current = map;
        let args = Object.freeze(Array.prototype.slice.call(arguments));

        for (let item of args) {
            if (current.has(item)) {
                current = current.get(item);
            } else {
                let next = new Map();
                current.set(item, next);
                current = next;
            }
        }

        if (!current.final) {
            current.final = args;
        }

        return current.final;
    }

    return tuple;
})();

And voilà.

let m = new Map();
m.set(tuple(3, 5), [tuple(3, 5, 3), tuple(3, 5, 4)]);
m.get(tuple(3, 5)); // [[3, 5, 3], [3, 5, 4]]