A skip list container class in Python

The _SkipListIterator class is used to represent an iterator that walks down a skip list. It has one piece of internal state: a pointer to the _SkipItem instance that marks the next item, or to the terminator instance if there are no more items.

It has only three methods, a constructor and the .__iter__() and .next() methods required for Python iterators. The .__iter__() method just returns the instance; without this method, you can't use this object in constructs like “for k in ...”.

# - - - - -   c l a s s   _ S k i p L i s t I t e r a t o r   - - - - -

class _SkipListIterator:
    """Represents an active iterator over a SkipList object.

      Exports:
        _SkipListIterator ( skipItem ):
          [ skipItem is a _SkipItem ->
              return a new iterator whose next item is skipItem,
              or which is at end of list if skipItem's forward
              link points to itself ]
        .skipItem:
          [ if self is exhausted ->
              a terminator _SkipItem
            else ->
              a _SkipItem containing the value that will be returned
              next time ]
        .__iter__(self):    [ returns self ]
        .next():
          [ if self.skipItem's level-0 link is None ->
              raise ValueError
            else if self.skipItem.links[0] == self.skipItem ->
              raise StopIteration
            else ->
              self.skipItem  :=  self.skipItem.links[0]
              return self.skipItem.child ]  # *Before* advancing!
    """

# - - -   _ S k i p L i s t I t e r a t o r . _ _ i n i t _ _   - - -

    def __init__ ( self, skipItem ):
        """Constructor for _SkipListIterator"""
        self.skipItem  =  skipItem

# - - -   _ S k i p L i s t I t e r a t o r . n e x t   - - -

    def next ( self ):
        """Return the next child item and advance"""
        if  self.skipItem.links[0] is None:
            raise ValueError, "Iterator points to a deleted item."
        elif  self.skipItem.links[0] is self.skipItem:
            raise StopIteration
        else:
            result  =  self.skipItem.child
            self.skipItem  =  self.skipItem.links[0]
            return result

In order for a _SkipListIterator object to qualify as an iterator, and be useable in contexts such as “for k in S”, the object must have a special .__iter__() method that returns the iterator.

# - - -   _ S k i p L i s t I t e r a t o r . _ _ i t e r _ _   - - -

    def __iter__ ( self ):
        """Returns the iterator itself."""
        return self