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



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



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






 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




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


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







 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




13:47:50 PST ---



 

 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