Enumerable Objects
Enumerable objects implement the IEnumerable interface. The GetEnumerator method is the only member of this interface. It returns an enumerator, which is used to enumerate nongeneric collections.
This is the IEnumerable interface:
public interface IEnumerable { IEnumerator GetEnumerator(); } Each invocation of the GetEnumerator method returns a unique enumerator. The enumerator is a state machine that minimally maintains a snapshot of the target collection and a cursor. The cursor points to the current item of the collection. The snapshot is a static copy of the collection. What happens if a collection is modified while being enumerated? An exception occurs. You could lock the collection during enumeration, but it might cause substantial performance degradation. As a best practice, an enumerator should capture the collection as a snapshot. This isolates the enumerator from changes to the original collection. In addition, the snapshot collection is read-only. The GetEnumerator method should be thread-safe, guaranteeing that a unique enumerator is returned, which references an isolated collection regardless of the thread context.
Enumerators
Enumerators are part of the enumeration pattern and normally implemented as a nested class within the collection type. The primary benefit of nested classes is access to the private members of the outer class. This access allows you to avoid breaking the rules of encapsulation to allow the enumerator class to access the data store of the collection. The data store is undoubtedly a private member of the collection class.
Enumerators implement the IEnumerator interface, which has three members. This is the IEnumerator interface:
public interface IEnumerator { object Current {get;} bool MoveNext(); void Reset(); } The Current property returns the current element of the collection. MoveNext moves the Current property to the next element. If the iteration has completed, MoveNext returns false. Otherwise, MoveNext returns true. Notice that there is not a MovePrevious method; enumeration is forward only. The Reset method returns the enumeration to the beginning of the collection.
The enumerator is the state machine representing the enumeration. Part of the state machine is the cursor, which is the collection index or locator. The cursor is not necessarily an integral value, but normally it is. For a link list, the cursor may be a node, which is an object. When the enumerator is created, the cursor initially points before the first element of the collection. Do not access the Current property while the cursor is in this initial state. Call MoveNext first, which positions the cursor at the first element of the collection.
The following is a typical constructor of an enumerator. In this example, the constructor makes a snapshot of the collection. For reasons of simplicity, the collection is a basic array. The cursor is then set to –1, which is before the first element of the collection.
public Enumerator(object [] items) { elements=new object[items.Length]; Array.Copy(items, elements, items.Length); cursor=-1; } The MoveNext method increments the value of the cursor. This action moves the Current property to the next element of the collection. If the list has been fully iterated, MoveNext returns false. Collections are not circular, where MoveNext might cycle through a collection. Circular collections are not within the enumerator pattern. The Current property is not valid after the collection has been fully enumerated. For this reason, do not use the Current property after MoveNext returns false.
Here is one possible implementation of the MoveNext method:
public bool MoveNext() { ++cursor; if(cursor>(elements.Length-1)) { return false; } return true; } The Reset method resets the enumeration. The cursor is updated to point to before the collection again. Resetting the cursor also automatically resets the Current property.
Here is a Reset method:
public void Reset() { cursor=-1; } With the cursor as a reference to the current item, the Current property provides access to the current element of the collection. The Current property must be read-only. Implement the get method of the property but not the set method. The implementation should check for fence-post errors. If the index is before or after the collection, the appropriate exception should be thrown.
Here is an implementation of the Current property:
public object Current { get { if(cursor>(elements.Length-1)) { throw new InvalidOperationException( "Enumeration already finished"); } if(cursor == -1) { throw new InvalidOperationException( "Enumeration not started"); } return elements[cursor]; } } Enumerator states Enumerators can be in one of four possible states. Table 7-1 lists the enumerator states.
| State | Description |
|---|---|
| Before | This is the state of the enumerator before enumeration has started or after it has been reset. The first call to MoveNext changes the state from Before to Running. |
| Running | This is the state when MoveNext is calculating the next element (Current) of the iteration. When MoveNext returns true, the next element has been enumerated, and the state changes to Suspended. If MoveNext returns false, the state changes to After. At that time, the Current property is no longer available. |
| Suspended | The state of the enumerator between enumerations. Calling MoveNext changes the state from Suspended to Running while calculating the next Current property. |
| After | This is the state after enumeration has completed. Reset returns the enumeration to Before, and enumeration can be restarted. |
Enumerator Example
Sample code for an enumerator class and client are provided as follows. This is also the complete listing for some of the partial code presented earlier in this segment. The SimpleCollection is a thin wrapper for a basic array. Actually, it is somewhat redundant because arrays are already fully functional collections, including exposing an enumerator. However, this simple example is ideal for demonstrating the enumerator pattern.
The enumerator pattern recommends isolation of the underlying collection. In this code, the enumerator is created as a nested class, in which a snapshot of the collection is made in the constructor. The isolated collection is created from a copy of the array. In addition, the Current property is read-only, which prevents changes to the collection data.
In Main, an instance of the SimpleCollection is created. It is initialized with an integer array. The collection is then iterated using the IEnumerator interface.
using System; using System.Collections; namespace Donis.CSharpBook{ public class Starter{ public static void Main(){ SimpleCollection simple=new SimpleCollection( new object[] {1,2,3,4,5,6,7}); IEnumerator enumerator=simple.GetEnumerator(); while(enumerator.MoveNext()) { Console.WriteLine(enumerator.Current); } } } public class SimpleCollection: IEnumerable { public SimpleCollection(object [] array) { items=array; } public IEnumerator GetEnumerator() { return new Enumerator(items); } private class Enumerator: IEnumerator { public Enumerator(object [] items) { elements=new object[items.Length]; Array.Copy(items, elements, items.Length); cursor=-1; } public bool MoveNext() { ++cursor; if(cursor>(elements.Length-1)) { return false; } return true; } public void Reset() { cursor=-1; } public object Current { get { if(cursor>(elements.Length-1)) { throw new InvalidOperationException( "Enumeration already finished"); } if(cursor == -1) { throw new InvalidOperationException( "Enumeration not started"); } return elements[cursor]; } } private int cursor; private object [] elements=null; } private object [] items=null; } } As mentioned, the SimpleCollection class makes a copy of the collection in the enumerator. This isolates the collection from contamination caused by modifications. This is the recommended approach for volatile collections. SimpleCollection is volatile because the elements of the underlying collection can be modified. If the collection is static, a copy may not be necessary. Isolation protects a collection against changes. If the collection is static, this is not an issue, and isolation is not required.
Enumerator Example (Static Collection)
Here is the SimpleCollection class rewritten for a static collection. The underlying collection is read-only, which makes it static. When the enumerator is created, the this reference of the enumerable object is passed to the constructor. Future and unique enumerators share this reference to access the same collection—maybe simultaneously. The state machine encapsulates the back reference and a cursor. The back reference is the this reference to the outer object. With the back reference, the enumerator gains access to members of the outer class, including the collection, which allows the enumerator to iterate the collection directly.
public class SimpleCollection: IEnumerable { public SimpleCollection(object [] array) { items=array; } public IEnumerator GetEnumerator() { return new Enumerator(this); } private class Enumerator: IEnumerator { public Enumerator(SimpleCollection obj) { oThis=obj; cursor=-1; } public bool MoveNext() { ++cursor; if(cursor>(oThis.items.Length-1)) { return false; } return true; } public void Reset() { cursor=-1; } public object Current { get { if(cursor>(oThis.items.Length-1)) { throw new InvalidOperationException( "Enumeration already finished"); } if(cursor == -1) { throw new InvalidOperationException( "Enumeration not started"); } return oThis.items[cursor]; } } private int cursor; private SimpleCollection oThis; } private object [] items=null; } Collections that have inconstant changes are not ideal for either of the enumerator models presented: contentious or static. Copying the collection per each enumerator is costly when changes are infrequent. The static model is inappropriate because the collection may indeed change, albeit not regularly. A versioned collection is the solution and combines traits of the contentious and static models for implementing enumerators.
Enumerator Example (Versioned Collection)
The following code contains an implementation for a versioned collection. A private field called version has been added to the collection class. An indexer has been added to allow clients to modify the collection. The version is incremented whenever the collection is modified. A version number has also been added to the enumerator, which is the nested class. In the constructor, the version is initialized to the version of the outer collection. When the Current property is accessed, the version number inside the enumerator is compared to that of the collection. If unequal, the collection has been modified since the enumerator was created and an exception is raised. This is the implementation model of the collections in the .NET Framework class library (FCL), such as the ArrayList, Stack, Queue, and other collection classes.
The Main method is changed to test the versioning. The collection is modified in the method after the enumerator has been obtained. After the modification, the Current property is used, which causes the expected exception:
using System; using System.Collections; namespace Donis.CSharpBook{ public class Starter{ public static void Main(){ SimpleCollection simple=new SimpleCollection( new object[] {1,2,3,4,5,6,7}); IEnumerator enumerator=simple.GetEnumerator(); enumerator.MoveNext(); Console.WriteLine(enumerator.Current); enumerator.MoveNext(); simple[4]=10; Console.WriteLine(enumerator.Current); // Exception raised enumerator.MoveNext(); } } public class SimpleCollection: IEnumerable { public SimpleCollection(object [] array) { items=array; version=1; } public object this[int index] { get { return items[index]; } set { ++version; items[index]=value; } } public IEnumerator GetEnumerator() { return new Enumerator(this); } private class Enumerator: IEnumerator { public Enumerator(SimpleCollection obj) { oThis=obj; cursor=-1; version=oThis.version; } public bool MoveNext() { ++cursor; if(cursor>(oThis.items.Length-1)) { return false; } return true; } public void Reset() { cursor=-1; } public object Current { get { if(oThis.version != version) { throw new InvalidOperationException( "Collection was modified"); } if(cursor>(oThis.items.Length-1)) { throw new InvalidOperationException( "Enumeration already finished"); } if(cursor == -1) { throw new InvalidOperationException( "Enumeration not started"); } return oThis.items[cursor]; } } private int version; private int cursor; private SimpleCollection oThis; } private object [] items=null; private int version; } }
IEnumerator Problem
Several techniques to implement the enumerator pattern have been shown. The varied strategies share common problems. Enumerators, which implement the IEnumerator interface, manipulate System.Object types. This is the heart of the problem.
-
There is a performance penalty from boxing and unboxing value types.
-
Alternatively, there is a performance cost to downcasting to reference types.
-
Frequent boxing stresses the managed heap.
-
Casting to and from System.Object is required, which is not type-safe.
These problems were identified in the previous chapter. The solution was generic types. That is the solution here also. The .NET Framework offers generic versions of the IEnumerable and IEnumerator interfaces.
EAN: 2147483647
Pages: 161