Find Gap Date Ranges from two Set of Date Ranges C#

Question

I have Base date Ranges and Test Date Range. I need to get GAP between base and test meaning Missing Date Ranges that are in Base but not in Test. what would be the best way to do this?

Base Date Ranges
1/1/2012    1/10/2012
1/11/2012   1/25/2012


Test Date Ranges
1/2/2012    1/7/2012
1/8/2012    1/9/2012
1/15/2012   1/30/2012

Output:

Missing Date Ranges that are in Base but not in Test 
1/1/2012    1/2/2012
1/7/2012    1/8/2012
1/9/2012    1/10/2012
1/11/2012   1/15/2012

Tried this so far

   static void Main(string[] args)
    {


        List<DateRanges> aDateRanges = new List<DateRanges>();
        List<DateRanges> bDateRanges = new List<DateRanges>();

        aDateRanges.Add(new DateRanges(new DateTime(2012, 1, 1), new DateTime(2012, 1, 10)));
        aDateRanges.Add(new DateRanges(new DateTime(2012, 1, 11), new DateTime(2012, 1, 25)));


        bDateRanges.Add(new DateRanges(new DateTime(2012, 1, 2), new DateTime(2012, 1, 7)));
        bDateRanges.Add(new DateRanges(new DateTime(2012, 1, 8), new DateTime(2012, 1, 9)));
        bDateRanges.Add(new DateRanges(new DateTime(2012, 1, 15), new DateTime(2012, 1, 30)));

        DisplayDateRanges(GetGaps(aDateRanges, bDateRanges, 0), "Final Gap Fill");
        Console.WriteLine("Completed");
        Console.Read();
    }

    public class DateRanges
    {
        public DateTime StartDate { get; set; }
        public DateTime EndDate { get; set; }
        public DateRanges(DateTime Start, DateTime End)
        {
            StartDate = Start;
            EndDate = End;
        }
    }

    public static void DisplayDateRanges(List<DateRanges> dateRanges, string title)
    {
        Console.WriteLine("************************{0}****************************", title);
        Console.WriteLine(Environment.NewLine + "New Recursion");
        foreach (DateRanges br in dateRanges)
        {
            Console.WriteLine("Start Date {0}   End Date {1}", br.StartDate, br.EndDate);
        }

    }

    public static List<DateRanges> GetGaps(List<DateRanges> aDateRanges, List<DateRanges> bDateRanges, int recursionlevel)
    {
        List<DateRanges> gapFill = new List<DateRanges>();
        List<DateRanges> gapFillTemp = new List<DateRanges>();
        List<DateRanges> bDateRangesTemp = new List<DateRanges>(bDateRanges);
        Console.WriteLine(Environment.NewLine + "+++++++++++++++++++++++++++++++++++++++++Recursion Level Id {0} +++++++++++++++++++++++++++++++++++++++++", recursionlevel);
        DisplayDateRanges(aDateRanges, " A Date Ranges ");
        DisplayDateRanges(bDateRanges, " B Date Ranges ");

        foreach (DateRanges br in bDateRanges)
        {
            if (br.StartDate == br.EndDate)
                return gapFill;
            foreach (DateRanges ar in aDateRanges)
            {
                if (ar.StartDate == ar.EndDate)
                    return gapFill;
                if (br.StartDate == ar.StartDate && br.EndDate == ar.EndDate)
                    continue;
                else if (br.StartDate >= ar.StartDate && br.EndDate <= ar.EndDate)
                {
                    gapFillTemp.AddRange(GetGaps(new List<DateRanges> { new DateRanges(ar.StartDate, br.StartDate) }, bDateRangesTemp, recursionlevel + 1));
                    if (gapFillTemp.Count == 0)
                    {
                        //gapFillTemp.Add(new DateRanges(ar.StartDate, br.StartDate));
                    }
                    bDateRangesTemp.AddRange(gapFillTemp);
                    gapFill.AddRange(gapFillTemp);
                    gapFillTemp.Clear();

                    gapFillTemp.AddRange(GetGaps(new List<DateRanges> { new DateRanges(br.EndDate, ar.EndDate) }, bDateRangesTemp, recursionlevel + 1));
                    if (gapFillTemp.Count == 0)
                    {
                       // gapFillTemp.Add(new DateRanges(br.EndDate, ar.EndDate));
                    }
                    bDateRangesTemp.AddRange(gapFillTemp);
                    gapFill.AddRange(gapFillTemp);
                    gapFillTemp.Clear();
                }
                else if (br.StartDate < ar.EndDate && br.EndDate >= ar.EndDate)
                {
                    gapFillTemp.AddRange(GetGaps(new List<DateRanges> { new DateRanges(ar.StartDate, br.StartDate) }, bDateRangesTemp, recursionlevel + 1));
                    if (gapFillTemp.Count == 0)
                    {
                        //gapFillTemp.Add(new DateRanges(ar.StartDate, br.StartDate));
                    }
                    bDateRangesTemp.AddRange(gapFillTemp);
                    gapFill.AddRange(gapFillTemp);
                    gapFillTemp.Clear();
                }

                else if (ar.StartDate >= br.StartDate && ar.StartDate < br.EndDate)
                {
                    gapFillTemp.AddRange(GetGaps(new List<DateRanges> { new DateRanges(br.EndDate, ar.EndDate) }, bDateRangesTemp, recursionlevel + 1));
                    if (gapFillTemp.Count == 0)
                    {
                       // gapFillTemp.Add(new DateRanges(br.EndDate, ar.EndDate));
                    }
                    bDateRangesTemp.AddRange(gapFillTemp);
                    gapFill.AddRange(gapFillTemp);
                    gapFillTemp.Clear();
                }

                else if (ar.StartDate >= br.StartDate && ar.EndDate <= br.EndDate)
                {
                    //     AS----AE
                    //  BS----------BE           
                    //Do Nothing

                }
                else
                {
                    if (AllowedToAdd(bDateRangesTemp, new DateRanges(ar.StartDate, ar.EndDate)))
                    {
                        bDateRangesTemp.Add(new DateRanges(ar.StartDate, ar.EndDate));
                        gapFill.Add(new DateRanges(ar.StartDate, ar.EndDate));
                    }
                }

            }



        }
        return gapFill;
    }


    static bool AllowedToAdd(List<DateRanges> bDateRanges, DateRanges newItem)
    {
        return !bDateRanges.Any(m =>
            (m.StartDate < newItem.StartDate &&
             newItem.StartDate < (m.EndDate))
            ||
            (m.StartDate < (newItem.EndDate) &&
             (newItem.EndDate) <= (m.EndDate))
            ||
            (newItem.StartDate < m.StartDate &&
             m.StartDate < (newItem.EndDate))
            ||
            (newItem.StartDate < (m.EndDate) &&
             (m.EndDate) <= (newItem.EndDate))
            );
    }

Answer 1

The following code satisfies the given constraints of the problem:

Unit Test

    static void Main(string[] args)
    {
        IEnumerable<DateRange> _base = new[] { new DateRange() { Start = DateTime.Parse("1/1/2012"), End = DateTime.Parse("1/10/2012")},
                                               new DateRange() { Start = DateTime.Parse("1/11/2012"), End = DateTime.Parse("1/25/2012")} };

        IEnumerable<DateRange> _test = new[] { new DateRange() { Start = DateTime.Parse("1/2/2012"), End = DateTime.Parse("1/7/2012")},
                                               new DateRange() { Start = DateTime.Parse("1/8/2012"), End = DateTime.Parse("1/9/2012")},
                                               new DateRange() { Start = DateTime.Parse("1/15/2012"), End = DateTime.Parse("1/30/2012")} };

        IEnumerable<DateRange> _theoreticalGaps = new[] { new DateRange() { Start = DateTime.Parse("1/1/2012"), End = DateTime.Parse("1/2/2012")},
                                               new DateRange() { Start = DateTime.Parse("1/7/2012"), End = DateTime.Parse("1/8/2012")},
                                               new DateRange() { Start = DateTime.Parse("1/9/2012"), End = DateTime.Parse("1/10/2012")},
                                               new DateRange() { Start = DateTime.Parse("1/11/2012"), End = DateTime.Parse("1/15/2012")} };


        var gapsInTestNotInBase = FindGaps(_base, _test);

        Debug.Assert(Enumerable.SequenceEqual(_theoreticalGaps, gapsInTestNotInBase));
    }

FindGaps Method

    public static IEnumerable<DateRange> FindGaps(IEnumerable<DateRange> baseCollection, IEnumerable<DateRange> testCollection)
    {
        var allBaseDates = baseCollection.SelectMany(o => o.GetDiscreetDates())
            .Distinct()
            .OrderBy(o => o.Ticks);

        var missingInTest = (from d in allBaseDates
                             let inRange = testCollection.Any(o => d.IsInRange(o))
                             where !inRange
                             select d).ToArray();

        var gaps = missingInTest.Select(o => new DateRange() { Start = o, End = o.AddDays(1) });

        gaps = gaps.GroupConsecutive();

        return gaps;

    }

DateRange Class

public class DateRange
{
    protected bool Equals(DateRange other)
    {
        return Start.Equals(other.Start) && End.Equals(other.End);
    }

    public override int GetHashCode()
    {
        unchecked
        {
            return (Start.GetHashCode()*397) ^ End.GetHashCode();
        }
    }

    public DateTime Start { get; set; }
    public DateTime End { get; set; }

    public IEnumerable<DateTime> GetDiscreetDates()
    {
        //Start is not allowed to equal end.
        if (Start.Date == End.Date)
            throw new ArgumentException("Start cannot equal end.");

        var output = new List<DateTime>();

        var current = Start.Date;

        while (current < End.Date) {
            output.Add(current);
            current = current.AddDays(1);
        }

        return output;
    }

    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((DateRange) obj);
    }
}

Extension Methods

public static class Extensions
{
    public static bool IsInRange(this DateTime testDate, DateRange range)
    {
        return range.Start <= testDate && range.End > testDate;
    }

    public static IEnumerable<DateRange> GroupConsecutive(this IEnumerable<DateRange> input)
    {
        var current = input.ToArray();
        var nextIndex = 0;

        //uses lookahead to figure out if gaps are consecutive.
        for (int i = 0; i < current.Length - 1; i++) {

            //If the next range is consecutive to the current, skip;
            if (!current[i].End.IsInRange(current[i + 1])) {
                yield return new DateRange()
                               {
                                   Start = current[nextIndex].Start,
                                   End = current[i].End
                               };
                nextIndex = i + 1;
            }
        }

        //If the last elements were consecutive, pull out the final item.
        if (nextIndex != current.Length) {
            yield return new DateRange()
            {
                Start = current[nextIndex].Start,
                End = current[current.Length - 1].End
            };
        }
    }
}

Answer 2

You can use the Time Period Library for .NET to calculate the gaps:

// ----------------------------------------------------------------------
public void GapFinder()
{
  // base periods
  TimePeriodCollection basePeriods = new TimePeriodCollection();
  basePeriods.Add( new TimeRange( new DateTime( 2012, 1, 1 ), new DateTime( 2012, 1, 10 ) ) );
  basePeriods.Add( new TimeRange( new DateTime( 2012, 1, 11 ), new DateTime( 2012, 1, 25 ) ) );
  ITimePeriodCollection combinedBasePeriods = new TimePeriodCombiner<TimeRange>().CombinePeriods( basePeriods );

  // test periods
  TimePeriodCollection testPeriods = new TimePeriodCollection();
  testPeriods.Add( new TimeRange( new DateTime( 2012, 1, 2 ), new DateTime( 2012, 1, 7 ) ) );
  testPeriods.Add( new TimeRange( new DateTime( 2012, 1, 8 ), new DateTime( 2012, 1, 9 ) ) );
  testPeriods.Add( new TimeRange( new DateTime( 2012, 1, 15 ), new DateTime( 2012, 1, 30 ) ) );
  ITimePeriodCollection combinedTestPeriods = new TimePeriodCombiner<TimeRange>().CombinePeriods( testPeriods );

  // gaps
  TimePeriodCollection gaps = new TimePeriodCollection();
  foreach ( ITimePeriod basePeriod in combinedBasePeriods )
  {
    gaps.AddAll( new TimeGapCalculator<TimeRange>().GetGaps( combinedTestPeriods, basePeriod ) );
  }
  foreach ( ITimePeriod gap in gaps )
  {
    Console.WriteLine( "Gap: " + gap );
  }
} // GapFinder

Answer 3

this worked too

static void Main(string[] args) {

    List<DateRanges> aDateRanges = new List<DateRanges>();
    List<DateRanges> bDateRanges = new List<DateRanges>();

    aDateRanges.Add(new DateRanges(new DateTime(2012, 1, 1), new DateTime(2012, 1, 10)));
    aDateRanges.Add(new DateRanges(new DateTime(2012, 1, 11), new DateTime(2012, 1, 25)));


    bDateRanges.Add(new DateRanges(new DateTime(2012, 1, 2), new DateTime(2012, 1, 7)));
    bDateRanges.Add(new DateRanges(new DateTime(2012, 1, 8), new DateTime(2012, 1, 9)));
    bDateRanges.Add(new DateRanges(new DateTime(2012, 1, 15), new DateTime(2012, 1, 30)));

    DisplayDateRanges(GetGaps(aDateRanges, bDateRanges, 0), "Final Gap Fill");
    Console.WriteLine("Completed");
    Console.Read();
}

public class DateRanges
{
    public DateTime StartDate { get; set; }
    public DateTime EndDate { get; set; }
    public DateRanges(DateTime Start, DateTime End)
    {
        StartDate = Start;
        EndDate = End;
    }
}

public static void DisplayDateRanges(List<DateRanges> dateRanges, string title)
{
    Console.WriteLine("************************{0}****************************", title);
    Console.WriteLine(Environment.NewLine + "New Recursion");
    foreach (DateRanges br in dateRanges)
    {
        Console.WriteLine("Start Date {0}   End Date {1}", br.StartDate, br.EndDate);
    }

}

public static List<DateRanges> GetGaps(List<DateRanges> aDateRanges, List<DateRanges> bDateRanges, int recursionlevel)
{
    List<DateRanges> gapFill = new List<DateRanges>();
    List<DateRanges> gapFillTemp = new List<DateRanges>();
    List<DateRanges> bDateRangesTemp = new List<DateRanges>(bDateRanges);
    Console.WriteLine(Environment.NewLine + "+++++++++++++++++++++++++++++++++++++++++Recursion Level Id {0} +++++++++++++++++++++++++++++++++++++++++", recursionlevel);
    DisplayDateRanges(aDateRanges, " A Date Ranges ");
    DisplayDateRanges(bDateRanges, " B Date Ranges ");

    foreach (DateRanges br in bDateRanges)
    {
        if (br.StartDate == br.EndDate)
            return gapFill;
        foreach (DateRanges ar in aDateRanges)
        {
            if (ar.StartDate == ar.EndDate)
                return gapFill;
            if (br.StartDate == ar.StartDate && br.EndDate == ar.EndDate)
                continue;
            else if (br.StartDate >= ar.StartDate && br.EndDate <= ar.EndDate)
            {
                gapFillTemp.AddRange(GetGaps(new List<DateRanges> { new DateRanges(ar.StartDate, br.StartDate) }, bDateRangesTemp, recursionlevel + 1));
                if (gapFillTemp.Count == 0)
                {
                    //gapFillTemp.Add(new DateRanges(ar.StartDate, br.StartDate));
                }
                bDateRangesTemp.AddRange(gapFillTemp);
                gapFill.AddRange(gapFillTemp);
                gapFillTemp.Clear();

                gapFillTemp.AddRange(GetGaps(new List<DateRanges> { new DateRanges(br.EndDate, ar.EndDate) }, bDateRangesTemp, recursionlevel + 1));
                if (gapFillTemp.Count == 0)
                {
                   // gapFillTemp.Add(new DateRanges(br.EndDate, ar.EndDate));
                }
                bDateRangesTemp.AddRange(gapFillTemp);
                gapFill.AddRange(gapFillTemp);
                gapFillTemp.Clear();
            }
            else if (br.StartDate < ar.EndDate && br.EndDate >= ar.EndDate)
            {
                gapFillTemp.AddRange(GetGaps(new List<DateRanges> { new DateRanges(ar.StartDate, br.StartDate) }, bDateRangesTemp, recursionlevel + 1));
                if (gapFillTemp.Count == 0)
                {
                    //gapFillTemp.Add(new DateRanges(ar.StartDate, br.StartDate));
                }
                bDateRangesTemp.AddRange(gapFillTemp);
                gapFill.AddRange(gapFillTemp);
                gapFillTemp.Clear();
            }

            else if (ar.StartDate >= br.StartDate && ar.StartDate < br.EndDate)
            {
                gapFillTemp.AddRange(GetGaps(new List<DateRanges> { new DateRanges(br.EndDate, ar.EndDate) }, bDateRangesTemp, recursionlevel + 1));
                if (gapFillTemp.Count == 0)
                {
                   // gapFillTemp.Add(new DateRanges(br.EndDate, ar.EndDate));
                }
                bDateRangesTemp.AddRange(gapFillTemp);
                gapFill.AddRange(gapFillTemp);
                gapFillTemp.Clear();
            }

            else if (ar.StartDate >= br.StartDate && ar.EndDate <= br.EndDate)
            {
                //     AS----AE
                //  BS----------BE           
                //Do Nothing

            }
            else
            {
                if (AllowedToAdd(bDateRangesTemp, new DateRanges(ar.StartDate, ar.EndDate)))
                {
                    bDateRangesTemp.Add(new DateRanges(ar.StartDate, ar.EndDate));
                    gapFill.Add(new DateRanges(ar.StartDate, ar.EndDate));
                }
            }

        }



    }
    return gapFill;
}


static bool AllowedToAdd(List<DateRanges> bDateRanges, DateRanges newItem)
{
    return !bDateRanges.Any(m =>
        (m.StartDate < newItem.StartDate &&
         newItem.StartDate < (m.EndDate))
        ||
        (m.StartDate < (newItem.EndDate) &&
         (newItem.EndDate) <= (m.EndDate))
        ||
        (newItem.StartDate < m.StartDate &&
         m.StartDate < (newItem.EndDate))
        ||
        (newItem.StartDate < (m.EndDate) &&
         (m.EndDate) <= (newItem.EndDate))
        );
}

Answer 4

Extension methods

public static class DateRangeEnumerable
{
    public static IEnumerable<DateTime> GetDates(this IEnumerable<DateRange> source)
    {
        var sortedSource = source.OrderBy(r => r.From);

        foreach (var range in sortedSource)
        {
            var d = range.From;
            while (d < range.To)
            {
                yield return d;
                d = d.AddDays(1);
            }
        }
    }

    public static IEnumerable<DateRange> GetRanges(this IEnumerable<DateTime> source)
    {
        var sortedSource = source.OrderBy(d => d);
        var enumerator = sortedSource.GetEnumerator();

        if (!enumerator.MoveNext())
            yield break;

        DateTime from = enumerator.Current;
        DateTime prev = from;

        while (true)
        {
            while (true)
            {
                if (enumerator.MoveNext())
                {
                    if (enumerator.Current == prev.AddDays(1))
                        prev = enumerator.Current;
                    else
                        break;
                }
                else
                {
                    yield return new DateRange() { From = from, To = prev.AddDays(1) };
                    yield break;
                }

            }

            yield return new DateRange() { From = from, To = prev.AddDays(1) };

            from = enumerator.Current;
            prev = enumerator.Current;
        }
    }
}

Usage:

var missing = BaseRanges.GetDates().Except(TestRanges.GetDates());
var ranges = missing.GetRanges();

I've tested it on your sample data and returns what it should.

Both extension methods are lazy and reads/returns one element at the time.

I'm pretty sure GetRanges method can be made much more readable :)