Section 1.5. Implement GetEnumerator with Complex Data Structures
1.5. Implement GetEnumerator with Complex Data StructuresTo add an iterator to your original LinkedList class, you'll implement IEnumerable<T> on both LinkedList and the Node class: public class LinkedList<T> : IEnumerable<T> public class Node<T> : IComparable<Node<T>>, IEnumerable<Node<T>> 1.5.1. How do I do that?As noted in the previous lab, the IEnumerable interface requires that you implement only one method, GetEnumerator, as shown in Example 1-5. (Changes from Example 1-3 are highlighted.) Example 1-5. Enumerating through your linked listusing System; using System.Collections.Generic; namespace GenericEnumeration { 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 // node now implements IEnumerable allowing its use in a foreach loop public class Node<T> : IComparable<Node<T>>, IEnumerable<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) { 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; } // Method required by IEnumerable IEnumerator<Node<T>> IEnumerable<Node<T>>.GetEnumerator( ) { Node<T> nextNode = this; // iterate through all the nodes in the list // yielding each in turn do { Node<T> returnNode = nextNode; nextNode = nextNode.next; yield return returnNode; } while (nextNode != null); } System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator( ) { throw new NotImplementedException( ); } } // end class // implements IEnumerable so that you can use a LinkedList // in a foreach loop public class LinkedList<T> : IEnumerable<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 LinkedList( ) { } // 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; } } // Implement IEnumerable required method // iterate through the node (which is enumerable) // and yield up the data from each node returned IEnumerator<T> IEnumerable<T>.GetEnumerator( ) { foreach (Node<T> node in this.headNode) { yield return node.Data; } } System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator( ) { throw new NotImplementedException( ); } } class Program { private static void DisplayList<T>(string intro, LinkedList<T> theList) where T : IComparable<T> { Console.WriteLine(intro + ": " + theList); } // entry point static void Main(string[ ] args) { LinkedList<Pilgrim> pilgrims = new LinkedList<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")); DisplayList<Pilgrim>("Pilgrims", pilgrims); Console.WriteLine("Iterate through pilgrims..."); // Now that the linked list is enumerable, we can put // it into a foreach loop foreach (Pilgrim p in pilgrims) { Console.WriteLine("The pilgrim's name is " + p.ToString( )); } } } }Output: Pilgrims: The Cook, The Knight, The Man of Law, The Miller, The Reeve Iterate through pilgrims... The pilgrim's name is The Cook The pilgrim's name is The Knight The pilgrim's name is The Man of Law The pilgrim's name is The Miller The pilgrim's name is The Reeve 1.5.2. What just happened?The linked list implements its enumerator to call foreach on the head node (which you can do because Node also implements IEnumerable). Then you yield the data object you get back from the node: IEnumerator<T> IEnumerable<T>.GetEnumerator( ) { foreach (Node<T> node in this.headNode) { yield return node.Data; } }This gives Node the responsibility of iterating through the node list, which is accomplished, once again, using the yield statement in its own GetEnumerator method. Note: When you use the yield statement, the C# compiler automatically generates a nested implementation of IEnumerator for you. It keeps its own state; you simply tell it which value to yield. IEnumerator<Node<T>> IEnumerable<Node<T>>.GetEnumerator( ) { Node<T> nextNode = this; do { Node<T> returnNode = nextNode; nextNode = nextNode.next; yield return returnNode; } while (nextNode != null); }You initialize nextNode to the current node, and then you begin your do...while loop. This is guaranteed to run at least once. returnNode is set to nextNode, and then, once that is stashed away, nextNode is set to its next node (that is, the next node in the list). Then you yield returnNode. Each time through you are returning the next node in the list until nextNode is null, at which time you stop. 1.5.3. What about......the fact that in LinkedList you asked for each Node<T> in headNode? Is headNode a collection? Actually, headNode is the top node in a linked list. Because Node implements IEnumerable, the node is acting like a collection. This isn't as arbitrary as it sounds because a node acts as a collection in the sense that it can give you the next node in the list. You could redesign the linked list to make the nodes "dumber" and the list itself "smarter," in which case it would be the list's job to iterate over each node in turn. 1.5.4. Where can I learn more?You can learn more about the IEnumerable<T> interface in the MSDN Help files, "Topic: IEnumerable<T>." |
EAN: 2147483647
Pages: 95