www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 12027] New: Range of true bits for std.bitmanip.BitArray

reply d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12027

           Summary: Range of true bits for std.bitmanip.BitArray
           Product: D
           Version: D2
          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 2014-01-29 08:24:12 PST ---
std.bitmanip.BitArray is sometimes used to represent sparse sets. For this
usage it's handy to be able to iterate only on the bits set to true. So I
suggest to add a method that returns a range that yields the indexes of only
the true bits. Probably it's not hard to create such range using std.range and
std.algorithm, but a range implemented natively inside BitArray is probably
faster (it can skip whole empty words, and skip the empty bits faster).

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jan 29 2014
next sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12027


Peter Alexander <peter.alexander.au gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |peter.alexander.au gmail.co
                   |                            |m


--- Comment #1 from Peter Alexander <peter.alexander.au gmail.com> 2014-02-02
04:53:46 PST ---
https://github.com/D-Programming-Language/phobos/pull/1901

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 02 2014
prev sibling next sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12027



--- Comment #2 from bearophile_hugs eml.cc 2014-02-02 05:11:33 PST ---
(In reply to comment #1)
 https://github.com/D-Programming-Language/phobos/pull/1901

See also Issue 4717 and Issue 10239 -- Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Feb 02 2014
prev sibling next sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12027



--- Comment #3 from github-bugzilla puremagic.com 2014-03-01 12:28:56 PST ---
Commits pushed to master at https://github.com/D-Programming-Language/phobos

https://github.com/D-Programming-Language/phobos/commit/08820e2f146d7a7268f25fd130188929c62dd51c
Fix Issue 12027 - Iterate set bits in BitArray.

Also adds:
- countTrailingZeros(v)
- countBitsSet(v)
- bitsSet(v)

Notes:
- There is a `popcnt` function in `core.bitops`, but it only works with `int`.
- `bitsSet(v)` could be a bidirectional and possibly even random access range,
but I'll leave that for future work for now.

https://github.com/D-Programming-Language/phobos/commit/c78cfd97fba32893be2b3dd33425c0d8716409bd
Merge pull request #1901 from Poita/bug12027

Fix Issue 12027 - Iterate set bits in BitArray.

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Mar 01 2014
prev sibling next sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12027



--- Comment #4 from bearophile_hugs eml.cc 2014-03-01 12:48:48 PST ---
(In reply to comment #3)

 Also adds:
 - countTrailingZeros(v)
 - countBitsSet(v)
 - bitsSet(v)

Apparently only bitsSet is working for me: void main() { import std.stdio, std.bitmanip; BitArray b; b.init([0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0]); b.bitsSet.writeln; b.countTrailingZeros.writeln; b.countBitsSet.writeln; } It gives: test.d(7,6): Error: ScopeDsymbol test.__anonymous.__anonymous template std.bitmanip.countTrailingZeros(T)(T value) if (isIntegral!T) is private test.d(7,6): Error: template std.bitmanip.countTrailingZeros cannot deduce function from argument types !()(BitArray), candidates are: ..\dmd2\src\phobos\std\bitmanip.d(3440,14): std.bitmanip.countTrailingZeros(T)(T value) if (isIntegral!T) test.d(8,6): Error: ScopeDsymbol test.__anonymous.__anonymous template std.bitmanip.countBitsSet(T)(T value) if (isIntegral!T) is private test.d(8,6): Error: template std.bitmanip.countBitsSet cannot deduce function from argument types !()(BitArray), candidates are: ..\dmd2\src\phobos\std\bitmanip.d(3502,14): std.bitmanip.countBitsSet(T)(T value) if (isIntegral!T) -- Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Mar 01 2014
prev sibling next sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12027


bearophile_hugs eml.cc changed:

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


-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Mar 01 2014
prev sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12027



--- Comment #5 from Peter Alexander <peter.alexander.au gmail.com> 2014-03-01
13:47:50 PST ---
(In reply to comment #4)
 (In reply to comment #3)
 
 Also adds:
 - countTrailingZeros(v)
 - countBitsSet(v)
 - bitsSet(v)

Apparently only bitsSet is working for me:

countTrailingZeros and countBitsSet are only defined for built-in integral types at the moment. They were needed to implement bitsSet. However, I was persuaded to make them private because druntime defines popcnt and bsf, but not generically. blackwhale argued that popcnt/bsf should be extended to be more generic in druntime, but I argued that druntime was for things only necessary for the D language to work, and these weren't necessary. We disagreed, so compromised and just marked them as private for now until we figure out how to resolve it. btw, bitsSet also works on built-in integers, e.g. 5.bitsSet.equal([0, 2]); -- Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Mar 01 2014