Theme index -- Keyboard shortcut: 'u'  Previous theme in this lecture -- Keyboard shortcut: 'p'  Next slide in this lecture -- Keyboard shortcut: 'n'Generic Types and Methods

A complete PDF version of the text book is now available. The PDF version is an almost complete subset of the HTML version (where only a few, long program listings have been removed). See here.

41.  Motivation for Generic Types

This chapter starts the lecture about generics: Generic types and generic methods. With generics we are aiming at more general types (classes, structs, interfaces, etc). The measure that we will bring into use is type parametrization.

This chapter is intended as motivation. Type parameterized types will be the topic of Chapter 42 and type parameterized methods will be treated in Chapter 43.

41.1 Operations on sets41.3 The class ObjectSet
41.2 The classes IntSet and StringSet41.4 Problems
 

41.1.  Operations on sets
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

In this chapter we decide to develop and use the class Set. We use the class Set as a motivating example. It is our goal, once and for all, to be able to write a class Set that supports all possible types of elements. It is the intention that the class Set can be used in any future program, in which there is a need for sets.

It is noteworthy that .NET has not supported a mathematical set class until version 3.5. As of version 3.5, the class HashSet<T> supports sets, see also Section 45.1. Thus, at the time of writing this material, there was no set class available in the .NET Framework.

From a mathematical perspective, a set is an unordered collection of items without duplicates. The class Set represents a mathematical set of items. We equip class Set with the following well-known 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 set operations Intersection, Union, and Diff are handled in Exercise 11.1.

 

41.2.  The classes IntSet and StringSet
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

Let us imagine that we first encounter a need for sets of integers. This causes us (maybe somewhat narrow-minded) to write a class called IntSet. Our version of class IntSet is shown in Program 41.1. The version provided in the paper version of the material is abbreviated to save some space. The version in the web version is complete with all details.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

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 41.1    The class IntSet.

The class IntSet is an example of an everyday implementation of integer sets. We have not attempted to come up with a clever representation that allows for fast set operations. The IntSet class is good enough for small sets. If you are going to work on sets with many elements, you should use a set class of better quality.

We chose to represent the elements in an integer array. We keep track of the position where to insert the next element (by use of the instance variable next). If there is not enough room in the array, we use the Array.Resize operation to make it larger. We delete elements from the set by shifting elements in the array 'to the left', in order to avoid wasted space. This approach is fairly expensive, but it is good enough for our purposes. The IntSet class is equipped with a GetEnumerator method, which returns an iterator. (We encountered iterators (enumerators) in the Interval class studied in Section 21.3. See also Section 31.6 for details on iterators. The GetEnumerator details are not shown in the paper version). The enumerator allows for traversal of all elements of the set with a foreach control structure.

A set is only, in a minimal sense, dependent on the types of elements (in our case, the type int). It does not even matter if the type of elements is a value type or a reference type (see Section 14.1 and Section 13.1 respectively). We do, however, apply equality on the elements, via use of the Equals method. Nevertheless, the type int occurs many times in the class definition of IntSet. We have emphasized occurrences of int with color marks in Program 41.1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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 41.2    A client of IntSet.

In Program 41.2 we see a sample application of class IntSet. We establish two empty integer sets s1 and s2, we insert some numbers into these, and we try out some of the set operations on them. The comment lines 20-23 make use of set operations which will be implemented in Exercise 11.1. The output of Program 41.2 confirms that s2 is a subset of s1. The program output is shown in Listing 41.3 (only on web).

1
2
3
4

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

We will now assume that we, a couple of days after we have programmed class IntSet, realize a need of class StringSet. Too bad! Class StringSet is almost like IntSet. But instead of occurrences of int we have occurrences of string.

We know how bad it is to copy the source text of IntSet to a new file called StringSet, and to globally replace 'int' with 'string'. When we need to modify the set class, all our modifications will have do be done twice!

For illustrative purposes - and despite the observation just described - we have made the class StringSet, see Program 41.4 (only on web). We have also replicated the client program, in Program 41.5 (only on web) and the program output in Listing 41.6 (only on web).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

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 41.4    The class StringSet. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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 41.5    A client of StringSet. 

1
2
3
4

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

 

41.3.  The class ObjectSet
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

In Section 41.2 we learned the following lesson:

There is an endless number of TypeSet classes. One for each Type. Each of them is similar to the others.

We will now review the solution to the problem which was used in Java before version 1.5, and in C# before version 2. These are the versions of the two languages prior to the introduction of generics.

The idea is simple: We implement a set class of element type Object. We call it ObjectSet. The type Object is the most general type in the type system (see Section 28.2). All other types inherit from the class Object.

Below, in Program 41.7 we show the class ObjectSet. In the paper version, only an outline with a few constructors and methods is included. The web version shows the full definition of class ObjectSet.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

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 41.7    The class ObjectSet.

We can now write programs with a set of Die, a set of BankAccount, a set of int, etc. In Program 41.8 (only on web) we show a program, similar to Program 41.2, which illustrates sets of Die objects. (The class Die can be found in Section 10.1).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

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 41.8    A client of ObjectSet - working with sets of Die objects. 

1
2
3
4

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
Listing 41.9    Output from the ObjectSet client program.

The main problem with class ObjectSet is illustrated below in Program 41.10. In line 12-20 we make a set of dice (s1), a set of integers (s2), a set of strings (s3), and set of mixed objects (s4). Let us focus on s1. If we take a die out of s1 with the purpose of using a Die operation on it, we need to typecase the element to a Die. This is shown in line 23. From the compiler's point of view, all elements in the set s1 are instances of class Object. With the cast (Die)o in line 23, we guarantee that each element in the set is a Die. (If an integer or a playing card should sneak into the set, an exception will be thrown). - The output of the program is shown in Listing 41.11 (only on web).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

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 41.10    A client of ObjectSet - working with set of different types. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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
--------------
Listing 41.11    Output from the the client of ObjectSet - the version that works with sets of different types.

 

41.4.  Problems
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

The classes 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"

Generic types, to be introduced in the following chapter, offer a type safe alternative to ObjectSet, in which we are able to avoid type casting.

Generated: Monday February 7, 2011, 12:20:55
Theme index -- Keyboard shortcut: 'u'  Previous theme in this lecture -- Keyboard shortcut: 'p'  Next slide in this lecture -- Keyboard shortcut: 'n'