Ok, nach einigem Tüfteln konnte ich anscheinend eine funktionierende Version implementieren. Also für diejenigen, die nach einer funktionierenden Lösung suchen, hier ist meine:
private static class RangeVal implements Comparable {
public final BigInteger value;
public int count;
public RangeVal(BigInteger value, int count) {
super();
this.value = value;
this.count = count;
}
@Override
public String toString() {
return value + (isStart() ? "S" : "E") + count;
}
@Override
public int compareTo(RangeVal o) {
// Zuerst nach Wert sortieren
int v = value.compareTo(o.value);
if (v != 0)
return v;
// Dann Starts vor Ende sortieren
return -count;
}
public boolean isStart() {
return count > 0;
}
}
/**
* Eine Liste von Bereichen nach ihrer Nummer sortieren, dann Anfang/Ende sortieren und mehrere Start-/Endwerte zusammenführen
*
* @param temp
* eine Liste von RangeVal, die unsortiert sein kann
*/
private static void preSort(List temp) {
Collections.sort(temp);
RangeVal last = null;
for (Iterator iterator = temp.iterator(); iterator.hasNext();) {
RangeVal rangeVal = iterator.next();
if ((last != null) && last.value.equals(rangeVal.value) && (last.isStart() == rangeVal.isStart())) {
iterator.remove();
last.count += rangeVal.count;
} else
last = rangeVal;
}
}
/**
* Teilt eine Liste in ValueRange-Objekte auf, die sich nicht überschneiden, aber die von den Werten angegebenen Bereiche vollständig darstellen
*
* @param value
* eine Liste von RangeVal-Objekten, die aufgeteilt werden müssen
* @return
*/
private static SortedSet split(List value) {
preSort(value);
SortedSet res = new TreeSet();
int count = 0;
BigInteger start = null;
for (RangeVal rangeVal : value) {
count += rangeVal.count;
if (rangeVal.isStart()) {
if (start != null) {
//Wenn ein Start nicht beendet wurde, müssen wir ihn gerade vor dem neuen Start beenden
res.add(new ValueRange(start, rangeVal.value.subtract(BigInteger.ONE)));
}
//Setze den Start auf das aktuelle Element
start = rangeVal.value;
} else {
//Beende den aktuellen Bereich bei diesem Element
res.add(new ValueRange(start, rangeVal.value));
if (count > 0) {
//Wenn wir später ein weiteres Ende erwarten, muss das Element nach diesem um eins weiter starten
start = rangeVal.value.add(BigInteger.ONE);
} else
//Kein neuer Bereich mehr
start = null;
}
}
return res;
}
public static void main(String[] args) {
// 5->8 9->10 11
System.out.println(split(createRanges(5, 8, 9, 10, 11, 11)));
// 5, 6->7, 8, 9, 10
System.out.println(split(createRanges(5, 10, 6, 8, 8, 9)));
System.out.println(split(createRanges(5, 10, 6, 8, 8, 9, 6, 9)));
System.out.println(split(createRanges(5, 10, 6, 8, 8, 9, 6, 9, 6, 11, 8, 9)));
System.out.println(split(createRanges(5, 10, 6, 8, 8, 9, 6, 9, 6, 11, 8, 9, 14, 18)));
}
private static List createRanges(int... r) {
List temp = new LinkedList();
for (int i = 0; i < r.length; i++) {
temp.add(new RangeVal(BigInteger.valueOf(r[i]), (i % 2) == 0 ? 1 : -1));
}
System.out.println("HDLSimulator.createRanges()" + temp);
return temp;
}
