Skip to content

Instantly share code, notes, and snippets.

@voroninp
Created October 15, 2022 21:52
Show Gist options
  • Save voroninp/44449bf898ca5d1fa9e55bcd280ef138 to your computer and use it in GitHub Desktop.
Save voroninp/44449bf898ca5d1fa9e55bcd280ef138 to your computer and use it in GitHub Desktop.
public ref struct IndexSet
{
public static int SizeInBytes(uint maxIndex)
{
var indicesCount = maxIndex + 1;
var (size, additionalBits) = ((int)(indicesCount >> 3), indicesCount & 0b111);
if (additionalBits > 0)
{
size++;
}
return size;
}
private readonly Span<byte> _bits;
private readonly uint _maxIndex;
private int _count;
public int Count => _count;
public IndexSet(uint maxIndex, Span<byte> bits)
{
var bitsCount = bits.Length << 3;
if (maxIndex >= bitsCount )
{
throw new ArgumentException($"Bits count '{bitsCount}' is not enough to cover range of indices: [0; {maxIndex}].");
}
_maxIndex = maxIndex;
_bits = bits;
_count = 0;
}
public bool Add(uint index)
{
if (index > _maxIndex)
{
throw new ArgumentException("Value is greater than max index.", nameof(index));
}
var (@byte, bit) = ((int)(index >> 3), (int)index & 0b111);
var @new = (_bits[@byte] >> bit & 1) == 0;
if (@new)
{
_bits[@byte] |= (byte)(1 << bit);
_count++;
}
return @new;
}
public bool Remove(uint index)
{
if (index > _maxIndex)
{
throw new ArgumentException("Value is greater than max index.", nameof(index));
}
var (@byte, bit) = ((int)(index >> 3), (int)index & 0b111);
var existed = (_bits[@byte] >> bit & 1) == 1;
if (existed)
{
_bits[@byte] &= (byte)~(1 << bit);
_count--;
}
return existed;
}
public readonly bool Contains(uint index)
{
if (index > _maxIndex)
{
throw new ArgumentException("Value is greater than max index.", nameof(index));
}
var (@byte, bit) = ((int)(index >> 3), (int)index & 0b111);
return (_bits[@byte] >> bit & 1) == 1;
}
public uint[] Indices()
{
var items = new uint[_count];
var added = 0;
for (var index = 0U; index <= _maxIndex; index++)
{
var (@byte, bit) = ((int)(index >> 3), (int)index & 0b111);
var exists = (_bits[@byte] >> bit & 1) == 1;
if (exists)
{
items[added++] = index;
}
}
return items;
}
}
@voroninp
Copy link
Author

There's similar System.Collections.BitArray

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment