The Trunk: Collections-ul.644.mcz

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!