Exercise index of this lecture   Alphabetic index   Course home   

Exercises and solutions
Operators, Delegates, and Events

6.1   Interval indexer  

The Interval type represents an oriented interval [from - to] of integers. We use the Interval example to illustrate the overloading of operators. If you have not already done so, read about the idea behind the struct Interval in the course teaching material.

In the client of struct Interval we use an indexer to access elements of the interval. For some interval i, the expression i[0] should access the from-value of i, and i[i.Length-1] should access the to-value of i.

Where, precisely, is the indexer used in the given client class?

Add the indexer to the struct Interval (getter only) which accesses element number j (0 <= j <= i.Length) of an interval i.

Hint: Be careful to take the orientation of the interval into account.

Does it make sense to program a setter of this indexer?

Solution

Here follows the class Interval with an indexer (getter only).

using System;
using System.Collections;

public struct Interval: IEnumerable{

  private readonly int from, to;

  public Interval(int from, int to){
    this.from = from;
    this.to = to;
  }

  public int From{
    get {return from;}
  }

  public int To{
    get {return to;}
  }

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


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

  public static explicit operator int[] (Interval i){
    int[] res = new int[i.Length];
    for (int j = 0; j < i.Length; j++) res[j] = i[j];
    return res; 
  }

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

}

I do not find that a setter would make sense. A setter would compromise the non-mutability of Interval.

6.2   An interval overlap operation  

In this exercise we continue our work on struct Interval, which we have used to illustrate overloaded operators in C#.

Add an Interal operation that finds the overlap between two intervals. Your starting point should be the struct Interval. In the version of struct Interval, provided as starting point for this exercise, intervals may be empty.

Please analyze the possible overlappings between two intervals. There are several cases that need consideration. The fact that Interval is oriented may turn out to be a complicating factor in the solution. Feel free to ignore the orientation of intervals in your solution to this exercise.

Which kind of operation will you chose for the overlapping operation in C# (method, property, indexer, operator)?

Before you program the operation in C# you should design the signature of the operation.

Program the operation in C#, and test your solution in an Interval client program. You may chose to revise the Interval client program from the teaching material.

Solution

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

  • I is to the left of J
  • J is to the left of I

Similarly, case 4 can be split into

  • I overlaps the left border of J
  • I overlaps the right border of J

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

  }

}

6.3   Finding and sorting elements in an array  

In this exercise we will work with searching and sorting in arrays. To be concrete, we work on an array of type Point, where Point is the type we have been programming in earlier exercises.

Via this exercise you are supposed to learn how to pass a delegate to a method such as Find and Sort. The purpose of passing a delegate to Find is to specify which point we are looking for.

Make an array of Point objects. You can, for instance, use this version of class Point. You can also use a version that you wrote as solution to one of the previous exercises.

Use the static method System.Array.Find to locate the first point in the array that satisfies the condition:

The sum of the x and y coordinates is (very close to) zero

The solution involves the programming of an appropriate delegate in C#. The delegate must be a Point predicate: a method that takes a Point as parameter and returns a boolean value.

Next, in this exercise, sort the list of points by use of one of the static Sort methods in System.Array. Take a look at the Sort methods in System.Array. There is an overwhelming amount of these! We will use the one that takes a Comparison delegate, Comparison<T>, as the second parameter. Please find this method in your documentation browser. Why do we need to pass a Comparison predicate to the Sort method?

Comparison<Point> is a delegate that compares two points, say p1 and p2. Pass an actual delegate parameter to Sort in which

   p1 <= p2 if and only if p1.X + p1.Y <= p2.X + p2.Y

Please notice that a comparsion between p1 and p2 must return an integer. A negative integer means that p1 is less than p2. Zero means that p1 is equal to p2. A positive integer means that p1 is greater than p2.

Test run you program. Is your Point array sorted in the way you excepts?

Solution
using System;

class FindInArray{

  public static bool NullPoint(Point p){
       return Math.Abs(p.X + p.Y) <= 0.0001;
  }       

  public static void Main(){

    /* An array of points:  */
    Point[] points = { new Point(1,2),
                       new Point(-1,2),
                       new Point(-2,2),
                       new Point(-4,5),
                       new Point(-5,5),
                       new Point(5,5),
                       new Point(-5,-5)
                     };

    /* Solution with anonymous delegate: */
    Point fp = Array.Find(points,
                                 delegate(Point p){
                                   return Math.Abs(p.X + p.Y) <= 0.0001;}
                             );

    if (fp != null)
        Console.WriteLine("We found point: {0}", fp);
    else
        Console.WriteLine("We did not find a point");


    /* Solution with a named static method: */
    Point fp1 = Array.Find(points, NullPoint);

    if (fp1 != null)
        Console.WriteLine("We found point: {0}", fp1);
    else
        Console.WriteLine("We did not find a point");


    /* Finding all desired points: */ 
    Point[] pts = Array.FindAll(points, NullPoint);
    Console.WriteLine("We found these points:");
    foreach(Point p in pts) Console.WriteLine(p);

    
    /* Sorting the points as desired: */
    Array.Sort(points, 
               delegate(Point p1, Point p2){
                 if (p1.X + p1.Y < p2.X + p2.Y)
                   return -1;
                 else if (p1.X + p1.Y == p2.X + p2.Y)
                   return 0;
                 else return 1;
               });

    Console.WriteLine("Sorted points:");
    foreach(Point p in points) Console.WriteLine(p);
  }

}

6.4   How local are local variables and formal parameters?  

When we run the following program

using System;
public class Application { 

  public delegate double NumericFunction(double d);   
  static double factor = 4.0;

  public static NumericFunction MakeMultiplier(double factor){
     return delegate(double input){return input * factor;};
  }

  public static void Main(){
    NumericFunction f = MakeMultiplier(3.0); 
    double input = 5.0;

    Console.WriteLine("factor = {0}", factor);
    Console.WriteLine("input = {0}", input);
    Console.WriteLine("f is a generated function which multiplies its input with factor");
    Console.WriteLine("f(input) = input * factor = {0}", f(input));
  }
}

we get this output

factor = 4
input = 5
f is a generated function which multiplies its input with factor
f(input) = input * factor = 15

Explain!

Solution

Here is the program (again):

using System;
public class Application { 

  public delegate double NumericFunction(double d);   
  static double factor = 4.0;

  public static NumericFunction MakeMultiplier(double factor){
     return delegate(double input){return input * factor;};
  }

  public static void Main(){
    NumericFunction f = MakeMultiplier(3.0); 
    double input = 5.0;

    Console.WriteLine("factor = {0}", factor);
    Console.WriteLine("input = {0}", input);
    Console.WriteLine("f is a generated function which multiplies its input with factor");
    Console.WriteLine("f(input) = input * factor = {0}", f(input));
  }
}

and its output:

factor = 4
input = 5
f is a generated function which multiplies its input with factor
f(input) = input * factor = 15

There are obviously two variables called factor in this program: (1) The static (global) variable factor, and the formal parameter factor of MakeMultiplier.

According to normal wisdom, the formal parameter factor is a local variable which only exists during the call of MakeMultiplier.

In addition, it is common wisdom that free names of functions are bound in the context of the function definitions, not in the context of funcion calls. Thus, in the the anonymous function

  delegate(double input){return input * factor;}

the free name factor is bound to the formal parameter of MakeMultiplier, and never to more global variables of the same name.

(A free name in a function is a name which is used in the function, but not defined in the function).

These observations contradict each other.

In C#, local variables of a function may survive the activation of the function. Thus, the the formal parameter factor (bound to 3.0) is available in the WriteLine statements of Main. In C#, this is often called captured outer variables. The function

  delegate(double input){return input * factor;}

gives rise to a closure, which holds on to its free names (here the variable factor).

6.5   Additional Die events  

In this exercise we add yet another method to the existing event i class Die, and we add another event to Die.

In the Die event example, we have a public event called twoSixesInARow which is triggered if a die shows two sixes in a row. In the sample client program we add an anonymous method to this event which reports the string parameter of the event on standard output.

Add yet another method to the twoSixesInARow event which counts the number of times 'two sixes in a row' appear. For this purpose we need - quite naturally - an integer variable for counting. Where should this variable be located relative to the 'counting method': Will you place the variable inside the new method, inside the Die class, or inside the client class of the Die?

Add a similar event called fullHouse, of the same type Notifier, which is triggered if the Die tosses a full house. A full house means (inspired from the rules of Yahtzee) two tosses of one kind and three tosses of another kind - in a row. For instance, the toss sequence 5 6 5 6 5 leads to a full house. Similarly, the 1 4 4 4 1 leads to a full house. The toss sequence 5 1 6 6 6 6 5 does not contain a full house sequence, and the toss sequence 6 6 6 6 6 is not a full house.

Be sure to test-drive the program and watch for triggering of both events.

Solution

The method DoWeHaveFullHouse is the most challenging. It searches the last five entries of the history list. It needs to find out which eyes make up the full house, and how many occurrences of these eyes have been encountered. Here comes my version of the Die class:

using System;
using System.Collections.Generic;

public class Die {
  public delegate void Notifier(string message);  // A delegate type

  private int numberOfEyes;
  private Random randomNumberSupplier; 
  private int maxNumberOfEyes;
  private List<int> history;
  public event Notifier twoSixesInARow;       
  public event Notifier fullHouse;       

  public int NumberOfEyes{
     get {return numberOfEyes;}
  }

  public Die (): this(6){}

  public Die (int maxNumberOfEyes){
    randomNumberSupplier = new Random(unchecked((int)DateTime.Now.Ticks));
    this.maxNumberOfEyes = maxNumberOfEyes;
    numberOfEyes = randomNumberSupplier.Next(1, maxNumberOfEyes + 1);
    history = new List<int>();
    history.Add(numberOfEyes);
  }
    
  public void Toss (){
    numberOfEyes = randomNumberSupplier.Next(1,maxNumberOfEyes + 1);
    history.Add(numberOfEyes);
    if (DoWeHaveTwoSixesInARow(history))
       twoSixesInARow("Two sixes in a row");
    if (DoWeHaveFullHouse(history))
       fullHouse("You have a Full House");
  }

  private bool DoWeHaveTwoSixesInARow(List<int> history){
    int histLength = history.Count;
    return histLength >= 2 && 
           history[histLength-1] == 6 && 
           history[histLength-2] == 6;
  }



  private bool DoWeHaveFullHouse(List<int> history){
    int d1 = 0, d2 = 0,   // number of eyes of the two dies involved in the full house. 0 means uninitialized.
        n1 = 0, n2 = 0,   // how many do we have of each.
        histLength = history.Count;
    if (histLength >= 5){
      for (int i = -5; i <= -1; i++){    // consult history of last 5 tosses
        if      (d1 == 0) {d1 = history[histLength + i]; n1 = 1;}  // the first toss determines d1
        else if (d2 == 0 && d1 != history[histLength + i])
                          {d2 = history[histLength + i]; n2 = 1;}  // a later toss, typically the second, determines d2
        else if (d1 == history[histLength + i]) n1++;
        else if (d2 == history[histLength + i]) n2++;
        else return false;                                         // if we ever come here we have encountered non-full-house toss
      }
      return (n1 == 2 && n2 == 3) || (n1 == 3 && n2 == 2);
   } else return false;
  }
       
  public override String ToString(){
    return String.Format("Die[{0}]: {1}", maxNumberOfEyes, NumberOfEyes);
  }
}

It should be noticed that 'instances of full house' may overlap each other.

Here follows the sample Die client class, where we add methods to the public events in class Die.

using System;

class diceApp {

  public static void Main(){

    Die d1 = new Die();

    d1.twoSixesInARow += 
     delegate (string mes){
       Console.WriteLine(mes);
     };

    d1.fullHouse += 
     delegate (string mes){
       Console.WriteLine(mes);
     };

    int doubleSixes = 0;

    d1.twoSixesInARow += 
     delegate (string mes){   // counts how many times we get
       doubleSixes++;         // two sixes in a row
     };

    for(int i = 1; i < 1000; i++){
      d1.Toss();
      Console.WriteLine("{0}: {1}", i, d1.NumberOfEyes);  
    }

    Console.WriteLine("Number of two sixes in a row: {0}.", doubleSixes);

 }
}

The variable doubleSixes is a local variable in Main in diceApp. This variable is in the scope of the anonymous function which increases the variable doubleSixes.

Generated: Monday February 7, 2011, 12:16:15