HBitArray.cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Diagnostics;


namespace g3
{
    /// <summary>
    /// HBitArray is a hierarchical variant of BitArray. Basically the idea
    /// is to make a tree of 32-bit blocks, where at level N, a '0' means that
    /// no bits are true in level N-1. This means we can more efficiently iterate
    /// over the bit set. 
    /// 
    /// Uses more memory than BitArray, but each tree level is divided by 32, so
    /// it is better than NlogN
    /// </summary>
   [Serializable] public class HBitArray : IEnumerable<int>
    {
        struct MyBitVector32
        {
            int bits;
            public bool this[int i]
            {
                get { return (bits & (1 << i)) != 0; }
                set {
                        if (value)
                            bits |= (1 << i);
                        else
                            bits &= ~(1 << i);
                    }
            }
            public int Data { get { return bits; } }
        }


        MyBitVector32[] bits;

        struct Layer
        {
            public MyBitVector32[] layer_bits;
        }
        Layer[] layers;
        int layerCount;
        int max_index;
        int count;

        public HBitArray(int maxIndex)
        {
            max_index = maxIndex;
            int base_count = (maxIndex / 32);
            if (maxIndex % 32 != 0)
                base_count++;
            bits = new MyBitVector32[base_count];
            count = 0;

            layerCount = 2;
            layers = new Layer[layerCount];

            int prev_size = bits.Length;
            for ( int i = 0; i < layerCount; ++i ) {
                int cur_size = (prev_size / 32);
                if (prev_size % 32 != 0)
                    cur_size++;
                layers[i].layer_bits = new MyBitVector32[cur_size];
                prev_size = cur_size;
            }
        }


        public bool this[int i]
        {
            get { return Get(i); }
            set { Set(i, value); }
        }


        public int Count
        {
            get { return max_index; }
        }

        public int TrueCount
        {
            get { return count; }
        }


        public bool Contains(int i)
        {
            return Get(i) == true;
        }

        public void Add(int i)
        {
            Set(i, true);
        }

        public void Set(int i, bool value)
        {
            int byte_i = i / 32;
            int byte_o = i - (32 * byte_i);

            Debug.Assert(byte_o < 32);

            if (value == true) {
                if (bits[byte_i][byte_o] == false) {
                    bits[byte_i][byte_o] = true;
                    count++;

                    // [TODO] only need to propagate up if our current field was zero
                    for (int li = 0; li < layerCount; ++li) {
                        int layer_i = byte_i / 32;
                        int layer_o = byte_i - (32 * layer_i);
                        layers[li].layer_bits[layer_i][layer_o] = true;
                        byte_i = layer_i;
                    }
                }

            } else {
                if (bits[byte_i][byte_o] == true) {
                    bits[byte_i][byte_o] = false;
                    count--;

                    // [RMS] [June 6 2017] not sure if this comment is still true or not. Need to experiment.
                    // [TODO] only need to propagate up if our current field becomes zero
                    //ACK NO THIS IS WRONG! only clear parent bit if our entire bit is zero!

                    for (int li = 0; li < layerCount; ++li) {
                        int layer_i = byte_i / 32;
                        int layer_o = byte_i - (32 * layer_i);
                        layers[li].layer_bits[layer_i][layer_o] = false;
                        byte_i = layer_i;
                    }
                }
            }
        }


        public bool Get(int i)
        {
            int byte_i = i / 32;
            int byte_o = i - (32 * byte_i);
            return bits[byte_i][byte_o];
        }
 


        public IEnumerator<int> GetEnumerator()
        {
            if (count > max_index / 3) {
                for ( int bi = 0; bi < bits.Length; ++bi ) {
                    int d = bits[bi].Data;
                    int dmask = 1;
                    int maxj = (bi == bits.Length - 1) ? max_index % 32 : 32;
                    for (int j = 0; j < maxj; ++j) {
                        if ((d & dmask) != 0)
                            yield return bi * 32 + j;
                        dmask <<= 1;
                    }
                }

            } else {
                for (int ai = 0; ai < layers[1].layer_bits.Length; ++ai) {
                    if (layers[1].layer_bits[ai].Data == 0)
                        continue;
                    for (int aj = 0; aj < 32; aj++) {
                        if (layers[1].layer_bits[ai][aj]) {

                            int bi = ai * 32 + aj;
                            Debug.Assert(layers[0].layer_bits[bi].Data != 0);
                            for (int bj = 0; bj < 32; bj++) {
                                if (layers[0].layer_bits[bi][bj]) {
                                    int i = bi * 32 + bj;

                                    int d = bits[i].Data;
                                    int dmask = 1;
                                    for (int j = 0; j < 32; ++j) {
                                        if ((d & dmask) != 0)
                                            yield return i * 32 + j;
                                        dmask <<= 1;
                                    }

                                    // this is more expensive, but good for testing...
                                    //for ( int j = 0; j < 32; ++j ) {
                                    //    if (bits[i][j] == true)
                                    //        yield return i * 32 + j;
                                    //}
                                }
                            }
                        }
                    }
                }
            }
        }



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


    }
}