Re: Web IDL maplike: Allow spec prose to specify how key-type should be compared?

On Mon, Mar 2, 2015 at 3:08 PM, Tab Atkins Jr. <jackalmage@gmail.com> wrote:

> On Mon, Mar 2, 2015 at 2:28 PM, David Dorwin <ddorwin@google.com> wrote:
>
[...]

> Given that this is backed by a Map, I don't think we can realistically
> do this until Maps gain the ability to specify a key comparator.
>



The following code is untested, and was written only to play with an idea
provoked by this thread. It may also be besides the actual point of this
thread, but...



/*
 * Makes a projection from keys to ids.
 *
 * Given the usual kind of comparator, with the signature
 *
 * interface Comparator<K> {
 *   hash(k :K) :value;
 *   eq(k1 :K, k2 :K) :boolean;
 * }
 *
 * with the usual contract that eq forms an equivalence class of Ks,
 * and hash is a many-to-one mapping from these equivalence classes to
 * hashable non-object values of some sort, like numbers. Let's call
 * the K objects that a given comparator compares "keys". We assume
 * here that keys are genuine objects and so can be used as keys in
 * WeakMaps.
 *
 * For objects, EcmaScript 2015 Maps map from object identities
 * to values. Let's call an empty object whose only purpose is to have
 * a unique identity, for use as keys in these Map objects, an "id".
 *
 * makeProjector, given a comparator, returns a project function which
 * projects keys to ids. Like the comparator's hash, it maps all keys
 * in the same equivalence class (as defined by the comparator) into
 * the same id. Unlike the comparator's hash, the mapping from
 * equivalence class to id is one-to-one.
 */

const projectors = new WeakMap();

function makeProjector(comparator) {
  if (projectors.has(comparator)) {
    // Caching the comparator-to-projector mapping does much more than
    // save the trivial effort to make a new projector. It means that
    // all the projecting for a given comparator gets to share the
    // same idCache.
    return projectors.get(comparator);
  }
  const buckets = new Map();
  const idCache = new WeakMap();
  function project(key) {
    if (idCache.has(key)) {
      // Thus, *for any given key object, we only use the comparator*
*      // the first time we project it*.
      return idCache.get(key);
    }
    const hash = comparator.hash(key);
    let bucket = void 0;
    let id = void 0;
    findId: if (buckets.has(hash)) {
      const bucket = buckets.get(hash);
      for (let [k,i] of bucket) {
        if (comparator.eq(key, k)) {
          id = i;
          break findId;
        }
      }
      id = Object.freeze(Object.create(null));
      bucket.push([key,id]);
    } else {
      id = Object.freeze(Object.create(null));
      buckets.set(hash, [[key,id]]);
    }
    idCache.set(key, id);
    return id;
  }
  projectors.set(comparator, Object.freeze(project));
  return project;
}




/*
 * Uses makeProjector to make the obvious Map wrapper
 */
function Mapish(comparator) {
  const project = makeProjector(comparator);
  const map = new Map();
  return Object.freeze({
    has(key) { return map.has(project(key)); }
    get(key) { return map.get(project(key)); }
    set(key,v) { map.set(project(key),v); }
    delete(key) { map.delete(project(key)); }
  });
}