StateVector.cs

//lifted from .net's open source BitArray class.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Threading;

namespace Std.BasicTypes
{
    internal struct StateVector : IEnumerable<bool>
    {
        // XPerY=n means that n Xs can be stored in 1 Y. 
        private const int BitsPerInt32 = 32;

        private readonly int[] _bits;

        private int _version;

        public int SetBitCount
        {
            get
            {
                var count = 0;
                for (var idx = 0; idx < GetArrayLength(Length, BitsPerInt32); idx++)
                {
                    var word = _bits[idx];
                    word = word - ((word >> 1) & 0x55555555);
                    word = (word & 0x33333333) + ((word >> 2) & 0x33333333);
                    word = (word + (word >> 4)) & 0x0F0F0F0F;
                    word = word + (word >> 8);
                    word = word + (word >> 16);

                    count += word & 0x0000003F;
                }

                return count;
            }
        }

        public IEnumerable<int> GetSetIndexes()
        {
            for (var idx = 0; idx < Length; idx++)
            {
                if (this[idx])
                {
                    yield return idx;
                }
            }
        }

        /*=========================================================================
        ** Allocates space to hold length bit values. All of the values in the bit
        ** array are set to defaultValue.
        **
        ** Exceptions: ArgumentOutOfRangeException if length < 0.
        =========================================================================*/
        public StateVector(int length, bool defaultValue = false)
            : this()
        {
            if (length < 0)
            {
                throw new ArgumentOutOfRangeException(nameof(length));
            }

            Length = length;
            _bits = new int[GetArrayLength(length, BitsPerInt32)];

            var fillValue = defaultValue
                ? unchecked((int) 0xffffffff)
                : 0;
            for (var i = 0; i < _bits.Length; i++)
            {
                _bits[i] = fillValue;
            }

            _version = 0;
        }

        public bool this[int index]
        {
            get => Get(index);
            set => Set(index, value);
        }

        public int Length { get; }

        /*=========================================================================
        ** Returns the bit value at position index.
        **
        ** Exceptions: ArgumentOutOfRangeException if index < 0 or
        **             index >= GetLength().
        =========================================================================*/
        public bool Get(int index)
        {
            if (index < 0 || index >= Length)
            {
                throw new ArgumentOutOfRangeException(nameof(index));
            }

            return (_bits[index / 32] & (1 << (index % 32))) != 0;
        }

        /*=========================================================================
        ** Sets the bit value at position index to value.
        **
        ** Exceptions: ArgumentOutOfRangeException if index < 0 or
        **             index >= GetLength().
        =========================================================================*/
        public void Set(int index, bool value)
        {
            if (index < 0 || index >= Length)
            {
                throw new ArgumentOutOfRangeException(nameof(index));
            }

            if (value)
            {
                _bits[index / 32] |= 1 << (index % 32);
            }
            else
            {
                _bits[index / 32] &= ~(1 << (index % 32));
            }

            _version++;
        }

        public void Reset()
        {
            var ints = GetArrayLength(Length, BitsPerInt32);
            for (var i = 0; i < ints; i++)
            {
                _bits[i] = 0;
            }

            _version++;
        }

        /*=========================================================================
        ** Sets all the bit values to value.
        =========================================================================*/
        public void SetAll(bool value)
        {
            var fillValue = value
                ? unchecked((int) 0xffffffff)
                : 0;
            var ints = GetArrayLength(Length, BitsPerInt32);
            for (var i = 0; i < ints; i++)
            {
                _bits[i] = fillValue;
            }

            _version++;
        }

        /*=========================================================================
        ** Returns a reference to the current instance ANDed with value.
        **
        ** Exceptions: ArgumentException if value == null or
        **             value.Length != this.Length.
        =========================================================================*/
        public StateVector And(StateVector value)
        {
            if (Length != value.Length)
            {
                throw new ArgumentException("Array lengths differ");
            }

            var ints = GetArrayLength(Length, BitsPerInt32);
            for (var i = 0; i < ints; i++)
            {
                _bits[i] &= value._bits[i];
            }

            _version++;
            return this;
        }

        /*=========================================================================
        ** Returns a reference to the current instance ORed with value.
        **
        ** Exceptions: ArgumentException if value == null or
        **             value.Length != this.Length.
        =========================================================================*/
        public StateVector Or(StateVector value)
        {
            if (Length != value.Length)
            {
                throw new ArgumentException("Array lengths differ");
            }

            var ints = GetArrayLength(Length, BitsPerInt32);
            for (var i = 0; i < ints; i++)
            {
                _bits[i] |= value._bits[i];
            }

            _version++;
            return this;
        }

        /*=========================================================================
        ** Returns a reference to the current instance XORed with value.
        **
        ** Exceptions: ArgumentException if value == null or
        **             value.Length != this.Length.
        =========================================================================*/
        public StateVector Xor(StateVector value)
        {
            if (Length != value.Length)
            {
                throw new ArgumentException("Array lengths differ");
            }

            var ints = GetArrayLength(Length, BitsPerInt32);
            for (var i = 0; i < ints; i++)
            {
                _bits[i] ^= value._bits[i];
            }

            _version++;
            return this;
        }

        /*=========================================================================
        ** Inverts all the bit values. On/true bit values are converted to
        ** off/false. Off/false bit values are turned on/true. The current instance
        ** is updated and returned.
        =========================================================================*/
        public StateVector Not()
        {
            var ints = GetArrayLength(Length, BitsPerInt32);
            for (var i = 0; i < ints; i++)
            {
                _bits[i] = ~_bits[i];
            }

            _version++;
            return this;
        }

        /// <summary>
        ///     Used for conversion between different representations of bit array.
        ///     Returns (n+(div-1))/div, rearranged to avoid arithmetic overflow.
        ///     For example, in the bit to int case, the straightforward calc would
        ///     be (n+31)/32, but that would cause overflow. So instead it's
        ///     rearranged to ((n-1)/32) + 1, with special casing for 0.
        ///     Usage:
        ///     GetArrayLength(77, BitsPerInt32): returns how many ints must be
        ///     allocated to store 77 bits.
        /// </summary>
        /// <param name="n"></param>
        /// <param name="div">
        ///     use a conversion constant, e.g. BytesPerInt32 to get
        ///     how many ints are required to store n bytes
        /// </param>
        /// <returns></returns>
        private static int GetArrayLength(int n, int div)
        {
            return n > 0
                ? (n - 1) / div + 1
                : 0;
        }

        public IEnumerator<bool> GetEnumerator()
        {
            var length = Length;
            var version = _version;

            for (var bitIdx = 0; bitIdx < length; bitIdx++)
            {
                if (version != _version)
                {
                    throw new InvalidOperationException(
                        "Cannot modify the bit array while it is being enumerated over.");
                }
                yield return Get(bitIdx);
            }
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }
}