Nicolas Cellier uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-nice.248.mcz==================== Summary ====================
Name: Collections-nice.248
Author: nice
Time: 10 December 2009, 6:09:40 am
UUID: 5d63293d-c113-c84e-8437-2fed14a79a58
Ancestors: Collections-nice.247
Just for fun, optimize a bit more WideCharacterSet bitmap:do:
1) it now enumerates Characters in ascending value
2) the trick to eliminate the lowest bit is just beautiful (a generalization of isPowerOfTwo)
Of course, I could also tabulate all the bits in an Array of 255 ByteArray, but that would be no fun...
=============== Diff against Collections-nice.247 ===============
Item was changed:
----- Method: WideCharacterSet>>bitmap:do: (in category 'private') -----
bitmap: aMap do: aBlock
"Execute a block with each value (0 based) corresponding to set bits.
Implementation: this version works best for sparse maps.
The powers of two and highBit tables are inlined for speed"
+ | byte byteOffset lowBits |
+ lowBits := #[1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 7 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 8 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 7 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1]. "The lowBits table is a 1-based bitOffset"
- | byte bitOffset byteOffset powersOf2 highBits |
- powersOf2 := #[1 2 4 8 16 32 64 128].
- highBits := #[0 1 1 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7].
1 to: aMap size do: [:i |
(byte := aMap at: i) = 0 ifFalse: [
+ byteOffset := (i bitShift: 3) - 9. "This byteOffset is -1 based"
+ ["Evaluate the block with 0-based (byteOffset + bitOffset)"
+ aBlock value: (byteOffset + (lowBits at: byte)).
+ "Eliminate the low bit and loop if some bit remain"
+ (byte := byte bitAnd: byte - 1) = 0] whileFalse]]!
- byteOffset := (i - 1) bitShift: 3.
- [aBlock value: (byteOffset + (bitOffset := highBits at: byte)).
- (byte := byte - (powersOf2 at: 1 + bitOffset)) = 0] whileFalse]]!
Locked
