JAVA & Joda Time API: сравнивайте интервалы, обнаруживайте перекрывающиеся и генерируйте новые интервалы.

Question

Я работаю над проектом, который меня смущает очень плохо.

Учитывая это List<TimeInterval> list, который содержит элементы класса TimeInterval, который выглядит следующим образом:

public class TimeInterval { 
    private static final Instant CONSTANT = new Instant(0); 
    private final LocalDate validFrom; 
    private final LocalDate validTo; 


    public TimeInterval(LocalDate validFrom, LocalDate validTo) { 
     this.validFrom = validFrom; 
     this.validTo = validTo; 
    } 


    public boolean isValid() { 
     try { 
      return toInterval() != null; 
     } 
     catch (IllegalArgumentException e) { 
      return false; 
     } 
    } 


    public boolean overlapsWith(TimeInterval timeInterval) { 
     return this.toInterval().overlaps(timeInterval.toInterval()); 
    } 


    private Interval toInterval() throws IllegalArgumentException { 
     return new Interval(validFrom.toDateTime(CONSTANT), validTo.toDateTime(CONSTANT)); 
    } 

интервалы генерируются с использованием следующих:

TimeInterval tI = new TimeInterval(ld_dateValidFrom, ld_dateValidTo); 

Интервалы внутри списка могут перекрывать друг друга :

|--------------------| 
     |-------------------| 

Это должно быть изменено т в:

|-------||-----------||------| 

Он должен НЕ результат:

|--------|-----------|-------| 

Вообще в цифрах:

I1: 2014-01-01 - 2014-01-30 
I2: 2014-01-07 - 2014-01-15 

Это должно привести к:

I1: 2014-01-01 - 2014-01-06 
I2: 2014-01-07 - 2014-01-15 
I3: 2014-01-16 - 2014-01-30 

Я использую API-интерфейс JODA Time, но поскольку я использую в первый раз, я действительно не знаю, как решить мою проблему. Я уже посмотрел на метод overlap()/overlapWith(), но я до сих пор его не понимаю.

Ваша помощь очень ценится!

UPDATE я нашел что-то похожее на мою проблему >here<, но это не помогает мне сейчас.

---

Я попробовал это снова и снова, и даже если он работал в течение первых интервалов я проверил, это на самом деле не работает так, как я хотел.

Вот интервалы я были даны:

2014-10-20 ---> 2014-10-26 
2014-10-27 ---> 2014-11-02 
2014-11-03 ---> 2014-11-09 
2014-11-10 ---> 2014-11-16 
2014-11-17 ---> 9999-12-31 

Это функция, я использую для создания новых интервалов:

private List<Interval> cleanIntervalList(List<Interval> sourceList) { 
    TreeMap<DateTime, Integer> endPoints = new TreeMap<DateTime, Integer>(); 

    // Fill the treeMap from the TimeInterval list. For each start point, 
    // increment the value in the map, and for each end point, decrement it. 
    for (Interval interval : sourceList) { 
     DateTime start = interval.getStart(); 
     if (endPoints.containsKey(start)) { 
      endPoints.put(start, endPoints.get(start)+1); 
     } 
     else { 
      endPoints.put(start, 1); 
     } 
     DateTime end = interval.getEnd(); 
     if (endPoints.containsKey(end)) { 
      endPoints.put(end, endPoints.get(start)-1); 
     } 
     else { 
      endPoints.put(end, 1); 
     } 
    } 
    System.out.println(endPoints); 

    int curr = 0; 
    DateTime currStart = null; 

    // Iterate over the (sorted) map. Note that the first iteration is used 
    // merely to initialize curr and currStart to meaningful values, as no 
    // interval precedes the first point. 

    List<Interval> targetList = new LinkedList<Interval>(); 

    for (Entry<DateTime, Integer> e : endPoints.entrySet()) { 
     if (curr > 0) { 
      if (e.getKey().equals(endPoints.lastEntry().getKey())){ 
       targetList.add(new Interval(currStart, e.getKey())); 
      } 
      else { 
       targetList.add(new Interval(currStart, e.getKey().minusDays(1))); 
      } 
     } 
     curr += e.getValue(); 
     currStart = e.getKey(); 
    } 
    System.out.println(targetList); 
    return targetList; 
} 

Это то, что выход на самом деле выглядит следующим образом:

2014-10-20 ---> 2014-10-25 
2014-10-26 ---> 2014-10-26 
2014-10-27 ---> 2014-11-01 
2014-11-02 ---> 2014-11-02 
2014-11-03 ---> 2014-11-08 
2014-11-09 ---> 2014-11-09 
2014-11-10 ---> 2014-11-15 
2014-11-16 ---> 2014-11-16 
2014-11-17 ---> 9999-12-31 

И это то, что вывод ДОЛЖЕН выглядеть:

2014-10-20 ---> 2014-10-26 
2014-10-27 ---> 2014-11-02 
2014-11-03 ---> 2014-11-09 
2014-11-10 ---> 2014-11-16 
2014-11-17 ---> 9999-12-31 

Поскольку нет никакого перекрытия в исходных интервалов, я не понимаю, почему он производит такие вещи, как

2014-10-26 ---> 2014-10-26 
2014-11-02 ---> 2014-11-02 
2014-11-09 ---> 2014-11-09 
etc 

Я пытался исправить это в течение всего дня и Я до сих пор не добираюсь туда :(Любая помощь очень ценится!

Answer 1

Предлагаемый алгоритм основан на ответе, который вы уже нашли. Во-первых, вам нужно отсортировать все конечные точки интервалов.

TreeMap<LocalDate,Integer> endPoints = new TreeMap<LocalDate,Integer>(); 

ключей Эта карта - которые рассортированы так как это TreeMap - будут объекты LocalDate в начале и в конце ваших интервалов. Они сопоставляются с числом, которое представляет количество конечных точек на эту дату, вычитаемое из числа начальных точек на эту дату.

Теперь перейдите по списку TimeInterval. Для каждого, для начальной точки, проверьте, находится ли он уже на карте. Если это так, добавьте один в Integer. Если нет, добавьте его на карту со значением 1.

Для конечной точки того же интервала, если она существует на карте, вычтите 1 из целого. Если нет, создайте его со значением -1.

Как только вы закончили заполнение endPoints, создайте новый список для интервалов «разбитых», которые вы создадите.

List<TimeInterval> newList = new ArrayList<TimeInterval>(); 

Теперь начните итерация endPoints. Если в исходном списке был хотя бы один интервал, у вас будет не менее двух очков в endPoints. Вы берете первое и сохраняете ключ (LocalDate) в переменной currStart и связанный с ним Integer в другой переменной (curr или что-то в этом роде).

Петля, начиная со второго элемента до конца. На каждой итерации:

• Если curr > 0, создать новый TimeInterval начиная с currStart и заканчивая текущей датой ключа. Добавьте его в newList.
• Добавьте значение Integer в значение curr.
• Назначить ключ следующим образом: currStart.

И так далее до конца.

Что происходит здесь: заказ дат гарантирует, что у вас нет совпадений. Каждый новый интервал гарантированно не перекрывается с новым, поскольку у них есть эксклюзивные и отсортированные конечные точки. Трюк здесь заключается в том, чтобы найти пробелы на временной шкале, которые не охватываются никакими интервалами. Эти пустые пространства характеризуются тем, что ваш curr равен нулю, так как это означает, что все интервалы, начатые до текущего момента времени, также закончились. Все остальные «пробелы» между конечными точками покрываются хотя бы одним интервалом, поэтому в вашем newList должен быть соответствующий новый интервал.

Настоящая реализация, но, пожалуйста, обратите внимание, что я не использовал Joda Time (у меня ее нет на данный момент, и здесь нет конкретной функции, требующей ее). Я создал свой собственный элементарную TimeInterval класс:

public class TimeInterval { 
    private final Date validFrom; 
    private final Date validTo; 

    public TimeInterval(Date validFrom, Date validTo) { 
     this.validFrom = validFrom; 
     this.validTo = validTo; 
    } 

    public Date getStart() { 
     return validFrom; 
    } 

    public Date getEnd() { 
     return validTo; 
    } 

    @Override 
    public String toString() { 
     return "[" + validFrom + " - " + validTo + "]"; 
    } 
} 

Важно, чтобы добавить методы доступа для начала и конца, чтобы быть в состоянии выполнить алгоритм, как я написал. На самом деле, вы должны, вероятно, использоватьJoda или реализовать их ReadableInterval, если вы хотите использовать их расширенные функции.

Теперь для самого метода. Для этого, чтобы работать с вашими вам придется изменить все Date к LocalDate:

public static List<TimeInterval> breakOverlappingIntervals(List<TimeInterval> sourceList) { 

    TreeMap<Date,Integer> endPoints = new TreeMap<>(); 

    // Fill the treeMap from the TimeInterval list. For each start point, increment 
    // the value in the map, and for each end point, decrement it. 

    for (TimeInterval interval : sourceList) { 
     Date start = interval.getStart(); 
     if (endPoints.containsKey(start)) { 
      endPoints.put(start, endPoints.get(start) + 1); 
     } else { 
      endPoints.put(start, 1); 
     } 
     Date end = interval.getEnd(); 
     if (endPoints.containsKey(end)) { 
      endPoints.put(end, endPoints.get(start) - 1); 
     } else { 
      endPoints.put(end, -1); 
     } 
    } 

    int curr = 0; 
    Date currStart = null; 

    // Iterate over the (sorted) map. Note that the first iteration is used 
    // merely to initialize curr and currStart to meaningful values, as no 
    // interval precedes the first point. 

    List<TimeInterval> targetList = new ArrayList<>(); 
    for (Map.Entry<Date,Integer> e : endPoints.entrySet()) { 
     if (curr > 0) { 
      targetList.add(new TimeInterval(currStart, e.getKey())); 
     } 
     curr += e.getValue(); 
     currStart = e.getKey(); 
    } 
    return targetList; 
} 

(Обратите внимание, что это, вероятно, будет более эффективно использовать изменяемые Integer-подобный объект, а не Integer здесь, но я выбрал ясности).

Answer 2

Я не совсем готов к скорости на Джоде; Мне нужно будет прочитать об этом, если вы хотите решение с перекрытием.

Однако это возможно только с датами. Это в основном псевдокод, но нужно перевести точку. Я также добавил обозначение, чтобы вы могли узнать, как выглядят интервалы. Также есть некоторая путаница для меня относительно того, следует ли добавлять 1 или вычитать 1 для перекрытия, поэтому я ошибся на стороне осторожности, указав наружу из перекрытия (-1 для начала, +1 для конца).

TimeInterval a, b; //a and b are our two starting intervals 
TimeInterval c = null;; //in case we have a third interval 

if(a.start > b.start) { //move the earliest interval to a, latest to b, if necessary 
    c = a; 
    a = b; 
    b = c; 
    c = null; 
} 

if(b.start > a.start && b.start < a.end) { //case where b starts in the a interval 
    if(b.end > a.end) { //b ends after a |AA||AB||BB| 
     c = new TimeInterval(a.end + 1, b.end);//we need time interval c 
     b.end = a.end; 
     a.end = b.start - 1; 
    } 
    else if (b.end < a.end) { //b ends before a |AA||AB||AA| 
     c = new TimeInterval(b.end + 1, a.end);//we need time interval c 
     a.end = b.start - 1; 
    } 
    else { //b and a end at the same time, we don't need c |AA||AB| 
     c = null; 
     a.end = b.start - 1; 
    } 
} 
else if(a.start == b.start) { //case where b starts same time as a 
    if(b.end > a.end) { //b ends after a |AB||B| 
     b.start = a.end + 1; 
     a.end = a.end; 
    } 
    else if(b.end < a.end) { //b ends before a |AB||A| 
     b.start = b.end + 1; 
     b.end = a.end; 
     a.end = b.start; 
    } 
    else { //b and a are the same |AB| 
     b = null; 
    } 
} 
else { 
    //no overlap 
} 

Answer 3

Полуоткрытый

Предлагаю вам пересмотреть условия своей цели. Joda-Time мудро использует подход «Half-Open» для определения промежутка времени. Начало включительно в то время как окончание эксклюзивный. Например, неделя начинается с начала первого дня и заканчивается, , но не включая, первый момент следующей недели. Полуоткрытие оказывается весьма полезным и естественным способом обработки промежутков времени, как обсуждается в других ответах.

Используя этот полуоткрытый подход к вашему примеру, вы действительно хотите этот результат:

|--------|-----------|-------| 

I1: 2014-01-01 - 2014-01-07 
I2: 2014-01-07 - 2014-01-16 
I3: 2014-01-16 - 2014-01-30 

Поиск StackOverflow для «полуоткрытый», чтобы найти обсуждение и примеры, такие как this answer мой.

Интервал времени Joda

Joda время имеет отличную Interval класса для представления промежуток времени, определенного парой конечных точек на временной шкале. Этот класс интервалов предлагает overlap, overlaps (sic), abuts и gap методов. Обратите внимание, в частности, на метод overlap, который генерирует новый интервал при сравнении двух других; это может быть ключом к вашему решению.

Но, к сожалению, этот класс работает только с объектами DateTime, а не LocalDate (только по дате, без времени суток или по часовому поясу). Возможно, отсутствие поддержки LocalDate - это то, почему вы или ваша команда придумали этот класс TimeInterval. Но я предлагаю скорее использовать этот пользовательский класс, рассмотрев возможность использования объектов DateTime с классами Joda-Time. Я не уверен на 100%, что лучше, чем переносить свой собственный класс интервалов только для даты (я был соблазн сделать это), но моя кишка говорит мне об этом.

Чтобы настроить фокус на дни, а не на день + время, на ваших объектах DateTime вызовите метод withTimeAtStartOfDay, чтобы отрегулировать временную часть до первого момента дня. Этот первый момент обычно 00:00:00.000, но не обязательно из-за летнего времени (DST) и, возможно, других аномалий. Просто будьте осторожны и согласуетесь с часовым поясом; возможно, использовать UTC повсюду.

Вот пример кода в Joda-Time 2.5 с использованием значений, предложенных в Вопросе. В этих конкретных строках вызов withTimeAtStartOfDay может быть ненужным, поскольку по умолчанию Joda-Time устанавливается в первый момент дня, когда не предоставляется ни один день. Но я предлагаю использовать эти звонки на withTimeAtStartOfDay, так как он делает ваш код самодокументированным в отношении ваших намерений. И это делает все ваше дневное использование кода DateTime согласованным.

Interval i1 = new Interval(new DateTime("2014-01-01", DateTimeZone.UTC).withTimeAtStartOfDay(), new DateTime("2014-01-30", DateTimeZone.UTC).withTimeAtStartOfDay()); 
Interval i2 = new Interval(new DateTime("2014-01-07", DateTimeZone.UTC).withTimeAtStartOfDay(), new DateTime("2014-01-15", DateTimeZone.UTC).withTimeAtStartOfDay()); 

Оттуда примените логику, предложенную в других ответах.