CODEWITHSUNDEEP
javascriptecmascript-6settuples
DavidXYZ
DavidXYZ

Reputation: 366

Set of Tuples in JavaScript?

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.

Upvotes: 13

Views: 8482

Answers (6)

Tomer Aberbach
Tomer Aberbach

Reputation: 646

You can use the keyalesce, which returns the same key for the same sequence of values, to solve this problem.

const set = new Set()
set.add(keyalesce([1, 1]))

console.log(set.has(keyalesce([1, 1])))
//=> true

See this post for how keyalesce works internally.

Upvotes: 2

Monarch Wadia
Monarch Wadia

Reputation: 4976

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

Upvotes: 3

vasilyrud
vasilyrud

Reputation: 855

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]

Upvotes: 4

DavidXYZ
DavidXYZ

Reputation: 366

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.

Upvotes: 0

Unmitigated
Unmitigated

Reputation: 89364

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

Upvotes: 6

DavidXYZ
DavidXYZ

Reputation: 366

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.

Upvotes: 2

Related Questions