给定已排序的非重叠连续间隔的集合,如何添加新间隔或从中删除现有间隔。请建议我一个良好的数据结构来存储这些间隔,这可以使这些变化成为可能。
例:
Given collection: [1,4), [4,9), [9,12)
Insert: [5,8)
Result: [1,4), [4,5), [5, 8), [8, 9), [9, 12)
Delete: [4, 5)
Result: [1,5), [5, 8), [8, 9), [9, 12)
在删除的情况下,如果可能的话,它应该添加到前一个,否则下一个(s)。
我根本不打扰离散间隔。由于定义需要“排序的非重叠连续间隔”,我只存储间隔的边界(“intervalBoundaries
”),并且从该列表中,我将按需创建间隔范围(“getRanges()
”)。
这里我的例子(也许应该修改“deleteRange()
”方法以涵盖边缘情况):
/*
*/
package de.test.stackoverflow;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import org.apache.commons.lang.StringUtils;
public class Intervals {
public static final class Range {
final int from;
final int to;
public Range(int from, int to) {
this.from = from;
this.to = to;
}
public int getFrom() {
return from;
}
public int getTo() {
return to;
}
@Override
public String toString() {
return String.format("[%d, %d)", from, to);
}
}
final SortedSet<Integer> intervalBoundaries = new java.util.TreeSet<>();
public List<Range> getRanges() {
final List<Range> res = new java.util.ArrayList<>();
if (intervalBoundaries.size() > 1) {
final List<Integer> tmpBounds = new java.util.ArrayList<>(intervalBoundaries);
for (int i = 0; i < tmpBounds.size() - 1; i++) {
res.add(new Range(tmpBounds.get(i), tmpBounds.get(i + 1)));
}
}
return res;
}
public void insertBoundary(Integer bound) {
// duplicates in sets are automatically removed
intervalBoundaries.add(bound);
}
public void insertRange(Integer from, Integer to) {
intervalBoundaries.add(from);
intervalBoundaries.add(to);
}
public void insertRange(Range x) {
insertRange(x.getFrom(), x.getTo());
}
public void deleteRange(Range x) {
final Collection<Integer> boundsToDelete = new java.util.LinkedHashSet<>();
for (Integer intervalBoundary : intervalBoundaries) {
if (intervalBoundary >= x.getFrom() && intervalBoundary < x.getTo()) {
boundsToDelete.add(intervalBoundary);
}
}
intervalBoundaries.removeAll(boundsToDelete);
if (x.getTo() < intervalBoundaries.last()) {
insertBoundary(x.getTo());
}
if (x.getFrom() > intervalBoundaries.last()) {
insertBoundary(x.getFrom());
}
}
public static void main(String[] args) {
Intervals i = new Intervals();
i.insertRange(new Range(1, 4));
i.insertRange(new Range(4, 9));
i.insertRange(new Range(9, 12));
System.out.println("Given collection: " + StringUtils.join(i.getRanges(), ", "));
final Range insertRange = new Range(5, 8);
System.out.println("insert: " + insertRange);
i.insertRange(insertRange);
System.out.println("Result: " + StringUtils.join(i.getRanges(), ", "));
final Range deleteRange = new Range(4, 5);
System.out.println("delete: " + deleteRange);
i.deleteRange(deleteRange);
System.out.println("Result: " + StringUtils.join(i.getRanges(), ", "));
final Range deleteRange2 = new Range(3, 9);
System.out.println("delete: " + deleteRange2);
i.deleteRange(deleteRange2);
System.out.println("Result: " + StringUtils.join(i.getRanges(), ", "));
final Range deleteRange3 = new Range(2, 15);
System.out.println("delete: " + deleteRange3);
i.deleteRange(deleteRange3);
System.out.println("Result: " + StringUtils.join(i.getRanges(), ", "));
}
}