www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 4124] New: toString() for BitArray and more

reply d-bugmail puremagic.com writes:
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: -------
Apr 24 2010
next sibling parent d-bugmail puremagic.com writes:
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: -------
Oct 13 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
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: -------
Jan 25 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
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: -------
Jan 25 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
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: -------
Feb 17 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
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: -------
Feb 17 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
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: -------
Feb 17 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
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: -------
Jun 01 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
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: -------
Jun 01 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
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: -------
Jun 01 2013
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4124


bearophile_hugs eml.cc changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|toString() for BitArray and |toString() for BitArray
                   |more                        |


--- Comment #9 from bearophile_hugs eml.cc 2013-06-02 04:59:14 PDT ---
Removed "and more" from the title

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