java整数区间

为什么写这个类？

• 投放系统每条投放都会附带一组城市id，如果投放全国，或者海外全部，或某种城市组合，导致内容放入redis过大(超过2MB无法放入redis)，经过分析城市id大多是连续的，因此采用该类对城市id列表做压缩

为什么不使用bitmap或bitset？

• 看bitset源码发现 一个bitmap, bitset受最大值的影响，而不因为数字个数影响其内存占用

如何兼顾查找效率？

• 从一组城市id转变为整数区间时，会对区间进行排序形成有序区间，数据结构选用ArrayList，算法采取二分查找，以此达到更好的查找效率

使用区间类替换Set之后的效果？

• 对比redis里面的数据大小，同一个运营位的内容从2.05MB下降到 115KB, 压缩效果明显

import com.google.common.collect.Lists;
import lombok.Getter;
import lombok.Setter;
import org.apache.commons.collections.CollectionUtils;

import java.io.Serializable;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

/**
 * 功能描述: 用于表达连续的整数区间
 *
 * @author : yuanchao.he
 * @version 1.0 2017-04-06
 */
@Getter
@Setter
public class LocalRange implements Serializable {
    private int lowerRange;
    private int upperRange;

    public LocalRange(int lowerRange, int upperRange) throws Exception {
        if (lowerRange > upperRange) {
            throw new Exception(
                "invalid range number, upperRange must greater or equal to lowerRange");
        }
        this.lowerRange = lowerRange;
        this.upperRange = upperRange;
    }

    private LocalRange() {}

    /**
     * 单个区间内是否包含特定的整数
     * @param current
     * @return
     */
    public boolean contains(final int number) {
        return this.lowerRange <= number && number <= this.upperRange;
    }

    /**
     * 一组区间内是否包含特定的整数
     * @param ranges
     * @param number
     * @return
     */
    public static boolean contains(final List<LocalRange> ranges, final int number){
        return binarySearch(ranges, number)!=null;
    }

    /**
     * 采用二分查找的方式来查询
     * @param ranges
     * @param number
     * @return
     */
    public static LocalRange binarySearch(List<LocalRange> ranges, int number) {
        if (CollectionUtils.isEmpty(ranges)) {
            return null;
        }
        int from = 0;
        int to = ranges.size() - 1;
        while (from <= to) {
            int middle = (to - from) / 2 + from;
            if (ranges.get(middle).contains(number)) {
                return ranges.get(middle);
            }
            if (ranges.get(middle).getUpperRange() < number) {
                from = middle + 1;
            }
            if (ranges.get(middle).getLowerRange() > number) {
                to = middle - 1;
            }
        }
        return null;
       }

    /**
     * 将集合中的整数转化为一组区间
     * @param collection
     * @return
     */
    public static List<LocalRange> fromCollection(Collection<Integer> collection) {
        if (CollectionUtils.isEmpty(collection)) {
            return Collections.emptyList();
        }
        List<Integer> numbers = Lists.newArrayList(collection);
        Collections.sort(numbers);
        List<LocalRange> ranges = Lists.newArrayList();
        int lowerRange = numbers.get(0);
        int upperRange = numbers.get(0);
        for (int index = 1; index < numbers.size(); index++) {
            if ((upperRange + 1) == numbers.get(index)) {
                upperRange = numbers.get(index);
            } else {
                ranges.add(LocalRange.init(lowerRange, upperRange));
                lowerRange = numbers.get(index);
                upperRange = lowerRange;
            }
        }
        ranges.add(LocalRange.init(lowerRange, upperRange));
        return ranges;
    }

    private static LocalRange init(int lowerRange, int upperRange) {
        LocalRange localRange = new LocalRange();
        localRange.lowerRange = lowerRange;
        localRange.upperRange = upperRange;
        return localRange;
    }

}