Mnemonist

BitVector

The BitVector is the same thing as the BitSet, except it can grow dynamically if required.

const BitVector = require('mnemonist/bit-set');

Constructor

const vector = new BitVector(length);

Members

Methods

Mutation

Read

Iteration

#.array

The underlying Uint8Array.

const vector = new BitVector(19);

vector.array;
>>> Uint8Array [0, 0, 0]

#.capacity

Number of bits that can be stored by the vector before needing to reallocate memory.

Note that since bits are stored on the bytes of a Uint32Array, capacity will snap at the nearest multiple of 32.

const vector = new BitVector(53);

vector.capacity
>>> 64

#.length

Length of the set, that is to say the number of bits stored by the vector.

const vector = new BitVector(4);

vector.length;
>>> 4

#.size

Number of bits set, that is to say the total number of ones stored by the vector.

const vector = new BitVector(4);

vector.size;
>>> 0

vector.flip(2);

vector.size;
>>> 1

#.grow

Applies the growing policy once and reallocates the underlying vector.

If given a number, will run the growing policy until we attain a suitable capacity.

const vector = new BitVector();

vector.grow();

// Grow until we can store at least 100 items:
vector.grow(100);

#.pop

Removes the last value from the vector and returns it.

Note that this method won’t deallocate memory. You can use #.reallocate for that.

O(1)

const vector = new BitVector();

vector.push(1);
vector.push(1);

vector.pop();
>>> 1

#.push

Push a bit into the vector.

O(1) amortized

const vector = new BitVector();

vector.push(1);
vector.push(false);

#.set

Sets the bit at the given index. Optionally you can indicate the bit’s value (0, 1, true or false).

O(1)

const vector = new BitVector(4);

vector.set(3);
vector.test(3);
>>> true

vector.set(3, false);
vector.test(3);
>>> false

#.reallocate

Reallocates the underlying array and truncates length if needed.

const vector = new BitVector();

vector.reallocate(75);

vector.set(7);

// This will truncate length
vector.reallocate(23);

#.reset

Resets the bit at the given index, meaning setting it to 0.

O(1)

const vector = new BitVector(4);

vector.set(3);
vector.reset(3);
vector.test(3);
>>> false

#.resize

Resize the vector’s length. Will reallocate if current capacity is insufficient.

Note that it won’t deallocate if the given length is inferior to the current one. You can use #.reallocate for that.

const vector = new BitVector(10);

vector.resize(5);
vector.length;
>>> 5
vector.capacity;
>>> 32

// This will reallocate
vector.resize(45);
vector.length;
>>> 45
vector.capacity;
>>> 64

#.flip

Toggles the bit at the given index.

O(1)

const vector = new BitVector(4);

vector.flip(3);
vector.test(3);
>>> true
vector.flip(3)
vector.test(3);
>>> false

#.clear

Resets every bit stored by the vector.

const vector = new BitVector(4);

vector.set(1);
vector.set(3);

vector.clear();
vector.size
>>> 0

#.get

Returns the bit at the given index.

O(1)

const vector = new BitVector(4);

vector.set(1);

vector.get(1);
>>> 1

vector.get(3);
>>> 0

#.rank

Returns the number of bits set to 1 up to (but not including) the provided index.

O(i), i being the provided index.

const vector = new BitVector(4);

vector.set(1);
vector.set(2);

vector.rank(1);
>>> 0
vector.rank(3);
>>> 2

#.select

Returns the index of the nth bit set to 1 in the vector.

O(n)

const vector = new BitVector(4);

vector.set(0);
vector.set(2);

vector.select(1);
>>> 0
vector.select(2);
>>> 2

#.test

Test the bit at the given index, returning a boolean.

O(1)

const vector = new BitVector(4);

vector.set(1);

vector.test(1);
>>> true

vector.test(3);
>>> false

#.forEach

Iterates over the set’s bits.

const vector = new BitVector(4);

vector.set(1);

vector.forEach((bit, i) => {
  console.log(bit, i);
});

#.values

Returns an iterator over the set’s values.

const vector = new BitVector(4);

vector.set(1);

const iterator = vector.values()

iteraror.next().value
>>> 0

#.entries

Returns an iterator over the set’s entries.

const vector = new BitVector(4);

vector.set(0);

const iterator = vector.entries()

iteraror.next().value
>>> [0, 1]

iterator.next().value
>>> [1, 0]

Iterable

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

const vector = new BitVector(4);

for (const bit of vector) {
  console.log(bit);
}