Path: csiph.com!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: v_borchert@despammed.com (Volker Borchert)
Newsgroups: comp.lang.java.programmer
Subject: Re: Wanted: List of intervals
Date: 11 Mar 2017 18:15:03 GMT
Organization: Private site at Eddersheim, Germany
Lines: 40
Distribution: world
Message-ID: <oa1er7$1mm$1@Gaia.teknon.de>
References: <o854lm$f4d$1@Gaia.teknon.de> <6jjvbc1irodjda97u74rd9e855hm75oqd1@4ax.com> <o9sajn$j53$1@Gaia.teknon.de> <slrnoc3o37.sk7.avl@logic.at> <o9vkil$gkj$1@Gaia.teknon.de> <slrnoc7s5n.sk7.avl@logic.at>
X-Trace: individual.net NFq68m38c4pbdRhdEGYBtAnh0lZBhl4w6/gmu2uBPUNYl+8QVu
Cancel-Lock: sha1:MWoFfo7mT7z/EWiwpP+Wj8X/w8M=
Xref: csiph.com comp.lang.java.programmer:36402

Andreas Leitgeb wrote:
> Volker Borchert <v_borchert@despammed.com> wrote:
> > Andreas Leitgeb wrote:
> >> Volker Borchert <v_borchert@despammed.com> wrote:
> >> > Was hoping to find a solution to avoid creating possibly large
> >> > numbers of adjacent intervals without slowing down. Lesson learnt.
> >> Just wondering if you actually noticed the suggestions about
> >> large sparse Bitsets.
> > Yes. If I understood it correctly, it's somewhat similar to a "trie"?
> 
> In a way, yes.
> 
> The other nice aspect is, that by toggling duplicate entries, you get
> merged intervals on insertion without extra effort.

As I had noticed upthread:

>>> After some thinking and explaining the problem to my horse
>>> while warming up, I came up with a neat trick based on the
>>> precondition that the ranges do never overlap: it is sufficient
>>> to keep a single SortedSet<long>, do
>>> 	void add(long lower, long upper) {
>>> 	  if (lower < upper) {
>>> 	    if (!set.remove(lower))
>>> 	      set.add(lower);
>>> 	    if (!set.remove(upper))
>>> 	      set.add(upper);
>>> 	    assert (set.size() & 1) == 0;
>>> 	  }
>>> 	}
>>> then iteration over set will return lower and upper bounds
>>> alternatingly.

With your set, toggle() would do the "if (!remove()) add()"
efficiently.

-- 

"I'm a doctor, not a mechanic." Dr Leonard McCoy <mccoy@ncc1701.starfleet.fed>
"I'm a mechanic, not a doctor." Volker Borchert  <v_borchert@despammed.com>