[Issue 4717] New: std.bitmanip.BitArray changes

[d-bugmail at puremagic.com]

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

           Summary: std.bitmanip.BitArray changes
           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 2010-08-23 17:26:32 PDT ---
The method sort() of std.bitmanip.BitArray doesn't look so useful, and it may
be removed.

On the other hand there is some very commonly useful functionality that it is
missing in BitArray:
1) b[] = 0; and b[] = 1; to set and reset the whole array quickly, this is a
very common need.
2) countSet(): returns the number of bits set inside the bit array.
3) flip(n): to invert the state of the n-th bit of the bit array.
4) set(n): to set (to 1) the n-th bit of the bit array.
5) reset(n): to reset (set to 0) the n-th bit of the bit array.
6) flipAll(): to invert the state of all bits of the bit array.
7) toSting(): that converts the bit array into a string like
"BitArray(\"0101010011001\")".
8) this() (constructor) method that builds a bit array from a string like
"0101010011001", it's the opposite of the toString().

Optionally:
9) Basic Range interface for the BitArray, so you may use map() on it.
10) firstSet(): returns the index of the first bit that is set, starting the
search from the less significant bit. This is for more specialized usage, like
some heaps.


Notes:
- The count() is also known known as Population or Hamming weight. This is
useful for Hamming distances, to count bits in many situations, like for
example for the Sieve of Eratosthenes. There are ways and refined algorithms to
speed up this operation a lot. And this is a very commonly useful operation. I
may offer some D code if you want. See also:
http://en.wikipedia.org/wiki/Hamming_weight
http://graphics.stanford.edu/~seander/bithacks.html
And see also the __builtin_popcount() built-in function of GCC.
- The flip(n), set(n) and reset(n) methods are useful because they may be made
more efficient than opIndexAssign().
- Regarding firstSet(), see also the __builtin_ffs() built-in function of GCC.
- Methods like opXorAssign() probably need to be converted to the new operator
overloading of D2.

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