Path: csiph.com!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Andreas Leitgeb <avl@logic.at>
Newsgroups: comp.lang.java.programmer
Subject: Re: Wanted: List of intervals
Date: Sun, 19 Feb 2017 17:36:18 -0000 (UTC)
Organization: A noiseless patient Spider
Lines: 39
Message-ID: <slrnoajm02.pvm.avl@logic.at>
References: <o854lm$f4d$1@Gaia.teknon.de> <o85eag$uqr$1@dont-email.me> <o85qo5$kpr$1@Gaia.teknon.de> <o86p7j$5ea$1@dont-email.me> <o88v9p$gln$1@Gaia.teknon.de> <o89hiu$fj$2@dont-email.me> <o8a923$qv3$1@Gaia.teknon.de> <o8cf5p$76l$1@dont-email.me>
Reply-To: avl@logic.at
Injection-Date: Sun, 19 Feb 2017 17:36:18 -0000 (UTC)
Injection-Info: mx02.eternal-september.org; posting-host="5c08112f5fa74d29b8a2fb56bc769941"; logging-data="19385"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18iu83l3iVBFu01XoicdO3U"
User-Agent: slrn/1.0.2 (Linux)
Cancel-Lock: sha1:+SCgZtdVnS08aI33aewbW8bj6mk=
Xref: csiph.com comp.lang.java.programmer:36343

Eric Sosman <esosman@comcast-dot-net.invalid> wrote:
>      Although at first I thought you were more concerned with speed
> than with size, it now appears memory consumption is important to
> you also.  If that's the case, ...
>      1) If you are Quite Certain that the intervals are disjoint,

(Any "you"-references furtheron address the OP, not Eric)

Under this disjointness-assumption I'd create a SparseBigBitSet class:

It holds an array of BitSet of some (fine-tuneable) size BLOCK each.
The SparseBigBitSet will implement something like Set<Long> interface,
(except maybe for primitive long, rather than Long) and for each
offset l, l will be split into l/BLOCK and l%BLOCK, where l/BLOCK
will determine which BitSet to pick from main array (and on demand 
create it), while l%BLOCK will address the bit within the BitSet.
Due to signedness of int used within each BitSet and on the array,
you might only get close to virtual 2^62 bits of the total long range.
If that's a problem, split up the array into a cascade of arrays.
(the more levels of arrays you stack, the better will the "sparse-
feature" work.)

This will provide you with a giant virtual bitset, whose total
consumed heap-size will only roughly grow with actual 1-bits
saved in it.

For convenience, the SparseBigBitSet class should offer a 
toggle(long l) method, because that will be the most common
operation used on it.

When you read in the data from file, you toggle each offset in the
bit set.  Any offset that shows up twice (and thus disappears) was
a join-point of two adjacent intervals.

For reading out, BitSet has a method for finding next 1-bits, and
between the BitSets you can skip all null-entries in your array.
Iterating the 1-bits, then you get alternating interval starts 
and interval ends, already sorted!