C# Developers' Journal (original) (raw)

BitSet Remember some time ago I asked for the collection that has Add() and Contains() methods and a least possible overhead? Here we are. This is a specialized collection of this kind that will work for positive integers.

public class BitSet
{
    private const int BIT_COUNT = 64;
    private ulong[] data;

    private int count = 0;
    public int Count { get { return count; } }

    public int[] Values
    {
        get
        {
            int index = 0;
            int[] values = new int[count];
            for (int i = 0; i < data.Length * BIT_COUNT; i++)
                if (Contains(i))
                    values[index++] = i;
            return values;
        }
    }

    public BitSet(int max_value)
    {
        data = new ulong[max_value / BIT_COUNT + 1];
    }

    public bool Contains(int value)
    {
        ulong bit_mask = (ulong)1 << (value % BIT_COUNT);
        return bit_mask == (data[value / BIT_COUNT] & bit_mask);
    }

    public void Add(int value)
    {
        if (!Contains(value))
        {
            data[value / BIT_COUNT] |= (ulong)1 << (value % BIT_COUNT);
            count++;
        }
    }

    public void Remove(int value)
    {
        if (Contains(value))
        {
            data[value / BIT_COUNT] ^= (ulong)1 << (value % BIT_COUNT);
            count--;
        }
    }

    public void Clear()
    {
        for (int i = 0; i < data.Length; i++)
            data[i] = 0;
    }
}