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: Wanted: List of intervals Date: 16 Feb 2017 21:13:26 GMT Organization: Private site at Eddersheim, Germany Lines: 31 Distribution: world Message-ID: X-Trace: individual.net 1hI0H1hATGL8Mr4e1/uKxgXkcM3hO6BIpTfqYWWKeJORRna5kS Cancel-Lock: sha1:OKjJw5WFXIUmySzEEUnICIxG6C0= Xref: csiph.com comp.lang.java.programmer:36310 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. Why do I worry? Because some essential native libraries are 32-bit only... -- "I'm a doctor, not a mechanic." Dr Leonard McCoy "I'm a mechanic, not a doctor." Volker Borchert