Is there a Java library that will create a range of numbers from a list of numbers?

Question

I create a table of contents and I have a map of product numbers per page. So the entry might look like this:

ABC123 => [59, 58, 57, 19, 36, 15, 33, 34, 13, 39, 11, 37, 38, 21, 20, 40, 63, 60, 45, 46, 22, 23, 24, 26, 3, 2, 10, 1, 7, 6, 5, 4, 8] 

What I want to get from this:

 1-8,10,11,13,15,19-24,26,33,34,36-38,40,45,46,57-60 

I can code this, of course, but I decided that someone else had solved this problem. My googling gave nothing.

I appreciate any help you can offer, as always!

Answer 1

You can collect the numbers in a sorted set and then iterate over the numbers.

Quick and dirty example:

 SortedSet<Integer> numbers = new TreeSet<Integer>(); numbers.add( 1 ); numbers.add( 2 ); numbers.add( 3 ); numbers.add( 6 ); numbers.add( 7 ); numbers.add( 10 ); Integer start = null; Integer end = null; for( Integer num : numbers ) { //initialize if( start == null || end == null ) { start = num; end = num; } //next number in range else if( end.equals( num - 1 ) ) { end = num; } //there a gap else { //range length 1 if( start.equals( end )) { System.out.print(start + ","); } //range length 2 else if ( start.equals( end - 1 )) { System.out.print(start + "," + end + ","); } //range lenth 2+ else { System.out.print(start + "-" + end + ","); } start = num; end = num; } } if( start.equals( end )) { System.out.print(start); } else if ( start.equals( end - 1 )) { System.out.print(start + "," + end ); } else { System.out.print(start + "-" + end); } 

Productivity: 1-3,6,7,10

Answer 2

Apache Commons has an IntRange type that you can use. Unfortunately, I did not find a suitable set of utilities to create them. Here is a basic approach you could use:

 //create a list of 1-integer ranges List<IntRange> ranges = new LinkedList<IntRange>(); for ( int pageNum : pageNums ) { ranges.add(new IntRange(pageNum)); } //sort the ranges Collections.sort(ranges, new Comparator<IntRange>() { public int compare(IntRange a, IntRange b) { return Integer.valueOf(a.getMinimumInteger()).compareTo(b.getMinimumInteger()); } }); List<IntRange> output = new ArrayList<IntRange>(); if ( ranges.isEmpty() ) { return output; } //collapse consecutive ranges IntRange range = ranges.remove(0); while ( !ranges.isEmpty() ) { IntRange nextRange = ranges.remove(0); if ( range.getMaximumInteger() == nextRange.getMinimumInteger() - 1 ) { range = new IntRange(range.getMinimumInteger(), nextRange.getMaximumInteger()); } else { output.add(range); range = nextRange; } } output.add(range); 

Alternatively, you can skip the first step and create ranges directly from the sorted list of page numbers.

Answer 3

Edit: Best Description:

I had to deal with something similar to supporting a sorted set of finite ranges, I used a combination of the Guava range class and binary search to insert an element into the corresponding range or create a new single Range (range A with 1 element), eventually with a large by the number of inserts, the ranges have a chance of expanding (or reducing / splitting in case of deletion), deletion is pretty fast, because searching for the corresponding range where the element uses a binary search:

 import com.google.common.collect.DiscreteDomains; import com.google.common.collect.Lists; import com.google.common.collect.Range; import com.google.common.collect.Ranges; import java.util.Collection; import java.util.List; public class IntRangeCollection { private int factor=10; private List<Range<Integer>> rangeList=null; public IntRangeCollection() { rangeList=Lists.newArrayListWithExpectedSize(1000); } public IntRangeCollection(final int size) { rangeList=Lists.newArrayListWithExpectedSize(size); } public IntRangeCollection(final int size, final int factor) { rangeList=Lists.newArrayListWithExpectedSize(size); this.factor=factor; } protected IntRangeCollection(final List<Range<Integer>> rangeList) { this.rangeList=rangeList; } public static IntRangeCollection buildIntRangesCollectionFromArrays(final List<Integer[]> arrays) { final List<Range<Integer>> rangeList=Lists.newArrayListWithCapacity(arrays.size()); for(Integer[] range : arrays){ rangeList.add(range.length == 1 ? Ranges.singleton(range[0]) : Ranges.closed(range[0], range[1])); } return new IntRangeCollection(rangeList); } public boolean addElements(final Collection<Integer> elements) { boolean modified=false; for(Integer element : elements){ modified=addElement(element) || modified; } return modified; } public boolean removeElements(final Collection<Integer> elements) { boolean modified=false; for(Integer element : elements){ modified=removeElement(element) || modified; } return modified; } public boolean addElement(final Integer element) { final Range<Integer> elementRange=Ranges.singleton(element); if(rangeList.isEmpty()){ rangeList.add(elementRange); } else{ int start=0, mid=0, end=rangeList.size() - 1; Range<Integer> midRange=null; while(start<=end){ mid=(start + end) / 2; midRange=rangeList.get(mid); if(midRange.contains(element)){ return false; } else if(testLinkable(midRange, element)){ rangeList.set(mid, midRange.span(elementRange)); if(mid>0){ final Range<Integer> a=rangeList.get(mid - 1); if(testLinkable(a, midRange)){ rangeList.set(mid - 1, a.span(midRange)); rangeList.remove(mid); mid--; } } if(mid<rangeList.size() - 1){ final Range<Integer> b=rangeList.get(mid + 1); if(testLinkable(midRange, b)){ rangeList.set(mid, midRange.span(b)); rangeList.remove(mid + 1); } } return true; } else if(midRange.lowerEndpoint().compareTo(element)<0){ start=mid + 1; } else{ end=mid - 1; } } //noinspection ConstantConditions rangeList.add(midRange.lowerEndpoint().compareTo(element)<0 ? mid + 1 : mid, elementRange); } return true; } public boolean removeElement(final Integer element) { final Range<Integer> elementRange=Ranges.singleton(element); if(rangeList.isEmpty()){ rangeList.add(elementRange); } else{ int start=0, mid, end=rangeList.size() - 1; while(start<=end){ mid=(start + end) / 2; final Range<Integer> midRange=rangeList.get(mid); if(midRange.contains(element)){ final Integer lower=midRange.lowerEndpoint(), upper=midRange.upperEndpoint(); if(lower.equals(upper)){ rangeList.remove(mid); } else if(lower.equals(element)){ rangeList.set(mid, Ranges.closed(element + 1, upper)); } else if(upper.equals(element)){ rangeList.set(mid, Ranges.closed(lower, element - 1)); } else{ rangeList.set(mid, Ranges.closed(element + 1, upper)); rangeList.add(mid, Ranges.closed(lower, element - 1)); } return true; } else if(midRange.lowerEndpoint().compareTo(element)<0){ start=mid + 1; } else{ end=mid - 1; } } } return false; } public List<Integer> getElementsAsList() { final List<Integer> result=Lists.newArrayListWithExpectedSize(rangeList.size() * factor); for(Range<Integer> range : rangeList){ result.addAll(range.asSet(DiscreteDomains.integers())); } return result; } public List<Integer[]> getRangesAsArray() { final List<Integer[]> result=Lists.newArrayListWithCapacity(rangeList.size()); for(Range<Integer> range : rangeList){ final Integer lower=range.lowerEndpoint(), upper=range.upperEndpoint(); result.add(lower.equals(upper) ? new Integer[]{lower} : new Integer[]{lower,upper}); } return result; } public int getRangesCount() { return rangeList.size(); } private boolean testLinkable(final Range<Integer> range, final Integer element) { return Ranges.closed(range.lowerEndpoint() - 1, range.upperEndpoint() + 1).contains(element); } private boolean testLinkable(final Range<Integer> a, final Range<Integer> b) { return Ranges.closed(a.lowerEndpoint() - 1, a.upperEndpoint() + 1).isConnected(b); } @Override public String toString() { return "IntRangeCollection{" + "rangeList=" + rangeList + '}'; } public static void main(String[] args) { final int MAX_NUMBER=1000; final long startMillis=System.currentTimeMillis(); final IntRangeCollection ranges=new IntRangeCollection(); for(int i=0; i<MAX_NUMBER; i++){ //noinspection UnsecureRandomNumberGeneration ranges.addElement((int) (Math.random() * MAX_NUMBER)); } System.out.println(MAX_NUMBER + " contained in " + ranges.rangeList.size() + " ranges done in " + (System.currentTimeMillis() - startMillis) + "ms"); System.out.println(ranges); for(int i=0; i<MAX_NUMBER / 4; i++){ //noinspection UnsecureRandomNumberGeneration ranges.removeElement((int) (Math.random() * MAX_NUMBER)); } System.out.println(MAX_NUMBER + " contained in " + ranges.rangeList.size() + " ranges done in " + (System.currentTimeMillis() - startMillis) + "ms"); System.out.println(ranges); } } 

Answer 4

You can use Arrays.sort () and find nearby duplicates / ranges. However, I suspect that a TreeSet might be easier to use.

Answer 5

This is a good example ; it shows an easy way to accomplish this.