Generics are type-safe

When you declare an array, you must specify the exact type of data it can hold. If you specify int, the array can’t hold anything other than ints or other numeric types that C# can convert implicitly to int. You see compiler errors at build-time if you try to put the wrong kind of data into an array. Thus the compiler enforces type-safety, enabling you to fix a problem before it ever gets out the door. A compiler error beats the heck out of a runtime error. Compiler errors are useful because they help you spot problems now.

The old-fashioned nongeneric collections aren't type-safe. In C#, everything IS_A Object because Object is the base type for all other types, both value types and reference types. (Don't worry if you don’t understand IS_A — it’s explained in the “IS_A versus HAS_A — I’m So Confused_A” section of Book 2, Chapter 5.) But when you store value types (numbers, chars, bools, and structs) in a collection, they must be boxed going in and unboxed coming back out. It's as though you’re putting items in an egg to place them inside an egg carton and then breaking the eggshells after removing them from the egg carton to get the items back out. (Reference types such as string, Student, and BankAccount don't undergo boxing.)

The first consequence of nongenerics lacking type-safety is that you need a cast, as shown in the following code, to get the original object out of the ArrayList because it’s hidden inside an Object:

ArrayList aList = new ArrayList();
// Add five or six items, then …
string myString = (string)aList[4]; // Cast to string.

Fine, but the second consequence is this: You can put eggs in the carton, sure. But you can also add marbles, rocks, diamonds, fudge — you name it. An ArrayList can hold many different types of objects at the same time. So it's legal to write this:

ArrayList aList = new ArrayList();
aList.Add("a string"); // string -- OK
aList.Add(3); // int -- OK
aList.Add(aStudent); // Student -- OK

However, if you put a mixture of incompatible types into an ArrayList (or another nongeneric collection), how do you know what type is in, say, aList[3]? If it's aStudent and you try to cast it to string, you get a runtime error. It's just like Harry Potter reaching into a box of Bertie Botts’s Every Flavor Beans: He doesn’t know whether he’ll grab raspberry beans or earwax.

To be safe, you have to resort to using the is operator (discussed in Book 2) or the alternative, the as operator:

// See if the object is the right type, then cast it …
if (aList[i] is Student) // Is the object there a Student?
{
Student theStudent = (Student)aList[i]; // Yes, so it's safe to cast.
}
// Or do the conversion and see if it went well…
Student aStudent = aList[i] as Student; // Extract a Student, if present;
if (aStudent != null) // if not, "as" returns null.
{
// OK to use aStudent; "as" operator worked.
}

You can avoid all this extra work by using generics. Generic collections work like arrays: You specify the one and only type they can hold when you declare them.

Generics are efficient

Polymorphism allows the type Object to hold any other type, as with the egg carton analogy in the previous section. But you can incur a penalty by putting in value-type objects — numeric, char, and bool types and structs — and taking them out. That's because value-type objects that you add have to be boxed. (See Book 2 for more on polymorphism.)

Boxing isn’t worrisome unless your collection is big (although the amount of boxing going on can startle you and be more costly than you imagined). If you’re stuffing a thousand, or a million, ints into a nongeneric collection, it takes about 20 times as long, plus extra space on the memory heap, where reference-type objects are stored. Boxing can also lead to subtle errors that will have you tearing your hair out. Generic collections eliminate boxing and unboxing.

Shipping packages at OOPs

Here's the scene for an example: a busy shipping warehouse similar to UPS or FedEx. Packages stream in the front door at OOPs, Inc., and are shipped out the back as soon as they can be processed. Some packages need to be delivered by way of superfast, next-day teleportation; others can travel a tiny bit slower, by second-day cargo pigeon; and most can take the snail route: ground delivery in your cousin Fred’s ’82 Volvo.

But the packages don’t arrive at the warehouse in any particular order, so as they come in, you need to expedite some of them as next-day or second-day. Because some packages are more equal than others, they are prioritized, and the folks in the warehouse give the high-priority packages special treatment.

Except for the priority aspect, this situation is tailor-made for a queue data structure. A queue is perfect for anything that involves turn-taking. You’ve stood (or driven) in thousands of queues in your life, waiting for your turn to buy Twinkies or pay too much for prescription medicines. You know the drill.

The shipping warehouse scenario is similar: New packages arrive and go to the back of the line — normally. But because some have higher priorities, they’re privileged characters, like those Premium Class folks at the airport ticket counter. They get to jump ahead, either to the front of the line or not far from the front.

Queuing at OOPs: PriorityQueue

The shipping queue at OOPs deals with high-, medium-, and low-priority packages coming in. Here are the queuing rules:

• High-priority packages (next-day) go to the front of the queue — but behind any other high-priority packages that are already there.
• Medium-priority packages (second-day) go as far forward as possible — but behind all the high-priority packages, even the ones that a laggard will drop off later, and also behind other medium-priority packages that are already in the queue.
• Low-priority ground-pounders must join at the back of the queue. They get to watch all the high priorities sail by to cut in front of them — sometimes, way in front of them.

C# comes with built-in queues, even generic ones. But older versions don’t come with a priority queue, so you have to build your own. How? A common approach is to embed several actual queues within a wrapper class, sort of like this:

class Wrapper // Or PriorityQueue
{
Queue queueHigh = new Queue ();
Queue queueMedium = new Queue ();
Queue queueLow = new Queue ();
// Methods to manipulate the underlying queues…

Wrappers are classes (or methods) that encapsulate complexity. A wrapper may have an interface quite different from the interfaces of what’s inside it — that’s an adapter.

The wrapper encapsulates three actual queues here (they could be generic), and the wrapper must manage what goes into which underlying queue and how. The standard interface to the Queue class, as implemented in C#, includes these two key methods:

• Enqueue() (pronounced “N-Q”) inserts items into a queue at the back.
• Dequeue() (pronounced “D-Q”) removes items from the queue at the front.

For the shipping-priority queue, the wrapper provides the same interface as a normal queue, thus pretending to be a normal queue itself. It implements an Enqueue() method that determines an incoming package's priority and decides which underlying queue it gets to join. The wrapper’s Dequeue() method finds the highest-priority Package in any of the underlying queues. The formal name of this wrapper class is PriorityQueue.

The example relies on a random-number generator that you can set in both Main() and the CreatePackage() method of the PackageFactory. The call to Random(2) uses a seed value (the number used as a starting point for the random-number calculation) so that you get the same results every time. This approach allows for reproducible testing results, which is a common practice with developers who don't want to deal with number differences between application runs. Of course, you could use Random() by itself, which would allow the seed to change automatically, so you can see a more realistic presentation of application output, but you'll need to make this change yourself. Using the default Random(2), you see the following output:

Add a random number (0 - 20) of random packages to queue:
Creating 15 packages:
Generating and adding random package 0 with priority High
Generating and adding random package 1 with priority Medium
Generating and adding random package 2 with priority Low
Generating and adding random package 3 with priority High
Generating and adding random package 4 with priority Low
Generating and adding random package 5 with priority Low
Generating and adding random package 6 with priority High
Generating and adding random package 7 with priority Medium
Generating and adding random package 8 with priority Low
Generating and adding random package 9 with priority Low
Generating and adding random package 10 with priority High
Generating and adding random package 11 with priority Low
Generating and adding random package 12 with priority Low
Generating and adding random package 13 with priority Medium
Generating and adding random package 14 with priority Medium
See what we got:
Packages received: 15
Remove a random number of packages (0-20):
Removing up to 8 packages
Shipped package with priority High
Shipped package with priority High
Shipped package with priority High
Shipped package with priority High
Shipped package with priority Medium
Shipped package with priority Medium
Shipped package with priority Medium
Shipped package with priority Medium

Unwrapping the package

This example relies on a simplified example package. Class Package focuses on the priority part, although a real Package object would include other members. Here's the code for class Package:

class Package : IPrioritizable
{
private Priority _priority;

//Constructor
public Package(Priority priority) => _priority = priority;

//Priority -- Return package priority -- read-only.
public Priority Priority
{
get => _priority;
}

// Plus ToAddress, FromAddress, Insurance, etc.
}

All that Package needs for the example are

• A private data member to store its priority
• A constructor to create a package with a specific priority (Because there is only one variable to initialize, you can use the expression body constructor version, which is explained in the “Using Expression-Bodied Members” section of Book 2, Chapter 4.)
• A method (implemented as a read-only property here) to return the priority (Because there is no special code in this property, you can use the expression body version.)

Two aspects of class Package require some explanation: the Priority type and the IPrioritizable interface that Package implements.

Touring Main()

Before you spelunk the PriorityQueue class, it's useful to get an overview of how it works in practice at OOPs, Inc. Here’s the Main() method for the PriorityQueue example:

static void Main(string[] args)
{
Console.WriteLine("Create a priority queue:");
PriorityQueue<Package> pq = new PriorityQueue<Package>();
Console.WriteLine(
"Add a random number (0 - 20) of random packages to queue:");
Package pack;
PackageFactory fact = new PackageFactory();

// You want a random number less than 20.
Random rand = new Random(2);
int numToCreate = rand.Next(20); // Random int from 0 - 20
Console.WriteLine(" Creating {0} packages: ", numToCreate);

for (int i = 0; i < numToCreate; i++)
{
Console.Write(" Generating and adding random package {0}", i);
pack = fact.CreatePackage();
Console.WriteLine(" with priority {0}", pack.Priority);
pq.Enqueue(pack);
}

Console.WriteLine("See what we got:");
int total = pq.Count;
Console.WriteLine("Packages received: {0}", total);

Console.WriteLine("Remove a random number of packages (0-20): ");
int numToRemove = rand.Next(20);
Console.WriteLine(" Removing up to {0} packages", numToRemove);

for (int i = 0; i < numToRemove; i++)
{
pack = pq.Dequeue();
if (pack != null)
{
Console.WriteLine(" Shipped package with priority {0}",
pack.Priority);
}
}

Console.Read();
}

Here's what happens in Main():

1. Instantiate a PriorityQueue object for type Package.

2. Create a PackageFactory object whose job is to create new packages with randomly selected priorities, on demand.

   A factory is a class or method that creates objects for you. You tour PackageFactory in the section “Using a (nongeneric) Simple Factory class,” later in this chapter.

3. Use the .NET library class Random to generate a random number and then call PackageFactory to create that number of new Package objects with random priorities.
4. Add each package to the PriorityQueue by using pq.Enqueue(pack).
5. Write the number of packages created and then randomly remove some of them from the PriorityQueue by using pq.Dequeue().
6. End after displaying the number of packages removed.

Writing generic code the easy way

Now you have to figure out how to write a generic class, with all those <T>s. Looks confusing, doesn't it? Well, it’s not so hard, as this section demonstrates.

The simple way to write a generic class is to write a nongeneric version first and then substitute the <T>s. For example, you can write the PriorityQueue class for Package objects, test it, and then “genericize” it. Here's a small piece of a nongeneric PriorityQueue to illustrate (don’t add this code to the current example; it won’t compile):

class PriorityQueue<T> where T : IPrioritizable
{
//Queues -- the three underlying queues: all generic!
private Queue<T> _queueHigh = new Queue<T>();
private Queue<T> _queueMedium = new Queue<T>();
private Queue<T> _queueLow = new Queue<T>();

//Enqueue -- Prioritize T and add an item of type T to correct queue.
// The item must know its own priority.
public void Enqueue(T item)
{
switch (item.Priority) // Require IPrioritizable for this property.
{
case Priority.High:
_queueHigh.Enqueue(item);
break;
case Priority.Medium:
_queueMedium.Enqueue(item);
break;
case Priority.Low:
_queueLow.Enqueue(item);
break;
default:
throw new ArgumentOutOfRangeException(
item.Priority.ToString(),
"bad priority in PriorityQueue.Enqueue");
}
}
// And so on …

Testing the logic of the class is easier when you write the class nongenerically first. When all the logic is straight, you can use find-and-replace to replace the name Package with T.

Saving PriorityQueue for last

Why would a priority queue be last? It may seem a little backward, but you've seen the code that relies on the priority queue to perform tasks. Now it’s time to examine the PriorityQueue class. This section shows the code and then walks you through it so that you see how to deal with a couple of small issues. Take it a piece at a time.

Using a (nongeneric) Simple Factory class

The “Saving PriorityQueue for last” section, earlier in this chapter, uses a simple factory object to generate an endless stream of Package objects with randomized priority levels. At long last, that simple class can be revealed:

class PackageFactory
{
//A random-number generator
Random _randGen = new Random(2);

//CreatePackage -- The factory method selects a random priority,
// then creates a package with that priority.
// Could implement this as iterator block.
public Package CreatePackage()
{
// Return a randomly selected package priority.
// Need a 0, 1, or 2 (values less than 3).
int rand = _randGen.Next(3);

// Use that to generate a new package.
// Casting int to enum is clunky, but it saves
// having to use ifs or a switch statement.
return new Package((Priority)rand);
}
}

Class PackageFactory has one data member and one method. (You can just as easily implement a simple factory as a method rather than as a class — for example, a method in class Program.) When you instantiate a PackageFactory object, it creates an object of class Random() and stores it in the data member _randGen. To obtain a value between 0 and 2 to store in rand as a priority, the code calls _randGen.Next(3). A value of 0 represents a high-priority item.

Contravariance

A scheduling application could have Events, which have a date, and then a set of subclasses, one of which is Course. A Course is an Event. Each course knows its own number of students and the methods used to interact with them. One of these methods is MakeCalendar():

public void MakeCalendar(IEnumerable<Event> theEvents)
{
foreach (Event item in theEvents)
{
Console.WriteLine(item.WhenItIs.ToString());
}
}

Pretend that it makes a calendar. For now, all it does is print the date to the console. MakeCalendar is system-wide, so it expects some enumerable list of events.

The application also has an EventSorter class that you can pass into a list's Sort() method. That method then uses the EventSorter object's Compare() method to decide which item should come first in the sorted list. Here is the EventSorter class:

class EventSorter : IComparer<Event>
{
public int Compare(Event x, Event y)
{
return x.WhenItIs.CompareTo(y.WhenItIs);
}
}

The event manager makes a list of courses, sorts them, and then makes a calendar. ScheduleCourses creates the list of courses and then calls courses.Sort() with an EventSorter as an argument, as shown here:

public void ScheduleCourses()
{
List<Course> courses = new List<Course>()
{
new Course(){NumberOfStudents=20,
WhenItIs = new DateTime(2021, 2, 1)},
new Course(){NumberOfStudents=14,
WhenItIs = new DateTime(2021, 3, 1)},
new Course(){NumberOfStudents=24,
WhenItIs = new DateTime(2021, 4, 1)},
};

// Pass an ICompare<Event> class to the List<Course> collection.
// It should be an ICompare<Course>, but it can use ICompare<Event>
// because of contravariance
courses.Sort(new EventSorter());


// Pass a List of courses, where a List of Events was expected.
// We can do this because generic parameters are covariant
MakeCalendar(courses);
}

But wait, this is a list of courses that calls Sort(), not a list of events. Doesn't matter — IComparer<Event> is a contravariant generic for T (its return type) as compared to IComparer<Course>, so it's still possible to use the algorithm.

Now the application passes a list into the MakeSchedule method, but that method expects an enumerable collection of Events. Parameters are covariant for generics, so it's possible to pass in a List of courses because Course is covariant to Event.

There is another example of contravariance, using parameters rather than return values. If you have a method that returns a generic list of courses, you can call that method expecting a list of Events, because Event is a superclass of Course.

You know how you can have a method that returns a String and assign the return value to a variable that you have declared an object? Now you can do that with a generic collection, too.

In general, the C# compiler makes assumptions about the generic type conversion. As long as you're working up the chain for parameters or down the chain for return types, C# will just magically figure the type out.

Covariance

The application now passes the list into the MakeSchedule method, but that method expects an enumerable collection of Events. Parameters are covariant for generics, so it's possible to pass in a List of courses because Course is covariant to Event. This is covariance for parameters. You can read more about covariance and contravariance for generic types at https://docs.microsoft.com/en-us/dotnet/standard/generics/covariance-and-contravariance.