C# Recursion Problem -
i have range class want able subtract set of ranges.
i can single 1 fine.
e.g.
range range1 = new range(0,100); range range2 = new range(40,60); list<range> differences = range1.difference(range2); differences[0]; // 0 40 differences[1]; // 60 100 the problem stuck on when finding difference between range , 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 10 results[1]; // 70 90 the algorithm should take result difference between range , rangeset[0] , use result input next iteration etc etc. , return set of ranges result.
i'm guessing require recursive method cant head around it????
to 'clarify'. problem more complex range example have given. here test trying 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"); // 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 it's hard me explain.
agreed recursive algorithm unnecessary. need primitive set operations work , can done enough. hardest of these subtract operation, removal of 1 or more ranges single range. once have down need union can normalize ranges again.
here 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() { (int = start; <= 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); (; 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 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 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 following output:
subtract 40-60 0-100: 0 ~ 39 61 ~ 100 normalized ranges remove: 10 ~ 70 90 ~ 120 results: 0 ~ 9 71 ~ 89 press key continue . . . the primary issue remaining fence post errors in examples. need decide if range inclusive of end or not, adjust accordingly.
i note preceding program not intended 'production' ready... example of how solve issues involved. better implementation union , subtract ranges without iterating items in ranges. concept still same, build set operations , go there.
btw, if going have few hundred items use hashset or dictionary , on life ;)
Comments
Post a Comment