A skip list container class in Python

This routine locates the predecessor of the first item after a given point that is before the given key value.

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

    def __searchPoint ( self, searchItem, level, key ):
        """Search one level of the skip list for a given key.

          [ ( level is in [0,self.__maxLevels ) ) and
            ( search-precedes ( searchItem, key ) ) ->
                return search-point-after ( level, key,
                searchItem ) ]
        """

First we set the local variables prevItem and nextItem to the item where we start, and its successor, respectively.

        #-- 1 --
        # [ prevItem  :=  searchItem
        #   nextItem  :=  successor of searchItem in (level)th list ]
        prevItem  =  searchItem
        nextItem  =  searchItem.links[level]

Then we move both these variables down the linked list at the given level so long as nextItem still precedes the key we're searching for. See Section 4.20, “SkipList.__searchPrecedes()”.

        #-- 2 --
        # [ if nextItem is not self.__heads ->
        #     if search-precedes ( nextItem, key ) ->
        #       prevItem  :=  last item E in nth-list(nextItem, level)
        #                     such that search-precedes(E, key) is true
        #       nextItem  :=  <anything>
        #     else -> I ]
        while self.__searchPrecedes ( nextItem, key ):
            prevItem  =  nextItem
            nextItem  =  nextItem.links[level]

Finally, we return the predecessor item.

        #-- 3 --
        return prevItem