Neodymium Plated Magnet

    fast-bitset

    1.3.2 • Public • Published

    fast-bitset

    Build Status

    Join the chat at https://gitter.im/mattkrick/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

    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.

    bitSet.get(idx) ⇒ boolean

    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

    bitSet.set(idx) ⇒ boolean

    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

    bitSet.setRange(from, to) ⇒ boolean

    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

    bitSet.unset(idx) ⇒ boolean

    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

    bitSet.unsetRange(from, to) ⇒ boolean

    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

    bitSet.toggle(idx) ⇒ boolean

    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

    bitSet.toggleRange(from, to) ⇒ boolean

    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

    bitSet.clear() ⇒ boolean

    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

    bitSet.dehydrate() ⇒ string

    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)

    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 early

    Kind: instance method of BitSet

    Param Type Description
    func function the function to pass the next set bit to

    bitSet.getCardinality() ⇒ number

    Get the cardinality (count of set bits) for the entire bitset

    Kind: instance method of BitSet
    Returns: number - cardinality

    bitSet.getIndices() ⇒ Array

    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

    bitSet.isSubsetOf(bs) ⇒ Boolean

    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

    bitSet.isEmpty() ⇒ boolean

    Quickly determine if a bitset is empty

    Kind: instance method of BitSet
    Returns: boolean - true if the entire bitset is empty, else false

    bitSet.isEqual(bs) ⇒ boolean

    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

    bitSet.toString() ⇒ string

    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

    bitSet.ffs(_startWord) ⇒ number

    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)

    bitSet.ffz(_startWord) ⇒ number

    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)

    bitSet.fls(_startWord) ⇒ number

    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)

    bitSet.flz(_startWord) ⇒ number

    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)

    bitSet.nextSetBit(idx) ⇒ number

    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

    bitSet.nextUnsetBit(idx) ⇒ number

    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

    bitSet.previousSetBit(idx) ⇒ number

    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)

    bitSet.previousUnsetBit(idx) ⇒ number

    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)

    Install

    npm i fast-bitset

    DownloadsWeekly Downloads

    19

    Version

    1.3.2

    License

    MIT

    Last publish

    Collaborators

    • mattkrick