10

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.

1
  • 1
    The default .has() on a Set object looks for the physical same object, not any old object with the same properties. So, you can't directly use the existing .has() for this. It looks like hev's answer is probably your best bet.
    – jfriend00
    Jul 30, 2020 at 22:08

5 Answers 5

5

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

4
  • This is good, thanks. I still wonder if there is a way to do this without strings to avoid that time/space inefficiency.
    – DavidXYZ
    Jul 30, 2020 at 19:33
  • 1
    @DavidXYZ There isn't really any easier way. Jul 30, 2020 at 19:35
  • @DavidXYZ Would you prefer using something like a hash set? Jul 31, 2020 at 23:51
  • 1
    the fact that there is literally no substitute for comparable tuples in javascript is absolutely insane
    – Nearoo
    Feb 13, 2022 at 23:02
3

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();
  })
})
2

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.

2

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]
0

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.

1

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.