Levente Uzonyi uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-ul.644.mcz

==================== Summary ====================

Name: Collections-ul.644
Author: ul
Time: 22 August 2015, 2:50:48.28 am
UUID: 55f3957f-2ae4-4899-b3db-62dd7723d0f2
Ancestors: Collections-ul.643

Extracted and enhanced Bitset from WideCharacterSet.

=============== Diff against Collections-ul.643 ===============

Item was added:
+ Collection subclass: #Bitset
+ 	instanceVariableNames: 'bytes tally'
+ 	classVariableNames: ''
+ 	poolDictionaries: ''
+ 	category: 'Collections-Support'!
+ 
+ !Bitset commentStamp: 'ul 8/22/2015 00:52' prior: 0!
+ I implement Bitsets, which are dictionary-like data structures mapping 0-1 values to integers between 0 and capacity-1, or in another way they are set-like data structures which can include values between 0 and capacity-1.
+ I implement three different kind of APIs, each corresponding to a way of thinking about this data structure:
+ - A Set-like API with #add:, #remove: and #includes:
+ - A Dictionary-like API with #at:, #at:put:
+ - And a bit-manipulation API with #bitAt:, #clearBitAt: and #setBitAt:.
+ 
+ Instance Variables
+ 	bytes:		<ByteArray>
+ 	tally:		<Integer>
+ 
+ bytes
+ 	- a ByteArray which holds the values for each integer key. Each byte holds 8 values.
+ 
+ tally
+ 	- the number of objects in this set, or the number or 1 values in this dictionary.
+ !

Item was added:
+ ----- Method: Bitset class>>new (in category 'instance creation') -----
+ new
+ 
+ 	self error: 'Use #new: instead.'!

Item was added:
+ ----- Method: Bitset class>>new: (in category 'instance creation') -----
+ new: capacity
+ 
+ 	^self basicNew initialize: capacity!

Item was added:
+ ----- Method: Bitset>>= (in category 'comparing') -----
+ = anObject
+ 
+ 	self species == anObject species ifFalse: [ ^false ].
+ 	anObject size = tally ifFalse: [ ^false ].
+ 	^anObject bytes = bytes!

Item was added:
+ ----- Method: Bitset>>add: (in category 'adding') -----
+ add: anInteger
+ 	"Add anInteger to this set. Return anInteger."
+ 
+ 	self setBitAt: anInteger.
+ 	^anInteger!

Item was added:
+ ----- Method: Bitset>>at: (in category 'accessing') -----
+ at: anInteger
+ 
+ 	^self bitAt: anInteger
+ 		!

Item was added:
+ ----- Method: Bitset>>at:put: (in category 'accessing') -----
+ at: anInteger put: aBit
+ 
+ 	^self bitAt: anInteger put: aBit
+ 		!

Item was added:
+ ----- Method: Bitset>>bitAt: (in category 'bit manipulation') -----
+ bitAt: anInteger
+ 	"Return the bit corresponding to anInteger."
+ 
+ 	^((bytes at: (anInteger bitShift: -3) + 1) bitShift: 0 - (anInteger bitAnd: 7)) bitAnd: 1
+ 		!

Item was added:
+ ----- Method: Bitset>>bitAt:put: (in category 'bit manipulation') -----
+ bitAt: anInteger put: aBit
+ 	"Set the value corresponding to anInteger to aBit. Return the new value."
+ 
+ 	aBit caseOf: {
+ 		[ 0 ] -> [ self clearBitAt: anInteger ].
+ 		[ 1 ] -> [ self setBitAt: anInteger ] }.
+ 	^aBit
+ 		
+ 		!

Item was added:
+ ----- Method: Bitset>>bytes (in category 'private') -----
+ bytes
+ 
+ 	^bytes!

Item was added:
+ ----- Method: Bitset>>capacity (in category 'accessing') -----
+ capacity
+ 	"Return the highest integer this collection can store plus one."
+ 
+ 	^bytes size * 8!

Item was added:
+ ----- Method: Bitset>>clearBitAt: (in category 'bit manipulation') -----
+ clearBitAt: anInteger
+ 	"Set the value corresponding to anInteger to 0. Return true if the value wasn't 0."
+ 
+ 	| index value mask newValue |
+ 	index := (anInteger bitShift: -3) + 1.
+ 	value := bytes at: index.
+ 	mask := 1 bitShift: (anInteger bitAnd: 7).
+ 	(newValue := (value bitOr: mask) - mask) = value ifTrue: [ ^false ].
+ 	bytes at: index put: newValue.
+ 	tally := tally - 1.
+ 	^true
+ !

Item was added:
+ ----- Method: Bitset>>do: (in category 'enumerating') -----
+ do: aBlock
+ 	"Evaluate aBlock with each integer which has its bit set to 1."
+ 
+ 	| byte byteOffset lowBits remainingBits |
+ 	remainingBits := tally.
+ 	lowBits := Integer lowBitPerByteTable.
+ 	1 to: bytes size do: [ :index |
+ 		1 <= remainingBits ifFalse: [ ^self ].
+ 		(byte := bytes at: index) = 0 ifFalse: [
+ 			byteOffset := (index bitShift: 3) - 9. "- 8 - 1 to make it -1 based."
+ 			[
+ 				aBlock value: (lowBits at: byte) + byteOffset. "byteOffset is -1 based, lowBits is 1-based."
+ 				remainingBits := remainingBits - 1.
+ 				"Eliminate the low bit and loop if there're any remaning bits set."
+ 				(byte := byte bitAnd: byte - 1) = 0 ] whileFalse ] ]!

Item was added:
+ ----- Method: Bitset>>hash (in category 'comparing') -----
+ hash
+ 	"#hash is implemented, because #= is implemented."
+ 
+ 	^(self species hash bitXor: tally hashMultiply) bitXor: bytes hash!

Item was added:
+ ----- Method: Bitset>>includes: (in category 'testing') -----
+ includes: anInteger
+ 
+ 	anInteger isInteger ifFalse: [ ^false ].
+ 	-1 < anInteger ifFalse: [ ^false ].
+ 	anInteger < self capacity ifFalse: [ ^false ].
+ 	^(self bitAt: anInteger) = 1!

Item was added:
+ ----- Method: Bitset>>initialize: (in category 'private') -----
+ initialize: capacity
+ 	"Capacity is expected to be a non-negative, multiple-of-eight integer."
+ 
+ 	bytes := ByteArray new: capacity // 8.
+ 	tally := 0!

Item was added:
+ ----- Method: Bitset>>postCopy (in category 'copying') -----
+ postCopy
+ 	"Copy bytes as well."
+ 
+ 	bytes := bytes copy!

Item was added:
+ ----- Method: Bitset>>remove:ifAbsent: (in category 'removing') -----
+ remove: anInteger ifAbsent: absentBlock
+ 
+ 	(self clearBitAt: anInteger) ifTrue: [ ^anInteger ].
+ 	^absentBlock value!

Item was added:
+ ----- Method: Bitset>>removeAll (in category 'removing') -----
+ removeAll
+ 
+ 	tally = 0 ifTrue: [ ^self ].
+ 	bytes atAllPut: 0. "Unlike most #removeAll implementations, we don't allocate a new ByteArray here, because this is a bit more efficient. The VM would have to fill the new array with zeroes anyway."
+ 	tally := 0!

Item was added:
+ ----- Method: Bitset>>setBitAt: (in category 'bit manipulation') -----
+ setBitAt: anInteger
+ 	"Set the value corresponding to anInteger to 1. Return true if the value wasn't 1."
+ 
+ 	| index value newValue |
+ 	index := (anInteger bitShift: -3) + 1.
+ 	value := bytes at: index.
+ 	(newValue := (1 bitShift: (anInteger bitAnd: 7)) bitOr: value) = value ifTrue: [ ^false ].
+ 	bytes at: index put: newValue.
+ 	tally := tally + 1.
+ 	^true!

Item was added:
+ ----- Method: Bitset>>size (in category 'accessing') -----
+ size
+ 	"Return the number of 1 values in this collection."
+ 
+ 	^tally!