Exercise index of this lecture   Alphabetic index   Course home   

Exercises and solutions
Generic Types and Methods

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

Solution

The three requested methods Intersection, Union, and Diff appear in the middle of the following version of the generic class set<T>:

using System;
using System.Collections.Generic;
using System.Collections;

public class Set<T> {
 
  /* Invariant: At most one occurrence of an element in the array store 
     Consequtive storing from low end.
  */

  private int capacity;
  private static int DefaultCapacity = 3;
  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 Set<T> Intersection(Set<T> other){
    Set<T> res = new Set<T>(this.Count);
    foreach(T e in this)
      if (other.Member(e))
          res.Insert(e);
    return res;
  }

  public Set<T> Union(Set<T> other){
    Set<T> res = new Set<T>(this.Count + other.Count);
    foreach(T e in this) res.Insert(e);
    foreach(T e in other) res.Insert(e);
    return res;
  }

  // Subtract other elements from this set.
  public Set<T> Diff(Set<T> other){
    Set<T> res = new Set<T>(this);
    foreach(T e in other) res.Delete(e);
    return res;
  }

  public override string ToString(){
    string elRes = "";
    for(int idx = 0; idx < next; idx++) 
      if (store[idx] != null)
        elRes += " " + store[idx];
    return "{" + elRes + " "+ "}" + this.Count;
  }
  
  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(){
    }

  }    
    
  public IEnumerator<T> GetEnumerator (){
    return new SetEnumerator(this);
  }

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

}

11.2   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>

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

Solution

Here is the class Pair<S,T>:

using System;

public class Pair<T,S>{
  private T first;
  private S second;

  public Pair(T first, S second){
    this.first = first; this.second = second;
  }

  public T First{
     get {return first;}
  }

  public S Second{
     get {return second;}
  }
  
}

11.4   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!

Solution

The solution rely on the generic class Pair<T,S> from an earlier exercise. To be as complete as possible, we first show Pair<T,S>:

using System;

public class Pair<S,T>{
  private S first;
  private T second;

  public Pair(S first, T second){
    this.first = first; this.second = second;
  }

  public S First{
     get {return first;}
  }

  public T Second{
     get {return second;}
  }
  
}

ComparablePair<T,U> is here:

using System;

public class ComparablePair<T,U>: Pair<T,U>, IComparable<ComparablePair<T,U>> 
  where T: IComparable<T>
  where U: IComparable<U> {

  public ComparablePair(T first, U second): base(first, second){
  }

  public int CompareTo(ComparablePair<T,U> other){
    int firstCompare = this.First.CompareTo(other.First);
    if (firstCompare != 0)
       return firstCompare;
    else 
       return this.Second.CompareTo(other.Second);
  }

}

Finally we show a client of ComparablePair<T,U>:

using System;

class App{

  public static void Main(){

    ComparablePair<int, bool> cp1 = new ComparablePair<int, bool>(4, false),
                              cp2 = new ComparablePair<int, bool>(4, true);

    int res = cp1.CompareTo(cp2);

    Console.WriteLine("Result of comparison: {0}", res);

  }

}

The program outputs:

Result of comparison: -1

The two First constituents are both 4, and thus equal to each other. The tow Second constituents are false and true, respectively. false is less than true (false.CompareTo(true) == -1), and therefore cp1.CompareTo(cp2) == -1.

This ends the solution to this exercise.

Generated: Monday February 7, 2011, 12:20:50