class SparseBitmap < DelegateClass( Hash )

    def initialize( enum=[] )
        @internal_hash={}
        @bucketsize=0.size * 8
        enum.each {|v|
            add v
        }
        super @internal_hash
    end

    def pack
        mykeys=self.keys.pack('w*')
        myvals=self.values.pack('w*')
        "#{mykeys.size},#{myvals.size}:#{mykeys},#{myvals}"
    end

    def self.unpack( str )
        header,body=str.force_encoding('ASCII-8BIT').split(':',2)
        keysize,valsize=header.split(',').map(&:to_i)
        raise ArgumentError, "Bad packed string" unless body[keysize]==','
        keystr=body[0,keysize]
        valstr=body[keysize+1,valsize]
        newkeys=keystr.unpack('w*')
        newvals=valstr.unpack('w*')
        s=self.new
        s.instance_variable_get(:@internal_hash).replace( Hash[newkeys.zip(newvals)] )
        s
    end
=begin
    def pack
        @internal_hash.to_msgpack
    end

    def self.unpack str
        s=self.new
        s.instance_variable_get(:@internal_hash).replace( MessagePack.unpack(str) )
        s
    end
=end

    def add( v )
        begin
            v=Integer( v )
        rescue
            raise ArgumentError, "#{self.class}: #{__method__}: Unable to parse #{v.inspect} as an int"
        end
        bucket=v / @bucketsize
        bit=v % @bucketsize
        # set the nth bit in the correct bucket
        @internal_hash[bucket]||=0
        @internal_hash[bucket] |= 1 << bit
    end
    alias :<< :add

    def contains?( v )
        begin
            v=Integer( v )
        rescue
            raise ArgumentError, "#{self.class}: #{__method__}: Unable to parse #{v.inspect} as an int"
        end
        bucket=v / @bucketsize
        return false unless @internal_hash[bucket]
        bit=v % @bucketsize
        @internal_hash[bucket][bit]==1
    end

    def to_a
        @internal_hash.each_with_object([]) {|keyval,ary|
            (0...@bucketsize).each {|bit_idx|
                if keyval[1][bit_idx]==1
                    ary << keyval[0]*64 + bit_idx
                end
            }
        }
    end

end