fast-bitset
A fast bitset with some nice methods.
##Features
- Outperforms all other bitset packages in terms of speed and space
- All bit operations execute in O(1) time (does not iterate through bits)
- Useful methods for graph algorithms
- Any array that stores booleans can safely be replaced by a bitset for improved speed
- Uses 64x less space than a nontyped array
##Installation
npm install fast-bitset --save
##License MIT
##API
- BitSet
- new BitSet(nBitsOrKey)
- .get(idx) ⇒
boolean
- .set(idx) ⇒
boolean
- .setRange(from, to) ⇒
boolean
- .unset(idx) ⇒
boolean
- .unsetRange(from, to) ⇒
boolean
- .toggle(idx) ⇒
boolean
- .toggleRange(from, to) ⇒
boolean
- .clear() ⇒
boolean
- .clone() ⇒
BitSet
- .dehydrate() ⇒
string
- .and(bs) ⇒
BitSet
- .or(bs) ⇒
BitSet
- .xor(bs) ⇒
BitSet
- .forEach(func)
- .getCardinality() ⇒
number
- .getIndices() ⇒
Array
- .isEmpty() ⇒
boolean
- .isEqual(bs) ⇒
boolean
- .toString() ⇒
string
- .ffs(_startWord) ⇒
number
- .ffz(_startWord) ⇒
number
- .fls(_startWord) ⇒
number
- .flz(_startWord) ⇒
number
- .nextSetBit(idx) ⇒
number
- .nextUnsetBit(idx) ⇒
number
- .previousSetBit(idx) ⇒
number
- .previousUnsetBit(idx) ⇒
number
new BitSet(nBitsOrKey)
Create a new bitset. Accepts either the maximum number of bits, or a dehydrated bitset
Param | Type | Description |
---|---|---|
nBitsOrKey | number | string |
Number of bits in the set or dehydrated bitset. For speed and space concerns, the initial number of bits cannot be increased. |
boolean
bitSet.get(idx) ⇒ Check whether a bit at a specific index is set
Kind: instance method of BitSet
Returns: boolean
- true if bit is set, else false
Param | Type | Description |
---|---|---|
idx | number |
the position of a single bit to check |
boolean
bitSet.set(idx) ⇒ Set a single bit
Kind: instance method of BitSet
Returns: boolean
- true if set was successful, else false
Param | Type | Description |
---|---|---|
idx | number |
the position of a single bit to set |
boolean
bitSet.setRange(from, to) ⇒ Set a range of bits
Kind: instance method of BitSet
Returns: boolean
- true if set was successful, else false
Param | Type | Description |
---|---|---|
from | number |
the starting index of the range to set |
to | number |
the ending index of the range to set |
boolean
bitSet.unset(idx) ⇒ Unset a single bit
Kind: instance method of BitSet
Returns: boolean
- true if set was successful, else false
Param | Type | Description |
---|---|---|
idx | number |
the position of a single bit to unset |
boolean
bitSet.unsetRange(from, to) ⇒ Unset a range of bits
Kind: instance method of BitSet
Returns: boolean
- true if set was successful, else false
Param | Type | Description |
---|---|---|
from | number |
the starting index of the range to unset |
to | number |
the ending index of the range to unset |
boolean
bitSet.toggle(idx) ⇒ Toggle a single bit
Kind: instance method of BitSet
Returns: boolean
- true if set was successful, else false
Param | Type | Description |
---|---|---|
idx | number |
the position of a single bit to toggle |
boolean
bitSet.toggleRange(from, to) ⇒ Toggle a range of bits
Kind: instance method of BitSet
Returns: boolean
- true if set was successful, else false
Param | Type | Description |
---|---|---|
from | number |
the starting index of the range to toggle |
to | number |
the ending index of the range to toggle |
boolean
bitSet.clear() ⇒ Clear an entire bitset
Kind: instance method of BitSet
Returns: boolean
- true
BitSet
bitSet.clone() ⇒ Clone a bitset
Kind: instance method of BitSet
Returns: BitSet
- an copy (by value) of the calling bitset
string
bitSet.dehydrate() ⇒ Turn the bitset into a comma separated string that skips trailing 0 words and ends with the MAX_BIT. Useful if you need the bitset to be an object key (eg dynamic programming) Can rehydrate by passing the result into the constructor
Kind: instance method of BitSet
Returns: string
- representation of the bitset
BitSet
bitSet.and(bs) ⇒ Perform a bitwise AND on two bitsets Both bitsets must have the same number of words, no length check is performed to prevent and overflow
Kind: instance method of BitSet
Returns: BitSet
- a new bitset that is the bitwise AND of the two
Param | Type |
---|---|
bs | BitSet |
BitSet
bitSet.or(bs) ⇒ Perform a bitwise OR on two bitsets Both bitsets must have the same number of words, no length check is performed to prevent and overflow
Kind: instance method of BitSet
Returns: BitSet
- a new bitset that is the bitwise OR of the two
Param | Type |
---|---|
bs | BitSet |
BitSet
bitSet.xor(bs) ⇒ Perform a bitwise XOR on two bitsets Both bitsets must have the same number of words, no length check is performed to prevent and overflow
Kind: instance method of BitSet
Returns: BitSet
- a new bitset that is the bitwise XOR of the two
Param | Type |
---|---|
bs | BitSet |
bitSet.forEach(func)
Run a custom function on every set bit. Faster than iterating over the entire bitset with a get()
Source code includes a nice pattern to follow if you need to break the for-loop eaarly
Kind: instance method of BitSet
Param | Type | Description |
---|---|---|
func | function |
the function to pass the next set bit to |
number
bitSet.getCardinality() ⇒ Get the cardinality (count of set bits) for the entire bitset
Kind: instance method of BitSet
Returns: number
- cardinality
Array
bitSet.getIndices() ⇒ Get the indices of all set bits. Useful for debugging, but if you can break early, make your own loop
Kind: instance method of BitSet
Returns: Array
- Indices of all set bits
boolean
bitSet.isEmpty() ⇒ Quickly determine if a bitset is empty
Kind: instance method of BitSet
Returns: boolean
- true if the entire bitset is empty, else false
boolean
bitSet.isEqual(bs) ⇒ Quickly determine if both bitsets are equal (faster than checking if the XOR of the two is === 0) Both bitsets must have the same number of words, no length check is performed to prevent and overflow
Kind: instance method of BitSet
Returns: boolean
- true if the entire bitset is empty, else false
Param | Type |
---|---|
bs | BitSet |
string
bitSet.toString() ⇒ Get a string representation of the entire bitset, including leading 0s (useful for debugging)
Kind: instance method of BitSet
Returns: string
- a base 2 representation of the entire bitset
number
bitSet.ffs(_startWord) ⇒ Find first set bit (useful for processing queues, breadth-first tree searches, etc.)
Kind: instance method of BitSet
Returns: number
- the index of the first set bit in the bitset, or -1 if not found
Param | Type | Description |
---|---|---|
_startWord | number |
the word to start with (only used internally by nextSetBit) |
number
bitSet.ffz(_startWord) ⇒ Find first zero (unset bit)
Kind: instance method of BitSet
Returns: number
- the index of the first unset bit in the bitset, or -1 if not found
Param | Type | Description |
---|---|---|
_startWord | number |
the word to start with (only used internally by nextUnsetBit) |
number
bitSet.fls(_startWord) ⇒ Find last set bit
Kind: instance method of BitSet
Returns: number
- the index of the last set bit in the bitset, or -1 if not found
Param | Type | Description |
---|---|---|
_startWord | number |
the word to start with (only used internally by previousSetBit) |
number
bitSet.flz(_startWord) ⇒ Find last zero (unset bit)
Kind: instance method of BitSet
Returns: number
- the index of the last unset bit in the bitset, or -1 if not found
Param | Type | Description |
---|---|---|
_startWord | number |
the word to start with (only used internally by previousUnsetBit) |
number
bitSet.nextSetBit(idx) ⇒ Find first set bit, starting at a given index
Kind: instance method of BitSet
Returns: number
- the index of the next set bit >= idx, or -1 if not found
Param | Type | Description |
---|---|---|
idx | number |
the starting index for the next set bit |
number
bitSet.nextUnsetBit(idx) ⇒ Find first unset bit, starting at a given index
Kind: instance method of BitSet
Returns: number
- the index of the next unset bit >= idx, or -1 if not found
Param | Type | Description |
---|---|---|
idx | number |
the starting index for the next unset bit |
number
bitSet.previousSetBit(idx) ⇒ Find last set bit, up to a given index
Kind: instance method of BitSet
Returns: number
- the index of the next unset bit <= idx, or -1 if not found
Param | Type | Description |
---|---|---|
idx | number |
the starting index for the next unset bit (going in reverse) |
number
bitSet.previousUnsetBit(idx) ⇒ Find last unset bit, up to a given index
Kind: instance method of BitSet
Returns: number
- the index of the next unset bit <= idx, or -1 if not found
Param | Type | Description |
---|---|---|
idx | number |
the starting index for the next unset bit (going in reverse) |