Linq query to merge overlapping elements

Question

I have this class representing a period of time:

 public class Period
 {
 public Period(DateTime dateFrom)
 {
 DateFrom = dateFrom;
 }
 public Period(DateTime dateFrom, DateTime? dateTo)
 {
 DateFrom = dateFrom;
 DateTo = dateTo;
 }
 public DateTime DateFrom { get; set; }
 public DateTime? DateTo { get; set; }
 public bool IsOverlapping(Period other)
 {
 if (!DateTo.HasValue)
 {
 return DateFrom <= other.DateTo.Value;
 }
 if (!other.DateTo.HasValue)
 {
 return other.DateFrom <= DateTo.Value;
 }
 return DateFrom <= other.DateTo.Value && other.DateFrom <= DateTo.Value;
 }
 public bool IsFinite => DateTo.HasValue;
 public bool IsInfinite => !IsFinite;
 protected bool Equals(Period other)
 {
 return DateFrom.Equals(other.DateFrom) && Nullable.Equals(DateTo, other.DateTo);
 }
 public override bool Equals(object obj)
 {
 if (ReferenceEquals(null, obj)) return false;
 if (ReferenceEquals(this, obj)) return true;
 if (obj.GetType() != this.GetType()) return false;
 return Equals((Period) obj);
 }
 public override int GetHashCode()
 {
 return HashCode.Combine(DateFrom, DateTo);
 }
 }

Now a have a list of periods and for each of them I have to perform an network call so to minimize them I decide to merge all overlapping periods.

So a list like that :

• 2020年01月01日 -> 2020年01月10日
• 2020年02月05日 -> 2020年02月10日
• 2020年02月07日 -> 2020年02月15日
• 2020年02月13日 -> 2020年02月20日
• 2020年03月01日 -> 2020年03月10日
• 2020年03月25日 -> 2020年03月31日
• 2020年03月30日 ->

Should become :

• 2020年01月01日 -> 2020年01月10日
• 2020年02月05日 -> 2020年02月20日
• 2020年03月01日 -> 2020年03月10日
• 2020年03月25日 ->

I tried this code

 public static IEnumerable<Period> Implementation(IEnumerable<Period> periods)
 {
 return periods.OrderBy(p => p.DateFrom)
 .Aggregate(new List<Period>(), (ps, p) =>
 {
 if (!ps.Any())
 {
 ps.Add(p);
 return ps;
 }
 var last = ps.Last();
 if (last.IsOverlapping(p))
 {
 if (last.IsInfinite || p.IsInfinite)
 {
 ps[ps.Count() - 1] = new Period(DateTimeHelpers.Min(last.DateFrom, p.DateFrom), null);
 }
 else
 {
 ps[ps.Count() - 1] = new Period(DateTimeHelpers.Min(last.DateFrom, p.DateFrom),
 DateTimeHelpers.Max(last.DateTo.Value, p.DateTo.Value));
 }
 return ps;
 }
 ps.Add(p);
 return ps;
 });
 }

Here is the DateTimeHelpers I'm using :

public class DateTimeHelpers
{
 public static DateTime Max(DateTime first, DateTime second)
 {
 return first <= second
 ? second
 : first;
 }
 public static DateTime Min(DateTime first, DateTime second)
 {
 return first >= second
 ? second
 : first;
 }
}

It's working properly but I'm not satisfied with it so I wonder if there is a more performant/elegant/readable way to do it ?

I'm not talking about just refactoring to extract some methods but a fundamentally different solution, it's possible I missed a useful LINQ operator.

Here is my test if you want to reproduce it (MsTest + FluentAssertions). The period are not in the right order to ensure it will be take care of by the method itself:

 // Arrange
 var periods = new List<Period>()
 {
 new Period(new DateTime(2020, 2, 13), new DateTime(2020, 2, 20)),
 new Period(new DateTime(2020, 3, 1), new DateTime(2020, 3, 10)),
 new Period(new DateTime(2020, 3, 25), new DateTime(2020, 3, 31)),
 new Period(new DateTime(2020, 3, 30)),
 new Period(new DateTime(2020, 1, 1), new DateTime(2020, 1, 10)),
 new Period(new DateTime(2020, 2, 5), new DateTime(2020, 2, 10)),
 new Period(new DateTime(2020, 2, 7), new DateTime(2020, 2, 15))
 };
 // Act
 var mergedPeriods = Implementation(periods);
 // Assert
 mergedPeriods.Should().HaveCount(4);
 mergedPeriods[0].Should().Be(new Period(new DateTime(2020, 1, 1), new DateTime(2020, 1, 10)));
 mergedPeriods[1].Should().Be(new Period(new DateTime(2020, 2, 5), new DateTime(2020, 2, 20)));
 mergedPeriods[2].Should().Be(new Period(new DateTime(2020, 3, 1), new DateTime(2020, 3, 10)));
 mergedPeriods[3].Should().Be(new Period(new DateTime(2020, 3, 25)));

• Jesse C. Slicer: I voted to close as the Period class, as presented, doesn't compile and therefore can't be reviewed.
• Arcord: Well... For this example I made the DateFrom not nullable and I forgot to remove the ".Value" in the code. It's maybe a bit excessive to say the code can't be reviewed... I will update it to also provide the Equals/GetHashCode I guess...
• Jesse C. Slicer: I will remove my close vote now that it has been updated to work.
• Peter Csala: Your Aggreate still does not compile: DateFrom does not have Value. Please also indicate which DateTimeHelpers nuget package are you using.
• Arcord: I remove the .Value (...) and add my helpers implementation.

Answer 1

Here are my observations:

Period

• public Period(DateTime dateFrom): Do not repeat yourself. Just call the other ctor:

public Period(DateTime dateFrom) 
 : this(dateFrom, null)
{ }

• public DateTime DateFrom { get; set; }: Because you have a ctor, where you specify its value that's why you don't need public setter:

public DateTime DateFrom { get; }
public DateTime? DateTo { get; }

• return DateFrom <= other.DateTo.Value;: other.DateTo can be null, so this could result an InvalidOperationException. Include null check as well:

if (!DateTo.HasValue)
{
 return other.DateTo != null && DateFrom <= other.DateTo.Value;
}

• IsFinite: It is used only by the IsInfinite, so you could merge them:

public bool IsInfinite => !DateTo.HasValue;

• Equals and GetHashCode: The default ones are good, you don't need to override them.

So, the Period class after refactor:

public class Period
{
 public Period(DateTime dateFrom)
 : this(dateFrom, null)
 { }
 public Period(DateTime dateFrom, DateTime? dateTo)
 {
 DateFrom = dateFrom;
 DateTo = dateTo;
 }
 public DateTime DateFrom { get; }
 public DateTime? DateTo { get; }
 public bool IsOverlapping(Period other)
 {
 if (!DateTo.HasValue)
 {
 return other.DateTo != null && DateFrom <= other.DateTo.Value;
 }
 if (!other.DateTo.HasValue)
 {
 return other.DateFrom <= DateTo.Value;
 }
 return DateFrom <= other.DateTo.Value && other.DateFrom <= DateTo.Value;
 }
 public bool IsInfinite => !DateTo.HasValue;
}

---

DateTimeHelpers

• Min: I think the GetEarlier name would be more expressive. Also you can easily modify it to become an extension method:

public static DateTime GetEarlier(this DateTime first, DateTime second)
 => first >= second ? second : first;

• Max It is used against DateTo properties. So, I would suggest to rename it to GetLater and use DateTime? instead of DateTime:

public static DateTime? GetLater(this DateTime? first, DateTime? second)
 => first <= second ? second : first;

• Implementation: This name is way too generic. I would suggest to change it to be an extension method and name it like Merge or Consolidate or whatver:

public static IReadOnlyCollection<Period> Merge(this IEnumerable<Period> periods)
{
}

• When they are not overlapping: I would suggest to handle that case right after the empty collection case. With this approach you have to early exits inside the Aggregator

periods
 .OrderBy(period => period.DateFrom)
 .Aggregate(new List<Period>(),
 (mergedPeriods, period) =>
 {
 if (!mergedPeriods.Any())
 {
 mergedPeriods.Add(period);
 return mergedPeriods;
 }
 var latest = mergedPeriods.Last();
 if (!latest.IsOverlapping(period))
 {
 mergedPeriods.Add(period);
 return mergedPeriods;
 }
 
 //When overlapping
 });

• When they are overlapping: Here you have several repeated commands The repetition can be refactored like this:

DateTime from = latest.DateFrom.GetEarlier(period.DateFrom);
DateTime? to = null;
if (!latest.IsInfinite && !period.IsInfinite)
{
 to = latest.DateTo.GetLater(period.DateTo);
}
mergedPeriods[^1] = new Period(from, to);
return mergedPeriods;

• Instead of calculating the from in both cases here we calculate only once
• Instead of accessing the last element in both cases here we access it only once
  • We use here C# 8's new syntax: [^1]
• Instead of calling the ctor in both cases here we call it only once
• Instead of having two branches now can handle the special case with a single branch

So, the Helper class after refactor:

public static class Helpers
{
 public static DateTime GetEarlier(this DateTime first, DateTime second)
 => first >= second ? second : first;
 public static DateTime? GetLater(this DateTime? first, DateTime? second)
 => first <= second ? second : first;
 public static IReadOnlyCollection<Period> Merge(this IEnumerable<Period> periods)
 => periods
 .OrderBy(period => period.DateFrom)
 .Aggregate(new List<Period>(),
 (mergedPeriods, period) =>
 {
 if (!mergedPeriods.Any())
 {
 mergedPeriods.Add(period);
 return mergedPeriods;
 }
 var latest = mergedPeriods.Last();
 if (!latest.IsOverlapping(period))
 {
 mergedPeriods.Add(period);
 return mergedPeriods;
 }
 DateTime from = latest.DateFrom.GetEarlier(period.DateFrom);
 DateTime? to = null;
 if (!latest.IsInfinite && !period.IsInfinite)
 {
 to = latest.DateTo.GetLater(period.DateTo);
 }
 mergedPeriods[^1] = new Period(from, to);
 return mergedPeriods;
 });
}

---

Usage is this simple

foreach (var period in periods.Merge())
{
 Console.WriteLine($"{period.DateFrom:M} => {period.DateTo:M}");
}

• Arcord: I missed your answer. I was more looking into a different type of algorithm for the "merge" method but your remarks are relevant :-)