Find connecting ranges in a set a ranges

Question

Lets say I have the following set of ranges:

1 -> 3
4 -> 5
7 -> 8
13 -> 15
16 -> 16

How can I get a set of:

1 -> 5
7 -> 8
13 -> 16

Please change your question from library finding request (which is off-topic) to something else like, "how can I change this ... into that ...?". Also consider providing more info about your problem, like if ranges are always ordered, can they intersect, and so on... — Pshemo, Apr 10 '15 at 14:38
You could arrange this in a **Range Tree**. This would be a really easy structure to implement. See the following link. http://en.wikipedia.org/wiki/Range_tree. . . . You could also use a **Segment Tree**: http://en.wikipedia.org/wiki/Segment_tree — Evan Bechtol, Apr 10 '15 at 14:39
Maybe this can help (in the same spirit): http://stackoverflow.com/questions/23070332/translate-sorted-set-to-a-range-statement-in-java/23070645 — Alexis C., Apr 10 '15 at 14:41
Sort by *left* border, then combine if `next left border <= prior right border + 1` — Dmitry Bychenko, Apr 10 '15 at 14:42
Guava's `RangeSet` is a general-purpose tool for this sort of problem. — Louis Wasserman, Apr 10 '15 at 16:13

score 0 · Answer 1 · answered Apr 10 '15 at 14:51

Why would you need a library for this? Thats not that much code.

class Range{         
     int start , end;

     public Range(int start , int end){
          this.start = start;
          this.end = end;
     }
}

public static void join(List<Range> ranges){
     //sort the list ascending for easier comparison
     Collections.sort(ranges , (r1 , r2) -> {
          if(r1 < r2)return -1;
          else if(r1 > r2)return 1;
          else return 0;
     });

     int tmp = 1; //counter for the position in the list
     while(tmp < ranges.size()){
          if(ranges.get(tmp).start < ranges.get(tmp - 1).end){
                //the range at position tmp intersects with the previous 
                //one -> replace with the joined ranges
                Range r = new Range(ranges.get(tmp - 1).start , ranges.get(tmp).end);
                ranges.remove(tmp);
                ranges.remove(tmp - 1);
                ranges.add(r , tmp - 1);
           }else
                tmp++;//this pair (tmp - 1 / tmp) doesn't intersect -> next pair
     }
}

I'm not sure you can make the assumption that ranges are given in order, although in his question they certainly are... — kpie, Apr 10 '15 at 14:58
@kpie i didn't make any assumptions. The first thing my algorithm does is sorting the ranges. — , Apr 10 '15 at 14:59
@kpie thats a lambda expression that is representing a comparator. — , Apr 10 '15 at 15:16

score 0 · Answer 2 · answered Apr 10 '15 at 14:56

I would probably use sets. (psudo-code) something like

pairs = "a -> b \n c -> d \n e -> f"

for example

listOfPairs = pairs.split("\n")
_set = new set()
for k : listOfPairs{
    temp = k.split("->")
    _set += _set( range(temp[1],temp[2]) )
}

At This point we have a set with all the numbers in the ranges. Now we have to go over the total range and identify the sub ranges.

c = min(_set)
ans = ""
while(c <= max(_set)){
    if(c in _set && !(c-1 in _set) ){
        ans += string(c) + "->"
    }
    if( (c in _set) && !(c+1 in _set) ){ 
        ans += string(c) + " \n"
    }
}

score 0 · Answer 3 · answered Apr 10 '15 at 15:28

This can also be implemented with a TreeMap whose keys are the range starts and values are the range ends as follows:

public class ContinuousRangeSet {
    private TreeMap<Integer, Integer> ranges = new TreeMap<Integer, Integer>();

    public void addRange(int start, int end) {
        int effectiveStart = start, effectiveEnd = end;
        Map.Entry<Integer, Integer> previousRange = ranges.floorEntry(start);
        if (previousRange != null && previousRange.getValue() + 1 >= start) {
            // the start is in the middle of an existing range
            effectiveStart = previousRange.getKey();
        }

        SortedMap<Integer,Integer> overlappingRanges = ranges.subMap(start, true, end + 1, true);
        if (!overlappingRanges.isEmpty()) {
            Integer lastOverlappingKey = overlappingRanges.lastKey();
            if (ranges.get(lastOverlappingKey) > end) {
                // the end is in the middle of an existing range
                effectiveEnd = ranges.get(lastOverlappingKey);
            }
        }
        // we don't want to keep the overlapping ranges
        overlappingRanges.clear();

        ranges.put(effectiveStart, effectiveEnd);
    }

    public static void main(String[] args) {
        ContinuousRangeSet rangeSet = new ContinuousRangeSet();
        rangeSet.addRange(1, 3);
        rangeSet.addRange(4, 5);
        rangeSet.addRange(7, 8);
        rangeSet.addRange(13, 15);
        rangeSet.addRange(16, 16);
        System.out.println(rangeSet.ranges);

        rangeSet.addRange(3, 14);
        System.out.println(rangeSet.ranges);
    }
}

Output:

{1=5, 7=8, 13=16}
{1=16}

(notice I didn't test all the edge cases...)

Find connecting ranges in a set a ranges

3 Answers3