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: 17 Feb 2017 02:49:07 GMT Organization: Private site at Eddersheim, Germany Lines: 59 Distribution: world Message-ID: References: X-Trace: individual.net YA2ppy/32iy+LB35M+6Y9wNJSNi2tT4U55mBSGKvZXF/Jhk6Zk Cancel-Lock: sha1:Bq4pavrA49iwwDSpxM5A4Ruh39g= Xref: csiph.com comp.lang.java.programmer:36319 Arne Vajh??j wrote: > On 2/16/2017 4:13 PM, Volker Borchert wrote: > > Given: a file containing an unordered list of disjoint but possibly > > adjacent [long lower, long upper) intervals. > > Wanted: a list of such intervals, sorted by lower, with adjacent input > > intervals concatenated > > > > The worst case input list size n is (current knowledge) a million. > > > > Currently, I just read them into an ArrayList, sort() it and finally > > concatenate. ("Make it work _first_ before you make it work _fast_.") > > Asymptotic time is dominated by sorting's O(n log n). > > > > Does anyone know of a suitable (i.e., asymptotic time O(n log n) > > or better, but less than 2n references) data structure that merges > > during insertion? Apache commons-collections TreeList is unordered > > thus requires binary search at O(log^2 n) for insert, and standard > > TreeSet seems to be expensive when looking for previous and next. > > > > BSD-ish license preferred, LGPL OK, commercial will be considered. > > > > If I can't find anything, I'll probably write a special mergesort > > that does the concatenation during merge. Not optimal, but better > > than nothing and easy enough. > > You say *long*. Does that mean that total range bytes can not be > in memory? I think you misunderstood, maybe I wasn't clear enough. I'll provide a trivial example. Given: a file reading 27 48 250 260 115 162 60 81 203 240 85 100 272 304 162 203 10 27 350 372 304 350 Wanted: an Iterable containing 10 48 60 81 85 100 115 240 250 260 272 373 Or: an array containing 10 48 60 81 85 100 115 240 250 260 272 373 Or: ...? -- "I'm a doctor, not a mechanic." Dr Leonard McCoy "I'm a mechanic, not a doctor." Volker Borchert