Mnemonist

MultiSet


A MultiSet is like a Set excepts it is able to store items more than once and is therefore able to count them.

For more information about the MultiSet, you can head here.

const MultiSet = require('mnemonist/multi-set');

Constructor

The MultiSet takes no argument.

Static #.from

Alternatively, one can build a MultiSet from an arbitrary JavaScript iterable likewise:

const set = MultiSet.from([1, 2, 3]);

Members

Methods

Mutation

Read

Iteration

Helpers

Static methods dealing with multisets.

#.dimension

Number of distinct items in the set.

const set = new MultiSet();

set.add('hello');
set.add('hello');

set.dimension
>>> 1

#.size

Total number of items in the set.

const set = new MultiSet();

set.add('hello');
set.add('hello');

set.size
>>> 2

#.add

Adds the item to the set. Optionally, you can provide a number which is the number of times the same item is added.

Adding an item 0 times is a no-op.

Adding an item a negative number of times will remove items.

O(1)

const set = new MultiSet();

set.add('hello');

// Adding "hello" more than once
set.add('hello', 3);

#.set

Sets the multiplicity of an item in the set.

Setting the multiplicity of an item to be 0 or a negative number will remove said item from the set.

O(1)

const set = new MultiSet();

set.set('hello', 4);
set.multiplicity('hello');
>>> 4

#.remove

Removes the item from the set once. Optionally, you can provide a number which is the number of times the same item is removed.

Removing an item 0 times is a no-op.

Removing an item a negative number of times will add items.

O(1)

const set = new MultiSet();

set.add('hello', 3);

set.remove('hello');
set.multiplicity('hello');
>>> 2

set.remove('hello', 2);
set.multiplicity('hello');
>>> 0

#.delete

Removes all the occurrences of the given item from the set.

O(1)

const set = new MultiSet();

set.add('hello');
set.add('hello');

set.delete('hello');
set.multiplicity('hello');
>>> 0

#.edit

Edit an item to become another one. If the item does not exist in the set, this will do nothing. If target item already exist in the set, multiplicities will be merged.

O(1)

const set = new MultiSet();

set.add('a');
set.add('b');

set.edit('a', 'c'); // 'a' becomes 'c' in the set
set.has('a');
>>> false

set.edit('c', 'b'); // 'c' becomes 'b', totalling 2 occurrences
set.has('c');
>>> false
set.multiplicity('b');
>>> 2

#.clear

Completly clears the set of all its items.

const set = new MultiSet();

set.add('hello');
set.clear();

set.size
>>> 0

#.count

Same as #.multiplicity below.

#.frequency

Returns the frequency of the given item in the set.

O(1)

const set = new MultiSet();

set.add('apple', 5);
set.add('pear', 2);
set.add('melon', 3);

set.frequency('apple');
>>> 0.5

#.has

Returns whether the given item is found in the set.

O(1)

const set = new MultiSet();

set.add('hello');
set.has('hello');
>>> true

set.has('world');
>>> false

#.get

Same as #.multiplicity below.

#.multiplicity

Returns the number of times the given item is found in the set.

O(1)

const set = new MultiSet();

set.add('hello');
set.multiplicity('hello');
>>> 1

#.top

Retrieves the top k items with their assorted count in sorted order.

O(n log k) time

O(k) memory

const set = MultiSet.from('So-many-letters-in-this-boring-string.');
set.top(3);
>>> [['-', 6], ['t', 4], ['n', 4]]

#.forEach

Iterates over each of the items stored by the set.

const set = new MultiSet();

set.add('hello');
set.add('hello');

set.forEach((value) => {
  console.log(value);
});
>>> 'hello'
>>> 'hello'

#.forEachMultiplicity

Iterates over each of the multiplicities stored by the set.

const set = new MultiSet();

set.add('hello');
set.add('hello');
set.add('world');

set.forEachMultiplicity((count, key) => {
  console.log(key, count);
});
>>> 'hello', 2
>>> 'world', 1

#.keys

Returns an iterator over the set’s keys, i.e. the set’s unique values.

const set = new MultiSet();

set.add('hello', 4);
set.add('world', 5);

const iterator = set.keys();

iterator.next().value
>>> 'hello'
iterator.next().value
>>> 'world'

#.values

Returns an iterator over the set’s repeated values.

const set = new MultiSet();

set.add('hello', 2);
set.add('world');

const iterator = set.values();

iterator.next().value
>>> 'hello'
iterator.next().value
>>> 'hello'

#.multiplicities

Returns an iterator over the set’s multiplicities.

const set = new MultiSet();

set.add('hello');
set.add('hello');

const iterator = set.multiplicities();

iterator.next().value
>>> ['hello', 2]

Iterable

Alternatively, you can iterate over a set’s values using ES2015 for...of protocol:

const set = new MultiSet();

set.add('hello');
set.add('hello');

for (const value of set) {
  console.log(value);
}



isSubset

Static method returning whether the first multiset is a subset of the second.

const letters = MultiSet.from('aaabbc');
const lessLetters = MultiSet.from('aab');

MultiSet.isSubset(lessLetters, letters);
>>> true

isSuperset

Static method returning whether the first multiset is a superset of the second.

const letters = MultiSet.from('aaabbc');
const lessLetters = MultiSet.from('aab');

MultiSet.isSuperset(letters, lessLetters);
>>> true