Robert Dockins robdockins at fastmail.fm
Sat Apr 8 18:54:58 EDT 2006

```On Apr 8, 2006, at 1:58 PM, David F. Place wrote:

> Thanks Bulat and Robert.  I implemented Bulat's idea as the
> following.  It tests faster than Roberts.  I use Robert's to
> compute the table.  The performance seems satisfactory now.
>
> size :: Set a -> Int
> size (Set w) = countBits w
>     where
>       countBits w
>           | w == 0 = 0
>           | otherwise = countBits (w `shiftR` 8) + bitsTable!(w .&.
> 0xFF)
>
> bitsTable :: Array Word Int
> bitsTable = array (0,255) \$ [(i,bitcount i) | i <- [0..255]]
>
> bitcount :: Word -> Int
> bitcount 0 = 0
> bitcount x = 1 + bitcount (x .&. (x-1))

There's a couple of other nice bit-twiddily things you can do:

countBits :: Word -> Int
countBits w
| w == 0 = 0
| otherwise = countBits (w `shiftR` 8) + bitsTable!(w .&. 0xFF)

bitsTable :: Array Word Int
bitsTable = array (0,255) \$ [(i,bitcount i) | i <- [0..255]]

bitcount :: Word -> Int
bitcount 0 = 0
bitcount x = 1 + bitcount (x .&. (x-1))

lsb :: Word -> Int
lsb x = countBits ((x-1) .&. (complement x))

-- stolen from http://aggregate.org/MAGIC/
msb :: Word -> Int
msb x0 = let
x1 = x0 .|. (x0 `shiftR` 1)
x2 = x1 .|. (x1 `shiftR` 2)
x3 = x2 .|. (x2 `shiftR` 4)
x4 = x3 .|. (x3 `shiftR` 8)
x5 = x4 .|. (x4 `shiftR` 16)
in countBits x5 - 1

findMinIndex :: Word -> Int
findMinIndex 0 =
error "EnumSet.findMin: empty set has no minimal element"
findMinIndex w = lsb w

findMaxIndex :: Word -> Int
findMaxIndex 0 =
error "EnumSet.findMax: empty set has no maximal element"
findMaxIndex w = msb w

Which should make all access to the greatest or least element O(1).
I guess, come to think of it, all operations on EnumSet are O(1) by
virtue of the set size being upper-bounded.  At any rate this turns
recursion into unboxable straight-line code and I think it does less
allocations.

Rob Dockins

Speak softly and drive a Sherman tank.
Laugh hard; it's a long way to the bank.
-- TMBG
```