Chapter 11
Generic Types and Methods

Kurt Nørmark ©
Department of Computer Science, Aalborg University, Denmark

Abstract
Previous lecture Next lecture
Index References Contents		This lecture is about type parametrization, also known as generics. We discuss both type parameterized classes, structs, methods, and delegates. We start with a motivational part, in which we understand why existing approaches are not good enough. During this part we develop several versions of a class for mathematical sets. This leads to a generic version of class Set in C#. As another example, we generalize the preexisting string class to String<T>, where T is IComparable. This leads, in a natural way, to a discussion of the contrast between IComparable and IComparable<T>. In the last part of the lecture we study generic methods and generic delegates.

Motivation for Generic Types
Operations on sets
Slide Annotated slide Contents Index
References Textbook 

We will use the class Set as the motivating example in this lecture

  • Set operations

    • aSet.Member(element)

    • aSet.Insert(element)

    • aSet.Delete(element)

    • aSet.Count

    • aSet.Subset(anotherSet)

    • aSet.GetEnumerator()

    • aSet.Intersection(anotherSet)

    • aSet.Union(anotherSet)

    • aSet.Diff(anotherSet)

The classes IntSet and StringSet
Slide Annotated slide Contents Index
References Textbook 

A set of int and a set of string are very similar

Program: The class IntSet. 
using System;
using System.Collections;

public class IntSet {

  private int capacity;
  private static int DefaultCapacity = 10;
  private int[] store;
  private int next;     // The next place to insert

  public IntSet(int capacity){
    this.capacity = capacity;
    store = new int[capacity];
    next = 0;
  }

  public IntSet(): this(DefaultCapacity){
  }

  public IntSet(int[] elements): this(elements.Length){
    foreach(int  el in elements) this.Insert(el);
  }

  // Copy constructor
  public IntSet(IntSet s): this(s.capacity){
    foreach(int  el in s) this.Insert(el);
  }

  public bool Member(int  element){
    for(int idx = 0; idx < next; idx++)
      if (element.Equals(store[idx]))
        return true;
    return false;
  }

  public void Insert(int  element){
    if (!this.Member(element)){
      if (this.Full){
        Console.WriteLine("[Resize to {0}]", capacity * 2);
        Array.Resize<int>(ref store, capacity * 2);
        capacity = capacity * 2;
      }
      store[next] = element;
      next++;
    }
  }

  public void Delete(int  element){
    bool found = false;
    int foundIdx = 0;
    for(int idx = 0; !found && (idx < next); idx++){
      if (element.Equals(store[idx])){
         found = true;
         foundIdx = idx;
      }
    }
    if (found){   // shift remaining elements left
      for(int idx = foundIdx+1; idx < next; idx++)
        store[idx-1] = store[idx];
      store[next-1] = default(int  );
      next--;
    }
  }

  public int Count{
    get{
      return next;
    }
  }

  // Is this set a subset of other
  public bool Subset(IntSet other){
    foreach(int  e in this)
      if (!other.Member(e))
         return false;
    return true;
  }
     
  public override string ToString(){
    string elRes = "";
    for(int idx = 0; idx < next; idx++) 
      elRes += " " + store[idx];
    return "{" + elRes + " "+ "}";
  }

  private bool Full{
    get{
      return next == capacity;
    }
  }

  public IEnumerator GetEnumerator (){
    return new SetEnumerator(this);
  }
  
  private class SetEnumerator: IEnumerator{
 
    private readonly IntSet set; 
    private int idx;

    public SetEnumerator (IntSet s){
      this.set = s;
      idx = -1;   // position enumerator outside range
    }
 
    public Object Current{ 
      get {
       return set.store[idx];
      }
    }

    public bool MoveNext(){
      if (idx < set.next - 1){
        idx++; 
        return true;
      }
      else
         return false;
    }

    public void Reset(){
      idx = -1;         
    }

    public void Dispose(){
    }

  }    
   
}

Program: A client of IntSet. 
using System;
using System.Collections;

class App{

 public static void Main(){
   IntSet s1 = new IntSet(),
          s2 = new IntSet();

   s1.Insert(1); s1.Insert(2);  s1.Insert(3);
   s1.Insert(4); s1.Insert(5);  s1.Insert(6);
   s1.Insert(5); s1.Insert(6);  s1.Insert(8);
   s1.Delete(3); s1.Delete(6);  s1.Insert(9);

   s2.Insert(8); s2.Insert(9); 

   Console.WriteLine("s1: {0}", s1);
   Console.WriteLine("s2: {0}", s2);

// Exercises:
// Console.WriteLine("{0}", s2.Intersection(s1));
// Console.WriteLine("{0}", s2.Union(s1));
// Console.WriteLine("{0}", s2.Diff(s1));

   if (s1.Subset(s2))
     Console.WriteLine("s1 is a subset of s2");
   else 
     Console.WriteLine("s1 is not a subset of s2");

   if (s2.Subset(s1))
     Console.WriteLine("s2 is a subset of s1");
   else 
     Console.WriteLine("s2 is not a subset of s1");
 }
}

Program: Output from the IntSet client program. 
s1: { 1 2 4 5 8 9 }
s2: { 8 9 }
s1 is not a subset of s2
s2 is a subset of s1

Program: The class StringSet. 
using System;
using System.Collections;

public class StringSet {

  private int capacity;
  private static int DefaultCapacity = 10;
  private string[] store;
  private int next;

  public StringSet(int capacity){
    this.capacity = capacity;
    store = new string[capacity];
    next = 0;
  }

  public StringSet(): this(DefaultCapacity){
  }

  public StringSet(string[] elements): this(elements.Length){
    foreach(string el in elements) this.Insert(el);
  }

  // Copy constructor
  public StringSet(StringSet s): this(s.capacity){
    foreach(string el in s) this.Insert(el);
  }

  public bool Member(string element){
    for(int idx = 0; idx < next; idx++)
      if (element.Equals(store[idx]))
        return true;
    return false;
  }

  public void Insert(string element){
    if (!this.Member(element)){
      if (this.Full){
        Console.WriteLine("[Resize to {0}]", capacity * 2);
        Array.Resize<string>(ref store, capacity * 2);
        capacity = capacity * 2;
      }
      store[next] = element;
      next++;
    }
  }

  public void Delete(string element){
    bool found = false;
    int  foundIdx = 0;
    for(int idx = 0; !found && (idx < next); idx++){
      if (element.Equals(store[idx])){
         found = true;
         foundIdx = idx;
      }
    }
    if (found){   // shift remaining elements left
      for(int idx = foundIdx+1; idx < next; idx++)
        store[idx-1] = store[idx];
      store[next-1] = default(string);
      next--;
    }
  }

  public int Count{
    get{
      return next;
    }
  }

  // Is this set a subset of other
  public bool Subset(StringSet other){
    foreach(string e in this)
      if (!other.Member(e))
         return false;
    return true;
  }
     
  private bool Full{
    get{
      return next == capacity;
    }
  }

  public IEnumerator GetEnumerator (){
    return new SetEnumerator(this);
  }
  
  private class SetEnumerator: IEnumerator{
 
    private readonly StringSet set; 
    private int idx;

    public SetEnumerator (StringSet s){
      this.set = s;
      idx = -1;   // position enumerator outside range
    }
 
    public Object Current{ 
      get {
       return set.store[idx];
      }
    }

    public bool MoveNext(){
      if (idx < set.next - 1){
        idx++; 
        return true;
      }
      else
         return false;
    }

    public void Reset(){
      idx = -1;         
    }

    public void Dispose(){
    }

  }    

  public override string ToString(){
    string elRes = "";
    for(int idx = 0; idx < next; idx++) 
      elRes += " " + store[idx];
    return "{" + elRes + " "+ "}";
  }

   
}

Program: A client of StringSet. 
using System;
using System.Collections;

class App{

 public static void Main(){
   StringSet s1 = new StringSet(),
             s2 = new StringSet();

   s1.Insert("a"); s1.Insert("b");  s1.Insert("c");
   s1.Insert("dd"); s1.Insert("ee");  s1.Insert("ff");
   s1.Insert("ggg"); s1.Insert("hhh");  s1.Insert("iii");
   s1.Delete("c"); s1.Delete("ff");  s1.Insert("iii");

   s2.Insert("a"); s2.Insert("iii"); 

   Console.WriteLine("s1: {0}", s1);
   Console.WriteLine("s2: {0}", s2);

// Exercises:
// Console.WriteLine("{0}", s2.Intersection(s1));
// Console.WriteLine("{0}", s2.Union(s1));
// Console.WriteLine("{0}", s2.Diff(s1));

   if (s1.Subset(s2))
     Console.WriteLine("s1 is a subset of s2");
   else 
     Console.WriteLine("s1 is not a subset of s2");

   if (s2.Subset(s1))
     Console.WriteLine("s2 is a subset of s1");
   else 
     Console.WriteLine("s2 is not a subset of s1");
 }
}

Program: Output from the IntSet client program. 
s1: { a b dd ee ggg hhh iii }
s2: { a iii }
s1 is not a subset of s2
s2 is a subset of s1

It is tedious to make a maintain both of these classes separately

The class ObjectSet
Slide Annotated slide Contents Index
References Textbook 

A set of Objects fulfills all needs, but ...

Program: The class ObjectSet. 
using System;
using System.Collections;

public class ObjectSet {

  private int capacity;
  private static int DefaultCapacity = 10;
  private Object[] store;
  private int next;

  public ObjectSet(int capacity){
    this.capacity = capacity;
    store = new Object[capacity];
    next = 0;
  }

  public ObjectSet(): this(DefaultCapacity){
  }

  public ObjectSet(Object[] elements): this(elements.Length){
    foreach(Object el in elements) this.Insert(el);
  }

  // Copy constructor
  public ObjectSet(ObjectSet s): this(s.capacity){
    foreach(Object  el in s) this.Insert(el);
  }

  public bool Member(Object  element){
    for(int idx = 0; idx < next; idx++)
      if (element.Equals(store[idx]))
        return true;
    return false;
  }

  public void Insert(Object  element){
    if (!this.Member(element)){
      if (this.Full){
        Console.WriteLine("[Resize to {0}]", capacity * 2);
        Array.Resize<Object>(ref store, capacity * 2);
        capacity = capacity * 2;
      }
      store[next] = element;
      next++;
    }
  }

  public void Delete(Object  element){
    bool found = false;
    int  foundIdx = 0;
    for(int idx = 0; !found && (idx < next); idx++){
      if (element.Equals(store[idx])){
         found = true;
         foundIdx = idx;
      }
    }
    if (found){   // shift remaining elements left
      for(int idx = foundIdx+1; idx < next; idx++)
        store[idx-1] = store[idx];
      store[next-1] = default(Object  );
      next--;
    }
  }

  public int Count{
    get{
      return next;
    }
  }

  // Is this set a subset of other
  public bool Subset(ObjectSet other){
    foreach(Object  e in this)
      if (!other.Member(e))
         return false;
    return true;
  }
     
  public override string ToString(){
    string elRes = "";
    for(int idx = 0; idx < next; idx++) 
      elRes += " " + store[idx];
    return "{" + elRes + " "+ "}";
  }

  private bool Full{
    get{
      return next == capacity;
    }
  }

  public IEnumerator GetEnumerator (){
    return new SetEnumerator(this);
  }
  
  private class SetEnumerator: IEnumerator{
 
    private readonly ObjectSet set; 
    private int idx;

    public SetEnumerator (ObjectSet s){
      this.set = s;
      idx = -1;   // position enumerator outside range
    }
 
    public Object  Current{ 
      get {
       return set.store[idx];
      }
    }

    public bool MoveNext(){
      if (idx < set.next - 1){
        idx++; 
        return true;
      }
      else
         return false;
    }

    public void Reset(){
      idx = -1;         
    }

    public void Dispose(){
    }

  }    
   
}

Program: A client of ObjectSet - working with sets of Die objects. 
using System;
using System.Collections;

class App{

 public static void Main(){
   ObjectSet s1 = new ObjectSet(),
             s2 = new ObjectSet();

   Die d1 = new Die(6),  d2 = new Die(10),
       d3 = new Die(16), d4 = new Die(8);

   s1.Insert(d1); s1.Insert(d2);  s1.Insert(d3);
   s1.Insert(d4); s1.Insert(d1);  s1.Insert(d1);
   s1.Delete(d1); s1.Delete(d2); 

   s2.Insert(d3); s2.Insert(d3); s2.Insert(d4); 

   Console.WriteLine("s1: {0}", s1);
   Console.WriteLine("s2: {0}", s2);

// Exercises:
// Console.WriteLine("{0}", s2.Intersection(s1));
// Console.WriteLine("{0}", s2.Union(s1));
// Console.WriteLine("{0}", s2.Diff(s1));

   if (s1.Subset(s2))
     Console.WriteLine("s1 is a subset of s2");
   else 
     Console.WriteLine("s1 is not a subset of s2");

   if (s2.Subset(s1))
     Console.WriteLine("s2 is a subset of s1");
   else 
     Console.WriteLine("s2 is not a subset of s1");
 }
}

Program: Output from the ObjectSet client program. 
s1: { Die[16]:2 Die[8]:1 }
s2: { Die[16]:2 Die[8]:1 }
s1 is a subset of s2
s2 is a subset of s1

Program: A client of ObjectSet - working with set of different types. 
using System;
using System.Collections;

class App{

 public static void Main(){
   Die d1 = new Die(6),  d2 = new Die(10),
       d3 = new Die(16), d4 = new Die(8);
   int sum = 0;
   string netString = "";

   ObjectSet 
     s1 = new ObjectSet(                  // A set of dice
            new Die[]{d1, d2, d3, d4}),
     s2 = new ObjectSet(                  // A set of ints
            new Object[]{1, 2, 3, 4}),
     s3 = new ObjectSet(                  // A set of strings
            new string[]{"a", "b", "c", "d"}),
     s4 = new ObjectSet(                  // A set of mixed things...
            new Object[]{new Die(6), "a", 7});

   foreach(Object o in s1){
      ((Die)o).Toss();
      Console.WriteLine("{0}", (Die)o);
   }

   Console.WriteLine("--------------");

   // Alternative - illustrating built-in cast of foreach
   foreach(Die d in s1){
      d.Toss();
      Console.WriteLine("{0}", d);
   }
   Console.WriteLine("--------------");

   foreach(Object o in s2)
      sum += ((int)o);
   Console.WriteLine(
     "Sum: {0}", sum);
   Console.WriteLine("--------------");

   foreach(Object o in s3)
      netString += ((string)o);
   Console.WriteLine(
     "NetString: {0}", netString);
   Console.WriteLine("--------------");

   foreach(Object o in s4)
      Console.WriteLine("{0}", o);

   Console.WriteLine("--------------");
 }
}

Program: Output from the the client of ObjectSet - the version that works with sets of different types. 
Die[6]:6
Die[10]:10
Die[16]:15
Die[8]:8
--------------
Die[6]:3
Die[10]:4
Die[16]:6
Die[8]:3
--------------
Sum: 10
--------------
NetString: abcd
--------------
Die[6]:1
a
7
--------------

Class ObjectSet is not type safe

Use of class Object as element type requires a lot of casting

Problems
Slide Annotated slide Contents Index
References Textbook 

IntSet, StringSet and ObjectSet suffer from both programming and type problems

  • Problems with IntSet and StringSet

    • Tedious to write both versions: Copy and paste programming.

    • Error prone to maintain both versions

  • Problems with ObjectSet

    • Elements of the set must be downcasted in case we need to use some of their specialized operations

    • We can create an inhomogeneous set

      • A set of "apples" and "bananas"

Reference

Inhomogeneous sets can also be seen as an advantage

Generic Types
The generic class Set<T>
Slide Annotated slide Contents Index
References Textbook 

It is attractive to parameterize the class Set with its element type T

Program: The class Set<T>. 
using System;
using System.Collections.Generic;
using System.Collections;

public class Set<T> {

  private int capacity;
  private static int DefaultCapacity = 10;
  private T[] store;
  private int next;

  public Set(int capacity){
    this.capacity = capacity;
    store = new T[capacity];
    next = 0;
  }

  public Set(): this(DefaultCapacity){
  }

  public Set(T[] elements): this(elements.Length){
    foreach(T el in elements) this.Insert(el);
  }

  // Copy constructor
  public Set(Set<T> s): this(s.capacity){
    foreach(T el in s) this.Insert(el);
  }

  public bool Member(T element){
    for(int idx = 0; idx < next; idx++)
      if (element.Equals(store[idx]))
        return true;
    return false;
  }

  public void Insert(T element){
    if (!this.Member(element)){
      if (this.Full){
        Console.WriteLine("[Resize to {0}]", capacity * 2);
        Array.Resize<T>(ref store, capacity * 2);
        capacity = capacity * 2;
      }
      store[next] = element;
      next++;
    }
  }

  public void Delete(T element){
    bool found = false;
    int  foundIdx = 0;
    for(int idx = 0; !found && (idx < next); idx++){
      if (element.Equals(store[idx])){
         found = true;
         foundIdx = idx;
      }
    }
    if (found){   // shift remaining elements left
      for(int idx = foundIdx+1; idx < next; idx++)
        store[idx-1] = store[idx];
      store[next-1] = default(T);
      next--;
    }
  }

  public int Count{
    get{
      return next;
    }
  }

  // Is this set a subset of other
  public bool Subset(Set<T> other){
    foreach(T e in this)
      if (!other.Member(e))
         return false;
    return true;
  }
     
  public override string ToString(){
    string elRes = "";
    for(int idx = 0; idx < next; idx++) 
      elRes += " " + store[idx];
    return "{" + elRes + " "+ "}";
  }

  private bool Full{
    get{
      return next == capacity;
    }
  }

  public IEnumerator<T> GetEnumerator (){
    return new SetEnumerator(this);
  }
  
  private class SetEnumerator: IEnumerator<T>{
 
    private readonly Set<T> set; 
    private int idx;

    public SetEnumerator (Set<T> s){
      this.set = s;
      idx = -1;   // position enumerator outside range
    }
 
    public T Current{ 
      get {
       return set.store[idx];
      }
    }

    Object IEnumerator.Current{ 
      get {
       return set.store[idx];
      }
    }

    public bool MoveNext(){
      if (idx < set.next - 1){
        idx++; 
        return true;
      }
      else
         return false;
    }

    public void Reset(){
      idx = -1;         
    }

    public void Dispose(){
    }

  }    
   
}

Program: A client of Set<T> - working with sets of different types. 
using System;
using System.Collections;

class App{

 public static void Main(){
   Die d1 = new Die(6),  d2 = new Die(10),
       d3 = new Die(16), d4 = new Die(8);
   int sum = 0;
   string netString = "";


   // Working with sets of dice:
   Set<Die>  s1 = new Set<Die>(       // A set of dice
                      new Die[]{d1, d2, d3, d4});
   foreach(Die d in s1){
      d.Toss();
      Console.WriteLine("{0}", d);
   }


   // Working with sets of ints
   Set<int> s2 = new Set<int>(        // A set of ints
                      new int[]{1, 2, 3, 4});
   foreach(int i in s2)
      sum += i;
   Console.WriteLine("Sum: {0}", sum);


   // Working with sets of strings
   Set<string> s3 = new Set<string>(  // A set of strings
                      new string[]{"a", "b", "c", "d"});
   foreach(string str in s3)
      netString += str;
   Console.WriteLine("Appended string: {0}", netString);

 }
}

Program: Output from the Set<T> client program. 
Die[6]:3
Die[10]:10
Die[16]:16
Die[8]:8
Sum: 10
Appended string: abcd

Exercise 11.4. Intersection, union, and difference: Operations on sets

On the accompanying slide we have shown a generic class set<T>.

Add the classical set operations intersection, union and set difference to the generic class set<T>.

Test the new operations from a client program.

Hint: The enumerator, that comes with the class set<T>, may be useful for the implementation of the requested set operations.

Exercise 11.4. An element access operation on sets

The only way to get access to an element from a set is via use of the enumerator (also known as the iterator) of the set. In this exercise we wish to change that.

Invent some operation on the set that allows you to take out an existing element in the set. This corresponds to accessing a given item in an array or a list, for instance via an indexer: arr[i] and lst[j]. Notice in this context that there is no order between elements in the set. It is not natural to talk about "the first" or "the last" element in the set.

Given the invented operation in Set<T> use it to illustrate that, for some concrete type T, no casting is necessary when elements are accessed from Set<T>

Exercise 11.4. A generic Pair class

Program a generic class Pair<S,T> which aggregates two values of the types S and T respectively. It is sufficient to program non-mutable pairs. Be sure to equip the class with an appropriate constructor, and appropriate getter properties.

An actual type is provided when the class Set is used, for instance in a client class.

Generic Types
Slide Annotated slide Contents Index
References Textbook 

C# supports generic classes, generic structs, generic interfaces, and generic delegate types

  • Template

    • C<T> is not a type

    • C<T> is a template from which a type can be constructed

    • T is a formal type parameter

  • Constructed type

    • The type constructed from a template

    • C<int>, C<string>, and D<C<int>>

    • int, string, and C<int> are actual type parameters of C and D

The ability to have generic types is known as parametric polymorphism

Constraints on Formal Type Parameters
Slide Annotated slide Contents Index
References Textbook 

It is possible to express a number of constraints on a formal type parameter

The more constraints on T, the more we can do on T-objects in the body of C<T>

Program: Illustrations of the various constraints on type parameters. 
class C<S,T>: D  
    where T: A, ICloneable
    where S: B {
 ...
}

class E<T>: D
    where T: class{
 ...
}

class F<T>: D
    where T: struct{
 ...
}

class G<T>: D
    where T: new(){
 ...
}

Constraints: Strings of comparable elements
Slide Annotated slide Contents Index
References Textbook 

String<T> generalizes string of char to string of comparable elements

Reference

Program: The generic class String<T>. 
using System;

public class String<T>: IComparable<String<T>> where T: IComparable<T>{
  
  private T[] content;

  public String(){
    content = new T[0];
  }

  public String(T e){
    content = new T[]{e}; 
  }

  public String(T e1, T e2){
    content = new T[]{e1, e2}; 
  }

  public String(T e1, T e2, T e3){
    content = new T[]{e1, e2, e3}; 
  }

  public int CompareTo(String<T> other){
    int thisLength = this.content.Length,
        otherLength = other.content.Length;
 
    for (int i = 0; i < Math.Min(thisLength,otherLength); i++){
      if (this.content[i].CompareTo(other.content[i]) < 0)  
         return -1;
      else if (this.content[i].CompareTo(other.content[i]) > 0)
         return 1;
    }
    // longest possible prefixes of this and other are pair-wise equal.
    if (thisLength < otherLength)
       return -1;
    else if (thisLength > otherLength)
       return 1;
    else return 0;
  }

  public override string ToString(){
    string res = "[";
    for(int i = 0; i < content.Length;i++){
      res += content[i];
      if (i < content.Length - 1) res += ", ";
    }
    res += "]";
    return res;
  } 

}

Program: Illustrating a number of String<int> objects. 
using System;

class StringApp{

  public static void Main(){  
                              
    ReportCompare(new String<int>(), new String<int>(1));             
    ReportCompare(new String<int>(1), new String<int>(1));            
    ReportCompare(new String<int>(1,2,3), new String<int>(1));        
    ReportCompare(new String<bool>(false), 
                  new String<bool>(false, true, false));        
    ReportCompare(new String<bool>(true, true, false), 
                  new String<bool>(true, true,false));    
  }

  public static void ReportCompare<T>(String<T> s, String<T> t)
    where T: IComparable<T>{
    Console.WriteLine("Result of comparing {0} and {1}: {2}", 
                      s, t, s.CompareTo(t));
  }   

}

Program: Output from the String<int> program. 
Result of comparing [] and [1]: -1
Result of comparing [1] and [1]: 0
Result of comparing [1, 2, 3] and [1]: 1
Result of comparing [1] and [1, 2, 3]: -1
Result of comparing [1, 2, 3] and [1, 2, 3]: 0

Program: Illustrating Strings of different types. 
using System;

class StringApp{

  public static void Main(){

    ReportCompare(new String<int>(1, 2), 
                  new String<int>(1));
    ReportCompare(new String<string>("1", "2", "3"), 
                  new String<string>("1"));
    ReportCompare(new String<double>(0.5, 1.7, 3.0), 
                  new String<double>(1.0, 1.7, 3.0));
    ReportCompare(new String<bool>(true, false), 
                  new String<bool>(false, true));
    ReportCompare(new String<Die>(new Die(), new Die()),
                  new String<Die>(new Die(), new Die()));
  }

  public static void ReportCompare<T>(String<T> s, String<T> t)
    where T: IComparable<T>{
    Console.WriteLine("Result of comparing {0} and {1}: {2}", 
                      s, t, s.CompareTo(t));
  }   

}

Program: Output from the String of different types program. 
Result of comparing [1, 2] and [1]: 1 
Result of comparing [1, 2, 3] and [1]: 1 
Result of comparing [0,5, 1,7, 3] and [1, 1,7, 3]: -1 
Result of comparing [True, False] and [False, True]: 1 
Result of comparing [[3], [6]] and [[3], [5]]: 1

Exercise 11.5. Comparable Pairs

This exercise is inspired by an example in the book by Hansen and Sestoft: C# Precisely.

Program a class ComparablePair<T,U> which implements the interface IComparable<ComparablePair<T,U>>. If you prefer, you can build the class ComparablePair<T,U> on top of class Pair<S,T> from an earlier exercise in this lecture.

It is required that T and U are types that implement Icomparable<T> and Icomparable<U> respectively. How is that expressed in the class ComparablePair<T,U>?

The generic class ComparablePair<T,U> should represent a pair (t,u) of values/objects where t is of type T and u is of type U. The generic class should have an appropriate constructor that initializes both parts of the pair. In addition, there should be properties that return each of the parts. Finally, the class should - of course - implement the operation CompareTo because it is prescribed by the interface System.IComparable<ComparablePair<T,U>>.

Given two pairs p = (a,b) and q= (c,d). p is considered less than q if a is less than c. If a is equal to c then b and d controls the ordering. This is similar to lexicographic ordering on strings.

If needed, you may get useful inspiration from the Icomparable class String<T> on the accompanying slide.

Be sure to test-drive your solution!

Another example of constraints
Slide Annotated slide Contents Index
References Textbook 

Two generic classes for which constraints are necessary

Program: Two generic classes C and D - what is the problem?. 
/* Example from Hansen and Sestoft: C# Precisely */

//  What are the problems? 

class C<T>{
  T f = null;
}

class D<U>{
  U? f;
}

Program: Two generic classes C and D - with compiler errors. 
/* Example from Hansen and Sestoft: C# Precisely */

class C<T>{
  // Compiler Error message:
  // Cannot convert null to type parameter 'T' because it could 
  // be a value type. Consider using 'default(T)' instead.
  T f = null;
}

class D<U>{
  // Compiler Error message:
  // The type 'U' must be a non-nullable value type in order to use 
  // it as parameter 'T' in the generic type or method 
  // 'System.Nullable<T>'
  U? f;
}

Program: Two generic classes C and D - with the necessary constraints. 
/* Example from Hansen and Sestoft: C# Precisely */

class C<T> where T: class{
  T f = null;
}

class D<U> where U: struct{
  U? f;
} 

class Appl{

  // Does NOT compile:
  C<double> c = new C<double>();
  D<A>      d = new D<A>();  

  // OK:
  C<A>      c1 = new C<A>();
  D<double> d1 = new D<double>();  
  
} 

class A{}

Variance
Slide Annotated slide Contents Index
References Textbook 

A CheckAccount is a BankAccount

But is a Set<CheckAccount> a Set<BankAccount> ?

Program: Sets of check accounts and bank accounts. 
using System;

class SetOfAccounts{

  public static void Main(){

    // Construct accounts:
    BankAccount ba1 = new BankAccount("John", 0.02),
                ba2 = new BankAccount("Anne", 0.02),
                ba3 = new BankAccount("Frank", 0.02);

    CheckAccount ca1 = new CheckAccount("Mike", 0.03),
                 ca2 = new CheckAccount("Lene", 0.03),
                 ca3 = new CheckAccount("Joan", 0.03);

    // Constructs empty sets of accounts:
    Set<BankAccount> s1 = new Set<BankAccount>();
    Set<CheckAccount> s2 = new Set<CheckAccount>();

    // Insert elements in the sets:
    s1.Insert(ba1);  s1.Insert(ba2);
    s2.Insert(ca1);  s2.Insert(ca2);

    // Establish s1 as an alias to s2
    s1 = s2;   // Compile-time error:
               // Cannot implicitly convert type 'Set<CheckAccount>' 
               // to 'Set<BankAccount>'

    // Insert a BankAccount object into s1, 
    // and via the alias also in s2
    s1.Insert(new BankAccount("Bodil", 0.02));

    // Activates some CheckAccount operation on a BankAccount object
    foreach(CheckAccount ca in s2)
      ca.SomeCheckAccountOperation();

    Console.WriteLine("Set of BankAccount: {0}", s1);
    Console.WriteLine("Set of CheckAccount: {0}", s2);
   

  }

}

Reference

  • Covariance

    • The set types vary in the same way as the element types

  • Contravariance

    • The set types vary in the opposite way as the element types

  • Invariance

    • The set types are not affected by the variations of the element types

C# 3.0 uses invariance

Generic structs
Slide Annotated slide Contents Index
References Textbook 

Generic structs are very similar to generic classes

We use the generic struct Nullable<T> as an example

Reference

  • Struct Nullable<T>

    • The type T? serves as a convenient alias of Nullable<T>

    • The generic type Nullable<T> enjoys additional special support by the C# compiler

      • Lifted operators

Program: A partial reproduction of struct Nullable<T>. 
using System;

public struct Nullable<T> 
  where T : struct{

  private T value;
  private bool hasValue;

  public Nullable(T value){
    this.value = value;
    this.hasValue = true;
  }

  public bool HasValue{
    get{
      return hasValue;
    }
  }

  public T Value{
    get{
      if(hasValue)
        return value;
      else throw new InvalidOperationException();
    }
  }

}

Generic interfaces: IComparable<T>
Slide Annotated slide Contents Index
References Textbook 

We illustrate generic interfaces with IComparable

Program: A reproduction of the non-generic interface IComparable. 
using System;

public interface IComparable{
  int CompareTo(Object other);
}

Program: A reproduction of the generic interface IComparable<T>. 
using System;

public interface IComparable <T>{
  int CompareTo(T other);
}

Program: A class Die that implements IComparable. 
using System;

public class Die: IComparable {
  private int numberOfEyes;
  private Random randomNumberSupplier; 
  private const int maxNumberOfEyes = 6;

  public Die(){
    randomNumberSupplier = Random.Instance();
    numberOfEyes = NewTossHowManyEyes();
  }   

  // Assume as a precondition that other is a Die
  public int CompareTo(Object other){
    return this.numberOfEyes.CompareTo(((Die)other).numberOfEyes);
  }
    
  public void Toss(){
    numberOfEyes = NewTossHowManyEyes();
  }

  private int NewTossHowManyEyes (){
    return randomNumberSupplier.Next(1,maxNumberOfEyes + 1);
  }

  public int NumberOfEyes() {
    return numberOfEyes;
  }

  public override String ToString(){
    return String.Format("[{0}]", numberOfEyes);
  }

}

public class Random {

  // Singleton pattern:
  // Keeps track of unique instance of this class
  private static Random uniqueInstance = null;

  // Holds the instance of System.Random
  private System.Random systemRandom;

  // Singleton pattern: Private constructor.
  private Random(){
    systemRandom = new System.Random(unchecked((int)DateTime.Now.Ticks));
  }

  public static Random Instance(){
    if (uniqueInstance == null)
      uniqueInstance = new Random();
    return uniqueInstance;
  }

  public int Next(int lower, int upper){
    // delegate to systemRandom
    return systemRandom.Next(lower,upper);
  }

}

class App{

  public static void Main(){

    Die[] dice = new Die[]{new Die(), new Die(), new Die(), new Die(),
                           new Die(), new Die(), new Die(), new Die(),
                          };
    Console.WriteLine("Before sorting");
    foreach(Die d in dice)
      Console.Write("{0} ", d);
    
    Console.WriteLine();

    Console.WriteLine("After sorting");
    Array.Sort(dice);
    foreach(Die d in dice)
      Console.Write("{0} ", d);

  }

}

Program: A class Die that implements IComparable<T>. 
using System;

public class Die: IComparable<Die> {
  private int numberOfEyes;
  private Random randomNumberSupplier; 
  private const int maxNumberOfEyes = 6;

  public Die(){
    randomNumberSupplier = Random.Instance();
    numberOfEyes = NewTossHowManyEyes();
  }   

  public int CompareTo(Die other){
    return this.numberOfEyes.CompareTo(other.numberOfEyes);
  }
    
  public void Toss(){
    numberOfEyes = NewTossHowManyEyes();
  }

  private int NewTossHowManyEyes (){
    return randomNumberSupplier.Next(1,maxNumberOfEyes + 1);
  }

  public int NumberOfEyes() {
    return numberOfEyes;
  }

  public override String ToString(){
    return String.Format("[{0}]", numberOfEyes);
  }

}

public class Random {

  // Singleton pattern:
  // Keeps track of unique instance of this class
  private static Random uniqueInstance = null;

  // Holds the instance of System.Random
  private System.Random systemRandom;

  // Singleton pattern: Private constructor.
  private Random(){
    systemRandom = new System.Random(unchecked((int)DateTime.Now.Ticks));
  }

  public static Random Instance(){
    if (uniqueInstance == null)
      uniqueInstance = new Random();
    return uniqueInstance;
  }

  public int Next(int lower, int upper){
    // delegate to systemRandom
    return systemRandom.Next(lower,upper);
  }

}

class App{

  public static void Main(){

    Die[] dice = new Die[]{new Die(), new Die(), new Die(), new Die(),
                           new Die(), new Die(), new Die(), new Die(),
                          };
    Console.WriteLine("Before sorting");
    foreach(Die d in dice)
      Console.Write("{0} ", d);
    
    Console.WriteLine();

    Console.WriteLine("After sorting");
    Array.Sort(dice);
    foreach(Die d in dice)
      Console.Write("{0} ", d);

  }

}

The implementation of the generic interface is more type safe and less clumsy than the implementation of the non-generic solution

Generic equality interfaces
Slide Annotated slide Contents Index
References Textbook 

The generic interface IEquatable<T> prescribes an Equals operation, and as such it is more fundamental than the interface IComparable<T>.

The generic interface IEqualityComparer<T> prescribes both Equals and GetHashCode.

Program: A reproduction of the generic interface IEquatable<T>. 
using System;

public interface IEquatable <T>{
  bool Equals (T other);
}

Program: A reproduction of the generic interface IEqualityComparer<T>. 
using System;

public interface IEqualityComparer <T>{
  bool Equals (T x, T y);
  int GetHashCode (T x);
}

  • Practical use of these interfaces

    • Collection classes of T elements often need to know if two elements of type T are equal to each other

    • From T it is possible to request a default equality comparer, which implements IEqualityComparer<T>

Generic Classes and Inheritance
Slide Annotated slide Contents Index
References Textbook 

Can a generic/non-generic class inherit from a non-generic/generic class?

  • Legal subclassing

    • A generic subclass of a non-generic superclass

    • A generic subclass of a constructed superclass

    • A generic subclass of generic superclass

  • Illegal subclassing

    • A non-generic subclass of generic superclass

References

Program: Possible and impossible subclasses of Set classes. 
using System;

// A generic subclass of a non-generic superclass.
class SomeGenericSet1<T>: IntSet{
  // ...
}

// A generic subclass of a constructed superclass
class SomeGenericSet2<T>: Set<int>{
  // ...
}

// A generic subclass of a generic superclass
// The most realistic case
class SpecializedSet<T>: Set<T>{
  // ...
}

// A non-generic subclass of a generic superclass
// Illegal. Compile-time error:
// The type or namespace name 'T' could not be found
class Set: Set<T>{
  // ...
}

Generic Methods
Generic Methods
Slide Annotated slide Contents Index
References Textbook 

A generic method is a template of a method that takes a number of type parameters

It is possible to have generic methods in both generic and non-generic types

Program: The generic method ReportCompare in the generic String programs. 
using System;

class StringApp{

  public static void Main(){  
                              
    ReportCompare(new String<int>(), new String<int>(1));             
    ReportCompare(new String<int>(1), new String<int>(1));            
    ReportCompare(new String<int>(1,2,3), new String<int>(1));        
    ReportCompare(new String<bool>(false), 
                  new String<bool>(false, true, false));        
    ReportCompare(new String<bool>(true, true, false), 
                  new String<bool>(true, true,false));    
  }

  public static void ReportCompare<T>(String<T> s, String<T> t)
    where T: IComparable<T>{
    Console.WriteLine("Result of comparing {0} and {1}: {2}", 
                      s, t, s.CompareTo(t));
  }   

}

Program: An equivalent program without automatic inference of the actual type parameters. 
using System;

class StringApp{

  public static void Main(){  
                              
    ReportCompare<int>(new String<int>(), new String<int>(1));             
    ReportCompare<int>(new String<int>(1), new String<int>(1));            
    ReportCompare<int>(new String<int>(1,2,3), new String<int>(1));        
    ReportCompare<bool>(new String<bool>(false), 
                        new String<bool>(false, true, false));        
    ReportCompare<bool>(new String<bool>(true, true, false), 
                        new String<bool>(true, true, false));    
  }

  public static void ReportCompare<T>(String<T> s, String<T> t)
    where T: IComparable<T>{
    Console.WriteLine("Result of comparing {0} and {1}: {2}", 
                      s, t, s.CompareTo(t));
  }   

}

Reference

Program: A generic bubble sort program. 
using System;

class SortDemo{

  static void BubbleSort<T>(T[] a) where T: IComparable<T>{
   int n = a.Length;
   for (int i = 0; i < n - 1; ++i)
     for (int j = n - 1; j > i; --j)
       if (a[j-1].CompareTo(a[j]) > 0)
          Swap(ref a[j-1], ref a[j]);
  }

  public static void Swap<T>(ref T a, ref T b){
    T temp;
    temp = a; a = b; b = temp;
  }

  public static void ReportArray<T>(T[] a){
    foreach(T t in a) Console.Write("{0,4}", t);
    Console.WriteLine();  
  }

  public static void Main(){
    double[] da = new double[]{5.7, 3.0, 6.9, -5,3, 0.3};

    Die[] dia = new Die[]{new Die(), new Die(),  new Die(), 
                          new Die(),  new Die(),  new Die()};

    ReportArray(da); BubbleSort(da); ReportArray(da);
    Console.WriteLine();
    ReportArray(dia); BubbleSort(dia); ReportArray(dia);
    Console.WriteLine();

    // Equivalent:
    ReportArray(da); BubbleSort<double>(da); ReportArray(da);
    Console.WriteLine();
    ReportArray(dia); BubbleSort<Die>(dia); ReportArray(dia);
  }

}

Program: Output from the generic bubble sort program. 
 5,7   3 6,9  -5   3 0,3
  -5 0,3   3   3 5,7 6,9

 [4] [3] [1] [1] [5] [2]
 [1] [1] [2] [3] [4] [5]

  -5 0,3   3   3 5,7 6,9
  -5 0,3   3   3 5,7 6,9

 [1] [1] [2] [3] [4] [5]
 [1] [1] [2] [3] [4] [5]

Generic Delegates
Slide Annotated slide Contents Index
References Textbook 

Reference

Program: Generic reprogramming of the program that composes functions. 
using System;

public class CompositionDemo {

  // A function from S to T
  public delegate T Function <S,T>(S d);

  // The generic function for function composition
  // g: T -> U
  // f: U -> S
  // f o g: T -> S
  public static Function<T,S> Compose<T,U,S>    // T to S via U
                   (Function<U,S> f, Function<T,U> g){
    return delegate(T d){return f(g(d));};
  }   

  // A generic PrintTable function
  // f: S -> T
  public static void PrintTableOfFunction<S,T>
                   (Function<S,T> f, string fname, 
                    S[] inputValues){
    foreach(S s in inputValues)
      Console.WriteLine("{0,35}({1,-4:F3}) = {2}", fname, s, f(s));

    Console.WriteLine();
  }   

  public static double Square(double d){
    return d*d;
  }

  public static double Cubic(double d){
    return d*d*d;
  }

  public static double Minus3(double d){
    return d-3;
  }

  public static void Main(){
    PrintTableOfFunction(Compose<double,double,double>(Cubic, Minus3) , 
                         "Cubic of Minus3", 
                         new double[]{0.0, 0.5, 1.0, 1.5, 2.0});

    PrintTableOfFunction(
      Compose<double,double,double>(
            Square, 
            delegate(double d){
              return d > 2 ? -d : 0;}) ,
            "Square of if d>2 then -d else 0", 
            new double[]{0.0, 0.5, 1.0, 1.5, 2.0, 2.5, 3.0});
   }

}

Program: Output from the Generic reprogramming of the program that composes functions. 
                    Cubic of Minus3(0,000) = -27
                    Cubic of Minus3(0,500) = -15,625
                    Cubic of Minus3(1,000) = -8
                    Cubic of Minus3(1,500) = -3,375
                    Cubic of Minus3(2,000) = -1

    Square of if d>2 then -d else 0(0,000) = 0
    Square of if d>2 then -d else 0(0,500) = 0
    Square of if d>2 then -d else 0(1,000) = 0
    Square of if d>2 then -d else 0(1,500) = 0
    Square of if d>2 then -d else 0(2,000) = 0
    Square of if d>2 then -d else 0(2,500) = 6,25
    Square of if d>2 then -d else 0(3,000) = 9

Program: An example that involves other types than double. 
using System;

public class CompositionDemo {

  // A function from S to T
  public delegate T Function <S,T>(S d);

  // The generic function for function composition
  // from T to S via U
  public static Function<T,S> Compose<T,U,S>
                   (Function<U,S> f, Function<T,U> g){
    return delegate(T d){return f(g(d));};
  }   

  // A generic PrintTable function
  public static void PrintTableOfFunction<S,T>
                   (Function<S,T> f, string fname, 
                    S[] inputValues){
    foreach(S s in inputValues)
      Console.WriteLine("{0,35}({1,-4:F3}) = {2}", fname, s, f(s));

    Console.WriteLine();
  }   

  // DieFromInt: int -> Die
  public static Die DieFromInt(int i){
    return new Die(i);
  }

  // Round: double -> int
  public static int Round(double d){
    return (int)(Math.Round(d));
  }

  public static void Main(){
    double[] input = new double[25];
    for(int i = 0; i < 25; i++)
      input[i] = (double) (i*2);

    // Compose(DieFromInt, Round): double -> Die 
    // (via int) 

    PrintTableOfFunction(Compose<double,int,Die>(DieFromInt, Round), 
                         "Die of double", 
                         input);
  }

}

Program: Output from the example that involves the types double, int, and Die. 
                      Die of double(0,000) = Die[0]:1
                      Die of double(2,000) = Die[2]:2
                      Die of double(4,000) = Die[4]:4
                      Die of double(6,000) = Die[6]:6
                      Die of double(8,000) = Die[8]:5
                      Die of double(10,000) = Die[10]:8
                      Die of double(12,000) = Die[12]:2
                      Die of double(14,000) = Die[14]:4
                      Die of double(16,000) = Die[16]:10
                      Die of double(18,000) = Die[18]:9
                      Die of double(20,000) = Die[20]:20
                      Die of double(22,000) = Die[22]:16
                      Die of double(24,000) = Die[24]:9
                      Die of double(26,000) = Die[26]:18
                      Die of double(28,000) = Die[28]:10
                      Die of double(30,000) = Die[30]:16
                      Die of double(32,000) = Die[32]:15
                      Die of double(34,000) = Die[34]:27
                      Die of double(36,000) = Die[36]:17
                      Die of double(38,000) = Die[38]:10
                      Die of double(40,000) = Die[40]:13
                      Die of double(42,000) = Die[42]:24
                      Die of double(44,000) = Die[44]:3
                      Die of double(46,000) = Die[46]:21
                      Die of double(48,000) = Die[48]:37

Predefined generic delegates
Slide Annotated slide Contents Index
References 

The System namespace contains a set of generic Func and Action delegates that cover the signature of most functions

Program: A reproduction of the generic Action and Function delegate types. 
// From MSDN:
namespace System
{
    public delegate void Action();
    public delegate void Action<T>(T obj); 
    public delegate void Action<T1,T2>(T1 arg1, T2 arg2);
    public delegate void Action<T1,T2,T3>(T1 arg1, T2 arg2, T3 arg3);
    public delegate void Action<T1,T2,T3,T4>
                                 (T1 arg1, T2 arg2, T3 arg3, T4 arg4);

    public delegate TResult Func<TResult>();
    public delegate TResult Func<T, TResult>(T arg);
    public delegate TResult Func<T1, T2, TResult>(T1 arg1, T2 arg2);
    public delegate TResult Func<T1, T2, T3, TResult>
                                 (T1 arg1, T2 arg2, T3 arg3);
    public delegate TResult Func<T1, T2, T3, T4, TResult>
                                 (T1 arg1, T2 arg2, T3 arg3, T4 arg4);
}

Generic types and methods - Pros and Cons
Slide Annotated slide Contents Index
References Textbook 

What are the advantages and disadvantages of generic types?

  • Advantages

    • Readability and Documentation

      • More precise indication of types.

      • Less downcasting from class Object

    • Type Checking

      • Better and more precise typechecking

    • Efficiency

      • There is a potential for more efficient programs

      • Less casting - fewer boxings

  • Disadvantages

    • Complexity

      • Yet another abstraction and parametrization-level on top of the existing

Collected references
Contents Index
Downcasting
The generic interface IComparable<T> Later in these notes
Covariance and Contravariance - parameters Earlier in these notes
Nullable types Earlier in these notes
Class Set<T> Earlier in these notes
Class IntSet Earlier in these notes
Class String<T> Earlier in these notes
Delegates Earlier in these notes

 

Chapter 11: Generic Types and Methods
Course home     Author home     About producing this web     Previous lecture (top)     Next lecture (top)     Previous lecture (bund)     Next lecture (bund)     
Generated: February 7, 2011, 12:20:20