diff -r ab6ec0c97bf5 -r d36b1e1c301f BitArray.st --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/BitArray.st Fri Oct 14 17:46:33 2016 +0200 @@ -0,0 +1,519 @@ +" + COPYRIGHT (c) 1997 by eXept Software AG / Claus Gittinger + All Rights Reserved + + This software is furnished under a license and may be used + only in accordance with the terms of that license and with the + inclusion of the above copyright notice. This software may not + be provided or otherwise made available to, or used by, any + other person. No title to or ownership of the software is + hereby transferred. + + This is a demo example: + + THIS SOFTWARE IS PROVIDED BY THE CONTRIBUTOR ``AS IS'' AND + ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + ARE DISCLAIMED. IN NO EVENT SHALL THE CONTRIBUTOR BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + SUCH DAMAGE. +" +"{ Package: 'stx:libbasic' }" + +"{ NameSpace: Smalltalk }" + +ArrayedCollection variableByteSubclass:#BitArray + instanceVariableNames:'tally' + classVariableNames:'' + poolDictionaries:'' + category:'Collections-Arrayed' +! + +!BitArray class methodsFor:'documentation'! + +copyright +" + COPYRIGHT (c) 1997 by eXept Software AG / Claus Gittinger + All Rights Reserved + + This software is furnished under a license and may be used + only in accordance with the terms of that license and with the + inclusion of the above copyright notice. This software may not + be provided or otherwise made available to, or used by, any + other person. No title to or ownership of the software is + hereby transferred. + + This is a demo example: + + THIS SOFTWARE IS PROVIDED BY THE CONTRIBUTOR ``AS IS'' AND + ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + ARE DISCLAIMED. IN NO EVENT SHALL THE CONTRIBUTOR BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + SUCH DAMAGE. +" + +! + +documentation +" + BitArrays are specially tuned to store bits, and are useful for bulk bit/boolean data. + They require only 1/32th (32bit machines) or 1/64th (64bit machines) of the memory + compared to an array of booleans. + + They one stores 8 bits per byte. Since instances store bits in multiples + of 8, the real size of the collection is kept in an extra instance variable (tally). + It may be useful if huge boolean arrays are needed. + + There are 10 types of people in this world: + Those who understand binary, & those who don't. + + ATTENTION: + Bits 1 to 8 of the BooleanArray are stored in bits 8 to 1 of the + corresponding byte, to allow easy mapping to ASN.1 BIT STRING encoding + in the BER. (i.e. MSB-first) + Do not change this. + + [memory requirements:] + OBJ-HEADER + ((size + 7) // 8) + + [author:] + Claus Gittinger + + [see also:] + BooleanArray ByteArray WordArray Array +" +! + +examples +" + [exBegin] + (BitArray new:7) inspect + [exEnd] + [exBegin] + (BitArray new:7) basicInspect + [exEnd] + [exBegin] + |bits| + + bits := BitArray new:1000000. + (bits at:9999) printCR. + bits at:9999 put:1. + (bits at:9999) printCR. + [exEnd] +" +! ! + +!BitArray class methodsFor:'instance creation'! + +fromBytes:aByteArray + "return a new instance, capable of holding aByteArray size*8 bits, initialized from aByteArray" + + |a| + + a := self new: aByteArray size*8. + 1 to:aByteArray size do:[:i | a byteAt:i put:(aByteArray at:i)]. + ^ a + + " + BitArray fromBytes:#[ 2r00001111 2r10101010 2r01010101] + " +! + +new + "return a new instance, capable of holding size bits" + + ^ self new:0 + + " + BitArray new + " +! + +new:size + "return a new instance, capable of holding size bits" + + |nBytes| + + nBytes := (size + 7) // 8. + ^ (super new:nBytes) setTally:size + + " + BitArray new:10 + " +! + +uninitializedNew:size + ^ self new:size +! ! + +!BitArray class methodsFor:'queries'! + +maxVal + "the minimum value which can be stored in instances of me. + For BitArrays, this is 1" + + ^ 1 +! + +minVal + "the minimum value which can be stored in instances of me. + For BitArrays, this is 0" + + ^ 0 +! ! + +!BitArray methodsFor:'accessing'! + +at:index + "retrieve the bit at index (1..)" + + |byte mask i0| + + (index between:1 and:tally) ifFalse:[ + ^ self subscriptBoundsError:index + ]. + i0 := index - 1. + byte := super basicAt:(i0 // 8)+1. + mask := 1 bitShift:(7 - (i0 \\ 8)). + ^ (byte bitTest:mask) ifTrue:[1] ifFalse:[0] + + " + (BitArray new:1000) at:555 + (BitArray new:1000) at:400 put:1; at:400 + " + + " + |b| + + b := BitArray new:1000. + b at:555 put:1. + b at:555 + " +! + +at:index put:aNumber + "store the argument, aNumber at index (1..); + return the argument, aNumber (sigh)." + + |byte mask idx i0| + + (index between:1 and:tally) ifFalse:[ + ^ self subscriptBoundsError:index + ]. + + i0 := index - 1. + idx := (i0 // 8) + 1. + byte := super basicAt:idx. + mask := 1 bitShift:(7 - (i0 \\ 8)). + aNumber == 1 ifTrue:[ + byte := byte bitOr:mask + ] ifFalse:[ + aNumber == 0 ifTrue:[ + byte := byte bitAnd:(mask bitInvert) + ] ifFalse:[ + "/ not 0 or 1 + ^ self elementBoundsError:aNumber + ] + ]. + super basicAt:idx put:byte. + ^ aNumber. + + " + |b| + + b := BitArray new:1000. + b at:555 put:1. + b at:555 + " +! + +byteAt:index + "retrieve 8 bits at index; the index is 1 for the first 8 bits, 2 for the next 8 bits etc." + + ^ self basicAt:index + + " + ((BitArray new:8) at:1 put:1); byteAt:1 + " +! + +byteAt:index put:aByte + "store 8 bits at index; the index is 1 for the first 8 bits, 2 for the next 8 bits etc." + + ^ self basicAt:index put:aByte + + " + ((BitArray new:8) byteAt:1 put:128); at:1 + " +! + +occurrencesOf:anElement + "count the occurrences of the argument, anElement in the receiver" + + |nOnes| + + nOnes := self countOnes. + anElement == 1 ifTrue:[ + ^ nOnes + ]. + anElement == 0 ifTrue:[ + ^ tally - nOnes + ]. + ^ 0 + + " + (BitArray new:10) + at:4 put:1; + at:6 put:1; + at:7 put:1; + occurrencesOf:1 + + (BitArray new:10) + at:4 put:1; + at:6 put:1; + at:7 put:1; + occurrencesOf:0 + " +! ! + +!BitArray methodsFor:'converting'! + +bytes + "answer myself as a ByteArray containing my bytes" + + |size bytes| + + size := self basicSize. + bytes := ByteArray new:size. + 1 to:size do:[:index| + bytes at:index put:(self byteAt:index) + ]. + ^ bytes +! ! + +!BitArray methodsFor:'filling & replacing'! + +atAllPut:aNumber + "replace all elements of the collection by the argument, aNumber. + The argument, aBoolean must be 0 or 1. + Notice: This operation modifies the receiver, NOT a copy; + therefore the change may affect all others referencing the receiver." + + |v lastIndex| + + lastIndex := self basicSize. + lastIndex == 0 ifTrue:[^ self]. + + aNumber == 1 ifTrue:[ + v := 255 + ] ifFalse:[ + aNumber == 0 ifTrue:[ + v := 0 + ] ifFalse:[ + "/ + "/ booleanArrays can only hold true and false + "/ + ^ self elementBoundsError:aNumber + ] + ]. + 1 to:lastIndex-1 do:[:i | + self basicAt:i put:v + ]. + + "/ ensure 0-bits above tally + v := #[ 2r11111111 + 2r10000000 + 2r11000000 + 2r11100000 + 2r11110000 + 2r11111000 + 2r11111100 + 2r11111110 ] at:(tally\\8)+1. + self basicAt:lastIndex put:v. + + " + ((self new:10) atAllPut:1) countOnes + ((self new:8) atAllPut:1) countOnes + " +! ! + +!BitArray methodsFor:'logical operations'! + +bitOr:aBitArray + |new mySize "{ Class: SmallInteger }" otherSize "{ Class: SmallInteger }"| + + mySize := self basicSize. + otherSize := aBitArray basicSize. + + new := self class basicNew:(mySize max:otherSize). + new setTally:(self size max:aBitArray size). + + 1 to:mySize do:[:i| + new basicAt:i put:(self basicAt:i). + ]. + 1 to:otherSize do:[:i| + new basicAt:i put:((new basicAt:i) bitOr:(aBitArray basicAt:i)). + ]. + + ^ new + + " + ((BitArray new:5) at:3 put:1; yourself) bitOr:((BitArray new:8) at:5 put:1; yourself) + " +! ! + +!BitArray methodsFor:'private'! + +countOnes + "count the 1-bits in the receiver" + + |sz bI count| + + count := 0. + + "/ because remaining bits in the highest byte are always 0, + "/ we can simply count the 1-bits in ALL bytes... (see lastByte handling in atAllPut:) + bI := 1. + sz := self basicSize. + [bI <= sz] whileTrue:[ + count := count + (self basicAt:bI) bitCount. + bI := bI + 1. + ]. + ^ count + +"/ |i nI bI bits count| +"/ i := bI := 1. +"/ [ +"/ nI := i + 8. +"/ nI <= tally +"/ ] whileTrue:[ +"/ bits := self basicAt:bI. +"/ count := count + bits bitCount. +"/ bI := bI + 1. +"/ i := nI +"/ ]. +"/ [i <= tally] whileTrue:[ +"/ (self at:i) ifTrue:[ count := count + 1]. +"/ i := i + 1. +"/ ]. +"/ ^ count + + " + (BooleanArray new:100) + at:14 put:true; + at:55 put:true; + countOnes + + (BooleanArray new:100) + at:14 put:true; + at:55 put:true; + occurrencesOf:true + + (BooleanArray new:100) + at:14 put:true; + at:55 put:true; + occurrencesOf:false + " +! + +indexOfNth:n occurrenceOf:what + "return the index of the nTh occurrence of a value, or 0 if there are not that many" + + |sz byteIndex count countInByte| + + n > self size ifTrue:[^ 0]. + + count := 0. + + byteIndex := 1. + sz := self basicSize. + [byteIndex <= sz] whileTrue:[ + countInByte := (self basicAt:byteIndex) bitCount. + what = self defaultElement ifTrue:[ + countInByte := 8-countInByte. + ]. + count := count + countInByte. + count >= n ifTrue:[ + count := count - countInByte. + (byteIndex-1)*8+1 to:(byteIndex-1)*8+8 do:[:bitIndex | + (self at:bitIndex) = what ifTrue:[ + count := count + 1. + count = n ifTrue:[ + ^ bitIndex. + ] + ]. + ]. + ^ 0 + ]. + byteIndex := byteIndex + 1. + ]. + ^ 0 + + " + (BooleanArray new:100) + at:1 put:true; + at:2 put:true; + at:4 put:true; + at:5 put:true; + at:6 put:true; + at:7 put:true; + at:8 put:true; + at:10 put:true; + indexOfNth:8 occurrenceOf:false + " +! + +setTally:size + "set my tally - that is the actual number of bits in me + (usually a little less than the number of bits in my byte array)" + + tally := size +! ! + +!BitArray methodsFor:'queries'! + +defaultElement + ^ 0 +! + +isValidElement:anObject + "return true, if I can hold this kind of object" + + ^ anObject == 0 or:[anObject == 1] +! + +size + "return the size of the receiver" + + ^ tally +! ! + +!BitArray methodsFor:'visiting'! + +acceptVisitor:aVisitor with:aParameter + "dispatch for visitor pattern; send #visitBitArray:with: to aVisitor" + + ^ aVisitor visitBitArray:self with:aParameter +! ! + +!BitArray class methodsFor:'documentation'! + +version + ^ '$Header$' +! + +version_CVS + ^ '$Header$' +! ! +