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(bsOrIdx) ⇒
BitSet
- .or(bsOrIdx) ⇒
BitSet
- .xor(bsOrIdx) ⇒
BitSet
- .forEach(func)
- .circularShift(number) ⇒
Bitset
- .getCardinality() ⇒
number
- .getIndices() ⇒
Array
- .isSubsetOf(bs) ⇒
Boolean
- .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
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. |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
Clear an entire bitset
Kind: instance method of BitSet
Returns: boolean
- true
bitSet.clone() ⇒ BitSet
Clone a bitset
Kind: instance method of BitSet
Returns: BitSet
- an copy (by value) of the calling bitset
Turn the bitset into a comma separated string that skips leading & trailing 0 words. Ends with the number of leading 0s and 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.and(bsOrIdx) ⇒ BitSet
Perform a bitwise AND on 2 bitsets or 1 bitset and 1 index. 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 | Description |
---|---|---|
bsOrIdx | BitSet | Number |
a bitset or single index to check (useful for LP, DP problems) |
bitSet.or(bsOrIdx) ⇒ BitSet
Perform a bitwise OR on 2 bitsets or 1 bitset and 1 index. 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 | Description |
---|---|---|
bsOrIdx | BitSet | Number |
a bitset or single index to check (useful for LP, DP problems) |
bitSet.xor(bsOrIdx) ⇒ BitSet
Perform a bitwise XOR on 2 bitsets or 1 bitset and 1 index. 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 | Description |
---|---|---|
bsOrIdx | BitSet | Number |
a bitset or single index to check (useful for LP, DP problems) |
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 early
Kind: instance method of BitSet
Param | Type | Description |
---|---|---|
func | function |
the function to pass the next set bit to |
Circular shift bitset by an offset
Kind: instance method of BitSet
Returns: Bitset
- a new bitset that is rotated by the offset
Param | Type | Description |
---|---|---|
number | Number |
of positions that the bitset that will be shifted to the right. Using a negative number will result in a left shift. |
Get the cardinality (count of set bits) for the entire bitset
Kind: instance method of BitSet
Returns: number
- cardinality
Get the indices of all set bits. Useful for debugging, uses forEach
internally
Kind: instance method of BitSet
Returns: Array
- Indices of all set bits
Checks if one bitset is subset of another. Same thing can be done using and operation and equality check, but then new BitSet would be created, and if one is only interested in yes/no information it would be a waste of memory and additional GC strain.
Kind: instance method of BitSet
Returns: Boolean
- true
if provided bitset is a subset of this bitset, false
otherwise
Param | Type | Description |
---|---|---|
bs | BitSet |
a bitset to check |
Quickly determine if a bitset is empty
Kind: instance method of BitSet
Returns: boolean
- true if the entire bitset is empty, else false
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 |
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
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) |
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) |
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) |
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) |
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 |
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 |
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) |
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) |