You can accomplish this, as you mention, via a separate extension method - however, this comes at a cost. Most importantly, any other user of your class or you later will have to learn a new API that accomplishes nothing - you're making your class more difficult to use by not using standard interfaces, since it violates the user's expectations.
It also introduces an extra level of indirection for every step of the iteration. Probably not a performance problem, but still somewhat unnecessary when I don't think you're really gaining anything very significant.
Also, by not implementing IEnumerable , you're counting yourself out of collection initializers. I sometimes implement IEnumerable explicitly just to opt into collection initialization, throwing an exception from GetEnumerator.
And I am really OK with that. It's a tiny price to pay for full compatibility with every other piece of. NET code ever written ;. It is so much easier to use IEnumerable for reflection. This is because IEnumerable only exposes one GetEnumerator method, and that one without any arguments. It is impossible to tell, through means of IEnumerable interface, which iteration algorithm we desire.
Therefore, this kind of declaration for the tree is impossible:. To resolve the issue, we have to provide multiple GetEnumerator methods, like here:. In this implementation, method name indicates the algorithm. Any iteration algorithm depends on internal organization of the tree data structure, which in turn jeopardizes its encapsulation. We will return to this problem later in this article.
Right now, we have reached one important conclusion. If the data structure implements IEnumerable interface directly, then it is doomed to only one iteration algorithm. This may be a needless constraint put up-front, even before concrete implementation comes. Implementing IEnumerable implies some default iteration sequence.
But some concrete implementation might object to this, for example if general iteration is less optimal. This looks fine, right? It looks right because we consider list a basic structure and we already have some ideas how we would use objects implementing the interface. Even without concrete list implementation, we can see code like this:. Same thing, same implementation. We consider repository an expensive object, the one which relies on storage, which always comes with performance penalty.
In practice, repository is often declared like this:. The trick with this declaration is that it lets us choose the iteration algorithm. There is this GetAll method which suffers the full performance penalty, but the fact that it is not the only, mandatory method, means that we can add more of them:.
This flavor comes with the predicate that should be satisfied by elements returned from the repository. Concrete repositories could come up with internal optimization in presence of the predicate, who knows. Some implementations prefer LINQ expressions, rather than plain predicates:.
Concrete implementations could then leverage expressions to exercise more optimized queries on the underlying storage. There is nothing wrong with this approach.
It is a valid option when we have more or less clear picture of future concrete implementations that will need to incorporate filtering as part of the iterating algorithm. Note that methods of the abstract repository given above are not returning IEnumerator. They return IEnumerable instead. That is another powerful concept. Not only that iteration algorithm has been externalized, but it has been represented as a separate view on the collection. It almost looks like the collection itself has been replicated to a separate object, which is then responsible to provide the enumerator on request.
But the collection did not replicate, of course. And that opens several questions, primarily regarding the question who is responsible to ensure that the collection does not change while enumerators are active on it. On the other hand, returning IEnumerable from the method comes handy if you wish to use the foreach loop. This keyword actually expects IEnumerable , rather than IEnumerator. Therefore, returning IEnumerator from a method other than GetEnumerator of the IEnumerable interface turns to be a bad idea.
There is not much help from the language using such a method. As an example, we can take a look at the array-like class which will support two iteration methods in the future: from front and from back.
The basic implementation only supports adding elements:. I have a different plan. I will expose methods that return IEnumerable. Right now, it is only important to understand the basic flow of the dynamic array. It lets us append new elements freely and each time the internal array is completely filled up it gets resized so that more elements can be added. We can use this class in the following way:.
If we wanted to expose a method which returns IEnumerator , that would not go that easy. We need a class implementing the IEnumerator interface:. Quite a lot of typing, you see. But that is not the only issue here. See how this enumerator receives the array and its used capacity through the constructor.
This is the leaky abstraction. In order to work, this enumerator must know exact internal organization of the DynamicArray class. But now that we have the enumerator class, we can use it in the DynamicArray quite easily:. Then, things become more complicated at the using side again. But we had to rely on manual loop control, in form of the GetEnumerator-MoveNext-Current sequence of calls.
This is not the preferable way. It is much easier if we go with the method returning IEnumerable instead. And that is all! Only two lines of code effectively replace almost 50 lines of code we had to type to construct the enumerator class. Even more, this implementation is not leaky. DynamicArray is completely opaque, even with the GetForwardSequence method in place.
We are free to change internal organization, for example to use a List instead of the array, and nothing outside the DynamicArray will have to change. Further down the stream, client code becomes simpler as well, thanks to the foreach loop which works fine on the IEnumerable implementations:. Bottom line is that returning IEnumerator from the method costs us on more than one account:.
This is the complete source code of the dynamic array class. It exposes feature to append an element to the array, as well as to iterate through the array from the beginning or from the ending.
This implementation demonstrates the principle that the collection can benefit from avoiding to implement the IEnumerable interface. Instead, it can expose methods that return IEnumerable , letting the clients decide which iteration method they will request rather than establishing one iteration order as the default.
Now that we have a basic implementation of the dynamic array, we can think of more complicated scenarios. Suppose that we wanted to add a RemoveAt feature — a method which removes an element at specified position. Here is the code:. This is the complete source code of the DynamicArray generic class. In addition to Append method, now it contains the RemoveAt method, which simply moves all subsequent elements by one position towards the beginning of the array and reduces the used size of the array.
Quite simple feature, but it has introduced a defect to the design. To be honest, it is hard to tell what this loop is supposed to print. Should it print the whole array, despite the fact that its content is being moved with each iteration? Whatever the intention, here is what the loop really prints out:.
This is somewhere in between of whatever we could expect. The loop has printed some elements of the array, while at the same time skipping the others. Values 1 and 2 existed in the array but did not appear in the output. This is typical erratic behavior of structures that allow iteration but do not check whether the content has changed while some enumerator was active.
Long story short — we need to introduce versioning to the class. Even if there is no exception, the operation could silently run incorrectly like we saw above, which is even worse option. So, here is the implementation. We are introducing the version field in the DynamicArray class. Operations like Append and RemoveAt increment the version number. To avoid the historical problem of. NET collections, we are using bit unsigned version numbers, which ensures that version will never repeat during the lifetime of an object.
Here is the complete implementation of the DynamicArray class with custom version checking:. This is the final implementation of the DynamicArray class. This time it comes with internal version number, which is increased every time the content of the collection changes.
Enumerators on their end take a snapshot of the version number and then check it against current version whenever they make a move that could cause erratic behavior. All holes are plugged, and all users who try to change the collection while there are active enumerators on it will be punished accordingly.
Suppose that we want to implement binary tree collection. The tree would consist of nodes, each node carrying an informative content, like this:. This class is just a DTO, data transfer object. It does not provide any behavior. But nodes can be combined by a proper collection class to construct a binary tree structure.
Below is the BinaryTree generic class which leverages the BinaryNode class to implement the binary tree data structure. Please take your time to analyze this implementation. You will see that it works on the principle of the cursor. There is the Current property which refers to currently selected node. This lets us set left and right child nodes on any of the nodes in the tree, provided that we have previously navigated to that particular node using one of the Move methods — MoveToRoot , MoveLeft and MoveRight.
With this tree structure implementation, we can construct an arithmetic expression, for example, with code like this:. Not much fun. It will be better if we had some means to iterate through the tree. Binary trees have three standard traversal orders: preorder, in which the node is traversed before its left and right subtrees; inorder, in which left subtree is traversed first, followed by the current node and right subtree; and postorder, in which left and right subtrees are traversed before the node that holds them.
We can easily write three methods that return IEnumerable , one for each of the traversal algorithms. However, note that this tree class is mutable. It allows us to change the tree content while enumerating nodes. Like before, we have to protect the client from dangers of traversing and modifying the collection simultaneously.
The solution will be the same as before — we will add a bit unsigned integer which will play the role of the version number. Here is the modified binary tree class:. As you can see, all Set methods are increasing the version number. On the other hand, Move methods do not increase the version number. This is because Move methods do not produce any change to the data structure.
It changes the state of the object, but data structure remains the same. Since enumerators are only interested to know the links between tree nodes, and these links did not change, there is no reason to increase the version number from inside any of the Move methods.
With version number in place, we can start implementing the three enumeration strategies. Preorder first:. Traversal algorithm is not that simple, admittedly. It is based on passing the tree nodes through the stack, pushing each of the nodes to the output as soon as it leaves the stack and pushing its child nodes for further processing. This way of doing things will ensure that each node will appear in the output right before its left subtree and then its right subtree.
That is precisely the definition of the preorder sequence. Observe how we are asserting the collection version with every step of the loop. That is the mandatory step when working with mutable collection content. This time the assertion itself is moved to a utility method AssertVersion , because the same feature will appear in the remaining two enumeration methods. This time we are using stack to keep track of the nodes that we are traversing.
In addition to the node itself, we have to keep track of an additional flag, indicating whether the left subtree has already been traversed or not. This is important, because in inorder sequence the node must wait until its left tree has been fully processed. You can study this algorithm in detail if you like. We will swiftly move to the last enumeration algorithm, postorder:.
The postorder algorithm also relies on the stack structure, this time forcing the node to wait on the stack until both left and right subtree have been fully traversed.
Only after that, the node will be pushed to the output. Note once again that every iteration of the loop begins with the call to AssertVersion method. This ensures that the caller will receive an InvalidOperationException as soon as it tries to modify the tree while an enumerator is still active on the same tree.
This concludes implementation of all three iteration algorithms on the binary tree data structure which allows us to change its contained nodes.
Lesson learned from this exercise is that we must track content version all the time. The root cause of this requirement is that content of the collection is mutable. Not only that BinaryNode class is mutable, but BinaryTree class is actually mutating the node objects from its Set methods. That promises troubles when it comes to enumerating tree nodes, and consequently we have to track content version.
On a related note, BinaryTree class has turned to be quite long and complicated. This will give rise to a different idea — to externalize enumeration algorithm. We already had this idea before and now we are close to returning to it. If we could move preorder, inorder and postorder algorithms to separate classes, then the BinaryTree class would be reduced to a half of its current size in terms of number of lines of code.
But that is not all. With proper enumeration classes, we could even produce more elegant code than the one demonstrated in the BinaryTree class. There is one more idea that we should analyze before externalizing iteration algorithms. Namely, if tree nodes could be immutable, then there would be no way to change any actual tree representation that is currently being enumerated, even if the containing tree object has been changed.
This may sound like a mind-bending idea, but it is actually very simple. That is precisely what we are going to do next. One of the complications we had in the example with binary tree is that the tree structure can change while an enumerator is active on it.
This could lead to improper behavior — sequence of tree elements that appear on the output could differ from both current and original content of the tree and actual sequence would be clearly incorrect. We have already seen one method of dealing with the problem in previous section, where the tree class was maintaining the version number. This has solved the problem, but the solution has an unpleasant side-effect.
Sometimes, the caller could receive an InvalidOperationException , if it has modified the tree structure while iterating it. As a matter of fact, we could improve the situation by making BinaryNode objects immutable. Instead of modifying any node in the tree, we could replace it with completely new node.
Here is the new implementation of the BinaryNode class:. This is the immutable binary node. It carries data and holds references to left and right subtrees.
Should we want to change the node, we would have to construct a new one. Note also that the only public constructor is the one which only receives the data content. Child references will be constructed through the use of WithLeftChild and WithRightChild methods, which will enforce a well-defined process of constructing the binary tree one step at the time.
Also, there is this SetContent method which produces a new node with same child references, but modified content. Now comes the BinaryTree. IEnumerable is an interface that allows us to iterate over a collection; it does so by exposing a single GetEnumerator method, which in turn returns an IEnumerator : a simple interface that provides methods to access the current element in the collection, move to the next item, and reset back to the beginning of the collection.
Take this Stack implementation — you can check here this post on how to implement a Stack in C — and see if you notice some functionality lacking:.
How could we do that? Yes, yucks. If we want to iterate the stack in a sane manner, we need to improve our BasickStack class implementation. We could do that by adding functions that check if the Stack is empty, or by exposing the number of elements.
But if we implement the IEnumerable interface, we will be able to use a foreach like this:. Brief, when implementing a custom Data Structure we can implement the IEnumerable interface to add iteration functionality. When adding the interface we see we need to implement two methods that return an IEnumerator :.
Since our stack implementation uses generics, we want to implement IEnumerable. But IEnumerable extends from IEnumerable. Therefore we have methods for both the generic, and non generic enumerator. Having implemented IEnumerable , we need now to move on to implementing our Enumerator. The class we've just written would be suitable as a basis from which to write a more sophisticated collection.
The final approach in writing GetEnumerator is to write a class that implements IEnumerator directly. Note that the first call to MoveNext should move to the first and not the second item in the list.
0コメント