[squeak-dev] large dense sets of 1..n

Ralph Boland rpboland at gmail.com
Tue Aug 24 01:37:28 UTC 2010


>> I need to create some dense sets which will contain
>> subsets of the integers á1..n where n is very large.
>> I don't want to use regular sets because they would use to much space.
...
>> Is there code already that does this?
...
>> Ralph Boland
>
> You can see example in WideCharacterSet in image, or also load
> BitArray from SqueakMap.

> See also these messages for playing with bits
> http://lists.squeakfoundation.org/pipermail/squeak-dev/2009-December/141893.html
...

I downloaded BitArray and discovered that it used Form.
This seemed backwards to me so I looked at Form and discovered
that Form uses Bitmap.  Bitmap looked like what I was looking for
so I looked at Bitmap.
To use Bitmap I would need to add methods  at:  and  at:put:  based on code
from class BitArray. However, the code in BitArray use instance variables
wordCache cacheIndex which make accessing consecutive bits more efficient.

So my plan was to create class BitSet which will be a subclass of Bitmap and
have instance variables wordCache and casheIndex.  Of course this didn't work
because I am not allowed to add instance variables to BitSet.

So my plan now is to make BitSet a subclass of ArrayedCollection with
an instance variable bitmap holding objects of class Bitmap.
I will implement some but not all of the methods in BitArray.
I will also implement methods booleanAt:  and booleanAt:put:.

BitSet will be a class in a package that I will eventually release to SqueakMap
so I thought it was worth allowing comments before I implement BitSet.

So comments welcome.

Regards,

Ralph Boland



More information about the Squeak-dev mailing list