Is there something like mulitiSet in JavaScript?

Question

I know that JavaScript now has sets, but I wonder if there is something to realize the function of multiSet, or if there is some framework that has the functions of multiset which I really need a lot.

Or I have to code it by myself to do the research of Red-Black Tree?

Saldivar

@jfriend00 Exactly this search brought me here, following your instructions would create an infinite loop :-) – Ellene

You don't need a redblack tree, what you could probably use is a sorted list, binary search, and a operator for merging sorted lists. – Tractile

Answer 1

There are no built-in multiset structure, but there are some libraries that have such:

• mnemonist → MultiSet
• TSTL → TreeMultiSet

Feel free to add your favorite library in this question.

Polemoniaceous

Answer 2

You can build your own multiset using the Builtin map type and numerical values:

class Multiset {
    _backing = new Map();
    add(value) {
        if (this._backing.has(value)) {
            this._backing.set(value, 1 + this._backing.get(value));
        } else {
            this._backing.set(value, 1);
        }
    }

    delete(value) {
        if (this._backing.get(value) > 0) {
            this._backing.set(value, this._backing.get(value) - 1);
        } else {
            //do nothing
        }
    }

    get(value) {
        if (this._backing.get(value) > 0) {
            return this._backing.get(value);
        } else {
            return 0;
        }
    }
}

Scales

Answer 3

This is an old question, but it came in at the top of my search. I've ended up using lodash (similar to underscore): For example,

_.countBy([1, 2, 1, 4, 4, 1])

gives the result

{ '1': 3, '2': 1, '4': 2 }

Quicktempered

Answer 4

this answer from @AlgorithmicCanary provides the right approach, but we can use more of JavaScript's features:

• We can define other methods that the native Set provides, like forEach, clear, size, [Symbol.iterator]. These should treat each of the key's occurrences individually.

• We could align the methods to fit the Set protocol, so that:

  • add returns the instance, and
  • delete returns the success of the deletion, and
  • the constructor accepts an iterable to populate the MultiSet

• We could really delete the Map entry when a count gets to zero, so that the has method on the underlying Map returns the expected result.

• get can benefit from the ?? operator, returning 0 for any key that does not exist.

• We can use private fields for the map and its size (cardinality).

Code:

class MultiSet {
    #size = 0        // Use private fields
    #map = new Map  
    
    constructor(iterable) { // Argument as the standard Set allows for
        for (const value of iterable) this.add(value);
    }
    
    add(value) {
        this.#map.set(value, (this.#map.get(value) ?? 0) + 1);
        this.#size++;
        return this; // As the standard Set does
    }

    delete(value) {
        const count = this.#map.get(value);
        if (!count) return false;
        if (count == 1) this.#map.delete(value);
        else this.#map.set(value, count - 1);
        this.#size--; 
        return true; // boolean: as the standard Set does
    }

    *[Symbol.iterator]() { // Make instance iterable
        for (let [key, count] of this.#map) {
            while (count-- > 0) yield key;
        }
    }
    
    forEach(cb, thisArg) {
        for (const key of this) cb.call(thisArg, key, key, this);
    }
    
    *entries() {
        for (const key of this) yield [key, key];
    }

    get(value) { return this.#map.get(value) ?? 0 }
    has(value) { return this.#map.has(value) }
    get size() { return this.#size; }
    keys()     { return this[Symbol.iterator]() }
    values()   { return this[Symbol.iterator]() }
    // Add other Set methods as they become availabe:
    // ...
}

// Demo
const ms = new MultiSet([1, 2, 1, 3, 1, 2]);
console.log("get(1) ==", ms.get(1)); // 3
console.log("has(3) ==", ms.has(3));
console.log("delete(3) ==", ms.delete(3)); // true
console.log("delete(3) ==", ms.delete(3)); // false
console.log("has(3) ==", ms.has(3));
console.log("get(3) ==", ms.get(3));
console.log("get(2) ==", ms.get(2));
console.log("Iteration of keys:")
console.log(...ms);

Caskey