Вставить или удалить в коллекцию непрерывных интервалов без перекрытия

Question

Учитывая набор отсортированных непересекающихся непрерывных интервалов, как добавить новый интервал или удалить существующий интервал из него. Пожалуйста, предложите мне хорошую структуру данных для хранения этих интервалов, которые могут сделать эти изменения возможными.

Пример:

Given collection: [1,4), [4,9), [9,12)

Insert: [5,8)
Result: [1,4), [4,5), [5, 8), [8, 9), [9, 12)

Delete: [4, 5)
Result: [1,5),  [5, 8), [8, 9), [9, 12)

В случае удаления следует добавить к предыдущему первый, если возможно, в противном случае следующий (ые).

Answer 1

Я бы просто не стал беспокоиться о дискретных интервалах. Поскольку определение требует «отсортированных непересекающихся непрерывных интервалов», я сохраню только границы интервалов («intervalBoundaries»), и из этого списка я создам интервалы по требованию («getRanges()») ,

Вот мой пример (возможно, метод "deleteRange()" должен быть пересмотрен, чтобы охватить крайние случаи):

/*
 */
package de.test.stackoverflow;

import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import org.apache.commons.lang.StringUtils;

public class Intervals {

    public static final class Range {

        final int from;
        final int to;

        public Range(int from, int to) {
            this.from = from;
            this.to = to;
        }

        public int getFrom() {
            return from;
        }

        public int getTo() {
            return to;
        }

        @Override
        public String toString() {
            return String.format("[%d, %d)", from, to);
        }

    }

    final SortedSet<Integer> intervalBoundaries = new java.util.TreeSet<>();

    public List<Range> getRanges() {
        final List<Range> res = new java.util.ArrayList<>();
        if (intervalBoundaries.size() > 1) {
            final List<Integer> tmpBounds = new java.util.ArrayList<>(intervalBoundaries);
            for (int i = 0; i < tmpBounds.size() - 1; i++) {
                res.add(new Range(tmpBounds.get(i), tmpBounds.get(i + 1)));
            }
        }
        return res;
    }

    public void insertBoundary(Integer bound) {
        // duplicates in sets are automatically removed
        intervalBoundaries.add(bound);
    }

    public void insertRange(Integer from, Integer to) {
        intervalBoundaries.add(from);
        intervalBoundaries.add(to);

    }

    public void insertRange(Range x) {
        insertRange(x.getFrom(), x.getTo());
    }

    public void deleteRange(Range x) {
        final Collection<Integer> boundsToDelete = new java.util.LinkedHashSet<>();
        for (Integer intervalBoundary : intervalBoundaries) {
            if (intervalBoundary >= x.getFrom() && intervalBoundary < x.getTo()) {
                boundsToDelete.add(intervalBoundary);
            }
        }
        intervalBoundaries.removeAll(boundsToDelete);
        if (x.getTo() < intervalBoundaries.last()) {
            insertBoundary(x.getTo());
        }
        if (x.getFrom() > intervalBoundaries.last()) {
            insertBoundary(x.getFrom());
        }
    }    

    public static void main(String[] args) {
        Intervals i = new Intervals();
        i.insertRange(new Range(1, 4));
        i.insertRange(new Range(4, 9));
        i.insertRange(new Range(9, 12));
        System.out.println("Given collection: " + StringUtils.join(i.getRanges(), ", "));
        final Range insertRange = new Range(5, 8);
        System.out.println("insert: " + insertRange);
        i.insertRange(insertRange);
        System.out.println("Result: " + StringUtils.join(i.getRanges(), ", "));
        final Range deleteRange = new Range(4, 5);
        System.out.println("delete: " + deleteRange);
        i.deleteRange(deleteRange);
        System.out.println("Result: " + StringUtils.join(i.getRanges(), ", "));
        final Range deleteRange2 = new Range(3, 9);
        System.out.println("delete: " + deleteRange2);
        i.deleteRange(deleteRange2);
        System.out.println("Result: " + StringUtils.join(i.getRanges(), ", "));
        final Range deleteRange3 = new Range(2, 15);
        System.out.println("delete: " + deleteRange3);
        i.deleteRange(deleteRange3);
        System.out.println("Result: " + StringUtils.join(i.getRanges(), ", "));

    }

}