Visual CSharp 1002005 A Developers Notebook [Electronic resources] نسخه متنی

1.3. Implement the Collection Interfaces

In addition to its generic collection classes, .NET 2.0 also provides
a set of generic interfaces
that enable you to create type-safe collections that have all the
functionality of the earlier, nongeneric .NET 1.x collection types.
You'll find these interfaces in the
System.Collections.Generic namespace. The namespace also
includes a number of related generic interfaces, such as
IComparable<T>, which you can use to compare two
objects of type T regardless of whether they are
part of a collection.

You can create a sorted linked
list by having each datatype stored in the list implement the
IComparable<T> interface and by having your
Node object be responsible for inserting each new
Node at the correct (sorted) position in the
linked list.

1.3.1. How do I do that?

Integer already implements
IComparable; you can easily modify
Pilgrim to do so as well. Modify the definition of
the Pilgrim class to indicate that it implements
the IComparable<T> interface:

public class Pilgrim : IComparable<Pilgrim>

Be sure to implement the CompareTo and the
Equals methods that the interface requires. The
objects these methods receive will be of type
Pilgrim because this is a type-safe interface, not
a "standard" interface that would
pass in objects:

public int CompareTo(Pilgrim rhs)
public bool Equals(Pilgrim rhs)

All you need to do now is change the logic of adding a node. This
time, instead of adding to the end of the list,
you'll insert the new node into the list where it
belongs based on the implementation of the
CompareTo method.

Note: You can constrain the datatypes your generic type accepts
by using constraints.

For this to work, you must ensure that the datatype held in the node
implements IComparable. You accomplish this with a
constraint using the keyword where:

public class Node<T> : IComparable<Node<T>> where T:IComparable<T>

This line of code declares a class Node of
T that implements IComparable
(of Node of T) and that is
constrained to hold datatypes that implement
IComparable. If you try to have your
Node class hold an object that does not implement
IComparable, you will receive an error message
when you attempt to compile it.

You must be careful to return the new head of the list if the new
node is "less than" the current
head of the list, as shown in Example 1-3 (Changes
from the previous example are highlighted.)

Example 1-3. Implementing generic interfaces

using System;
using System.Collections.Generic;
namespace ImplementingGenericInterfaces
{
public class Pilgrim : IComparable<Pilgrim>
{
private string name;
public Pilgrim(string name)
{
this.name = name;
}
public override string ToString( )
{
return this.name;
}
// implement the interface
public int CompareTo(Pilgrim rhs)
{
return this.name.CompareTo(rhs.name);
}
public bool Equals(Pilgrim rhs)
{
return this.name =  = rhs.name;
}
}
// node must implement IComparable of Node of T
// constrain Nodes to only take items that implement Icomparable
// by using the where keyword.
public class Node<T> : IComparable<Node<T>> where T:IComparable<T>
{
// member fields
private T data;
private Node<T> next = null;
private Node<T> prev = null;
   
// constructor
public Node(T data)
{
this.data = data;
}
// properties
public T Data { get { return this.data; } }
public Node<T> Next
{
get { return this.next; }
}
public int CompareTo(Node<T> rhs)
{
// this works because of the constraint
return data.CompareTo(rhs.data); 
}
public bool Equals(Node<T> rhs)
{
return this.data.Equals(rhs.data);
}
// methods
public Node<T> Add(Node<T> newNode)
{
if (this.CompareTo(newNode) > 0) // goes before me
{
newNode.next = this;  // new node points to me
// if I have a previous, set it to point to
// the new node as its next
if (this.prev != null)
{
this.prev.next = newNode;
newNode.prev = this.prev;
}
// set prev in current node to point to new node
this.prev = newNode;
// return the newNode in case it is the new head
return newNode;
}
else         // goes after me
{
// if I have a next, pass the new node along for comparison
if (this.next != null)
{
this.next.Add(newNode);
}
// I don't have a next so set the new node
// to be my next and set its prev to point to me.
else
{
this.next = newNode;
newNode.prev = this;
}
return this;
}
}
public override string ToString( )
{
string output = data.ToString( );
if (next != null)
{
output += ", " + next.ToString( );
}
return output;
}
}      // end class
public class 
SortedLinkedList<T> where T : IComparable<T>
{
// member fields
private Node<T>  headNode = null;
// properties
// indexer
public T this[int index]
{
get
{
int ctr = 0;
Node<T> node = headNode;
while (node != null && ctr <= index)
{
if (ctr =  = index)
{
return node.Data;
}
else
{
node = node.Next;
}
++ctr;
} // end while
throw new ArgumentOutOfRangeException( );
}      // end get
}          // end indexer
// constructor
public SortedLinkedList( )
{
}
// methods
public void Add(T data)
{
if (headNode =  = null)
{
headNode = new Node<T>(data);
}
else
{
headNode = headNode.Add(new Node<T>(data));
}
}
public override string ToString( )
{
if (this.headNode != null)
{
return this.headNode.ToString( );
}
else
{
return string.Empty;
}
}
}
class Program
{
// entry point
static void Main(string[  ] args)
{
SortedLinkedList<int>
 mySortedLinkedList = new SortedLinkedList<int>( );
Random rand = new Random( );
Console.Write("Adding: ");
for (int i = 0; i < 10; i++)
{
int nextInt = rand.Next(10);
Console.Write("{0}  ", nextInt);
mySortedLinkedList.Add(nextInt);
}
SortedLinkedList<Pilgrim>
 pilgrims = new SortedLinkedList<Pilgrim>( );
pilgrims.Add(new Pilgrim("The Knight"));
pilgrims.Add(new Pilgrim("The Miller"));
pilgrims.Add(new Pilgrim("The Reeve"));
pilgrims.Add(new Pilgrim("The Cook"));
pilgrims.Add(new Pilgrim("The Man of Law"));
Console.WriteLine("\nRetrieving collections...");
DisplayList<int>("Integers", mySortedLinkedList);
DisplayList<Pilgrim>("Pilgrims", pilgrims);
//Console.WriteLine("Integers: " + mySortedLinkedList);
//Console.WriteLine("Pilgrims: " + pilgrims);
Console.WriteLine("The fourth integer is " + mySortedLinkedList[3]);
Pilgrim d = pilgrims[2];
Console.WriteLine("The third pilgrim is " + d);
//         foreach (Pilgrim p in pilgrims)
//         {
//            Console.WriteLine
("The pilgrim's name is " + p.ToString( ));
//         }
}   // end main
private static void DisplayList
<T>(string intro, SortedLinkedList<T> theList)
where T : IComparable<T>
{
Console.WriteLine(intro + ": " + theList);
}
}   // end class
}      // end namespace

Output:

Adding: 2  8  2  5  1  7  2  8  5  5  
Retrieving collections...
Integers: 1, 2, 2, 5, 7, 8, 8
Pilgrims: The Cook, The Knight, The Man of Law, The Miller, The Reeve
The fourth integer is 5
The third pilgrim is The Man of Law

1.3.2. What just happened?

The Pilgrim class changed just enough to implement
the generic IComparable interface. The linked list
didn't change at all, but the
Node class did undergo some changes to support the
sorted list.

First, the Node class was marked to implement
IComparable and was constrained to hold only
objects that themselves implement IComparable:

public class Node<T> : IComparable<Node<T>> where T:IComparable<T>

Second, Node added a reference to the previous
node, in addition to the next node (making this a doubly linked
list):

private Node<T> next = null;
private Node<T> prev = null;

The Node class must implement
CompareTo and Equals. These are
simple to implement because the constraint ensures that the data you
are comparing also implements IComparable:

public int CompareTo(Node<T> rhs)
{
// this works because of the constraint
data.CompareTo(rhs.data); 
}

1.3.3. What about . . .

...the IComparable requirement? Why did
Pilgrim and Node require
IComparable, but the linked list did
not?

To understand this, it's important to note that both
Pilgrims and Nodes must be
compared; linked lists are not compared. Because the linked list is
sorted by sorting its nodes, there is no need to compare two linked
lists to see which one is "greater"
than the other.

...what about passing generic types to a method; can I do that?

Yes, you can pass a generic type to a method, but only if the method
is generic. In Example 1-3, you display the contents
of the list of integers and the list of pilgrims with the following
code:

Console.WriteLine("Integers: " + myLinkedList);
Console.WriteLine("Pilgrims: " + pilgrims);

You are free to create a method to take these lists and display them
(or manipulate them):

private void DisplayList<T>(string intro, LinkedList
<T> theList) where T : IComparable<T>
{
Console.WriteLine(intro + ": " + theList);
}

When you call the method, you supply the type:

DisplayList<int>("Integers", myLinkedList);
DisplayList<Pilgrim>("Pilgrims", pilgrims);

Tip: The compiler is capable of type inference, so you can rewrite the
preceding two lines as follows:

DisplayList("Integers", myLinkedList);
DisplayList("Pilgrims", pilgrims);

1.3.4. Where can I learn more?

The MSDN Library covers the Generic
namespace extensively. Search on
Systems.Collections.Generic. Also, see my article on generics on
O'Reilly's ONDotnet.com site at
http://www.ondotnet.com/pub/a/dotnet/2004/05/17/libertyl.