Проблема
У меня большой список диапазонов IP-адресов, и я хочу эффективно найти диапазоны, в которые входит данный IP-адрес. Возможно перекрытие диапазонов. Для простоты и обобщения этой проблемы для Stackoverflow я заменяю IP-адрес целым числом. (Но в основном это может быть любой пользовательский класс, к которому может применяться диапазон и порядок диапазонов.)
Пример проблемы
// Note: this class has a natural ordering that is inconsistent with equals.
class IntRange implements Comparable<IntRange> {
private int start;
private int end;
public IntRange(int start, int end) {
this.start = start;
this.end = end;
}
public boolean inRange(int i) {
return i >= start && i <= end;
}
@Override
public int compareTo(IntRange other) {
if (start < other.start) {
return -1;
} else if (start <= other.start && end >= other.end) {
return 0;
} else {
return 1;
}
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
IntRange intRange = (IntRange) o;
return start == intRange.start && end == intRange.end;
}
@Override
public int hashCode() {
return Objects.hash(start, end);
}
}
class Program {
private static List<IntRange> findRanges(IntRange[] ranges, int i) {
// How to implement this?
}
public static void main(String[] args) {
IntRange[] ranges = {
new IntRange(-10, 5),
new IntRange(8, 11),
new IntRange(9, 13),
new IntRange(20, 30),
new IntRange(800, 1000)
};
// Should contain IntRange(8, 12) and IntRange(9, 13) as result
List<IntRange> matchingRanges = findRanges(ranges,10);
}
}
Учитывая приведенный выше список диапазонов, я хотел бы найти диапазоны, содержащие заданное целое число, например 10. В этом случае будет соответствовать только диапазон [8, 12], так что это будет результат.
Вопрос
Как можно Я решаю эту проблему с помощью Java Collection API, если возможно? Решение должно быть эффективным, поэтому простой перебор N по списку недостаточно эффективен. должно быть каким-то образом возможно с использованием Java Collection API с использованием компараторов и таких вещей, как TreeSet?
Обычно при использовании TreeSet я ищу тот же тип элемента, например, ищу объект Person , где имя и фамилия должны совпадать, чтобы быть равными. Но в этом случае я хочу найти целое число в TreeSet of IntRanges, поэтому метод equals не подходит.
Пример с IP-адресами вместо целых
Решения могут быть предоставлены для целых чисел вместо IP-адресов, чтобы вопрос был простым и общим. Но если вы хотите попробовать его для IP-адресов, можно ли использовать этот код для представления диапазонов IP-адресов:
class IpRange {
private byte[] start; // 4 bytes for IPv4, 16 bytes for IPv6
private byte[] end;
// Only for testing purposes
public IpRange(int start, int end) {
this.start = BigInteger.valueOf(start).toByteArray();
this.end = BigInteger.valueOf(end).toByteArray();
}
public IpRange(byte[] start, byte[] end) {
this.start = start;
this.end = end;
}
public boolean inRange(byte[] ip) {
return Arrays.compare(start, ip) <= 0 && Arrays.compare(end, ip) >= 0;
}
public static void main(String[] args) {
// Test 1: test inRange function
IpRange ir = new IpRange(40, 60);
System.out.println(ir.inRange(BigInteger.valueOf(39).toByteArray())); // false
System.out.println(ir.inRange(BigInteger.valueOf(50).toByteArray())); // true
System.out.println(ir.inRange(BigInteger.valueOf(61).toByteArray())); // false
// Test 2
// In production, this range contains thousands of entries
IpRange[] ranges = {
new IpRange(-10, 5),
new IpRange(8, 12),
new IpRange(20, 30),
new IpRange(800, 1000)
};
// How to efficiently check in which ranges ip is 'inRange'?
int ip = 25;
}
}