Hi Ralph,

On Sun, Aug 22, 2010 at 6:11 PM, Ralph Boland <rpboland at gmail.com> wrote:
> 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.
> Instead I want to map each set to an array of approximately size
> n/8 bytes which, because my sets will be dense, will save space.
> Containment of a number k  in a set is to be determined by testing
> whether bit  k  is set or cleared.  Pretty standard stuff I think.
>
> Is there code already that does this?

I'm not positive what your requirements are, but a number of
special-collections related to storing Integers are available when you
load Magma.

"MaLargeArrayOfNumbers" is an auto-growing, never-shrinking array of
numbers.  All numbers have the same number of bits available to
represent them, which must be set at creation time.  It supports the
#add:, #at:, #at:put:, and #size API, and uses a file to allow an
array-of-numbers that is larger than available RAM.

"MaIntervalCollection" keeps track of a collection of intervals.  As
intervals are added that intersect or are within the
proximityThreshold of existing intervals, the existing interval is
enlarged to include for the new interval.  If an interval is removed
in the middle of a large interval such that a "hole" is created, a new
interval will be created and the adjacent one is adjusted so that they
will represent only the valid ranges.

Finally, MaHashIndex is a Integer key / Integer value Dictionary that,
like MaLargeArrayOfNumbers, can employ the file-system for sizes
larger than RAM, as well as access by index position.  However, it
also allows access by key.

All of these are part of a subordinate package ("Ma special
collections") that can be used without Magma, I just don't have
updated separate configurations for all sub-packages...

HTH,
  Chris