Lecture thumbnail 0:00 / 0:00 All right.
So what we’re going to take a look at, first of all, is how to construct an iterator, which is a
separate object.
So let me set up a very simple scenario where we’re going to build a binary tree and then we’re going
to implement different forms of traversal.
In actual fact, we’ll only implement one form of traversal, but hopefully that will be enough to tell
you how to implement the others.
So let’s suppose we’re building a binary tree, so the class which makes up the binary tree is a node
and I’ll make a generic type node of T so I’ll have public T value.
Once again, I’m using public fields here.
I’ll have public references to the left and right nodes in the tree.
So I will have public node of T and I will have left and right here.
In addition, I will have public node of t parent.
So that’s going to be a reference to the parent node if there is indeed a parent node.
So for the root node parent will be null obviously.
And then I’ll have a bunch of constructors, I’ll have a constructor which simply initializes the value.
Let’s get rid of this part because it can be null.
The value can be a reference type or a value type, so who knows?
And in addition, let’s make another constructor where we’ll initialize the value as well as the left
and right nodes.
Now, in terms of once again, I’ll get rid of this part, but in terms of getting the parent initialized,
then the parent of any nodes which are children.
So these are effectively the left and right children of the current node.
They’re going to be set to the current object.
So we’re going to say left dot parent equals right dot parent equals this.
Okay?
So we kind of set the parents automatically.
And now what we can do is we can already start using this node definition to build a very simple tree.
So I’m going to build a tree which looks like this so I will have a value one.
So we’re going to be using integers.
I will have the value one at the top level and then I will have the value two on the left branch and
the value three on the right branch.
So a very simple binary tree with just three elements in it.
And we’re going to traverse this tree and we’re going to do an in-order traversal.
So just just as a reminder, the kind of traversals you can do on the tree.
If you do in order, the traversal will be 213.
So first of all, you go to the left.
Most element in the tree.
If there is indeed the left most element, then you go to the root and then the right most elements
in order.
So in order traversal will be two, one, three, and then you can do other traversals, like for example,
preorder traversal would be one, two, three, I believe.
And there is also post order and so on.
We’re just going to stick to in order for this particular demo.
So what we’re going to do is first of all, we’ll define the root.
So I’ll say var root equals new node of N.
So we’re going to have integers.
So the root has the value one, and then it has two children with the values two and three.
So we’ll make a new node event with the value two and a new node of INT.
Try to press the right shortcut with the value three here.
So this is the tree.
And now I want to traverse the tree in order.
And for this we’re going to build the classic iterator.
So the classic approach to the iterator is where you actually build it yourself as opposed to letting
the C-sharp language generate one for you, which is how it’s done normally.
And we’ll take a look at it in the next clip.
So now we’re going to make a new class, a new class called inorder iterator of T.
Also, because our node is generic, we have to have this thing generic as well.
So here we will have a few critical members.
So the first critical member is node of T called current and this indicates the current node or the
node to which the iterator points.
We will also have a constructor in the constructor we will take the root, so we’ll take node of T called
root and we’ll do something with it.
And then the critical methods of an iterator are first of all, move next public bool move next.
So move next attempts to move you to the next element being iterated and it returns a boolean indicating
whether that operation succeeded.
So if you’re in the final element, this movenext will return false.
But if there is a way to go, it moves to the next element in the right order and it returns a true.
So that’s what we’re going to build.
That’s the API.
You can add additional methods here.
Like for example, you can add, let’s say a reset method.
So you can add a reset method which would reset the iterator back to the starting position.
So now the question is, well, how do we implement this?
And clearly from the outset you can see that we’re going to have a lot of problems here and we’re going
to have a very unpleasant implementation because you’re probably used to yield return and recursive
operations and all the rest of it.
Well, if you’re building an iterator like this and I have to say, this is more of a C plus plus way
of building iterators, then unfortunately, it’s going to be a bit ugly.
So first of all, we want to store the root somewhere.
So we’ll introduce.
Field called Route.
But in addition, we actually want to immediately set the current pointer or the current reference,
this reference to the starting element being iterated.
So how do we do that?
Well, we find the leftmost element.
That’s how you start with inorder traversal.
So what we say essentially is we say while actually first of all, we assign current to root as well,
current equals root.
There we go.
And then we traverse on the current to the leftmost element.
So we say while current dot left is not equal to no current equals current dot left.
So if you can imagine if we are on a tree which looks like this, so we have one and then we have two
and three down here, two and three, then what’s happening is this value.
The value of one actually happens to be the root.
But because of our manipulations, we have immediately set the value two to be the current.
So two is current right now and one is root.
And the idea when we do move next is we first of all pretend that we move to the second element, the
element two, then we move to one, then we move to three, and then we return false.
So that’s the sequence of operations.
And for this to be possible, because the typical setup with Movenext goes something like this, you
say something like, First of all, you make the actual iterator, so var it equals new in order iterator
once again of type int And here you specify the root and then you say something like this while it dot
move.
Next you perform some operation on the iterator, get the current value and do something with it.
So move next on its first execution has to return whatever current points to.
And for that we’re going to have an additional flag as to whether or not we yield the start value.
So I’m going to have here private boolean yielded start equals.
Well, we don’t have to set it to false.
It’s false by default.
So now that we have this kind of value, what we can do is move.
Next is we can check whether we’ve yielded the starting value.
And if we haven’t, then let’s just return.
True, because current already points to the starting value.
So we can say if we haven’t yielded the starting value, then let’s set yielded start to true.
Let’s set it to true and then return true because we can in fact yield an element.
So here the true or false indicates whether the element currently pointed to is actually is is valid
in actual fact, because we can we can sort of move past the the iteration point and yield the null
or something to that effect.
So here we’re saying, yeah, it’s an okay element.
Now that we have yielded the top element, what we need to do is we need to go into the other elements.
And the way this is done is quite complicated.
Once again, since we’re not using enumerables and yield return and all the rest of it, what we do
is we check whether the right part of the current node is available, and if it is, then we go to the
right part and navigate all the way to the left part.
So it looks something like this.
If current dot right, actually let’s do current right.
Not so if current right is not equal to null, we set current equals current dot.
Right.
And then of course, we make a big while loop where we check current left against Null.
And while it’s not null, we set current equals current dot left.
And then of course we return.
True.
So we’ve navigated to the leftmost node of the right part of the tree.
If there was in fact a right part of the tree.
Otherwise we do an even more complicated operation.
And here what we do is we set the parent so we make a variable for the parent.
We say current parent.
Because now we have to navigate up the tree and then we say, while parent is not equal to null and
current is equal to parent dot, right.
What we do is we basically set current to the parent current equals P, and then P gets assigned to
its own parent.
P equals P dot parent.
So we’re trying to walk up the parent stack and when we have done so, we set current equals P and then
we return.
And here is the question what kind of value do we return?
Now we can walk up the stack to the point where current actually ends up being null, and that’s the
terminating condition for our whole iteration.
So we return current not equal to null, and that is the implementation of our in-order traversal.
As you can see, it looks ugly.
I mean, it’s nowhere near as intuitive as you want it to be.
There is lots of this weirdness with the temporary variable and whatever.
I can’t read it.
I mean, I know what it does, but it’s not nice.
So what we’re going to do is we’re going to use this implementation of Movenext and we’re actually going
to output the current value being iterated.
We’ll put a comma in between them and we’ll put a line break at the end.
So I’m going to write it dot current dot value.
So that’s the current value being pointed to by the iterator.
I’m going to write a comma here like so and then I will write a line to terminate the line.
So let’s see if what we’ve just built actually works.
Hooray.
So we get the right iterations, we get to one and three.
So what I’ve just illustrated and you can also add additional things here, like for example, if you
want to reset the iterator, for some reason you just set current equal to root and then you say yielded
start equals false.
Now what I’ve just implemented here is the way in which iterators actually work under the hood in systems
like the.
Net framework.
So in the c sharp language, this is how the for each statement works.
It just does move next while move next, please yield the current value.
So I’ve implemented this by hand, but I’ve also given you a taste of just how ugly in order traversal
is.
And it shouldn’t be like this in order traversal should be recursive and unfortunately we cannot realistically
do recursion here.
So we’re going to do recursion on the next demo and we’re going to move away from this idea of having
a separate object being the iterator because the C sharp language builds a state machine specifically
for this.
So there is no point in making our own iterators of this particular form.
This is the C plus plus style of doing things.
And luckily in the C sharp language, things are a lot better.
Play Stop Play Play Play Start Play information alert