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

I am creating a table of contents, and what I have is a Map of product numbers to pages. So an 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 is:

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

I can code t开发者_JS百科his of course, but I figured that someone else has already solved this problem. My Googling has yielded naught.

I appreciate any help you can offer, as always!

You could collect the numbers into 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's 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);
}

Yields: 1-3,6,7,10

Apache Commons has the IntRange type that you can use. Unfortunately I didn't find a good corresponding set of utilities to create them. Here's the 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 could skip the first step and create the ranges directly from the sorted list of page numbers.

Edit: A better description:

I had to deal with something similar to support a sorted collection of finite ranges, I used a mix of Google's Guava Range class and binary search to insert the element at the corresponding range or create a new singleton Range (A range with 1 element), eventually with more inserts the ranges have chances of expanding (Or shrinking/splitting in case of removal), removal is pretty fast because locating the corresponding range where the element is 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);
  }

}

You can use Arrays.sort() and find neighbouring duplicates/ranges. However I suspect TreeSet may be simpler to use.

This is a good example, it shows a simple way to accomplish this.