What is the best way to implement a Set of coordinates in JavaScript? I would like to be able to do things like:
let s=new Set();
s.add([1,1]);
if (s.has([1,1])) // false, since these are different arrays
The above doesn't work, since the Set is storing a reference to the array instead of the contents.
You can subclass Set for more flexibility.
class ObjectSet extends Set{
add(elem){
return super.add(typeof elem === 'object' ? JSON.stringify(elem) : elem);
}
has(elem){
return super.has(typeof elem === 'object' ? JSON.stringify(elem) : elem);
}
}
let s=new ObjectSet();
s.add([1,1]);
console.log(s.has([1,1]))
console.log(s.has([1,2,3]));
console.log([...s]);
console.log([...s].map(JSON.parse));//get objects back
I was building a game when I came across this problem.
Here's a typescript class that might be able to help you. It uses a tree to do its magic.
You should be able to easily modify this to use arrays instead of the x and y parameters
// uses an internal tree structure to simulate set-like behaviour
export default class CoordinateSet {
tree: Record<number, Record<number, boolean>> = {}
add(x: number, y: number) {
this.tree[x] ||= {}
this.tree[x][y] = true;
}
remove(x: number, y: number) {
// if the coordinate doesn't exist, don't do anything
if (!this.tree[x] || !this.tree[y]) {
return;
}
// otherwise, delete it
delete this.tree[x][y];
// if the branch has no leaves, delete the branch, too
if (!Object.keys(this.tree[x]).length) {
delete this.tree[x]
}
}
has(x: number, y: number) {
return !!this.tree[x]?.[y];
}
}
And tests, which will also show you how it works:
import CoordinateSet from "./CoordinateSet";
describe("CoordinateSet", () => {
it("Can add a coordinate", () => {
const cs = new CoordinateSet();
expect(cs.has(1,1)).toBeFalsy();
cs.add(1, 1);
expect(cs.has(1,1)).toBeTruthy();
});
it("Can remove a coordinate", () => {
const cs = new CoordinateSet();
cs.add(1, 1);
expect(cs.has(1,1)).toBeTruthy();
cs.remove(1,1);
expect(cs.has(1,1)).toBeFalsy();
})
})
This can be done with strings:
let s=new Set();
s.add("1,1");
s.add("2,2");
console.log(s.has("1,1"), s.has("1,2")); // true false
However, I would prefer to do this with some type of numeric tuple to avoid repeated string conversion logic.
If you only plan to store pairs of coords, another possibility is to use a combination of a Map (for the first coord) and a Set (for the second coord).
function TupleSet() {
this.data = new Map();
this.add = function([first, second]) {
if (!this.data.has(first)) {
this.data.set(first, new Set());
}
this.data.get(first).add(second);
return this;
};
this.has = function([first, second]) {
return (
this.data.has(first) &&
this.data.get(first).has(second)
);
};
this.delete = function([first, second]) {
if (!this.data.has(first) ||
!this.data.get(first).has(second)
) return false;
this.data.get(first).delete(second);
if (this.data.get(first).size === 0) {
this.data.delete(first);
}
return true;
};
}
let mySet = new TupleSet();
mySet.add([0,2]);
mySet.add([1,2]);
mySet.add([0,3]);
console.log(mySet.has([1,3]));
console.log(mySet.has([0,2]));
mySet.delete([0,2]);
console.log(mySet.has([0,2]));Unfortunately, unlike a normal Set for which:
You can iterate through the elements of a set in insertion order. — MDN Set
This approach will, for the example above, iterate in the order:
[0,2]
[0,3]
[1,2]
If we can assume that our tuples are finite integers, they could be encoded as a float.
class TupleSet extends Set{
add(elem){
return super.add((typeof elem === 'object'
&& Number.isSafeInteger(elem[0])
&& Number.isSafeInteger(elem[1]))
? elem[0]+elem[1]/10000000 : elem);
}
has(elem){
return super.has((typeof elem === 'object'
&& Number.isSafeInteger(elem[0])
&& Number.isSafeInteger(elem[1]))
? elem[0]+elem[1]/10000000 : elem);
}
}
function TupleSetParse(elem){
return (Number.isFinite(elem)?
[Math.round(elem),Math.round((elem-Math.round(elem))*10000000)]:elem);
}
let s=new TupleSet();
s.add([1,5]);
s.add([1000000,1000000]);
s.add([-1000000,-1000000]);
console.log(s.has([1,5])); // true
console.log(s.has([1,2])); // false
console.log([...s].map(TupleSetParse));
// [ [ 1, 5 ], [ 1000000, 1000000 ], [ -1000000, -1000000 ] ]
Of course, this is limited in range. And it is fragile to some malformed input, so additional error checking should be added. However, after some testing, this method is only 25% better in speed and memory usage than the JSON.stringify approach. So, JSON is the preferred approach.