Exercises in this lecture   Go to the notes, in which this exercise belongs -- Keyboard shortcut: 'u'   Alphabetic index   Course home   

Exercise solution:
An interval overlap operation


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:

  1. I and J are disjoint
  2. I is contained in J
  3. J is contained in I
  4. I and J overlaps in another way

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).

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

}

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;

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

  }

}