Set Methods
Part III
Previously:
decided instance methods should use
internal slots on `this`, but should use the
public API on `arg`.
But how exactly do you access the public API?
Set.prototype.union = function(arg) {
let argIterator = %GetIterator(arg)%;
let resultList = new %List%;
for (let item of argIterator)
%AddItemToList%(resultList, item);
for (let item of this.[[SetData]])
%AddItemToList%(resultList, item);
let result = new %Set%;
result.[[SetData]] = resultList;
return result;
};
Set.prototype.union
Set.prototype.intersection = function(arg) {
let thisSize = this.[[SetData]].length;
let argSize = %ToNumber%(arg.size);
let argHas = %BoundFunctionCreate%(arg.has, arg, []);
let argIterator = %GetIterator%(arg);
let resultList = new %List%;
if (thisSize > argSize) {
for (let item of argIterator)
if (%ListContainsItem%(this.[[SetData]], item))
%AddItemToList%(resultList, item);
} else {
for (let item of this.[[SetData]])
if (argHas(item))
%AddItemToList%(resultList, item);
}
let result = new %Set%;
result.[[SetData]] = resultList;
return result;
};
Set.prototype.intersection
Why does the `.intersection` algorithm vary by size?
Because it's big-O worse if you don't.
Consider `small.intersect(large)` or `large.intersect(small)`.
Always iterating the argument means the first is slow.
Always doing membership tests on the argument means the second is slow.
We can't just convert the argument to a Set, because that requires iterating the whole argument, which is a potentially expensive operation we're trying to avoid.
So how do we access the public API?
Several options.
0: Using internal slots on the argument
Previously decided this was not acceptable (means you can't pass a Proxy for a Set, among other downsides).
Not revisiting this option.
1: `[Symbol.iterator]` and `.has`
This has IMO unacceptable behavior if you pass a Map.
map.has acts as if a Map is a Set of keys.
map[Symbol.iterator] does not: it returns entry objects.
First behavior means you get the intersection with the set of keys of the map. Second means you get the empty set.
1: `[Symbol.iterator]` and `.has`
So `set.intersection(map)` works sometimes:
only if `map.size >= set.size`. (!!!)
"Does it quack like a duck" should be a property of the interface of the argument, not its precise value.
2: `.keys` and `.has`
This means `union` and `intersection` perform iteration in a different way: seems bad.
Also has the same problem as Map for at least some userland types.
class IndexedSet {
#set = new Set;
#list = [];
get size() { return this.#set.size; }
add(v) {
if (!this.#set.has(v)) {
this.#set.add(v);
this.#list.push(v === 0 ? 0 : v);
}
}
// membership, consistent with `Symbol.iterator` but not `keys`
has(v) { return this.#set.has(v); }
at(i) { return this.#list.at(i); }
// indices, consistent with `at` but not `has`
keys() { return this.#list.keys(); }
[Symbol.iterator]() { return this.#list.values(); }
}
It's fine for Map or IndexedSet not to work
as an argument at all, but not for them
to only work sometimes.
This is a fundamental problem with using String-named methods for this API.
3: `[Symbol.iterator]` and `[Symbol.SetHas]`
Add a new Symbol (name/location TBD) for Set membership testing.
Map would not implement this symbol.
Now everything works.
3: `[Symbol.iterator]` and `[Symbol.SetHas]`
Maybe also do `[Symbol.SetSize]`?
4: Some other way to declare an object supports being passed to `.intersection` and `.difference`?
For example, a [Symbol.isSet] whose presence promises that .keys and .has are consistent.
This adds another observable property access.
Discussion
Where do the new symbols live?
Please not `Symbol`.
Maybe `Set.protocol.has`?
This will set precedent going forward.