- From: Mark S. Miller <erights@google.com>
- Date: Mon, 2 Mar 2015 16:45:03 -0800
- To: "Tab Atkins Jr." <jackalmage@gmail.com>
- Cc: David Dorwin <ddorwin@google.com>, public-script-coord <public-script-coord@w3.org>, Boris Zbarsky <bzbarsky@mit.edu>
- Message-ID: <CABHxS9hHM5=12BPyK_kf0X5Tbd_d-qmtWp1t-iU5Wnrb19yn5Q@mail.gmail.com>
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)); } }); }
Received on Tuesday, 3 March 2015 00:45:32 UTC