Designing a MultiMap (in DOM, would like to be consistent with ES)
On Fri, Nov 30, 2012 at 3:38 PM, Tab Atkins Jr. <jackalmage at gmail.com> wrote:
As I expressed in an earlier thread to es-discuss, Anne van Kesteren is currently writing the URL spec, and as part of that he's designing the URLQuery interface, which is essentially a MultiMap (a Map where one key can map to multiple values). I was convinced in the previous thread that trying to make a MultiMap a subclass of Map was a red herring, and that MultiMap should instead be a parallel class to Map, like Set is.
So, I've been working with Anne to design the URLQuery interface against a speculative future MultiMap API. I figured it would be a good idea to run it against es-discuss before we settle on it. ^_^
Note that right now, we've trimmed down the MultiMap features of URLQuery to the bare minimum necessary (getAll and append), to avoid forcing tc39's hand as much as possible.
Our approach is that MultiMap should be able to masquerade as a Map,
This means that you're still trying to make MultiMap a subtype of Map, whether it is a subclass or not. That herring still seems pink. But I'll go with this premise below.
adding the additional functionality in overloads or variant functions. Conceptually, imagine the MultiMap as an ordered list of (k,v) pairs, with no restriction (compare to Map, which places a restriction that there are no pairs with the same k).
get(k) => returns the value of the first (k,_) pair, or else undefined. getAll(k) => returns a (possibly empty) array of all values associated with the key
set(k,v) => finds the first (k,) pair, and replaces its value with v. Removes any other (k,) pairs. If there were no (k,) pairs, adds (k,v) to the end of the map. setAll(k, [v]) => replaces (k,) pairs until either the input list or the existing pairs runs out. Removes any other (k,_) pairs. If there were leftover values, adds (k,v) pairs to the end of the map.
append(k,v) => adds (k,v) to the end of the map. appendAll(k,[v]) => adds multiple values. Needed?
has(k, v?) => return true/false if a (k,_) pair is in the map. If the second arg is provided, returns true/false if (k,v) is in the map.
delete(k, v?) => removes all (k,_) pairs from the map. If the second arg is provided, removes only the (k,v) pairs.
For iterators, obviously keys() would only return unique keys.
That seems to conflict with the spirit of the rest of your design. Continue to think of the MultiMap as an ordered list of k,v pairs. keys() should return all the successive k elements in order, including duplicates. values() does likewise for the v elements, and items() does likewise for the pairs. Everything is parallel, has the same cardinality and order, and zips up just fine.
On Fri, Nov 30, 2012 at 3:53 PM, Mark S. Miller <erights at google.com> wrote:
On Fri, Nov 30, 2012 at 3:38 PM, Tab Atkins Jr. <jackalmage at gmail.com> wrote:
Our approach is that MultiMap should be able to masquerade as a Map,
This means that you're still trying to make MultiMap a subtype of Map, whether it is a subclass or not. That herring still seems pink. But I'll go with this premise below.
It's useful for URLQuery, where for a lot of cases you don't need the MultiMap functionality, just a Map, but there are plenty of edge cases (reasonably common ones) where you do need that functionality. So, best of both worlds - when you don't care, you can just treat it as a Map. When you do care, you're covered for that too.
I figure if it's useful for URLQuery, there's a decent change it's useful for others, too, and it has only a small impact on the API.
For iterators, obviously keys() would only return unique keys.
That seems to conflict with the spirit of the rest of your design. Continue to think of the MultiMap as an ordered list of k,v pairs. keys() should return all the successive k elements in order, including duplicates. values() does likewise for the v elements, and items() does likewise for the pairs. Everything is parallel, has the same cardinality and order, and zips up just fine.
That's possible, but it means that you can't iterate through keys() and query the map with the values. That may or may not be an issue. I'm fine either way, but if we do that, we definitely want a secondary items() iterator that groups the values together.
Perhaps consider .push(key, …values) instead of .append(key, value) and .appendAll(key, values).
I’ve seen this kind of MultiMap around, so I presume people like the heterogenous range type. I’ve gone a different way in my work, where MultiMap was a Map that would set the value for a missing key to an empty array. Then, extended Array to have a "one" or "only" method.
getAll(key) ~ get(key) get(key) ~ get(key).one() setAll(key, values) ~ set(key, values) set(key, value) ~ set(key, [value]) append(key, value) ~ get(key).push(value) appendAll(key, values) ~ get(key).push(...values)
For the URL use case, this loses information about interleaving of keys, which is usually unimportant except (perhaps) in making round trips between parse and stringify.
Kris Kowal
I've written up the proposal properly as executable code, a la the Map proposal:
/** A non-stupid alternative to Array.prototype.indexOf */ function indexOfIdentical(keys, key) { for (var i = 0; i < keys.length; i++) { if (keys[i] is key) { return i; } } return -1; }
import {Name} from '@name'; const keysName = new Name; // These should be non global. const valsName = new Name;
class MultiMap { constructor(iterable = []) { this[keysName] = []; this[valsName] = []; for (let [k, v] of iterable) { this.append(k, v); } } get(key) { const keys = this[keysName]; const i = indexOfIdentical(keys, key); return i < 0 ? undefined : this[valsName][i]; } getAll(key) { const keys = this[keysName]; const vals = this[valsName]; const arr = []; for(var i = 0; i < keys.length; i++) { if(keys[i] is key) { arr.push(vals[i]); } } return arr; } has(key, ...val) { const keys = this[keysName]; if(val.length == 0) { return indexOfIdentical(keys, key) >= 0; } else { const vals = this[valsName]; for(const [i,k] of keys) { if(k is key && vals[i] is val[0]) { return true; } } return false; } } set(key, ...val) { const keys = this[keysName]; const vals = this[valsName]; var vali = 0; for(var i = 0; i < keys.length; i++) { if(keys[i] is key) { if(vali < val.length) { vals[i] = val[vali]; vali++; } else { keys.splice(i,1); vals.splice(i,1); i--; } } } if(vali < val.length) { this.push(key, ...val.slice(vali)); } return this; } append(key, ...val) { const keys = this[keysName]; const vals = thsi[valsName]; val.forEach((e)=>{keys.push(key); vals.push(val);}); return this; } delete(key, ...val) { const keys = this[keysName]; const vals = this[valsName]; for(let i = 0; i < keys.length; i++) { if(keys[i] is key && (val.length == 0 || indexOfIdentifical(val,vals[i]) >= 0)) keys.splice(i,1); vals.splice(i,1); i--; } } return this; } *items() { for (var i = 0; i < this[keysName].length; i++) { yield [this[keysName][i], this[valsName][i]]; } } *groupedItems() { var seenAlready = new Set(); var keys = this[keysName]; for(var i = 0; i < keys.length; i++) { if(seenAlready.has(keys[i])) continue; seenAlready.add(keys[i]); yield [keys[i], this.getAll(keys[i])]; } } *keys() { for (var i = 0; i < this[keysName].length; i++) { yield this[keysName][i]; } } *values() { for (var i = 0; i < this[keysName].length; i++) { yield this[valsName][i]; } } }
Object.defineProperty(MultiMap.prototype, "iterator", {configurable: true, writable: true, value: MultiMap.prototype.items});
Changes from the initial proposal:
- I've eliminated every *All method except getAll, and replaced them by just making the normal methods variadic, as implicitly suggested by Kris. I expect the spread operator to solve the "but I've got an array of values!" problem elegantly, but until then .apply will work.
- I've added a groupedItems generator, which returns only unique keys along with an array of all associated values.
I've kept append rather than changing to push as Kris suggests. There's already not any agreement about what this kind of method should be called in ES (it's Array#push, but Set#add), while the DOM has generally standardized on "append" as the verb for this kind of thing. As well, the fact that it has a distinguished key argument makes it kinda different from Array#push.
Any further thoughts? If not, we'll go forward with this design in the URL spec, and hopefully when TC39 fills in behind us with a MultiMap class it can match up with what we've done.
Correct me if this stuff isn't actually going to end up as ES6, but my reading of meeting notes from July? indicate this is in:
Instead of
import {Name} from '@name'; const keysName = new Name; // These should be non global. const valsName = new Name; class MultiMap { ... }
You can do
class MultiMap { private @keys, @vals; .... }
And change anything like "this[keysName]" to "this. at keys"
Also "iterator" will be a public symbol (or whatever "public" ends up being named) that can be imported from '@iter'.
On Mon, Dec 3, 2012 at 10:08 AM, Brandon Benvie <brandon at brandonbenvie.com> wrote:
Correct me if this stuff isn't actually going to end up as ES6, but my reading of meeting notes from July? indicate this is in:
Instead of
import {Name} from '@name'; const keysName = new Name; // These should be non global. const valsName = new Name; class MultiMap { ... }
You can do
class MultiMap { private @keys, @vals; .... }
And change anything like "this[keysName]" to "this. at keys"
Also "iterator" will be a public symbol (or whatever "public" ends up being named) that can be imported from '@iter'.
Yes, I was just copying the code from the current Map wiki page and doing the minimal edits. I'm aware that several parts of it have changed, but didn't consider it worthwhile to figure out exactly what to change it to. You obviously knew what I meant. ^_^
As I expressed in an earlier thread to es-discuss, Anne van Kesteren is currently writing the URL spec, and as part of that he's designing the URLQuery interface, which is essentially a MultiMap (a Map where one key can map to multiple values). I was convinced in the previous thread that trying to make a MultiMap a subclass of Map was a red herring, and that MultiMap should instead be a parallel class to Map, like Set is.
So, I've been working with Anne to design the URLQuery interface against a speculative future MultiMap API. I figured it would be a good idea to run it against es-discuss before we settle on it. ^_^
Note that right now, we've trimmed down the MultiMap features of URLQuery to the bare minimum necessary (getAll and append), to avoid forcing tc39's hand as much as possible.
Our approach is that MultiMap should be able to masquerade as a Map, adding the additional functionality in overloads or variant functions. Conceptually, imagine the MultiMap as an ordered list of (k,v) pairs, with no restriction (compare to Map, which places a restriction that there are no pairs with the same k).
get(k) => returns the value of the first (k,_) pair, or else undefined.
getAll(k) => returns a (possibly empty) array of all values associated
with the key
set(k,v) => finds the first (k,_) pair, and replaces its value with v.
Removes any other (k,) pairs. If there were no (k,) pairs, adds (k,v) to the end of the map. setAll(k, [v]) => replaces (k,_) pairs until either the input list or
the existing pairs runs out. Removes any other (k,_) pairs. If there were leftover values, adds (k,v) pairs to the end of the map.
append(k,v) => adds (k,v) to the end of the map.
appendAll(k,[v]) => adds multiple values. Needed?
has(k, v?) => return true/false if a (k,_) pair is in the map. If the
second arg is provided, returns true/false if (k,v) is in the map.
delete(k, v?) => removes all (k,_) pairs from the map. If the second
arg is provided, removes only the (k,v) pairs.
For iterators, obviously keys() would only return unique keys. Unsure whether values() should return individual values, or arrays of values associate with each key (and same for items()). I lean toward the latter, so that the iterators returned by keys() and values() are comparable (zipping them gets you the same value as calling items()). Would we want a second items()-like iterator that returns the individual (k,v) pairs?
Thoughts?