score:6

Accepted answer

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

score:4

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
            };
        }
    }
}

score: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 :)

score:0

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))
        );
}

Related Articles