http://d.puremagic.com/issues/show_bug.cgi?id=4124

           Summary: toString() for BitArray and more
           Product: D
           Version: future
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: Phobos
        AssignedTo: nobody@puremagic.com
        ReportedBy: bearophile_hugs@eml.cc


--- Comment #0 from bearophile_hugs@eml.cc 2010-04-24 16:26:12 PDT ---
A toString() method for std.bitmanip.BitArray is useful. It can use a simple representation like the Python bitarray:

0101001010100001

Or as java.util.BitSet (but I prefer the Python version):

{1, 3, 6, 8, 10, 15}


Other methods useful for BitArray:
- reset all bits
- set all bits
- are all bit set?
- are all bit reset?
- count set bits (there are _very_ efficient algorithms to do this).
- set n-th bit (this can be a little more efficient than bs[n]=1;)
- reset n-th bit (this can be a little more efficient than bs[n]=1;)
- flip n-th bit


I think the sort() method of BitArray is not commonly useful.

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

http://d.puremagic.com/issues/show_bug.cgi?id=4124



--- Comment #1 from bearophile_hugs@eml.cc 2011-10-13 11:22:06 PDT ---
Maybe the usefulness of isSet(), set(), and reset() methods is visible with two
benchmarks. They implement the same algorithm (a simple sieve), the first uses
a BitArray, and the second a manually implemented bit array. On my 32 bit
system the second program is about two times faster than the first one.


import std.stdio, std.algorithm, std.range, std.math, std.bitmanip, std.datetime;

uint[] primes(uint n) {
    if (n < 2) return [];

    BitArray F;
    F.length = n + 1;
    F[0] = true;
    F[1] = true;
    foreach (i; 2 .. cast(uint)sqrt(n))
        if (!F[i])
            for (uint j = i * i; j <= n; j += i)
                F[j] = true;

    return array(filter!((i){ return !F[i]; })(iota(n+1)));
}

void main() {
    StopWatch sw;
    sw.start();
    primes(30_000_000);
    sw.stop();
    writeln(sw.peek().msecs / 1000.0);
}





import std.stdio, std.algorithm, std.range, std.math, std.datetime;

size_t[] primes(in size_t n) {
    enum size_t bpc = size_t.sizeof * 8;
    auto F = new size_t[n / bpc + 1];
    F[] = size_t.max;

    bool isSet(in size_t i) nothrow {
        immutable size_t offset = i / bpc;
        immutable size_t mask = 1 << (i % bpc);
        return (F[offset] & mask) != 0;
    }

    void clear(in size_t i) nothrow {
        immutable size_t offset = i / bpc;
        immutable size_t mask = 1 << (i % bpc);
        if ((F[offset] & mask) != 0)
            F[offset] = F[offset] ^ mask;
    }

    clear(0);
    clear(1);

    foreach (i; 2 .. cast(size_t)sqrt(n))
        if (isSet(i))
            for (uint j = i * i; j <= n; j += i)
                clear(j);

    return array(filter!isSet(iota(n + 1)));
}

void main() {
    StopWatch sw;
    sw.start();
    size_t n = primes(30_000_000).length;
    sw.stop();
    writeln(sw.peek().msecs / 1000.0);
    writeln("n primes: ", n);
}

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

http://d.puremagic.com/issues/show_bug.cgi?id=4124


Andrej Mitrovic <andrej.mitrovich@gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |andrej.mitrovich@gmail.com


--- Comment #2 from Andrej Mitrovic <andrej.mitrovich@gmail.com> 2013-01-25 11:50:14 PST ---
It can use a simple
representation like the Python bitarray:
0101001010100001

What about this instead:
0101_0010_1010_0001

I think it would also be useful to be able to initialize a bitarray with an integral literal, e.g.:

BitArray bta = bitArray!0101_0010_1010_0001;

It would statically check that all digits are 0 or 1 (is there a bit twiddling
trick for this?).

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

http://d.puremagic.com/issues/show_bug.cgi?id=4124



--- Comment #3 from Andrej Mitrovic <andrej.mitrovich@gmail.com> 2013-01-25 11:50:35 PST ---
(In reply to comment #2)
> It can use a simple
> representation like the Python bitarray:
> 0101001010100001

That should have been a quote.

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

http://d.puremagic.com/issues/show_bug.cgi?id=4124


Andrej Mitrovic <andrej.mitrovich@gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |pull
         AssignedTo|nobody@puremagic.com        |andrej.mitrovich@gmail.com


--- Comment #4 from Andrej Mitrovic <andrej.mitrovich@gmail.com> 2013-02-17 17:03:02 PST ---
It would help if you didn't make multiple feature requests in a single entry. As for toString (the name of the report), I've implemented it here:

https://github.com/D-Programming-Language/phobos/pull/1144

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

http://d.puremagic.com/issues/show_bug.cgi?id=4124



--- Comment #5 from bearophile_hugs@eml.cc 2013-02-17 17:24:18 PST ---
(In reply to comment #4)
> It would help if you didn't make multiple feature requests in a single entry.

When I am asking things like this for a single struct of Phobos:

- reset all bits
- set all bits

Is it right to create two different enhancement requests for those two things?

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

http://d.puremagic.com/issues/show_bug.cgi?id=4124



--- Comment #6 from Andrej Mitrovic <andrej.mitrovich@gmail.com> 2013-02-17 17:28:06 PST ---
(In reply to comment #5)
> (In reply to comment #4)
> > It would help if you didn't make multiple feature requests in a single entry.
> 
> When I am asking things like this for a single struct of Phobos:
> 
> - reset all bits
> - set all bits
> 
> Is it right to create two different enhancement requests for those two things?

One would be enough since they're highly related. toString is largely unrelated to this though.

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

http://d.puremagic.com/issues/show_bug.cgi?id=4124



--- Comment #7 from github-bugzilla@puremagic.com 2013-06-01 07:32:37 PDT ---
Commits pushed to master at https://github.com/D-Programming-Language/phobos

https://github.com/D-Programming-Language/phobos/commit/4f5079e4f8d38e1d469e4b28303553f36f49e33b Fixes Issue 4124 - Implement toString for BitArray.

https://github.com/D-Programming-Language/phobos/commit/9d331e2dc43a590c486c1b4862c0b1173b2f6799 Merge pull request #1144 from AndrejMitrovic/Fix4124

Issue 4124 - Implement toString for BitArray.

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

http://d.puremagic.com/issues/show_bug.cgi?id=4124


Kenji Hara <k.hara.pg@gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED


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

http://d.puremagic.com/issues/show_bug.cgi?id=4124



--- Comment #8 from bearophile_hugs@eml.cc 2013-06-01 20:04:36 PDT ---
(In reply to comment #7)
> Commits pushed to master at https://github.com/D-Programming-Language/phobos
> 
> https://github.com/D-Programming-Language/phobos/commit/4f5079e4f8d38e1d469e4b28303553f36f49e33b Fixes Issue 4124 - Implement toString for BitArray.
> 
> https://github.com/D-Programming-Language/phobos/commit/9d331e2dc43a590c486c1b4862c0b1173b2f6799 Merge pull request #1144 from AndrejMitrovic/Fix4124
> 
> Issue 4124 - Implement toString for BitArray.

Thank you. This introduces a good toString for BitArray. Then I will move elsewhere the missing things.

I think this stuff can go in a single enhancement request because they are easy
and short to implement:
- reset all bits
- set all bits
- are all bit set?
- are all bit reset?
- set n-th bit (this can be a little more efficient than bs[n]=1;)
- reset n-th bit (this can be a little more efficient than bs[n]=1;)
- flip n-th bit

Maybe it's better to move this into a separated ER because it looks simple but
implementing a pop count very efficiently is not so easy:
- count set bits

----------------

Now (unlike "%s") "%b" produces a string output that's not usable to build a new BitArray, maybe this is another worth enhancement request:


import std.stdio, std.bitmanip, std.conv, std.string;
void main() {
    BitArray b1;
    b1.init([0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]);
    writefln("%b", b1); // Prints: 00001111_00001111
    BitArray b2;

    // Error: function std.bitmanip.BitArray.init (bool[] ba)
    // is not callable using argument types (string)
    b2.init("00001111_00001111");
}

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