Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.java.programmer > #36402
| 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> (permalink) |
| 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 |
Show key headers only | View raw
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>
Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-02-16 21:13 +0000
Re: Wanted: List of intervals Arne Vajhøj <arne@vajhoej.dk> - 2017-02-16 17:11 -0500
Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-02-17 02:49 +0000
Re: Wanted: List of intervals Arne Vajhøj <arne@vajhoej.dk> - 2017-02-16 22:32 -0500
Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-02-18 07:28 +0000
Re: Wanted: List of intervals Robert Klemme <shortcutter@googlemail.com> - 2017-02-19 20:02 +0100
Re: Wanted: List of intervals Arne Vajhøj <arne@vajhoej.dk> - 2017-02-19 17:13 -0500
Re: Wanted: List of intervals Eric Sosman <esosman@comcast-dot-net.invalid> - 2017-02-19 17:18 -0500
Re: Wanted: List of intervals Robert Klemme <shortcutter@googlemail.com> - 2017-02-19 23:31 +0100
Re: Wanted: List of intervals Arne Vajhøj <arne@vajhoej.dk> - 2017-02-19 23:00 -0500
Re: Wanted: List of intervals Arne Vajhøj <arne@vajhoej.dk> - 2017-02-19 23:09 -0500
Re: Wanted: List of intervals Arne Vajhøj <arne@vajhoej.dk> - 2017-02-19 22:52 -0500
Re: Wanted: List of intervals Eric Sosman <esosman@comcast-dot-net.invalid> - 2017-02-20 07:47 -0500
Re: Wanted: List of intervals Andreas Leitgeb <avl@logic.at> - 2017-02-20 13:30 +0000
Re: Wanted: List of intervals Arne Vajhøj <arne@vajhoej.dk> - 2017-02-20 08:51 -0500
Re: Wanted: List of intervals Robert Klemme <shortcutter@googlemail.com> - 2017-02-16 23:18 +0100
Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-02-17 02:54 +0000
Re: Wanted: List of intervals Martin Gregorie <martin@address-in-sig.invalid> - 2017-02-16 23:58 +0000
Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-02-17 03:30 +0000
Re: Wanted: List of intervals Martin Gregorie <martin@address-in-sig.invalid> - 2017-02-17 12:10 +0000
Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-02-18 08:06 +0000
Re: Wanted: List of intervals Martin Gregorie <martin@address-in-sig.invalid> - 2017-02-18 13:18 +0000
Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-02-18 19:58 +0000
Re: Wanted: List of intervals Martin Gregorie <martin@address-in-sig.invalid> - 2017-02-18 20:45 +0000
Re: Wanted: List of intervals Eric Sosman <esosman@comcast-dot-net.invalid> - 2017-02-19 10:57 -0500
Re: Wanted: List of intervals Andreas Leitgeb <avl@logic.at> - 2017-02-19 17:36 +0000
Re: Wanted: List of intervals a.laforgia@gmail.com - 2017-02-17 03:13 -0800
Re: Wanted: List of intervals Eric Sosman <esosman@comcast-dot-net.invalid> - 2017-02-17 08:20 -0500
Re: Wanted: List of intervals Roedy Green <inquiry@mindprod.com> - 2017-03-08 01:30 -0800
Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-03-09 19:32 +0000
Re: Wanted: List of intervals Andreas Leitgeb <avl@logic.at> - 2017-03-09 23:05 +0000
Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-03-11 01:40 +0000
Re: Wanted: List of intervals Andreas Leitgeb <avl@logic.at> - 2017-03-11 12:39 +0000
Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-03-11 18:15 +0000
Re: Wanted: List of intervals Andreas Leitgeb <avl@logic.at> - 2017-03-11 21:47 +0000
csiph-web