A skip list container class in Python |  |
A skip list container class in Python | |
Starting with version 2.2, the Python language now supports a powerful new concept called the iterator.
An iterator is just an object that keeps track of a
position within some sequence. The only requirement is
that it have a .next() method
that, when called:
If there are any elements left in the sequence, the method returns the next element in the sequence, and the iterator also advances its own internal state to point to the following item, if there is one.
When the sequence is exhausted, the method raises
the StopIteration exception
to signal that no more elements remain.
Some container classes return themselves as the result of
the .__iter__() special method, so
that the required .next() method
uses some internal state stored inside the container
class instance. However, the drawback to this approach
is that you can't have two or more iterators pointing at
different places in the sequence at the same time.
When we want to return a pointer at a position within a
SkipList object, we can do so by pointing at a _SkipItem object.
When we need to advance through the rest of the sequence,
we can just follow the forward links in that object.
This means there can exist two or more iterators walking
through a skip list at the same time.