package org.davidmoten.hilbert;

import java.util.ArrayList;
import java.util.List;

//immutable
public final class Ranges {

    private final List<Range> ranges;

    Ranges(List<Range> ranges) {
        this.ranges = ranges;
    }

    public static Ranges create() {
        return new Ranges(new ArrayList<>());
    }

    static Builder builder() {
        return new Builder(new ArrayList<>());
    }

    static final class Builder {

        private List<Range> ranges;

        Builder(List<Range> ranges) {
            this.ranges = ranges;
        }

        void add(long value) {
            int modifiedIndex = -1;
            for (int i = 0; i < ranges.size(); i++) {
                Range range = ranges.get(i);
                if (range.contains(value)) {
                    throw new RuntimeException("unexpected");
                } else if (range.low() == value + 1) {
                    ranges.set(i, new Range(value, range.high()));
                    modifiedIndex = i;
                    break;
                } else if (range.high() == value - 1) {
                    ranges.set(i, new Range(range.low(), value));
                    modifiedIndex = i;
                    break;
                } else if (value < range.low()) {
                    ranges.add(i, new Range(value, value));
                    modifiedIndex = i;
                    break;
                }
            }
            if (modifiedIndex == -1) {
                ranges.add(new Range(value, value));
            } else if (modifiedIndex < ranges.size() - 1) {
                Range modified = ranges.get(modifiedIndex);
                Range r = ranges.get(modifiedIndex + 1);
                if (modified.high() == r.low() - 1) {
                    // join the two Range objects
                    ranges.set(modifiedIndex, new Range(modified.low(), r.high()));
                    ranges.remove(modifiedIndex + 1);
                }
            }
        }

        Ranges build() {
            return new Ranges(ranges);
        }
    }

    public List<Range> get() {
        return ranges;
    }

    public Ranges add(long low, long high) {
        Builder b = new Ranges.Builder(ranges);
        // TODO this is inefficient (but only used in unit tests)
        for (long i = low; i <= high; i++) {
            b.add(i);
        }
        return b.build();
    }

    public int size() {
        return ranges.size();
    }

}

@@ -2370,32 +2370,1050 @@
 build();%0A    %7D%0A%0A
+    public Ranges shrink() %7B%0A        // find the smallest gap and join those ranges%0A        int smallestGapIndex = -1;%0A        %7B%0A        long smallestGap = Long.MAX_VALUE;%0A        for (int i = 1; i %3C ranges.size(); i++) %7B%0A            long gap = ranges.get(i).low() - ranges.get(i - 1).high();%0A            if (gap %3C smallestGap) %7B%0A                smallestGap = gap;%0A                smallestGapIndex = i - 1;%0A            %7D%0A        %7D%0A        %7D%0A        if (smallestGapIndex != -1) %7B%0A            List%3CRange%3E list = new ArrayList%3C%3E(ranges.size() - 1);%0A            for (int i = 0; i %3C smallestGapIndex; i++) %7B%0A                list.add(ranges.get(i));%0A            %7D%0A            list.add(Range.create(//%0A                    ranges.get(smallestGapIndex).low(), ranges.get(smallestGapIndex + 1).high()));%0A            for (int i = smallestGapIndex + 2; i %3C ranges.size(); i++) %7B%0A                list.add(ranges.get(i));%0A            %7D%0A            return new Ranges(list);%0A        %7D else %7B%0A            return this;%0A        %7D%0A    %7D%0A%0A
     public int s

add Ranges.shrink