Path: csiph.com!aioe.org!.POSTED!not-for-mail
From: =?UTF-8?Q?Arne_Vajh=c3=b8j?= <arne@vajhoej.dk>
Newsgroups: comp.lang.java.programmer
Subject: Re: Wanted: List of intervals
Date: Sun, 19 Feb 2017 17:13:32 -0500
Organization: Aioe.org NNTP Server
Lines: 26
Message-ID: <o8d5aa$1pve$1@gioia.aioe.org>
References: <o854lm$f4d$1@Gaia.teknon.de> <o8583e$7tj$1@gioia.aioe.org> <o85ob3$k76$1@Gaia.teknon.de> <o85qrk$hsd$1@gioia.aioe.org> <egu8f3Fd40lU1@mid.individual.net>
NNTP-Posting-Host: PBuS014lhzVyHjLbXmo/ZQ.user.gioia.aioe.org
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Complaints-To: abuse@aioe.org
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:45.0) Gecko/20100101 Thunderbird/45.7.1
X-Notice: Filtered by postfilter v. 0.8.2
Xref: csiph.com comp.lang.java.programmer:36347

On 2/19/2017 2:02 PM, Robert Klemme wrote:
> On 17.02.2017 04:32, Arne Vajhøj wrote:
>
>> If that example is realistic then you can simply:
>> * allocate byte array of suitable length
>> * loop through intervals and mark corresponding bytes
>
> What are "corresponding bytes"?  Do you want to use the byte array as a
> bitset and mark all bits corresponding to values inside intervals?

Yes.

>> * loop through bytes and create new intervals
>>
>> But if the numbers really need to be long aka is greater
>> than MAX_INT, then that strategy does not work.
>
> Even for ints the approach seems pretty wasteful, if I understood you
> correctly.

I am not so sure about that. It is O(n) in number of intervals.
No sorting required.

Arne