BitMap64

Namespace: SnowBank.Buffers · struct

Implements: IFormattable, IReadOnlyList<bool>, IEnumerable<bool>, IEnumerable, IReadOnlyCollection<bool>

Represents a fixed-size bit map, backed by an array of 64-bit words

Constructors

BitMap64

BitMap64(long bits)

Initialize a new BitMap

bits — Minimum required capacity (in bits)

The internal capacity will always be rounded to the upper 64 bits. All bits will be cleared (0)

BitMap64(ulong[] words)

Initialize a Bitmap from an existing storage

words — Array of words used by this bitmap (each word storing 64 bits)

This Bitmap will mutate the content of . Likewise, any change made to will be visible from this instance

BitMap64(Memory<ulong> words)

Initialize a Bitmap from an existing storage

words — Array of words used by this bitmap (each word storing 64 bits)

This Bitmap will mutate the content of . Likewise, any change made to will be visible from this instance

Properties

Capacity

long Capacity { get; }

Returns the capacity (in bits) of this bitmap

Item

bool Item { get; set; }

Methods

BytesForCapacity

static uint BytesForCapacity(long capacity)

Returns the number of bytes required to store a bitmap of the specified capacity

capacity — Capacity (in bits) of the bitmap

Returns: Size (in bytes) of the buffer

Clear

void Clear(long bitIndex)

Clears a specific bit

static void Clear(Span<ulong> map, long bitIndex)

Clears a specific bit

void Clear(long bitIndex, long count)

Clears a range of bits

static void Clear(Span<ulong> map, long bitIndex, long count)

Clears a range of bits

ClearAll

void ClearAll()

Clears all bits of a map

static void ClearAll(Span<ulong> map)

Clears all bits of a map

ClearAndCount

void ClearAndCount(long bitIndex, ref long count)

Clears a specific bit, while maintaining a population count

static void ClearAndCount(Span<ulong> map, long bitIndex, ref long count)

Clears a specific bit, while maintaining a population count

Copy

BitMap64 Copy()

Return a copy of the bitmap

Returns: New bitmap which is identical, but does not share the same underlying storage

FindNext

long FindNext(long start)

Finds the index of the first set bit starting at a specific position in the map, or a negative value if the range contains all 0 until the end

long FindNext(long start, long endExclusive)

Find the index of the first set bit in the specified range of the map, or a negative value if the range contains all 0

static long FindNext(ReadOnlySpan<ulong> map, long capacity, long start, long endExclusive)

Find the index of the first set bit in the specified range of the map, or a negative value if the range contains all 0

FindNextUnsafe

static long FindNextUnsafe(UInt64* map, long start, long endExclusive)

Find the index of the first set bit in the specified range of the map, or a negative value if the range contains all 0

map — Pointer to the first word of the bitmap
start — Bit index of the first position to scan
endExclusive — Bit index of the position where the scan ends

FindSpan

long FindSpan(uint span, long start = 0)

Finds the start index of the first run of span contiguous set bits, or a negative value if none exists

span — Number of consecutive set bits to look for (must be 1 or more)
start — Bit index where the scan starts

Returns: If non-negative, all bits from the returned index to (index + span - 1) are set (1)

static long FindSpan(ReadOnlySpan<ulong> map, long capacity, uint span, long start)

Finds the start index of the first run of span contiguous set bits in the specified range, or a negative value if none exists

FindSpanUnsafe

static long FindSpanUnsafe(UInt64* map, uint span, long start, long size)

Finds the start index of the first run of span contiguous set bits in the specified range, or a negative value if none exists

map — Pointer to the first word of the bitmap
span — Number of consecutive set bits to look for (must be 1 or more)
start — Bit index where the scan starts
size — Size (in bits) of the bitmap

Flip

bool Flip(long bitIndex)

Inverts the state of a specific bit, and return its previous state

Returns: If true, the bit has transitioned from set (1) to cleared (0). If false, the bit has transitioned from cleared (0) to set (1).

static bool Flip(Span<ulong> map, long bitIndex)

Inverts the state of a specific bit, and return its previous state

Returns: If true, the bit has transitioned from set (1) to cleared (0). If false, the bit has transitioned from cleared (0) to set (1).

GetEnumerator

BitEnumerator GetEnumerator()

Enumerates all the bits in this map

GetHighestBit

long GetHighestBit()

Returns the index of the highest bit set, or a negative value if all bits are cleared

This is O(N)

static long GetHighestBit(UInt64* words, long capacity)

Returns the index of the highest bit set, or a negative value if all bits are cleared

This is O(N)

GetLowestBit

long GetLowestBit()

Returns the index of the lowest bit set, or a negative value if all bits are cleared

This is O(N)

static long GetLowestBit(UInt64* words, long capacity)

Returns the index of the lowest bit set, or a negative value if all bits are cleared

This is O(N)

GetSetBits

BitIndexEnumerable GetSetBits()

Enumerates the indexes of all the set bits in this map

Population

long Population()

Counts the number of bits that are set

Returns: Number of bits set, or 0 if all bits are cleared

This is O(N)

Set

void Set(long bitIndex)

Sets a specific bit

static void Set(Span<ulong> map, long bitIndex)

Sets a specific bit

void Set(long bitIndex, long count)

Sets a specific bit

static void Set(Span<ulong> map, long bitIndex, long count)

Sets a specific bit

SetAll

void SetAll()

Clears all bits of a map

static void SetAll(Span<ulong> map)

Clears all bits of a map

SetAndCount

void SetAndCount(long bitIndex, ref long count)

Sets a specific bit, while maintaining a population count

static void SetAndCount(Span<ulong> map, long bitIndex, ref long count)

Sets a specific bit, while maintaining a population count

Stringify

static string Stringify(ReadOnlySpan<ulong> map, long capacity, int base)

Returns a string representation of a bitmap in the specified base

static string Stringify(UInt64* map, long capacity, int base)

Returns a string representation of a bitmap in the specified base

Test

bool Test(long bitIndex)

Tests if a specific bit is set

Returns: If true, the bit is set (1). If false, the bit is not set (0).

static bool Test(ReadOnlySpan<ulong> map, long bitIndex)

Tests if a specific bit is set

Returns: If true, the bit is set (1). If false, the bit is not set (0).

TestAll

bool TestAll(long bitIndex, long count)

Tests if all the bits in a range are set

Returns: If true, the bit is set (1). If false, the bit is not set (0).

static bool TestAll(ReadOnlySpan<ulong> map, long bitIndex, long count)

Tests if all the bits in a range are set

Returns: If true, all the bits are set (1). If false, at least on bit is cleared (0).

TestAndClear

bool TestAndClear(long bitIndex)

Clears a specific bit and return its previous state

Returns: If true, the bit was set (1). If false, the bit was already cleared (0).

static bool TestAndClear(Span<ulong> map, long bitIndex)

Clears a specific bit and return its previous state

Returns: If true, the bit was set (1). If false, the bit was already cleared (0).

TestAndSet

bool TestAndSet(long bitIndex)

Sets a specific bit and return its previous state

static bool TestAndSet(Span<ulong> map, long bitIndex)

Sets a specific bit and return its previous state

TestAny

bool TestAny(long bitIndex, long count)

Tests if at least one bit in a range is set

Returns: If true, at least one bit is set (1). If false, all the bits are cleared (0).

static bool TestAny(ReadOnlySpan<ulong> map, long bitIndex, long count)

Tests if at least one bit in a range is set

Returns: If true, at least one bit is set (1). If false, all the bits are cleared (0).

ToArray

bool[] ToArray()

Returns an array of Boolean for each bit in this map

static bool[] ToArray(ReadOnlyMemory<ulong> map)

Returns an array of Boolean for each bit in a buffer

ToBinary

string ToBinary(char zero = '0', char one = '1')

Returns a base-2 string representation of this bitmap, composed of 1s and 0s

ToHex

string ToHex()

Returns a base-16 string representation of this bitmap, composed of 0-9+A-F characters

ToString

string ToString()

string ToString(string format, IFormatProvider provider = null)

Toggle

void Toggle(long bitIndex, bool on)

Changes the state of a specific bit

static void Toggle(Span<ulong> map, long bitIndex, bool on)

Changes the state of a specific bit

ToggleAndCount

void ToggleAndCount(long bitIndex, bool on, ref long count)

Changes the state of a specific bit, while maintaining a population count

static void ToggleAndCount(Span<ulong> map, long bitIndex, bool on, ref long count)

Changes the state of a specific bit, while maintaining a population count

WordsForCapacity

static int WordsForCapacity(long capacity)

Returns the number of 64-bit words required to store a bitmap of the specified capacity

capacity — Capacity (in bits) of the bitmap

Returns: Size (in 64-bit words) of the buffer

This returns the minimum length for an ulong[] array large enough to fit all the bits.

Fields

IndexShift

const int IndexShift

Shift to get index of word from bit index

WordMask

const int WordMask

Mask to get offset of bit inside word from bit index

WordSize

const int WordSize

Number of bits per word

Words

readonly Memory<ulong> Words

Array used to store the bits of this bitmap