Efficiently find an integer in a sorted collection of integer ranges

Problem

I have a large list of IP-address ranges, and I want to efficiently find the ranges to which a given IP-address is in range. Overlap of ranges is possible. For simplicity and generalization of this problem for Stackoverflow, I substitute IP-address with an integer. (But basically, it could be any custom class for which a range and ordering of ranges could apply.)

Problem example

// 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); 
}
}

Given the list of ranges above, I would like to find the ranges which contains a given integer, for example 10. In that case, only the range [8, 12] would match, so that would be the result.

Question

How can I solve this problem with the Java Collection API, if possible?
The solution should be efficient, so a brute force N search through a list is not effective enough.

I could also manually create a binary search tree, but I would expect that something like this should be somehow possible using the Java Collection API using comparators and things like a TreeSet?

Normally, when using a TreeSet, I would search for the same type of element, for example, search for a Person object, where the firstname and lastname have to match to be equal. But in this case, I want to search for an integer in a TreeSet of IntRanges, so the equals method is not suitable.

Example with IP-addresses instead of integers

Solutions can be provided for integers instead of IP-addresses, to keep the question general and simple. But in case you want to try it for IP-addresses, can this code can be used to represent IP-address ranges:

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;
}
}

If the ranges are disjoint (one range never overlaps with or contains other ranges), this is easy to solve with TreeMap.

Create a TreeMap which associates the start of the range with the end of the range:

var map = new TreeMap<Integer,Integer>()
map.put(-10, 5)
map.put(8, 12)
map.put(20, 30)
map.put(800, 1000)

Then, you can use the floorEntry method to find if a number is potentially within a range. For example, floorEntry(25) will return the map entry with key 20 and value 30, corresponding to the range 20-30. Then you simply check if your number is less than the end of the range you've found.

boolean isContainedInRange(int value) {
Map.Entry<Integer, Integer> entry = map.floorEntry(value);
return entry != null && value < entry.getValue());
}

For the general case, where ranges may overlap and you are looking for all ranges, one solution is to have two TreeMaps: one associates the range start with the range end, and the other does the reverse.

var reverseMap = new TreeMap<Integer,Integer>();
reverseMap.put(5, -10);
reverseMap.put(12, 8);
reverseMap.put(13, 9);
reverseMap.put(30, 20);

Now, given a value, with these two maps you can find the set of ranges that start before a value using map.headMap(). You can also find the set of ranges that end after the given value using reverseMap.tailMap(). The set intersection of these two gives you all the ranges that contain the given value. The intersection is computed with the Set.retainAll method.

TreeMap<Integer, Integer> ranges = new TreeMap<>(map.headMap(value, true));
ranges.keySet().retainAll(reverseMap.tailMap(value).values());

This is not particularly efficient though. For an efficient solution, you will need to implement a custom data structure, such as:

• https://en.wikipedia.org/wiki/Segment_tree
• https://en.wikipedia.org/wiki/Interval_tree

Try binarySearch(List<? extends T> list, T key, Comparator<? super T> c))

By choosing a suitable Comparator<IntRange> class you can get the negative insertion point (i.e. (-(insertion point) - 1)) or the correct index of the key. The insertion point is defined as the point at which the key would be inserted into the list. An additional inRange() test can check if the key is available at the index position.

package examples;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Objects;
//Note: this class has a natural ordering that is inconsistent with equals.
class IntRange {
private static class IntComparator implements Comparator<IntRange> {
@Override
public int compare(IntRange o1, IntRange o2) {
if (o1.start <= o2.start && o1.end >= o2.end) {
return 0;
}
if (o1.start < o2.start) {
return -1;
} else if (o1.start > o2.start) {
return 1;
} else if (o1.end > o2.end) {
return 1;
}
return -1;
}
}
private static List<IntRange> findRanges(List<IntRange> ranges, int i) {
IntRange test = new IntRange(i, i);
int index = Collections.binarySearch(ranges, test, new IntComparator());
if (index < 0) {
index = -(index + 1);
}
ArrayList<IntRange> result = new ArrayList<IntRange>();
for (int j = index - 1; j >= 0; j--) {
IntRange r = ranges.get(j);
if (r.inRange(i)) {
result.add(0, r);
} else {
break;
}
}
for (int j = index; j < ranges.size(); j++) {
IntRange r = ranges.get(j);
if (r.inRange(i)) {
result.add(r);
} else {
break;
}
}
return result;
}
public static void main(String[] args) {
ArrayList<IntRange> ranges = new ArrayList<IntRange>();
ranges.add(new IntRange(-10, 5));
ranges.add(new IntRange(8, 12));
ranges.add(new IntRange(17, 20));
ranges.add(new IntRange(20, 30));
ranges.add(new IntRange(800, 1000));
// Should contain IntRange(8, 12) as result
List<IntRange> matchingRanges = findRanges(ranges, 10);
for (int i = 0; i < matchingRanges.size(); i++) {
System.out.println(matchingRanges.get(i).toString());
}
// Should contain IntRange(17, 20) and IntRange(20, 30) as result
matchingRanges = findRanges(ranges, 20);
for (int i = 0; i < matchingRanges.size(); i++) {
System.out.println(matchingRanges.get(i).toString());
}
}
private int start;
private int end;
public IntRange(int start, int end) {
this.start = start;
this.end = end;
}
@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);
}
public boolean inRange(int i) {
return i >= start && i <= end;
}
@Override
public String toString() {
return "IntRange [start=" + start + ", end=" + end + "]";
}
}