Beginning Object-Oriented Programming with C# (2012)
Part III
Writing Your Own Classes
Chapter 12
Generics
What you will learn in this chapter:
· Generics
· Advantages generics offer
· Boxing and unboxing
· Run time type checking
· Interfaces
· Recursion
wrox.com code downloads for this chapter
You can find the wrox.com code downloads for this chapter at www.wrox.com/remtitle.cgi?isbn=9781118336922 on the Download Code tab. The code in the Chapter12 folder is individually named according to the names throughout the chapter.
This chapter discusses generics, a feature that has been a part of C# since its 2005 release. Generics have the potential to save you a ton of programming effort.
Generics offer you a way to stretch your programming time in ways that just make sense. In this chapter you examine what this relatively new OOP feature has to offer.
What Are Generics?
The best way to appreciate what generics bring to the programming table is with an example. Sorting data is a common programming problem. I once was interviewed for a consulting job and part of the interview was a programming test in which I was expected to generate a series of random numbers, display them in a listbox, sort them into ascending order, and redisplay them in a second listbox. The interviewers weren't happy when I bypassed writing my own sort routine and simply turned on the Sorted property in the second listbox. Moral: Know your toolkit. But suppose you have to sort a series of integer data into ascending order and you can't use the listbox trick. How would you write the solution?
As part of your introduction to generics, in the following Try It Out you write a short program that sorts a list of data into ascending order. The example is then modified to show you how generics can make such tasks much easier.
Try It Out: Quicksort (Chapter12ProgramQuickSort.zip)
Although volumes have been written on sorting algorithms, one of the fastest general-purpose sorts is the Quicksort. The algorithm uses a divide-and-conquer approach to partitioning the data and then calls itself recursively to perform the sorting task. A sample run of the program is shown in Figure 12.1 and may be used to lay out the user interface.
Figure 12.1 User Interface
To try this program:
1. Create a new project in the normal manner.
2. Create a user interface that looks something like that shown in Figure 12.1.
3. Download the code from the file: Chapter12ProgramQuickSort.zip.
The listbox object on the left shows the “raw” data produced by the generation of 10 integer values using the pseudo-random number class (Random). After the user clicks the Sort button, that same list of numbers is sorted and then displayed in the second listbox object. (No, I didn't take the shortcut and simply set the Sorted property to true.)
How It Works
As usual, frmMain performs four of the Five Program Steps, leaving the Process step for the code found in clsSort. The code for frmMain is shown in Listing 12-1.
Listing 12-1: Program to Sort a List of Data. (frmMain.cs)
#define MYDEBUG
//#undef MYDEBUG
using System;
using System.Windows.Forms;
public class frmMain : Form
{
private const int MAXVAL = 1000; // Max random number to generate
private int[] data; // Data array to sort
private int number; // Number of elements in array
private TextBox txtNumber;
private Button btnGen;
private ListBox lstOutput;
private Button btnClose;
private Button btnSort;
private ListBox lstSorted;
private Label label1;
#region Windows code
public frmMain()
{
InitializeComponent();
}
public static void Main()
{
frmMain main = new frmMain();
Application.Run(main);
}
private void btnGen_Click(object sender, EventArgs e)
{
bool flag;
int i;
flag = int.TryParse(txtNumber.Text, out number);
if (flag == false)
{
MessageBox.Show("Enter whole digits only.", "Input Error");
txtNumber.Focus();
return;
}
#if MYDEBUG
Random rnd = new Random(number); // For testing purposes
#else
Random rnd = new Random();
#endif
data = new int[number];
lstOutput.Items.Clear(); // Clear listbox objects
lstSorted.Items.Clear();
for (i = 0; i < data.Length; i++) // Set random values
{
data[i] = rnd.Next(MAXVAL);
lstOutput.Items.Add(data[i].ToString());
}
}
private void btnSort_Click(object sender, EventArgs e)
{
int i;
clsSort mySort = new clsSort(data);
mySort.quickSort(0, data.Length-1); // Sort the data
for (i = 0; i < data.Length; i++) // Show it
{
lstSorted.Items.Add(data[i].ToString());
}
}
private void btnClose_Click(object sender, EventArgs e)
{
Close();
}
}
The listing takes advantage of the scaffold coding technique that was mentioned in Chapter 11. In particular, notice the lines at the top of the listing and the scaffolding that follows:
#define DEBUG
#undef DEBUG
// Omitted lines of code. . .
#if DEBUG
Random rnd = new Random(number); // For testing purposes
#else
Random rnd = new Random();
#endif
Because of the #undef preprocessor directive, the #if test later in the program is logic False, which means that the constructor for the Random class is called without an argument. This causes rnd to produce a differing set of pseudo-random numbers on each run of the program. (It's calledpseudo-random because the distribution of numbers only approximates a true random distribution of numbers.) When you develop the code, it is often useful to have a repeatable series of numbers produced so that you have a stable test dataset while debugging and testing. To establish that testing environment, simply comment out the #undef DEBUG line that toggles in the parameterized constructor for the Random class. When you finish testing, remove comment characters for the #undef, as shown in Listing 12-1.
The line
data[i] = rnd.Next(MAXVAL);
simply generates a series of random numbers that fall within the domain of 0 to MAXVAL, which is a symbolic constant set to a value of 1000. The set of random values is then added to the listbox object.
The following statements define a clsSort object named mySort and then call the quickSort() method to sort the data:
clsSort mySort = new clsSort(data);
mySort.quickSort(data.Length 1); // Sort the data
Notice that the constructor is passed the raw data as an argument. The code for clsSort is shown in Listing 12-2.
Listing 12-2: Code for clsSort (clsSort.cs)
using System;
using System.Collections.Generic;
using System.Text;
class clsSort
{
int[] data;
public clsSort(int[] vals)
{
data = vals; // Copies the rvalue
}
/*****
* Purpose: This method sorts an array of integers values into
* ascending order via recursive calls to quickSort().
*
* Parameter list:
* int first the first value to sort
* int last the last value to sort
*
* Return value:
* void
*****/
public void quickSort(int first, int last)
{
int start; // Index for left partition
int end; // Index for right partition
start = first; // Keep copy of first element of array…
end = last; // …and the last one.
if (last first >= 1) // Make sure there's enough data to sort
{
int pivot = data[first]; // Set partitions
while (end > start) // While indexes don't match…
{ // Do left partition
while (data[start] <= pivot && start <= last && end >
start)
start++;
// Do right partition
while (data[end] > pivot && end >= first && end >= start)
end--;
if (end > start) // If right partition index smaller…
swap(start, end); // …do a swap
}
swap(first, end); // Swap last element with pivot
quickSort(first, end 1); // Sort around partitions
quickSort(end + 1, last);
}
else
{
return;
}
}
/*****
* Purpose: This method performs the data swap for quickSort()
*
* Parameter list:
* int pos1 the array index to first value
* int pos2 the array index to second value
*
* Return value:
* void
*****/
public void swap(int pos1, int pos2)
{
int temp;
temp = data[pos1];
data[pos1] = data[pos2];
data[pos2] = temp;
}
}
There are several things to notice about the class. First, in the constructor, the following statement does a normal rvalue-to-rvalue assignment:
data = vals; // Copies the rvalue
However, if you recall, the rvalue of a reference variable is a memory address pointer to the memory location where the data resides, so the end result is that the variables data and vals now both refer to the same data. This also means, however, that the original sequence of random values will be lost after the data is sorted. If you need to preserve that sequence for some reason, you could define the data as an array of the same size and copy those values in the constructor's statement block:
public clsSort(int[] vals)
{
int[] data = new int[vals.Length];
Array.Copy(vals, data, vals.Length);
}
Recursion
The theory behind the Quicksort algorithm is to partition the set of numbers into two pieces around a pivot point in the data. The code looks at the data around the two partitions and calls a swap() method to exchange values to reorder the data. The code then calls the same quickSort () method from within itself. The process of a method calling itself is called recursion.
The good news about recursion is that you are, in effect, reducing the amount of code by reusing the same method call rather than by writing some form of loop to accomplish the same task. The bad news is that it's easy to get the code wrong, especially when determining that you've hit the last recursive call. Because a recursive method call creates a new set of local variables each time the method is called, a runaway recursion can eventually run out of memory and the program dies an ugly death. Also, because calling a method involves a certain amount of overhead each time the method is called (such as the overhead of pushing and popping data off the stack), recursion is often a little slower than a nonrecursive solution to the problem.
However, most Quicksort implementations use recursion so that's what's done here. You can see the two recursive calls toward the end of Listing 12-2. As mentioned earlier, the swap() method simply exchanges two values when the algorithm requires it.
Many sorting algorithms have performance factors dictated by big-O notation (for example, the notation O(N2)). This type of notation suggests that if the number of values to sort increases tenfold, it takes a hundred times longer to sort the data. The Quicksort, on the other hand, is bound by the relationship O(N * LogN) which can make the sort time almost linear. (That is, 10 times the data takes about 10 times as long.) A piece of trivia: Most programmers feel that the Bubble Sort is the slowest sorting algorithm on the planet. Actually, if the data is already in sorted order and a new item is added to the data set, the Bubble Sort can be one of the fastest algorithms to sort that new data set. (You can dazzle your friends at your next cocktail party when this topic comes up.) Conclusion: Few laws in programming are etched in stone.
Okay. Now you have a class that can sort data with good performance. You can save the code somewhere for later use. After all, one of the real benefits of OOP is code reuse, right? Well, it depends.
Data Problems
Fast-forward a few months: A client comes to you with a programming problem. Part of the solution requires that you sort the data prior to the final processing of the data. A few neurons fire and you remember the sorting code you wrote a while back. Cool! Time to drag out the clsSort code and integrate it into the solution. You read the rest of the client's specs for the program and….
Uh-oh.
The client's specs require sorting of the double data type, but your clsSort code works only with int data. Of course, you could rewrite the code, changing everything to use a double data type, but then you lose the ability to sort integer data. Or you could copy the code and have separate intand double sorting methods within the class. However, if you do that you have twice as much code to test, debug, and maintain. Wouldn't it be nice if one sorting method could be used to sort both types of data? This is exactly the type of problem that generics are designed to solve.
Introduction to Generics
Simply stated, generics enable you to create “typeless” data structures in C#. In the Quicksort example presented earlier, you defined an instance of the clsSort object with the following syntax:
clsSort mySort = new clsSort(data);
As you saw, the problem is that the algorithm is based upon using an int data type for the processing. With a generic class, the definition becomes:
clsSort<T> mySort = new clsSort<T>(data);
The data type you want to use is substituted for the term T within the enclosing angle brackets. For example, if you want to sort the int data values stored in the data array, you would use this code:
clsSort<int> mySort = new clsSort<int>(data);
In some later project that uses the double data type, you would use this code:
clsSort<double> mySort = new clsSort<double>(data);
One of the key advantages of generics is that the same code can process different data types without the source code being changed for each data type! If you write a class using the generic model, that class can process different data types without your having to craft methods for each data type. The Visual Studio compiler generates the necessary code to handle the different data types for you.
Generics Versus ArrayLists
You might be saying, “Wait a minute! Can't ArrayLists do the same thing? After all, they come with a Sort() method.” Well, not really. ArrayLists suffer from a few messy limitations. Consider the following code fragment:
ArrayList a = new ArrayList();
int i = 5;
a[0] = i;
a[1] = "t";
The preceding code compiles without complaint. So what's the problem? The problem is that it doesn't complain when it should. The good news about ArrayLists is that they are designed to hold anything. The bad news is that ArrayLists can hold anything. In the snippet you just saw, an integer is assigned into the ArrayList and that is followed with the assignment of a string literal into the same ArrayList.
Although sorting any data type in the array provides for a flexible means of storing things, it also means that no type checking is performed on the data. Further, how can you safely read back the data from the ArrayList? You give up the safety of data type checking with ArrayLists.
Now consider what happens if you add this statement for processing in the previously defined Arraylist:
i = a[0];
The compiler complains about this statement, saying:
Cannot implicitly convert type 'object' to 'int'. An explicit conversion exists
(are you missing a cast?)
The compiler removes the error message only if you change the statement to implement an explicit cast:
i = (int) a[0];
Casting everything from an ArrayList to its final destination type is tedious at best. Losing the benefits of data type checking is tantamount to writing code now that will produce a train wreck later. Finally, as mentioned in Chapter 8, there are some performance issues with the underlying way that ArrayLists work.
Boxing and Unboxing
Recall from Chapter 5 that C# surrounds all value types with object “wrappers” so that you can treat value types as though they were objects. Essentially, everything in C# derives from System.Object, and ArrayLists make use of this fact in performing their magic of allowing virtually any object to be stored in an ArrayList. However, anytime you use a value type as an object, C# must convert that value type into an object in a process called boxing. Likewise, the process to convert a boxed object back into its value type is called unboxing. It is this boxing/unboxing capability that enables you to use methods such as ToString() with a value type.
However, there is no such thing as a free lunch and the flexibility that wrappers bring to the party is paid for in performance. It has been estimated that there is approximately a 100 percent performance penalty associated with the boxing-unboxing process.
Generics overcome many of these limitations. Perhaps one of the greatest benefits of generics is that they provide strong type checking, yet enable you to avoid type casting every time you use a data item. To illustrate the use of generics, implement your Quicksort algorithm using them in the following “Try It Out.”
Try It Out: A Generic Quicksort (Chapter12ProgramGenericQuickSort.zip)
The user interface for your generic version of the sort program is shown in Figure 12.2. The program asks the user to specify the data type she wants to use, and a click of the Show Unsorted button shows the raw data that is generated. In this example, the program has generated 10 randomdouble data values. Clicking the Show Sorted button presents the same double data, but in sorted order. See Figure 12.2.
Figure 12.2 Generic Quicksort
If you select the String radio button, the program asks the user to enter a list of comma-separated strings in the textbox object. The string data is sorted using the same code used to sort the double data. A sample run for string data is shown in Figure 12.3.
Figure 12.3 Generic Sort on Strings
Using Figure 12.2 as a model for the user interface:
1. Create a new project in the usual manner.
2. Fill in the source code from Listings 12-3 and 12-4 or download the file Chapter12ProgramGenericQuickSort.zip.
As you see in a moment, you can have such data sorting flexibility yet keep the strong data type checking protection without a heavy performance hit because of boxing and unboxing. You also don't need to mess around with type casts. Clearly, generics are a worthy addition to your programming toolkit.
How It Works
Examine the source code in frmMain that drives the sorting tests. This is shown in Listing 12-3.
Listing 12-3: Using Generics to Sort Data (frmMain.cs)
using System;
using System.Windows.Forms;
public class frmMain : Form
{
const int INTEGER = 1; // Symbolic constants
const int LONG = 2;
const int DOUBLE = 3;
const int STRING = 4;
const int UNSORTED = 1;
const int SORTED = 2;
const int MAXVALUE = 1000;
int items; // Values to generate
int choice; // Which data type selected
int whichListbox; // Which listbox getting this data
int[] iData; // Data arrays
long[] lData;
double[] dData;
string[] sData;
Random rnd = new Random();
private GroupBox groupBox1;
private RadioButton rbString;
private RadioButton rbDouble;
private RadioButton rbLong;
private Label label1;
private TextBox txtItems;
private TextBox txtString;
private ListBox lstUnsorted;
private ListBox lstSorted;
private Button btnRaw;
private Button btnSort;
private Button btnClose;
private RadioButton rbInt;
#region Windows code
public frmMain()
{
InitializeComponent();
rbInt.Checked = true; // Set defaults
choice = INTEGER;
}
public static void Main()
{
frmMain main = new frmMain();
Application.Run(main);
}
private void btnClose_Click(object sender, EventArgs e)
{
Close();
}
// Show the raw data first
private void btnRaw_Click(object sender, EventArgs e)
{
bool flag;
int i;
flag = int.TryParse(txtItems.Text, out items);
if (flag == false)
{
MessageBox.Show("Numeric only. Re-enter", "Input Error");
txtItems.Focus();
return;
}
lstUnsorted.Items.Clear(); // Clear old data
lstSorted.Items.Clear();
whichListbox = UNSORTED;
switch (choice) // Select the data type
in use
{
case INTEGER: // Integer
iData = new int[items];
for (i = 0; i < items; i++)
{
iData[i] = rnd.Next(MAXVALUE);
}
break;
case LONG: // Long
lData = new long[items];
for (i = 0; i < items; i++)
{
lData[i] = (long)rnd.Next(MAXVALUE);
}
break;
case DOUBLE: // Double
dData = new double[items];
for (i = 0; i < items; i++)
{
dData[i] = rnd.NextDouble() * MAXVALUE;
}
break;
case STRING: // String
sData = txtString.Text.Split(','); // Split into
strings
break;
}
ShowData(); // Show data in listbox
object
}
private void btnSort_Click(object sender, EventArgs e)
{
whichListbox = SORTED;
switch (choice)
{
case INTEGER: // Data types again. . .
clsQuickSort<int> iSort = new clsQuickSort<int>(iData);
iSort.Sort();
break;
case LONG:
clsQuickSort<long> lSort = new clsQuickSort<long>
(lData);
lSort.Sort();
break;
case DOUBLE:
clsQuickSort<double> dSort = new
clsQuickSort<double>
(dData);
dSort.Sort();
break;
case STRING:
clsQuickSort<string> sSort = new
clsQuickSort<string>
(sData);
sSort.Sort();
break;
}
ShowData();
}
private void ShowData() // Simply displays the data
{
int i;
switch (choice)
{
case INTEGER: // Data types again. . .
for (i = 0; i < items; i++)
{
if (whichListbox == SORTED)
lstSorted.Items.Add(iData[i].ToString());
else
lstUnsorted.Items.Add(iData[i].ToString());
}
break;
case LONG:
for (i = 0; i < items; i++)
{
if (whichListbox == SORTED)
lstSorted.Items.Add(lData[i].ToString());
else
lstUnsorted.Items.Add(lData[i].ToString());
}
break;
case DOUBLE:
for (i = 0; i < items; i++)
{
if (whichListbox == SORTED)
lstSorted.Items.Add(dData[i].ToString());
else
lstUnsorted.Items.Add(dData[i].ToString());
}
break;
case STRING:
for (i = 0; i < sData.Length; i++)
{
if (whichListbox == SORTED)
lstSorted.Items.Add(sData[i].ToString());
else
lstUnsorted.Items.Add(sData[i].ToString());
}
break;
}
}
private void rbInt_Click(object sender, EventArgs e)
{
choice = INTEGER;
}
private void rbLong_Click(object sender, EventArgs e)
{
choice = LONG;
}
private void rbDouble_Click(object sender, EventArgs e)
{
choice = DOUBLE;
}
private void rbString_Click(object sender, EventArgs e)
{
choice = STRING;
}
}
The code starts with the definition of several symbolic constants, followed by a series of array reference objects. These arrays ultimately hold the data to be sorted. The frmMain constructor sets the default data type to be an integer for the radio button choices and the current choice (choice = INTEGER). The default number of values to generate for the numeric data types is 10, as shown in Figure 12.2.
Using the Split( ) Method for Strings
The count when string data types are selected is set by the number of comma-delimited string entries made in the txtString textbox object. This is accomplished with the statement:
sData = txtString.Text.Split(',');
The Split() method examines txtString looking for the comma character. Each time it finds a comma, it creates a new string for the characters leading up to (but not including) the comma. After all substrings have been read, the array of strings is assigned into sData. The Split() method can use multiple separator characters if you need them. You can find the details using the online help. (That is, double-click the word Split in the source code to highlight it, and then press the F1 key.)
If the user selects something other than the default INTEGER option, the variable choice is set in the appropriate radio button click event code. For example, if the user clicks the Double radio button, the following code executes, setting choice to the appropriate value:
private void rbDouble_Click(object sender, EventArgs e)
{
choice = DOUBLE;
}
The variable choice selects the appropriate code via the various switch statements.
Generating the Data
Depending upon the value of choice, the appropriate array is filled with data. How this is done is shown in the following code fragment:
switch (choice) // Select the data type
in use
{
case INTEGER: // Integer
iData = new int[items];
for (i = 0; i < items; i++)
{
iData[i] = rnd.Next(MAXVALUE);
}
break;
case LONG: // Long
lData = new long[items];
for (i = 0; i < items; i++)
{
lData[i] = (long)rnd.Next(MAXVALUE);
}
break;
case DOUBLE: // Double
dData = new double[items];
for (i = 0; i < items; i++)
{
dData[i] = rnd.NextDouble() * MAXVALUE;
}
break;
case STRING: // String
sData = txtString.Text.Split(','); // Split into
strings
break;
}
For the INTEGER and LONG data types, the parameterized Next() method generates a pseudo-random number inside a for loop. The number of passes through the loop is determined by the items variable entered by the user. Passing in the value MAXVALUE means that the values generated fall within the range of 0 and MAXVALUE (exclusively). For the DOUBLE data type, the method NextDouble() returns a value between 0 and 1 (exclusively). Therefore, multiplying the fractional value returned from the NextDouble() method by MAXVALUE sets the same range for the double data type. For string data, the Split() method populates the sData array, as explained earlier.
After the values have been generated, the call to ShowData() moves the data into the listbox to show the values that were generated.
Using a Generic Class
After the raw data have been generated and displayed in the listbox object, you are ready to pass the unsorted data to the generic version of the Quicksort method. The following code fragment shows how the sort method is called for the differing data types:
private void btnSort_Click(object sender, EventArgs e)
{
whichListbox = SORTED;
switch (choice)
{
case INTEGER: // Integer
clsQuickSort<int> iSort = new clsQuickSort<int>
(iData);
iSort.Sort();
break;
case LONG:
clsQuickSort<long> lSort = new clsQuickSort<long>
(lData);
lSort.Sort();
break;
case DOUBLE:
clsQuickSort<double> dSort = new
clsQuickSort<double>
(dData);
dSort.Sort();
break;
case STRING:
clsQuickSort<string> sSort = new
clsQuickSort<string>
(sData);
sSort.Sort();
break;
}
ShowData();
}
In each case, the code uses the generic syntax to create an object of the clsQuickSort class. That is, the statement to instantiate the object has the following form:
clsQuickSort<T> typeSort = new clsQuickSort<T>(typeData);
Therefore, depending upon the value of choice , the four objects are instantiated using one of the following four statements:
clsQuickSort<int> iSort = new clsQuickSort<int>(iData);
clsQuickSort<long> lSort = new clsQuickSort<long>(lData);
clsQuickSort<double> dSort = new clsQuickSort<double>(dData);
clsQuickSort<string> sSort = new clsQuickSort<string>(sData);
After the appropriate object has been instantiated, the code calls the object's Sort() method to sort the data (such as iSort.Sort()). After that, code has executed, the data has been sorted, and the sorted data is displayed in the second listbox object.
Now see what changes you have to make to the Quicksort code.
Generic Quicksort
The code for clsQuickSort is presented in Listing 12-4. Note the second using statement in the listing that makes generics possible in the clsQuickSort class. This Generic namespace contains generic classes, structures, and interfaces to support generic dictionaries, lists, queues, and stacks. In this section you draw upon generics only as they relate to the implementation of a generic class.
The third line in Listing 12-4,
public class clsQuickSort<T> where T : IComparable
uses the generic angle bracket notation that surrounds the data type (T) used by the object of the class. Recall that when you instantiated an object of a generic class, perhaps for the double data type, it took the following form:
clsQuickSort<double> dSort = new clsQuickSort<double>(dData);
Therefore, the dSort object is of type double and that becomes the T type in the opening statement of the class definition. In other words, instantiating object dSort makes the statement
public class clsQuickSort<T> where T : IComparable
appear as though the class is written as:
public class clsQuickSort<double> where double : IComparable
The compiler generates the necessary code to accommodate the data types that might be passed to the generic clsQuickSort class. For the moment ignore the expressions that follow the where keyword in the statement, which are discussed a little later in the chapter in the section titled “Using Generics with Constraints and Interfaces.”
Listing 12-4: Generic Quicksort Source Code (clsSort.cs)
using System;
using System.Collections.Generic;
public class clsQuickSort<T> where T : IComparable
{
// ================= instance member ====================
T[] data;
// ================= constructor ====================
public clsQuickSort(T[] values)
{
data = values; // copy rvalue of unsorted data
}
// ================= Property methods ====================
// ================= Helper methods ====================
/*****
* Purpose: This method gets the initial pivot point for the sort and then
* calls itself recursively until all values have been set.
*
* Parameter list:
* int first index of first element of partition
* int last index of last element of partition
*
* Return value:
* void
*****/
private void doSort(int first, int last)
{
if (first == last)
{
return; // Done
}
else
{
int pivot = getPivotPoint(first, last);
if (pivot > first)
doSort(first, pivot 1);
if (pivot < last)
doSort(pivot + 1, last);
}
}
/*****
* Purpose: This method sets the pivot point for the sort.
*
* Parameter list:
* int start index to start of partition
* int end index to end of partition
*
* Return value:
* void
*****/
private int getPivotPoint(int first, int last)
{
int pivot = first;
int start = first; // Keep copies
int end = last;
if (last first >= 1)
{
while (end > start)
{
while (data[pivot].CompareTo(data[start]) >= 0 &&
start <= last && end > start)
start++;
while (data[pivot].CompareTo(data[end]) <= 0 &&
end >= first && end >= start)
end--;
if (end > start)
swap(start, end);
}
swap(first, end);
doSort(first, end 1);
}
return end;
}
/*****
* Purpose: This method performs the data swap for quickSort()
*
* Parameter list:
* int pos1 index to first value to swap
* int pos2 index to second value to swap
*
* Return value:
* void
*****/
private void swap(int pos1, int pos2)
{
T temp;
temp = data[pos1];
data[pos1] = data[pos2];
data[pos2] = temp;
}
// ================= General methods ====================
/*****
* Purpose: This is the user interface entry point for the Quicksort
*
* Parameter list:
* n/a
*
* Return value:
* void
*
* CAUTION: This routine assumes constructor is passed unsort data
*****/
public void Sort()
{
int len = data.Length;
if (len < 2) // Enough to sort?
return;
doSort(0, data.Length 1);
}
}
You might think that it would be a fairly simple process to convert the code shown in Listing 12-2 to use generics. A complication, however, arises with statements like:
while (data[start] <= pivot && start <= last && end > start)
Unlike some other languages that support similar constructs (such as templates in C++), C# does not like the use of relational operators with a generic type T. Because of that limitation, the C# compiler complains about the expression,
data[start] <= pivot
in the while statement because you are trying to compare two operands of type T. Because the pivot point for the data array plays an important part in the Quicksort algorithm, you must modify the code to work around this limitation.
Fortunately, the points of complaint by the compiler center on the comparison of the pivot point with a particular element of the array. You can fix that.
Using Generics with Constraints and Interfaces
If you had written the first line of the class as:
public class clsQuickSort<T>
you would be saying that this class works with any data type you can think of. That is, you could use an object of this class with all value types and all reference types, including any custom objects you may have created. Such a class signature means that clsQuickSort is usable with any type of data on the planet. Such a generic class is known as an unbounded generic class. Unbounded generic classes are not limited, or constrained, to any particular type of data.
As you might imagine, however, there might be data types that don't lend themselves to the Quicksort algorithm. Indeed, I have chosen to limit the use of the class to those data types that support the ICompare interface. The following expression uses the where keyword to introduce a constraintfor the class:
where T : IComparable
The expression begins with the where keyword followed by the generic data type indicator (T), a colon (:), and an interface name. You can verbalize the complete class signature,
public class clsQuickSort<T> where T : IComparable
as “The clsQuickSort may be used with any data type T subject to the constraint that data type T implements the IComparable interface.” In other words, tight type checking on the types of data that may use this class is provided. If the data type supports the ICompare interface, that data type can be sorted by the implementation of the Quicksort algorithm. It should be clear, therefore, that the where keyword constrains the class to only those data types that support the ICompare interface. Therefore, clsQuickSort is known as a constrained generic class.
Interfaces
Okay, but what is an interface? An interface is a reference object that has no implementation, or code, associated with it. Recall from Chapter 4 that you made a strong distinction between the terms define and declare. Programmers use those two terms as if they are the same. They are not, and it's just plain sloppy to use them interchangeably. A data definition must have memory allocated for the data. This also means that an lvalue for that data exists in the symbol table. Conversely, it was pointed out that a data declaration does not cause memory to be allocated for the data. The purpose of a data declaration serves only to fill in an attribute list for the data item in the symbol table. Data declarations do not provide memory for the data. Interfaces may include declarations for method signatures, properties, and events. They do not, however, provide the code to implement those methods, properties, or events. As you can see, an interface is a declaration precisely because no code is associated with the interface.
The IComparable interface used in Listing 12-4 supports only one method in the interface. You can write this interface as follows:
public interface IComparable
{
int CompareTo(Object obj);
}
Each of the value types supports the IComparable interface, which means that the wrapper class around each value type has a CompareTo() method that you can use to compare one data item of that type against another data item of the same type. If the int value returned from CompareTo() is less than 0, it means that the current instance is less than obj. If the return value is 0, the two instances are equal. If the return value is positive, the current instance is greater than obj.
For example, given an object named obj,
obj.CompareTo(obj)
is required to return 0 if the two objects are the same. Likewise, if a different object named whatever is different from obj, then,
obj.CompareTo(whatever)
must return a value other than 0 and,
whatever.CompareTo(obj)
must return a value of the opposite sign. That is, if obj.CompareTo(whatever) returns 1, then whatever.CompareTo(obj) must return 1.
An interface is a promise that you make as a programmer to anyone who uses the code in the class that implements the IComparable interface, including the C# compiler. If you want to use the IComparable interface with a class that you write that doesn't provide the CompareTo() method, your class must write the code for that method, ensuring that it obeys the return value rules for the interface.
Why Use an Interface?
Not too long ago, I flew in a private plane with a friend who has his private pilot's license. About 40 years ago I also had my pilot's license, but ran out of money as a broke graduate student and didn't fly a plane after that. What amazed me the most a while ago were the avionics (radar and other electronics) that I saw in my friend's plane. One of the questions that crossed my mind during the flight with my friend was, “Could I fly this plane with all these new electronic thingies?”
Actually, the basics of flying haven't changed much. You have a yoke and pedals that control the basic movements of the plane. Therefore, a basic plane class might have,
public clsPrivatePlane : IControls
and you might declare the IControls interface as:
public interface IControls
{
int Yoke(int pitch, int yaw);
int Pedals(int direction);
int Throttle(int rateOfFuelFlow);
}
With these basic controls defined, a pilot could “fly” an object of the class, although the FAA might have dozens of citations for rules that might be broken along the way. Over the years, as new avionics were added, you could upgrade your private plane class to reflect the new stuff today's planes have. You might change the class to,
public clsPrivatePlane : IControls, IAvionics
where IAvionics provides for the methods and members necessary to reflect today's avionics. If my friend later wants to do stunt flying, which may require certain devices to equip the plane, the class could again be expanded:
public clsPrivatePlane : IControls, IAvionics, IStunts
(By convention, most interface declarations begin with the capital letter I.) The key thing to notice here is explained in the following Note.
Note
Earlier versions of the plane class can still exist if classes are created that don't implement the newer interfaces or “empty” methods are used for the new interfaces.
These empty interface methods simply mean the current plane object doesn't support these advanced features. Perhaps more important, an upgraded plane doesn't “break” the code for the earlier versions of the plane. This is the real strength of interfaces: If done correctly, interfaces decouple the user interface from the underlying code.
For example, consider the IControls that I used when I was flying. All the control surfaces for the plane were connected to the cockpit with steel cables. The IControls for many private planes today are based on a system of hydraulics for the control surfaces. The IControls for modern military aircraft are fly-by-wire, and the control surfaces are computer-controlled. However, as a pilot using an object of the class, I can view IControls as a black box because I don't care how the control surfaces are moved. That is, I don't care about the implementation of the controls. I care only that the controls do move the control surfaces when I touch them. (It's a big problem if the control surfaces stop moving while you're flying a plane!) Using an interface means that I can still use the same code to call the Yoke(), Pedals(), and Throttle() methods regardless of whether I'm flying a canvas-covered Piper J2 or the F/A-22 Raptor.
Using an Interface
If you look closely at the code in Listing 12-4, you find two statements,
while (data[pivot].CompareTo(data[start]) >= 0 &&
start <= last && end > start)
and:
while (data[pivot].CompareTo(data[end]) <= 0 &&
end >= first && end >= start)
Each of these uses the CompareTo() method of the IComparable interface for examining the pivot values in the data arrays. Because the wrapper classes for value types implement the CompareTo() method, you don't need to write the code! Again, this is one of the nice features of OOP in general and interfaces in particular. The .NET Framework provides the code you need to use the IComparable interface.
If you want to compare objects of classes that you've written, you will probably need to write your own CompareTo() method. However, even if you do need to write the code to implement an interface, you still gain the flexibility provided by interfaces.
How Do You Know an Interface Is Implemented for a Data Type?
In Figure 12.3, the btnSort_Click() event uses a switch statement to determine which data object to create for the sort method. This means that only the four data types presented in the radio button objects can be selected. But how can you determine if a data type you use implements a specific interface? There are four ways to do this.
Implement the Interface Yourself
First, if the data type is an object that you created, you must specify the interface(s) it supports. This is what you did for the clsQuickSort class. You simply wrote the class stating as part of the class signature that the class is constrained for those data types that support the IComparable interface. You are free, of course, to add your own interfaces to a class. If you do that, then you must provide the interface declaration and its supporting code. (The IControls interface mentioned earlier in this chapter is an example of how to implement an interface with your code.)
Use the C# Documentation
The second way to determine if a data type supports a given interface is to examine its documentation. Using the C# documentation, you can look up the relevant data types to see if they support the IComparable interface.
For example, if you select Help Index from the C# main menu, you can search the int keyword. The search provides you with information about that data type. Figure 12.4 shows what you see when you index on the int keyword.
Figure 12.4 Help in int Keyword
On the right side of the figure, in the middle, you can see the table heading .NET Framework Type. Immediately under that column heading is the link System.Int32. If you click that link, you see the information presented in Figure 12.5.
Figure 12.5 Finding interfaces for int data type
In the C# section, you can see that System.Int32 supports the IComparable interface (along with several others).
The process for the string data type is a little different because a string is a reference type to begin with. If you perform an index search on string, you are told that it is an alias name for String in the .NET Framework. Following that link, you find the information presented in Figure 12.6.
Figure 12.6 Finding the string interfaces
This confirms that the string data type also supports the IComparable interface. Using the C# documentation is an easy way to determine if a specific C# data type supports a specific interface. However, these two methods are not runtime ways to determine whether a data type supports a certain interface. How can you make the determination at run time?
Use the is Operator
The third way to determine if a data type supports a given interface is to use the is operator. The syntax for the is operator is as follows:
TypeInQuestion is InterfaceInQuestion
For example, if you want to see if a data type passed to the clsQuickSort constructor supports the IComparable interface, you can add the following test code to the constructor presented in Listing 12-4:
public clsQuickSort(T[] values)
{
data = values; // copy rvalue of unsorted data
if (data[0] is IComparable)
{
Console.WriteLine("data[0] is IComparable");
}
}
Note the use of the is operator in the if statement. If you set a breakpoint on the if statement, you can check each data type passed to the class to see if it supports the IComparable interface. In the final version of the code, you would probably want to flag a data set that fails the if test and returns an error message to the caller.
Using the IComparable interface in clsQuickSort enables you to get around the fact that generics currently don't directly support the relational operators. If you take a little time, you can find that the code functions the same way it did in the nongeneric form of the class code.
Use the as Operator
Fourth, you can use the as operator to determine if an object supports a specific interface. The as operator has the following syntax form:
expression as type
The as operator is actually used to perform conversions between compatible reference data types. However, if the conversion cannot be made, it produces null as the outcome of the expression. This is kind of nice because if the conversion fails, the result is null rather than an exception being thrown.
For example, ArrayList data types support only the IList interface. You could check this fact using code similar to that shown in the following code fragment:
ArrayList val = new ArrayList();
IComparable val1 = val as IComparable;
if (val1 == null)
{
Console.WriteLine("val1 doesn't support IComparable");
}
In this example, an ArrayList reference named val is defined and then used the as operator to see if you could convert val into an IComparable object named val1. If ArrayList objects don't support the IComparable interface, the conversion fails and val1 is null. Because ArrayLists do not support the IComparable interface, the conversion fails, and the failure message is written to the console.
If you modify the code to define val using the following statement,
int val = 5;
the conversion is made successfully, and the failure message is not displayed. (You must assign a value to val or the compiler issues an uninitialized local variable error message.)
Generics and interfaces can often team up to make a given class much more flexible for the data types it can process. Obviously, the time to think about generics is during the design phase of a project. Although the design time might increase slightly, you will be rewarded with a much more robust class for those that do implement generics.
Summary
In this chapter you learned how generics can reduce the code burden to develop a new application. You concentrated on how generics enable you to write classes and methods in a way that makes them capable to process different data types. Not only do generics provide code flexibility, they also do it with strongly typed data yet without the hassles involved in having to cast every expression. You also learned how to use interfaces to simplify your code. Interfaces guarantee the user that specific functionality is provided by the code. Entire books have been written on interfaces and their related topics, which are worth your study.
Exercises
You can find the answers to the following exercises in Appendix A.
1. What are the major advantages of generics?
2. Listing 12-3 shows a method named ShowData() that you can use to fill the listbox objects with the appropriate data. How would you modify that method to take advantage of generics?
3. What are the major advantages of interfaces?
4. The swap() method in clsQuickSort is sloppy because you rely on class scope for the data swapped. Rewrite the swap() method so that it can still swap any type of data of the class, but without relying on class scope.
5. One of the major banes of writing commercial software is adding new features without breaking older versions. Do any of the topics discussed in this chapter cause you to rethink software versioning?
What You Learned in This Chapter
|
TOPIC |
KEY POINTS |
|
Generics |
A means to add code flexibility but retain strict type checking |
|
Generic advantages |
Enables one body of code to process what seems to be typeless code; enhances code reuse |
|
Boxing, unboxing |
The overhead processes associated with converting to-and-from value types to objects and back |
|
Interfaces |
A flexible means to add new class functionality without breaking old code |