How to create a collection holding tuples where each tuple must be unique?

Question

I'm using TypeScript and want to create a collection of objects. Each object has some properties. The combination of the properties must be unique inside the collection.

So these sample combinations would be valid

[
    [ 1, 2 ],
    [ 2, 1 ],
]

but adding another combination e.g. [ 1, 2 ] would throw an "key already exists" error.

Just as a sidenote: My question assumes there are 3 keys representing the "composite key". If there is a more flexible solution ... why not.

I tried to implement my own "map-like" structure as a showcase in JavaScript

class MyCollection {
  constructor() {
    this.items = [];
  }

  add(firstTupleItem, secondTupleItem, thirdTupleItem) {
    if (this.has(firstTupleItem, secondTupleItem, thirdTupleItem)) {
      console.log(`ERR: Combination of [${firstTupleItem}, ${secondTupleItem}, ${thirdTupleItem}] already exists!`);

      return;
    }

    console.log(`Added combination of [${firstTupleItem}, ${secondTupleItem}, ${thirdTupleItem}]`);

    this.items.push([firstTupleItem, secondTupleItem, thirdTupleItem]);
  }

  has(firstTupleItem, secondTupleItem, thirdTupleItem) {
    return this.items.some(item =>
      item[0] === firstTupleItem &&
      item[1] === secondTupleItem &&
      item[2] === thirdTupleItem);
  }
}

const myCollection = new MyCollection();

/* passes as expected */

myCollection.add(1, 2, 3);
myCollection.add(2, 1, 3);
myCollection.add(3, 1, 2);
myCollection.add(1, 3, 2);

/* fails as expected */

myCollection.add(1, 2, 3);

console.log(myCollection.items);

Using a map might be faster but the value side seems to be wasted

class MyCustomMap extends Map<[number, number, number], [number, number, number]> {
    addItem(item: [number, number, number]) {
        super.set(item, item);
    }
}

Do I have to implement such a collection on my own or are there any better solutions? (using TypeScript)

Answer 1

You basically want a Set, a JavaScript collection that contains at most one of any given value; if a value you add() to a Set is the same as one that already exists in the Set, nothing changes. Unfortunately, the definition of what makes two values "the same" is not what you want it to be. Set and the related Map collection use "same-value zero" equality. For primitives like string and number such equality is fine, but for objects like [1, 2] (yes, Arrays are objects in JS), it amounts to object identity equality, similar to what you get with === (the difference is only around NaN):

const a = [1, 2];
const b = [1, 2];
console.log(a === b); // false

const c = a;
console.log(a === c); // true
const a = [1, 2];

This kind of makes sense, especially in light of possible property writes:

a[1] = 100;
console.log(a); // [1, 100]
console.log(b); // [1, 2]
console.log(c); // [1, 100]

But since you're not planning to hold onto array references and modify their contents (are you?), you'd much rather have something like your own custom equality function, where two arrays are equal if their contents are equal.

And unfortunately, Set and Map do not support this directly.

---

If you want something like this, you'll need to implement it yourself. One way to do this is to come up with a function f() which converts your objects to a primitive key value such that f(o1) === f(o2) if and only if o1 and o2 should be considered "equal". The easiest way to do this for arrays-of-primitives is to use JSON.stringify().

So if your objects are of type Props:

type Props = [number, number, number];

Then the conversion function f() can be written as propsToKey():

function propsToKey(props: Props): string {
    return JSON.stringify(props);
}

Now, in your class, you hold onto a Set of those keys instead of the objects. Or, you can hold onto a Map keyed by the keys whose values are the objects, so you can still return the original object if you want. You wrap every Set method you care about in something that calls propsToKey() appropriately. Oh, and since it seems you want your add() method to take a variadic number of arguments (e.g., 3 for [number, number, number]) instead of an array, then we should use rest/spread syntax where appropriate.

Okay, let's do this to implement MyCollection:

class MyCollection {
    private items: Map<string, Props> = new Map();
    add(...props: Props) {
        this.items.set(propsToKey(props), props);
        return this;
    }
    clear() {
        this.items.clear();
    }
    delete(...props: Props) {
        return this.items.delete(propsToKey(props));
    }
    forEach(cb: (...props: Props) => void) {
        return this.items.forEach(v => cb(...v));
    }
    has(...props: Props) {
        return this.items.has(propsToKey(props));
    }
    get size() {
        return this.items.size;
    }
    values() {
        return this.items.values();
    }
}

Let's test it:

const myCollection = new MyCollection();
myCollection.add(1, 2, 3);
myCollection.add(2, 1, 3);
myCollection.add(3, 1, 2);
myCollection.add(1, 3, 2);
console.log(Array.from(myCollection.values())) // [[1, 2, 3], [2, 1, 3], [3, 1, 2], [1, 3, 2]] 

myCollection.add(1, 2, 3);
console.log(Array.from(myCollection.values())) // [[1, 2, 3], [2, 1, 3], [3, 1, 2], [1, 3, 2]] 

Looks good!

Playground link to code