Generic Collection Classes

Many generic interfaces and collection classes are defined in the namespace System.Collections.Generic. These classes can be used instead of the collection classes that were discussed in Chapter 9, "Collections." Many of the classes dealt with in the previous chapter have a similar generic class, so this section does not differentiate between a list and a dictionary but focuses on generic features instead.

Generic Collections Overview

Before taking a closer look at how to use the collection classes, this section gives you an overview of which generic collection classes and interfaces are available.

The major interfaces and their functionality are defined in the following table.

Interface	Methods and Properties	Description
ICollection<T>	Add(), Clear(), Contains(), CopyTo(), Remove() Count, IsReadOnly	The interface ICollection<T> is implemented by collection classes. Methods of this interface can be used to add and remove elements from the collection. The generic interface ICollection<T> inherits from the non-generic interface IEnumerable. With this it is possible to pass objects implementing ICollection<T> to methods that require IEnumerable objects as parameters.
IList<T>	Insert(), RemoveAt(), IndexOf() Item	The interface IList<T> allows you to access a collection using an indexer. It is also possible to insert or remove elements at any position of the collection. Similar to ICollection<T>, the interface IList<T> inherits from IEnumerable.
IEnumerable<T>	GetEnumerator()	The interface IEnumerable<T> is required if a foreach statement is used with the col- lection. This interface defines the method GetEnumerator() that returns an enumer- ator implementing IEnumerator<T>. The generic interface IEnumerable<T> inherits from the non-generic interface IEnumerable.
IEnumerator<T>	Current	The foreach statement uses an enumerator implementing IEnumerator<T> for access- ing all elements in a collection. The interface IEnumerator<T> inherits from the non-generic interfaces IEnumerator and IDisposable. The interface IEnumerator defines the methods MoveNext() and Reset(), IEnumerator<T> defines the type-safe version of the property Current.
IDictionary <TKey, TValue>	Add(),ContainsKey(), Remove(),TryGetValue(), Item, Keys, Values	The interface IDictionary<K, V> is implemented by collections whose elements have a key and a value.
IComparer<T>	Compare()	The interface IComparer<T> is used to sort elements inside a collection with the Compare() method.
IEquality Comparer<T>	Equals(),GetHashCode()	IEqualityComparer<T> is the second interface to compare objects. With this inter- face the objects can be compared for equal- ity. The method GetHashCode() should return a unique value for every object. The method Equals() returns true if the objects are equal, false otherwise.

The generic collection classes and their functionality are shown in the following table.

Class	Implemented Interfaces	Description
List<T>	IList<T> ICollection<T> IEnumerable<T>	The List<T> class is the generic replacement for the ArrayList class. Similarly to the ArrayList class, the List<T> class can grow and shrink dynamically. Besides the implementa- tion of the three implemented inter- faces, this class also supports additional functionality like sorting and reversing the elements in the collection.
Dictionary <TKey, TValue>	IDictionary<TKey, TValue> ICollection<KeyValuePair <TKey, TValue>> IEnumerable <KeyValuePair <TKey, TValue>> ISerializable IDeserializationCallback	Dictionary<TKey, TValue> is a collection class that stores key and value pairs.
SortedList <TKey, TValue>	IDictionary<TKey, TValue> ICollection<KeyValuePair <TKey, TValue>> IEnumerable<KeyValuePair <TKey, TValue>>	SortedList<TKey, TValue> is similar to Dictionary<TKey, TValue> with the difference that this collection is sorted by the key.
LinkedList<T>	ICollection<T> IEnumerable<T> ISerializable IDeserializationCallback	LinkedList<T> is a double-linked list. With a double-linked list one element references the next and the previous.
Queue<T>	ICollection<T> IEnumerable<T>	Queue<T> is a collection with first-in, first-out behavior. The element that was added first will be read first from the queue. This is similar to a print-queue where the oldest print jobs are pro- cessed first.
		The method Enque() adds an object to the end of the queue; the method Deque() returns and removes an object from the beginning of the queue. With the method Peek() it is possible to read the first object from the queue without removing it.
Stack<T>	ICollection<T> IEnumerable<T>	Stack<T> is a collection with first-in, last-out behavior. The element that was added last will be read first from the stack. The Stack<T> offers the methods Push() and Pop(). With Push() an object is added to the end of the stack, while Pop() reads and removes the object from the end of the stack. The method Peek() reads the last object from the stack without removing it.

The .NET Framework offers some generic collection base classes that can be used to create a custom generic collection class. The classes in the following table are found in the namespace System. Collections.ObjectModel.

Class	Implemented Interfaces	Description
Collection<T>	IList<T> ICollection<T> IEnumerable<T>	The class Collection<T> can be used as a base class for a custom generic collection class. It implements the inter- faces IList<T>, ICollection<T>, and IEnumerable<T>. Behind the scenes, this class makes use of the List<T> class. However, it doesn't offer all the methods that List<T> does. So with a custom generic collection class you can offer the methods that are appropriate for the use case. With a custom collection class you can access the underlying List<T> object with the protected property Items.
ReadOnly Collection<T>	IList<T> ICollection<T> IEnumerable<T>	ReadOnlyCollection<T> is a read- only version of the class Collection<T>. All the methods from the interfaces that allow adding and removing elements are explicitly implemented and throw a NotSupportedException. An object of this class can be created by passing any collection that implements the IList<T> interface to the constructor.
KeyedCollection <TKey, TItem>	IList<TItem> ICollection<TItem> IEnumerable<TItem>	KeyedCollection<TKey, TItem> is an abstract base class that can be used for custom collection classes that have a key and a value. This class inherits from Collection<TItem>.

Using the List<T> Class

The class List<T> in the namespace System.Collections.Generic is a very similar in its usage to the ArrayList class from the namespace System.Collections. This class implements the IList, ICollection, and IEnumerable interfaces. Because Chapter 9 already discussed the methods of these interfaces, this section looks at how to use the List<T> class.

The following example uses the class Racer as elements to be added to the collection to represent a Formula-1 racer. This class has two fields, a name and a car, that can be accessed with properties. With the constructor of the class the name of the racer and the car can be passed to set the members. The method ToString() is overridden to return the name of the racer and the car:

 public class Racer { private string name; public string Name { get { return name; } } private string car; public string Car { get { return car; } } public Racer(string name, string car) { this.name = name; this.car = car; } public override string ToString() { return name + ", " + car; } } 

The variable racers is defined to be of type List<Racer>. With the new operator a new object of the same type is created. Here the default constructor of the List<T> class is used. This class also has a constructor to reserve memory for a specific number of items, and a constructor to copy elements from another collection of type List<T>.

Because the class List<T> was instantiated with the concrete class Racer, now only Racer objects can be added with the Add() method. With the class List<T>, the Add() method is defined as void Add(T item). In the following sample code five Formula-1 racers are created and added to the collection. Then, using the foreach statement, every team in the collection is iterated to be displayed on the console:

 List<Racer> racers = new List<Racer>(); racers.Add(new Racer("Michael Schumacher", "Ferrari")); racers.Add(new Racer("Juan Pablo Montoya", "McLaren-Mercedes")); racers.Add(new Racer("Kimi Raikkonen", "McLaren-Mercedes")); racers.Add(new Racer("Mark Webber", "Williams-BMW")); racers.Add(new Racer("Rubens Barichello", "Ferrari")); foreach (Racer r in racers) { Console.WriteLine(r); } 

With the List<T> class, not only can you add items and access them by using an enumerator; this class also has methods to insert and remove elements, clear the collection, and copy the elements to an array. Even more powerful functionality is discussed next. List<T> offers methods to search and to convert elements, reverse the order, and so on.

Finding elements

In this section, you search for all racers in the collection that drive a Ferrari.

The List<T> class offers Find() and FindAll() methods with these declarations:

 public T Find(Predicate<T> match);  public List<T> FindAll(Predicate<T> match); 

Both methods require a Predicate<T> as an argument. Predicate<T> is a delegate that references a predicate method. A predicate is a method that returns a Boolean value. If the predicate returns true, there's a match and the element is found. If it returns false, the element is not added to the result of the search. With the definition of Predicate<T>, the predicate must have a single argument of type T. The Find() method returns the first element with a predicate match, and the FindAll() method returns all elements with a predicate match in a list collection.

So you have to define a predicate. You use the predicate method DrivingCarPredicate() for finding a racer with a specific car. This method is defined in the class FindRacer, which can be initialized with the car to search. DrivingCarPredicate() receives a Racer object and compares the car of the Racer object with the car that is set in the constructor to return true or false accordingly:

 public class FindRacer { private string car; public FindRacer(string car) { this.car = car; } public bool DrivingCarPredicate(Racer racer) { return racer.Car == car; } } 

To find the specific racers, the FindRacer class is initiated and initialized with a Ferrari, because you want to find all Ferrari racers. With the FindAll() method of the List<T> class, a new predicate delegate is instantiated, and this predicate delegate receives the finder.DrivingCarPredicate method. FindAll() returns a list of type List<Racer> that is used with the foreach to iterate all returned racers to display them on the console:

 FindRacer finder = new FindRacer("Ferrari"); foreach (Racer racer in  racers.FindAll(new Predicate<Racer>(finder.DrivingCarPredicate))) { Console.WriteLine(racer); } 

As a result, Michael Schumacher and Rubens Barichello are displayed on the console.

Performing some action

Template delegates are not only used with the Find()/FindAll() methods; they are also used to perform some action with every element. The List<T> class offers a ForEach() method that uses an Action<T> delegate to perform some action with every element in the collection. The delegate Action<T> has a void return type.

In the example, the ForEach() method is used to display every racer to the console. Because here you just iterate through all racer objects and other initialization data is not needed with the iteration (such as the car with the FindAll() method), an anonymous method that has a Racer parameter is defined. The implementation of the anonymous method writes the racer to the console:

 racers.ForEach(delegate(Racer r) { Console.WriteLine(r); }); 

Note

Anonymous methods are discussed in Chapter 6, "Delegates and Events."

If only the racers where the previously used predicate applies should be written to the console, the methods ForEach() and FindAll() can be combined. With the list returned from FindAll(), the ForEach() method is invoked:

 // display all Ferrari drivers on the console FindRacer finder = new FindRacer("Ferrari"); racers.FindAll(new Predicate<Racer>(finder.DrivingCarPredicate)). ForEach(delegate(Racer r) { Console.WriteLine(r); }); 

This way, the complete foreach code block can be reduced to a single line of code. Of course it takes some time to get used to this coding style. If the implementation of anonymous methods are needed more than once, don't use anonymous methods. A helper method can do the task and help with reuse.

Sorting

The List<T> class allows sorting its elements. The Sort() method has several overloads defined. The arguments that can be passed are a generic delegate Comparison<T>, the generic interface IComparer<T>, and a range together with the generic interface IComparer<T>:

 public void List<T>.Sort(); public void List<T>.Sort(Comparison<T>); public void List<T>.Sort(IComparer<T>); public void List<T>.Sort(Int32, Int32, IComparer<T>); 

The Sort() method without arguments is possible only if the elements in the collection implement the interface IComparable.

Comparison<T> is a delegate to a method that has two parameters of type T and a return type int. If the parameter values are equal, the method must return 0. If the first parameter is less than the second, a value less than zero must be returned; otherwise a value greater than zero is returned.

With a simple implementation for the comparison method, an anonymous method can be used. The two parameters are of type Racer, and in the implementation the Name properties are compared by using the string method CompareTo():

 racers.Sort(delegate(Racer r1, Racer r2) {  return r1.Name.CompareTo(r2.Name); }); 

After the method has been invoked, the complete racer list is sorted based on the name of the racer.

Instead of using a delegate, the interface IComparer<T> also can be used to sort the collection. The class RacerComparer implements the interface IComparer<T> for Racer types. This class allows you to sort either by the name of the racer or by the car. Whether the sort should happen by the name or by the car is defined with the inner enumeration type CompareType. The CompareType is set with the constructor of the class RacerComparer. The interface IComparer<Racer> defines the method Compare that is required for sorting. In the implementation of this method, the CompareTo() method of the String class is used — either on the car or on the name:

 public class RacerComparer : IComparer<Racer> { public enum CompareType { Name, Car } private CompareType compareType; public RacerComparer(CompareType compareType) { this.compareType = compareType; } public int Compare(Racer x, Racer y) { int result = 0; switch (compareType) { case CompareType.Name: result = x.Name.CompareTo(y.Name); break; case CompareType.Car: result = x.Car.CompareTo(y.Car); break; } return result; } } 

When the racers collection is sorted, a new instance of the RacerComparer class is passed, and here the sort is done by the car:

 racers.Sort(new RacerComparer(RacerComparer.CompareType.Car)); 

Type conversion

With the List<T> method ConvertAll(), all types of a collection can be converted to a different type. The ConvertAll() method uses a Converter delegate that is defined like this:

 public sealed delegate TOutput Converter<TInput, TOutput>(TInput from); 

The generic types TInput and TOutput are used with the conversion. TInput is the argument of the delegate method and TOutput is the return type.

In this example all Racer types should be converted to Person types. Whereas the Racer type contains a name and a car, the Person type contains a firstname and a lastname. For the conversion, the car of the racer can be ignored but the name must be converted to a firstname and lastname:

 public class Person { private string firstname; private string lastname; public Person(string firstname, string lastname) { this.firstname = firstname; this.lastname = lastname; } public override string ToString() { return firstname + " " + lastname; } } 

The conversion happens by invoking the racers.ConvertAll<Person>() method. The argument of this method is defined as an anonymous method with an argument of type Racer and a Person type that is returned. In the implementation of the anonymous method a new Person object is created and returned. For the Person object, the Name of the Racer is converted to firstname and lastname:

 List<Person> persons = racers.ConvertAll<Person>(delegate(Racer r) { int ixSeparator = r.Name.LastIndexOf(' ') + 1; string lastname = r.Name.Substring(ixSeparator,  r.Name.Length - ixSeparator); string firstname = r.Name.Substring(0, ixSeparator - 1); return new Person(firstname, lastname);  }); 

The result of the conversion is a list containing the converted Person objects: persons of type List<Person>.

Using the Queue<T> Class

The class Queue<T> has the same functionality as the Queue class discussed in Chapter 9; that is, it is just a generic version of a queue. Elements are processed First-In, First-Out (FIFO).

The sample application for the Queue<T> class is a document management application. One thread is used to add documents to the queue, and another thread reads documents from the queue and processes them.

The elements stored in the queue are of type Document. The Document class defines a title and content:

 public class Document { private string title; public string Title { get { return title; } } private string content; public string Content { get { return content; } } public Document(string title, string content) { this.title = title; this.content = content; } } 

The DocumentManager class is a thin layer around the Queue<T> class. The class DocumentManager defines how to handle documents: adding documents to the queue with the AddDocument() method, and getting documents from the queue with the GetDocument() method.

Inside the AddDocument() method, the document is added to the end of the queue using the Enqueue() method. The first document from the queue is read with the Dequeue() method inside GetDocument(). Because multiple threads can access the DocumentManager concurrently, the access of the queue is locked with the lock statement.

Note

Threading and the lock statement are discussed in Chapter 13, "Threading."

IsDocumentAvailable is a read-only Boolean property that returns true if there are documents in the queue and false if not:

 public class DocumentManager { private readonly Queue<Document> documentQueue = new Queue<Document>(); public void AddDocument(Document doc) { lock (this) { documentQueue.Enqueue(doc); } } public Document GetDocument() { Document doc = null; lock (this) { doc = documentQueue.Dequeue(); } return doc; } public bool IsDocumentAvailable { get { return documentQueue.Count > 0; } } } 

The class ProcessDocuments processes documents from the queue in a separate thread. The only method that can be accessed from the outside is Start(). In the Start() method a new thread is instantiated. A ProcessDocuments object is created for starting the thread, and the Run() method is defined as the start method of the thread. ThreadStart is a delegate that references the method to be started by the thread. After creating the Thread object, the thread is started by calling the method Thread.Start().

With the Run() method of the ProcessDocuments class an endless loop is defined. Within this loop, the property IsDocumentAvailable is used to see if there is a document in the queue. If there is a document in the queue, the document is taken from the DocumentManager and processed. Processing here is only writing information to the console. In a real application, the document could be written to a file, to the database, or sent across the network.

 public class ProcessDocuments { public static void Start(DocumentManager dm) { new Thread(new ProcessDocuments(dm).Run).Start(); } protected ProcessDocuments(DocumentManager dm) { documentManager = dm; } private DocumentManager documentManager; protected void Run() { while (true) { if (documentManager.IsDocumentAvailable) { Document doc = documentManager.GetDocument(); Console.WriteLine("Processing document {0}", doc.Title); } Thread.Sleep(new Random().Next(20)); } } } 

In the Main() method of the application a DocumentManager object is instantiated, and the document processing thread is started. Then 1000 documents are created and added to the DocumentManager. With a real application, documents can be received from a Web service.

 class Program { static void Main(string[] args) { DocumentManager dm = new DocumentManager(); ProcessDocuments.Start(dm); // Create documents and add them to the DocumentManager for (int i = 0; i < 1000; i++) { Document doc = new Document("Doc " + i.ToString(), "content"); dm.AddDocument(doc); Console.WriteLine("added document {0}", doc.Title); Thread.Sleep(new Random().Next(20)); } } } 

When you start the application, the documents are added and removed from the queue as shown in Figure 10-1.

Figure 10-1

Using the LinkedList<T>

A collection class that has no similar version with a non-generic collection is LinkedList<T>. LinkedList<T> is a doubly linked list where one element references the next and the previous one as shown in Figure 10-2.

Figure 10-2

The advantage of a linked list is that if elements should be inserted in the middle of a list, the linked list is very fast. When an element is inserted only the Next reference of the previous element and the Previous reference of the next element must be changed to reference the inserted element. With a collection class, when an element is inserted all following elements must be moved.

Of course, there's also a disadvantage with linked lists. Linked lists can only be accessed one after the other. It takes a long time to find an element that's somewhere in the middle or at the end of the list.

The sample application uses a linked list LinkedList<T> together with a list List<T>. The linked list contains documents as in the previous example, but the documents have an additional priority associated with them. The documents will be sorted inside the linked list depending on the priority. If multiple documents have the same priority, the elements are sorted depending on the time the document was inserted.

Figure 10-3 describes the collections of the sample application. LinkedList<Document> is the linked list containing all the Document objects. The figure shows the title and the priority of the documents. The title indicates when the document was added to the list: The first document added has the title One, the second document Two, and so on. You can see that the documents One and Four have the same priority, 8, but because One was added before Four, it is earlier in the list.

Figure 10-3

When new documents are added to the linked list, they should be added after the last document that has the same priority. A LinkedList<Document> collection contains elements of type LinkedListNode<Document>. The class LinkedListNode<T> adds Next and Previous properties to walk from one node to the next. For referencing such elements, the List<T> is defined as List<LinkedListNode<Document>>. For fast access to the last document of every priority, the collection List<Linked ListNode> contains up to 10 elements, each referencing the last document of every priority. In the upcoming discussion the references to the last documents of every priority is called priority node.

From the previous example, the Document class is extended to contain the priority. The priority is set with the constructor of the class:

public class Document {    private string title;    public string Title    {       get       {          return title;       }    }    private string content;    public string Content    {       get       {          return content;       }    } private byte priority; public byte Priority { get { return priority; } } public Document(string title, string content, byte priority)    {       this.title = title;       this.content = content; this.priority = priority;    } }

The heart of the solution is the PriorityDocumentManager class. This class is very easy to use. With the public interface of this class new Document elements can be added to the linked list, the first document can be retrieved, and for testing purposes it also has a method to display all elements of the collection as they are linked in the list.

The class PriorityDocumentManager contains two collections. The collection of type LinkedList <Document> contains all documents. The collection of type List<LinkedListNode<Document>> contains references of up to 10 elements that are entry points to add new documents with a specific priority. Both collection variables are initialized with the constructor of the class PriorityDocumentManager. The list collection is also initialized with null:

 public class PriorityDocumentManager { private readonly LinkedList<Document> documentList; // priorities 0..9 private readonly List<LinkedListNode<Document>> priorityNodes; public PriorityDocumentManager() { documentList = new LinkedList<Document>(); priorityNodes = new List<LinkedListNode<Document>>(10); for (int i = 0; i < 10; i++) { priorityNodes.Add(new LinkedListNode<Document>(null)); } } 

Part of the public interface of the class is the method AddDocument(). AddDocument() does nothing more than call the private method AddDocumentToPriorityNode(). The reason for having the implementation inside a different method is that AddDocumentToPriorityNode() may be called recursively, as you see soon:

 public void AddDocument(Document d) { AddDocumentToPriorityNode(d, d.Priority); } 

The first action that is done in the implementation of AddDocumentToPriorityNode() is a check if the priority fits in the allowed priority range. Here the allowed range is between 0 and 9. If a wrong value is passed, an exception of type ArgumentException is thrown.

Next you check if there's already a priority node with the same priority as the priority that was passed. If there's no such priority node in the list collection, AddDocumentToPriorityNode() is invoked recursively with the priority value decremented to check for a priority node with the next lower priority.

If there's no priority node with the same priority or any priority with a lower value, the document can be safely added to the end of the linked list by calling the method AddLast(). Also, the linked list node is referenced by the priority node that's responsible for the priority of the document.

If there's an existing priority node, you can get the position inside the linked list where the document should be inserted. Here you must differentiate if a priority node already exists with the correct priority, or if there's just a priority node that references a document with a lower priority. In the first case you can just insert the new document after the position that's referenced by the priority node. Because the priority node always must reference the last document with a specific priority, the reference of the priority node must be set. It gets more complex if just a priority node referencing a document with a lower priority exists. Here the document must be inserted before all documents with the same priority as the priority node. To get the first document of the same priority, a while loop iterates through all linked list nodes using the Previous property until a linked list node is reached that has a different priority. This way, you know the position where the document must be inserted, and the priority node can be set:

 private void AddDocumentToPriorityNode(Document doc, int priority) { if (priority > 9 || priority < 0) throw new ArgumentException("Priority must be between 0 and 9"); if (priorityNodes[priority].Value == null) { priority--; if (priority >= 0) { // check for the next lower priority AddDocumentToPriorityNode(doc, priority); } else // now no priority node exists with the same priority or lower // add the new document to the end { documentList.AddLast(doc); priorityNodes[doc.Priority] = documentList.Last; } return; } else // a priority node exists { LinkedListNode<Document> priorityNode = priorityNodes[priority]; if (priority == doc.Priority)     // priority node with the same // priority exists { documentList.AddAfter(priorityNode, doc); // set the priority node to the last document with the same priority priorityNodes[doc.Priority] = priorityNode.Next; } else // only priority node with a lower priority exists { // get the first node of the lower priority LinkedListNode<Document> firstPriorityNode = priorityNode; while (firstPriorityNode.Previous != null && firstPriorityNode.Previous.Value.Priority == priorityNode.Value.Priority) { firstPriorityNode = priorityNode.Previous; } documentList.AddBefore(firstPriorityNode, doc); // set the priority node to the new value priorityNodes[doc.Priority] = firstPriorityNode.Previous; } } } 

Now only simple methods are left for discussion. DisplayAllNodes() just does a foreach loop to display the priority and the title of every document to the console.

The method GetDocument() returns the first document (the document with the highest priority) from the linked list and removes it from the list:

 public void DisplayAllNodes() { foreach (Document doc in documentList) { Console.WriteLine("priority: {0}, title {1}", doc.Priority, doc.Title); } } // returns the document with the highest priority (that's // in the linked list) public Document GetDocument() { Document doc = documentList.First.Value; documentList.RemoveFirst(); return doc; } } 

In the Main() method the PriorityDocumentManager is used to demonstrate its functionality. Eight new documents with different priorities are added to the linked list, and then the complete list is displayed:

 static void Main(string[] args) { PriorityDocumentManager pdm = new PriorityDocumentManager(); pdm.AddDocument(new Document("one", "Sample", 8)); pdm.AddDocument(new Document("two", "Sample", 3)); pdm.AddDocument(new Document("three", "Sample", 4)); pdm.AddDocument(new Document("four", "Sample", 8)); pdm.AddDocument(new Document("five", "Sample", 1)); pdm.AddDocument(new Document("six", "Sample", 9)); pdm.AddDocument(new Document("seven", "Sample", 1)); pdm.AddDocument(new Document("eight", "Sample", 1)); pdm.DisplayAllNodes(); Console.ReadLine(); } 

Figure 10-4 shows the result of the running program. You can see that the documents are sorted first by the priority and second by when the document was added.

Figure 10-4