I clearly recommend to implement the overlapping operation as a method in C#.
As a supplementary notation, we may provide operator notation for the overlap method, for instance I & J. In the solution shown below, we have overloaded the & operator. Given two intervals I and J the following cases need considerations: For practical programming purposes case 1 can be split into Similarly, case 4 can be split into Here is my version of type Interval with the extensions for interval overlapping (for oriented intervals). The new property Orientation determines the orientatin of an interval (0, 1, or -1). The method OverlapWith implements the solution to the exercise. Here is a simple client of struct Interval:using System;
using System.Collections;
public struct Interval{
private readonly int from, to;
private bool empty;
public Interval(int from, int to){
this.from = from;
this.to = to;
this.empty = false;
}
/* Constructs an empty interval. A Factory method. */
public static Interval MakeEmptyInterval (){
Interval res = new Interval();
res.empty = true;
return res;
}
public int From{ //-- Access to from and to via properties.
get {return from;}
}
public int To{
get {return to;}
}
public bool Empty{
get {return empty;}
}
public int Orientation {
get{
int res;
if (empty)
res = 0;
else if (from < to)
res = 1;
else if (to < from)
res = -1;
else res = 0;
return res;
}
}
public int Length{
get {return Math.Abs(to - from) + 1;}
}
public int this[int i]{
get {if (from <= to){
if (i >= 0 && i <= Math.Abs(from-to))
return from + i;
else throw new Exception("Index out of interval bounds"); }
else if (from > to){
if (i >= 0 && i <= Math.Abs(from-to))
return from - i;
else throw new Exception("Index out of interval bounds"); }
else throw new Exception("Should not happen"); }
}
/* The current interval determines the orientation of the resulting interval */
public Interval OverlapWith (Interval other){
// Positively oriented intervals:
Interval thisPI = (this.Orientation < 0) ? !this : this,
otherPI = (other.Orientation < 0) ? !other : other,
res;
if (thisPI.Empty || otherPI.Empty)
res = MakeEmptyInterval();
else if (thisPI.From > otherPI.To || thisPI.To < otherPI.From)
res = MakeEmptyInterval();
else if (thisPI.From < otherPI.From && otherPI.To < thisPI.To)
res = otherPI;
else if (otherPI.From <= thisPI.From && thisPI.To <= otherPI.To)
res = thisPI;
else if (thisPI.From <= otherPI.From && otherPI.From <= thisPI.To)
res = new Interval(otherPI.From, thisPI.To);
else if (otherPI.From <= thisPI.From && thisPI.From <= otherPI.To)
res = new Interval(thisPI.From, otherPI.To);
else throw new Exception("Should not happen");
return (this.Orientation < 0) ? !res : res;
}
// An operator for interval overlapping:
public static Interval operator &(Interval i, Interval j){
return i.OverlapWith(j);
}
public static Interval operator +(Interval i, int j){
return new Interval(i.From + j, i.To + j);
}
public static Interval operator +(int j, Interval i){
return new Interval(i.From + j, i.To + j);
}
public static Interval operator >>(Interval i, int j){
return new Interval(i.From, i.To + j);
}
public static Interval operator <<(Interval i, int j){
return new Interval(i.From + j, i.To);
}
public static Interval operator *(Interval i, int j){
return new Interval(i.From * j, i.To * j);
}
public static Interval operator *(int j, Interval i){
return new Interval(i.From * j, i.To * j);
}
public static Interval operator -(Interval i, int j){
return new Interval(i.From - j, i.To - j);
}
public static Interval operator !(Interval i){
return new Interval(i.To, i.From);
}
private class IntervalEnumerator: IEnumerator{
private readonly Interval interval;
private int idx;
public IntervalEnumerator (Interval i){
this.interval = i;
idx = -1; // position enumerator outside range
}
public Object Current{
get {return (interval.From < interval.To) ?
interval.From + idx :
interval.From - idx;}
}
public bool MoveNext (){
if ( idx < Math.Abs(interval.To - interval.From))
{idx++; return true;}
else
{return false;}
}
public void Reset(){
idx = -1;
}
}
public IEnumerator GetEnumerator (){
return new IntervalEnumerator(this);
}
}
using System;
public class app {
public static void Main(){
Interval iv1 = new Interval(16, 4),
iv2 = new Interval(10,38),
iv3 = iv1 & iv2;
if (iv3.Empty)
Console.WriteLine("iv3 is empty");
else
Console.WriteLine("iv3 is NOT empty");
Console.WriteLine("{0}, {1}, {2}, {3}", iv3.From, iv3.To, iv3.Length, iv3.Empty);
foreach(int k in iv3){
Console.Write("{0,4}", k);
}
Console.WriteLine();
}
}