gistfile1.txt

package rangeList;

import java.util.*;

class RangeList {
    TreeMap<Integer, Integer> m;
    RangeList() {
        m = new TreeMap<>();
    }

    void add(int[] range) {
        int start = range[0];
        int end = range[1];

        // 获取起始值对应的entry, 如果没有的话, 就返回比key数值更小的key中最大的一个
        Map.Entry<Integer, Integer> L = m.floorEntry(start);
        // 获取结束值对应的entry, 如果没有的话, 就返回比key数值更小的key中最大的一个
        Map.Entry<Integer, Integer> R = m.floorEntry(end);

        // 当起始值包括在原有的entry中时, 起始值沿用之前的entry
        // 不然的话起始值就用刚才floorEntry获得的值
        if (L != null && L.getValue() >= start) {
            start = L.getKey(); // update overlap start
        }

        // 当结束值被包含时, 直接使用之前的结束值
        // 不然就使用刚才floorEntry获得的结束值
        if (R != null && R.getValue() > end) {
            end = R.getValue(); // update overlap end
        }

        m.subMap(start, end).clear(); // 去除所有重复的部分
        m.put(start, end); // 把合并过的数值段存入treeMap
    }

    void remove(int[] range) {
        int start = range[0];
        int end = range[1];
        // 获取起始值对应的entry, 如果没有的话, 就返回比key数值更小的key中最大的一个
        Map.Entry<Integer, Integer> L = m.floorEntry(start);
        // 获取结束值对应的entry, 如果没有的话, 就返回比key数值更小的key中最大的一个
        Map.Entry<Integer, Integer> R = m.floorEntry(end);

        // 如果在entry中看前面删除的段落在之前还有剩余的部分, 需要补充回去
        if (L != null && L.getValue() > start) {
            m.put(L.getKey(), start);
        }

        // 如果在entry中看后面删除的段落在之前还有剩余的部分, 需要补充回去
        if (R != null && R.getValue() > end) {
            m.put(end, R.getValue());
        }

        // 删除传入的部分
        m.subMap(start, end).clear();
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();

        // 在非并发环境下直接遍历entrySet是能拿到想要的数据的
        // 如果是并发环境的话, 遍历的做法就需要有变化了
        for (Map.Entry<Integer, Integer> entry : m.entrySet()) {
            sb.append("[");

            sb.append(entry.getKey());
            sb.append(", ");
            sb.append(entry.getValue());
            sb.append(") ");
        }

        System.out.println(sb);
        return sb.toString();
    }


    public static void main(String[] args) {
        RangeList rl = new RangeList();

        rl.add(new int[]{1,5});
        rl.toString();


        rl.add(new int[]{10, 20});
        rl.toString(); // Should be: "[1, 5) [10, 20)"
        rl.add(new int[]{20,20});
        rl.toString(); // Should be: "[1, 5) [10, 20)"
        rl.add(new int[]{20,21});
        rl.toString();
        rl.add(new int[]{2, 4});
        rl.toString(); // Should be: "[1, 5) [10, 21)"

        rl.add(new int[]{3, 8});
        rl.toString(); // Should be: "[1, 8) [10, 21)"

        rl.remove(new int[]{10, 10});
        rl.toString(); // Should be: "[1, 8) [10, 21)"

        rl.remove(new int[]{10, 11});
        rl.toString(); // Should be: "[1, 8) [11, 21)"
        rl.remove(new int[]{15, 17});
        rl.toString(); // Should be: "[1, 8) [11, 15) [17, 21)"

        rl.remove(new int[]{3, 19});
        rl.toString(); // Should be: "[1, 3) [19, 21)"
    }
}