C# Recursion Problem

I have a Range class from which I want to be able to subtract a set of Ranges.

I can do a single one fine.

E.g.

Range range1 = new Range(0,100);
Range range2 = new Range(40,60);

List<Range> differences = range1.Difference(range2);

differences[0]; // 0 to 40
differences[1]; // 60 to 100

The problem I am stuck on is when finding the difference between a range and a set of ranges:

List<Range> rangeSet = new List<Range>();
rangeSet.Add(new Range(10, 30);
rangeSet.Add(new Range(25, 70);
rangeSet.Add(new Range(90, 120);

List<Range> results = range1.Difference(rangeSet);

The results should be:

results[0]; // 0 to 10
results[1]; // 70 to 90

The algorithm should take the result from the difference between range and rangeSet[0] and then use that result as the input to the next iteration etc etc. and finally return set of ranges that are the result.

I'm guessing that this would require a recursive method but I just cant get my head around it????

To 'clarify'. The problem is more complex than the range example I have given. Here is the test I am trying to get to pass.

    [Test]
    public void BandCanReturnDifferenceWithASetOfOtherBands()
    {
        var bandA = Band.Create<ChargeBand>("Band A");
        bandA.AddMonth(EMonth.January);
        bandA.AddMonth(EMonth.February);
        bandA.AddDayOfWeek(DayOfWeek.Monday);
        bandA.AddDayOfWeek(DayOfWeek.Tuesday);
   开发者_如何转开发     bandA.AddTimeRange(5, 0, 11, 0);

        var bandA2 = Band.Create<ChargeBand>("Band A2");
        bandA2.AddMonth(EMonth.January);
        bandA2.AddMonth(EMonth.December);
        bandA2.AddDayOfWeek(DayOfWeek.Wednesday);
        bandA2.AddDayOfWeek(DayOfWeek.Friday);
        bandA2.AddTimeRange(1, 0, 10, 0);
        bandA2.AddTimeRange(12, 0, 24, 0);

        IList<IBand> bands = new List<IBand>();
        bands.Add(bandA);
        bands.Add(bandA2);

        var bandB = Band.CreateAllTimesBand<ChargeBand>("Band B");

        // this should result in
        var bandR1 = Band.Create<ChargeBand>("R1");
        var bandR2 = Band.Create<ChargeBand>("R2");
        var bandR3 = Band.Create<ChargeBand>("R3");

        bandR1.AddMonth(EMonth.January);
        bandR1.AddMonth(EMonth.February);
        bandR1.AddDayOfWeek(DayOfWeek.Monday);
        bandR1.AddDayOfWeek(DayOfWeek.Tuesday);
        bandR1.AddTimeRange(0, 0, 5, 0);
        bandR1.AddTimeRange(11, 0, 24, 0);

        bandR2.AddMonth(EMonth.January);
        bandR2.AddMonth(EMonth.December);
        bandR2.AddDayOfWeek(DayOfWeek.Wednesday);
        bandR2.AddDayOfWeek(DayOfWeek.Thursday);
        bandR2.AddTimeRange(0, 0, 1, 0);
        bandR2.AddTimeRange(10, 0, 12, 0);

        bandR3.AddMonth(EMonth.March);
        bandR3.AddMonth(EMonth.April);
        bandR3.AddMonth(EMonth.May);
        bandR3.AddMonth(EMonth.June);
        bandR3.AddMonth(EMonth.July);
        bandR3.AddMonth(EMonth.August);
        bandR3.AddMonth(EMonth.September);
        bandR3.AddMonth(EMonth.October);
        bandR3.AddMonth(EMonth.November);
        bandR3.SetAllDays();
        bandR3.AddTimeRange(0, 0, 24, 0);


        //                              J,F,M,A,M,J,J,A,S,O,N,D - M,T,W,T,F,S,S - (00:00,24:00)
        //                              J,F                     - M,T           - (05:00,11:00)              
        //                              J,                    D -     W   F     - (01:00,10:00),(12:00,24:00)


        IList<IBand> expectedResults = new List<IBand>();
        expectedResults.Add(bandR1); // J,F - M,T             - (00:00,05:00),(11:00,24:00)
        expectedResults.Add(bandR2); // J,D - W,F             - (00:00,01:00),(10:00,12:00)
        expectedResults.Add(bandR3); // M,A,M,J,J,A,S,O,N     - (00:00,24:00)

        var actualResults = bandB.Difference(bands);

        Assert.AreEqual(expectedResults.Count, actualResults.Count);

        foreach (var result in actualResults)
        {
            Assert.IsTrue(expectedResults.Contains(result));
        }
    }

Sorry if i'm not making sense but it's hard for me to explain.

Agreed that a recursive algorithm is unnecessary. You just need some primitive set operations to work with and this can be done easily enough. The hardest of these is the subtract operation, removal of one or more ranges from a single range. Once you have that down you need a union that can normalize the ranges again.

Here is a working example:

    [System.Diagnostics.DebuggerDisplay("Range({Start} - {End})")]
    public class Range : IEnumerable<int>
    {
        public int Start, End;

        public Range(int start, int end)
        {
            Start = start;
            End = end;
        }

        public IEnumerator<int> GetEnumerator()
        {
            for (int i = Start; i <= End; i++)
                yield return i;
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        { return GetEnumerator(); }

        public IEnumerable<Range> Subtract(IEnumerable<int> removed)
        {
            IEnumerator<int> add = this.GetEnumerator();
            IEnumerator<int> rem = removed.GetEnumerator();

            bool hasmore = rem.MoveNext();
            while (add.MoveNext())
            {
                int start = add.Current;
                int end = start;

                while (hasmore && rem.Current < start)
                    hasmore = rem.MoveNext();

                if(!hasmore)
                {
                    while (add.MoveNext())
                        end = add.Current;
                    yield return new Range(start, end);
                    yield break;
                }

                if(rem.Current == start)
                {
                    hasmore = rem.MoveNext();
                    continue;
                }

                while (add.MoveNext())
                {
                    if (add.Current == rem.Current)
                    {
                        hasmore = rem.MoveNext();
                        break;
                    }
                    end = add.Current;
                }
                if (end >= start)
                    yield return new Range(start, end);
            }
        }
    }

    public static IEnumerable<int> UnionRanges(this IEnumerable<Range> ranges)
    {
        int pos = int.MinValue;
        foreach(Range r in ranges.OrderBy(x => x.Start))
        {
            pos = Math.Max(pos, r.Start);
            for (; pos <= r.End; pos++)
                yield return pos;
        }
    }

    public static IEnumerable<Range> CreateRanges(this IEnumerable<int> values)
    {
        Range r = null;
        foreach (int val in values)
        {
            if (r == null)
                r = new Range(val, val);
            else if (val == r.End + 1)
                r.End++;
            else
            {
                yield return r;
                r = new Range(val, val);
            }
        }
        if (r != null)
            yield return r;
    }

    public static void Main()
    {
        Range range1 = new Range(0, 100);
        Range range2 = new Range(40, 60);

        IEnumerable<Range> diff1 = range1.Subtract(range2);

        Console.WriteLine("Subtract 40-60 from 0-100:");
        foreach (Range r in diff1)
            Console.WriteLine("{0} ~ {1}", r.Start, r.End);

        List<Range> rangeSet = new List<Range>();
        rangeSet.Add(new Range(10, 30));
        rangeSet.Add(new Range(25, 70));
        rangeSet.Add(new Range(90, 120));

        Console.WriteLine("Normalized ranges to remove:");
        foreach (Range r in rangeSet.UnionRanges().CreateRanges())
            Console.WriteLine("{0} ~ {1}", r.Start, r.End);

        IEnumerable<Range> diff2 = range1.Subtract(rangeSet.UnionRanges());

        Console.WriteLine("Results:");
        foreach (Range r in diff2)
            Console.WriteLine("{0} ~ {1}", r.Start, r.End);
    }

The preceding program produces the following output:

Subtract 40-60 from 0-100:
0 ~ 39
61 ~ 100
Normalized ranges to remove:
10 ~ 70
90 ~ 120
Results:
0 ~ 9
71 ~ 89
Press any key to continue . . .

The primary issue remaining is the fence post errors in your examples. You need to decide if the range is inclusive of the end or not, then adjust accordingly.

I will note that the preceding program was not intended to be 'production' ready... It just an example of how to solve the issues involved. A better implementation could union and subtract the ranges without iterating the items in the ranges. The concept is still the same, build the set operations and go from there.

BTW, If you are only going to have a few hundred items I would just use a HashSet or Dictionary and get on with life ;)

You can try this:

        List<Range> rangeSet = new List<Range>();
        rangeSet.Add(new Range(10, 30));
        rangeSet.Add(new Range(25, 70));
        rangeSet.Add(new Range(90, 120));

        List<Range> results = new List<Range>();
        Range currentRange = rangeSet.First();
        foreach (var x in rangeSet.Skip(1))
        {
            results.Add(x.Difference(currentRange));
            currentRange = x;
        }