[Issue 12472] New: Fixed-sized Bit array too

[d-bugmail at puremagic.com]

https://d.puremagic.com/issues/show_bug.cgi?id=12472

           Summary: Fixed-sized Bit array too
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: Phobos
        AssignedTo: nobody at puremagic.com
        ReportedBy: bearophile_hugs at eml.cc


--- Comment #0 from bearophile_hugs at eml.cc 2014-03-26 05:54:48 PDT ---
I suggest to add to Phobos a simple data structure similar to BitArray but
implemented with a fixed-size array:


struct StaticBitArray(uint N) {
    alias T = size_t;
    enum size_t bpc = T.sizeof * 8;
    T[(N + bpc - 1) / bpc] data;
    static assert(N <= data.sizeof * 8);
    alias data this;

    alias length = N;

    T isSet(in size_t i) const pure nothrow {
        // Pre-condition here.
        immutable size_t offset = i / bpc;
        immutable T mask = (cast(T)1) << (i % bpc);
        return data[offset] & mask;
    }

    void set(in size_t i) pure nothrow {
        // Pre-condition here.    
        immutable size_t offset = i / bpc;
        immutable T mask = (cast(T)1) << (i % bpc);
        data[offset] |= mask;
    }

    void reset(in size_t i) pure nothrow {
        // Pre-condition here.    
        immutable size_t offset = i / bpc;
        immutable T mask = (cast(T)1) << (i % bpc);
        if ((data[offset] & mask) != 0)
            data[offset] = data[offset] ^ mask;
    }

    void setAll() const pure nothrow {
        //data[] = T.max; // Currently not efficient if N is small.
        foreach (immutable i; 0 .. data.length)
            data[i] = T.max;
    }

    void reseAll() const pure nothrow {
        //data[i] = 0; // Currently not efficient if N is small.
        foreach (immutable i; 0 .. data.length)
            data[i] = 0;
    }

    // Some more methods here. 
}


I have used set/reset methods because they are more efficient than
opIndexAssign when the compiler is not inlining much.

The advantages of this data structure are similar to the advantages of
fixed-size arrays compared to dynamic arrays (less indirection, less memory,
can be stored in-place simply and copied simply, simpler code and smaller
resulting binary, etc).

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------