Here are some hints that should help you to solve the problem yourself:
- IP-addresses can be fully converted to numbers, and vice versa. (Explanation for Java).
- Check whether ranges overlap (should be joined) by whether one's endpoint is included in the other range.
If you want a complete guide to how you may solve your issue, read on.
Joining ranges
What can be joined?
First we need to decide what ranges may be joined, which includes:
- Ranges that overlap:
- Partly overlapping ranges.
- Ranges where one is a subrange of the other.
- Ranges whose endpoints are immediate neighbours. (Ranges that are "touching".)
Sidenote: These two statements are equivalent:
- Range
[a1, a2] and [b1, b2] are neighbours.
- Range
[a1, a2] (partly) overlaps [b1 - 1, b2 + 1]. (Or vice versa.)
Overlapping ranges will still overlap after "extension" (statement 2). We will make use of this later on.
Convert to simpler type
Now that we know the conditions for joining, we need to be able to check them.
For easier checking, we can convert the IP-addresses to integers:
- From dot-notation:
Interpret IP-address as a base-256 4-"digit" number,
where a digit is a dot-separated integer.
- To dot-notation:
- Parse number to a 8-digit hexadecimal number
(with leading zeros, if necessary).
- Interpret every two base-16 digits as one base-256 digit.
- Parse the four base-256 digits to numbers.
- Join the numbers with dots.
const ip = "192.168.0.1";
console.log("IP:", ip);
console.log("IP as number:", fromIp(ip));
console.log("IP after roundtrip:", toIp(fromIp(ip)));
function fromIp(ip) {
const numbers = ip.split(".").map(split => Number(split));
const ipAsNumber = numbers.reverse().reduce((total, number, i) => {
return total + number * (256 ** i);
}, 0);
return ipAsNumber;
}
function toIp(number) {
const numberInHex = number.toString(16).padStart(8, "0");
const hexSplits = Array.from({length:4}, (v, i) => numberInHex.slice(i * 2, i * 2 + 2));
const ipSplits = hexSplits.map(hex => parseInt(hex, 16));
return ipSplits.join(".");
}
How to check joinability
Realizing the checking may become easier to understand if we visualize the conditions:
Notice how the lines A, C, D may be joined with line B. Their commonality is (abstractly):
- The joinable line's left end is to the left of B's right end.
- The joinable line's right end is to the right of B's left end.
Or, in code:
// Similar to the visualization
const rangeA = { from: 0, to: 3 };
const rangeB = { from: 2, to: 6 };
const rangeC = { from: 3, to: 4 };
const rangeD = { from: 5, to: 7 };
// Not "touching" rangeB
const unjoinableRange = { from: rangeB.to + 2, to: 10 };
console.log("Can join A & B?", isJoinable(rangeA, rangeB));
console.log("Can join C & B?", isJoinable(rangeC, rangeB));
console.log("Can join D & B?", isJoinable(rangeD, rangeB));
console.log("Joinable with unjoinable?", isJoinable(rangeB, unjoinableRange));
function isJoinable(range1, range2) {
const maxDiff = 1; // Extend by this much; aforementioned stmt. 2 in "What can be joined?"
return (range1.from - range2.to) <= maxDiff && (range2.from - range1.to) <= maxDiff;
}
.as-console-wrapper {max-height:100%!important}
Joining
With the above sections we can easily find what ranges may be joined. But we still have to actually join them together.
For that, we can use Array.reduce() to collect the (joined) ranges as follows:
// Ranges A,B,C,D from before
const joinableRanges = [
{ from: 2, to: 6 },
{ from: 0, to: 3 },
{ from: 3, to: 4 },
{ from: 5, to: 7 }
];
const unjoinableRanges = [
{ from: 9, to: 10 },
{ from: -6, to: -2 }
];
const ranges = [...joinableRanges, ...unjoinableRanges];
const joinedRanges = reduceRanges(ranges);
console.log("Original:", ranges);
console.log("Reduced:", joinedRanges);
function reduceRanges(rangesToReduce) {
const reducedRanges = rangesToReduce.reduce((ranges, range) => {
let joinWith = range; // Start checking for current range
const nextJoinableRange = () => ranges.find(r =>
r !== joinWith // Avoid joining with self
&& isJoinable(r, joinWith)
);
let joinableRange = nextJoinableRange();
if (!joinableRange) {
// No joinable range was found; add current range
ranges.push(range);
return ranges;
}
// A joinable range was found
do {
// Remove joinable range; will be replaced with joined range
const index = ranges.indexOf(joinableRange);
ranges.splice(index, 1);
// Add joined range
const joinedRange = {
from: Math.min(joinableRange.from, joinWith.from),
to: Math.max(joinableRange.to, joinWith.to)
};
ranges.push(joinedRange);
// Continue with (checking for) joining
joinWith = joinedRange;
} while (joinableRange = nextJoinableRange());
return ranges;
}, []);
return reducedRanges;
}
function isJoinable(range1, range2) {
return (range1.from - range2.to) <= 1 && (range2.from - range1.to) <= 1;
}
.as-console-wrapper {max-height:100%!important}
Finally
Putting everything together:
- Convert from IP-address ranges to number ranges.
- Join ranges:
- If current range is unjoinable, collect.
- Otherwise, join with joinable range.
- Replace joinable range with joined range.
- Repeat for joined range from 2.
- Convert from number ranges
const ipRanges = [
{ from: "118.184.192.0", to: "118.184.223.255" },
{ from: "118.187.0.0", to: "118.187.255.255" },
{ from: "118.187.0.0", to: "118.187.63.255" },
{ from: "118.187.64.0", to: "118.187.127.255" },
{ from: "118.191.4.0", to: "118.191.5.255" },
{ from: "118.191.6.0", to: "118.191.7.255" },
{ from: "118.191.8.0", to: "118.191.11.255" },
{ from: "118.191.12.0", to: "118.191.12.255" }
];
const numberRanges = ipRanges.map(({ from, to }) =>
({ from: fromIp(from), to: fromIp(to) })
);
const joinedRanges = reduceRanges(numberRanges);
const joinedIpRanges = joinedRanges.map(({ from, to }) =>
({ from: toIp(from), to: toIp(to) })
);
console.log("IP-ranges:", ipRanges );
console.log("Reduced IP-ranges:", joinedIpRanges);
function reduceRanges(rangesToReduce) {
const reducedRanges = rangesToReduce.reduce((ranges, range) => {
let joinWith = range;
const nextJoinableRange = () => ranges.find(r =>
r !== joinWith && isJoinable(r, joinWith)
);
let joinableRange = nextJoinableRange();
if (!joinableRange) {
ranges.push(range);
return ranges;
}
do {
const index = ranges.indexOf(joinableRange);
ranges.splice(index, 1);
const joinedRange = {
from: Math.min(joinableRange.from, joinWith.from),
to: Math.max(joinableRange.to, joinWith.to)
};
ranges.push(joinedRange);
joinWith = joinedRange;
} while (joinableRange = nextJoinableRange());
return ranges;
}, []);
return reducedRanges;
}
function isJoinable(range1, range2) {
return (range1.from - range2.to) <= 1 && (range2.from - range1.to) <= 1;
}
function fromIp(ip) {
const numbers = ip.split(".").map(split => Number(split));
const ipAsNumber = numbers.reverse().reduce((total, number, i) => {
return total + number * (256 ** i);
}, 0);
return ipAsNumber;
}
function toIp(number) {
const numberInHex = number.toString(16).padStart(8, "0");
const hexSplits = Array.from({length:4}, (v, i) => numberInHex.slice(i * 2, i * 2 + 2));
const ipSplits = hexSplits.map(hex => parseInt(hex, 16));
return ipSplits.join(".");
}
.as-console-wrapper {max-height:100%!important}
This answer includes only how to join IP-address ranges.
As apparent in your answer, you receive the ranges in a specific format (ranges as start-end, one per line). You may still want to convert from that format to some easier-to-work-with object. See this as an exercise!
