C# Pass Type As Generic Argument Essay

45.  Generic Collections in C#

In this chapter we will study different list interfaces and classes.

 

45.1.  Overview of Generic Collections in C#
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

We start by showing a type hierarchy of list-related types. The white boxes in Figure 45.1 are interfaces and the grey boxes are classes.

Figure 45.1    The class and interface inheritance tree related to Lists

All interfaces and classes seen in Figure 45.1, apart from and , will be discussed in the forthcoming sections of the current chapter.

The class (see Section 28.2 ) which conceptually is the superclass of all native array types in C#, also implements the generic interfaces . Notice, however, that 's implementation of is carried out by special means, and that it does not show up in the usual C# documentation. A more detailed discussion of the class is carried out in Section 47.1.

Version 3.5 of the .NET Framework contains a class, , that supports the mathematical set concept. As such, it is similar to the class , which we used as example for introduction of generic types in Section 42.1. is, however, much more efficient than .

 

45.2.  The Interface
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

At the most general level of Figure 45.1traversability is emphasized. This covers the ability to step through all elements of a collection. The interface announces one parameterless method called . The type parameter is the type of the elements in the collection.

  • Operations in the interface :
    • ( )

As the name indicates, returns an enumerator, which offers the following interface:

  • Operations in the interface :
    • ( )
    • ( )

We have discussed the non-generic versions of both interfaces in Section 31.6. An object is used as the basis of traversal in a loop.

Without access to an object it would not be possible to traverse the elements of a collection in a foreach loop. You do not very often use the operation explicitly in your own program, but you most probably rely on it implicitly! The reason is that many of your collections are traversed, from one end to the other, by use of foreach. The foreach control structure would not work without the operation . As you can see from Figure 45.1 all of our collections implement the interface and hereby they provide the operation .

It is worth noticing that an object of type does not support removal of elements from the collection. In C# it is therefore not allowed to remove elements during traversal of a collection in a foreach loop. In the Java counterpart to (called in Java), there is a method. The method can be called once for each step forward in the collection. is an optional operation in the Java interface. Consequently, removal of elements is not necessarily supported by all implementations of the Java interface.

 

45.3.  The Interface
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

At the next level of Figure 45.1 we encounter the interface. It can be summarized as follows.

  • Operations in the interface :
    • The operation prescribed in the superinterface
    • bool ( element)
    • void ( element)
    • bool ( element)
    • void ()
    • void ( targetArray, int startIndex)
    • int
    • bool

In addition to traversability, elements of type can be added to and removed from objects of type . At this level of abstraction, it is not specified where in the collection an element is added. As listed about, a few other operations are supported: Membership testing (), resetting (), copying of the collection to an array (), and measuring of size (). Some collections cannot be mutated once they have been created. The property allows us to find out if a given object is a read only collection.

 

45.4.  The Interface
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

At the next level of interfaces in Figure 45.1 we meet . This interface prescribes random access to elements.

  • Operations in the interface :
    • Those prescribed in the superinterfacesand
    • [int index]
    • int ( element)
    • void (int index, element)
    • void (int index)

In addition to , the type allows for indexed access to the elements. The first mentioned operation () is an indexer, and is its inverse operation. (See Chapter 19 for a general discussion of indexers). In addition, has operations for inserting and removing elements at given index positions.

 

45.5.  Overview of the class
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

We now encounter the first class in the collection hierarchy, namely . Most interfaces and classes discussed in this chapter belong to the namespace , but of some odd reason the class belongs to .

As can be seen from Figure 45.1 the generic class implements the generic interface . As such it supports all the operations of the three interfaces we discussed in Section 45.2 - Section 45.4. As it appears from Figure 45.1 the generic class implements the same interface. It turns out that is a minimal class which implements the three interfaces, and not much more. As we will see in Section 45.9, has many more operations, most of which are not prescribed by the interfaces it implement.

Basically, an instance of supports indexed access to its elements. Contrary to arrays, however, there is no limit on the number of elements in the collection. The generic class has another twist: It is well suited as a superclass for specialized (non-generic) collections. We will see why and how in Section 45.7.

Below we list the complete, public interface of :

  • Constructors
    • ,  
    • Via a collection initializer:
  • Element access
  • Measurement
  • Element addition
    • ,  
  • Element removal
    • ,   ,  
  • Searching
  • Boolean Queries
  • Conversions

Collection initializers are new in C# 3.0. Instead of initializing a collection via an , typically an array, such as in

Collection<int> lst = new Collection<int>(new int[]{1, 2, 3, 4});

it is possible in C# 3.0 to make use of collection initializers:

Collection<int> lst = new Collection{1, 2, 3, 4};

A collection initializer uses the method repeatedly to insert the elements within into an empty list.

Collection initializers are often used in concert with object initializers, see Section 18.4, to provide for smooth creation of collection of objects, which are instances of our own types.

You may be interested to know details of the actual representation (data structure) used internally in the generic class . Is it an array? Is it a linked list? Or is it something else, such as a mix of arrays and lists, or a tree structure? Most likely, it is a resizeable array. Notice however that from an object-oriented programming point of view (implying encapsulation and visibility control) it is inappropriate to ask such a question. It is sufficient to know about the interface of together with the time complexities of the involved operations. (As an additional remark, the source code of the C# libraries written by Microsoft is not generally available for inspection. Therefore we cannot easily check the representation details of the class). The interface of includes details about the execution times of the operations of relative to the size of a collection. We deal with timing issues of the operations in the collection classes in Section 45.17.

 

45.6.  Sample use of class
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

Let us now write a program that shows how to use the central operations in . In Program 45.1 we use an instance of the constructed class . Thus, we deal with a collection of character values. It is actually worth noticing that we in C# can deal with collections of value types (such as ) as well as collections of reference types (such as ).

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
using System; using System.Collections.ObjectModel; using System.Collections.Generic; class BasicCollectionDemo{ public static void Main(){ // Initialization - use of a collection initializer. After that add 2 elements. IList<char> lst = new Collection<char>{'a', 'b', 'c'}; lst.Add('d'); lst.Add('e'); ReportList("Initial List", lst); // Mutate existing elements in the list: lst[0] = 'z'; lst[1]++; ReportList("lst[0] = 'z'; lst[1]++;", lst); // Insert and push towards the end: lst.Insert(0,'n');ReportList("lst.Insert(0,'n');", lst); // Insert at end - with Insert: lst.Insert(lst.Count,'x');// equivalent to lst.Add('x'); ReportList("lst.Insert(lst.Count,'x');", lst); // Remove element 0 and pull toward the beginning: lst.RemoveAt(0);ReportList("lst.RemoveAt(0);", lst); // Remove first occurrence of 'c': lst.Remove('c');ReportList("lst.Remove('c');", lst); // Remove remaining elements: lst.Clear();ReportList("lst.Clear(); ", lst); } public static void ReportList<T>(string explanation, IList<T> list){ Console.WriteLine(explanation); foreach(T el in list) Console.Write("{0, 3}", el); Console.WriteLine(); Console.WriteLine(); } }
Program 45.1    Basic operations on a Collection of characters.

The program shown above explains itself in the comments, and the program output in Listing 45.2 is also relatively self-contained. Notice the use of the collection initializer in line 9 of Program 45.1. As mentioned in Section 45.5 collection initializers have been introduced in C# 3.0. In earlier versions of C# it was necessary to initialize a collection by use or an array initializer (see the discussion of Program 6.7) via the second constructor mentioned above.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Initial List a b c d e lst[0] = 'z'; lst[1]++; z c c d e lst.Insert(0,'n'); n z c c d e lst.Insert(lst.Count,'x'); n z c c d e x lst.RemoveAt(0); z c c d e x lst.Remove('c'); z c d e x lst.Clear();
Listing 45.2    Output of the program with basic operations on a Collection of characters.

We make the following important observations about the operations in :

  • The indexer     mutates an existing element in the collection
    • The length of the collection is unchanged
  • The operation splices a new element into the collection
    • Push subsequent elements towards the end of the collection
    • Makes the collection longer
  • The and operations take elements out of the collections
    • Pull subsequent elements towards the beginning of the collection
    • Makes the collection shorter

 

45.7.  Specialization of Collections
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

Let us now assume that we wish to make our own, specialized (non-generic) collection class of a particular type of objects. Below we will - for illustrative purposes - write a class called which is intended to hold instances of class . It is reasonable to program as a subclass of an existing collection class. In this section we shall see that is a good choice of superclass of .

The class depends on the class . You are invited to take a look at class via the accompanying slide . We do not include class here because it does not add new insight to our interests in collection classes. The four operations of class are shown below.

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
using System; using System.Collections.ObjectModel; public class AnimalFarm: Collection<Animal>{ protected override void InsertItem(int i, Animal a){ base.InsertItem(i,a); Console.WriteLine("**InsertItem: {0}, {1}", i, a); } protected override void SetItem(int i, Animal a){ base.SetItem(i,a); Console.WriteLine("**SetItem: {0}, {1}", i, a); } protected override void RemoveItem(int i){ base.RemoveItem(i); Console.WriteLine("**RemoveItem: {0}", i); } protected override void ClearItems(){ base.ClearItems(); Console.WriteLine("**ClearItems"); } }
Program 45.3    A class AnimalFarm - a subclass of - testing protected members.

It is important to notice that the four highlighted operations in Program 45.3 are redefinitions of virtual, protected methods in . Each of the methods activate the similar method in the superclass (this is method combination). In addition, they reveal on standard output that the protected method has been called. A more realistic example of class will be presented in Program 45.6.

The four operations are not part of the client interface of class . They are protected operations. The client interface of is identical to the public operations inherited from . It means that we use the operations , , etc. on instances of class .

We should now understand the role of the four protected operations , , , and relative to the operations in the public client interface. Whenever an element is inserted into a collection, the protected method is called. Both and are programmed by use of . Similarly, both and are programmed by use of . And so on. We see that the major functionality behind the operations in is controlled by the four protected methods , , , and .

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
using System; using System.Collections.ObjectModel; class App{ public static void Main(){ AnimalFarm af = new AnimalFarm(); // Populating the farm with Add af.Add(new Animal("elephant")); af.Add(new Animal("giraffe")); af.Add(new Animal("tiger")); ReportList("Adding elephant, giraffe, and tiger with Add(...)", af); // Additional population with Insert af.Insert(0, new Animal("dog")); af.Insert(0, new Animal("cat")); ReportList("Inserting dog and cat at index 0 with Insert(0, ...)", af); // Mutate the animal farm: af[1] = new Animal("herring", AnimalGroup.Fish, Sex.Male); ReportList("After af[1] = herring", af); // Remove tiger af.Remove(new Animal("tiger")); ReportList("Removing tiger with Remove(...)", af); // Remove animal at index 2 af.RemoveAt(2); ReportList("Removing animal at index 2, with RemoveAt(2)", af); // Clear the farm af.Clear(); ReportList("Clear the farm with Clear()", af); } public static void ReportList<T>(string explanation, Collection<T> list){ Console.WriteLine(explanation); foreach(T el in list) Console.WriteLine("{0, 3}", el); Console.WriteLine(); Console.WriteLine(); } }
Program 45.4    A sample client of AnimalFarm - revealing use of protected methods.

Take a close look at the output of Program 45.4 in Listing 45.5. The output explains the program behavior.

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
**InsertItem: 0, Animal: elephant **InsertItem: 1, Animal: giraffe **InsertItem: 2, Animal: tiger Adding elephant, giraffe, and tiger with Add(...) Animal: elephant Animal: giraffe Animal: tiger **InsertItem: 0, Animal: dog **InsertItem: 0, Animal: cat Inserting dog and cat at index 0 with Insert(0, ...) Animal: cat Animal: dog Animal: elephant Animal: giraffe Animal: tiger **SetItem: 1, Animal: herring After af[1] = herring Animal: cat Animal: herring Animal: elephant Animal: giraffe Animal: tiger **RemoveItem: 4 Removing tiger with Remove(...) Animal: cat Animal: herring Animal: elephant Animal: giraffe **RemoveItem: 2 Removing animal at index 2, with RemoveAt(2) Animal: cat Animal: herring Animal: giraffe **ClearItems Clear the farm with Clear()
Listing 45.5    Output from sample client of AnimalFarm.

 

45.8.  Specialization of Collections - a realistic example
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

The protected methods in class , as shown in Section 45.7, did only reveal if/when the protected methods were called by other methods. In this section we will show a more realistic example that redefines the four protected methods of in a more useful way.

In the example we program the following semantics of the insertion and removal operations of class

  • If we add an animal, an additional animal of the opposite sex is also added.
  • Any animal removal or clearing of an animal farm is rejected.

In addition, we add a operation to , which returns a collection (an sub animal farm) of all animals that belongs to a given group (such as all birds).

The class has not been changed, and it still available via accompanying slide.

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.ObjectModel; public class AnimalFarm: Collection<Animal>{ // Auto insert animal of opposite sex protected override void InsertItem(int i, Animal a){ if(a.Sex == Sex.Male){ base.InsertItem(i,a); base.InsertItem(i, new Animal(a.Name, a.Group, Sex.Female)); } else { base.InsertItem(i,a); base.InsertItem(i,new Animal(a.Name, a.Group, Sex.Male)); } } // Prevent removal protected override void RemoveItem(int i){ Console.WriteLine("[Removal denied]"); } // Prevent clearing protected override void ClearItems(){ Console.WriteLine("[Clearing denied]"); } // Return all male animals in a given group public AnimalFarm GetGroup(AnimalGroup g){ AnimalFarm res = new AnimalFarm(); foreach(Animal a in this) if (a.Group == g && a.Sex == Sex.Male) res.Add(a); return res; } }
Program 45.6    The class AnimalFarm - a subclass of .

Notice the way we implement the rejection in and : We do not call the superclass operation.

In Program 45.7 (only on web) we show an client program similar (but not not identical) to Program 45.4. The program output in Listing 45.8 (only on web) reveals the special semantics of the virtual, protected operations from - as redefined in Program 45.6.

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
using System; using System.Collections.ObjectModel; class App{ public static void Main(){ AnimalFarm af = new AnimalFarm(); // Populating the farm with Add af.Add(new Animal("elephant")); af.Add(new Animal("giraffe")); af.Add(new Animal("tiger")); ReportList("Adding elephant, giraffe, and tiger with Add(...)", af); // Additional population with Insert af.Insert(0, new Animal("blueJay", AnimalGroup.Bird)); af.Insert(0, new Animal("goldenEagle", AnimalGroup.Bird)); ReportList("Inserting blue jay and golden eagle at index 0 with Insert(0, ...)", af); // Extract birds: AnimalFarm birds = af.GetGroup(AnimalGroup.Bird); ReportList("The birds in farm - extraced with GetGroup", birds); // Remove tiger af.Remove(new Animal("tiger")); ReportList("Removing tiger with Remove(...)", af); // Remove animal at index 2 af.RemoveAt(2); ReportList("Removing animal at index 2, with RemoveAt(2)", af); // Clear the farm af.Clear(); ReportList("Clear the farm with Clear()", af); } public static void ReportList<T>(string explanation, Collection<T> list){ Console.WriteLine(explanation); foreach(T el in list) Console.WriteLine("{0, 3}", el); Console.WriteLine(); Console.WriteLine(); } }
Program 45.7    A sample client of AnimalFarm.

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
Adding elephant, giraffe, and tiger with Add(...) Animal: elephant(Female) Animal: elephant(Male) Animal: giraffe(Female) Animal: giraffe(Male) Animal: tiger(Female) Animal: tiger(Male) Inserting blue jay and golden eagle at index 0 with Insert(0, ...) Animal: goldenEagle(Female) Animal: goldenEagle(Male) Animal: blueJay(Female) Animal: blueJay(Male) Animal: elephant(Female) Animal: elephant(Male) Animal: giraffe(Female) Animal: giraffe(Male) Animal: tiger(Female) Animal: tiger(Male) The birds in farm - extraced with GetGroup Animal: goldenEagle(Female) Animal: goldenEagle(Male) Animal: blueJay(Female) Animal: blueJay(Male) [Removal denied] Removing tiger with Remove(...) Animal: goldenEagle(Female) Animal: goldenEagle(Male) Animal: blueJay(Female) Animal: blueJay(Male) Animal: elephant(Female) Animal: elephant(Male) Animal: giraffe(Female) Animal: giraffe(Male) Animal: tiger(Female) Animal: tiger(Male) [Removal denied] Removing animal at index 2, with RemoveAt(2) Animal: goldenEagle(Female) Animal: goldenEagle(Male) Animal: blueJay(Female) Animal: blueJay(Male) Animal: elephant(Female) Animal: elephant(Male) Animal: giraffe(Female) Animal: giraffe(Male) Animal: tiger(Female) Animal: tiger(Male) [Clearing denied] Clear the farm with Clear() Animal: goldenEagle(Female) Animal: goldenEagle(Male) Animal: blueJay(Female) Animal: blueJay(Male) Animal: elephant(Female) Animal: elephant(Male) Animal: giraffe(Female) Animal: giraffe(Male) Animal: tiger(Female) Animal: tiger(Male)
Listing 45.8    Output from sample client of AnimalFarm.

 

45.9.  Overview of the class
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

We are now going to study the generic class . As it appears from Figure 45.1 both and implement the same interface, namely , see Section 45.4. But as already noticed, offers many more operations than .

In the same style as in earlier sections, we provide an overview of the important operations of .

  • Constructors
    • ,   ,  
    • Via a collection initializer:
  • Element access
    • this,  
  • Measurement
  • Element addition
    • ,   ,   ,
  • Element removal
    • ,   ,   ,   ,  
  • Reorganization
    • ,   ,
      ,   ,
      ,  
  • Searching
    • ,   ,  
    • ,   ,   ,
      ,   ,   ,  
  • Boolean queries
    • ,   ,  
  • Conversions
    • ,   ,  

Compared with the class offers sorting, searching, reversing, and conversion operations. also has a number of "range operations" which operate on a number of elements via a single operation. We also notice a number of higher-order operations: Operations that take a delegate value (a function) as parameter. is a generic method which is parameterized with the type . accepts a function of delegate type which converts from type to .

 

45.10.  Sample use of class
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

In this and the following sections we will show how to use some of the operations in . We start with a basic example similar to Program 45.1 in which we work on a list of characters: . We insert a number of values into a list, and we remove some values as well. The program appears in Program 45.9 and the self-explaining output can be seen in Listing 45.10 (only on web). Notice in particular how the range operations (line 28) and (line 40) operate on the list.

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
using System; using System.Collections.Generic; /* Very similar to our illustration of class Collection<char> */ class BasicListDemo{ public static void Main(){ // List initialization and adding elements to the end of the list: List<char> lst = new List<char>{'a', 'b', 'c'}; lst.Add('d'); lst.Add('e'); ReportList("Initial list, followed by lst.Add('d'); lst.Add('e');", lst); // Mutate existing elements in the list lst[0] = 'z'; lst[1]++; ReportList("lst[0] = 'z'; lst[1]++;", lst); // Insert and push towards the end lst.Insert(0,'n');ReportList("lst.Insert(0,'n');", lst); // Insert at end - with Insert lst.Insert(lst.Count,'x');// equivalent to lst.Add('x'); ReportList("lst.Insert(lst.Count,'x');", lst); // Insert a new list into existing list, at position 2. lst.InsertRange(2, new List<char>{'1', '2', '3', '4'}); ReportList("lst.InsertRange(2, new List<char>{'1', '2', '3', '4'});", lst); // Remove element 0 and push toward the beginning lst.RemoveAt(0);ReportList("lst.RemoveAt(0);", lst); // Remove first occurrence of 'c' lst.Remove('c');ReportList("lst.Remove('c');", lst); // Remove 2 elements, starting at element 1 lst.RemoveRange(1, 2);ReportList("lst.RemoveRange(1, 2);", lst); // Remove all remaining digits lst.RemoveAll(delegate(char ch){return Char.IsDigit(ch);});ReportList("lst.RemoveAll(delegate(char ch){return Char.IsDigit(ch);});", lst); // Test of all remaining characters are letters if (lst.TrueForAll(delegate(char ch){return Char.IsLetter(ch);})) Console.WriteLine("All characters in lst are letters"); else Console.WriteLine("NOT All characters in lst are letters"); } public static void ReportList<T>(string explanation, List<T> list){ Console.WriteLine(explanation); foreach(T el in list) Console.Write("{0, 3}", el); Console.WriteLine(); Console.WriteLine(); } }
Program 45.9    Basic operations on a List of characters.

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
Initial list, followed by lst.Add('d'); lst.Add('e'); a b c d e lst[0] = 'z'; lst[1]++; z c c d e lst.Insert(0,'n'); n z c c d e lst.Insert(lst.Count,'x'); n z c c d e x lst.InsertRange(2, new List<char>{'1', '2', '3', '4'}); n z 1 2 3 4 c c d e x lst.RemoveAt(0); z 1 2 3 4 c c d e x lst.Remove('c'); z 1 2 3 4 c d e x lst.RemoveRange(1, 2); z 3 4 c d e x lst.RemoveAll(delegate(char ch){return Char.IsDigit(ch);}); z c d e x All characters in lst are letters
Listing 45.10    Output of the program with basic operations on a List of characters.

 

45.11.  Sample use of the Find operations in
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

In this section we will illustrate how to use the search operations in . More specifically, we will apply the methods , and on an instance of , where is a type, such as defined by the struct in Program 14.12. The operations discussed in this section do all use linear search. It means that they work by looking at one element after the other, in a rather trivial way. As a contrast, we will look at binary search operations in Section 45.13, which searches in a "more advanced" way.

In the program below - Program 45.11 - we declare a in line 11, and we add six points to the list in line 13-16. In line 20 we shown how to use to locate the first point in the list whose x-coordinate is equal to 5. The same is shown in line 25. The difference between the two uses of is that the first relies on a delegate given on the fly: , while the other relies on an existing static method (defined in line 40 - 42). The approach shown in line 20 is, in my opinion, superior.

In line 29 we show how to use the variant , which returns a list instead of just a single , as returned by . In line 36 we show how can be used to find the index of a given in a list. It is worth asking how the parameter of is compared with the points in list. The documentation states that the points are compared by use of the default equality comparer of the type , which in our case is struct . We have discussed the default equality comparer in Section 42.9 in the slipstream of our coverage of the generic interfaces and .

We use the static method to show a list on standard output. We call several times in Program 45.11. The program output is shown in Listing 45.12.

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
using System; using System.Collections.Generic; class C{ public static void Main(){ System.Threading.Thread.CurrentThread.CurrentCulture = new System.Globalization.CultureInfo("en-US"); List<Point> pointLst = new List<Point>(); // Construct points and point list: pointLst.Add(new Point(0,0)); pointLst.Add(new Point(5, 9)); pointLst.Add(new Point(5,4)); pointLst.Add(new Point(7.1,-13)); pointLst.Add(new Point(5,-2)); pointLst.Add(new Point(14,-3.4)); ReportList("Initial point list", pointLst); // Find first point in list with x coordinate 5 Point p = pointLst.Find(delegate(Point q){return (q.Getx() == 5);}); Console.WriteLine("Found with delegate predicate: {0}\n", p); // Equivalent. Use predicate which is a static method p = pointLst.Find(new Predicate<Point>(FindX5)); Console.WriteLine("Found with static member predicate: {0}\n", p); // Find all points in list with x coordinate 5 List<Point> resLst = new List<Point>(); resLst = pointLst.FindAll(delegate(Point q){return (q.Getx() == 5);}); ReportList("All points with x coordinate 5", resLst); // Find index of a given point in pointLst. // Notice that Point happens to be a struct - thus value comparison Point searchPoint = new Point(5,4); Console.WriteLine("Index of {0} {1}", searchPoint, pointLst.IndexOf(searchPoint)); } public static bool FindX5(Point p){ return p.Getx() == 5; } public static void ReportList<T>(string explanation,List<T> list){ Console.WriteLine(explanation); int cnt = 0; foreach(T el in list){ Console.Write("{0, 3}", el); cnt++; if (cnt%4 == 0) Console.WriteLine(); } if (cnt%4 != 0) Console.WriteLine(); Console.WriteLine(); } }
Program 45.11    Sample uses of List.Find.

1 2 3 4 5 6 7 8 9 10 11 12
Initial point list Point:(0,0). Point:(5,9). Point:(5,4). Point:(7.1,-13). Point:(5,-2). Point:(14,-3.4). Found with delegate predicate: Point:(5,9). Found with static member predicate: Point:(5,9). All points with x coordinate 5 Point:(5,9). Point:(5,4). Point:(5,-2). Index of Point:(5,4). 2
Listing 45.12    Output from the Find program.

 

45.12.  Sample use of Sort in
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

As a client user of the generic class it is likely that you never need to write a sorting procedure! You are supposed to use one of the already existing methods in .

Sorting the elements in a collection of elements of type depends on a less than or equal operation on . If the type is taken directly from the C# libraries, it may very well be the case that we can just use the default less than or equal operation of the type . If is one of our own types, we will have to supply an implementation of the comparison operation ourselves. This can be done by passing a delegate object to the method.

Below, in Program 45.13 we illustrate most of the four overloaded operations in . The actual type parameter in the example, passed for , is . The program output (the lists before and after sorting) is shown in Listing 45.14 (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
using System; using System.Collections.Generic; class C{ public static void Main(){ List<int> listOriginal = new List<int>{5, 3, 2, 7, -4, 0}, list; // Sorting by means of the default comparer of int: list = new List<int>(listOriginal); ReportList(list); list.Sort(); ReportList(list); Console.WriteLine(); // Equivalent - explicit notatation of the Comparer: list = new List<int>(listOriginal); ReportList(list); list.Sort(Comparer<int>.Default); ReportList(list); Console.WriteLine(); // Equivalent - explicit instantiation of an IntComparer: list = new List<int>(listOriginal); ReportList(list); list.Sort(new IntComparer()); ReportList(list); Console.WriteLine(); // Similar - use of a delegate value for comparison: list = new List<int>(listOriginal); ReportList(list); list.Sort(delegate(int x, int y){ if (x < y) return -1; else if (x == y) return 0; else return 1;}); ReportList(list); Console.WriteLine(); } public static void ReportList<T>(List<T> list){ foreach(T el in list) Console.Write("{0, 3}", el); Console.WriteLine(); } } public class IntComparer: Comparer<int>{ public override int Compare(int x, int y){ if (x < y) return -1; else if (x == y) return 0; else return 1; } }
Program 45.13    Four different activations of the List.Sort method.

Throughout Program 45.13 we do several sortings of , as declared in line 8. In line 14 we rely the default comparer of type . The default comparer is explained in the following way in the .NET framework documentation of :

This method uses the default comparer . for type to determine the order of list elements. The . property checks whether type implements the generic interface and uses that implementation, if available. If not, . checks whether type implements the interface. If type does not implement either interface, . throws an .

The sorting done in line 21 is equivalent to line 14. In line 21 we show how to pass the default comparer of type explicitly to the method.

Let us now assume the type does not have a default comparer. In other words, we will have to implement the comparer ourselves. The call of in line 28 passes a new instance to . The class is programmed in line 53-61, at the bottom of Program 45.13. Notice that is a subclass of , which is an abstract class in the namespace with an abstract method named . The generic class is in many ways similar to the class , which we touched on in Section 42.9. Most important, both have a static property, which returns a comparer object.

As a final resort that always works we can pass a comparer function to . In C#, such a function is programmed as a delegate. (Delegates are discussed in Chapter 22). Line 35-40 shows how this can be done. Notice that the delegate we use is programmed on the fly. This style of programming is a reminiscence of functional programming.

I find it much more natural to pass an ordering method instead of an object of a class with an ordering method. (The latter is a left over from older object-oriented programming languages in which the only way to pass a function as parameter is via an object of a class in which is an instance method). In general, I also prefer to be explicit about the ordering instead of relying on some default ordering which may turn out to surprise you.

5 3 2 7 -4 0 -4 0 2 3 5 7 5 3 2 7 -4 0 -4 0 2 3 5 7 5 3 2 7 -4 0 -4 0 2 3 5 7 5 3 2 7 -4 0 -4 0 2 3 5 7
Listing 45.14    Output of the sorting program.

Let us summarize the lessons that we have learned from the example:

  • Some types have a default comparer which is used by
  • The default comparer of T can extracted by
  • An anonymous delegate comparer is attractive if the default comparer of the type does not exist, of if it is inappropriate.

Exercise 12.1. Shuffle List

Write a operation that disorders the elements of a collection in a random fashion. A shuffle operation is useful in many context. There is no operation in . In the similar Java libraries there is a shuffle method.

In which class do you want to place the operation? You may consider to make use of extension methods.

You can decide on programming either a mutating or a non-mutating variant of the operation. Be sure to understand the difference between these two options.

Test the operation on . The class (representing a playing card) is one of the classes we have seen earlier in the course.

Solution

Exercise 12.2. Course and Project classes

In the earlier exercise about courses and projects (found in the lecture about abstract classes and interfaces) we refined the program about , , and to use a common superclass called . Revise your solution (or the model solution) such that the courses in the class are represented as a variable of type instead of by use of four variables of type .

Reimplement and simplify the method in class . Take advantage of the new representation of the courses in a project, such that the "3 out of 4 rule" (see the original exercise) is implemented in a more natural way.

Solution

 

45.13.  Sample use of BinarySearch in
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

The search operations discussed in Section 45.11 all implemented linear search processes. The search operations of this section implement binary search processes, which are much faster when applied on large collections. On collections of size n, linear search has - not surprisingly - time complexity O(n). Binary search has time complexity O(log n). When n is large, the difference between n and log n is dramatic.

The operations in require, as a precondition, that the list is ordered before the search is performed. If necessary, the operation (see Section 45.12) can be used to establish the ordering.

You may ask why we should search for an element which we - in the starting point - is able to pass as input to the method. There is a couple of good answers. First, we may be interested to know if the element is present or not in the list. Second, it may also be possible to search for an incomplete object (by only comparing some selected fields in the method). Using this approach we are actually interested in finding the complete object, with all the data fields, in the collection.

If the operation finds an element in the list, the index of the element is returned. This is a non-negative integer. If the element is not found, a negative integer, say i, is returned. Below we will see that that -i (or more precisely the bitwise complement ~i) in that case is the position of the element, if it had been present in the list.

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
using System; using System.Collections.Generic; class BinarySearchDemo{ public static void Main(){ System.Threading.Thread.CurrentThread.CurrentCulture = new System.Globalization.CultureInfo("en-US"); List<Point> pointLst = new List<Point>(); // Point is a struct. // Construct points and point list: pointLst.Add(new Point(0,0)); pointLst.Add(new Point(5, 9)); pointLst.Add(new Point(5,4)); pointLst.Add(new Point(7.1,-13)); pointLst.Add(new Point(5,-2)); pointLst.Add(new Point(14,-3.4)); ReportList("The initial point list", pointLst); // Sort point list, using a specific point Comparer. // Notice the PointComparer: // Ordering according to sum of x and y coordinates IComparer<Point> pointComparer = new PointComparer(); pointLst.Sort(pointComparer); ReportList("The sorted point list", pointLst); int res; Point searchPoint; // Run-time error. // Failed to compare two elements in the array. // searchPoint = new Point(5,4); // res = pointLst.BinarySearch(searchPoint); // Console.WriteLine("BinarySearch for {0}: {1}", searchPoint, res); searchPoint = new Point(5,4); res = pointLst.BinarySearch(searchPoint, pointComparer); Console.WriteLine("BinarySearch for {0}: {1}", searchPoint, res); searchPoint = new Point(1,8); res = pointLst.BinarySearch(searchPoint, pointComparer); Console.WriteLine("BinarySearch for {0}: {1}", searchPoint, res); } public static void ReportList<T>(string explanation,List<T> list){ Console.WriteLine(explanation); int cnt = 0; foreach(T el in list){ Console.Write("{0, 3}", el); cnt++; if (cnt%4 == 0) Console.WriteLine(); } if (cnt%4 != 0) Console.WriteLine(); Console.WriteLine(); } } // Compare the sum of the x and y coordinates. // Somewhat non-traditional! public class PointComparer: Comparer<Point>{ public override int Compare(Point p1, Point p2){ double p1Sum = p1.Getx() + p1.Gety(); double p2Sum = p2.Getx() + p2.Gety(); if (p1Sum < p2Sum) return -1; else if (p1Sum == p2Sum) return 0; else return 1; } }
Program 45.15    Sample uses of List.BinarySearch.

Program 45.15 works on a list of points. Six points are created and inserted into a list in line 13-16. Next, in line 23, the list is sorted. As it appears from the comparer programmed in line 62-72, a point p is less than or equal to point q, if p.x + p.y <= q.x + q.y. You may think that this is odd, but it is our decision for this particular program example.

In line 33 we attempt to activate binary searching by use of the default comparer. But such a comparer does not exist for class Point. This problem is revealed at run-time.

In line 37 and 41 we search for the points (5,4) and (1,8) respectively. In both cases we expect to find the point (5,4), which happens to be located at place 3 in the sorted list. The output of the program, shown in Program 45.17 (only on web) confirms this.

The initial point list Point:(0,0). Point:(5,9). Point:(5,4). Point:(7.1,-13). Point:(5,-2). Point:(14,-3.4). The sorted point list Point:(7.1,-13). Point:(0,0). Point:(5,-2). Point:(5,4). Point:(14,-3.4). Point:(5,9). BinarySearch for Point:(5,4). : 3 BinarySearch for Point:(1,8). : 3
Listing 45.16    Output from the BinarySearch program.

In the next program, Program 45.17 we illustrate what happens if we search for a non-existing point with . The class and the generic method are not shown in the paper version of Program 45.17. Please consult Program 45.15 where they both appear.

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
using System; using System.Collections.Generic; class BinarySearchDemo{ public static void Main(){ System.Threading.Thread.CurrentThread.CurrentCulture = new System.Globalization.CultureInfo("en-US"); List<Point> pointLst = new List<Point>(); // Construct points and point list: pointLst.Add(new Point(0,0)); pointLst.Add(new Point(5, 9)); pointLst.Add(new Point(5,4)); pointLst.Add(new Point(7.1,-13)); pointLst.Add(new Point(5,-2)); pointLst.Add(new Point(14,-3.4)); ReportList("Initial point list", pointLst); // Sort point list, using a specific point Comparer: IComparer<Point> pointComparer = new PointComparer(); pointLst.Sort(pointComparer); ReportList("Sorted point list", pointLst); int res; Point searchPoint; searchPoint = new Point(1,1); res = pointLst.BinarySearch(searchPoint, pointComparer); Console.WriteLine("BinarySearch for {0}: {1}\n", searchPoint, res); if (res < 0){ // search point not found pointLst.Insert(~res, searchPoint); // Insert searchPoint such // that pointLst remains sorted Console.WriteLine("Inserting {0} at index {1}", searchPoint, ~res); ReportList("Point list after insertion", pointLst); } } public static void ReportList<T>(string explanation,List<T> list){ Console.WriteLine(explanation); int cnt = 0; foreach(T el in list){ Console.Write("{0, 3}", el); cnt++; if (cnt%4 == 0) Console.WriteLine(); } if (cnt%4 != 0) Console.WriteLine(); Console.WriteLine(); } } // Compare the sum of the x and y coordinates. // Somewhat non-traditional! public class PointComparer: Comparer<Point>{ public override int Compare(Point p1, Point p2){ double p1Sum = p1.Getx() + p1.Gety(); double p2Sum = p2.Getx() + p2.Gety(); if (p1Sum < p2Sum) return -1; else if (p1Sum == p2Sum) return 0; else return 1; } }
Program 45.17    Searching for a non-existing Point.

The scene of Program 45.17 is the same as that of Program 45.15. In line 28 we do binary searching, looking for the point (1,1). None of the points in the program have an "x plus y sum" of 2. Therefore, the point (1,1) is not located by . The method returns a negative ghost index. The ghost index is the bitwise complement of the index where to insert the point in such a way that the list will remain sorted. (Notice the bitwise complement operation which turns 0 to 1 and 1 to 0 at the binary level). The program output reveals that position ~(-3) is the natural place of the point (1,1) to maintain the ordering of the list. Notice that the value of ~(-3) is 2, due the use of two's complement arithmetic. This explains the rationale of the negative values returned by .

The output of Program 45.17

Let's first talk about pure parametric polymorphism and get into bounded polymorphism later.

Parametric Polymorphism

What does parametric polymorphism mean? Well, it means that a type, or rather type constructor is parameterized by a type. Since the type is passed in as a parameter, you cannot know in advance what it might be. You cannot make any assumptions based on it. Now, if you don't know what it might be, then what is the use? What can you do with it?

Well, you could store and retrieve it, for example. That's the case you already mentioned: collections. In order to store an item in a list or an array, I need to know nothing about the item. The list or array can be completely oblivious to the type.

But what about the type? If you are not familiar with it, is a type which maybe has a value and maybe doesn't. Where would you use it? Well, for example, when getting an item out of a dictionary: the fact that an item might not be in the dictionary is not an exceptional situation, so you really shouldn't throw an exception if the item isn't there. Instead, you return an instance of a subtype of , which has exactly two subtypes: and . is another candidate of something that really should return a instead of throwing an exception or the whole dance.

Now, you might argue that is kinda-sorta like a list which can only have zero or one elements. And thus kinda-sorta a collection.

Then what about ? It's a type which promises to return a value at some point in the future, but doesn't necessarily have a value right now.

Or what about ? How would you represent the concept of a function from one type to another type if you cannot abstract over types?

Or, more generally: considering that abstraction and reuse are the two fundamental operations of software engineering, why wouldn't you want to be able to abstract over types?

Bounded Polymorphism

So, let's now talk about bounded polymorphism. Bounded polymorphism is basically where parametric polymorphism and subtype polymorphism meet: instead of a type constructor being completely oblivious about its type parameter, you can bind (or constrain) the type to be a subtype of some specified type.

Let's go back to collections. Take a hashtable. We said above that a list doesn't need to know anything about its elements. Well, a hashtable does: it needs to know that it can hash them. (Note: in C#, all objects are hashable, just like all objects can be compared for equality. That's not true for all languages, though, and is sometimes considered to be design mistake even in C#.)

So, you want to constrain your type parameter for the key type in the hashtable to be an instance of :

Imagine if instead you had this:

What would you do with a you get out of there? You can't do anything with it, you only know it's an object. And if you iterate over it, all you get yielded is a pair of something you know is an (which doesn't help you much because it only has one property ) and something you know is an (which helps you even less).

Or something based on your example:

The item needs to be serializable because it is going to be stored on disk. But what if you have this instead:

With the generic case, if you put a in, you get a back, with methods and properties like , , , , , etc. Something you can work with. Now, the other case? You put in a but you get back a , which has just one property: . What are you going to do with that?

There are also some neat tricks you can do with bounded polymorphism:

F-bounded polymorphism

F-bounded quantification is basically where the type variable appears again in the constraint. This can be useful in some circumstances. E.g. how do you write an interface? How do you write a method where the return type is the type of the implementing class? In a language with a MyType feature, that's easy:

In a language with bounded polymorphism, you can do something like this instead:

Note that this is not as safe as the MyType version, because there is nothing stopping someone from simply passing the "wrong" class to the type constructor:

Abstract Type Members

As it turns out, if you have abstract type members and subtyping, you can actually get by completely without parametric polymorphism and still do all the same things. Scala is heading in this direction, being the first major language that started out with generics and then trying to remove them, which is exactly the other way around from e.g. Java and C#.

Basically, in Scala, just like you can have fields and properties and methods as members, you can also have types. And just like fields and properties and methods can be left abstract to be implemented in a subclass later, type members can also be left abstract. Let's go back to collections, a simple , that would look something like this, if it were supported in C#:

Categories: 1

0 Replies to “C# Pass Type As Generic Argument Essay”

Leave a comment

L'indirizzo email non verrĂ  pubblicato. I campi obbligatori sono contrassegnati *