Generic Classes

The concept of a data structure (e.g., a stack), that contains data elements can be understood independently of the element type it manipulates. A generic class provides a means for describing a class in a type-independent manner. We can then instantiate type-specific objects of the generic class. This capability is an opportunity for software reusability.

Once you have a generic class, you can use a simple, concise notation to indicate the actual type(s) that should be used in place of the class's type parameter(s). At compilation time, the compiler ensures the type safety of your code, and the runtime system replaces type parameters with actual arguments to enable your client code to interact with the generic class.

One generic Stack class, for example, could be the basis for creating many Stack classes (e.g., "Stack of double," "Stack of int," "Stack of char," "Stack of Employee"). Figure 26.5 presents a generic Stack class declaration. A generic class declaration is similar to a non-generic class declaration, except that the class name is followed by a type parameter list (line 5) and, in this case, a constraint on its type parameter (which we will discuss shortly). Type parameter E represents the element type the Stack will manipulate. As with generic methods, the type parameter list of a generic class can have one or more type parameters separated by commas. (You will create a generic class with two type parameters in Exercise 26.11.) Type parameter E is used throughout the Stack class declaration (Fig. 26.5) to represent the element type. Class Stack declares variable elements as an array of type E (line 8). This array (created at line 20 or 22) will store the Stack's elements. [Note: This example implements a Stack as an array. As you have seen in Chapter 25, Data Structures, Stacks also are commonly implemented as linked lists.]

Figure 26.5. Generic class Stack declaration.

 1 // Fig. 26.5: Stack.cs
 2 // Generic class Stack
 3 using System;
 4
 5 class Stack< E >
 6 {
 7 private int top; // location of the top element
 8 private E[] elements; // array that stores Stack elements
 9
10 // parameterless constructor creates a Stack of the default size
11 public Stack() : this( 10 ) // default stack size
12 {
13 // empty constructor; calls constructor at line 17 to perform init
14 } // end Stack constructor
15
16 // constructor creates a Stack of the specified number of elements
17 public Stack( int stackSize )
18 {
19 if ( stackSize > 0 ) // validate stackSize
20 elements = new E[ stackSize ]; // create stackSize elements
21 else
22 elements = new E[ 10 ]; // create 10 elements
23

24 top = -1; // Stack initially empty 25 } // end Stack constructor 26 27 // push element onto the Stack; if successful, return true 28 // otherwise, throw FullStackException 29 public void Push( E pushValue ) 30 { 31 if ( top == elements.Length - 1 ) // Stack is full 32 throw new FullStackException( String.Format( 33 "Stack is full, cannot push {0}", pushValue ) ); 34 35 top++; // increment top 36 elements[ top ] = pushValue; // place pushValue on Stack 37 } // end method Push 38 39 // return the top element if not empty 40 // else throw EmptyStackException 41 public E Pop() 42 { 43 if ( top == -1 ) // Stack is empty 44 throw new EmptyStackException( "Stack is empty, cannot pop" ); 45 46 top--; // decrement top 47 return elements[ top + 1 ]; // return top value 48 } // end method Pop 49 } // end class Stack

Class Stack has two constructors. The parameterless constructor (lines 1114) passes the default stack size (10) to the one-argument constructor, using the syntax this (line 11) to invoke another constructor in the same class. The one-argument constructor (lines 1725) validates the stackSize argument and creates an array of the specified stackSize (if it is greater than 0) or an array of 10 elements, otherwise.

Method Push (lines 2937) first determines whether an attempt is being made to push an element onto a full Stack. If so, lines 3233 throw a FullStackException (declared in Fig. 26.6). If the Stack is not full, line 35 increments the top counter to indicate the new top position, and line 36 places the argument in that location of array elements.

Figure 26.6. FullStackException class declaration.

(This item is displayed on page 1379 in the print version)

 1 // Fig. 26.6: FullStackException.cs
 2 // Indicates a stack is full.
 3 using System;
 4
 5 class FullStackException : ApplicationException
 6 {
 7 // parameterless constructor
 8 public FullStackException() : base( "Stack is full" )
 9 {
10 // empty constructor
11 } // end FullStackException constructor
12
13 // one-parameter constructor
14 public FullStackException( string exception ) : base( exception )
15 {
16 // empty constructor
17 } // end FullStackException constructor
18 } // end class FullStackException

Method Pop (lines 4148) first determines whether an attempt is being made to pop an element from an empty Stack. If so, line 44 throws an EmptyStackException (declared in Fig. 26.7). Otherwise, line 46 decrements the top counter to indicate the new top position, and line 47 returns the original top element of the Stack.

Figure 26.7. EmptyStackException class declaration.

(This item is displayed on page 1379 in the print version)

 1 // Fig. 26.7: EmptyStackException.cs
 2 // Indicates a stack is empty
 3 using System;
 4
 5 class EmptyStackException : ApplicationException
 6 {
 7 // parameterless constructor
 8 public EmptyStackException() : base( "Stack is empty" )
 9 {
10 // empty constructor
11 } // end EmptyStackException constructor
12
13 // one-parameter constructor
14 public EmptyStackException( string exception ) : base( exception )
15 {
16 // empty constructor
17 } // end EmptyStackException constructor
18 } // end class EmptyStackException

Classes FullStackException (Fig. 26.6) and EmptyStackException (Fig. 26.7) each provide a parameterless constructor and a one-argument constructor of exception classes (as discussed in Section 12.8). The parameterless constructor sets the default error message, and the one-argument constructor sets a custom error message.

As with generic methods, when a generic class is compiled, the compiler performs type checking on the class's type parameters to ensure that they can be used with the code in the generic class. The constraints determine the operations that can be performed on the type parameters. The runtime system replaces the type parameters with the actual types at runtime. For class Stack (Fig. 26.5), no type constraint is specified, so the default type constraint, object, is used. The scope of a generic class's type parameter is the entire class.

Now, let's consider an application (Fig. 26.8) that uses the Stack generic class. Lines 1314 declare variables of type Stack< double > (pronounced "Stack of double") and Stack< int > (pronounced "Stack of int"). The types double and int are the Stack's type arguments. The compiler replaces the type parameters in the generic class so that the compiler can perform type checking. Method Main instantiates objects doubleStack of size 5 (line 18) and intStack of size 10 (line 19), then calls methods TestPushDouble (lines 2848), TestPopDouble (lines 5173), TestPushInt (lines 7696) and TestPopInt (lines 99121) to manipulate the two Stacks in this example.

Figure 26.8. Generic class Stack test program.

 1 // Fig. 26.8: StackTest.cs
 2 // Stack generic class test program.
 3 using System;
 4
 5 class StackTest
 6 {
 7 // create arrays of doubles and ints
 8 static double[] doubleElements =
 9 new double[]{ 1.1, 2.2, 3.3, 4.4, 5.5, 6.6 };
10 static int[] intElements =
11 new int[]{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
12
13 static Stack< double > doubleStack; // stack stores double objects
14 static Stack< int > intStack; // stack stores int objects 
15
16 static void Main( string[] args )
17 {
18 doubleStack = new Stack< double >( 5 ); // Stack of doubles
19 intStack = new Stack< int >( 10 ); // Stack of ints
20
21 TestPushDouble(); // push doubles onto doubleStack
22 TestPopDouble(); // pop doubles from doubleStack
23 TestPushInt(); // push ints onto intStack
24 TestPopInt(); // pop ints from intStack
25 } // end Main
26
27 // test Push method with doubleStack
28 static void TestPushDouble()
29 {
30 // push elements onto stack
31 try
32 {
33 Console.WriteLine( "
Pushing elements onto doubleStack" );
34
35 // push elements onto stack
36 foreach ( double element in doubleElements )
37 {
38 Console.Write( "{0:F1} ", element );
39 doubleStack.Push( element ); // push onto doubleStack
40 } // end foreach
41 } // end try
42 catch ( FullStackException exception )
43 {
44 Console.Error.WriteLine();
45 Console.Error.WriteLine( "Message: " + exception.Message );
46 Console.Error.WriteLine( exception.StackTrace );
47 } // end catch
48 } // end method TestPushDouble
49
50 // test Pop method with doubleStack
51 static void TestPopDouble()
52 {

53 // pop elements from stack 54 try 55 { 56 Console.WriteLine( " Popping elements from doubleStack" ); 57 58 double popValue; // store element removed from stack 59 60 // remove all elements from Stack 61 while ( true ) 62 { 63 popValue = doubleStack.Pop(); // pop from doubleStack 64 Console.Write( "{0:F1} ", popValue ); 65 } // end while 66 } // end try 67 catch ( EmptyStackException exception ) 68 { 69 Console.Error.WriteLine(); 70 Console.Error.WriteLine( "Message: " + exception.Message ); 71 Console.Error.WriteLine( exception.StackTrace ); 72 } // end catch 73 } // end method TestPopDouble 74 75 // test Push method with intStack 76 static void TestPushInt() 77 { 78 // push elements onto stack 79 try 80 { 81 Console.WriteLine( " Pushing elements onto intStack" ); 82 83 // push elements onto stack 84 foreach ( int element in intElements ) 85 { 86 Console.Write( "{0} ", element ); 87 intStack.Push( element ); // push onto intStack 88 } // end foreach 89 } // end try 90 catch ( FullStackException exception ) 91 { 92 Console.Error.WriteLine(); 93 Console.Error.WriteLine( "Message: " + exception.Message ); 94 Console.Error.WriteLine( exception.StackTrace ); 95 } // end catch 96 } // end method TestPushInt 97 98 // test Pop method with intStack 99 static void TestPopInt() 100 { 101 // pop elements from stack 102 try 103 { 104 Console.WriteLine( " Popping elements from intStack" ); 105 106 int popValue; // store element removed from stack 107 108 // remove all elements from Stack 109 while ( true ) 110 { 111 popValue = intStack.Pop(); // pop from intStack 112 Console.Write( "{0} ", popValue ); 113 } // end while 114 } // end try 115 catch ( EmptyStackException exception ) 116 { 117 Console.Error.WriteLine(); 118 Console.Error.WriteLine( "Message: " + exception.Message ); 119 Console.Error.WriteLine( exception.StackTrace ); 120 } // end catch 121 } // end method TestPopInt 122 } // end class StackTest

Pushing elements onto doubleStack
1.1 2.2 3.3 4.4 5.5 6.6
Message: Stack is full, cannot push 6.6
 at Stack`1.Push(E pushValue) in
 C:Examplesch25Fig25_05StackStack.cs:line 32
 at StackTest.TestPushDouble() in
 C:Examplesch25Fig25_05StackStackTest.cs:line 39

Popping elements from doubleStack
5.5 4.4 3.3 2.2 1.1
Message: Stack is empty, cannot pop
 at Stack`1.Pop() in C:Examplesch25Fig25_05StackStack.cs:line 44
 at StackTest.TestPopDouble() in
 C:Examplesch25Fig25_05StackStackTest.cs:line 63

Pushing elements onto intStack
1 2 3 4 5 6 7 8 9 10 11
Message: Stack is full, cannot push 11
 at Stack`1.Push(E pushValue) in
 C:Examplesch25Fig25_05StackStack.cs:line 32
 at StackTest.TestPushInt() in
 C:Examplesch25Fig25_05StackStackTest.cs:line 87

Popping elements from intStack
10 9 8 7 6 5 4 3 2 1
Message: Stack is empty, cannot pop
 at Stack`1.Pop() in C:Examplesch25Fig25_05StackStack.cs:line 44
 at StackTest.TestPopInt() in
 C:Examplesch25Fig25_05StackStackTest.cs:line 111

Method TestPushDouble (lines 2848) invokes method Push to place the double values 1.1, 2.2, 3.3, 4.4 and 5.5 stored in array doubleElements onto doubleStack. The for statement terminates when the test program attempts to Push a sixth value onto doubleStack (which is full, because doubleStack can store only five elements). In this case, the method throws a FullStackException (Fig. 26.6) to indicate that the Stack is full. Lines 4247 catch this exception, and print the message and stack trace information. The stack trace indicates the exception that occurred and shows that Stack method Push generated the exception at lines 3435 of the file Stack.cs (Fig. 26.5). The trace also shows that method Push was called by StackTest method TestPushDouble at line 39 of StackTest.cs. This information enables you to determine the methods that were on the method call stack at the time that the exception occurred. Because the program catches the exception, the C# runtime environment considers the exception to have been handled, and the program can continue executing.

Method TestPopDouble (lines 5173) invokes Stack method Pop in an infinite while loop to remove all the values from the stack. Note in the output that the values are popped off in last-in-first-out orderthis, of course, is the defining characteristic of stacks. The while loop (lines 6165) continues until the stack is empty. An EmptyStackException occurs when an attempt is made to pop from the empty stack. This causes the program to proceed to the catch block (lines 6772) and handle the exception, so the program can continue executing. When the test program attempts to Pop a sixth value, the doubleStack is empty, so method Pop tHRows an EmptyStackException.

Method TestPushInt (lines 7696) invokes Stack method Push to place values onto intStack until it is full. Method TestPopInt (lines 99121) invokes Stack method Pop to remove values from intStack until it is empty. Once again, note that the values pop off in last-in-first-out order.

Creating Generic Methods to Test Class Stack< E >

Note that the code in methods TestPushDouble and TestPushInt is almost identical for pushing values onto a Stack< double > or a Stack< int >, respectively. Similarly the code in methods TestPopDouble and TestPopInt is almost identical for popping values from a Stack< double > or a Stack< int >, respectively. This presents another opportunity to use generic methods. Figure 26.9 declares generic method TestPush (lines 3253) to perform the same tasks as TestPushDouble and TestPushInt in Fig. 26.8that is, Push values onto a Stack< E >. Similarly, generic method TestPop (lines 5577) performs the same tasks as TestPopDouble and TestPopInt in Fig. 26.8that is, Pop values off a Stack< E >. Note that the output of Fig. 26.9 precisely matches the output of Fig. 26.8.

Figure 26.9. Passing a generic type Stack to a generic method.

 1 // Fig 26.9: StackTest.cs
 2 // Stack generic class test program.
 3 using System;
 4 using System.Collections.Generic;
 5
 6 class StackTest
 7 {
 8 // create arrays of doubles and ints
 9 static double[] doubleElements =
10 new double[]{ 1.1, 2.2, 3.3, 4.4, 5.5, 6.6 };
11 static int[] intElements =
12 new int[]{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };

13 14 static Stack< double >doubleStack; // stack stores double objects 15 static Stack< int >intStack; // stack stores int objects 16 17 static void Main( string[] args ) 18 { 19 doubleStack = new Stack< double >( 5 ); // Stack of doubles 20 intStack = new Stack< int >( 10 ); // Stack of ints 21 22 // push doubles onto doubleStack 23 TestPush( "doubleStack", doubleStack, doubleElements ); 24 // pop doubles from doubleStack 25 TestPop( "doubleStack", doubleStack ); 26 // push ints onto intStack 27 TestPush( "intStack", intStack, intElements ); 28 // pop ints from intStack 29 TestPop( "intStack", intStack ); 30 } // end Main 31 32 static void TestPush< E >( string name, Stack< E > stack, 33 IEnumerable< E > elements ) 34 { 35 // push elements onto stack 36 try 37 { 38 Console.WriteLine( " Pushing elements onto " + name ); 39 40 // push elements onto stack 41 foreach ( E element in elements ) 42 { 43 Console.Write( "{0} ", element ); 44 stack.Push( element ); // push onto stack 45 } // end foreach 46 } // end try 47 catch ( FullStackException exception ) 48 { 49 Console.Error.WriteLine(); 50 Console.Error.WriteLine( "Message: " + exception.Message ); 51 Console.Error.WriteLine( exception.StackTrace ); 52 } // end catch 53 } // end method TestPush 54 55 static void TestPop< E >( string name, Stack< E > stack ) 56 { 57 // push elements onto stack 58 try 59 { 60 Console.WriteLine( " Popping elements from " + name ); 61 62 E popValue; // store element removed from stack 63 64 // remove all elements from Stack 65 while ( true ) 66 { 67 popValue = stack.Pop(); // pop from stack 68 Console.Write( "{0} ", popValue ); 69 } // end while 70 } // end try 71 catch ( EmptyStackException exception ) 72 { 73 Console.Error.WriteLine(); 74 Console.Error.WriteLine( "Message: " + exception.Message ); 75 Console.Error.WriteLine( exception.StackTrace ); 76 } // end catch 77 } // end TestPop 78 } // end class StackTest

Pushing elements onto doubleStack
1.1 2.2 3.3 4.4 5.5 6.6
Message: Stack is full, cannot push 6.6
 at Stack`1.Push(E pushValue) in
 C:Examplesch25Fig25_05StackStack.cs:line 35
 at StackTest.TestPush[E](String name, Stack`1 stack, IEnumerable`1
 elements) in C:Examplesch25Fig25_05StackStackTest.cs:line 44

Popping elements from doubleStack
5.5 4.4 3.3 2.2 1.1
Message: Stack is empty, cannot pop
 at Stack`1.Pop() in C:Examplesch25Fig25_05StackStack.cs:line 49
 at StackTest.TestPop[E](String name, Stack`1 stack) in
 C:Examplesch25Fig25_05StackStackTest.cs:line 67

Pushing elements onto intStack
1 2 3 4 5 6 7 8 9 10 11
Message: Stack is full, cannot push 11
 at Stack`1.Push(E pushValue) in
 C:Examplesch25Fig25_05StackStack.cs:line 35
 at StackTest.TestPush[E](String name, Stack`1 stack, IEnumerable`1
 elements) in C:Examplesch25Fig25_05StackStackTest.cs:line 44

Popping elements from intStack
10 9 8 7 6 5 4 3 2 1
Message: Stack is empty, cannot pop
 at Stack`1.Pop() in C:Examplesch25Fig25_05StackStack.cs:line 49
 at StackTest.TestPop[E](String name, Stack`1 stack) in
 C:Examplesch25Fig25_05StackStackTest.cs:line 67

Method Main (lines 1730) creates the Stack< double > (line 19) and Stack< int > (line 20) objects. Lines 2329 invoke generic methods TestPush and TestPop to test the Stack objects.

Generic method TestPush (lines 3253) uses type parameter E (specified at line 32) to represent the data type stored in the Stack. The generic method takes three argumentsa string that represents the name of the Stack object for output purposes, an object of type Stack< E > and an IEnumerable< E >the type of elements that will be Pushed onto Stack< E >. Note that the compiler enforces consistency between the type of the Stack and the elements that will be pushed onto the Stack when Push is invoked, which is the type argument of the generic method call. Generic method TestPop (lines 5577) takes two argumentsa string that represents the name of the Stack object for output purposes and an object of type Stack< E >. Notice that the type parameter E used in both TestPush and TestPop methods has a new constraint, because both methods take an object of type Stack< E > and the type parameter in the Stack generic class declaration has a new constraint (line 5 in Fig. 26.5). This ensures that the objects that TestPush and TestPop manipulate can be used with generic Stack class, which requires objects stored in the Stack to have a default or parameterless public constructor.